Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

COMPARATIVE ANALYSIS OF THE CONTROL METHOD OF ARITHMETIC OPERATIONS IN THE RESIDUE NUMBER SYSTEM

Gordenko D.V. 1 Rezenkov D.N. 2
1 Stavropol state agrarian university
2 Branch of the Russian state social university in Stavropol
Modular codes of residue number system possess potential opportunities to create the codes, capable to find and correct errors in the course of operation performance, irrespective of the nature of emergence of arithmetic errors. In case of error detection the correction of a wrong combination is made. The comparative analysis of the numbers represented in the residue number system and AN code is given in the article. The analysis showed that natural redundancy of an AN code is much higher, than redundancy of the numbers represented in the residue number system. AN code advantages are determined. On the basis of the carried-out analysis it is possible to make a conclusion that application of AN codes to control the arithmetic operations in the residue number system has the following advantages: simplicity of realization; speed; not large volume of calculations and reduction of hardware expenses.
residue number system
correction of mistakes
orthogonal bases
AN-code

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

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

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

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

. (1)

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

Выберем основания системы остаточных классов p1=3, p2=5, p3=7, p4=11. Разрядность остатков по заданным основаниям системы согласно (1) будет равна:

, , , .

Число всех возможных кодовых комбинаций равно:

, , , .

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

Введем в рассмотрение коэффициент использования кода, под которым условимся понимать отношение количества используемых кодовых комбинаций к количеству возможных

. (2)

Коэффициент использования кода по заданным основаниям СОК равен:

, ,

, .

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

, (3)

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

, ,

, .

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

, (4)

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

Выберем значение A=11, тогда

,

,

,

,

.

Коэффициент использования AN-кода равен:

, ,

, .

Естественная избыточность кода равна

, , , .

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

Сложность устройства может быть оценена в элементах памяти как

, (5)

где m – коэффициент, учитывающий наличие, кроме памяти, дополнительных элементов. Проведем сравнительную оценку согласно выражению (5).

Для обнаружения и исправления однократной ошибки в СОК необходимо ввести не менее двух контрольных оснований, p5=13, p6=19. Сложность устройства согласно (5) будет равна [1]:

,

.

Сложность устройства в AN-коде будет больше, чем устройства в СОК, если не брать во внимание коэффициент m.

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

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

, (6)

где аi – коэффициенты ОПС; pi – основания системы счисления, для i=1, 2, …, n. Если принять p1, p2, p3,…, pn одновременно основаниями СОК и ОПС, тогда диапазоны представления чисел совпадают. Число А представляется в системе остаточных классов в виде набора наименьших неотрицательных вычетов (a1, a2, …, an), вычисленных по модулю каждого из оснований pi , и определяются выражением

. (7)

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

, (8)

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

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

, (9)

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

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

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

, (10)

, (11)

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

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

, (12)

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

,

,

, (13)

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

.

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

. (14)

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

1-й этап

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

,

, (15)

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

.

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

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

2-й этап

Получение коэффициентов ОПС ai осуществляется суммированием по модулю pi всех произведений kij (16) с учетом переноса при i=1,…, n. Перенос по основаниям p1 и pn не происходит.

. (16)

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

, (17)

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

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

, (18)

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

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

. (19)

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

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

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

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

, (20)

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

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

. (21)

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

. (22)

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

Рецензенты:

Калмыков И.А., д.т.н., профессор, профессор кафедры информационной безопасности автоматизированных систем Института информационных технологий и телекоммуникаций ФГАОУ ВПО «Северо-Кавказский федеральный университет», г. Ставрополь.

Копытов В.В., д.т.н., профессор, директор ООО «ИС-Софт», г. Ставрополь.