Scientific journal
Advances in current natural sciences
ISSN 1681-7494
"Перечень" ВАК
ИФ РИНЦ = 0,746

APPLICATION OPERATIONS EXPANSION SYSTEM BASES MODULAR CODE FOR DETECTION AND CORRECTION ERRORS

Gapochkin A.V. 1 Barbaryn V.G. 1 Kalmykov M.I. 1 Martirosyan A.G. 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]. Применение непозиционных модулярных кодов обеспечивает за счет параллельной работы с небольшими остатками обработку ЦОС с максимальным быстродействием.

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

Постановка задачи исследований

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

gapoch01.wmf, (1)

где gapoch02.wmf; gapoch03.wmf.

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

gapoch04.wmf, (2)

где gapoch05.wmf; gapoch06.wmf.

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

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

В работах [1–3] приведены доказательства о величине минимальной избыточности, которую необходимо ввести в модулярный код, чтобы обеспечить коррекцию любой однократной ошибки. Так согласно этим работам выделение из общего набора n оснований двух контрольных оснований, таких что

gapoch07.wmf, (3)

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

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

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

gapoch09.wmf, (4)

то его модулярный код не содержит ошибок.

Если число А не принадлежит рабочему диапазону, то есть

gapoch10.wmf, (5)

то его модулярный код СОК содержит ошибку.

Это обусловлено тем, что ошибка преобразует правильную комбинацию модулярного кода gapoch11.wmf в запрещенную комбинацию gapoch12.wmf, где gapoch13.wmf – искаженный остаток, gapoch14.wmf – глубина ошибки. В этом случае перевод искаженного числа из рабочего диапазона, в диапазон полный. Поэтому во всех алгоритмах поиска и коррекции ошибок в модулярном непозиционном коде применяют позиционные характеристики [4–9]. Это позволяет узнать местоположение искаженной комбинации gapoch15.wmf в полном диапазоне, определяемым

gapoch16.wmf. (6)

а затем однозначно определить основание, по которому произошла ошибка, а также ее глубину.

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

В основу метода, базирующегося на вычислении синдрома ошибок по контрольным основаниям, положено определение разности между значениями остатков gapoch18.wmf по контрольным основаниям исходного числа gapoch19.wmf и результатом вычисления остатков gapoch20.wmf с использованием рабочих оснований. Математически данный метод можно представить

gapoch21.wmf (7)

где gapoch22.wmf; f – алгоритм вычисления остатков по рабочим основаниям.

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

Если в упорядоченной системе остаточных классов с рабочими p1, p2,…, pk и контрольными основаниями pk+1, pk+2, удовлетворяющих условию (3), код СОК числа gapoch23.wmf не содержит ошибок, если выполняется условие

gapoch24.wmf, (8)

где

gapoch25.wmf;

Ra – ранг числа A в безизбыточной СОК;

gapoch26.wmf; j=k+1,k+2.

Рассмотрим более подробно данный алгоритм. Известно, что интервальный номер l, в котором находится код СОК числа A определяется выражением

gapoch27.wmf. (9)

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

gapoch28.wmf. (10)

Подставив последнее равенство в выражение (9) и, воспользовавшись свойством сравнимости ортогональных базисов полной и безизбыточной системы остаточных классов, получаем

gapoch29.wmf, (11)

где

gapoch30.wmf; gapoch31.wmf;

gapoch32.wmf.

Положим, что Рконт = pj, j=k+1,…,k+r. Тогда (11) примет вид

gapoch33.wmf (12)

Если полином gapoch34.wmf>, то интервальный номер будет равен нулю gapoch35.wmf. Следовательно, справедливо

gapoch36.wmf (13)

Тогда

gapoch37.wmf, (14)

где gapoch38.wmf .

Таким образом, на основании (14) было произведено вычисление остатков gapoch39.wmf по контрольным основаниям на основе известных значений gapoch40.wmf.

Следовательно, если выполняется условие

gapoch41.wmf,

то полином gapoch42.wmf, и он не содержит ошибки.

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

Выводы

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