Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,222

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

Калмыков И.А., Лисицын А.В., Гахов В.Р.

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

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

Особое место среди позиционных характеристик модулярных кодов полиномиальной системы класса вычетов (ПСКВ) занимает интервальный номер полинома f [2,3]. Процесс определения интервала полинома f сводится к выполнению операции:

f.                                                       (1)

где f - рабочий диапазон, f; - основание ПСКВ.

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

Выразим полином f через его остатки f в виде

f                                (2)

где r(z)- ранг полинома A(z).

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

f,   (3)

где f;  f- ранг безизбыточной системы ПСКВ, определяемой основаниями f; f.

Таким образом, определение интервального номера f полинома A(z) сводится к выполнению модульных операций в ПСКВ поля f.

Если f, то исходное A(z) лежит внутри рабочего диапазона Pраб и не является запрещенным. В противном случае A(z) - ошибочная комбинация, а Lинт указывает местоположение и глубину ошибки f по i-му основанию.

Основным недостатком предложенного метода является необходимость реализации немодульной процедуры - вычисления ранга числа A(z), что, в конечном счете, снижает скорость работы устройства и его надежность [4]. Для решения данной проблемы целесообразно воспользоваться нормированным следом Sk+1, l=1,2,,...,r. Исходя из условия подобия ортогональных базисов рабочих оснований в избыточной Bi и безызбыточной f системах f, f и делимости без остатка ортогональных базисов контрольных оснований на Pраб, т.е. f,  fвыражение (1) принимает вид:

f,                                  (4)

где f; f; f- нормированный след по j-ому основанию.

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

f,        (5)

Значение полинома f позволяет однозначно определять местоположение полинома f относительно Pраб(z). Если f, то полином A(z) лежит внутри рабочего диапазона и не содержит ошибки. В противном случае - полином A(z) является ошибочным. Так, для полинома f значение интервального полинома согласно (3) составит

f,

f свидетельствует о наличии ошибки в исходной комбинации A(z).

Используем выражение (5) для определения интервального полинома:

f; f;

f; f;

f.

Тогда

f

f

Таким образом, применение выражения (5) позволяет осуществить вычисление интервального полинома Lинт(z) на основе только модульных процедур, используя значения нормированного следа f, l=1,2,...,r.

В работе [4] представлена структура устройства вычисления интервального полинома, реализованного в нейросетевом логическом базисе, для поля GF(24). Применение разработанного алгоритма позволяет исправить 100% однократных ошибок и свыше 95% двукратных ошибок. Полученные результаты имеют важное практическое значение, так как позволяют строить отказоустойчивые параллельные вычислительные системы.

СПИСОК ЛИТЕРАТУРЫ

  1. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. - М.: Сов. радио, 1968.- 440 с.
  2. Калмыков И.А. Математические модели нейросетевых отказоустойчивых вычислительных средств, функционирующих в полиномиальной системе классов вычетов/Под ред. Н.И. Червякова. - М.: ФИЗМАТЛИТ, 2005. - 276 с.
  3. Калмыков И.А., Червяков Н.И., Щелкунова Ю.О., Бережной В.В. Математическая модель нейронной сети для коррекции ошибок в непозиционном коде расширенного поля Галуа/Нейрокомпьютеры: разработка, применение. №8-9, 2003. С. 10-16.
  4. Калмыков И.А., Емельяненко С.В., Лисицын А.В. Устройство для вычисления сумм парных произведений в полиномиальной системе классов вычетов. Решение о выдаче патента (№ 2004101990/09(001852). Приоритет от 22.01.2004.

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

Калмыков И.А., Лисицын А.В., Гахов В.Р. АЛГОРИТМ ОБНАРУЖЕНИЯ И КОРРЕКЦИИ ОШИБКИ В МОДУЛЯРНОМ КОДЕ НА ОСНОВЕ ВЫЧИСЛЕНИЯ ИНТЕРВАЛЬНОГО НОМЕРА ПОЛИНОМА // Фундаментальные исследования. – 2006. – № 2. – С. 30-32;
URL: http://www.fundamental-research.ru/ru/article/view?id=4710 (дата обращения: 24.07.2019).

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

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