Модулярные коды полиномиальной системы классов вычетов ПСКВ обладают потенциальными возможностями по построению кодов, способных обнаруживать и исправлять ошибки в процессе выполнения операций, независимо от природы возникновения арифметических ошибок [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)) =ai(z)Bi(z)modPполн(z). (1)
Если положить условие, что полином A(z) является разрешенным, т.е. A(z)ÎPpa6(z), то справедливо
A(z) = (a1(z), a2(z), ...,ak(z)) = aj(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)- A1(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, по контрольному основанию даст значения
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(z)рk+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).
Следует отметить, что распределение ошибок по интервалам числового диапазона полностью зависит от величины контрольного основания, т.е. от имеющей место избыточности.
СПИСОК ЛИТЕРАТУРЫ:
- Калмыков И.А. Математические модели нейросетевых отказоустойчивых вычислительных средств, функционирующих в полиномиальной системе класса вычетов. - М.: ФИЗМАТЛИТ, 2005. -274с.
- Калмыков И.А., Червяков Н.И., Щелкунова Ю.О., Бережной В.В. Архитектура отказоустойчивой нейронной сети для цифровой обработки сигналов /Нейрокомпьютеры: разработка, применение. №12, 2004, с.51-60.
- Калмыков И.А., Тимошенко Л.И., Резеньков Д.Н. Непозиционное кодирование информации в конечных полях для отказоустойчивых спецпроцессоров цифровой обработки сигналов. - Инфокоммуникационные технологии. №3 2007 года, с.36-39.
- Калмыков И.А., Ермолаева Е.В., Резеньков Д.Н.. Спектральный методобнаружения и коррекции ошибок в кодах ПСКВ. - Научно-техническая конференция. ч.1, с.153.
Библиографическая ссылка
Калмыков И.А., Резеньков Д.Н. ЛОКАЛИЗАЦИИ ОШИБОК В МОДУЛЯРНЫХ КОДАХ ПОЛИНОМИАЛЬНОЙ СИСТЕМЫ КЛАССОВ ВЫЧЕТОВ С МИНИМАЛЬНОЙ ИЗБЫТОЧНОСТЬЮ // Фундаментальные исследования. – 2008. – № 3. – С. 75-76;URL: https://fundamental-research.ru/ru/article/view?id=2785 (дата обращения: 16.10.2024).