Разработка отказоустойчивого спецпроцессора цифровой обработки сигнала, функционирующего в полиномиальной системе классов вычетов Саркисов Артём Брониславович

Содержание к диссертации

Введение

Глава 1. Анализ отказоустойчивых вычислительных систем цифровой обработки сигналов. Разработка и постановка задачи диссертационных исследований 21

1.1 Основные сферы применения методов и алгоритмов цифровой обработки сигналов 21

1.2 Разработка и исследование математической модели отказоустойчивой вычислительной системы цифровой обработки сигналов 27

1.3 Основные сферы применения системного анализа 33

1.4 Системный анализ альтернатив повышения скорости цифровой обработки сигналов 35

1.5 Системный анализ альтернатив повышения отказоустойчивости вычислительных систем цифровой обработки сигналов 42

1.6 Математическая постановка задачи исследований 47

Выводы 51

Глава 2. Разработка нейросетевых алгоритмов выполнения модульных операций в коде ПСКВ 54

2.1 Принципы работы отказоустойчивой вычислительной системы цифровой обработки сигнала в ПСКВ 54

2.2 Разработка нейросетевого алгоритма многоразрядного сложения по модулю два 56

2.3 Разработка алгоритма выполнения модульной операции умножения по модулю 63

Выводы 69

Глава 3. Разработка алгоритмов выполнения немодульных операций для спецпроцессора ЦОС класса вычетов 70

3.1 Прямое преобразование из позиционной системы счисления в полиномиальную систему классов вычетов 70

3.2 Обратное преобразование полиномиального кода классов вычетов в позиционный код 76

3.3 Разработка алгоритма расширения системы оснований ПСКВ и его схемная реализация 79 3.4 Разработка алгоритма коррекции ошибок в кодах ПСКВ на основе расширения числа оснований 83

Выводы 88

Глава 4. Разработка отказоустойчивой параллельной системы цифровой обработки сигналов с реконфигурируемой структурой 90

4.1 Метод реконфигурации непозиционной системы ЦОС, базирующийся на обменных операциях 90

4.2 Разработка алгоритма пересчета ортогональных базисов при перераспределении вычислительной нагрузки в условиях отказов 95

4.3 Разработка параллельной непозиционной системы цифровой обработки сигналов с реконфигурируемой структурой 105

Выводы 119

Заключение 122

Список литературы 126

Приложения 143

• Разработка и исследование математической модели отказоустойчивой вычислительной системы цифровой обработки сигналов
• Разработка нейросетевого алгоритма многоразрядного сложения по модулю два
• Разработка алгоритма коррекции ошибок в кодах ПСКВ на основе расширения числа оснований
• Разработка параллельной непозиционной системы цифровой обработки сигналов с реконфигурируемой структурой

Введение к работе

Актуальность проблемы и направление исследований

В последние годы наблюдается тенденция по более широкому применению методов цифровой обработки сигналов (ЦОС) в самых разных сферах. Использование методов ЦОС позволяет достичь хороших показателей в области обеспечения помехоустойчивости связи, обеспечивая при этом достаточно простое и надежное сопряжение подсистем первичной и вторичной обработки сигналов. Кроме того, применение методов ЦОС способствует максимальному извлечению данных из принятого сигнала, подверженного воздействию помех.

Однако сфера применения методов ЦОС оказывает существенное воздействие на показатели качества обработки сигналов, то есть – на скоростные и точностные параметры специализированых процессоров (СП), используемых в цифровой обработке сигналов. Так как задачи ЦОС требуют выполнения больших объемов вычислений над большими массивами данных в реальном масштабе времени, то это приводит к тому, что СП ЦОС используют многоядерные гетерогенные платформы, MIMD-типа. Однако это негативно сказывается на надежность таких систем. При этом среднее время ликвидации последствий сбоев и отказов в работе СП ЦОС превышает на несколько порядков среднюю продолжительность выполнения одной задачи.

Таким образом, налицо следующее противоречие. Повышение

требований к производительности специализированных СП ЦОС, с одной
стороны, требует от разработчиков все шире применять параллельные методы
цифровой обработки сигналов, а с другой стороны, при этом снижается
надежность работы таких СП ЦОС из-за увеличения частоты возникновения
отказов и сбоев, которое приводит к выходу из строя такой

специализированной системы ЦОС.

Эффективно решить такое противоречие возможно, если обеспечить устойчивость к отказам для параллельных СП ЦОС. В этом случае при возникновении отказа спецпроцессор сохраняет возможность выполнять свой функционал, но при снижении в допустимых пределах показателей качества. Другими словами, такая вычислительная система ЦОС при возникновении потока отказов будет постепенно реконфигурировать свою структуру, что приведет к снижению ее эффективности, но в допустимых пределах. Поэтому в диссертационной работе будет рассмотрен такой вид отказоустойчивости для СП ЦОС. Поэтому разработка отказоустойчивых специализированных процессоров ЦОС, осуществляющих цифровую обработку сигналов в реальном масштабе, является актуальной задачей.

Актуальность обеспечения отказоустойчивости параллельных

вычислительных систем ЦОС привело к появлению большого количества исследований в данной сфере. Проведенный анализ работ, позволил выделить три основных подхода к решению данной задачи.

