УДК 681.3

КОНТРОЛЬ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ

Кондрашов Александр Владимирович1, Горденко Дмитрий Владимирович1, Резеньков Денис Николаевич1
1Ставропольский государственный аграрный университет

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

Ключевые слова: АN-код, коррекция ошибок, ортогональные базисы, система остаточных классов


CONTROL ARITHMETIC OPERATIONS IN THE RESIDUE NUMBER SYSTEM

Kondrashov Aleksandr Vladimirovich1, Gordenko Dmitry Vladimirovich1, Rezenkov Denis Nikolaevich1
1Stavropol state agrarian university

Abstract
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.

Keywords: AN-code, correction of mistakes, orthogonal bases, residue number system


Рубрика: Математика

Библиографическая ссылка на статью:
Кондрашов А.В., Горденко Д.В., Резеньков Д.Н. Контроль арифметических операций в системе остаточных классов // Исследования в области естественных наук. 2014. № 6 [Электронный ресурс]. URL: http://science.snauka.ru/2014/06/7491 (дата обращения: 01.05.2017).

Модулярные коды системы остаточных классов обладают потенциальными возможностями по построению кодов, имеющих возможность обнаруживать и исправлять ошибки в процессе функционирования, независимо от причины возникновения арифметических ошибок [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-кодов для контроля арифметических операций в системе остаточных классов имеет следующие достоинства: простота реализации; быстродействие; не большой объем вычислений и уменьшение аппаратурных затрат.


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


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


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

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться: