Научный журнал
Международный журнал экспериментального образования

ISSN 2618–7159
ИФ РИНЦ = 0,440

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

Гапочкин А.В. 1 Калмыков М.И. 1 Айриян А.А. 1
1 ФГАОУ ВПО «Северо-Кавказский федеральный университет»
Модулярные коды относятся к непозиционным арифметическим кодам. Введение избыточных оснований позволяет осуществлять процедуры поиска и коррекции ошибок, возникающие в процессе функционирования вычислительных систем из-за отказа оборудования. Для определения местоположения и глубины ошибки в модулярных кодах используют позиционные характеристики. Одной из таких характеристик является след числа. В работе представлен алгоритм параллельного вычисления данной характеристики.
модулярные коды
система остаточных классов
обнаружение и коррекция ошибок
позиционные характеристики
след числа
1. Червяков Н.И., Сахнюк П.А., Шапошников А.В., Ряднов С.А. Модулярные параллельные вычислительные структуры нейросетевых систем. – М.: Физматлит., 2003. – 303 с.
2. Калмыков И.А., Оленев А.А., Бережной В.В. Систолический процессор дискретного преобразования Фурье с коррекцией ошибки// Патент на изобретение RUS 2018950.
3. Бережной В.В., Калмыков И.А., Червяков Н.И., Щелкунова Ю.О., Шилов А.А. Нейросетевая реализация в полиномиальной системе классов вычетов операций ЦОС повышенной разрядности// Нейрокомпьютеры: разработка и применение. – 2004. – № 5-6. – С. 94.
4. Калмыков И.А., Чипига А.Ф. Структура нейронной сети для реализации цифровой обработки сигналов повышенной разрядности// Наука. Инновации. Технологии. – 2004. – Т.38. – С. 46.
5. Калмыков И.А., Червяков Н.И., Щелкунова Ю.О., Шилов А.А., Бережной В.В Архитектура отказоустойчивой нейронной сети для цифровой обработки сигналов// Нейрокомпьютеры: разработка и применение. – 2004. – № 12. – С. 51-57.
6. Калмыков И.А., Зиновьев А.В., Емарлукова Я.В., Высокоскоростные систолические отказоустойчивые процессоры цифровой обработки сигналов для инфотелекоммуникационных систем// Инфокоммуникационные технологии. Самара. – 2009. – №2. – С. 31-37.
7. Калмыков И.А., Резеньков Д.Н., Тимошенко Л.И. Непозиционное кодирование информации в конечных полях для отказоустойчивых спецпроцессоров цифровой обработки сигналов// Инфокоммуникационные технологии. – 2007. – Т.5. – №3. – С. 36-39.
8. Калмыков И.А., Петлеванный С.В., Сагдеев А.К., Емарлукова Я.В. Устройство для преобразования числа из полиномиальной системы классов вычетов в позиционный код с коррекцией ошибки //Патент России № 2309535. 31.03.2006. Бюл. № 30 от 27.10.2007.
9. Калмыков И.А., Лисицын А.В., Гахов В.Р. Алгоритм обнаружения и коррекции ошибок в модулярном коде на основек выекции ошибок в непозиционном коде расширенного поля Галуа// Нейрокомпьютеры: разработка и применение. 2003. № 8-9. С. 10-17.
10. Калмыков И.А, .Хайватов А.Б., Математическая модель отказоустойчивых вычислительных средств, функционирующих в полиномиальной системе классов вычетов// Инфокоммуникационные технологии. – 2007. – Т.5. – №3. – С.39-42.
11. Калмыков И.А., Гахов В.Р., Емарлукова Я.В. Устройство обнаружения и коррекции ошибок в кодах полиномиальной системы классов вычетов //Патент России № 2300801. 30.06.2005. Бюл. № 16 от 10.06.2007.
12. Червяков Н.И., Калмыков И.А., Щелкунова Ю.О., Бережной В.В. Математическая модель нейронной сети для коррекции ошибок в непозиционном коде расширенного поля Галуа// Нейрокомпьютеры: разработка и применение. 2003. № 8-9. С. 10-17.
13. Чипига А.А., Калмыков И.А., Лободин М.В. Устройство спектрального обнаружения и коррекции в кодах полиномиальной системы классов вычетов// Патент России № 2301441. Бюл. № 17 от 20.06.2007.

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

