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

IMPROVEMENT OF INTERVAL ALGORITHM FOR COMPUTING THE NUMBER USED TO ERROR CORRECTION IN A MODULAR CODE

Zavorotinsky D.I. 1 Solodkin I.G. 1 Gapochkin A.V. 1 Kalmykov M.I. 1
1 Federal state Autonomous educational institution higher professional education «North-Caucasian federal university»
Modern redundant codes are used for the search operation and correction of errors that can occur as a result of the impact of noise on the combination or fail-coder-decoder. A special place among such codes occupy modular codes that relate to nonpositional codes. Since the codes are modular arithmetic, they are used for the correction of errors that can occur during the operation of computer systems. The algorithm detects the error codes used in modular positional characteristics. One such characteristic is the number of interval number. This paper presents an improved algorithm for computing these characteristics.
modular codes
redundant codes
the system of residual classes
error detection and correction
positional characteristics
interval number
the track number

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

Постановка и решение задачи исследования. Использование параллельных алгоритмов вычислений в современных информационных технологиях обусловлено высокими требованиями, предъявляемыми к скорости обработки информации. Чтобы обеспечить данное требование в ряде работ предлагается использовать модулярные коды [1–6]. Модулярные коды относятся к арифметическим кодам, которые применяются для выполнения алгоритмов, в которых используются модулярные операции – сложение, вычитание и умножение по модулю.

Так в системе остаточных классов (СОК) числа, которые принадлежат рабочему диапазону можно однозначно представить в виде набора остатков

zav01.wmf, (1)

где zav02.wmf. – рабочий диапазон; А < Pраб; zav03.wmf; i = 1,2,…,k.

Тогда для суммы, разности и произведения двух чисел А и В, имеющих соответственно модулярные коды (a1,a2,…,ak) и (b1, b2,…, bk) справедливы соотношения при i = 1,…,k

zav06.wmf, (2)

где ● – операции сложения, вычитания и умножения по модулю.

Тогда ортогональное преобразование сигнала определяется

zav07.wmf, (3)

где zav08.wmf – остаток по модулю отсчета входной последовательности zav09.wmf; zav10.wmf – остаток по модулю спектрального отсчета сигнала zav11.wmf; β – поворачивающий коэффициент дискретного преобразования Фурье.

При этом обратное ортогональное преобразование сигнала определяется

zav12.wmf, (4)

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

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

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

zav13.wmf. (5)

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

zav14.wmf. (6)

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

zav15.wmf, (7)

то она считается разрешенной.

При этом при возникновении ошибки такая комбинация переносится в область запрещенных комбинаций. Это связано с тем, что однократная ошибка переводит разрешенную комбинацию А = (a1,a2,…,ak+2) в комбинацию zav16.wmf, где zav17.wmf – искаженный остаток, ∆ai – глубина ошибки. В результате воздействия ошибки искаженное число выходит за пределы рабочего диапазона и переносится в диапазон полный. Значит если определить местоположение искаженной комбинации zav18.wmf, то можно однозначно выявить модуль, по которому произошла ошибка, а также определить ее величину ∆ai.

Чтобы провести эту процедуру в непозиционных модулярных кодах применяют различные позиционные характеристики [7–10]. Среди множества позиционных характеристик особое место занимает интервальный номер. Эта позиционная характеристика имеет достаточно простой физический смысл, так как задается следующим выражением

zav19.wmf. (8)

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

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

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

Если в упорядоченной системе СОК, содержащей k информационных и два избыточных оснований, в результате нулевизации модулярного кода числа A получен позиционная характеристика след

zav20.wmf, (9)

то интервал, в который будет перенесена ошибочная комбинация СОК числа A*, будет вычисляться

zav21.wmf, (10)

где zav22.wmf; Bj – ортогональный базис по j-му основанию СОК;

zav23.wmf – ранг в безизбыточной системы; zav24.wmf.

Чтобы доказать правильность усовершенствованного алгоритма вычисления интервального номера числа покажем, в начале, что если хотя бы один след числа zav25.wmf, где j =k+1, k+2, то код СОК числа A является запрещенным. Другими словами, код СОК содержит ошибку. Для этого проведем замену произведения двух контрольных оснований СОК одним составным основанием zav27.wmf.

Тогда исходный код СОК числа A, который задается в виде (k + 2) – мерного вектора, (a1,a2,…,ak+1, ak+2), примет вид

zav28.wmf, (11)

где zav29.wmf.

Известно, что если в коде СОК числа A, принадлежащего рабочему диапазону СОК, произошла ошибка, то результатом операции параллельной нулевизации кода числа A* с использованием псевдоортогональных базисов Aik будет отличный от нуля след числа

zav30.wmf, (12)

где zav31.wmf zav32.wmf;

zav33.wmf – ортогональный базис безизбыточной системы оснований СОК.

С другой стороны, согласно китайской теореме об остатках (КТО)

zav34.wmf, (13)

где zav35.wmf; Мj – ортогональный базис системы модулярного кода с контрольными основаниями pk+1 и pk+r.

Очевидно, что если след отличен от нуля zav36.wmf, то хотя бы один из остатков zav37.wmf должен отличаться от нуля.

Таким образом, если в результате параллельной нулевизации кода СОК числа A* и с помощью псевдоортогональных базисов будет получен след zav38.wmf, то данный полином содержит ошибку.

Покажем теперь, что величина интервального номера l кода СОК числа A будет определяться согласно алгоритма (10).

Пусть в результате процедуры нулевизации кода СОК искаженного числа A* получим след zav39.wmf отличный от нуля. Известно

zav40.wmf, (14)

где zav41.wmf; ∆ai – глубина ошибки по i-ому основанию.

При этом zav42.wmf = γ = (0,0,0,...,0,γk + 1, γk + 2).

Тогда на основании выражения (14) имеем

zav43.wmf. (15)

Согласно КТО и с учетом ai = 0, i = 1,2,…,k, имеем

zav44.wmf. (16)

Подставляем (16) в равенство (15) получаем

zav45.wmf. (17)

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

zav46.wmf, (18)

где zav47.wmf.

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

Выводы

Для эффективной работы систем цифровой обработки сигналов, функционирующих в СОК, необходимо, чтобы время необходимое на выполнение операции вычисления позиционной характеристики не превышало времени выполнения процедуры преобразования из модулярного кода в позиционный код. Проведенные исследования показали, что переход к усовершенствованному алгоритму позволяет сократить время вычисления позиционной характеристики при обработке 24-разрядных данных на 14,1 % по сравнению с классическим методом вычисления интервального номера числа.