Устройство для выполнения операций над полиномами в конечных полях

 

Изобретение относится к цифровой вычислительной технике и может быть использовано при построении кодирующих и декодирующих устройств для вычислений в конечных полях Галуа. Цель изобретения - расширение функциональных возможностей устройства путем увеличения набора выполняемых операций, а также обеспечения возможности изменения размерности поля. Поставленная цель достигается тем, что устройство содержит регистры 1, 2, 4 сдвига, генератор 3 импульсов, два элемента И-НЕ 5, 6, ДВА ЭЛЕМЕНТА И 7, 8 И ЭЛЕМЕНТ ИЛИ 9, вход 10 ввода размерности, вход 11 ввода последовательности, вход 12 ввода полинома, вход 13 установки, вход 14 разрешения записи, вход 15 запуска и выход 16 результата операции. 1 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 G 06 F 15/31

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABT0PCH0MV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕ .

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4436230/24-24 (22) 06.06.88 (46) 15.03.90. Бюл. ¹ 10 (72) Б. П. Козлов, Г. Л. Сливин, В. M. Трембач и Ю. A. Трубчанинов (53) 68!.325(088.8) (56) Авторское свидетельство СССР № 1 226445, кл . G 06 Р 7/52, 1984.

Авторское свидетельство СССР № 1295579, кл. G 06 F 5/31, 1 987. (54) УСТРОЙСТВО ДЛЯ ВЪП1ОЛНЕНИЯ ОПЕРАЦИЙ НАД ПОЛИНО||АМИ В КОНЕЧНЪ|Х ПОЛЯХ (57) Изобретение относится к цифровой вычислительной технике и может быть использовано при построении кодирующих и декодирующих устройств для вы„.Я0„„155О5З1 А

2 числений в конечных полях Галуа. Цель изобретения — расширение функциональных возможностей устройства путем увеличения набора выполняемых операций, а также обеспечения возможности изменения размерности поля. Поставленная цель достигается тем, что устройство содержит регистры 1, 2, 4 сдвига, генератор 3 импульсов, два элемента И-НЕ 5, 6, два элемента И 7, 8 и элемент ИЛИ 9, вход 10 ввода размерности, вход 11 ввода последовательности, вход 12 ввода полинома, вход

13 установки, вход 14 разрешения записи, вход !5 запуска и выход !6 результата операции. 1 ил.

1550531

