Устройство для определения вычетов

 

ПИСАНИЕ

ИЗОБРЕТЕНИЯ

Сова Сооетеккк пц660054

Социалистических

Республик

К ЯваОо СКОМУ СВМДЕХЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 12.04.77 (21) 2490108/18-24 с присоединением заявки ¹â€” (23) Приоритет— (5I ) М. Кл.

G 06F 11/08

Государствеииый комитет

Совета Министров СССР ро девам иааоретений

pr открытий (43) Опубликовано 30.04.79. Бюллетень № 16 (53) УДК 681.327 (088.8) (45) Дата опубликования описания 30.04.79 (72) Авторы изобретения

Р. Р. Варшамов и В. Н. Дынькин

Ордена Ленина институт проблем управления АН СССР (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ВЫЧЕТОВ

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

Известны устройства для вычисления в алгебре многочленов и конечных полей (1).

Однако их применение для вычисления вычетов по модулю фиксированного многочлена неэффективно из-за низкого быстродействия, ибо для определения вычета одночлена х" приходится находить вычеты всех одночленов х при i меньших п.

Наиболее близким техническим решением к данному предложению является устройство для определения вычетов, содержащее генератор импульсов, выход которого соединен со входом блока управления, первый и второй выходы которого соединены с управляющими входами кольцевого регистра и сумматора (21. Оно позволяет устанавливать разложимость многочлена, его неприводимые сомножители, их количество и степени, При нахождении показателя неприводимого многочлена f (x) степени к следует определить еще и вычеты двучленов x" — I (modf(x) ), где п — делитель числа 2 — 1.

Целью изобретения является повышение быстродействия при нахождении вычетов по модулю произвольного многочлена с

2 коэффициентами из поля GF j2 и вычисления его показателя (периода).

Цель изобретения достигается тем, что устройство содержит дополнительный регистр, коммутатор и группу элементов И, первые входы которых подключены к третьему выходу блока управления, вторые— к разрядным выходам дополнительного регистра, а выходы — к первым входам кольцевого регистра и дополнительного регистра, выход которого через коммутатор подключен ко второму входу кольцевого регистра, разрядные выходы кольцевого и дополнительного регистров подключены ко

15 входам сумматора, выход которого подключен к разрядным входам дополнительного регистра, управляющий вход которого подключен к четвертому выходу блока управления.

20 Функциональная схема устройства для определения вычетов изображена на чертеже.

Устройство содержит генератор 1 импульсов, блок 2 управления, коммутатор 3, 25 регистр 4 сдвига, сумматор 5, кольцевой регистр 6 с обратной связью и группу 7 элементов И.

Устройство работает следующим образом. В первоначальный момент времени доЗО полнительный рсгпстр 4 сдвига и кольце660054

3 вой регистр 6, соединенные через коммутатор 3, образуют единый регистр. Обратная связь кольцевого регистра 6 вы;:люче;1а.

Нумерация ячеек ед1шого рсгисгра начинается с крайней правой ячейки рс;истра 4 сдвига. При задан1111 11роизиольного хногочлена j(x) степени k коммута1ор 3 по сигналу с блока 2 управления устанавливает длину регистра 4 сдвига и кольцевого регистра 6 равную й. Б дополнительный регистр 4 и кольцсвой регистр 6 занссятся коэффициенты исследуемого многочлена, степень которого не превышает 2k. При этом в регистр 4 сдвига заносятся коэффициенты при степенях х от 1 до А, а в кольцевой регистр 6 — от k+ 1 до 2k.

Устройство начинает действовать при подаче тактовых импульсов с генератора 1 импульсов, Содержимое ячеек в едином регистре 4-6 может либо сдвигаться «лево, либо с помощью группы 7 элементов И переноситься из ячейки с номером 1 в ячейку с номером 21, l (i(k. Как только содержимое кольцевого регистра 6 становится ненулевым, блок 2 управления чере- коммутатор 3 разъединяет регистр 4 и кольцевой регистр 6 и включает обратную связь кольцевого регистра соответственно многочлену f (x). 1,одержимое кольцевого регистра 6 сдвигается циклически в теченис k тактов, а содержимое регистра 4 остается неизменным. Через k "àêòîâ блок 2 1правления отключает обратную связь и включает суммаfop 5. Содержимое регистра 4 сдвига и кольцевого регистра 6 суммируется и записывается в дополнительный регистр 4, а кольцевой регистр 6 очищается.

В дополнительном регистре 4 сдвига теперь находится вычет исследуемого многочлена по модулю многочлена х/(х). Устройство возвращается в первоначальное состояние и процесс, если это необходимо, 110вторястся. Количество таких повторений (циклов) устанавливается заранее и фиксируется блоком 2 управления.

ll p им ер. 111сть Е(х) =х +х- +1, то есть

k = 5. Требуется найти вычет одночлсна х" по модулю xf(х) и 1 (х), Поскольку хз =х((х ) xP, процесс вычисления начинается с вычисления вычета одночлена х7.

Длина регистра 4 и регистра 6 устанавливается равной 5-ти ячейкам с номерами

10, 9, 8, 7, 6 в регистре 6 и 5, 4, 3, 2, 1 в регистре 4. С ячейки 10 имеется обратная связь на ячейки 8 и 6.

Коэффициенты исследуемого многочлена х7 заносятся в регистры. Заполнение регистра 6 имеет вид: О О О 10, регистра 4

0 00 0 0. Поскольку содержимое регистра 6 отлично от нуля, регистры 4 и 6 разъединяются и включается обратная связь регистра 6, соответствующая многочлену х +х + 1. Производим пять сдвигов. Содержимое регистра 6 соответственно приниЭ

Зо

45 мает значения: 00100, 01000, 10000, О 1 О 1 О.

Затем содержимое регистра 6 складывается с содержимым регистра 4 (нулевым) и записывается в регисгр 4, а регистр 6 очи1Ilается. Содержимое регистра 4: О 10 1 О— вычет х modx (х — х + 1) .

В едином регистре содержимое «13 ячейки с номером 2 переносится в ячейку с номером 4, а из ячейки 4 — — в ячейку 8. Прп этом содержимое регистра 6: О О 1 О О, а регистра 4: 0 1 0 00.

Содержимое регистра 6 ненулевое. Единичнь1й регистр распадается и включается обратная связь.

Производится пят1з сдвигoB.

01000, 1 0000, 00 101, 01010, 1 О 1 О О.

Содержимое рсгпсгра 6 складывается с содержимым в регистре 4 и записывается в регистр 4, регистр 6 очищается.

Содержимое регистра 4: 1 1 1 ΠΠ— вы.Iет х14

Б регистре 4 находится вычст функции (х7) . Умножение на х равносильно сдвигу содержимого в едином pcl iicòpc па один

132зряд В.Iсво, что coo I Bc Гс; ву с1 содер:кпмому в регистре 6: 000 О ., рег11стре 4:

1 1 О О О.

Снова сдвигаем ва 5 тактов содержимое регистра 6:

00010, 00100, 01000, 10000, О О 1 О 1.

Складываем содсргк11мос рег1стров 6 и 4.

Результат записываем в регистр 4:

++ 10 1 — — вычет х1- . Содержимое регистра 6 обнуляем. B регистре 4 переносим из первой ячейки во вторую, пз 3 — в 6, из

4 — — в 8, из 5 — — в 10-ю. При этом содержимое регистра 6: 1 О 1 О 1, регистра 4: О О О 1 О.

Сдвигаем пять р;13 содержимое регистра 6:

01111, 11110, 11001, 10111, 0 1 О 1 1.

Складываем содержимое регистров 6 и

4. Результат записываем в регистр 4:

0 1 0 0 1 — вычет х".

Содержимое регистра 6 обнуляем.

Сдвигаем влево Ia один разряд содержимое регистра 4:

Содержимое регистра 4; 1 О О 1 Π— вы,1ет- <31

Б регистре 4 записан вычет одночлепа х" по модулю xf (х) =х +х +х, равный х + х .

660054

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

Составитель P. Варгпат;ов

Техред Н. Строганова

Koppe:iTîð Е. Угроватова

Редактор Б. Герцен

Заказ 568/10 Изд. ¹ 2о5 Тирани 779 Подписное

НПО Государственного ко:.:итста СССР по де. з:„изобретений ll открытий

113035, л,ос в», )K-35. Рау :";"l;«:ë.|., д. 4 5

Типография, пр. Сапунова, 2

Действительно хз = (х -+х -,— х) (хв5++- х" -+ хдо-+х|в- хгв-+х|в-+х"--+х з-+х в

+xII+x +x x4 - +x +x

Для опредслс; ия вычета по модул1о

f(x) переносим содержимое регистра 4 в регистр 6, что осуществляется сдвигом влево на пять тактов.

Тогда содержимое регистров примет вид: регистра 6: 1 О 0 1 О, регистра 4: О G О 0 О.

Сдвигаем влево один раз при вкл1оченной обратной связи содержимое регистра 6:

00001.

Складываем содержимое регистров 6 и 4.

Результат записываем в регистр 4. Содержимое регистра 6: О О О О О, регистра 4: 15

О О О О 1 — вычет х" (modx + х + 1)

Таким образом, вычет х" по модулю х +х +1 равен единице. Поскольку 31 число простое, делаем вывод, что многочлен

f(x) неприводим и, более того, приметивен. 20

Из представления х" =х((х ) ) видно, что в процессе вычисления находятся вычеты одночленов с х 4 х15 хзо Таким образом, общее количество циклов (сдвигов на пять тактов в регистре 6 с обратной связью) для 25 определения вычета х" (modxt(x) ) не превышает )log 31(= 5.

Таким образом, предлагаемое устройство обеспечивает увеличение скорости при нахождении показателя исследуемого много- 30 члена и предоставляет дополнительную возможность быстрого нахождения вычета произвольного многочлена по заданному.

Устройство для определения вычетов, содср>кащсе генератор импул сов, выход которого соединен со входом блока управления, первый и второй выходы которого соединены с управляющими входами кольцевого регистра и сумматора, о т л и ч а ющееся тем, что, с целью повышения быстродействия устройства, оно содержит дополнительный регистр, коммутатор и rpyniiy элементов И, первые входы которых подключены к третьему выходу блока управления, вторые — к разрядным выходам дополнительного регистра, выходы — к первым входам кольцевого регистра и дополнительного регистра, выход которого через коммутатор подключен ко второму входу кольцевого регистра, разрядные выходы кольцевого регистра и дополнительного регистра подключены ко входам сумматора, выход которого подключен к разрядным входам дополнительного регистра, управляющий вход которого подключен и четвертому выходу блока управления.

Источники информации, принятые во внимание при экспертизе

1. Питерсон У., Уэлдоц Э Коды, исправляющие ошибки. М„«Мир», 1976, 2. Авторское свидетельство СССР

¹ 257148, кл. G 06F 7/38, 1969.