В основу первого подхода обеспечения свойства к отказам положены методы и алгоритмы, которые используют аппаратную избыточность. Такой подход позволяет обеспечить гарантию непрерывности функционирования параллельного СП ЦОС во время его работы. Как правило, в таких методах

используется (2М-1)-кратная избыточность (М=2,3...) вычислительной системы с последующим маскированием отказа. Другая альтернатива повышения отказоустойчивости параллельного СП ЦОС базируется на методах структурного резервирования.

Альтернативные методы обеспечения отказоустойчивости СП ЦОС, входящие во вторую группу, используют временную избыточность. Как правило, в основу применения методов обеспечения отказоустойчивости ВС ЦОС положены достоинства, которые предоставляет параллельно-конвейерная организация вычислений.

Альтернативными решения обеспечения отказоустойчивости СП ЦОС являются методы и алгоритмы, которые используют информационную избыточность. Основу таких методов составляют корректирующие коды. Альтернативой позиционным помехоустойчивым корректирующим кодам выступают АN-коды, которые можно применять для проверки выполнения арифметических операций. Следует отметить, что эти коды отличаются от комбинационных корректирующих кодов, тем, что избыточные разряды получаются с использованием арифметических операций.

В качестве альтернативного решения, позволяющего повысить
отказоустойчивость СП ЦОС, можно отметить применение корректирующих
модулярных кодов, в том числе кодов полиномиальной системы классов
вычетов (ПСКВ). Значительный научный вклад в теорию построения

модулярных непозиционных кодов внесли как отечественные, так и зарубежные ученые, среди которых можно выделить: И.Я. Акушский, Д.И. Юдицкий, В.М. Амербаев, Н.И. Червяков, А.А. Коляда, И.Т. Пак, Торгашев, И.А. Калмыков, О.А. Финько, Д. Свобода, N. Szabo, M. Valach, H.L. Garner, A.S. Fraenkel, A. Huang, B. Purhami, W. Ienkns, H. Krisha, A. Omondi, A. Premkumar, Sousa и другие. Высокая скорость обработка сигналов в таких системах определяется независимой и параллельной обработкой малоразрядных остатков по основаниям кода. Равноправность остатков модулярных кодов служат базисом для выполнения реконфигурации СП, которая является эффективных методом борьбы с последовательностью возникающих отказов.

Таким образом, очевидно, что наличие достаточно большого набора альтернатив, позволяющих повысить как скоростные, так и надежностные показатели специализированных процессоров ЦОС, не позволяют впрямую найти эффективное решение. Обеспечить эффективное решение такой задачи возможно только за счет использования математического аппарата системного анализа (СА). Использование методов СА позволит провести количественный сравнительный анализ альтернатив, что позволит в конечном итоге осуществить выбор наиболее выгодной альтернативы. Такая выбранная альтернатива позволит обеспечить эффективное решение полученного противоречия между обеспечением максимальной производительности и отказоустойчивости СП ЦОС.

Объектом диссертационного исследования является специализированные процессоры цифровой обработки сигналов, выполняющие ортогональные преобразования сигналов в реальном масштабе времени.

Целью диссертационной работы является повышение

отказоустойчивости спецпроцессоров цифровой обработки сигналов, за счет применения корректирующих модулярных кодов полиномиальной системы классов вычетов и реконфигурации структуры СП ЦОС.

Предметы исследования:

математический аппарат решения задач СА при разработке отказоустойчивых СП ЦОС, способных сохранять работоспособное состояние путем реконфигурации структуры;

методы и алгоритмы структурно-параметрического синтеза нейросетевых реализаций модульных и немодульных операций, выполняемых полиномиальными кодами ПСКВ;

алгоритмы и методы повышения надежности высокоскоростных СП ЦОС, использующие корректирующие модулярные коды.

Научная задача диссертационных исследований состоит в применении математического аппарата СА при разработке отказоустойчивого специализированного СП ЦОС класса вычетов, способного сохранять работоспособное состояние при возникновении потока отказов за счет реконфигурации своей структуры.

Для решения поставленной общей научной задачи была проведена ее декомпозиция на ряд следующих частных задач:

1. На основе постановки задачи системного анализа синтеза отказоустойчивой спецпроцессора цифровой обработки сигналов, функционирующей в кольце полиномов, провести разработку нейросетевых алгоритмов выполнения модульных операций в кольце полиномов, позволяющих сократить схемные затраты на реализацию операции.

2. Реализация нейросетевых алгоритмов выполнения немодульных операций ПСКВ, позволяющих сократить их схемные и временные реализации.

3. Разработка алгоритма, позволяющего проводить поиск и коррекцию ошибок с использованием избыточных кодов ПСКВ и его схемная реализация.

4. Разработка алгоритма ускоренного пересчета ортогональных базисов при реконфигурации структуры СП ЦОС, применение которого позволит сохранять работоспособное состояние вычислительного устройства путем снижения показателей качества при возникновении потока отказов.

Методы исследования. В ходе выполнения поставленных в диссертационной работе научных задач, были применены методы системного анализа, теории цифровой обработки сигналов, теории конечных полей, теории кодирования, теории нейронных сетей.

Научная новизна диссертационной работы:

5. Разработаны нейросетевые алгоритмы выполнения операций умножения и сложения по модулю в кодах ПСКВ, характеризующиеся меньшими схемными затратами по сравнению с ранее известными.

