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

ПИСАНИЕИЗОБРЕТЕНИЯ Соеоа Сооетеккк Р 1 е 660054 СоеЕкалксткиескик Республик(51) М. Кл,6 06 Г 11/ аявлено присоединением заявки-Государствеииый комитет Совета Министров СССР 23) Приоритет) У 681.327 (088.8) о девам иааоретени к открытий 2) Авторы изобретения Р. Р. Варшамов и В. Н, Дынькиндена Ленина институт проблем управления АН СССР(54) УСТРОЙСТВО ДЛЯ ОПР НИЯ ВЫЧЕТОВ д Оы 5 тся повышение дении вычетов многочлена с ЗО Изобретение относится к области автоматики и вычислительной техники и может быть использовано также, как кодирующее устройство при синтезе циклических кодов.Известны устройства для вычисления в 5 алгебре многочленов и конечных полей 1. Однако их применение для вычисления вычетов по модулю фиксированного многочлена неэффективно из-за низкого быстродействия, ибо для определения вычета о ночлена х" приходится находить вычет всех одночленов х при 1 меньших и.Наиболее близким техническим решением к данному предложению является устройство для определения вычетов, содер жащее генератор импульсов, выход которого соединен со входом блока управления, первый и второй выходы которого соединены с управляющими входами кольцевого регистра и сумматора 2. Оно позволяет 2 устанавливать разложимость многочлена, его неприводимые сомножители, их количество и степени, При нахождении показателя неприводимого многочлена 1(х) степени к следует определить еще и вычеты дву членов х" - 1(тот 11(х, где и - делитель числа 2 - 1.Целью изобретения являебыстродействия при нахожпо модулю произвольного коэффициентами из поля 6 Р 2 и вычисления его показателя (периода).Цель изобретения достигается тем, что устройство содержит дополнительный регистр, коммутатор и группу элементов И, первые входы которых подключены к третьему выходу блока управления, вторые - к разрядным выходам дополнительного регистра, а выходы - к первым входам кольцевого регистра и дополнительного регистра, выход которого через коммутатор подключен ко второму входу кольцевого регистра, разрядные выходы кольцевого и дополнительного регистров подключены ко входам сумматора, выход которого подключен к разрядным входам дополнительного регистра, управляющий вход которого подключен к четвертому выходу блока управления.Функциональная схема устройства для определения вычетов изображена на чертеже.Устройство содержит генератор 1 импульсов, блок 2 управления, коммутатор 3, регистр 4 сдвига, сумматор 5, кольцевой регистр 6 с обратной связью и группу 7 элементов И.Устройство работает следующим образом. В первоначальный момент времени дополнительный рсгпстр 4 сдвига и кольце3вой регистр 6, соединенные через коммутатор 3, образуют единый регистр. Об)ьтная связь кольцевого регистра 6 вылюче;1 а, Нумерация ячеек едшого рсгисгра пачинается с крайней правой ячейки рс;истра 4 сдвига, При задании произольного ь 1 ногочлена /х) степени Й коммутаор 3 по сигналу с блока 2 управления устанавливает длину регистра 4 сдвига и кольцевого регистра 6 равную й. Б дополнительный регистр 4 и кольцсвой регистр 6 занссятся коэффициенты исследуемого многочлена, степень которого не превышает 2 й. При этом в регистр 4 сдвига заносятся коэффициенты при степенях х от 1 до 1, а в кольцевой регистр б - от 1+1 до 2 й,Устройство начинает действовать при подаче тактовых импульсов с генератора 1 импульсов, Содержимое ячеек в едином регистре 4-6 может либо сдвигаться лево, либо с помощью группы 7 элементов И переноситься из ячейки с номеромв ячейку с номером 2, 1(4(й. Как только содержимое кольцевого регистра б становится ненулевым, блок 2 управления чере- коммутатор 3 разъединяет регистр 4 и кольцевой регистр б и включает обратную связь кольцевого регистра соответственно много- члену ) х). Содержимое кольцевого регистра 6 сдвигается циклически в теченис Й тактов, а содержимое регистра 4 остается неизменным. Через Й тактов блок 2 правления отключает обратную связь и включает сумматор 5. Содержимое регистра 4 сдвига и кольцевого регистра 6 суммируется и записывается в дополнительный регистр 4, а кольцевой регистр 6 очищается,В дополнительном регистре 4 сдвига теперь находится вычет исследуемого много- члена по модулю многочлена хх). Устройство возвращается В первоначальное состояние и процесс, если это необходи;ао, повторяется. Количество таких повторений циклов) устанавливается заранее и фиксируется блоком 2 управления. 11 р и в е р. 111 сть 1 х) =х+х-+1, то есть 1=5. Требуется найти вьчег одночлсна х" по модулю хх) и х), Поскольку х 1=хх) х, процесс вычисления начинается с вычисления вычета одночлена х 7, Длина регистра 4 и регистра 6 устанавливается равной 5-ти ячейкам с номерами 10, 9, 8, 7, 6 в регистре 6 и 5, 4, 3, 2, 1 в регистре 4, С ячейки 10 имеется обратная сВязь на 5 чейки 8 и 6.Коэффициенты исследуемого многочлена х 7 заносятся в регистры, Заполнение регистра б имеет вид: 00010, регистра 4 0 О О 0 О, Поскольку содержимое регистра б отлично от нуля, регистры 4 и б разъединяются и Включается обратная связь регистра 6, соответствующая многочлену хо+х+1. Производим пять сдвигов. Содержимое регистра 6 соответственно прини 660054 мает значения: 00100, 01000, 10000, 01010,Затем содержимое регистра б складывается с содержимым регистра 4 (нулевым) и записывается в регисгр 4, а регистр 6 очи 1 цается. Содержимое регистра 4: 01010 - вычет х (по 11 х х+х+1).В едином регистре содержимос из ячейки с номером 2 переносится в ячейку с номером 4, а из ячейки 4 -- в ячейку 8. Прп этом содержимое регистра б: 00100, а регистра 4; 01000.Содержимое регистра 6 ненулевое, Единичньй регистр распадается и включается обратная связь.ПроизВодится П 5 т сдВиГОВ.0100010000,00 101,01010,10100. 1 О 15 20 25 Зо 35 40 45 01111,11110,110 01,1 0111,01011.Складываем содержимое регистров 6 и4. Результат записываем в регистр 4;0 1 0 0 1 - вычет сзоСодержимое регистра 6 обнуляем,Сдвигаем влево па один разряд содержимое регистра 4:Содержимое регистра 4; 10010 - вых 31Б регистре 4 записан вычет одночлепах" по модулю хх) =хо+х+х, равныйх+ х,50 55 60 65 Содержимое регпсгра б складывается с содержимым в регистре 4 и записывается в регистр 4, регистр б очищается.Содержимое регистра 4: 11100 - вы.ет х 14Б регистре 4 находится вычст функции х 7) Умножение на х равносильно сдвигу содержимого едином рсгпстрс иа один разряд влево, что соотвстс; уст содержимому в регистре б: 0 0 0 0 ., регистре 4: 11000,Снова сдвигаем а 5 татосодержимое регистра б;00010,00100,01000,10000,00101.Складыасм содсрк 1 лос рег стров б и 4. Результат з аписыа ем В регистр 4:101 -- ычст х 1-, Содержимое регистра 6 обнуляем. В регистре 4 переносим из первой ячейки во вторую, пз 3 - в б, из 4 -- в 8, из 5 -- в 10-ю. При этом содержимое регистра б: 10101, регистра 4: 00010.Сдвигаем пять раз содержимое регистра 6:660054 Формула изобретения Г 1 1 Составитель Р, Варгиат;овТехред Н. Строганова Корректор Е, Угроватова Редактор Б. Герцен Заказ 568/10 Изд. М 265 Тирани 779 Подписное НПО Государственного ко:.:итета СССР по де,:,:д изооретенин и открытий 113035, Лосв, )К. Раун.окая иа:5., д. 4 5Типография, пр. Сапунова, 2 5Действительно хз= (хв+хз+х) (хв 5+ + х" + хдо+х" +хгв+хв+хгя+хц+х 1 в +хв+х 7+х 5+х 4+хз+х) +хз+х 2Для определения вычета по модул 1 о 1(х) переносим содержимое регистра 4 в регистр 6, что осуществляется сдвигом влево на пять тактов.Тогда содержимое регистров примег вид: регистра 6: 10010, регистра 4: 0000 0.Сдвигаем влево один раз при вкл 1 очен ной обратной связи содержимое регистра 6: 00001.Складываем содержимое регистров 6 и 4. Результат записываем в регистр 4. Содержимое регистра 6: 0 0 0 0 О, регистра 4: 15 00001 - вычет х" (пчос 1 х+х+1).Таким образом, вычет х" по модулю х+х+1 равен единице. Поскольку 31 число простое, делаем вывод, что многочлен 1(х) неприводим и, более того, приметивен. 20Из представления х" =х(х) 1 видно, что в процессе вычисления находятся вычеты одночленов т х 4 х 15 хзо Таким образом, общее количество циклов (сдвигов на пять тактов в регистре 6 с обратной связью) для 25 определения вычета х" (пчодх(х не превышает 1 од,31= 5.Таким образом, предлагаемое устройство обеспечивает увеличение скорости при нахождении показателя исследуемого много члена и предоставляет дополнительную возможность быстрого нахождения вычета произвольного многочлена по заданному. Устройство для определения вычетов, содержащсе генератор импул сов, выход которого соединен со входом блока управления, первь 1 й и второй выходы которого соединены с управляющими входами кольцевого регистра и сумматора, о т л и ч а ющееся тем, что, с целью повышения быстродействия устройства, оно содержит дополнительный регистр, коммутатор и группу элементов И, первые входы которых подключены к третьему выходу блока управления, вторые - к разрядным выходам дополнительного регистра, выходы - к первым входам кольцевого регистра и дополнительного регистра, выход которого через коммутатор подключен ко второму Входу кольцевого регистра, разрядные выходы кольцевого регистра и дополнительного регистра подключены ко входам сумматора, выход которого подключен к разрядным входам дополнительного регистра, управляющий вход которого подключен и четвертому выходу блока управления. Источники информации,принятые во внимание при экспертизе