Устройство для умножения элементов конечных полей

(51) 4 С 06 Р 7/52 ОПИСАН БРЕТ 4 НОЖЕНИЯ ЭЛЕ области изобре- ьных ится Цел кционеали ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ К АВТОРСКОМУ СВИДЕТЕЛЬСТ(56) ВагСее Т.С., ЯсЬпеЫег 0.1.Сошри 1 аггоп м 1 гЬ Р 1 пгге Рге 1 оз.1 пГогша.оп апй Сопгго 1, ч. 6,У 2, Типе 1962.Авторское свидетельство СССРУ 1013950, кл. С 06 Р 7/52, 1982. 54) УСТРОЙСТВО ДЛЯ У 1 МЕНТОВ КОНЕЧНЫХ ПОЛЕЙ 57) Изобретение отно ычислительной техник ения - расширение фу озможностей за счет вычислительной операции обращенияэлементов конечных полей. Для этогоустройство содержит дополнительноблок синхронизации, блок ш сумматоров, группу ш элементов И, ш-разрядные мультиплексоры, блоки трактируемых элементов задержки и матричногопреобразования, Все блоки иэлементысоединены в соответствии с решаемойзадачей, при этом блок синхронизации,блок трактуемых элементов задержки иблок матричного преобразования имеютсвою схемную реализацию. Изобретениеможет быть применено при построенииспециализированных вычислителей длякодирования и декодирования кодов,корректирующих ошибки. 3 з.п. ф-лы,6 ил.1226445 Вх. 23 Вх. Я 1 Вых,22 дх. 19 Вых, Tга Вых. Tрр Вых. 71 Вык Ъ Рьц.1 Вых. Тдз бьц, Ту Вых Ту Мулыпи - плексор 5 Мультик ющ 6Мультиплексор 17г бык. рег. 1 Вых. рег,2 Вык. рег. 12Рык, групЗ Вык. дл. 9алых дл. г,б тавитель В. Смирред В.Кадар ".Шекмар дактор Т, Кугрьппев орре аказ 2134/48 вниипи и 113035, Подпис ж 6 ств зоб жмитета СС открытий Госуд делам нно тек Ра.1 12Изобретение относится к вычислительной технике и может быть примене.но при построении специализированныхвычислителей для кодирования и деко,Дирования кодов, корректирующихошибки,Целью изобретения является расширение функциональных возможностейустройства за счет реализации вычислительной операции обращения элементов конечных полей.На фиг. 1 приведена блок-схемаустройства для умножения элементовконечных полей; на фиг. 2 - функциональная схема блока синхронизациипри тп=6; на фиг. 3 - функциональнаясхема регистра одного из сомножителей и мультиплексора с тремя коммутируемыми тп-разрядными входами; нафиг, 4 - схема соединений групп блоков матричного преобразования, блоков элементов И и блоков сумматоров;на фиг, 5 - схема блоков матричногопреобразования; на фиг, 6, - временная диаграмма работы устройстваУстройство содержит регистры 1 и2 первого и второго сомножителейгруппу 3 блоков 4 матричного преобразования, первую и вторую группы 5 и6 соответственно блоков 7 элементовИ 8, первый и второй блоки 9 и 10сумматоров 11 по модулю дна, выходной регистр 12, шину 13 единичногопотенциала устройства, блок синхронизации 14, первый, второй и третиймультиплексоры 15-17, выход 18 первого сомножителя и обращаемого элемента, вход 19 второго сомножителя,выход 20 результата устройства, вход21 признака режима работы устройства, выход 22 готовности устройствак выполнению вычислений, тактовыйвход 23, тактовый выход 24 блокасинхронизации, первую, вторую итретью группы управляющих выходов25-27 соответственно блока синхронизации.Блок синхронизации содержиттриггер 28, регистр 29 сдвига, состоящий из двух ступенчатых тактируемых 0-триггеров 30-34, элемент НЕ 35,блок 36 тактуемых элементов задержки, состоящий из элемента И 37 и.двух двухступенчатых тактируемых0-триггеров 38 и 39. Блок 14 синхронизации содержит также первый, нторой, третий, четвертый элементыИ 40-43, первый и второй элементыИЛИ-НЕ 44 и 45.6445 2 2=(2, ) =ЧЧ. 10 15 20 25 30 35 40 45 50 Каждый из мультиплексоров 15 и16 содержит блоки 46-48 из ш.элементов И 49 и блок 50 из тп элементовИЛИ 51. Первые входы элементов И 49блоков 46-48 являются группами первых, вторых и третьих коммутируемыхш-разрядных входов мультиплексоров15 и 16, объединенные вторые входыэлементов И 49 н каждом из блоков46-48 являются группой 25 (26) управляющих входов мультиплексора 15(16) Выходы элементов ИЛИ 51 являются выходами мультиплексоров 15и 16, В качестве мультиплексора 17с двумя коммутируемыми ш-разряднымивходами можно применить мультиплексор 5 или 16. В этом случае один,из блоков 46-48 можно исключить сзаменой элементов ИЛИ 51 на двухнходоные элементы ИЛИ. Регистр сомножителей 1 (2) содержит тп элементовНЕ 52 и тп 1 К-триггеров 53, выходыкоторых объединены и подключены ктактовому входу регистра 1(2) и квходу 23 устройства, прямые выходытригерон 53 являются выходами регистра 1(2), входы 1 и К триггеровподключены к входам регистра непосредственно и через элементы НЕ 52,а входы подключены к шине нулевогопотенциала устройства. Выходной регистр 1 имеет такие же состав исхему, что и регистры 1 и 2.Группа блоков матричного преобразования включает н себя (ш) перестраиваемых блоков 4 матричного преобразования и коммутатор 54, коммутирующий в зависимости от значенийкоэффициентов Г, =0,1, т=1 ш,порождающего многочлена Р(х)=1+1 х+1+Г х 2+ +т .,х +х сигналы 0или "1" на выходы коммутатора 54,Блок 4матричного преобразования содержитшдвухвходоных элементов И 55 ишдвухвходовых сумматоров 56 помодулю два,Устройство может работать н двухрежимах.В первом режиме производится умножение элементов конечного поля, вводимых н устройство по входу первогосомножителя Ч=(Ч Ч,) и входуФ1второго сомножителя Ч=.(Ч.Ч,) Во втором режиме производитсяобращение (по умножению) элементаконечного поля, вводимого н устройство по входу первого сомножителя,при,наличии сигнала "Обращение" навходе 21, т.е. нахождение элементаВ , обратного заданному элементу Впо умножению ВВ =В В=1 122 б 445ка 2 .Вычисленияпроизводятся в соответствии с соотношением(В)В В ВВ =В =ВРеализация этих вычислений в устройстве осуществляется (т)-кратным выполнением операции видаПри выполнении операции умножения Ч Ч на выходах группы блоков матричного преобразования формируются сигналы, соответствующие элемен. там конечного поля випагде о - примитивный элемент поля СГ(2 ). Те из элементов сБ,д=1,т, которым соответствуют единичные компоненты сомножителя Ч, проходят на входы первого блока сумматоров, на выходах которого формируются сигналы 2=(22 , соответствующие сумме2=БИЧ(ЫЦ,равной произведению Е=Ч Б, Сигналы с выходов первого блока сумматоров поступают через третий мультиплексор и выходной регистр на выход результата устройства. Одновременно с этим сигналы, соответствующие Е=Ч Б, поступают также на объединенные первые входы второй группы блоков элемента И, на вторые входы которых с выходов блоков матричного преобразования поступают сигналы, соответствующиет.П, оБ,о).Б, , ;А Б, ,с И В результате этого на выходе второго блока сумматоров получается сумма элементов2, (с. 3),-Нахождение значения В осуществляется в устройстве путем вычислетния (2 -2)-ой степени элемента В, которая равна В , так как В =1 для всех ненулевых элементов конечных полей характеристики два и поряд) г Й).10состоящей в возведении в квадрат величины Еи умножения ) Е "на) . гВ при начальных условиях (1=1) 152 =В, В =В(,)При этом операнд В вводитсяв регистр первого сомножителя, а11операнд Е- в регистр второго сомножителя при каждом новом значении )=1,2т. Это обеспечиваетполучение на выходах первого блока 30сумматоров произведения( ) (.)Е =Е Ва на выходах второго блока сумматоров - величиныВыполнение (н) раз вычислений(+) г ( г (.)Е =(2В с учетом начальныхи текущих условий, обеспечиваемыхсоответствующим числом переключенийцепей прохождения сигналов с помощьюпервого второго мультиплексоров и 45 блока синхронизации, приводит к получению на выходах второго блока сумматоров величины В , равной зна чению элемента конечного поля Вобратного заданному.50 Устройство работает следующимобразом.Сигналы тактовой частоты подаютсяпостоянно через вход 23 устройствана регистры 1 и 9 и блок 14 синхро низации. С выхода блока 14 синхронизации инвертированные сигналы тактовой частоты поступают на тактовыйвход регистра 12.3 1В исходном положении и после окончания вычислений по обращению элементов конечного поля триггер 28блока 14 находится в "нулевом" состоянии и с его инверсного выхода выдается сигнал "Единица", соответствующий "Готовности устройства кработе". Сигнал "Готовность" снимается на ш тактов лишь при переводеустройства в режим работы "Обращение" при поступлении на вход 21 сигнала признака режима работы "Обращение". При отсутствии на входе 21устройства сигнала "Обращение" и приналичии на выходе 22 устройства сигналаГотовность" устройство переводится в режим 1 Умножение".В режиме "Умножение" триггер 28,триггеры 30-34 и 38 и 39 находятсяв "нулевом" состоянии. Это определяет появление по одному "единичному" сигналу в каждой из групп выходов 25-27 блока 14 управления.Такая комбинация сигналов в группах выходов 26-27 блока 14 синхронизации обеспечивает прохождение навыход каждого из мультиплексоров16-17 сигналов по следующим коммутируемым входам:для мультиплексора 15 - сигналыпервого сомножителя по первым коммутируемым входам;для мультиплексора 16 - сигналывторого сомножителя по вторым коммутируемым входам;для мультиплексора 17 - сигналыс выходов первого блока 9 многовходовых сумматоров по первым, коммутируемым входам,Сигналы с выходов мультиплексоров15-17 записываются по заднему фронтусигналов тактовой частоты соответственно в регистры 1, 2 и 12. При этомв регистр 1 вводится первый сомножитель Ч, в регистр 2 - второй сомножитель П в регистр 12 - результатвычислений в предыдущем такте работы. 226445 Ь ветствующие следующим значениям элементов поля: П,Ы П,Ы 2 Б, , с й 0 5 30 40 50 55 Сигналы с выходов регистра 2 второго сомножителя поступают на входы группы 3 блоков 4 матричного преобразования, включенных последовательно друг за другом, В блоке 4 матричного преобразования производится умножение поступившего на его вход операнда на примитивный элемент И конечного поля, На в выходах группы 3 блоков 4 образуются сигналы, соот. Схема блока 4 матричного преобразования является перестраиваемой в зависимости от вида порождающего многочлена У(х), Перестройка блока 4 обеспечивается с коммутатором 54, С 3-го выхода коммутатора 54 выдается " 1", если соответствующий ему по порядку коэффициент Г заданного1 многочлена Р(х) равен единице, и выдается "О", если Г, =О, Вследствие этого сигналы с тех 1-х входов блока 4, х=1 . ш, для которых й =О, проходят через вход и выход сумматора 56 на (+ 1)-й выход блока 4 без изменений, а сигналы с входов, для которых Г, =1, проходят на (1+1)-й выход блока 4 в виде суммы их с сигналом на ш-м входе блока 4, Сигнал с тп-го входа поступает на вторые входы сумматоров 56 через первые входы и выходы тех элементов И 55, на вторые входы которых поступает единица из коммутатора 54. Сигнал с ш-го входа блока 4 всегда подается также на выход первого разряда этого блока, Такая схема блока 4 матричного преобразования обеспечивает умножения входного операнда на примитивный элемент о конечного поля, задаваемого многочленом Р(х).Сигналы с выходов группы 3 блоков 4 матричного преобразования поступают на входы сумматоров 11 блока 9 через те блоки 7 элементов И 8 группы 5, в которых на первые входы элементов И 8 подается единичный сигнал с выхода соответствующего разряда регистра 1. Если же на первые входы элементов И 8 какого- либо блока 7 подается нулевой сигнал с выхода регистра 1, то нули с выхоца элементов И 8 данного блока 7 не изменяют результата суммирования на выходе блока 9 сумматоров, который равняется произведению первого Ч и второго Б сомножителей т 2=(2 )=., (о( и) = ОСигналы с выхода сумматоров 11 поступают через открытые первые ком.10 мутируемые входы и выходы мультиплексора 17 на входы вьгходного регистра, в который они записываютсяпо заднему фронту сигнала тактовойчастоты следующего такта и далееподаются на выход 20 результатаустройства, Кроме того, сигналы свыхода сумматоров 11 поступают такжена первые входы элементов И 8 блоков 7,Сигналы с выходов группы 3 блоков 4 матричного преобразования поступают также на входы. блока 10 сумматоров через те блоки 7 элементов,которым соответствует, единичныйсигнал на первых входах элементов И.В результате на выходах блока 10 сумматоров образуется произведение,равное о1-12 Б=Е (Ы У) =(Ч Б) Б=Ч П Коммутируемым входом мультиплексоры 16 и 17 соединяются с выходамисвоих мультиплексоров в соответствиис временной диаграммой (фиг, 6)только в режиме "Обращение" и остаются всегда отключенными от выходовмультиплексоров при выполнении уст-,ройством операции умножения,Перевод устройства в режим работы "Обращение" задается подачей единичного сигнала на вход 21 устройства. Этот сигнал поступает на установочный вход Я триггера 28 .блока14 управления и переводит триггер вединичное состояние, снимая темсамым сигнал "Готовность устройствак работе" на выходе 22, Единичныйсигнал с триггера 28 поступает навход регистра 29. В результате этого и под воздействием сигналов тактовой частоты триггеры 30, 31-34,38, 39 регистра 29 и блока 36 тактируемых элементов задержки начинаютпоследовательно переключаться в единичное состояние, Совпадение единичных сигналов на входах элементовИ 42 и 43 в группах выходов 25 и 26,а также 27 происходит изменениесостояний отдельных выходов с нулевого на единичный и обратно, Приэтом в единичном состоянии всегдабудет не более одного выхода изгруппы.Сигналы в группах выходов 25-27,поступающие на управляющие входымультиплексоров 15-1.7, обеспечиваютпрохождение сигналов с одного из 15 20 25 30 35 40 45 50 55 трех (для мультиплексоров 15 и 16) или двух (для мультиплексора 17) коммутируемых ш-разрядных входов на выход мультиплексоров в соответствии с временной диаграммой (фиг. 6). При этом в мультиплексоре 15 в течение первого такта цикла обращения производится подключение на выходы первых входов, по которым с выхода 18 устройства поступает обращаемый элемент В. В течение последующих штактов на выход мультиплексора 15 коммутируются его третьи входы, подключенные к выходу регистра 1 первого сомножителя, В результате с выхода регистра 1 в течение первых штактов цикла обращения на входы группы 5 блоков 7 элементов И 8 будет выдаваться элемент В. На время (ш)-го такта через мультиплексор 15 разрешается прохождение в регистр 1 сигналов с датчика 13 единицы, соответствующих элементу конечного поля "единица" (комбинация двоичных сигналов: 1, О, , 0 с одной "1" в младшем разряде и ш"0" в остальных разрядах).В мультиплексоре 16 в первом такте цикла обращения происходит передача на выходы мультиплексора сигналов с первых коммутируемых входов, подключенных к выходу 18 устройства, в результате в регистр 2 вводится обращаемый элемент В. В течение следующих штактов через третьи коммутируемые входы мультиплексора 16 на входы регистра 2 подключаются сигналы с выходов сумматоров 11.Через мультиплексор 17 во время первых (тп) тактов цикла обращения запрещается выдача сигналов с выходов блока 9 и 10, так как ни на одном из выходов 27 в течение всего указанного времени не будет единичного сигнала, а на (т)-м также на мультиплексор 17 подается управляющий сигнал, разрешающий прохождение на выходной регистр 12 сигналов с выхода блока 10 сумматоров, которые будут соответствовать элементу-г -1В =В =ВВ начале ш-го такта цикла обращения единичный сигнал с выхода триггера 39 блока 36 поступает на установочные входы триггера 28 и всех триггеров регистра 29 и переводит их в нулевое состояние. В результате этого на выходе 22 появляется сигнал "Готовность устройства к работе"9 12 и производится переключение мультиплексоров 15-17 в исходное положение соответствующее режиму "Умножение",Введение в состав устройства для умножения элементов конечных полей дополнительных указанных блоков расширяет функциональные возможности устройства умножения путем реализации операции обращения элементов конечных полей. Это дозволяет строить универсальное вычислительное устройство, обеспечивающее выполнение всех возможных вычислительных операций (умножения, обращения и сложения), необходимость в которых возникает, например, при кодировании и декодировании кодов, построенных надконечными полями характеристики два, без применения дополнительного сложного оборудования для обращения элементов конечных полей.26445 1 О 5 10 15 20 щ) элементов И второй группы подключены -му выходу первого блока сумматоров, выход 1-го блока матричного преобразования соединен с вторым входом (1+1)-го блока элементов И второй группы, выходной регистр тактовый вход которого подключен к . второму выходу блока синхронизации, три щ разрядных мультиплексора, 1группы управляющих входов первого, второго третьего мультиплексоров подключены к выходам соответственно первой, второй и третьей групп блока синхронизации, первая группа информационных входов первого мультиплексора соединена с первой группой информационных входов второго мультиплексора и подключена к группе входов первого сомножителя устройства, вторая группа информационных входов первого мультиплексора подключена к выФормула изобретения 1. Устройство для умножения элементов конечных полей, содержащее регистры первого и второго сомножителей, тактовые входы которых подключены к тактовому входу устройства, группу блоков матричного преобразования, первый блок сумматоров, первуо группу 1 щ,блоков элементов И, первые входы щ блоков элементов И первой группы подключены к соответствующим выходам регистра первого сомножителя, выход 1.-го (=1,2 щ) блока элементов И первой группы подключен к -му входу первого блока сумматоров, выход 1-го блока матричного преобразования Ц =1,2, ,щ) соединен с входом (1+ 1)-го блока матричного преобразования и с вторым входом (1+1)-го блока элементов И первой группы, о т л и ч а ю щ е - е с я тем, что, с целью расширения функциональных возможностей устройства за счет реализации операции обращения элементов конечных полей, оно дополнительно содержит блок синхронизации, вход здания режима которого подключен к входу признака режима работы устройства, тактовый вход блока синхронизации соединен с тактовым входом устройства, первый выход блока синхронизации подключен к выходу признака готовности устройства, второй блок из щ сумматоров, вторую группу из щ блоков элементов И, первые входы -го блока (1.=1, 2,30 35 40 4 ь 5 О ходам регистра первого сомножителя,информационные входы которого подключены к выходам первого мультиплексора, третья группа информационныхвходов которого подключена к шинеединкчноге потенциала устройства, информационные входы регистра второгосомножителя подключены к выходамвторого мультинлексора,вторая группаинформационных входов которого подключена к гругпе входов второго сомножителя устройства, третья группаинформационных входов второго мультиплексора подключена к выходам второго блока сумматоров и к первой группеинформационных входов третьего мульти.плекс:ора, выходы которого подключенык информационным входам выходного регистра, выход которого подключен квыходу результата устройства, выходы элементов И 1-го блока второйгруппы подключены к соответствующим-м входам второго блока сумматоров,выходы первого блока сумматоров подключены к второй группе информационных входов третьего мультиплексора,при этом настроечные входы устройства подключены к входам задания порождающего полинома поля блоков матричного преобразования. 2, Устройство по п.1, о т л и ч а ю щ е е с я тем, что блок синхронизации содержит триггер, (щ)- разрядный регистр сдвига, блок так - тирующих элементов задержки, четыре элемента И, два элемента ИЛИ-НЕ, элемент НЕ, вход которого подключенк тактовому входу регистра сдвига и к входу тактовой частоты блока синхронизации, а выход подключен к второму входу блока синхронизации и к тактовому входу блока тактируемых элементов задержки, при этом первый, второй входы первого элемента И, а также первый вход второго элемента И подключены соответственно к прямому выходу триггера (ш)-го разряда, 10 инверсным выходам триггеров (ш)-го и (ш)-го разрядоврегистра сдвига, второй вход второго элемента И подключен к первому входу четвертого элемента И и к прямому выходу триггера первого разряда регистра сдвига, инверсный выход триггера первого разряда регистра сдвига подключен к первому входу третьего элемента И, второй вход которого подключен к ин формационному входу регистра сдвига и к прямому выходу триггера, а второй вход четвертого элемента И подключен к второму входу первого элемента И, вход установки триггера в единичное 25 состояние подключен к входу признака режимы работы блока синхронизации, выходы первого и второго элементов И подключены к входам первого элемента ИЛИ-НЕ, а выходы третьего и четвертого элементов И - к входам второго элемента ИЛИ-НЕ, прямой выход триггера (ш)-го разряда регистра сдвига подключен к первому информационному входу блока тактируемых элементов за 35 держки, первый управляющий выход которого подключен к установочным в состояние "О" входам регистра сдвига и триггера, инверсный выход триггера подключен к выходу признака готовнос ти устройства, выходы первого элемента ИЛИ-НЕ, первого и второго элементов И подключены к первой группе управляющих выходов блока синхронизации, выходы третьего элемента И, второго элемента ИЛИ-НЕ, четвертого элемента И - к второй группе управляющих выходов, а два управляющих выхода третьей группы подключены соответственно к инверсному выходу триггера и к второму выходу блокатактируемых элементов задержки, второй информационный вход которогоподключен к выходу (ш)-го разрядарегистра сдвига,3. Устройство по п.1, о т л и -ч а ю щ е е с я тем, что блок матричного преобразования содержит(ш) элементов И, (ш) сумматоровпо модулю два и коммутатор, первыйинформационный вход которого подключены к шине единичного потенциала,второй информационный вход - к шиненулевого потенциала, а управляющийвход - к входу задания порождающегополинома поля, первые входы 1-хсумматоров по модулю два подключенысоответственно к входам блока, вторые входы 1-х сумматоров по модулюдва подключены к выходам 1-х элементов И, первые входы которых подключены к соответствующему 1-му информационному выходу коммутатора, вторые входы элементов И подключены кш-му входу и к первому выходу блока,остальные (ш) выходы блока образуют соответственно выходы (ш) сумматоров по модулю два.4. Устройство по п,1, о т л и -ч а ю щ е е с я тем, что блок тактируемых элементов задержки содержитэлемент И, первый и второй триггеры,тактовые входы которых подключенык тактовому входу блока тактируемыхэлементов задержки и к первому входуэлемента И, выход которого подключен к тактовому выходу блока тактируемых элементов задержки, и второйвход - к прямому выходу первого триггера, сигнальный вход которого подключен к первому информационномувходу блока тактируемых элементовзадержки, информационный выход которого подключен к прямому выходу второго триггера, а второй информационный вход - к сигнальному входу второго триггера, входы установки в состояние "О" первого .и второго триггеров подключены к шине нулевого сигнала устройства.