Scientific journal
Advances in current natural sciences
ISSN 1681-7494
"Перечень" ВАК
ИФ РИНЦ = 0,775

DEVELOPMENT OF ALGORITHMS IN COMPUTING THE RANK NONPOSITIONAL CODES

Goloshubov K.S. 1 Solodkin I.G. 1 Gapochkin A.V 1 Kalmykov M.I. 1
1 Federal state Autonomous educational institution higher professional education «North-caucasian federal university
2604 KB
Modern modular codes have been widely used in many fields of human activity. Among these areas can be identified digital signal processing, the construction of fault-tolerant computing devices, capable of maintaining a healthy state in the event of failure, cryptographic algorithms to protect data. One of the required steps, the use of modular codes is to compute the rank. The paper presents an improved algorithm to compute-ment of the characteristics, as well as the circuit implementation of the neural network.
modular codes
the system of residual classes
polynomial system of residue classes
rank
neural networks

Информационные технологии (ИТ) находят все большее применение в различных областях современного общества. Это обусловлено тем, что ИТ позволяют повысить эффективность работы специалистов во множестве отраслей хозяйства. Наиболее широкое применение IT-технологии нашли в области инфотелекоммуникационных систем. Особое внимание в таких системах уделяется цифровой обработке сигналов (ЦОС). Для обеспечения реального масштаба времени обработки сигналов применяются параллельные алгоритмы вычислений.

Обеспечить высокие требования к производительности вычислительных устройств возможно только за счет реализации алгоритмов ЦОС на основе специализированных процессоров (СП).

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

gol01.wmf. (1)

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

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

gol02.wmf, (1*)

где. – А < Pраб; gol03.wmf.

Пусть даны два числа, представленные в коде СОК gol04.wmf и gol05.wmf. Тогда для суммы, разности и произведения двух чисел А и В, имеющих соответственно модулярные коды и справедливы соотношения при i = 1,…,k

gol08.wmf, (2)

где * – операции сложения, вычитания и умножения по модулю.

Тогда ортогональное преобразование сигнала и ему обратное преобразование будут определяться

gol09.wmf, (3)

gol10.wmf, (4)

где W – поворачивающий коэффициент дискретного преобразования Фурье хi (j) ≡ x(j) mod pi – остаток по модулю отсчета входной последовательности x = {x(0), x(1),..., x(N – 1); Хi(j) ≡ Хi(j) mod pi – остаток по модулю спектрального отсчета сигнала gol14.wmf.

Основу второй группы составляют алгебраические структуры, работающие в кольце полиномов. К ним можно отнести полиномиальную систему классов вычетов (ПСКВ). В данной системе используются неприводимые полиномы pi(z), которые выступают в роли оснований GCRD. Тогда набор этих оснований образует рабочий диапазон

gol15.wmf. (5)

В этом случае, двоичный код числа представляется в полиномиальной форме. Тогда при выполнении условия deg А < deg Pраб, можно однозначно представить в виде набора остатков

gol16.wmf, (6)

где – αi (z) ≡ A(z) mod pi (z); i = 1, 2,...,k.

Пусть даны два числа, представленные в коде ПСКВ gol18.wmf и gol19.wmf. Тогда для суммы, разности и произведения двух чисел А(z) и В(z), имеющих соответственно модулярные коды и справедливы соотношения при i = 1,…,k

gol22.wmf, (7)

где * – операции сложения, вычитания и умножения по модулю.

Так как эти модулярные коды работают с остатками, то благодаря малоразрядности обрабатываемых остатков, реализация вычислений проводится в реальном масштабе времени. При этом такие вычисления осуществляются параллельно по независимым вычислительным каналам, которые определяются модулями кода. Благодаря этому модулярные коды нашли широкое применение не только в области цифровой обработки сигналов [1–3], построения отказоустойчивых вычислительных устройств [4–6], но и при реализации алгоритмов защиты данных от НСД [7–10].

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

Как правило, восстановление полученного результата из непозиционной системы счисления к двоичному позиционному виду на основе китайской теоремы об остатках (КТО) согласно

gol23.wmf (8)

Основным недостатком данного выражения является необходимость выполнения операции суммирования парных произведений по модулю P(z) . При значительных значениях динамического диапазона P(z) построение сумматора по модулю P(z) проблематично.

Одним из путей решения данной проблемы является вычисление ранг числа – K(z). Тогда выражение (8) преобразуется к виду

gol28.wmf (9)

Исходя их условия взаимной простоты модулей gol29.wmf, и равенства (9.) очевидно, что K(z) является целочисленной функцией, определяемой из значений x(z).

В отличие от выражения (8) , в котором значения x(z) нельзя вывести за пределы кольца P(z), равенства (9) осуществляет смещение значения x(z) за пределы этого диапазона P(z). На рис. 1 представлена геометрическая интерпретация выражений (8) и (9). Если диапазон P(z) представить в виде окружности, то равенства (9) может быть описано спирально, с радиусом равным радиусу P(z).

gol106.wmf

Рис. 1. Геометрическая модель: а) – выражения (8); б) – выражения (9)