6. Проведено усовершенствование нейросетевого алгоритма выполнения немодульной операции расширения оснований кода ПСКВ, характеризуемый меньшими схемными затратами.

3. Разработан алгоритм поиска и коррекции ошибок кодов ПСКВ, на основе расширения системы оснований, схемная реализация которого позволяет исправлять ошибки при меньших схемных затратах.

4. Разработан алгоритм пересчета ортогональных базисов, применение которого позволит сократить схемные затраты на проведение реконфигурации ВС ЦОС при возникновении последовательности отказов.

Практическая значимость результатов данной работы:

1. В ходе выполнения диссертации проведена разработка нейросетевых устройств, предназначенных для выполнения модульных и немодульных операций, позволяющих выполнять эти операции в реальном масштабе времени при меньших схемных затратах. Данные устройства могут быть использованы при разработке параллельных отказоустойчивых СП цифровой обработки сигналов.

2. Разработан алгоритм расширения оснований ПСКВ, применение которого позволит создавать СП ЦОС класса вычетов, способных обеспечить более высокую точность вычислений за счет расширения динамического диапазона обрабатываемых операндов.

3. Использование разработанного алгоритма обнаружения и коррекции ошибок на основе расширения системы оснований позволяет создавать отказоустойчивые СП ЦОС, способные исправлять ошибки, возникающие в процессе функционирования.

4. Произведена разработка структуры отказоустойчивой специализированной параллельно-конвейерной СП ЦОС, функционирующей в кольце полиномов и способной сохранять работоспособное состояние при возникновении отказов за счет реконфигурации структуры.

Основные положения, выносимые на защиту:

5. Нейросетевые алгоритмы выполнения модульных операций в кодах ПСКВ, которые требуют меньших схемных затрат по сравнению с известными за счет изменения функций активации нейронов.

6. Алгоритм выполнения немодульной операции расширения оснований кода ПСКВ, который позволяет сократить схемные затраты за счет совмещения операции вычисления ранга и ортогональных базисов ПСКВ при использовании нейронной сети.

7. Алгоритм поиска и коррекции ошибок кодов ПСКВ, использующий расширение системы оснований, схемная реализация которого позволяет обнаруживать и исправлять ошибки при меньших схемных затратах по сравнению с ранее известными.

8. Алгоритм пересчета ортогональных базисов, применение которого позволит сократить схемные затраты на проведение реконфигурации ВС ЦОС при возникновении последовательности отказов за счет использования индексного представления элементов кода ПСКВ

Достоверность и обоснованность полученных результатов

обеспечивается строгостью производимых математических выкладок, которые были получены с помощью научно-методического аппарата системного анализа,

теории цифровой обработки сигналов, теории конечных полей, теории кодирования,
теории нейронных сетей. Справедливость полученных научных результатов
относительно эффективности разработанных алгоритмов повышения

отказоустойчивости СП ЦОС подтверждена сравнением с существующими.

Авторский вклад в разработку. Все изложенные в диссертационной работе результаты были получены при непосредственном участии автора. В качестве личного авторского вклада можно выделить разработку нейросетевых алгоритмов выполнения операций умножения и сложения по модулю, алгоритм выполнения немодульной операции расширения оснований кода ПСКВ, алгоритм обнаружения и коррекции ошибок в коде ПСКВ, использующий расширение оснований, алгоритм пересчета ортогональных базисов, используемый при реконфигурации СП ЦОС.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на следующих научных конференциях: V международная НТК «Инфокоммуникационные технологии в науке, производстве и образовании», Ставрополь: Северо-Кавказский государственный технический университет, 2012; всероссийская молодежная конференция «Теория и практика системного анализа», Белгород: Белгородский государственный национальный исследовательский университет, 2012; XIII всероссийская научная конференция «Высокопроизводительные параллельные вычисления на кластерных системах», Нижний Новгород, 2013; VII международная научная конференция СКФУ «Научный потенциал XXI века», Ставрополь, 2013; I международная научно-техническая конференция «Параллельная компьютерная алгебра и её приложения в новых инфокоммуникационных системах», Ставрополь. СКФУ, 2014; I всероссийская научно-техническая конференция «Фундаментальные и прикладные аспекты компьютерных технологий и информационной безопасности» – Ростов-на-Дону, ЮФУ, 2015; I - III всероссийская научно-техническая конференция «Студенческая наука для развития информационного общества», Ставрополь, Северо-Кавказский федеральный университет, 2014, 2015 и 2016.

Результаты диссертационной работы были использованы при выполнении проекта гранта РФФИ № 16-37-50032_мол_нр «Разработка методов и алгоритмов обеспечения отказоустойчивости систем цифровой обработки сигналов на основе использования многоверсионности непозиционных модулярных кодов».

Внедрение. В диссертационной работе изложены результаты

исследований, выполненных в 2013 – 2017 годах.

Согласно акта о внедрении, основные результаты диссертационного
исследования были внедрены в ООО «Инфоком-С». В ходе выполнения
научно-исследовательского проекта по теме «Разработка средств

высокоскоростной обработки данных информационных сенсоров в системах ситуационного управления» в рамках федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014—2020 годы» (уникальный

идентификатор RFMEFI57916X0135), реализуемого при поддержке

Министерства образования и науки Российской Федерации.

