Scientific journal
International Journal of Applied and fundamental research
ISSN 1996-3955
ИФ РИНЦ = 0,593

THE ALGORITHM TO EXPAND THE SYSTEM OF BASES USED FOR ERROR CORRECTION IN MODULAR CODE

Makarova A.V. 1 Sarkisov A.B. 1 Kalmykov I.A. 1 Zholobov P.A. 1 Efremenkov I.D. 1
1 Federal state Autonomous educational institution of higher professional education «North-Caucasus Federal University»
1833 KB
The desire to provide digital signal processing with maximum performance promoted the use of parallel computing methods. To ensure maximum performance of orthogonal transformations of signals using parallel processing on various levels. Currently, attention is paid to support parallel computations at the level of operations. To solve this problem is to use a non-positional modular codes. However, these codes allow not only to improve the performance of the special processor, but is able to detect and correct errors occurring due to malfunctions and equipment failures. Develop an effective method to find the location and depth error based on the use of modular codes is an important task. The work considers the application of polynomial system classes deductions for error correction using the procedure of system expansion bases.
modular codes
error correction
polynomial reside number system

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

Цель исследования

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

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

Особенность ПСКВ заключается в том, что независимость обработки информации по основаниям ПСКВ позволяет не только повысить скорость и точность обработки, но также и обеспечить обнаружение и коррекцию ошибок в процессе функционирования вычислительного устройства [1-3]. В ПСКВ в качестве оснований системы используются неприводимые полиномы mak01.wmf, где mak02.wmf, любой полином A(x), удовлетворяющий

mak03.wmf (1)

где mak04.wmf – рабочий диапазон системы, mak05.wmf – степень полинома, можно однозначно представить в виде набора остатков

mak06.wmf (2)

где mak07.wmf

Для обнаружения и исправления однократных ошибок в модулярном коде полинома mak08.wmf вводят два контрольных основания mak09.wmf и mak10.wmf, которые удовлетворяют условию

mak11.wmf (3)

Наличие двух контрольных основания позволяет определить местоположение ошибки и ее глубину в коде ПСКВ [4, 5, 8].

Возникновение ошибки в непозиционной кодовой конструкции A(z) переводит ее из подмножества разрешенных комбинаций в подмножество запрещенных. Согласно китайской теореме об остатках (КТО) значение ошибочного полинома A*(z) равно

mak12.wmf (4)

где mak13.wmf – полный диапазон кода ПСКВ; mak14.wmf – глубина ошибки по j-ому основанию кода ПСКВ; Bj(z) – ортогональный базис j-го основания ПСКВ; j = 1, 2, …, n + 2.

Анализ выражения (4) показывает, что местоположение ошибочного полинома A*(z) относительно рабочего диапазона Pраб(z) определяется величиной второго слагаемого.

Рассмотрим алгоритм перевода из безизбыточного полиномиального модулярного кода в позиционный код согласно КТО, имеем

mak15.wmf (5)

где mak16.wmf – ортогональный базис; mi(z) – вес ортогонального базиса; mak17.wmf; rA(z) – ранг кода ПСКВ.

Воспользуемся определением ортогональных базисов, тогда выражение (5) можно представить в виде

mak18.wmf (6)

Умножение остатка на вес ортогонального базиса выполняется по модулю pi(z), что позволяют отказаться от вычисления ранга rA(z) при использовании китайской теоремы об остатках при переводе к позиционному коду.

Чтобы осуществить поиск и коррекцию ошибки в коде ПСКВ на основе расширения системы оснований необходимо, используя остатки по рабочим основаниям (α1(z),…, αn(z)), вычислитель остатки по контрольным основаниям pn + 1(z) и pn + 2(z).

Тогда для вычисления первого контрольного остатка mak19.wmf по основанию mak20.wmf используем следующее выражение

mak21.wmf (7)

Второй контрольный остаток mak22.wmf по основанию mak23.wmf определяется

mak24.wmf (8)

После этого вычисленные остатки mak25.wmf и mak26.wmf складываются по модулю два с остатками mak27.wmf и mak28.wmf, которые входят в состав комбинации кода ПСКВ mak29.wmf. В результате получается синдром ошибки, который определит местоположение и глубину ошибки в коде

mak30.wmf (9)

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