Если x(z) является элементом P(z), то значение ранга K(z), должно удовлетворить условию

gol41.wmf (10)

где gol42.wmf – полиноминальное представление S.

Следовательно, величина K(z) не зависит от величины оснований gol44.wmf, а определяется только их количеством. Таким образом, для определения величины ранга K(z) удовлетворяющего условию (10), целесообразно ввести дополнительное основание pg(z), которое обеспечивает выполнение следующего равенства

gol47.wmf (11)

где gol48.wmf – порядок полиномов pg(z) и s(z) соответственно.

Введение дополнительного модуля pg(z) обеспечивает выполнение (12).

gol52.wmf (12)

Тогда из выражения (9), разделив обе части на P(z), получаем

gol54.wmf (13)

Используя полученное равенство (13), а также условия (12), имеем

gol55.wmf, (14)

где mi(z) – вес i-го ортогонального базиса, такой что gol57.wmf.

Таким образом, для вычисления значения ранга K(z) необходимо определить значения

gol59.wmf (15)

Следовательно, исходный полином x(z) можно представить в виде gol61.wmf –мерного вектора

gol62.wmf. (16)

При этом дополнительный модуль pg(z) не входит в состав ПСКВ и не оказывает влияние на величину диапазона P(z). Если gol65.wmf, что чаще всего оправдывает себя выбор pg(z), порядок которого не превышает четырех. Следовательно, для реализации (15) не требуется значительных аппаратных затрат.

Таким образом, надо определить величину ранга K(z) согласно (14), а затем на основании выражения (9) осуществить перевод x(z) из ПСКВ в позиционную систему счисления.

Пример 1. Пусть задано расширенное поле Галуа gol69.wmf, которое определяется следующими основаниями:

gol70.wmf

Полный диапазон системы составляет

gol71.wmf

При этом ортогональные базисы данной алгебраической системы равны:

gol72.wmf;

gol73.wmf;

gol74.wmf;

gol75.wmf;

gol76.wmf.

Так число оснований s = 5, то в полиноминальной форме это сложно представить как s = z2 + 1. Тогда, согласно (11), выбираем дополнительное основание pg(z) = z3.

Воспользуемся выражением (9) и определим значение ранга K(z) полинома x(z) = z7 + z6 + z4 + z3 + z + 1, который в исходной ПСКВ представляется в виде

x(z) = (0, z + 1, z, z3 + z, z3 + z2 + z +1)

Для контроля рассчитаем преобразование ПСКВ в позиционную систему счисления по формуле (9)

gol83.wmf

Откуда следует, что

gol84.wmf

Найдем теперь значение ранга K(z), используя выражение (14). Очевидно, что для выбранной системы оснований значения gol86.wmf, где i = 1, 2, 3, 4, 5, определяется следующим образом:

gol87.wmf

Значения весов ортогональных базисов полиномиальной системы классов вычетов поля GF(24), определяются как

gol89.wmf

Так как дополнительное основание pg(z) = z3, то

gol91.wmf

gol91а.wmf.

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

gol92.wmf

Полученное значение ранга K(z) совпадает со значением, непосредственно вычисляемым по формуле (9). Следовательно, предложенный алгоритм позволяет осуществлять выполнение операции вычисления ранга числа, используя только модульные процедуры. Нейросетевая реализация данного алгоритма приведена на рис. 2.

gol107.wmf

Рис. 2. Структура НС для вычисления ранга K(z)

Первый слой нейронной сети состоит из шести нейронов, которые осуществляют прием вектора

x(z) = (α1(z), α2(z), α3(z), α4(z), α5(z), α6(z)),

поданного на вход устройства. Синоптические веса связей gol96.wmf, где i = 1, 2, 3, 4, 5, представляют собой веса ортогональных базисов gol98.wmf и вычисляются заранее.

Результат умножения gol99.wmfи gol100.wmf преобразуется по модулю gol101.wmf во втором слое НС. Приведенные по модулю значения gol102.wmf, затем умножаются на gol103.wmf, и совместно с добавочным остатком подаются на выходной слой НС, где и происходит сложение по модулю gol104.wmf. Полученный результат представляет собой ранг числа K(z).

Заключение

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