Отдельные результаты диссертационного исследования вошли в состав
результатов указанного научно-исследовательского проекта и явились основой
для разработки математических методов и алгоритмов в составе технологии
высокоскоростного сбора и обработки данных от информационных сенсоров.
Апробация результатов диссертационного исследования проводилась в ходе
разработки и экспериментальных исследований программного комплекса
ситуационного управления при реализации модулей первичной обработки
сигналов системы сбора и параллельной обработки данных от

информационных сенсоров, что позволило снизить схемные затраты на реализацию модулей и повысить их отказоустойчивость.

Согласно акта о внедрении, результаты диссертационного исследования были внедрены в учебный процесс СКФУ.

Публикации. По теме диссертации опубликовано 28 работ в журналах и трудах конференций, из них 3 работы – в изданиях, рекомендованных ВАК РФ для опубликования научных положений диссертационных работ, 1 работа – в базе SCOPUS, получено 4 патента на изобретения и издана одна монография.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 169 наименования и 3 приложений. Общий объем 168 страниц.

Разработка и исследование математической модели отказоустойчивой вычислительной системы цифровой обработки сигналов

В настоящее время методы и алгоритмы цифровой обработки сигналов находит широкое применение в самых различных сферах. Очевидно, что эффективность выполнения ЦОС во многом определяется специализированной вычислительной системой, которая реализует соответствующий алгоритм цифровой обработки сигналов. При этом на выбор соответствующего метода и алгоритма цифровой обработки сигналов оказывают влияние множество параметров. В качестве основных параметров можно выделить [14,109]:

- тип источника сигнала;

- среда распространения цифровых сигналов;

- алгоритмы и способы передачи сигнала;

- полоса частот передаваемого сигнала в частотном диапазоне;

- динамический диапазон передаваемого сигнала; требуемая разрешающая способность ВС ЦОС.

Наиболее наглядно это проявляется в системах радиосвязи. Так как параметры передаваемого сигнала w по радио каналу во многом зависят от множества различных параметров w , то принимаемый сигнал будет пред-ставлять собой некоторую суперпозицию

При распространении сигнала по радио каналу параметры данного канала оказывают влияние на передаваемый сигнал. Поэтому введем функцию е, с помощью которой можно описать все изменения параметров сигнала связанные с характеристиками среды распространения. Тогда выражение (1.1) можно представить в виде

Последнее равенство позволяет оценить влияние линии связи на параметры передаваемого сигнала вдоль всей траектории его прохождения.

Таким образом, параметры сигнала на входе приемника во многом будут зависеть от параметров передаваемого сигнала. Значит принятый сигнал представить, как некоторую функцию G, в которой в качестве аргументов можно использовать параметры передаваемого сигнала. Тогда получаем

Для максимального извлечения информации из принятого сигнала w необходимо провести эффективную обработку сигнала, поступившего на вход приемника. Очевидно, что такая обработка будет представлять собой функцию обратную функции G. Значит система цифровой обработки сигналов должна реализовать эту процедуру согласно

Очевидно, что от соответствующего выбора метода и алгоритма цифровой обработки сигналов во многом будет зависеть эффективность обработки принятого сигнала.

Так как извлечение максимального количества информации из принятого сигнала является достаточно сложной процедурой при реализации в виде одного этапа, то на практике, предлагается проводить ее в два этапа [14]. Такой системный подход позволяет осуществить уменьшение вычислительной нагрузки на подсистемы ЦОС, а также снизить аппаратурные затраты. В основу такого подхода положено деление процедуры обработки поступившего на вход приемника сигнала на два последовательных этапа. На первом этапе в системе ЦОС выполняется первичная обработка сигнала. На втором этапе в системе ЦОС проводится применение методов и алгоритмов, позволяющих осуществить идентификацию такого сигнала.

Рассмотрим более подробно каждый из этапов обработки принятого сигнала системой ЦОС. На вход подсистемы, которая предназначена для выполнения первичной обработки сигнала, поступает сигнал х (t), который состоит из передаваемого сигнала х (пТ ), шума A (t) и случайных помех различного

Анализ выражения (1.5) показывает, что A (t) представляет собой ха-рактеристику самой вычислительной системы ЦОС. А третье слагаемое A (t) выражения (1.5) используется для описания воздействия помех на сигнал, которые возникают при прохождении сигнала по линии связи.

Поэтому на подсистему первичной обработки сигнала возлагаются задачи, которые связаны с обнаружением и выделением полезного сигнала. При этом такая цифровая обработка исходного сигнала, который представлен в виде совокупности цифровых отсчетов, производится на фоне случайных помех. При этом такие помехи могут иметь различную физическую природу. Тогда процедуру первичной обработки сигнала можно представить в виде

Как правило, в качестве алгоритмов первичной цифровой обработки сигналов используются [14,46,47,51,158,159,169]:

- ортогональные преобразования сигналов;

- процедуры линейной алгебры;

- линейная цифровая фильтрация;

- нелинейная цифровая фильтрации.

Результатами применения данных основных процедур первичной цифровой обработки сигналов могут стать следующие процедуры:

- поиск и выделение передаваемого сигнала на фоне шумов;

- уменьшение избыточности передаваемого сигнала путем сжатия;

- вычисление спектральных составляющих принятого сигнала;

- определение основных фазовых параметров принятого сигнала;

- вычисление энергетических параметров принятого сигнала.

