Устройство для анализа приводимости полиномов

 

I о и л-нМ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

257I48

Союз Соеетсиих

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

Республии

Зависимое от авт. свидетельства №

Заявлено 04.Ч!.1968 (№ 1246778/18-24) Кл. 42m, 7/38 с присоединением заявки №

Приоритет

МПК G 061

УДК 68!.325.6(088.8) Комитет ло делам изобретеиий и открытий ори Сосете Мииистрое

СССР

Опубликовано 11.XI.1969. Бюллетень № 35

Дата опубликования описания 2.IV.1970

Авторы изобретения

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

Институт автоматики и телемеханики

Заявитель

УСТРОЙСТВО ДЛЯ АНАЛИЗА ПРИВОДИМОСТИ

ПОЛИНОМОВ

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

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

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

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

На чертеже приведена блок-схема описываемого устройства.

Она содержит генератор 1 тактов, блок 2 управления, блок 8 умножения, стробирующ ий ключ 4, регистры 5 и б сдвига с тумблерами, сумматор 7 по модулю два, переключатели

8 — П, устройство 12 печати или внешней памяти и сумматоры 13 по модулю два.

:Выходы регистров 5 и б через переключатель 11 соединены с входом блока 3 умножения и соединены между собой при помощи

10 сумматора 7.

Выход блока 8 умножения через стробирующий ключ 4 и переключатели 8 — 10 соединен со входами регистров 5 и б, причем вход регистра 5, кроме того, через переключатель 8 сое1 динен с.выходом регистра б, а вход регистра б через переключатель 9 — с выходом сумматора 7. Кроме того, выход блока 3 умножения соединен со входом устройства 12 печапи также через ключ 4, а выход устройства 12 — со входом регистра б. Работа всех блоков находится под контролем блока 2 управления, соединенного с генератором 1 тактов.

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

Пусть в начальном состоянии переключатели 8 — 11 находятся в положении, указанном на чертеже. Исследуемый полином f (x) = а„х" +an тх — +,, + а„степени п набирают на тумблерах блока 3 умножения. Если пронуЗ0 меровать тумблеры справа налево от 0 до п, то номера замкнутых контактов должны сов257148 падать со степеняии х, коэффициенты при которых отличны от нуля. Тумблерами регистров 5 и б устанавливают длину этих регистров, равную (п+1), и в регистр 5 вводят подряд коэффициенты полинома f (х), стоящие при четных степенях аргумента (т. е. через один), начиная со старшего. Блок 2 управлен ия, построенный из стандартных элементов, приводится в исходное состояние. При подаче тактовых импульсов с генератора 1 устройство начинает действовать (назовем совокупность (2п+1) импульсов циклом). В первом цикле блок 2 управления подает на блок 8 умножения и регистр 5 тактовую частоту, а на регистр б — и ол ут актовую. Ключ 4 и р и помощи блока 2 управления пропускает в регистр б лишь коэффициенты произведения, стоящие при четных степенях х. В конце цикла блок 8 умножения и регистр 5 оказываются очищенными, а регистр б заполненным. Вслед за этим переключатели 10 i>t 11 меняют положение, т. е. переключатель 10 переходит на регистр 5, переключатель 11 — на регистр б, блок 2 управления переводится в режим второго цикла.

Теперь на регистр 5 подается полутактовая частота, а на регистр б и блок 8 — тактовая.

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

По окончании второго цикла блок 2 управления и переключатели 10 и 11 переходят в первоначальное состояние и процесс продолжается аналогичным образом. После (и — 1) цикла блок 8 и регистры 5 и б очищаются, в регистр 5 вводятся коэффициенты полинома

f(x), стоящие при нечетных степенях х, а блок 2 управления перестраивается таким образом, чтобы, управляя ключом 4, пропускать лишь коэффициенты произведен ия, стоящие при нечетных степенях х. И затем процесс продолжается еще (п — 1) циклов, После (2n — 2)-го цикла меняют положение переключатели 8 — 11. Регистры 5 и б очищаются, и в регистр 5 записывается исследуемый полином f(x), а в репистр б — результаты к и

5 Гп1 (п+к) цикла (к=1, 2, ..., (— ) — 1), сложенные предварительно по модулю д ва. Векторы, записанные в регистрах 5 и 6, складываются по-разрядно по модулю два. После каждого

10 (п+1)-го такта проверяется вектор, записанный в регистре 6. Процесс заканчивается, когда в регистре б оказывается записанным нулевой вектор. При этом содержимым регистра 8 является делитель полинома f(x).

15 Если полином f(x) не имеет делителей, отличных от 1(х) и единицы, то полином неприводим.

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

Предмет изобретения

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

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

257148

Составитель М. И. Аршавский

Редактор E. В. Семанова Текред T. П. Курилко Корректор Л. В. Юшина

Заказ 706/12 Тиран, 480 Под IIICIIO<

ЦНИИПИ Комитета по делам изобретений н открытий прп Совете М|шпстров СССР

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

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