Scientific journal

Fundamental research

ISSN 1812-7339

"Перечень" ВАК

ИФ РИНЦ = 1,674

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

Если на диапазон возможного изменения кодируемого множества полиномов наложить ограничения, то есть выбрать к из п оснований ПСКВ (к<п), то это позволит осуществить разбиение полного диапазона P_полн(z) расширенного поля Галуа GF(p^v) на два непересекающихся подмножества.

Первое подмножество называется рабочим диапазоном и определяется выражением

                           (1)

Многочлен A(z) с коэффициентами из поля GF(p) будет считаться разрешенным в том и только том случае, если он является элементом нулевого интервала полного диапазона P_полн(z), то есть принадлежит рабочему диапазону [2]

Второе подмножество GF(p^v), определяется произведением r=n-k контрольных оснований

                                                           (2)

задает совокупность запрещенных комбинаций. Если A(z) является элементом второго подмножества, то считается, что данная комбинация содержит ошибку. Таким образом, местоположение полинома A(z) относительно двух данных подмножеств позволяет однозначно определить, является ли кодовая комбинация    разрешенной, или она содержит ошибочные символы.

Рассмотрим корректирующие способности кодов ПСКВ, использующих одно контрольное основание [1]. В упорядоченной системе оснований ПСКВ в качестве контрольного основания выбирается модуль, удовлетворяющий условию

ord p_i(z) ≥ ord p_k+1(z)                    (3)

где i=1,2,...,k

Cчитаем, что если исходные операнды  и , как и результат выполнения арифметической операции в расширенном поле Галуа GF(p^v)

C(z)=A(z)◦B(z)

где ◦ - арифметическая операция, лежит внутри диапазона P_раб(z), то полином  не содержит ошибок. В противном случае, результат С(z) является ошибочным.

Переход из множества разрешенных комбинаций ПСКВ во множество запрещенных осуществляется в результате искажения значения остатка γ_i(z), i=1,...,k+1 и преобразования его к виду γ_i^*(z)≠ γ_i(z)

Заметим, что если полиномом С(z) является элементом рабочего диапазона, то справедливо:

С(z)< P_полн(z)/ p_k+1(z)                                          (4)

В тоже самое время, для упорядоченной системы оснований ПСКВ, выбор контрольного основания p_k+1(z), удовлетворяющего условию (3), обеспечивает выполнение

P_полн(z)/ p_i (z)≥P_полн(z)/ p_k+1(z)                               (5)

Тогда, на основании (4) справедливо

С(z)< P_полн(z)/ p_i(z)                                             (6)

Но искажение остатка по i-ому основанию ПСКВ приводит к тому, что полином C(z) не может находиться в интервале [0,P_полн(z)/p_i(z)]. Следовательно

С*(z)< P_полн(z)/ p_i(z)                                    (7)

тогда, исходя из условия (6), получаем

С*(z)> P_полн(z)/ p_k+1(z)

Следовательно, полином C*(z) не принадлежит рабочему диапазону P_pa6(z), и он содержит ошибку [3].

Если в упрощенной системе оснований p₁(z),...,p_k+1(z) ПСКВ полиномиальной системе классов вычетов расширенного поля Галуа GF(2^v) полином С*(z)ÏP_pa6(z), то модулярный код данного полинома содержит как минимум одну ошибку.

Положим, что C*(z) не содержит ошибки. Согласно китайской теореме об остатках имеем

С(z)=|γ₁(z)B₁(z)+...+ y_i^* (z)B_i(z)+...+y_k+1(z) B_k+1(z)|⁺_Pпол(z)                            (8)

В то же самое время существует элемент последовательности C_IR(z), который отличается от С*(z) значением по i-ому основанию γ _i^* = γ _i + ∆ γ _i(z) принадлежит P_pa6(z).

С(z)=| γ₁(z)B₁(z)+... + y_i (z)B_i(z)+...+y_k+1(z)B_k+1(z)|^*_Pпол(z)                                   (9)

Следовательно

[C*(z)/ P_pa6(z)]= [C(z)/ P_pa6(z)]                             (10)

Подставим выражения (8) и (9) в равенство (10) и, преобразовав их с учетом

B₁(z) = m_i(z)P_полн(z)/p_i(z) = m_i(z)P_pae(z)p_n+1(z)/p_i(z),           (11)

Получаем

 y_l(z)m_i(z)p_n+1(z)/p_i(z) =(γ _i +∆γ _i(z)) m_i(z) p_n+1(z)/p_i(z).                     (12)

Равенство (12) выполняется при условии γ _i(z) =(γ _i(z) + ∆ γ _i(z)), т.е. ∆ γ _i(z)=0.

Но согласно исходным данным γ _i^*(z)≠γ _i(z). Следовательно, C*(z) coдержит ошибку по i-ому основанию полиномиальной системы классов вычетов [1].

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

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

1. Калмыков И.А. Математические модели нейросетевых отказоустойчивых вычислительных средств, функционирующих в полиномиальной системе класса вычетов.-М.: ФИЗМАТЛИТ,2005.-274 с.
2. Калмыков И.А., Щелкунова Ю.О., Гахов В.Р., Шилов А.А. Математическая модель коррекции ошибок в полиномиальной системе класса вычетов на основе определения корней интервального полинома. - Физика волновых процессов и радиотехнические системы. Том 6, №5, с. 30-34.
3. Калмыков И.А., Тимошенко Л.И., Резеньков Д.Н. Непозиционное кодирование информации в конечных полях для отказоустойчивых спецпроцессоров цифровой обработки сигналов. - Инфокоммуникационные технологии. №3, 2007 года, с.36-39.