В результате проведения процедур первичной обработки принятого сигнала будут получены определенные характеристики сигнала, которые затем поступают на вход подсистемы вторичной обработки сигналов. Данная подсистема цифровой обработки сигналов может быть описана

Разработка нейросетевого алгоритма многоразрядного сложения по модулю два

В работе [104] показано, что независимо от типа базовых процедур и сферы применения системы модулярной обработки информации выполняют однотипные вычислительные процедуры. Таким образом, предлагается представить непозиционные спецпроцессоры в виде двухкаскадной модели. В первый каскад предлагается объединить модульные операции, а во второй - немодульные операции. При этом для построения эффективной системы модулярной обработки информации необходимо решить ряд оптимизационных задач. В работе [104] в качестве таких задач были выделены:

- выбор и синтез требуемых модульных и немодульных операций, позволяющих в максимальной степени достичь поставленных целей и результатов;

- оценка мощности диапазона разрабатываемой системы модулярной обработки информации, которая определяется мощностью исходных данных, разрядностью применяемых констант, используемых при решении задач;

- выбор модулей непозиционной системы счисления, применение которых позволит эффективно обеспечить требуемые точностностные характеристики системы обработки информации.

Очевидно, что эффективность функционирования системы модулярной обработки информации во многом будут определяться алгоритмами выполнения как немодульных операций, которые характеризуются значительными схемными и временными затратами, но и модульных операций. Так как большинство применяемых немодульных опера сводится к множеству последовательных модельных процедур, то разработка новых алгоритмов выполнения операций сложения и умножения по модулю p(z), позволит оптимизировать режим организации немодульных процедур. Поэтому разработка новых алгоритмов выполнения модульных операций является актуальной задачей.

Чтобы повысить эффективность применения модулярных кодов, в ряде работ было предложено использовать параллельную «элементную базу», которая базируется на нейронных сетях (НС) [99,100,101,103,104,166]. Известно, что НС имеют эффективное применение при решении задач, которые относятся к слабоформализуемых и неформализуемых задачам [13,18,90,127,128]. В качестве достоинства применения нейронных сетей отмечалось, что благодаря способности обучаться НС способны решать такие сложные задачи.

Однако нейронные сети имеют ярко выраженную параллельную структуру обработки данных. При этом они используют базовые операции { iT, sign }.

Но такие операции идентичны базовым операциям, которые применяются в алгоритмах и методах цифровой обработки сигналов. Значит между нейросете вым логическим базисом и задачами ЦОС наблюдается подобие. При этом такое же подобие наблюдается между модулярными кодами и нейронными сетями. Это связано с тем, что и модулярные коды и НС используют операции «сложение, умножение и вычитание». Соответствие нейронных сетей модулярным кодам достаточно полно раскрыто в работах [22,23,99,100,101,103,104,111,166]. Поэтому в диссертационной работе при разработке параллельных отказоустойчивых спецпроцессоров ЦОС будет применяться нейросетевой логический базис, как позволяющий в максимальной степени повысить эффективность кодов ПСКВ.

Одной из основных модульных операций ПСКВ является сложение по модулю характеристики поля GF (р), а так как спецпроцессор работает в двоичной системе счисления, то характеристика поля будет равной р = 2 . В связи с тем, что СП ПСКВ будет использовать нейросетевой базис, в диссертации был разработан нейросетевой алгоритм свертки входного вектора по модулю два.

Рассмотрим алгоритм работы трехслойной нейронной сети. Данная сеть содержит входной слой, скрытый слой и выходной слой нейронов. Нейроны входного слоя не участвует в вычислениях, а осуществляют перераспределение вектора Х = хпхп_!… X! на входы нейронов скрытого слоя. Оставшиеся два слоя предназначены для получения соответствующего отклика НС на этот сигнал. При использовании классической математической модели нейрона выполняется следующий алгоритм. На первом этапе вычисляется взвешенная сумма входного вектора согласно

Именно такой нейросетевой алгоритм положен в основу работы двухвхо-дового сумматора по модулю два, представленного в работе [20]. Используя данный сумматор, можно реализовать многовходовой сумматор по модулю два. Главным недостатком многовходового сумматора по модулю два, построенного на основе двухвходового нейросетевого сумматора и использующего каскадную реализацию, будут значительные схемные затраты.

В работе [108] представлена разработка алгоритма нейросетевого мно-говходового сумматора по модулю два, которая позволяет устранить данный недостаток, за счет использования функции активации «Tribas» в скрытом слое

Дальнейшая оптимизация структуры многовходового сумматора была показана в работе [26]. Чтобы осуществить уменьшение динамического диапазона весовых смещений и коэффициентов в данной работе предлагается произвести обучение НС сумматора с использованием мажоритарного генетического алгоритма с выделением доминанты. В доминанте, в качестве оператора отбора выступает линейное ринглирование, которое позволяет оценивать степень приспособленности особи не только положительными значениями. Однако использованием мажоритарного генетического алгоритма привело к ситуации, когда в качестве синаптических весов стали появляться отрицательные числа.

