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

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

Принцип использования AN-кодов для коррекции ошибок в системе остаточных классов заключается в следующем. Каждый остаток по модулю p_i представляется двоичным позиционным кодом N, который умножается на константу A. Далее производится выполнение арифметической операции над числами вида AN и последующее декодирование, включающее обнаружение и исправление ошибки.

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

.                    (1)

В этом случае общее число всех возможных кодовых комбинаций равно . Количество используемых кодовых комбинаций в одном основании СОК равно.

Отношение количества используемых кодовых комбинаций к количеству возможных

.                    (2)

Величину равную

                    (3)

будем называть коэффициентом избыточности кода.

При переводе чисел представленных остатками СОК в AN-код, разрядность остатков будет равна

,                (4)

где p_i – основания системы остаточных классов; A – константа; , – коэффициенты использования кодов представленные СОК и AN-кодом соответственно.

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

Для оценки объема вычислений при контроле арифметических операций проведем сравнительную оценку.

Известно, что коэффициенты системы счисления со смешанным основанием (обобщенная полиадическая система (ОПС)) могут быть использованы для обнаружения, локализации и исправления ошибки в системе остаточных классов. Целое число АÎ[0, P-1], где P=p₁×p₂×p₃×…×p_n –диапазон представимых чисел, может быть представлено в виде

,            (5)

где а_i – коэффициенты ОПС; p_i – основания системы счисления, для i=1, 2, …, n. Если принять p₁, p₂, p₃,…, p_n одновременно основаниями СОК и ОПС, тогда диапазоны представления чисел совпадают. Число А представляется в системе остаточных классов в виде набора наименьших неотрицательных вычетов (a₁, a₂, …, a_n), вычисленных по модулю каждого из оснований p_i и определяются выражением

.                        (6)

Число А=(a₁, a₂, …, a_n) можно восстановить в позиционной системе счисления с помощью выражения

,                    (7)

где B_i-ортогональные базисы СОК, i=1,2,…, n; P-диапазон представимых чисел в СОК.

Представления числа СОК в ОПС имеет вид

,                    (8)

где а_i – коэффициенты ОПС.

Преобразование данных, представленных в СОК в представлении ОПС осуществляется следующим образом.

Вычисляются ортогональные базисы B_i системы в зависимости от выбранных оснований СОК [1]

,                          (9)

,                  (10)

где m_i – веса ортогональных базисов; i=0, 1,…, n.

Представим ортогональные базисы B_i в ОПС, тогда

,            (11)

где b_i – коэффициенты ОПС, нахождение которых может быть осуществлено выражением

,

,

, (12)

…………………………… ,

.

Представления ортогональных базисов в ОПС имеет вид

.                    (13)

Для последовательного получения коэффициентов ОПС необходимо выполнить следующие операции [3].

1-й этап:

Производится произведение ортогональных базисов представленных в обобщенной полиадической системе на остатки a_i по модулю с учетом переноса при i=1,…, n. Перенос по основаниям p₁ и p_n не происходит.

,

,            (14)

……………………………… ,

.

Представим соотношение (14) в виде матрицы для более простого восприятия [1], [2]

где a_i – остатки по заданным основаниям СОК; i=1,…, n.

2-й этап

Получение коэффициентов ОПС a_i получаются суммированием по модулю p_i всех произведений k_ij (16) с учетом переноса при i=1,…, n. Перенос по основаниям p₁ и p_n не происходит.

.                        (15)

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

,                     (16)

где n – количество оснований системы остаточных классов.

Исходя из выше изложенного, количество операций Q для обнаружения ошибки в системе остаточных классов при условии, что базисы СОК вычислены и переведены в ОПС найдем по формуле

,                    (17)

где - количество операций на первом и втором этапах при переводе чисел представленных в СОК в ОПС; N-общее количество переносов.

Подставляя (17) и приняв G=1, L=1 получим

.            (18)

Из соотношения (18) следует, что количество выполняемых операций для обнаружения ошибки будет зависеть от количества оснований системы остаточных классов.

Для определения места ошибки используется метод проекций. Проекция p_i обозначается как , т.е. A представлено в сокращенной избыточной СОК при исключении i-й остаточной цифры. Следовательно, если окажется такая ситуация, что для любого произвольного числа A одна из проекций числа A_i будет правильной для любого i=1,…, n+r, тогда все другие проекции X_j при j≠i являются неправильными и остаточная цифра a_i определяется как ошибочная. В этом состоит суть метода локализации ошибки.

Локализация ошибки может быть решена путем вычисления цифр ОПС для n+r проекций и определения, которые из избыточных цифр ОПС нулевые

Пусть представлено в СОК по соответствующим основаниям p₁
, p₂,…, p_n, p_n+1, тогда при определении ошибки по основанию p_n+1 потребуется p_n проекций. Следовательно, количество операций для локализации ошибки определится выражением

,                    (19)

где Q- количество операций для вычисления коэффициентов ОПС.

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

.            (20)

Таким образом, общее количество операций необходимых для локализации ошибки в СОК определится выражением

.            (21)

Исходя из проведенного анализа, сделаем вывод, что применение AN-кодов для контроля арифметических операций в системе остаточных классов имеет следующие достоинства: простота реализации; быстродействие; не большой объем вычислений и уменьшение аппаратурных затрат.

1. Горденко Д.В., Резеньков Д.Н., Яйлаханов С.В. Высоконадежные комплексы и средства связи на нейросетевых элементах.  Москва, 2010.
2. Калмыков И.А., Резеньков Д.Н. Локализации ошибок в модулярных кодах полиномиальной системы классов вычетов с минимальной избыточностью
   Фундаментальные исследования. 2008. № 3. С. 23.
3. Калмыков И.А., Резеньков Д.Н., Горденко Д.В., Саркисов А.Б. Методы и алгоритмы реконфигурации непозиционных вычислительных структур для обеспечения отказоустойчивости спецпроцессоров. Монография. / – Ставрополь: издательско информационный центр «Фабула». – 2014. –180 с.

Все статьи автора «Горденко Дмитрий Владимирович»