Устройство для умножения полиномов над конечными полями gf (2 ) по модулю неприводимого многочлена

1661759 тора 6 и 7 нуля, дешифратор 8, группу 9 элементов И, коммутатор 10,элементы И 11, 12 и 13, элементы5ИЛИ 14, 15, элемент НЕ 16 и элемент17 памяти, 5 ил,Изобретение относится к специаЛизированным цифровым вычислительнымустройствам и может использоваться вкодирующих и декодирующих устройстВах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей СР(2"), образованныхнеприводимыми многочленами- видай(х) = х +, х Р,х+1, где х - 20фиктивная переменная, используемая;,ля записи полиномов конечных полей,коэффициенты при степенях фиктивной переменной, причем 3; ЕСГ,2),1 2 , . ша примитивный эле-имент поля СР(2 ) 06= х,Целью изобретения является расширение функциональных возможностей засчет реализации операции деленияполиномов, ЗОНа фиг.1 изображена функциональная схема устройства на фиг,2 - схема ш-разрядного регистра; на фиг,3 -,схема блока деления; на фиг,4 - схема блока умножения, на фиг.5 - схема 35дешифратора,1Устройство для умножения полиномов над конечными полями СР(2 ). 21 начала вычисления устройства,тактовый вход 22 устройства,ш-разрядные регистры 1 и 2 параллельные (фиг. 2) содержат щ элементов 23 памяти.аБлок деления 3 (фиг, 3) содержит55К двухвходовых сумматоров 24 по модулю два, где 1 - число ненулевых коэффициентов при степенях фиктивнойпеременной не равных ни нулю, ни а Цель изобретения - расширение функциональных возможностей за счет реализации операции деления полиномов.Устройство содержит два ш-разрядныхрегистра 1 и 2, блок 3 деления, дваблока 4 и 5 умножения, два дешифранеприводимом многочлене, образующем поле поминомов СР(2 ),Блоки умножения 4 и 5 (фиг4) содержат Е двухвходовых сумматоров 25по модулю два. Блоки умножения и деления предназначены соответственнодля умножения и деления полиномов напримитивный элемент поляДешифратор 8 (фиг.5) содержит элемент НЕ 26 и дешифратор 27 нуля,Индексы при номерах элементов,порядковые номера входов и выходовблоков и устройства, изменяющихся от1 до т, определяют соответствие этихэлементов, входов и выходов коэффициентам при степенях фиктивной переменной в полиномах поля СР(2 ф), значения которых на единицу меньше значений индексов и порядковых номеровсоответственно,Устройство для умножения и деления полиномов над конечными полямиСР(2) работает следующим образом.В исходном состоянии (фиг,1 и 2)элемент 17 памяти устройства и всеэлементы 23 памяти ш-разрядных регистров 1 и 2 обнулены. На тактовыйвход 22 устройства поступает непрерывная серия тактовых импульсов, ана остальные входы устройства поступают сигналы логического нуля. Логический нуль на входе 18 кода операции устройства соответствует операции умножения полиномов. Логическая единица на входе 18 кода операции устройства соответствует операции деления полиномов. При этом навыходе элемента 17 памяти, а значитна выходах элементов И 13 и ИЛИ 15,на всех выходах ш-разрядных регистров 1 и 2, а значит и на выходахэлементов И 9 группы, являющихся выходами результата операции устройства, сформированы сигналы логического нуля,Так как на выходах ш-разрядныхрегистров 1 и 2 сформированы сигналылогического нуля, то на выходах де61759 6 40 45 50 55 5 ,16шифраторов 6 и 7 нуля формируютсясигналы логической единицы. Следовательно, на выходе элемента ИЛИ ф 14,.а значит на одном из входов элемента И 12 сформирован сигнал логической единицы. На другом входе элемента И 12 тоже сформирован сигналлогической единицы, поскольку навыходе элемента И 11 сформировансигнал логического нуля Следовательно, на выходе элемента И 12,являющимся выходом 20 готовностирезультата устройства, сформировансигнал логической единицы, которыйуказывает на то, что на выходах результата операции устройства сформирован полином-произведение, В исходном состоянии результат операцииравен нулю и соответствует результату умножения двух полиномов, равныхнулю,Если же при исходном состоянииустройства на вход 18 кода операцииустройства подан сигнал логическойединицы, то на выходе элемента И 11,являющимся выходом 19 неопределенности результата устройства, формируется сигнал логической единицы, который указывает на то, что результатделения неопределен, При этом навыходе элемента И 12 формируетсясигнал логического нуля, указываяна то, что на выходах элементов И 9группы результат операции деления несформирован,На первом шаге работы, устройствана установочные входы элементов 23памяти щ-разрядных регистров 1 и 2подаются сигналы, равные либо коэффициентам полиномов-сомножителей приоперации умножения, либо полиномаделителя и полинома-делимого приоперации деления соответственно. Если оба полинома-операнда равны нулю,то имеем исходное состояние устройства с готовым результатом операции,зависящим от сигнала на входе 18 кода операции устройства.Если в щ-разрядный регистр 1 зане-.сен полином, равный единице поляСР(2 ), то на его первом выходе, азначит и на выходе дешифратора 8 формируется сигнал логической единицы.На выходе первого дешифратора 6 нуля(фиГ. 1), а значит и на выходе элемента И 11 формируется сигнал логического нуля, независимо от сигнала,подаваемого на вход 18 кода операции устройства, Это соответствует тому, что результат операции определен.При этом, поскольку на выходе элемента ИЛИ 14 сформирован сигнал логической единицы, поступающий на входустановки в нуль элемента 17 памяти,последний не установится в единицупо сигналу, подаваемому на его информационный вход, а на выходе 20устройства формируется сигнал логической единицы, который соответствует тому, что сформирован результатна выходах результата операции устройства, Этот результат операции соответствует сигналам, сформированнымна выходах щ-разрядного регистра 2и переданным через элементы И 9 группы на их выходы по сигналу логичес кой единицы, подаваемой с выхода дешифратора 8 на входы элементов И 9группы, В данном случае результатоперации равен полиному-операнду,заносимому в щ-разрядный регистр 2, 25 что соответствует равенству полинома-результата операции полиному-операнду, умножающемуся или делящемусяна единицу поля полинамов.Если в щ-разрядные регистры 1 и 2 З 0 занесены коэффициенты полиномов-операндов первого в ,не равного нулю и , второго - равного нулю соответственно, то на выходах дешифраторов 6 и 7нуля формируются сигналы логического нуля и логической единицы соответственно.Сигнал логического нуля на выходедешифратора 6 нуля формирует на .выходе элемента И 11 и на входе элемента НЕ 16 сигнал логического нуля,Сигнал логической единицы на выходе дешифратора 7 нуля формирует на выходе элемента ИЛИ 14, а значит навходе установки в нуль элемента 17памяти и на одном из входов элемента И 12, на другом входе которого с выхода элемента НЕ 16 сформирован сигнал логической единицы, Следовательно, на выходе 20 устройства формируется сигнал логической единицы, что соответствует наличию сформированного результата операции на выхо". дах результата операции устройства. Этот результат равен нулю, так как на входы элементов И 9 группы подаются с выходов щ-разрядного регистра 2сигналы логического нуля, В данном случае результат операции равен нулю, что соответствует равенству нулю ре 166175935 зультата умножения на нуль, либо результату деления нуля на ненулевойэлемент поля СР (2 ) соответственно,йЕсли в щ-разрядный регистр 1 за 5несены коэффициенты полинома не равного ни нулю, ни единице поля СР(2 )а в щ-разрядный регистр 2 - коэффициенты полинома не равного нулю,то устройство умножения и деленияПолиномов над конечными полямиСР(2 ) перходит на второй шаг своей работы.При этом на выходах дешифрато"ров б и 7 нуля и дешифратора 8сформированы сигналы логического нуля, Значит, на выходе элемента И.11,являющимся выходом 19 неопределенности результата устройства, и выхо 1де элемента ИЛИ 14 формируются сиг"налы логического нуля, по которомузакрывается элемент И 12, а такжеобеспечивается возможность установки в единицу элемента 1 памяти поего информационному входу, На выходах блока 3 деления (фиг.1, 3) сформированы сигналы, соответствующиерезультату от деления полинома, записанного в щ-разрядный регистр 1,на примитивный элемент поля, На выходах блоков 4 и 5 умножения (фиг,1,4) сформированы сигналы, соответствующие результату от умножения поли.номов, записанных в щ-разрядные регистры 1 и 2, на примитивный элементполя соответственно,Если на вход 18 кода операции устройства (фиг, 1) подан сигнал логического нуля, то сигналы на выходахкоммутатора 10, а значит и на информационных входах щ-разрядного регистра 1 будут равны сигналам на одноименных выходах блока 3 деления.на примитивный элемент поля. Следовательно, при поступлении тактовыхимпульсов на тактовый вход щ-разрядного регистра 1 на выходах регистра (фиг, 2) будут формироваться сигналы, соответствующие результатам отделения полиномов, записанных в ре"гистр 1 до поступления тактовых импульсов, на примитивный элемент поля.Этим обеспечивается выполнение устройством операции умножения полино 111 ъмов над конечным полем СР(2 ),Если на вход 18 кода операции устройства (фиг.1) подан сигнал логической единицы, то сигналы на выходах коммутатора 10, а значит и на информационных входах щ-разрядногорегистра 1 будут соответствоватьсигналам на одноименных выходах блока 4 умножения. Следовательно, припоступлении тактовых импульсов натактовый вход щ-разрядного регистра 1 на выходах регистра (фиг, 2)будут формироваться сигналы, соответствующие результатам от деленияполиномов, записанных в регистр 1до поступления тактовых импульсов,на примитивный элемент поля, Этимобеспечивается возможность выполненияустройством операции деления полиномов над конечными полями СР(2). Длязапуска устройства на выполнение операции, заданной сигналом на вход 18кода операции устройства, необходимона вход 21 начала вычисления устройства подать импульс, обеспечивающийего совпадение с началом поступленияодного из тактовых импульсов, например, либо длительностью импульса,равной периоду поступления тактовых им"пульсов, или импульс, синхронизированный по началу поступления с тактовым импульсом,Этим обеспечивается возможностьнеодновременной записи коэффициентовполиномов в щ-разрядные регистры 1и 2 соответственно, например, по одной щ-разрядной шине данных, а такжеобеспечивается воэможность синхронизации работы устройства с работойвнешнего генератора тактовых импульсов.При подаче импульса на вход 21 начала вычисления устройства на выходеэлемента 15, а значит и на информационном входе элемента 17 памяти сформируется импульс, совпадающий с началом одного из тактовых импульсов, подаваемых .на его тактовый вход. Приэтом элемент 17 памяти устанавливается в единицу и на его выходе, а значит и на одном из входов элементов И13 и ИЛИ 15 формируется сигнал логической единицы, который поддерживаетэтот сигнал на информационном входе,элемента 17 памяти. Следовательно,элемент памяти 17 переведется в нулевое состояние только по сигналу логической единицы на входе. установки в"0", Это произойдет только тогда,когда на выходе дешифратора 8 сформируется сигнал логической единицы,т.е. когда на выходах ш-разрядногорегистра 1 появится комбинация сигна 1 Ь 61 5 9 10лов, соответствующая единице поля.Сигнал логической единицы на одномиэ входов элемента И 13 разрешит прохождение тактовых импульсов с егодругого входа на его выход, а зна 5чит и на тактовые входы ш-разрядныхрегистров 1 и 2, В дальнейшем до формирования сигнала логической единицына выходе дешифратора 8 устройствоработает как устройство для умножения полиномов над конечными полямиСР(2 Ш) по модулю неприводимого многочлена, если сигнал на входе 18 кодаоперации устройства равен логическому нулю, или как устройство для деления полиномов над конечными полямиСГ(2 Ш) по модулю неприводимого многочлена, если потенциал на входе 18кода операции устройства равен логической единице,При формировании сигнала логической единицы на выходе дешифратора 8устройство переходит в состояние,соответствующее занесению единицы 25поля в ш-разрядный регистр 1 на первом шаге работы устройства. При этомэлемент 17 памяти по сигналу на егоуправляющем входе переводится в нулевое состояние, на выходах элементов И 11 и 12 формируются сигналы логического нуля и логической единицысоответственно, а на выходах результата операции устройства - сигналы,соответствующие результату выбранной35операции над двумя полиномами поля.Формула изобретенияУстройство для умножения полиномовнад конечными полями СР(2 ) по модулюпнеприводимого многочлена, содержащее40два ш-разрядных регистра, блок деления, первый блок умножения, дешифратор и группу из ш элементов И, первыевходы которых объединены и соединеныс выходом дешифратора, а выходы - свыходами ш коэффициентов результирующего полинома устройства, выходы первого и второго ш-разрядного регистра соединены соответственно с одноименными, входами блока деления ипервого блока умножения, тактовыевходы первого и второго ш-разрядныхрегистров объединены между собой,о т л и ч а ю щ е е с я тем, что,с целью расширения функциональныхвоэможностей за счет реализации операции деления полиномов, в него вве 1 дены второй блок умножения, элемент памяти, два дешифратора нуля, коммутатор, два элемента ИЛИ, элемент НЕ и три элемента И, причем установочные входы первого и второго щ-разрядных регистров соединены с входами щ коэффициентов первого и второго полиномов-операндов устройства соответственно, выходы первого щ-раэрядного регистра соединены соответственно с одноименными входами второ"го.блока умножения, первого дешифратора нуля и дешифратора, выход которого соединен с первым входом первого элемента ИЛИ, второй вход которого соединен с выходом первогодешифратора нуля и первым входом первого элемента И, второй вход которого соединен с входом кода операцииустройства и управляющим входом коммутатора, информационные входы первой и второй группы которого соединены соответственно с выходами второго блока умножения и блока деления,а выходы - с информационными входамипервого щ-разрядного первого регистра, тактовый вход которого соединенс выходом второго элемента И, первыйвход которого соединен с тактовымивходами устройства и элемента памяти,выход которого соединен с вторым входом второго элемента И и первым входом второго элемента ИЛИ, выход которого соединен с информационным входом элемента памяти, вход установкив "О" которого соединен с первым входом третьего элемента И и выходомпервого элемента ИЛИ, третий вход которого соединен с выходом второгодешифратора нуля, входы которого соединены с вторыми входами соответствующих элементов И группы и выходами второго ш-разрядного регистра, информационные входы которого соединены соответственно с выходами первого блока умножения, выход первогоэлемента И соединен с выходом неопределенности результата устройства ивходом элемента НЕ, выход которогосоединен с вторым входом третьегоэлемента И, выход которого соединенс выходом готовности результата устройства, вход начала вычисления которого соединен с вторым входом второго Элемента ИЛИ, 1661759