Устройство для умножения элементов конечного поля размерности 2

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскикСоциалистическихРеспублик щ 959077(61) Дополнительное к авт. свид-ву(22) Заявлено 121280 (21) 3229562/18-24 51) М. Кп. з с присоединением заявки Нов 6 06 Р 7/68 Государственный комитет СССР но делам изобретениИ и открытий(54) УСТРОЙСТВОКОНЕЧНОГ УМНОЖЕНИЯ ЭЛЕМЕНТОВЛЯ РАЗМЕРНОСТИ 2 в оженияржащеежитеустройства ява машинного врего п ог аммны 15 20 вестного устлементов ко- . 25 и 2 уипотреъемом, равМ 10 - д- би Изобретение отельной техникезовано в специалтельных устройствах,Известно устройство для уэлементов конечного поля, сорегистр множимого, регистр мля, блок умножения, выходнойгистр 11. тносится к вычисли- и может быть испольизированных вычислиНедостаткбм .такоголяется большая затратмено при реализации е р р ье средствами.Наиболее близким техническим решением к данному является табличное устройство для модульного умножения в системе остаточных классов, содержащее 21 н-разрядные параллельные регистры множимого и множителя, первую и вторую группы элементов И по 2 тн элементов И в каждой и блок памяти 12,При использовании изройства для умножения энечного поля размерностбуется блок памяти с об В случае перемножения чисел большойразрядности, что необходимо, например, при формировании помехозащищенных кодов, объем блока памятивозрастает настолько, что становится практически нереализуемым. Таким образом, недостатком устройстваявляется значительное увеличениеобъема блока памяти при.увеличенииразрядности перемножаемях чисел.Цель изобретения - уменьшениеобъема оборудования,Поставленная цель достигаетсятем, что в устройство дополнительновведены параллельный тн-разрядныйрегистр, первая.и вторая группыэлементов ИЛИ, по ии элементов ИЛИв каждой, третья, четвертая, пятаяи шестая группы элементов И по тиэлементов И в каждой, параллельный2 м-разрядный регистр адреса,.накапливакщий сумматор и блок управления, содержащий распределительтактовых сигналов и шесть элементов ИЛИ, причем выходы регистра множимого соединены соответственно спервыми входами элементов И первойгруппы, выходы регистра множител".соединенысоответственно с первымивходами элементов И второй группы,выходы е-разрядного параллельногорегистра соединены соответственнос первыми входами элементов И третьей.группы, вторые входы Е первых элементов И первой группы объединены и соединены с выходом первого элемента ИЛИ блока управления,вторые входи остальных элементов Ипервой группы объединены и соединены с выходом второго элемента ИЛИблока управления, вторые входы и пер Ц,вых элементов И второй группы объединены и соединены с выходом третьего элемента ИЛИ блока управления,вторые входы остальных элементов Ивторой группы объединены и соединены с выходом четвертого элемента ИЛИблока управления, вторые входы элементов И третьей группы объединеныи соединены с первым выходом распре-делителя тактовых сигналов блока управления и с объединенньпчи вторымн 1 фвходами элементов И четвертой группц, выходы ю первых элементов И первой группы соединены соответственнос первьщи входаьи элементов ИЛИ первой группы, выходы остальных элементов И первой группы соединены соответственно со вторыми входами элементов ИЛИ первой группы, выходы элементов И третьей группы соединысоответственно с третьими входамиэлементов ИЛИ первой групп, выходы в первых элементов И второй группы соединены соответственно с первыми входами элементов ИЛИ второйгрупги, выходы остальных элементов И 35второй группы соединены соответственно со вторыми входами элементовИЛИ второй группы, выходы элементов Ичетвертой -группы соединены соответственно с третьими входами злемен Отов ИЛИ второй группы, выходц элементов ИЛИ первой группы соединенысоответственно си первыми входамирегистра адреса, выходы элементов ИЛИвторой группы соединены соответствен"45но с остальными входами регистраадреса, выходи которого соответственно соединены с адресными входами блока памяти, выходы которого соединены соответственно с первыми входамиэлементов И пятой и шестой групп,вторые входы элементов И пятой группы объединены и соединены с вцходс)м пятого элемента ИЛИ блока управлбйия, вторые входц элементов И шестой группы объединены и соединеныс вцходом шестого элемента ИЛИ блока управления, выходы элементов Ипятой и шестой групп соединены соответственно с информационными входами накапливающего сумматора,. вцходы п первых разрядов которогосоединены соответственно с первыми,входами элементов И четвертой группы и являются щ первыми разрядамивыходной шины устройства, а остальные выходы накапливающего сумматора являются соответствующими разрядами выходной шины устройства, второй выход распределителя тактовыхсигналов блока управления соединенс первыми входами первого, третьегои пятого элементов ИЛИ блока управления, первый выход распределителятактовых сигналов блока управлениясоединен с первым входом шестогоэлемента ИЛИ блока управления, третий выход распределителя тактовыхсигналов блока управления соединенс первым входом четвертого элемента ИЛИ и со вторыми входами первого и пятого элементов ИЛИ блока управления, четвертый выход распределителя тактовых сигналов блока управления соединен с первым входомвторого элемента ИЛИ, вторым входомтретьего элемента ИЛЙ и третьим входом пятого элемента ИЛИ блока управленин, пятый выход распределителятактовых сигналов блока управлениясоединен со вторыми входами второго,четвертого и шестого элементов ИЛИблока управления,На чертеже изображена функциональная схема устройства.Устройство содержит 2 в-разрядные параллельные регистры 1, 2 множимого и множителя, 2 и элементов 3 И первой группы, 2 в элементов 4 И второй группы, блок 5 памяти, параллельный в-разрядный регистр б, и элементов 7 ИЛИ первбй группы, м элементов 8 ИЛИ второй группы, щ элементов 9 И третьей группы гл элементов 1 О И четвертой группы, м элементов 11 И пятой группы, ю элементов 12 И шестой группы, параллельный 2 в-разрядный регистр 13 адреса, накапливающий сумматор 14 и блок 15 управления, содержащий шесть элементов 16 ИЛИ и распределитель 17 тактовых сигналов.Устройство реализует возможность формирования произведения элементов поля размерности 2 фипутем последовательного использования операций над элементами поля размерности и, на которые разлагаются 2 и-разрядные числа множимого и множителя благодаря чему значительно уменьша( ется объем матрицы. Укаэанная возможность основана на том что любойзм фэлемент А поля 6 Г(2 ) можно представить в виде линейного многочлена вида а х + а, коэффициенты которого а и а являются как элементами поля ОГ(2), так и его подполя 6 Г(2), при этом элемент А может быть представлен в виде 2 ит-разрядной двоичной комбинации, а компоненты а и а - в видеи-разрядных двоичных комбинаций. Сложение двух элементов А и В поля СГ(2- )можно производить как сложение двухмногочленов:А + В = (а х + а) +(Ь х + Ь)(а .+ Ь)х + (а + Ь).При этом сложение производится по модулю два. Произведение двух элементов поля ОЕ(2) может быть выполнено как произведение двух соответствующих многочленов по модулю нериводимого квадратного многочлена Е(х) над полем СЕ(2). В . 10 качестве многочлена Е(х) может быть использован многочлен вида Е(х) = х. + х + с, где с - элемент поля СЕ(2"ф). Поэтому имеем:А В = (ах+ а)(Ьх+ Ь ) 15аЬх + (аЬ + аЬ)х + аЬаЬх + (аЬ + аЬ 1)х + а Ь. + + аЬ Е(х) = (аЬ + аЬ+ а, Ь,)х + + аЬ+ са Ь.Устройство осуществляет умноже- О ние за пять тактов работы распреде. лителя 17 тактовых сигналов и работает следующим образом.Два .перемножаемых элемента А и В поля ОЕ(2 ф) в виде 2 Ь-разрядных двоичных комбинаций в исходном состоянии хранятся в параллельных ре-. гистрах 1,2 множимого и множителя. В первый такт работы распределителя 17 тактовых сигналов блока 15 управления управляющий сигнал с выходов первого, третьего и пятого элементов 16 ИЛИ блока 15 управленияпоступает на вторые входы ю -первыхэлементов 3 И первой группы, щ -первых элементов 4 И второй группы иэлементов 11 И пятой группы, разрешая прохождение компоненты а с ьпервых выходов регистра 1 множимогочерез элементы 7 ИЛИ первой группына щ первые входы регистра 13 адреса, а компоненты Ь - с ю первых вы - .ходов регистра 2 множителя через элементы 8 ИЛИ второй группы на остальные входы регистра 13 адреса. Регистр13 адреса по компонентам Ми Ъ выбирает ячейку в блоке 5 памяти, в которой записано произведение этих компонент и считывает содержимое этой ячейки, которое в виде ю-разрядного двоичного числа через элементы 11 И пя- утой группы поступает на М первые инФормационные входы накапливающегосумматора 14.Во втором .такте работы распредели".теля 17 тактовых .сигналов блока 15управления управляющий сигнал с первого выхода распределителя 17 посту-пает на вторые входы элементов 9 И третьей группы и элементов 10 И четвертой группы, а с выхода шестогоэлемента 16 ИЛИ блока 15 управленияна вторые входы элементов 12 И шес.- той группы, разрешая прохождение компоненты,а с выходов параллельногорегистра 6 через элементы 7 ИЛИ первой группы на о первые входы регистра 13 адреса, а произведения а Ь с в первых выходов накапливающего сумматора 14 через элементы 8 ИЛИ второй группы на остальные входы регистра 13 адреса. С помощью регистра 13 адреса из блока 5 памяти считывается произведение а Ь с , которое через элементы 12 И шестой группы поступает на остальные инФормационные входы накапливающего сумматора 14.В третьем такте работы распределителя 17 тактовых сигналов блока 15 управления управляющий сигнал с выходов первого, четвертого и пятого элементов 16 ИЛИ блока 15 управления поступает на вторые входы ьи первых элементов 3 И первой группы, остальных элементов 4 И второй групы и элементов 11 И пятой группы, разрешая прохождение компоненты ас щ первых выходов регистра 1 мйожимого через элементы 7 ИЛИ первой группы на ю первые входы регистра 13 адреса, а компоненты Ь - с остальных выходов регистра 2 множителя через элементы 8 ИЛИ второй группы на остальные входы регистра 13 адреса. С помощью регистра 13 адреса из блока 5 памяти считывается произведение а Ь, которое через элементы 11 И пятой группы поступает иа ит первые входы накапливающего сумматора 14, суммируясь в нем с произведением аЬ . Таким образом, после третьего такта работы устройства, в м первых разрядах накапливающего сумматора 14 заФиксировано число (а Ь + а,Ь). Э четвертом такте работы управляющий сигнал с выходов второго, третьего и пятого элементов 16 ИЛИ блока 15 управления поступает на вторые входы остальных элементов 3 И первой группы, м первых элементов 4 И второй группы и элементов 11 И пятой группы, разрешая прохождение компонент а и Ь на входы регистра 13 адреса, а следовательно, и считываниеиз блока 5 памяти произведения а Ь , которое поступает через элементы 11 И пятой группы в ю первые разряды накапливающего сумматора 14.Таким образом, после четвертого такта работы устройства в щ первых разрядах накапливающего сумматора 14 записана сумма (з Ь + а,Ь + а, Ь) .В пятом такте работы управляющий сигнал с выходов второго, четвертого и шестого элементов 16 ИЛИ блока 15 управления поступает на вторые входы остад ных элементов 3 И первой группы, остал ных элементов 4 И второй группы и элементов 12 И шестой группы, разрешая прохождение компонент а.2 и Ь на входы регистра 13 адреса, а следовательно, и считывание из блока 5 памяти произведения а,2 Ьа,которое через элементы 12 И шес959077 15 ветстжнно со вторыми входами элементов ИЛИ первой группы, выходы эле ф 10 Ч = 2 в 2 -- бит,баходы остальных элементов И второй группы соединены соответственно со25 вторыми входами эЛементов ИЛИ второй Ч Ч( 10 фа(= -2 32 Формула изобретения Устройство для умножения элементов конечного поля размерности 2 в, содержащее параллельные 2 в-разрядные регистры множимого и множителя, первую и вторую группы элементов И по 2 в элементов И в каждой блок памяти,.о тл и ч а ю щ е е с я тем что, с целью уменьшения объема оборудования, в устройство введены параллельный в-разрядный регистр, первая и, вторая группы элементов ЙЛИ . 40 по в элементов ИЛИ в каждВй, третья, четвертая, пятая и шестая группы элементов И .по в элементов И в каждой, параллельный 2 в-разрядный регистр адреса(.,накапливающий сумма ,тор и блок управления(содержащий . распределитель тактовых сигналов и шесть элементов ИЛИ, причем выходы регистра множимого соединены соответственно с первыми входами элементов И первой группы, выходы регистра множителя соединены соответственно с первыми входами элементов И второй гуппи, выходы параллельного.и-разрядного регистра соединены соответственно с первыми входами элементов И третьей группы, вторые входы ю первых элементов И первой группы объединены и соединены с выходом пер вого элемента ИЛИ блока управления, вторые входы остальных элементов И первой группы .объединены и соединены с выходом второго элемента ИЛИ блока управления, вторые входы ти первых элементов И второй группы объединены и соединены с выходом третьего той группы поступает в остальные разряды накапливающего сумматора 14. Таким образом, после пятого такта работы устройства в фи первых разрядах накапливающего сумматора 14 зафиксирована компонента (а Ь + аЬ + + а Ь ), а в остальных разщщах - компонента (а Ь + саЬ., ) произведения АВУстройство по сравнению с прототипом обеспечивает выигрыш в объеме памяти для хранения произведений, а также в разрядности перемножаемых чисел.Если в прототипе объем памяти составляет то в данном стройстве он составитЧ = в 2 бит,и таким образом выигрыш в памятиданного, устройства по сравнению спрототипом элемента ИЛИ блока управления, вторые входы остальных элементов И второй группы объединены и соединены свыходом четвертого элемента ИЛИ блока управления, вторые входы элементов И третьей группы объединены исоединены с первым выходом распределителя тактовых сигналов блока управления и с объединенными вторыми входами элементов И четвертой группы,выходы и первых элементов И первойгруппы соединены соответственно с первыми входами элементов ИЛИ первой группы, выходы остальных элементов И первой группы соединены соотментов И третьей группы соединены соответственно с третьими входами элементов ИЛИ первой группы, выходы П первых элементов И второй группы соединены соответственно с первыми.входами элементов ИЛИ второй группы, выгруппы, выходы элементов И четвертой группы соединены соответственно с третьими входами элементов ИЛИ второй группы, выходы элементов ИЛИпервой группы соединены соответственно с ю первыми входами регистраадреса, выходы элементов ИЛИ второйгруппы соединены соответственно состальными входами регистра адреса,выходы которого соответственно соединены с адресными входами блока памяти, выходы которого соединены соответственно с первыми входами элементов И пятой и шестой групп, вто.рые входы элементов И пятой группыобъединены и соединены с выходом пятого элемента ИЛИ блока управления,вторые входы элементов И шестой груп.пы объединены и соединены с выходомшестого элемента ИЛИ блока управления, выходы элементов И пятой и,шестой групп соединены соответственно с информационными входами накапливающего .сумматора, выходы ипер,вых разрядов которого соединены соответственно с первыми входами элементов И четвертой группы иявляются в первыми разрядами выходнойшины устройства, а остальные выходынакапливающего сумматора являютсясоответствующими разрядами выходнойшины устройства, второй выход распределйтеля тактовых сигналов блокауправления соединен с первыми входами первого, третьего и пятого элементов ИЛИ блока управления, первыйвыход распределителя тактовых сигналов блока управления соединен спервым входом шестого элемента ИЛИблока управления, третий выход распределителя тактовых. сигналов блокауправления соединен с первым входом10 959077 ВНИИПИ Заказ 7018/66 Тираж 73 о лиал ППП,"Патент , г. Ужгород,ая,4 л.Про четвертого элемента ИЛИ и со вторыми входами первого и пятого элементов ИЛИ блока управления, четвертыйвыход распределителя тактовых сигналов блока управления соединен с первым входом второго элемента ИЛИ, 5вторым входом третьего элемента ИЛИи третьим входом пятого элемента ИЛИблока управления, пятый выход распределителя тактовых сигналов блокауправления соединен со вторыми входа мй второго, четвертого, и шестогоэлементов ИЛИ блока управления. Источники информации,принятые во внимание при экспертизе1. Блох Э.Л., Зяблов В.В. Обобщенные каскадные коды. Я., "Связью,1976, с, 99.2. Авторское свидетельство СССРМ 550636, кл. 6 06 Г 7/52,1971 (прототип).