Очевидно, что наиболее перспективный путь, позволяющий оптимизировать нейросетевой алгоритм вычисления свертки входного вектора по модулю два, базируется на уменьшении количества этапов выполнения операции. В работе [69] представлен разработанный нейросетевой алгоритм, который имеет три этапа работы. Для этого была изменена функция активации «Tribas» в скрытом слое НС на функцию (стрелку Пирса). Это изменение позволяет отказаться в разработанном нейросетевом алгоритме от функции активации в входном слое. Кроме того, в разработанном алгоритме предлагается использовать синаптические веса w .., которые равны единице. Это позволяет исключить из схемы формального нейрона умножителей синаптических весов. Рассмотрим данный разработанный нейросетевой алгоритм:

1. Первый этап - подача на многовходовой сумматор по модулю два вектора [х1; х2,..., хп ] и вычисление взвешенной суммы нейронами скрытого слоя.

В этом случае значение взвешенной суммы равно

Разработка алгоритма коррекции ошибок в кодах ПСКВ на основе расширения числа оснований

В отличие от классических позиционных помехоустойчивых кодов модулярные непозиционные коды характеризуются многоверсионной избыточностью [22,33,74,76,80]. Данная многоверсионность наглядно проявляется в возможности модулярных кодов использовать различные подходы к процедурам обнаружения и коррекции ошибок. Это во многом зависит от выбранной позиционной характеристики, с помощью которых избыточные модулярные коды определяют местоположение и глубину ошибки. Данное свойство кода ПСКВ позволяет варьировать основными характеристиками вычислительных устройств ЦОС для обеспечения требуемого уровня отказоустойчивости.

Так как информация обрабатывается в параллельно функционирующих вычислительных каналах по числу оснований ПСКВ, то при возникновении отказов ошибка не может перейти в другой вычислительный канал. В основе разработанного метода обнаружения и коррекции ошибки предлагается по значениям информационных остатков (аДг),...., ak(z)) проводить вычисление контрольных остатков (a +1(z),...., a +r(z)) . После этого производится вычисление синдрома ошибки согласно

Если синдром равен, то это говорит о том, что данная комбинация не содержит ошибку. В противном случае - кодовая комбинация считается ошибочной. Реализация разработанного алгоритма расширения системы оснований для обнаружения и коррекции ошибок в избыточных кодах ПСКВ приведена [65].

В этом случае при использовании двух контрольных оснований pk+i(z) и Pk+2(z), удовлетворяющих условию

На основе представленных теоретических положений был разработан алгоритм расширения системы оснований, состоящий в следующем. Предварительно вычисляемые данные:

- значение рабочего диапазона Рраб (z) = \\ рДг);

- значение P_(Z) = p(z)/p.(z);

- значение веса ортогональных базисов nii(z), используемых в безизбы-точной системе ПСКВ, т.е. состоящей из рабочих оснований pi(z), …, pk(z), для которых справедливо

B.(z) = m.(z)P (z)/p.(z) = lmod p,(z);

- значения ортогональных базисов, умноженные на остатки кода ПСКВ, т.е. ос .(z)B.(z)mod Рраб (z) .

Входные данные: модулярный код полиномиальной системы классов вычетов, определяемый к+2 основаниями, A(z) = (a (z), a (z), ... ,a (z)) , где a .(z) = A(z)mod p.(z).

Выходные данные: два контрольных остатка по модулям Pk+i(z), Pk+2(z), удовлетворяющие at+i(z) = A(z)mod pt+1(z), и a t+2 (z) = A (z) mod pt+2(z), с помощью которых вычисляется синдром ошибки согласно (3.25).

Тело разработанного алгоритма расширений системы оснований:

1. Остатки исходного кода ПСКВ по рабочим основаниям A(z) = (a1(z),a2(z),...,at(z)) умножается значения веса ортогонального базиса nii(z) по модулю рi(z), где i=1, 2,…, п. В результате на выходе умножителя получается результат y.(z) = a.(z)m.(z)mod p_(z).

2. Вычисленные значения y;(z) умножаются на константу pi(z)mod pk+1 и константу p_(z)mod pk+2 по модулю Pk+i(z) и Pk+2(z) соответственно. В результате определяются значения (ai(z)Bi(z)mod Р (z)) mod р k + j (z), где j=l,2, т.е.

3. Вычисляется значение остатков по контрольным основаниям Pk+i(z) pk+2(z) согласно (3.27) (3.28) .

4. Вычисляется синдром ошибки, используя остатки по контрольным основаниям исходной комбинации (ak+1(z), ak+2(z)) и вычисленные на предыду щих этапах алгоритма (a k+1 (z), а к+2 (z)) , согласно

5. Определить вектор ошибки по величине полученного синдрома с использованием блока памяти (LUT-таблицы) и сложить с исходной комбинацией

Пример реализации алгоритма поиска и коррекции ошибок на основе расширения системы оснований ПСКВ приведен в Приложении Б.

Проведем сравнительный анализ разработанного алгоритма обнаружения и коррекции ошибок с алгоритмом, осуществляющим данную процедуру с использованием позиционной характеристики интервальный номер. Данная позиционная характеристика задается равенством

Однако операцию деление в ПСКВ нельзя выполнять. Поэтому в работе [22] приведен алгоритм, позволяющий вычислитель данную ПХ, используя модульные операции, а также подобие ортогональных базисов систем модулярных кодов с контрольными основаниями и без них где B;(z) и B (Z) - ортогональные базисы модулярных кодов ПСКВ с контрольными основаниями и без них.

