Научный журнал
Международный журнал прикладных и фундаментальных исследований

ISSN 1996-3955
ИФ РИНЦ = 0,580

МЕТОД ВЫЧИСЛЕНИЯ ИНТЕРВАЛЬНОГО НОМЕРА В МОДУЛЯРНЫХ КОДАХ И ЕГО МОДИФИКАЦИЯ

Велигоша А.В. 1 Калмыков И.А. 1 Корниенко Р.С. 1 Ряднов С.А. 2
1 ФГАОУ ВПО «Северо-Кавказский федеральный университет»
2 Филиал Московского государственного университета приборостроения и информатики в городе Ставрополе
В настоящее время использование параллельных непозиционных кодов позволяет обеспечить максимальную производительность специализированных устройств, в частности спецпроцессоров цифровой обработки сигналов. При этом данные коды обладают потенциальной возможностью обнаруживать и корректировать ошибки, возникающие в процессе вычислений. Арифметичность избыточных модулярных кодов делает их привлекательными при построении отказоустойчивых вычислительных систем. Для коррекции ошибок в модулярных кодах используются позиционные характеристики, в частности, интервальный номер. В работе рассмотрены основные модификации вычисления данной позиционной характеристики, приведены аппаратные затраты на их реализацию.
параллельные вычисления
модулярные коды
коррекция ошибок
полиномиальная система классов вычетов
позиционные характеристики
интервальный номер
1. Katkov K.A., I.A. Kalmykov Application of Parallel Technologies in Navigation Management under the Conditions of Artificial Ionospheric Disturbances // World Applied Sciences Journal. – 2013. 26 (1). – Р. 108–113.
2. Kalmykov I.A., Katkov K.A., Naumenko D.O., Sarkisov A.B., Makarova A.V. Parallel modular technologies in digital signal processing // Life Science Journal – 2014. 11 (11s) – Р. 435–438; http://www.lifesciencesite.com.
3. Kalmykov I.A., Katkov K.A., Timoshenko L.I., Dunin A.V., Gish T.A. Application of modular technologies in the large-scale analysis of signals// Journal of Theoretical and Applied Information Technology. – 2015. – Vol. 80. № 3. – Р. 391–400; http://www.jatit.org/volumes/Vol80No3/2Vol80No3.pdf.
4. Калмыков И.А., Зиновьев А.В., Гахов В.Р. Применение систолических ортогональных преобразований в полиномиальной системе классов вычетов для повышения эффективности цифровой обработки сигналов // Инфокоммуникационные технологии. – 2010. – Т. 8. № 3. – С. 4–11.
5. Гапочкин А.В., Калмыков М.И., Айриян А.А. Коррекция ошибки в модулярном коде на основе алгоритма параллельного вычисления следа // Международный журнал экспериментального образования. – 2014. – № 8-3. – С. 34–38.
6. Гапочкин А.В., Калмыков М. И., Васильев П.С. Обнаружение и коррекция ошибки на основе вычисления интервального номера кода классов вычетов // Современные наукоемкие технологии. – 2014. – № 6. – С. 9–13.
7. Калмыков И.А., Саркисов А.Б., Калмыков М.И. Модулярный систолический процессор цифровой обработки сигналов с реконфигурируемой структурой // Вестник Северо-Кавказского федерального университета. – 2013. – № 2 (35). – С. 30–35.
8. Червяков Н.И., Калмыков И.А., Щелкунова Ю.О. Математическая модель нейронной сети для коррекции ошибок в непозиционном коде расширенного поля Галуа // Нейрокомпьютеры: разработка, применение. – 2003. – № 8-9. – С. 10–16.
9. Червяков Н.И., Калмыков И.А., Щелкунова Ю.О. Архитектура отказоустойчивой нейронной сети для цифровой обработки сигналов //Нейрокомпьютеры: разработка, применение. – 2004. – № 12. – С. 51–60.
10. Калмыков И.А., Резеньков Д.Н. Локализация ошибок в модулярных кодах полиномиальной системы классов вычетов // Фундаментальные исследования. – 2008. – № 3. – С. 75–76.

Использование параллельных модульных кодов позволяет не только повысить скорость обработки данных, но обеспечить свойство отказоустойчивости специализированным вычислительным устройствам, функционирующих в реальном масштабе времени. Среди модульных кодов занимают коды полиномиальной системе классов вычетов (ПСКВ). Данные коды, обладая свойством арифметичности, позволяют строить отказоустойчивые спецпроцессоры, которые способны сохранять работоспособное состояние за счет снижения в допустимых пределах основных показателей качества. Чтобы обеспечить коррекцию результата в кодах используют позиционные характеристики (ПХ), которые позволяют определить местоположение и глубину ошибки. Разработка и модификация методов вычисления позиционной характеристики – интервальный номер, позволят выполнять коррекцию результата при меньших аппаратных и временных затратах, что является актуальным.