Модулярные коды относятся к кодам, которые используются для вычислений. Малоразрядность обрабатываемых остатков позволяет осуществлять вычисления в реальном масштабе времени параллельно и независимо по вычислительным каналам, определяемыми основаниями кода. В настоящее время широкое распространение получили коды системы остаточных классов (СОК) и коды полиномиальной системы классов вычетов (ПСКВ) [1–4]. Основное различие между данными кодами состоит в том, что в качестве оснований в СОК используются взаимно простые числа, а кодах ПСКВ – неприводимые полиномы.

Так как данные коды относятся к непозиционным кодам, то в основу алгоритмов поиска и коррекции ошибок в модулярных кодах положена процедура вычисления позиционной характеристики [5–10]. В основу данного подхода положено некоторое функциональное отношение, позволяющее однозначно отражать множество значений модульных характеристик на множество рассматриваемых ошибок Е. При этом следует обеспечить, чтобы математическая модель, описывающее данное отношение, при реализации обеспечивала бы параллельную организацию вычислений. Так в работе [5] в качестве позиционной характеристики, которую используют для коррекции ошибок в модулярном коде выступают старшие коэффициенты обобщенной полиадической системы (ОПС). В работе [6] представлен алгоритм вычисления позиционной характеристики интервал. В работе [7] доказаны теоремы, позволяющие использовать для коррекции ошибки в модулярном коде нормированный след полинома. В работе [8] для повышения скорости вычисления коэффициентов ОПС предлагается использовать ортогональные базисы безизбыточной системы.

В работах [5, 6] предлагается для проведения операции поиска и коррекции однократной ошибки в коде СОК, задаваемом рабочими основаниями p1, p2,... pk, использовать два контрольных основания, которые бы удовлетворяли условию

air03.wmf, (1)

где k – количество рабочих оснований;

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

Альтернативным путем решения данной проблемы является метод определения правильности air23.wmf на основе вычисления следа числа, которое представляет собой переход от исходного модулярного кода к коду вида

air05.wmf,

при помощи преобразований, при которых не имеет место ни один выход за пределы рабочего диапазона системы.

Согласно [5] алгоритм вычисления следа числа заключается в последовательном вычитании из исходного модулярного кода, некоторых минимальных чисел, представленных в коде СОК. Эти числа называются константами нулевизации, при этом модулярный код числа А последовательно преобразуется к виду

air06.wmf,