Тогда, используя подобие ортогональных базисов, получаем B.(z) = R.(z)Pраб (z) + B (z) . (3.35)

Если модулярный код ПСКВ не содержит ошибку, то исходный полином А(z) лежит внутри рабочего диапазона. Значит интервальный номер будет равен нулю. Искажение остатка в коде ПСКВ приведет к тому, что полученный позиционный результат будет находиться вне рабочего диапазона. Об этом со общит интервальный номер, который будет L(z) Ф о . Для реализации рассмотренного алгоритма требуются схемные затраты, представленные в таблице 3.1. Таблица 3.1 - Схемные затраты для устройства вычисления (3.31)

Произведем аналогичные расчеты схемных затрат на реализацию разра ботанного алгоритма поиска и коррекции ошибок с использованием расширения оснований ПСКВ. Полученные данные сведены в таблицу 3.6.

Анализ таблиц 3.1 и 3.2 показывает, что разработанный алгоритм поиска и коррекции ошибок (3.31) при работе с полиномами пятой степени требует в 1,33 раза меньших схемных затрат, чем алгоритм вычисления интервального номера (3.36). Полученные результаты свидетельствуют о достаточно высокой эффективности разработанного алгоритма поиска и коррекции ошибок на основе расширения системы оснований.

Разработка параллельной непозиционной системы цифровой обработки сигналов с реконфигурируемой структурой

Произведем разработку параллельной непозиционной вычислительной системы цифровой обработки сигналов, которая будет способна обеспечивать работоспособное состояние при возникновении отказов за счет перераспределения вычислительной нагрузки между вычислительными каналами. Такой метод реконфигурации структуры позволит вычислительной системе классов вычетов быть в работоспособном состоянии при постепенном снижении большинства характеристик в пределах допустимых значений. То есть такая вычислительная система класса вычетов будет способна решать поставленные задачи при снижении в заданных пределах таких показателей как точность, скорость выполнения задачи, информационная надежность.

В настоящее время вычислительные системы на кристалле, которые ориентированы на выполнение алгоритмов цифровой обработки сигналов, работают как с фиксированной точкой, так и с плавающей точкой. При этом в системах с фиксированной точкой, как правило, преобладают разрядности 16 или 32. В системах ЦОС с плавающей точкой разрядность обрабатываемых данных равна 32 двоичным разрядам [96]. При выборе соответствующего формата данных необходимо учитывать все достоинства и недостатки каждого формата. Так использование фиксированного формата позволяет сократить схемные и энергетические затраты на реализацию. В качестве достоинства формата с плавающей точкой можно отметить больший динамический диапазон. Данное свойство достаточно важно в условиях, когда к точности проводимых вычислений предъявляются высокие требования.

Однако при реализации радиационно-стойкого сигнального процессора 1892ВМ8Я предлагается выполнение быстрого преобразования Фурье с использованием [96] разрядности входных данных равных 32, 16 и 8 бит. Таким образом, минимальная размерность входных данных, даже в настоящее время, при решении определенных задач ЦОС может составлять 8 бит.

При выполнении цифровой обработки сигналов в позиционной системе счисления могут возникнуть ситуации, когда использовать вычислительную систему на кристалле ЦОС с плавающей точкой невозможно. Такая ситуация может возникнуть из-за относительно высокой стоимости СнК или достаточно большого энергопотребления. В этом случае предлагается использовать СП ЦОС с фиксированной точкой. Но для обеспечения требуемой точности вычислений используется предварительное масштабирование данных. Однако такая компрессия данных возможно только за счет услужения алгоритма ЦОС. Поэтому для устранения данной сложной ситуации предлагается воспользоваться удвоенной разрядностью входного вектора при обработке данных. Однако такое решение также приводит к усложнению программы выполнения ЦОС и негативно влияет не скорость ЦОС.

Данных недостатков лишена вычислительная система ЦОС, функционирующая в модулярном коде, в частности, в полиномиальной системе классов вычетов. При реализации отказоустойчивой вычислительной системы на кристалле, реализующей ортогональные преобразования сигналов в кольце полиномов воспользуемся неприводимыми полиномами пятой степени. В качестве данных оснований ПСКВ выбираем многочлены Pl(z) = z5 + z3 + i, p2(z)=z +z +z +z + l, p3(z) = z +z +z +z + l, p4(z) = z +z +z +z + 1 .

Данные многочлены будут использованы в качестве информационных оснований ПСКВ. Тогда они обеспечат рабочий диапазон равный

Так как в качестве математической модели ЦОС предлагается использовать кольцо полиномов пятой степени, то при обработке входного вектора отсчетов предлагается применять прямоугольное окно размерностью равной N = зі отсчета. Использование такого окна позволит обеспечить достаточный уровень спектрального разрешения.

Оставшиеся два неприводимых полинома пятой степени будем использовать для обеспечения требуемого уровня информационной надежности выполнения поставленных задач ЦОС. Данные полиномы p5(z) = z5 + z2 + i и p6(z) = z5 + z3 + z2 + z + i позволят обеспечить коррекцию однократных ошибок, которые будут вызваны сбоями или отказами вычислительных каналов, определяемых основаниями ПСКВ. Это определяется свойством корректирующих кодов ПСКВ [22] и задается условием

При этом значение отсчетов входного вектора, а также поворачивающие коэффициенты должны быть представлены в виде остатков, которые определяются соответствующим основанием кода ПСКВ. В состав параллельной непозиционной вычислительной системы ЦОС входят модули:

