УДК 681.3

КОНТРОЛЬ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ НА ОСНОВЕ ПРИМЕНЕНИЯ AN-КОДОВ

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

Аннотация
В статье представлен сравнительный анализ чисел, представленных в системе остаточных классов и AN-коде. Анализ показал, что естественная избыточность AN-кода намного выше, чем избыточность чисел, представленных в системе остаточных классов. Определены достоинства AN-кода.

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


CONTROL ARITHMETIC OPERATIONS THROUGH THE APPLICATION OF AN-CODES

Gordenko Dmitry Vladimirovich1, Kondrashov Alexander Vladimirovich1, Doroshev Alexander Vasilevich1
1Stavropol state agrarian university

Abstract
The article presents a comparative analysis of the numbers represented in Residue number system and the AN-code. Analysis showed that the natural redundancy AN-code is much higher than the redundancy of numbers represented in the remaining classes. Defined dignity AN-code.

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

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

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

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

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

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

.                    (1)

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

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

.                    (2)

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

                    (3)

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

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

,                (4)

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

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

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

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

,            (5)

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

.                        (6)

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

,                    (7)

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

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

,                    (8)

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

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

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

,                          (9)

,                  (10)

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

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

,            (11)

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

,

,

, (12)

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

.

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

.                    (13)

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

1-й этап:

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

,

,            (14)

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

.

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


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

2-й этап

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

.                        (15)

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

,                     (16)

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

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

,                    (17)

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

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

.            (18)

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

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

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

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

,                    (19)

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

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

.            (20)

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

.            (21)

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


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


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


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

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

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

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

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