Изобретение относится к специалиэ ированным вычислительным ус тройствам и может быть использовано при пос троении кодирующих и декодирующих устройств для выполнения вычислений в конечных полях Галуа GF (2")..

Цель изобретения — расширение функциональных возможностей устройства, т1утем увеличения набора выполняемых операций путем увеличения набора выполняемых операций, а также обеспечеь1ия возможности изменения размерности гоголя.

На чертеже представлена йункциойальная схема устройства.

Устройство содержит: первый 1 и второй 2 регистры сдвига, генератор 3 импульсов, третий 4 регистр сдвига, ва элемента И-НЕ 5, 6, два элемента 20

Й 7, 8 и элемент ИЛИ 9.

Устройство имеет вход 10 ввода раз ерности, вход 11 ввода последовательНости, вход !2 ввода полинома, вход

13 установки, вход 14 разрешения за- 25 йиси, вход 15 запуска и выход 16 результата операции. Вход 10 устройства

Служит для получения размерности поля

I;anya GF (2"), вход 11 — для получения

К-1) — разрядной двоичной последова- 30 .ельности, определяющий неприводимый олином в поле Галуа заданной размер ности, вход 12 — для ввода полиномов, ход 14 для получения сигнала разреЬения записи полинома, вход 13 — для установки устройства в исходное состояние, вход 15 — для запуска гене ратора импульса.

Устройство работает следующим об разом.

При выполнении любой операции в

Поле Галуа GF (2 ) вначале задается и размерность этого поля. Для этого по входу 10 устройства поступает сигнал на входы первь х разрядов первого 1, второго 2 и третьего 4 регистров сдвига. Сигнал, задающий размерность поля, представляет собой последовательность длины (n-1) двоичных символов, содержащую в К-м разряде единич50 ный символ, а во всех остальных разрядах нули, К = 1, п-1.

Затем, по входу 11 устройства поступает сигнал в виде (К-1) — разрядной двоичной последовательности, определяющий неприводимый полином в поле

Галуа заданной размерности, который поступает на вхоцы вторых разрядов первого регистров сдвига 1, 2 и 4.

При выполнении любой операции заданной в поле, т.е. операции сложения, умножения и деления, первый полином в виде 1-разрядной двоичной последовательности 1 = 1, и поступает по входу 12 устройства на вход третьего разряда первого регистра сдвига I Одновременно с этим, по входу

14 разрешения записи устройства на вход разрешения записи первого регистра 1 сдвига поступает сигнал, разрешающий запись первого операнда. .Для выполнения операции сложения аналогично осуществляется запись второго полинома и в первом регистре. сдвига 1 будет получен результат сложения двух полиномов.

При выполнении операции умножения второй полином записывается в разряды второго 2 регистра сдвига, для чего по входу 14 разрешения записи устройства на вход разрешения записи второго регистра 2 сдвига подается сигнал, разрешающий запись, а на входе третьего разряда второго регистра

2 сдвига подается второй полином. Затем по входу запуска 15 устройства подается сигнал запуска генератора. импульсов 3. С выхода генератора импульсов на входы сдвига первого 1 и второго 2 регистров сдвига поступают импульсы до тех пор пока во втором регистре сдвига 2 не будет сформирован единичный полином. Тогда с выхода первого элемента И 7 через элемент, 9 ИЛИ выдается сигнал останова гене" ратора 3 импульсов, который поступает на его вход останова. При этом результат умножения будет записан в— первом регистре 1 сдвига.

Выполнение операции деления .осуществляется аналогично операции умножения, за исключением того, что второй полином записывается в третий регистр

4 сдвига, а сигнал останова генера.тора импульсов поступает с выхода второго элемента 8 И через элемент

9 ИЛИ на вход останова генератора импульсов ° Результат деления также будет записан в первом 1 регистре сдвига.

Для выполнения очередной операции устройство приводится в исходное состояние, для чего по входу установки устройства на выходы установки в ноль первого 1, второго 2, третьего 4 регистров сдвига выдается сигнал установки регистров в нулевое состояние.

Составитель С. Аверьянова

Редактор Л. Пчолинская Техред М.Дидик, Корректор В. Кабаций

Заказ 274 Тираж 565 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г.Ужгород, ул. Гагарина, 101

5 1 55053

Формула изобретения

Устройство для выполнения операций над полиномами в конечных полях, содержащее два регистра сдвига и генератор импульсов, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональных возможностей устройства путем увеличения набора выполняемых операций, а также обеспечения возможности изменения размерности поля, в него введены третий регистр сдвига, два элемента И-НЕ, два элемента И и элемент ИЛИ, причем входы 15 ввода размерности, ввода последовательности и ввода полинома устройст ва соединены соответственно с входами первого, второго и третьего разрядов всех регистров сдвига, входы 20 установки и разрешения записи устройства — соответственно с входами установки в "0" и разрешения записи всех регистров сдвига, входы сдвига которых соединены с выходом генера- 25 тора импульсов, вход запуска которо1 6

ro является входом запуска устройства, вход останова генератора импульсов соединен с выходом элемента ИЛИ, первый вход которого соединен с выходом первого элемента И, первый вход которого соединен с выходом первого разряда второго регистра сдвига, а второй вход элемента И соединен с вы-, ходом первого элемента И-НЕ, входы которого соединены соответственно с выходами разрядов с второго по и-й второго регистра сдвига (где и — разрядность регистров сдвига равная степени полинома), второй вход элемента

ИЛИ подключен к выходу второго элемен та И, первый вход которого соединен с выходом первого разряда третьего регистра сдвига, а второй вход элемента И соединен с выходом второго элемента И-НЕ, входы которого соединены соответственно с выходами разрядов с второго по п-й третьего регистра сдвига, выход первого регистра сдвига является выходом результата операции устройства.