Результаты исследования и их обсуждение

Пусть задано поле Галуа mak31.wmf, в котором определены информационные основания mak32.wmf, mak33.wmf, mak34.wmf, расширяем систему оснований за счет введения двух контрольных оснований mak35.wmf и mak36.wmf. В этом случае

mak37.wmf.

При этом полный диапазон составляет mak38.wmf Тогда контрольный полином

mak39.wmf

Определим значения рабочих оснований mak40.wmf и mak41.wmf:

mak42.wmf

Тогда веса ортогональных базисов равны mak43.wmf mak44.wmf mak45.wmf

Следовательно, ортогональные базисы mak46.wmf соответственно равны

mak47.wmf

mak48.wmf

mak49.wmf

Воспользуемся полином mak50.wmf, который представляется как mak51.wmf.

Расширяем систему оснований за счет mak52.wmf и mak53.wmf. Первое основания расширения системы mak54.wmf. Вычислим значения mak55.wmf. Тогда имеем

mak56.wmf

mak57.wmf,

mak58.wmf.

Определим произведения

mak59.wmf,

mak60.wmf,

mak61.wmf

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

mak62.wmf

Результат расширения по основанию mak63.wmf получили остаток mak64.wmf. Проведем проверку и определим остаток исходного полинома

mak65.wmf.

Второе основание расширения

mak66.wmf.

Вычислим значения mak67.wmf. Тогда имеем

mak68.wmf,

mak69.wmf,

mak70.wmf.

Определим произведение

mak71.wmf.

Они соответственно равны

mak72.wmf,

mak73.wmf,

mak74.wmf

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

mak75.wmf.

Результат расширения по основанию mak76.wmf – остаток mak77.wmf. Проведем проверку и определим остаток исходного полинома

mak78.wmf.

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

mak79.wmf.

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

mak81.wmf

Так как синдром ошибки равен нулю, то код ПСКВ не содержит ошибки.

Рассмотрим ситуацию, когда проверяемая комбинация ПСКВ содержит ошибку по первому основанию и ее глубина равна mak82.wmf. Тогда значение первого остатка равно mak83.wmf. Ошибочная комбинация модулярного кода ПСКВ имеет вид

mak84.wmf.

Определим mak85.wmf, для данной ошибочной комбинации кода ПСКВ. Получаем

mak86.wmf,

mak87.wmf

mak88.wmf.

Вычислим первый контрольный остаток, подставив значения в выражение (7)

mak89.wmf

Результатом расширения по модулю mak90.wmf является mak91.wmf.

Вычислим второй контрольный остаток, подставив значения в выражение (8)

mak92.wmf.

Результатом расширения по модулю mak93.wmf является остаток mak94.wmf.

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

mak95.wmf

Проверяемая комбинация содержит ошибки, так как синдром ошибки отличен от нуля. В таблице приведены значения глубины и местоположения ошибки в коде ПСКВ по рабочим основаниям и соответствующего им синдрома ошибки S1(z) и S2(z). Данные в таблице приведены в шестнадцатеричной системе счисления. По значению синдрома ошибки определяем, что ошибка произошла по первому основанию p1(z) = z + 1, а ее глубина равна mak96.wmf. Значит, вектор ошибки будет равен mak97.wmf.

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

mak98.wmf

Глубина и местоположение ошибки в коде ПСКВ по S1(z) и S2(z)

Основание

Глубина

S1(z)

S2(z)

p1(z) = z + 1

1

B

2

p2(z) = z2 + z + 1

1

7

9

2

A

7

3

D

E

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

1

E

D

2

1

F

3

F

2

4

6

B

5

8

6

6

7

4

7

9

9

8

C

5

9

2

8

A

D

A

B

3

7

C

A

E

D

4

3

E

B

1

F

5

C

Если ошибка произойдет по первому контрольному основанию p4(z) = z4 + z3 + 1, то значение первой составной синдрома S1(z) будет показывать глубину ошибки, а значение S2(z) будет равняться нулю.

Если ошибка произойдет по второму контрольному основанию p5(z) = z4 + z + 1, то значение второй составной синдрома S2(z) будет показывать глубину ошибки, а значение первой составляющей синдрома S1(z) будет равняться нулю.

Заключение

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