В работе рассмотрен метод вычисления позиционной характеристики – интервальный номер. Данная позиционная характеристика позволяет осуществлять поиск и коррекцию ошибок в кодах ПСКВ. С целью снижения схемных затрат на реализацию проведены модификации этого метода. Разработанные модификации метода вычисления интервального номера в кодах ПСКВ позволили снизить схемные затраты на 3-5 % по сравнению с классическим методом уже при обработке 15-разрядных данных.

Параллельные непозиционные коды являются базой для построения отказоустойчивых специализированных вычислительных устройств, функционирующих в реальном масштабе времени [1-3]. Коды полиномиальной системе классов вычетов (ПСКВ), обладая свойством арифметичности, позволяют строить отказоустойчивые спецпроцессоры, которые способны сохранять работоспособное состояние за счет снижения в допустимых пределах основных показателей качества. Чтобы обеспечить коррекцию результата в кодах используют позиционные характеристики (ПХ), которые позволяют определить местоположение и глубину ошибки. Разработка и модификация методов вычисления позиционной характеристики – интервальный номер, позволят выполнять коррекцию результата при меньших аппаратных и временных затратах, что является актуальным.

В коде ПСКВ позиционный двоичный код, представляется в полиномиальной форме, а затем этому полиному в соответствие ставится набор остатков [4-6]

vel01.wmf, (1)

где vel02.wmf; pi(z) – неприводимые полиномы поля GF(2); i = 1,…, k.

Этот набор оснований кода ПСКВ образует рабочий диапазон системы

vel03.wmf, (2)

Так как сравнения по одному и тому же модулю можно почленно складывать, то для двух полиномов

vel04.wmf и vel05.wmf, справедливо

vel06.wmf, (3)

vel07.wmf, (4)

vel08.wmf. (5)

где + и vel09.wmf – операция суммирования и вычитания по модулю р.

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

Введение r контрольных оснований ПСКВ, которые должны удовлетворять условию

vel10.wmf

vel11.wmf, (6)

приводит к расширению рабочего диапазона до полного диапазона

vel12.wmf. (7)

В основу большинства алгоритмов и методов поиска и коррекции ошибок в модулярных кодах положена процедура вычисления позиционной характеристики. Поскольку ошибка переводит правильный vel13.wmf в полином vel14.wmf vel15.wmf, лежащий вне рабочего диапазона, то, зная номер интервала, куда попал искаженный полином vel16.wmf, можно определить основание, по которому произошла ошибка, а также ее глубину. Таким образом, для определения местоположения полинома, представленного кодом ПСКВ, требуется вычисление позиционной характеристики (ПХ). При этом немодульные операции определения ПХ необходимо заменить модульными операциями, которые успешно реализуются в модулярных кодах [6-10].

Данное свойство модулярных кодов и предопределило повышенный интерес разработчиков к позиционной характеристике – интервальный номер полинома lинт(z). Процесс определения данной характеристики осуществляется согласно выражения

vel17.wmf. (8)

Несмотря на то, что процедура (8) относится к немодульным, ее сводят к совокупности модульных операций. В работе [6] представлено устройство, осуществляющее обнаружение и коррекцию ошибки в модулярном коде на основе вычисления интервального номера. В основу данного алгоритма положено свойство подобия ортогональных базисов полной, содержащей контрольные основания, и безизбыточной ПСКВ, согласно которому

vel18.wmf, (9)

где Bi*(z) и Bi(z) – ортогональные базисы безизбыточной и полной системы.

Тогда имеем

vel19.wmf (10)

где vel20.wmf.

Подставив последнее равенство в выражение (8) получаем

vel21.wmf. (11)

где K(z) – ранг полной системы оснований ПСКВ.

Так как множество значений интервального номера lинт(z) представляет собой кольцо по модулю Pконт(z), то выражение (11) преобразуется к виду

vel22.wmf, (12)

где ранг безизбыточной системы определяется выражением

vel23.wmf. (13)

Если lинт(z) = 0, то исходный полином А(z) лежит внутри рабочего диапазона и не является запрещенным. В противном случае А(z) – ошибочная комбинация. В табл. 1 представлены номера интервалов, в которые попадают ошибочные полиномы Al*(z),при возникновении однократной ошибки по основаниям ПСКВ. При этом полиномы p1(z) = z + 1, p2(z) = z2 + z + 1 и p3(z) = z4 + z3 + z2 + z + 1 являются рабочими основаниями. В качестве контрольных оснований выбраны полиномы p4(z) = z4 + z3 + 1 и p5(z) = z4 + z + 1.

Таблица 1

Распределение однократных ошибок кода ПСКВ в GF(24)

Основание ПСКВ

Глубина ∆ai(z)

Интервал, представленный в полиномиальной форме

p1(z) = z + 1

1

z7 + z4 + z2 + z

p2(z) = z2 + z + 1

1

z7 + z5 + z2 + z + 1

z

z7 + z6 + z5 + z4 + z2

p3(z) = z4 + z3 + z2 + z + 1

1

z7 + z4 + z3 + z + 1

z

z7 + z3 + z + 1

z2

z7 + z5

z3

z7 + z6 + z5 + z4 + z3 + z + 1