- модуль прямого преобразования ПСС-ПСКВ;

- модуль целочисленного ортогонального преобразования сигналов в кольце полиномоврДг) ;

- модуль обратного преобразования ПСКВ-ПСС.

Так как данная вычислительная система классов вычетов должна обладать возможностью сохранять работоспособное состояние при отказах и сбоях, то в ее состав необходимо добавить модуль реконфигурации. С помощью данного модуля можно выполнять перераспределение вычислительной нагрузки между оставшимися в работе вычислительными каналами. Структура параллельной непозиционной вычислительной системы ЦОС с реконфигурируемой структурой показана на рисунке 4.5.

Для обеспечения более высокой скорости выполнения ортогональных преобразований сигналов предлагается использовать систолический принцип вычислений с ярусно-параллельной формой [27,48,49,125,155,156,157]. В этом случае вычислительная система ЦОС на кристалле будет представлять собой конвейер. При этом конвейер будет состоять из однотипных вычислительно-процессорных ячеек (ВПЯ). В каждой вычислительно-процессорной ячейке будут находиться регистры, сумматор и умножитель по модулю p i (z) . На рисунке 4.6 представлена структура такой вычислительно-процессорной ячейки. Такая реализация позволит использовать разработанные во второй главе нейросете-вые алгоритмы выполнения модульных операций в ПСКВ.

При реализации первого модуля - модуля прямого преобразования из ПСС в модулярный код ПСКВ воспользуемся результатами решения второй частной задачи исследований. Тогда на основе исследований, которые были проведены в третьей главе диссертации, для построения прямого преобразователя ПСС-ПСКВ целесообразно провести системный анализ основных методов выполнения этой немодульной операции.

Все множество алгоритмов преобразования из позиционного кода в непозиционный модулярный код можно разбить на три основные группы. В первую группу можно поместить алгоритмы преобразования ПСС-модулярный код, которые используют итерационный алгоритм понижения разрядности. Как было показано в третьей главе диссертации алгоритмы первой группы реализуют преобразования кода ПСС в остатки, используя классический позиционный сумматор. При этом такая процедура задается выражением (3.3). Основные недостатки алгоритмов прямого преобразования показаны в третьей главе диссертации.

Во вторую группу можно поместить алгоритмы преобразования ПСС-модулярный код, которые используют пространственно-временную реализацию итерационного алгоритма понижения разрядности. Как было показано в третьей главе диссертации алгоритмы второй группы реализуют преобразования кода ПСС в остатки, используя каскадное соединение позиционных сумматоров. Такая процедура задается выражением (3.5). Переход к пространственно-временному распределению вычислительного процесса вычисления остатка позволяет повысить скорость получения a;(z) = A(z)mod p;(z). Основным недостатком таких алгоритмов прямого преобразования можно считать значительные схемные затраты.

Третья группа алгоритмов прямого преобразования использует метод непосредственного суммирования. Построение нейросетевого преобразователя из кода ПСС в остаток ПСКВ можно выполнить на основе равенства (3.7). Тогда для построения прямого преобразователя в модулярный код можно воспользоваться разработанным нейросетевым алгоритмом выполнения многовхо-дового сумматора по модулю. Тогда каждый вычислитель остатка будет содержать пять многовходовых сумматоров по модулю два. При этом размерность входного векто ра будет равен deg (fj p;(z)) = 20 .

При построении модуля обратного преобразования вектора остатков в позиционный код воспользуемся преобразователем, структура которого приведена в работе [58]. В состав этого преобразователя уже входит блок, позволяющий осуществлять перерасчет значений ортогональных базисов при постепенной деградации структуры параллельной непозиционной вычислительной сети ЦОС. Представленные выше результаты исследований показали, что использование разработанного алгоритма пересчета значений ортогональных базисов позволило уменьшить схемные затраты в 1,19 раза по сравнению с использованием мультипликативным алгоритмом.

Осуществим сравнительную оценку влияния разработанных алгоритмов выполнения модульных и немодульных операций на повышение отказоустойчивости параллельной непозиционной вычислительной системы ЦОС. При этом сравнение будем проводить с классическим методом, который использует методы маскирования отказов. Кроме этого, в сравнительном анализе будет использоваться непозиционная ВС ЦОС, использующая корректирующие коды ПСКВ. Для проведения сравнительного анализа используем показатель, выбранный при постановке задачи исследования.

Данный показатель позволяет оценить через отношения количества работоспособных состояний вычислительной системы цифровой обработки сигналов к общему количеству возможных состояний способность ВС ЦОС противостоять возникающим отказам. Воспользуемся данным показателем, чтобы провести сравнительный анализ различных подходов построения отказоустойчивых вычислительных систем, используемых для выполнения задач ЦОС. Для проведения анализа эффективности разработанных алгоритмов выполнения модульных и немодульных операций при разработке устойчивых к отказам и сбоям параллельной непозиционной вычислительной системы ЦОС будем использовать следующие допущения. Минимальная точность обрабатываемых данных при постепенной деградации системы ЦОС составляет 15 разрядов. Количество последовательно поступающих отказов составляет множество а = {1, 2, з}. Корректирующие способности модулярного кода ПСКВ - возможность исправлять однократную ошибку.