Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,899

DEVELOPMENT OF THE DEVICE DETECTION AND CORRECTION ERRORS BASED ON THE ALGORITHM OF THE EXTENDED SYSTEM OF MODULAR CODE BASES

Chernomazov C.A. 1 Martirosyan A.G. 1 Gapochkin A.V. 1 Kalmykov M.I. 1
1 Federal state Autonomous educational institution higher professional education «North-Caucasian federal university»
Using nonpositional modular codes due to the fact that these algebraic systems have the property of parallelism. These codes provide performing arithmetic operations, which include the operations of addition, subtraction and multiplication, in real time. This is due to the fact that information is processed independently of computing channels. In addition to increasing the processing speed nonpositional modular codes are able to detect and correct errors that may occur during the operation of special processors. To perform error correction procedures suggested in this article use the operation system expansion bases.
modular codes
codes of residue classes
the system of residual classes
detection and correction of errors
system expansion bases

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

Основная часть

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

cher01.wmf, (1)

где cher02.wmf – остаток, полученный при делении числа А на основание pi; i = 1,…,n; HOД(pi, pj), cher03.wmf.

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

cher04.wmf, (2)

где k – количество информационных рабочих оснований СОК; k < n.

При этом СОК обеспечивает полный диапазон, который определяется из следующего равенства

cher05.wmf, (3)

В работах [4–8], показано, что, если при переводе из модулярного кода в позиционный код, полученная величина числа (полинома) не превышает значение рабочего диапазона, то модулярный код не содержит ошибки.

В противном случае – модулярный код является запрещенным и содержит ошибку, как минимум в одном остатке.

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

В данном алгоритме берется исходное число A = (a1,…,ak, ak + 1, ak + 2), которое имеет два контрольных основания, удовлетворяющих условию

cher06.wmf, (4)

затем используя k информационных остатков a1, a2,…,ak, вычисляют остатки по контрольным основаниям cher07.wmf. После этого необходимо определить величину синдрома ошибки по этим двум контрольным основаниям

cher08.wmf (5)

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

Если кодовая комбинация СОК является запрещенной, то вычисленные значения остатков по контрольным основаниям cher09.wmf не совпадет с исходными величинами остатков избыточных оснований ak + 1 и ak + 2. При этом по величине синдрома ошибки можно однозначно определить ошибочное основание, а также величину ошибки.

Рассмотрим пример использования алгоритма расширения оснований. В данном алгоритме синдром ошибки будет определяться выражением

cher10.wmf, (6)

где cher11.wmf; Ra – ранг числа A в безизбыточной СОК; cher12.wmf; j = k + 1, k + 2.

Как отмечалось ранее, если в системе остаточных классов с рабочими p1, p2,…, pk и контрольными основаниями pk+1, pk+2, удовлетворяющих условию (4), модулярная кодовая конструкция A = (a1, a2,…, ak + 2) не содержит ошибок, если выполняется условие

cher13.wmf, (7)

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

Вычислим ортогональные базисы полной СОК. В данной полной системе основания ортогональные базисы равны

cher14.wmf

cher15.wmf

cher16.wmf

cher17.wmf

cher18.wmf

Представим ортогональные базисы, чтобы реализовать алгоритм (6)

cher19.wmf

cher20.wmf

cher21.wmf

cher22.wmf

cher23.wmf

Проведем расчет по модулю р4 = 7

cher24.wmf; cher25.wmf; cher26.wmf; cher27.wmf

Определим величину

cher28.wmf.

Проведем расчет по модулю р5 = 11

cher29.wmf; cher30.wmf; cher31.wmf; cher32.wmf

Определим величину

cher33.wmf.

Пусть имеем число А = (0, 2, 2, 2, 2) = 2. Вычислим значение остатков по контрольным основаниям для данного числа, используя разработанный алгоритм.

Вычислим значение ранг в безизбыточной системы, определяемые основаниями р1=2, р2 = 3, р3 = 5.

cher34.wmf

Тогда вычисленное значение первого остатка по контрольному основанию р4 = 7 для данной комбинации

cher35.wmf

Вычисленное значение первого остатка по контрольному основанию р5 = 11 для данной комбинации

cher36.wmf

Теперь определим величину синдрома ошибки согласно (7)

cher37.wmf

В результате синдром ошибки равен нулю, то это соответствует тому, что комбинация СОК А = (0, 2, 2, 2, 2) не содержит ошибки.

Пусть ошибка произошла по первому основанию и ее глубина равна ∆a1 = 1. Тогда модулярный код имеет вид А* = (1, 2, 2, 2, 2) = 2. Вычислим значение синдрома ошибки для данного числа, используя разработанный алгоритм.

Вычислим значение ранг в безизбыточной системы, определяемые основаниями р1 = 2, р2 = 3, р3 = 5.

cher38.wmf

Тогда вычисленное значение первого остатка по контрольному основанию р4 = 7 для данной комбинации

cher39.wmf

Вычисленное значение первого остатка по контрольному основанию р5 = 11 для данной комбинации

cher40.wmf

Теперь определим величину синдрома ошибки согласно (7)

cher41.wmf

В результате синдром ошибки отличен от нуля, то это соответствует тому, что комбинация СОК А* = (1, 2, 2, 2, 2) содержит ошибку.

Так как ошибочное число определяется из условия

cher42.wmf, (8)

то для получения нулевого синдрома ошибки необходимо из полученного синдрома вычесть значения cher43.wmf, где i = 1, 2, …, k; j = k + 1, k + 2.

Так значение безизбытоного ортогонального базиса cher44.wmf, то значения коррекции будут равны

cher45.wmf

cher46.wmf

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

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

Распределение однократных ошибок кода СОК

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

Глубина ∆αi

δ4

δ5

p1 = 2

1

1

4

p2 = 3

1

3

10

2

6

9

p3 = 5

1

6

6

2

5

1

3

4

7

4

3

2

p4 = 7

1

1

0

2

2

0

3

3

0

4

4

0

5

5

0

6

6

0

p5 = 11

1

0

1

2

0

2

3

0

3

4

0

4

5

0

5

6

0

6

7

0

7

8

0

8

9

0

9

10

0

10

Для реализации алгоритма (6) была разработана структура вычислительного устройства, осуществляющего процедуру поиска и исправления ошибок на основе расширения системы оснований. Структура данного устройства показана на рисунке.

chernom1.wmf

Структура устройства обнаружения и коррекции ошибки на основе расширения системы оснований

Устройство функционирует следующим образом. На вход 2 устройства для обнаружения и исправления ошибок в СОК подается контролируемое число, представленное в полиномиальной форме

cher49.wmf. (9)

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

cher50.wmf (10)

c образованием на его выходе сигнала

δ1=(α k+1-α* k+1))mod рk+1. (11)

При этом

α* k+1(1)1α1+ λ (1)2α2+…+ λ(1)kαk , (12)

где λ(1)i – константы системы СОК.

На входы блока 4 вычисления синдрома с выходов регистра 2 подается

cher51.wmf. (13)

С образованием на выходе сигнала

δ2=(α k+2+ α *k+2)mod pk+2. (14)

При этом

α*k+2= λ(2)1α1+ λ(2)2α2+…+ λ(2)kαk , (15)

где λ(2)i – константы системы.

Величины δ1 и δ2 в двоичном виде поступают на входы блока 5 памяти и выбирают оттуда соответствующую константу ошибки. Эта константа ошибки поступает в сумматор 6, где суммируется с искаженным A*, представленном в непозиционном виде поданным из регистра 1. Исправленное представление A с выхода сумматора 6 подается на выход 7 устройства.

Выводы

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