затем в полином (0, 0, air51.wmf,..., air52.wmf,..., air53.wmf и так далее. Осуществляя данную процедуру в течение k итераций, получается след числа

air08.wmf.

Применение классического алгоритма вычисления следа числа позволяет последовательно получать наименьшее число, которое будет кратным сначала p1, затем число – кратное произведению p1, p2, и в конечном итоге – кратный рабочему диапазону, определяемому выражением

air11.wmf. (2)

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

air12.wmf (3)

где

air13.wmf.

Чтобы применить разработанный параллельный алгоритм вычисления следа числа необходимо заменить константы нулевизации Mi на псевдоортогональные числа. К таким числам относятся ортогональные базисы, у которых нарушена ортогональность по контрольным основаниям. Если положить условие, что число не содержит ошибок, то есть air15.wmf, то это число модно представить в модулярном коде следующим образом

air16.wmf.

Тогда, согласно китайской теореме об остатках (КТО), данное число A можно представить в виде

air16а.wmf

air16е.wmf. (4)

При этом каждое слагаемое выражения (4) можно представить, используя air16о.wmf – ортогональный базис безизбыточной системы оснований, в виде

air19.wmf, (5)

Проведем расширение системы рабочих оснований p1, p2,... pk на r контрольных pk+1, pk+2,... pk+r,. Используя полный набор из air22.wmf оснований, представим air23.wmf в виде

air24.wmf (6)

Подставим выражения (6) в равенство (4). В результате получаем равенство

air25.wmf (7)

Следовательно,

air26.wmf (8)

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

air27.wmf, (9)

где rA – ранг числа А.

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

air28.wmf (10)

Пусть задана упорядоченная СОК с рабочими основаниями р1 = 2, р2 = 3, р3 = 5. В качестве контрольных оснований выберем основания р4 = 7 и р5 = 11. Определим все псевдоортогональные числа, учитывая невозможность выхода за пределы рабочего диапазона Pраб(z) = 30. Полученные значения представлены в табл. 1.

Таблица 1

Псевдоортогональные числа СОК

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

Псевдоортогональный базис

Код псевдоортогонального числа

р1 = 2

air29.wmf

(1, 0, 0, 1, 4)

р2 = 3

air30.wmf

(0, 1, 0, 3, 10)

air31.wmf

(0, 2, 0, 6, 9)

р3 = 5

air32.wmf

(0, 0, 1, 6, 6)

air33.wmf

(0, 0, 2, 5, 1)

air34.wmf

(0, 0, 3, 4, 7)

air35.wmf

(0, 0, 4, 3, 2)

Так как новые константы нулевизации подобраны таким образом, что в процессе вычитания из исходного числа A выход за пределы рабочего диапазона не осуществляется, то по результату (10) можно судить о правильности кодовой комбинации СОК. Если система равенств (10) обращается в ноль, то исходный модулярный код не содержит ошибки, в противном случае – кодовая комбинация СОК является ошибочным. В табл. 2 представлены значения вектора ошибки air36.wmf для различных значений ошибки в коде СОК.

Таблица 2

Значения вектора ошибки модулярного кода СОК

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

Значение вектора ошибки

γ4(z)

γ5(z)

0

0

(0, 0, 0)

1

4

(1, 0, 0)

3

10

(0, 1, 0)

6

9

(0, 2, 0)

6

6

(0, 0, 1)

5

1

(0, 0, 2,)

4

7

(0, 0, 3)

3

2

(0, 0, 4)

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

Рассмотрим пример применения параллельного алгоритма вычисления следа числа. Пусть задано число А = 29, которое принадлежит рабочему диапазону. Тогда в коде СОК данное число имеет вид А = (1, 2, 4, 1, 7). Произведем вычисление следа числа. Согласно КТО ранг данного числа равен rA = 1.

Для остатка α1 = 1 значение псевдоортогонального базиса имеет вид (1, 0, 0, 1, 4).

Для остатка α2 = 1 значение псевдоортогонального базиса имеет вид (0, 2, 0, 6, 9).

Для остатка α3 = 1 значение псевдоортогонального базиса имеет вид (0, 0, 4, 3, 2).

Значение air40.wmf.

Тогда значение следа согласно (10) имеет вид

air41.wmf

Вычислим значение следа по второму контрольному основанию.

Значение Pрабmod p5 = 30 mod 11 = 8. Тогда значение следа согласно (10) имеет вид

air43.wmf

Таким образом, можно сделать вывод, о том, что код СОК А = (1, 2, 4, 1, 7) не содержит ошибки.

Пусть ошибка произошла по первому основанию и ее глубина равна air44.wmf. Тогда в код СОК имеет вид Аош = (0, 2, 4, 1, 7). Произведем вычисление следа числа. Согласно КТО ранг данного

числа равен rA = 1.

Для остатка air45.wmf значение псевдоортогонального базиса имеет вид (0, 2, 0, 6, 9).

Для остатка air46.wmf значение псевдоортогонального базиса имеет вид (0, 0, 4, 3, 2).

Значение Pрабmod p4 = 30 mod 7 = 2.

Тогда значение следа согласно (10) имеет вид

air48.wmf

Вычислим значение следа по второму контрольному основанию.

air49.wmf

Так как позиционная характеристика отлична от нуля, то можно сделать вывод, о том, что код СОК А = (0, 2, 4, 1, 7) содержит ошибки. Согласно таблице 2 значение следа определяет, что ошибка по первому основанию, а ее глубина равна air50.wmf. Тогда откорректированное значение кода равно А = (1, 2, 4, 1, 7).

Выводы

Для повышения скорости выполнения операции вычисления позиционной характеристики след числа был разработан параллельный алгоритм. С этой целью вместо классических констант нулевизации предложено использовать псевдоортогональные базисы. Проведенные исследования показали, что переход к параллельному алгоритму позволил сократить время вычисления позиционной характеристики при обработке 16-разрядных данных на 17,3 % по сравнению с классическим методом вычисления следа числа. Кроме того, применение параллельного алгоритма вычисления позиционной характеристики след числа позволил сократить аппаратурные затраты для реализации процедуры поиска и коррекции ошибки.


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

Гапочкин А.В., Калмыков М.И., Айриян А.А. КОРРЕКЦИЯ ОШИБКИ В МОДУЛЯРНОМ КОДЕ НА ОСНОВЕ АЛГОРИТМА ПАРАЛЛЕЛЬНОГО ВЫЧИСЛЕНИЯ СЛЕДА // Международный журнал экспериментального образования. – 2014. – № 8-3. – С. 34-38;
URL: http://expeducation.ru/ru/article/view?id=5926 (дата обращения: 02.07.2020).

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

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