p4(z) = z4 + z3 + 1

1

z7 + z4 + z3

z

z7 + z3 + z + 1

z2

z7 + z5 + z3 + z2

z3

z7 + z6 + z5 + 1

p5(z) = z4 + z + 1

1

z5 + z4 + z

z

z6 + z5 + z2

z2

z7 + z6 + z3

z3

z5 + z3 + z + 1

Очевидно, что по величине lинт(z) можно однозначно определить местоположение и глубину vel24.wmf ошибки. В табл. 2 представлены схемные затраты на реализацию алгоритма (12), используемого для вычисления интервального номера.

Таблица 2

Схемные затраты для устройства вычисления интервального номера при реализации алгоритма (12)

 

Разрядность сумматоров

GF(23)

GF(24)

GF(25)

Количество сумматоров

5

2

1

 

6

2

3

 

7

 

1

 

8

 

3

 

12

   

2

16

   

1

18

   

2

19

   

2

21

   

3

Количество нейронов с учетом первого слоя

17

52

139

Анализ выражения (12) показывает, что применение составного модуля Рконт(z), по которому определяется значение интервального номера lинт(z), с точки зрения аппаратурных затрат, является не самым оптимальным. Это обусловлено тем, что одномерные исчисления над кольцом ZРконт по формуле (12) требует обработки log2 Рконт(z) – разрядных операндов.

Использование изоморфизма, порожденного китайской теоремой об остатках (КТО), позволяет перейти от одномерной обработки к многомерной. Приравнивая соответствующие значения Рконт(z) и оснований vel25.wmf vel26.wmf, получаем r преобразований

vel27.wmf (14)

Проведем расчет аппаратурных затрат необходимых для реализации данного нейроподобного вычислительного устройства. Полученные данные сведены в табл. 3.

Таблица 3

Схемные затраты для устройства вычисления интервального номера при реализации алгоритма (14)

 

Разрядность сумматоров

GF(23)

GF(24)

GF(25)

Количество сумматоров

2

1

   

3

1

   

4

1

2

 

5

1

   

6

 

3

 

7

 

1

 

8

 

2

 

10

   

1

12

   

3

16

   

2

18

   

2

19

   

1

22

   

1

Количество нейронов

7

32

99

Количество нейронов с учетом первого слоя

14

47

130

Анализ таблицы показывает, что применение данной модификации метода вычисления интервального номера в кодах ПСКВ позволяет сократить схемные затраты по сравнению с алгоритмом (12). Так как кода ПСКВ, использующего неприводимые полиномы поля vel28.wmf, схемные затраты сократились на 9,8 % по сравнению с реализацией согласно (12). Однако данная модификация метода вычисления позиционной характеристики не позволила достичь минимальных схемных затрат. Это связано в необходимостью реализации немодульной процедуры – вычисления ранга K(z), что в конечном счете снижает скорость работы устройства и его надежность.

Решить данную проблему можно за счёт модификации алгоритма вычисления интервального номера. В основу данной модификации положено свойство – отсутствие переноса единицы из младшего разряда в старший при выполнении арифметической операции сложения двух операндов в расширенных полях Галуа GF (2v). Таким образом, величина ранга K*(z) безизбыточной системы ПСКВ p1(z),…, pk(z) определяется значением vel29.wmf и vel30.wmf, и никоим образом не зависит от переполнения рабочего диапазона P(z). Следовательно, вычислив vel31.wmf modPраб(z), можно отказаться от вычисления K*(z) и перейти к двухслойной организации нейронной логики. Тогда (14) примет вид

vel32.wmf (15)

Схемные затраты, необходимые на реализацию модификации метода вычисления интервального номера в кодах ПСКВ, представленного равенством (15), сведены в табл. 4.

Таблица 4

Схемные затраты для устройства вычисления интервального номера при реализации алгоритма (15)

 

Разрядность сумматоров

GF(23)

GF(24)

GF(25)

 

1

 

4

 

Количество сумматоров

2

1

4

2

3

1

4

3

4

1

2

3

5

 

1

2

6

 

1

 

7

     

8

   

8

10

   

1

14

   

1

Количество нейронов с учетом первого слоя

14

44

115

Анализ таблицы показывает, что реализация модификации метода вычисления интервального номера согласно (15) позволяет понизить схемные затраты на 3-5 % в зависимости от размерности поля Галуа. При этом при увеличении размерности кода ПСКВ схемные затраты сокращаются в больших процентах.

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

Выводы

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


Библиографическая ссылка

Велигоша А.В., Калмыков И.А., Корниенко Р.С., Ряднов С.А. МЕТОД ВЫЧИСЛЕНИЯ ИНТЕРВАЛЬНОГО НОМЕРА В МОДУЛЯРНЫХ КОДАХ И ЕГО МОДИФИКАЦИЯ // Международный журнал прикладных и фундаментальных исследований. – 2016. – № 5-3. – С. 400-405;
URL: http://www.applied-research.ru/ru/article/view?id=9263 (дата обращения: 01.03.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074