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

ЛОКАЛИЗАЦИИ ОШИБОК В МОДУЛЯРНЫХ КОДАХ ПОЛИНОМИАЛЬНОЙ СИСТЕМЫ КЛАССОВ ВЫЧЕТОВ С МИНИМАЛЬНОЙ ИЗБЫТОЧНОСТЬЮ

Калмыков И.А., Резеньков Д.Н.

Модулярные коды полиномиальной системы классов вычетов ПСКВ обладают потенциальными возможностями по построению кодов, способных обнаруживать и исправлять ошибки в процессе выполнения операций, независимо от природы возникновения арифметических ошибок [1,2,3,4].

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

Теорема: если в нормированной системе оснований ПСКВ р1(z), p2(z),..., рк+1(z) задан полином A(z)=(a1(z), a2(z), ...,ak+1(z)) с нормированным следом γk+i(z), то данный полином является разрешенным при условии γk+i(z)=0, в противном случае - он содержит ошибку [1,2].

Доказательство

Применение китайской теоремы об остатках позволяет представить полином A(z) = (a1 (z), a2(z), ...,ak+l(z)) в виде суммы ортогональных полиномов

A(z) = (a1(z), a2(z), ...,ak+l(z)) =fai(z)Bi(z)modPполн(z).                                          (1)

Если положить условие, что полином A(z) является разрешенным, т.е. A(z)ÎPpa6(z), то справедливо

A(z) = (a1(z), a2(z), ...,ak(z)) = faj(z)Bj*(z)modPраб(z)                                             (2)

где Bj*(z) - ортогональные базисы безизбыточной системы оснований.

Тогда имеем

(a1(z), a2(z), ...,ak+l(z))= (a1(z), a2(z), ...,ak(z))                                                  (3)

Расширив безубыточную систему оснований ПСКВ р1(z), p2(z),..., pk(z) на основание pk+1(z), представим ортогональные базисы в виде

|a1(z)B1*(z)| +Pраб(z)=(a1(z),0,0,...,0, y1k+1(z))=A1(z);

|a1(z)B1*(z)| +Pраб(z)=(0, a2(z),0,...,0, y2k+1(z))=A2(z);                       (4)

...

|ak(z)Bk*(z)| +Pраб(z)=(0, 0,0,...,ak(z), ykk+1(z))=Ak(z);

Таким образом, получены псевдоортогональные полиномы, у которых ортогональность нарушена по контрольному основанию. Тогда нормированный след и Sk+1(z) полинома A(z) определяется как разность исходного A(z) и величин m псевдоортогональных полиномов

A(z)- fA1(z) = yk+1(z)                                                  (5)

Поскольку, согласно (3) выхода за пределы рабочего диапазона не происходит, то значение нормированного следа полинома yk+1(z)однозначно определяет факт наличия ошибки.

Если полином A(z) является разрешённым, то на основе (2) и (3) имеем, что значение нормированного следа yk+1(z) = 0.

Допустим, что ошибка возникла по i-ому основанию, i = 1,2,...,к+1. Рассмотрим случай, когда i= к+1. Тогда A*(z) = (a1(z),a2(z),...,a*k+I(z)). Так как все остатки по рабочим основаниям не изменялись, то сумма псевдоортогональных полиномов Ai(z), i=1,2, ...,k, по контрольному основанию даст значения

f yik+1(z)mod p k+1(z)= ak+I(z).

Но так как ошибка произошла по избыточному основанию, то справедливо a*k+I(z) ≠ak+I(z)

Следовательно, нормированный след полинома yk+1(z)≠0.

Пусть ошибка произошла по рабочему основанию p i(z), где i = 1,2,...,к. Тогда полином примет вид A*(z) = (a1(z),...,a*i(z),...,ak+I(z)). Очевидно, что изменение величины остатка ai(z) ≠ a*i(z) ведет к использованию в выражении (5) вместо псевдоортогонального полинома Ai(z)другого полинома Ai*(z). Таким образом γik+1(z)≠ γ*k+1(z). Следовательно, yk+1(z) ≠0. Значит полином A*(z) содержит ошибку.

Доказательство закончено.

Очевидно, что доказанная теорема позволяет использовать позиционную характеристику нормированный след полинома для построения эффективных процедур поиска и локализации ошибок в модулярных кодах ПСКВ. При этом значение номера интервала, в который попадает ошибочный полином A*(z) равен значению остатка по контрольному модулю yk+1(z) и определяется следующим образом [3]

l(z)= yk+1(z)=[∆ai(z)mi(zk+1(z) /pi(z)]modpk+1(z).                                        (6)

Поскольку каждая из ошибок может перевести правильный полином A(z) в полином A*(z), лежащий вне нулевого диапазона Pполн(z),то зная номер интервала куда попал A*(z), можно определить совокупность оснований, в остатках которых могла произойти ошибка. Кроме того, существенным фактором является возможность определения величины ошибки, которая перевела разрешенную комбинацию A(z) в запрещенный диапазон [4].

В связи с этим открывается дополнительные возможности к сокращению процесса определения места ошибки. Поскольку ошибки по рабочим основаниям p1(z), p2(z),...,pn(z) могут располагаться лишь в интервалах, определенных выражением ord pi(z)³ ord pk+1(z),то в случае когда имеет место ошибка, не относящаяся ни к одному из возможных интервалов, можно утверждать, что она имела место в остатке по контрольному основанию pn+1(z).

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

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

  1. Калмыков И.А. Математические модели нейросетевых отказоустойчивых вычислительных средств, функционирующих в полиномиальной системе класса вычетов. - М.: ФИЗМАТЛИТ, 2005. -274с.
  2. Калмыков И.А., Червяков Н.И., Щелкунова Ю.О., Бережной В.В. Архитектура отказоустойчивой нейронной сети для цифровой обработки сигналов /Нейрокомпьютеры: разработка, применение. №12, 2004, с.51-60.
  3. Калмыков И.А., Тимошенко Л.И., Резеньков Д.Н. Непозиционное кодирование информации в конечных полях для отказоустойчивых спецпроцессоров цифровой обработки сигналов. - Инфокоммуникационные технологии. №3 2007 года, с.36-39.
  4. Калмыков И.А., Ермолаева Е.В., Резеньков Д.Н.. Спектральный методобнаружения и коррекции ошибок в кодах ПСКВ. - Научно-техническая конференция. ч.1, с.153.

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

Калмыков И.А., Резеньков Д.Н. ЛОКАЛИЗАЦИИ ОШИБОК В МОДУЛЯРНЫХ КОДАХ ПОЛИНОМИАЛЬНОЙ СИСТЕМЫ КЛАССОВ ВЫЧЕТОВ С МИНИМАЛЬНОЙ ИЗБЫТОЧНОСТЬЮ // Фундаментальные исследования. – 2008. – № 3. – С. 75-76;
URL: http://fundamental-research.ru/ru/article/view?id=2785 (дата обращения: 19.06.2019).

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

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