Устройство для умножения элементов конечного поля GF(2 @ ) при м @ 3 Советский патент 1992 года по МПК G06F7/49 G06F7/52 

Изобретение относится к специализированным устройствам вычислительной техники и может использоваться в кодирующих и декодирующих устройствах, работающих с элементами конечных полей полиномов GF(2m) при m 3, например в устройствах системы компакт-диск.

Известны устройства деления полиномов над конечными полями GF(2m), содержащее два блока логарифмирования, блок вычитания и блок антилогарифмирования, причем входы блоков логарифмирования являются входами коэффициентов полиномов-сомножителей, выходы блоков логарифмирования подсоединены к двум группам входов блока вычитания соответственно, выход которого подсоединен к входу блока антилогарифмирования, выходы которого являются выходами коэффициентов

полинома-произведения соответственно, При замене в таких устройствах блока вычитания блоком суммирования устройства деления преобразуются в устройства умножения двух полиномов над конечными полями GF(2m).

Недостатками таких устройств являются их большая сложность реализации и большие аппаратурные затраты при m 4.

Известно устройство для деления элементов поля Галуа, содержащее первый и второй сдвиговые регистры, один элемент И, один элемент ИЛИ-НЕ, декодер, кодер и умножитель, причем, информационные входы первого и второго сдвиговых регистров являются входами устройства коэффициентов полинома-делителя и полинома-делимого соответственно, выходы подсоединены к входам декодера и к первой группе входов

GO 00 СЛ

умножителя соответственно, а тактовые входы объединены и подсоединены к выходу элемента И, первый вход которого является тактовым входом устройства, а второй вход подсоединен к выходу элемента ИЛИ- НЕ, входы которого объединены с второй группой входов умножителя и подсоединены к выходам кодера, входы которого подсоединены к выходам декодера, при этом выходы умножителя являются выходами коэффициентов результирующего полинома.

В этом устройстве производится операция умножения элементов конечного поля, а для выполнения операции деления элементов поля Галуа производится предварительное определение обратного элемента для полинома-делителя при помощи декодера и кодера, содержащее ПЗУ каждый.

Недостатком такого устройства являются его большие аппаратурные затраты.

Цель изобретения - сокращение аппаратурных затрат.

Для достижения поставленной цели в устройстве умножения элементов конечного поля GF(2 ) при m 3, содержащем три регистра, два мультиплексора, группу блоков матричного преобразования, группу блоков элементов И, блок сумматоров по модулю два и блок управления, причем выходы блоков матричного преобразования группы соединены соответственно с первыми входами блоков элементов И группы, выходы которых соединены с соответствующими входами сумматоров по модулю два блока, информационные входы первой и второй групп устройства соединены соответственно с информационными входами первой и второй групп первого мультиплексора, выходы первого регистра соединены с соответствующими входами блоков матричного преобразования, первый и второй входы блока управления соединены соответственно с входами Обращение и тактовым входом устройства, выход Готовность которого соединен с первым выходом блока управления, информационные входы первой группы устройства соединены с соответствующими установочными входами первого и второго регистров, выходы первого мультиплексора соединены соот- ветственносустановочными входами третьего регистра, выходы которого соединены соответственно с информационными входами первой группы второго мультиплексора, информационные входы второй группы которого соединены соответственно с выхода- ми второго регистра, а выходы соответственно с вторыми входами блоков элементов И группы, выходы сумматоров по модулю два блока соединены соответственно с информационными входами первого и третьего регистров и выходами результата устройства, вход сброса которого соединен с входами сброса первого и третьего регист- ров и третьим входом блока управления, первый вход которого соединен с первым управляющим входом первого мультиплексора, второй управляющий вход которого соединен с вторым входом блока управле0 ния, третий выход которого соединен с тактовыми входами первого и третьего регистров, четвертый, пятый, шестой и седьмой выходы блока управления соединены соответственно с входом сброса второго ре5 гистра, первым и вторым управляющими входами второго мультиплексора и выходом Занят устройства.

При этом блок управления содержит элемент ИЛИ, элемент И, три элемента

0 ИЛИ-НЕ, D-триггер, (1од2т +1)-разрядный двоичный счетчик (где Jlogamf - ближайшее целое большее к logam число, если fog2m - нецелое) и элемент НЕ, вход которого соединен с первым входом блока управления и

5 первым входом первого элемента ИЛИ-НЕ, выход которого соединен с первым входом второго элемента ИЛИ-НЕ, второй вход которого соединён с входом сброса D-тригге- ра, выходом элемента ИЛИ и четвертым

0 выходом блока управления, второй вход которого соединен с тактовым входом D-триг- гера и первым входом элемента И, второй вход которого соединен с выходом D-триг- гера, информационный вход которого сое5 динен с выходом второго элемента ИЛИ-НЕ, вторым входом первого элемента ИЛИ-НЕ и седьмым выходом блока управления, третий вход которого соединен с первым входом элемента ИЛИ и входом

0 установки в нуль (1од2т +1)-разрядного двоичного счетчика, счетный вход которого соединен с выходом элемента И и третьим выходом блока управления, второй выход которого соединен с выходом элемента НЕ,

5 а четвертый и пятый выходы - соответственно с прямым и инверсным выходами младшего разряда (1од2Гп +1)-разрядного двоичного счетчика, прямые выходы Qlog2mD старших разрядов которого соеди0 нены с соответствующими входами третьего элемента ИЛИ-НЕ, выход которого соединен с шестым выходом блока управления и вторым входом элемента ИЛИ.

На фиг.1 изображена структурная блок5 схема устройства умножения над полем GF(2m); на фиг.2 - структурная схема регистра с D-триггерами; на фиг.З - структурная схема регистра с RS-триггерами; на фиг.4 - структурная схема мультиплексора; на фиг.5 - структурная схема блока управления; на фиг.б - структурная схема двоичного счетчика блока управления; на фиг.7 - структурная схема 1од2т -входового элемента ИЛИ-НЕ блока управления; на фиг.8 - временные диаграммы работы блока уп- равления; на фиг.9 - временные диаграммы работы устройства умножения над полем GF(2m) при выполнении им операции обращения элемента поля при m 3.

Устройство умножения над полем GF(2m) (фиг.1) состоит из первого и второго регистров 1i и 12 с D-триггерами, третьего регистра 2 с RS-триггерами, одной группы 3 блоков матричного преобразования, первого и второго мультиплексоров 4i и 42 с двумя группами информационных входов каждый, одной группы 5 блоков элементов И, одного блока б сумматоров по модулю два и блока 7 управления, причем m установочных входов первого регистра 1i являются одно- именными m входами первой группы информационных входов устройства и объединены с одноименными m входами первой группы информационных входов первого мультиплексора 4i и с m информа- ционными входами регистра 2, m прямых выходов первого регистра 11 подсоединены к одноименным m входам группы 3 блоков матричного преобразования, т2 выходов которого подсоединены к соответствующим т2 входов первой группы входов группы 5 блоков элементов И, т2 выходов которой подсоединены к соответствующим m входам блока 6 сумматоров по модулю два, m выходов которого являются одноименным m информационными выходами устройства и подсоединены к одноименным объединенным m информационным входам первого и второго регистров 11 и 12, при этом m входов второй группы информационных входов первого мультиплексора 4i являются одноименными m входами второй группы информационных входов устройства, m выходов первого мультиплексора 4i подсоединены к одноименным m установочным входам вто- рого регистра 1а, m выходов которого подсоединены к одноименным m входам первой группы информационных входов второго мультиплексора 42, m входов второй группы информационных входов кото- рого подсоединены к одноименным m выходам регистра 2, a m выходов второго мультиплексора 42 подсоединены к одноименным m входам второй группы входов группы 5 блоков элементов И, причем m выходов блока 6 сумматоров по модулю два объединены с одноименными m информационными входами первого и второго регистров 1i и 12 и являются одноименными m информационными выходами устройства,

при этом первый и второй входы блока 7 управления, являющиеся соответственно входами Обращение и Исходное состояние устройства, подсоединены к первому управляющему входу первого мультиплексора 4i и к объединенным входам сброса в нулевое состояние первого и второго регистров 11 и 12, а третий вход блока 7 управления является тактовым входом устройства, при этом с первого по пятый выходы блока 7 управления подсоединены к второму управляющему входу первого мультиплексора 4i, к объединенным тактовым входам первого и второго регистров 11 и 12, к входу сброса в нулевое состояние регистра 2, к первому и к второму управляющим входам второго мультиплексора 42 соответственно, а шестой и седьмой выходы блока 7 управления - являются выходами Готов и Занят устройства. Регистр 11 (12) (фиг.2) состоит из m D-триггеров 8, причем входы установки в единичное состояние и информационные входы всех m D-триггеров 8 являются одноименными с порядковыми номерами D- триггеров 8 m установочными и гг. информационными входами регистра 11 (1a) соответственно, прямые выходы D-триггеров 8 являются одноименными с порядковыми номерами D-триггеров 8 m выходами регистра 1i(l2), при этом объединенные тактовые входы всех m D-триггеров 8 являются тактовым входом регистра 1i (1.2), а объединенные входы сброса в нулевое состояние всех m D-триггеров являются входом сброса в нулевое состояние регистра 1i (12).

Регистр 2 (фиг.З) состоит из m RS-тригге- ров 9, причем входы установки в единичное состояние всех m RS-триггеров 9 являются одноименными с порядковыми номерами RS- триггеров 9 m установочными входами регистра 2, а объединенные входы сброса всех RS-триггеров 9 являются входом сброса в нулевое состояние регистра 2.

Мультиплексор 4i (42)(фиг.4) состоит из 2т двухвходовых элементов И 10 и m двух- входовых элементов ИЛИ 11, причем первые входы первых по порядку счета m двухвходовых элементов И 10 являются одноименными с порядковыми номерами двухвходовых элементов И 10 m входами первой группы информационных входов мультиплексора 4i (42)t первые входы следующих по порядку счета m двухвходовых элементов И 10 с порядковыми номерами от (т + 1) по 2т являются m входами второй группы информационных .входов мультиплексора 4i (42) номерами на m меньше порядковых номеров соответствующего двухвходового элемента И 10, при этом вторые объединенные входы первых по порядку счета m двухвходовых элементов И 10 объединены и являются первым управляющим входом мультиплексора 4i (42), а вторые объединенные входы следующих по порядку счета m двухвходовых элементов И 10 с порядковыми номерами от (т + 1) по 2т включительно являются вторым управляющим входом мультиплексора 4i (42), причем выходы первых по порядку счета m двухвходовых элементов И 10 подсоединены к первым входам всех m одноименных двухвходовых элементов ИЛИ 11, вторые входы которых подсоединены к выходам следующих по порядку счета m двухвходовых элементов И 10 с порядковыми номерами на m больше порядковых номеров двухвходовых элементов ИЛИ 11 соответственно, а выходы являются одноименными m выходами мультиплексора 4i (42).

Блок 7 управления (фиг.5) состоит из инвертора 12, первого и второго двухвходовых элементов ИЛИ-НЕ 13т и 132, D-тригге- ра 14, элемента И 15, (1од2т +1)-разрядного двоичного счетчика 16, где символом log2m обозначено натуральное число, полученное при округлении числа Iog2m до ближайшего целого, если число Iog2m - нецелое, Qlog2mD- входового элемента ИЛИ-НЕ 17 и элемента 18 ИЛИ, причем, вход инвертора 12 является первым входом блока 7 управления и объединен с первым входом первого двух- входового элемента ИЛИ-НЕ 13i, выход которого подсоединен к первому входу второго двухвходового элемента ИЛИ-НЕ 132, первый вход элемента ИЛИ 18 является вторым входом блока 7 управления и объединен с входом установки в исходное состо- яние ()-разрядного двоичного счетчика 16, прямой вход D-триггера 14 подсоединен к первому входу элемента И 15, а тактовый вход D-триггера 14 объединен с вторым входом элемента И 15 и является третьим входом блока.7 управления, при этом выход инвертора 12 является первым выходом блока 7 управления, выход элемента И 15 объединен со счетным входом (1од2т +1)-разрядного двоичного счетчика 16 и является вторым выходом блока 7 управления, выход элемента ИЛИ 18 объединен с вторым входом двухвходового элемента ИЛИ-НЕ 132, с входом сброса в нулевое состояние D-триггера 14 и является третьим выходом блока 7 управления, причем инверсный и прямой выходы самого младшего разряда (1од2т +1)-разрядного двоичного счетчика 16 являются четвертым и пятым выходами блока 7 управления соответственно, выход .01од2тО-входового элемента ИЛИ-НЕ 17 объединен с вторым входом элемента ИЛИ 18 и является шестым

выходом блока 7 управления, выход второго двухвходового элемента ИЛИ-НЕ 132 является седьмым выходом блока 7 управления и объединен с вторым входом первого двухвходового элемента-ИЛИ-НЕ 13i и с информационным входом D-триггера 14, при этом прямые выходы log2m старших разрядов Qlog2m старших разрядов (1од2т +1)-разрядного двоичного счетчика 16 подсоединены соответственно к входам (1од2т)-входового элемента ИЛИ- НЕ 17.

(1од21п +1)-разрядный двоичный счетчик 16 (фиг.6) блока 7 управления состоит из

Qlog2m +1) D-триггеров 19, где символом log2m обозначено натуральное число, получаемое в результате округления до ближайшего целого числа Iog2m, если оно не целое, причем тактовый вход первого D-триггера

19i памяти является счетным входом двоичного счетчика 16, инверсный выход каждого из D-триггеров 19 подсоединен к собственному информационному входу, прямой выход предыдущего D-триггера 19i, где 1 1,2.

..., log2m, подсоединен к тактовому входу последующего D-триггера 19i+i, при этом инверсный и прямой выходы первого D- триггера 19i являются первым и вторым выходами двоичного счетчика 16, а прямые

выходы остальных og2m D-триггеров 19j, где j 2, 3,..., log2m +1, являются остальными 1од2пп выходами двоичного счетчика 16 с порядковыми номерами начиная с третьего, причем вход сброса в нулевое состояние

первого D-триггера 19i является входом установки в исходное состояние двоичного счетчика 16 и подсоединен к входам установки в единичное состояние тех D-триггеров 19j, где j 2, 3 log2m +1, для которых

соответствующие (j-1)-e разряды двоичного представления числа (2 log - m + 2) равны единице, и к входам сброса в нулевое состояние тех D-триггеров 19j, для которых соответствующие разряды двоичного

представления числа (2J|og2mf - m + 2) равны нулю.

01од2гп)-входовый элемент ИЛИ-НЕ 17 (фиг.7) блока 7 управления состоит из двухвходового элемента ИЛИ-НЕ 20 и из

Iog2rii -2 0 при m 4 двухвходовых элементов ИЛИ 21, причем выход двухвходового элемента ИЛИ-НЕ 20 является выходом 01од2гп)-входового элемента ИЛИ-НЕ 17, первый вход является первым входом

01од2гп)-входового элемента ИЛИ-НЕ 17, а второй вход является вторым входом (1од2т)-входового элемента ИЛИ-НЕ 17 при m 3 или 4 либо подсоединен к выходу первого двухвходового элемента 211 при

т 4, при этом первые входы Qlog2m - 2)

двухвходовых элементов ИЛИ 21 являются последующими входами (1од2т }-входовЬго элемента ИЛИ-НЕ 17с порядковыми номерами на единицу больше порядковых номеров двухвходовых элементов ИЛИ-НЕ 17, вторые входы предыдущих двухвходовых

элементов ИЛИ 21 j, где 1 1,2 log2m 3, подсоединены к выходам следующих двухвходовых элементов ИЛИ 21i+i, при этом второй выход последнего двухвходово- го элемента 21 iog2m -2 ИЛИ является последним, log2m, входом(1од2т г-входового элемента ИЛИ-НЕ 17.

Временные диаграммы работы блока 7 управления (фиг.8) состоят из двенадцати (а, б, в, г, д, е, ж, з, и, к, л, м) диаграмм изменений сигналов во времени при работе блока 7 управления на входах и выходах блока 7 управления и его элементов.

Буквенные обозначения временных ди- аграмм работы блока 7 управления устройства умножения над полем GF(2m) (фиг.8) соответствуют изменениям во времени сигналам на следующих входах и выходах блока 7 управления и его элементов (фиг.5): а - первый вход блока 7 управления; б - первый выход блока 7 управления; в - выход второго двухвходового элемента ИЛИ-НЕ 132 блока 6 управления (седьмой выход блока 7 управления); г - второй вход блока 7 управ- ления; д - выход двухвходового элемента ИЛИ 18 (третий выход блока 7 управления); е - прямой выход элемента 14 памяти блока 7 управления; ж - третий вход блока 7 управления; з - выход двухвходового элемен- та И 15 (второй выход блока 7 управления); и - четвертый выход блока 7 управления; к -пятый выход блока 7управления; л -входы 1од2т -входового элемента ИЛИ-НЕ 17 блока 7 управления; м - выход Qlog2m)-Bxo- дового элемента ИЛИ-НЕ 17(шестой выход блока 7 управления).

Временные диаграммы работы устройства над полем GF(2m) при выполнении им операции обращения элемента поля при m 3 (фиг.9) состоят из двенадцати (а, б, в, г, д, е, ж, з, и, к, л, м) диаграмм изменений сигналов во времени при выполнении устройством операции обращения элементов на входах и выходах устройства, блоке 7 управления и функциональных элементах устройства.

Буквенные обозначения временных диаграмм работы устройства умножения над полем GF(2m) при выполнении им операции обращения элемента поля (фиг.9) соответствует изменениям во времени сигналам на следующих входах и выходах устройства умножения над полем GF(2m), его блоке 7 управления и функциональных элементах

(фиг.1): а - первая группа информационных входов устройства; б - вход Обращение устройства; в - вход Исходное состояние устройства; г - тактовый вход устройства; д

-первый выход блока 7 управления; е - второй выход блока 7 управления; ж - третий выход блока 7 управления; з - четвертый выход блока 7 управления; и - пятый выход блока 7 управления; к- шестой выход блока 7 управления (выход Готов устройства); л

-седьмой выход блока 7 управления (выход Занят устройства); м- группа информационных выходов устройства.

При описании принципа действия устройства умножения над полем GF(2m) (фиг.1) и его функцинальных элементов выберем в качестве параметра сигнала на выходе или входе элемента или устройства напряжение, уровни которого определяются как для положительной логики. Таким образом, будем считать, что высокий уровень сигнала на входе или выходе функционального элемента или устройства определяет истинное значение величины приписываемой этому входу или выходу, в нулевой алгебре, а низкий уровень - ложное.

Кроме того, будем считать, что единице в двоичном представлении какого-либо числа соответствует сигнал высокого уровня на соответствующем выходе или входе, а нулю

-низкого уровня и, наоборот, сигнал высокого уровня на каком-либо входе или выходе соответствует единице в двоичном представлении соответствующего числа, а низкого уровня - нулю.

Прежде чем приступить к описанию принципа действия устройства умножения над полем GF(2m) (фиг.1), опишем сначала принцип действия 01од2тО-входового элемента ИЛИ-НЕ 17 и двоичного счетчика 16 блока 7 управления устройства умножения над полем СР(2ш)(фиг.7 и 6 соответственно), опишем принцип действия блока 7 управления устройства умножения над полем GF(2m) (фиг.5), а также принцип действия мультиплексора 4i (42), регистра 2 с RS-триггерами и регистра 1i (12) с D-триггерами устройства умножения над полем GF(2m) (фиг.4, 3 и 2 соответственно).

Кроме того, будем считать идентичными термин полином и термин элемент поля.

01од2тО-входовый элемент ИЛИ-НЕ 17 блока 7 управления над полем GF(2m) (фиг.7) работает следующим образом.

Если на всех входах (1од2пл0-входового элемента ИЛИ-НЕ 17 будут сформированы сигналы низких уровней, то на выходах всех его элементов 21 ИЛИ формируются сигналы низких уровней, а значит на оба входа двухвходового элемента ИЛИ-НЕ 20 подаются сигналы низких уровней, что приводит к формированию на его выходе и, следо- вательно, на выходе (1од2т)-входового элемента ИЛИ-НЕ 17 сигнала высокого уровня. В противном случае, если хотя бы на одном входе (1од2тО-входового элемента ИЛИ-НЕ 17 будет сформирован сигнал высокого уровня, то на его выходе сформируется сигнал низкого уровня.

(1од2т +1)-разрядный двоичный счетчик 16 блока 7 управления устройства умножения над полем GF(2m) (фиг.6) работает следующим образом.

В исходном состоянии двоичного счетчика 16 его первый D-триггер 19i сброшен в нулевое состояние, а состояния остальных D-триггеров 19 соответствуют двоичному представлению числа 2- °92т - т + 2. При этом на оба входа двоичного счетчика 16 подаются сигналы низких уровней. Если счетчик 16 находится не в исходном состоянии, то при подаче на вход установки в исходное состояние двоичного счетчика 16 импульсного сигнала высокого уровня первый D-триггер 19i сбросится в нулевое состояние, а остальные D-триггеры 19|, где i 2, 3, .... log2m + 1, установятся в состояния, соответствующие (1-1)-м разрядам двоичного представления натурального числа

2 log2m m + 2.

При этом на первом и втором выходах двоичного счетчика 16 сформируются сигналы высокого и низкого уровней соответственно, а на остальных выходах - сигналы, соответствующие двоичному представлению числа 2 log2m - m + 2.

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

Блок 7 управления устройства умножения (фиг.5) работает следующим образом.

В исходном состоянии блока 7 управления его (1од2Гл +1)-разрядный двоичный счетчик 16 находится в своем исходном состоянии (фиг.5 и 6), D-триггер 14 сброшен в нулевое состояние, на выходе первого элемента ИЛИ-НЕ 13i сформирован сигнал высокого уровня, на первый и второй входы блока 7 управления подаются сигналы низких уровней, а на третий вход постоянно подаются тактовые импульсы (фиг.5 и 8). При этом на первом и четвертом выходах блока 7 управления сформированы сигналы

высоких уровней как сигналы на выходе инвертора 12, на вход которого подан сигнал низкого уровня, и на инверсном выходе сброшенного в нуль первого D-триггера 19i двоичного счетчика 16 (фиг.5 и 6), а на ос0 тальных выходах блока 7 управления сформированы сигналы низких уровней: на втором выходе - как на выходе двухвходо- вого элемента И 15, на первый вход которого подан сигнал низкого уровня; на шестом

5 выходе, как на выходе (1од2тО-входового элемента ИЛИ-НЕ 17, не на всех входах которого сформированы сигналы низких уровней, ибо число 2- log2m - m + 2 не равно нулю при m 2; на третьем выходе, как на

0 выходе элемента И 18, на все входы которого подаются сигналы низких уровней; на пятом выходе, как на прямом выходе сброшенного в нуль первого D-триггера 19i (1од21Т| +1)-разрядного счетчика 16 (фиг.5 и

5 6), на седьмом выходе, как на выходе элемента ИЛИ-НЕ 132, на первый вход которого подается сигнал высокого уровня.

На двухвходовых элементах ИЛИ-НЕ 13 собран RS-триггер, поэтому в исходном

0 состоянии блока 7 управления на выходе второго двухвходового элемента ИЛИ-НЕ 132, а значит и на информационном входе элемента 14 памяти, сформирован сигнал низкого уровня.

5 При подаче сигнала высокого уровня на первый вход блока 7 управления на выходе первого элемента ИЛИ-НЕ 13i и на первом выходе блока 7 управления формируются сигналы низких уровней, а на выходе второ0 го элемента ИЛИ-НЕ 132 и, значит, на информационном входе D-триггера 14 и седьмом выходе блока 7 управления формируется сигнал высокого уровня. По переднему фронту очередного тактового импульса,

5 поступающего на третий вход блока 7 управления, а значит и на тактовый вход D-триггера 14 и второй вход элемента И 15, D-триггер 14 установится в единицу, на первом входе элемента И 15 сформируется сиг0 нал высокого уровня, и тактовые импульсы начнут формироваться на выходе элемента И 15, а значит и на втором выходе блока 7 управления и на счетном входе Qlog2m +1)- разрядного двоичного счетчика 16 (фиг.5 и

5 8). При этом состояние (1од2т +1)-разрядно- го счетчика 16 будет изменяться до тех пор, пока на всех входах (1од2т)-входового элемента ИЛИ-НЕ 17 не сформируются сигналы низких уровней, При формировании сигналов низких уровней на всех входах

(1од2т)-входового элемента ИЛИ-НЕ 17 на его выходе формируется сигнал высокого уровня, который поступает на шестой выход блока 7 управления и на второй вход элемента ИЛИ 18, на выходе которого тоже формируется сигнал высокого уровня, который поступает на третий выход блока 7 управления, на вход сброса в нулевое состояние элемента памяти 14 и на второй вход второго элемента ИЛИ-НЕ 132. При этом на выходе второго элемента ИЛИ-НЕ 132, а значит на седьмом выходе блока 7 управления и на информационном входе D- триггера, формируются сигналы низкого уровня, на первом входе элемента И Сформируется сигнал низкого уровня и, следовательно, на выходе элемента И 15, а значит, на счетном входе двоичного счетчика и на втором выходе блока 7 управления, формируется сигнал низкого уровня (фиг.5 и 8), а состояние блока 7 управления может измениться только при поступлении сигнала высокого уровня на его первый или второй выходы.

При подаче сигнала высокого уровня на второй вход блока 7 управления при сигнале низкого уровня на его первом входе (1од2т +1)-разрядный двоичный счетчик 16 устанавливается в свое исходное состояние и на выходе двухвходового элемента ИЛИ 18, а значит на входе сброса в нулевое состояние D-триггера 14, на втором входе второго элемента ИЛИ-НЕ 132 и на третьем выходе блока 7управления, формируется сигнал высокого уровня, по которому D-триггер 14 сбрасывается в нулевое состояние, а на выходах первого и второго элементов ИЛИ- НЕ 13i и 132 формируются сигналы высокого и низкого уровня соответственно.

Следовательно, при подаче сигнала высокого уровня на второй вход блока 7 управления блок 7 управления переходит в свое исходное состояние.

Таким образом, после подачи на первый вход блока 7 управления импульсного сигнала высокого уровня, при сигнале низкого уровня на его втором входе и непрерывной серией тактовых импульсов на его третьем входе, блок 7 управления отрабатывает свой полный цикл работы, в течение которого сигнал на пятом выходе блока 7 управления изменит свой уровень с низкого на высокий

2 Юд2тГ (2 Юд2тГ т + 2) т 2

раз. Следовательно, поскольку на тактовый вход двоичного счетчика 16 должно поступить в два раза больше перепадов уровней сигналов с низкого на высокий, чем сформированных таких же перепадов на его втором выходе, то на втором выходе блока 7 управления при отработке им полного цикла работы сформируются 2(т - 2) импульсных сигналов высокого уровня.

Мультиплексор А устройства умножения над полем GF(2m) (фиг.4) работает следующим образом.

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

5 одноименных входах второй группы информационных входов мультиплексора 4 при подаче сигнала высокого уровня на его второй управляющий вход. Мультиплексор 4 выполняет функцию управляемого ключа.

0 Регистр 2 устройства умножения над полем GF(2m) (фиг.З) работает следующим образом.

В исходном состоянии регистра 2 все RS-триггеры 9 находятся в нулевом состоя5 нии и на все входы регистра 2 подаются сигналы низких уровней. При этом на всех выходах регистра 2 сформированы сигналы низких уровней (регистр 2 сброшен в нулевое состояние).

0 При подаче каких-либо сигналов на информационные входы регистра 2 при сигнале низкого уровня на его входе сброса в нулевое состояние на выходах регистра формируются сигналы, равные сигналам на

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

5 Регистр 1 устройства умножения над полем GF(2m) (фиг.2) работает следующим образом.

В исходном состоянии регистра 1 его D-триггеры 8 находятся в нулевых состояни0 ях, а на все входы принудительной установки регистра 1, на его тактовый вход и вход сброса в нулевое состояние подаются сигналы низких уровней. При исходном состоянии регистра 2 сигналы на его информационных

5 входах не определяются и могут быть произвольными. При этом на всех выходах регистра 2 с D-триггерами сформированы сигналы низких уровней (регистр 2 сброшен в нулевое состояние). При подаче произвольных сигналов на входы принудительной установки регистра 1 при сигналах низких уровней на его тактовом входе и входе сброса в нулевое состояние, на выходах регистра 1 сформируются сигналы, равные сигналам на его одноименных входах принудительной установки. Значения уровней сигналов на выходах регистра 1 сохраняются и после подачи на все его входы принудительной установки сигналов низких уровней. При подаче сигнала высокого уровня на вход сброса в нулевое состояние регистра 1 при сигналах низких уровней на всех его входах принудительной установки все D-триггеры 8 сбрасываются в нулевое состояние и регистр 1 переходит в свое исходное состояние при сигнале низкого уровня на его тактовом входе.

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

Устройство умножения над полем CF(2m) работает следующим образом.

В исходном состоянии устройства умножения над полем GF(2m) его регистры 1, регистр 2 и блок 7 управления находятся в своих исходных состояниях, на тактовый вход устройства подается непрерывная серия тактовых импульсов высокого уровня, а на остальные входы подаются сигналы низких уровней, При этом, на всех входах группы 3 блоков матричного преобразования, а значит и на всех ее выходах сформированы сигналы низких уровней. Следовательно, на всех выходах группы 5 блоков элементов И, а значит и на всех выходах блока 6 сумматора по модулю два, тоже сформированы сигналы низких уровней, которые подаются на информационные выходы устройства умножения и на информационные входы обоих регистров 1i и 12, причем на выходе Готов устройства сформированы сигнал низкого уровня (фиг.9).

В исходном состоянии устройства умножения над полем GF(2m) (фиг.1 и 9) на первом и втором управляющих входах первого мультиплексора 4ч сформированы сигналы низкого и высокого уровней соответственно, а на первом и втором управляющих входах второго мультиплексора 42

сформированы сигналы высокого и низкого уровней соответственно.

Устройство умножения над полем GF(m) (фиг.1) может выполнять две операции над 5 конечным полем полиномов GF(2m): операцию умножения двух элементов поля и операцию определения обратного элемента для ненулевого элемента поля.

При выполнении устройством опёра0 ции умножения двух элементов поля GF(2m) на входы первой и второй групп информационных входов устройства умножения над полем GF(2m) подаются сигналы, соответствующие коэффициентам первого и

5 второго полиномов-сомножителей соответственно. При этом на выходах первого и второго регистров 1i и 12 (фиг.1 и 2) формируются сигналы, равные сигналам на установочных входах, а значит и на входах

0 первой и второй групп информационных входов устройства соответственно. Сигналы с выходов первого регистра 11 с D-триггера- ми, преобразуясь в группе 3 блоков матричного преобразования, подаются на входы

5 первой группы информационных входов группы 5 блоков элементов И, на входы второй группы информационных входов которой поступают через второй мультиплексор 42 сигналы с выходов второго регистра 12.

0 При этом на выходах блока 6 сумматоров по модулю два и на информационных выходах устройства умножения над полем GF(2m), формируются сигналы, соответствующие коэффициентам полинома-произведения.

5 Так, исходное состояние устройства умножения над полем GF(2m), соответствует операции умножения нулей поля GF(2m).

Для выполнения устройством умноже0 ния над полем GF(2m) операции определения обратного элемента для ненулевого элемента поля GF(2m) необходимо подать на входы первой группы информационных входов устройства сигналы, соответствующие

5 коэффициентам обращаемого полинома, при сигналах низких уровней на всех входах второй группы информационных входов устройства, на вход Обращение устройства подать импульсный сигнал высокого уровня

0 длительностью достаточной для передачи сигналов с входов первой группы информационных входов мультиплексора 4i на его выходы, а затем на все входы первой группы информационных входов устройства снова

5 подать сигналы низких уровней (фиг.1 и 9). При этом на выходах обоих регистров 1i и 12 и на выходах регистра 2 формируются сигналы, соответствующие коэффициентам обращаемого полинома, на выходе Занят устройства формируется сигнал высокого

уровня, на выходах блока 6 сумматоров по модулю два, а значит и на информационных входах обоих регистров 1i и 12, формируются сигналы, соответствующие коэффициентам полинома, равного квадрату обращаемого полинома, а блок 7 управления начинает работу в соответствии с логикой его работы (фиг. 1-9). По переднему фронту первого тактового сигнала, формирующемуся на втором выходе блока 7 управления, на четвертом и пятом выходах блока 7 управления, а значит и на первом и втором управляющих входах второго мультиплексора 42, формируются сигналы низкого и высокого уровней соответственно. При этом регистры 11 и 12 устанавливаются в состояния, соответствующие сигналам на выходах блока 6 сумматоров по модулю два, а значит коэффициентам полинома, равного квадрату обращаемого элемента, а на входы второй группы входов группы 5 блоков элементов И подаются через второй мультиплексор 42 сигналы с выходов регистра 2, соответствующие коэффициентам обращаемого полинома.

Следовательно, на протяжении первого тактового импульса, формирующегося на втором выходе блока 7 управления, на выходах блока 6 сумматоров по модулю два формируются сигналы, соответствующие кубу обращаемого полинома.

По переднему фронту второго тактового импульсного сигнала, формирующегося на втором выходе блока 7 управления, на четвертом и на пятом выходах блока 7 управления формируются сигналы высокого и низкого уровней соответственно. При этом регистры 1i и 12 устанавливаются в состояния, соответствующие кубу обращаемого полинома, а на входы второй группы входов группы 5 блоков элементов И подаются сигналы с второго регистра 12. Следовательно, на протяжении второго та кто во го импульса, формирующегося на втором выходе блока 7 управления, на выходах блока 6 сумматоров по модулю два, а значит и на информационных выходах устройства, формируются сигналы, соответствующие коэффициентам полинома, равного шестой степени обращаемого полинома.

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

предыдущего четного по порядку счета тактового сигнала на втором выходе блока 7 управления, а в течение действия следующего четного по порядку счета тактового

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

При полном цикле работы блока 7 управления на его втором выходе сформируются 2(т - 2) тактовых импульсных сигналов высокого уровня. Другими словами, при отработке блоком 7 управления полного цикла работы на его втором выходе формируются т-2 пар тактовых сигналов.

При этом в течение действия последнего в полном цикле работы (2т-4)-го тактового сигнала на втором выходе блока 7 управления на его третьем, четвертом и шестом выходах и, значит, на выходе Готов устройства, формируются сигналы высоких уровней, причем на втором и седьмом

выходах блока 7 управления после формирования сигнала высокого уровня на его третьем выходе формируются сигналы низкого уровня, которые не изменяются до подачи, импульсного сигнала высокого

уровня на вход Обращение устройства.

Следовательно, при формировании сигнала высокого уровня на выходе Готов устройства на его информационных выходах будут сформированы сигналы, соответствующие коэффициентам полинома, равного (2т-2)-й степени обращаемого полинома, ибо после занесения коэффициентов обращаемого полинома в устройство на его выходах сразу же были сформированы

сигналы, соответствующие коэффициентам полинома, равного квадрату обращаемого полинома.

Докажем это утверждение методом математической индукции. Обозначим буквой

В значение обращаемого полинома, а буквой С - значение полинома, соответствующего сигналам, сформированным на информационных выходах устройства после отработки блоком 7 управления полного

цикла работы.

При mi 3числоki 2m-4 2(тактовых импульсов) и Ci (В2- В)2 В6 Пригп2 4к2 2 4-4 4иС2 (Сг В)2 (В6-В)2

При плз 5 ka 2 5 - 4 6 и, Сз ,., (С2 В)2 (В14 В)2 В30 .В В Ч „, Пусть при mi, где € N, I 6, С В--

причем, ki 2 mi - 4.

Определим значение Ci + i при 5

mi+i mi+1. Вычислим:

ki+1 2 mi+i - 4 2(mi + 1) - 4 2 mi + 2 - 4 2 mi - 4 + 2 ki + 2.

Тогда

.„

- «°-„, n«iK

Си-1 - (d В)2 (ВГ B)2 B -А В -, что и требовалось доказать. Другими словами, при т 2, т М,Ст В .

Cm В В , где символом В записан полином из поля GF(2m), обратный нену- левому полиному из этого же конечного поля.

Таким образом, при формировании сигнала высокого уровня на выходе Готов устройства на информационных выходах устройства будут сформированы сигналы, соответствующие коэффициентам полинома, равного обратному к обращаемому полиному.

При формировании сигнала высокого уровня на третьем выходе блока 7 управления регистр 2 сбрасывается в нулевое состояние.

Сигналы высокого уровня на выходе Готов устройства и на третьем выходе бло- ка 7 управления будут сохраняться до тех пор, пока на вход Исходное состояние устройства не будет подан импульсный сигнал высокого уровня. При этом блок 7 управления установится в свое исходное состояние и после переходных процессов от переднего фронта импульсного сигнала, поступающего на второй вход блока 7 управления, на выходе Готов устройства сформируется сигнал низкого уровня, а по заднему срезу импульсного сигнала высокого уровня, поступающего на второй вход блока 7 управления, на третьем выходе блока 7 управления сформируется сигнал низкого уровня.

Кроме того, по импульсному сигналу, поступающему на вход Исходное состояние устройства, его оба регистра 11 и 12 сбросятся в нулевое состояние, после чего возможно выполнение очередной операции умножения или обращения над полем GF(2m).

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

0

5

0

5

0 5 0

5 0

5

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

Таким образом, предлагаемое устройство выполняет операцию умножения двух элементов поля GF(2m) так же, как и известное за один такт работы устройства, а операцию обращения элемента поля GF(2m) за 2т - 3 такта работы устройства, включая и такт приема коэффициентов обращаемого элемента, против m тактов работы при выполнении такой же операции обращения известным устройством.

Однако выполнение операций предлагаемым устройством производится меньшими аппаратурными затратами.

Докажем это утверждение.

Аппаратурные затраты прототипа составляют три m-разрядные регистра с IK- триггерами, два мультиплексора на три группы по m входов каждая, один мультиплексор на две группы по m информационных входов каждая, одну группу блоков матричного преобразования, две группы по т2 элементов И каждая, два блока по т-вхо- довых сумматора по модулю два каждый и блок синхронизации, содержащий (m+2) D- триггера, пять двухвходовых элементов И, два двухвходовые элементы ИЛИ-НЕ и один инвертор.

Аппаратурные затраты предлагаемого устройства составляют три m-разрядные регистра, из которых два с D-триггерами и один с RS-триггерами, два мультиплексора на две группы по m информационных входов каждый, одну группу блоков матричного преобразования, одну группу из т2 элементов И, один блок из m m-входовых сумматоров по модулю два и блок управления, содержащий один инвертор, один двухвходовый элемент И, один )-входовый элемент ИЛИ-НЕ, один двухвходовый элемент ИЛИ, два элемента ИЛИ-НЕ и Qlog2m +2) D-триггеров, где символом log2m обозначено натуральное число, полученное в результате округления до ближайшего большего целого числа Iog2m, если Iog2m число не целое.

При этом каждый из трех регистров известного устройства состоит из m IK-триггеров и m инверторов, а в предлагаемом устройстве два регистра содержат каждый по m D-триггеров, синхронизируемых по фронту и третий регистр содержит m RS-триггеров.

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

элемента И-НЕ и два трехвходовых элемента И-НЕ. D-триггер, входящий в состав первых двух регистров предлагаемого устройства, имеющий минимальные аппаратурные затраты, может быть реализован по другой известной схеме, причем для синхронизации триггера положительным фронтом в этой схеме элементы ИЛИ заменяются на элементы И, D-триггер содержит здесь шесть трехвходовых элемента И-НЕ.

RS-триггер, входящий в состав третьего регистра предлагаемого устройства, имеющий .минимальные аппаратурные затраты, может быть реализован по известной схеме, где RS-триггер содержит два двухвходовых элемента И-НЕ.

Для реализации схемы предлагаемого устройства из известного исключаются три m-разрядные регистра с IK-триггерами, два мультиплексора на три группы по m входов каждая, одна группа из т2 двухвходовых элементов И, один блок из m m-входовых сумматоров по модулю два и блок синхронизации, кроме того, в известную схему вводятся два m-разрядные регистра с D-триггерами, один m-разрядный регистр с RS-триггерами, один мультиплексор на две группы по m входов и блок управления.

Для сравнения исключенных из известного устройства и введенных в него аппара- турных затрат приведем аппаратурные затраты функциональных элементов типа регистров, мультиплексоров, блоков синхронизации и управления через их синтез на логических элементах типа И, И-НЕ и ИЛИ- НЕ, причем, синтез введенных функциональных элементов осуществим на двухвходовых логических элементах, представляющих в совокупности максимальные аппаратурные затраты введенных функцио- нальных элементов. Так, например, (1од2т)-входовый элемент ИЛ И-НЕ может быть реализован на Qlog2m -2) двухвходовых элементах ИЛИ и одном двухвходовом элементе ИЛИ-НЕ по схеме, приведенной на фиг.7.

Если на схеме, приведенной на фиг.7, поменять двухвходовые элементы ИЛИ и ИЛИ-НЕ соответственно на двухвходовые элементы И и И-НЕ, то приведенная на фиг.7 схема будет реализовывать Qlog2iriD- входовый элемент И-НЕ.

Докажем, что число двухвходовых элементов ИЛИ на схеме, приведенной на фиг.7, равно Qlog2m -2). Доказательство приведем по методу математической индукции.

Схема (1од2гп)-входового элемента ИЛИ-НЕ, приведенная на фиг,7, составлена так, чтобы ни один из входов ни одного из

двухвходовых элементов ИЛ И и ИЛ И-НЕ не был бы свободным и чтобы ни один из входов двухвходовых элементов ИЛИ и ИЛИ- НЕ не соединялись. Значит, при m 4 нет необходимости применять элементы ИЛИ, так как два входа двухвходового элемента ИЛИ-НЕ будут являться входами Qlog2m)- входового элемента ИЛЙ-НЕ. Для преобразования двухвходового элемента ИЛИ-НЕ в трехвходовый элемент ИЛИ-НЕ один из входов элемента ИЛИ-НЕ присоединим к выходу двухвходового элемента ИЛИ, два входа которого будут являться входами трехвходового элемента ИЛИ-НЕ, третий вход которого подсоединен к другому входу двухвходового элемента ИЛИ-НЕ. Следовательно, при числе log2m 3 число двухвходовых элементов ИЛИ в трехвходоеом элементе ИЛИ-НЕ равно единице.

- Для преобразования трехвходового элемента ИЛИ-НЕ в четырехвходовый необходимо и достаточно один из входов трехвходового элемента ИЛИ-НЕ подсоединить к выходу двухвходового элемента ИЛИ; два входа которого будут являться двумя входами четырехвходового элемента ИЛИ-НЕ, следующих два входа которого подсоединены соответственно к второму и третьему входам трехвходового элемента ИЛИ-НЕ. Следовательно, при log2m{ 4 число двухвходовых элементов ИЛИ в четырехвходо- вом элементе ИЛИ-НЕ равно двум.

Допустим, что k-входовый элемент И.ЛИ-Н.Е содержит к-2 двухвходовых элементов ИЛИ. Тогда для преобразования k-входового элемента ИЛИ-НЕ в (к+1}- входовый элемент ИЛИ-НЕ необходимо и достаточно его подсоединить к дополнительному одному двухвходовому элементу ИЛИ, входы которого будут являться двумя входами (k+1)-вход о во го элемента ИЛИ- НЕ, остальные к-1 входов которого будут являться остальными, неподсоединенными к выходу дополнительного элемента ИЛИ, k-1 входами k-входового элемента ИЛИ-НЕ соответственно. Следовательно, (к+1)-вхо- довый элемент ИЛИ-НЕ, числом равным k - 2 + 1 k - 1. Отсюда (1од2тО-входовый элемент И Л И-НЕ содержит Qlog2m -2) двухвходовых элемента ИЛИ и один двухвходо- вый элемент ИЛИ-НЕ, что и требовалось доказать.

Таким образом, для реализации схемы предлагаемого устройства из известной схемы исключаются в составе трёх т-раз- рядных регистров 3 m инверторов, 12т двухвходовых элементов И-НЕ и 6т трехвходовых элементов И-НЕ, в составе двух мультиплексоров на три группы по m входов - 6т двухвходовых элементов И и 2т трехвходовых элементов ИЛИ, в составе группы из т2 элементов И - т2 двухвходовых элементов И, в составе блока из m m-входовых сумматоров по модулю два - m m-входовые сумматоры по модулю два и в составе блока синхронизации - пять двухвходовых элементов И, один инвертор, два двухвходовые элемента ИЛИ-НЕ и (т+2) D-триггеров, при этом в известную схему вводятся в составе двух m-разрядных регистров с D-триггера- ми 12т трехвходовых элементов И-НЕ, в составе m-разрядного регистра с RS-тригге- рами вводятся 2т двухвходовых элементов И-НЕ, в составе мультиплексора на две группы по m входов вводятся 2т двухвходо- вых элементов И и m двухвходовых элементов ИЛИ, и в составе блока управления вводятся один инвертор, один двухвходо- вый элемент И, один двухвходовый элемент ИЛИ, два двухвходовых элемента ИЛИ-НЕ, один 1од2т -входовый элемент ИЛИ-НЕ, эквивалентный (log2m -2 двухвходовым элементам ИЛИ и одному элементу ИЛИ- НЕ, а также (2 + JlogamD D-триггеров где log2m - число, полученное в результате ок- ругления числа Iog2m до ближайшего большего целого, если число logam есть число не целое.

При подсчете алгебраической суммы числа однотипных логических элементов, исключенных (со знаком минус) и введенных (со знаком плюс) в известное устройство и из него соответственно, при реализации предлагаемого устройства имеем: число исключенных инверторов равно Зт; число исключенных двухвходовых элементов И равно (т2 + 4т + 4); число исключенных двухвходовых элементов И-НЕ равно Ют; число исключенных трехвходовых элементов ИЛ И равно 2т; число исклю- ченных т-входовых сумматоров по модулю два равно т; число исключенных D-тригге- ров равно (m - Jlog2mD; число введенных двухвходовых элементов ИЛИ равно (т + iog2m - 1); число введенных двухвходовых элементов ИЛИ-НЕ равно 1; число введенных трехвходовых элементов И-НЕ равно 6т.

Для дальнейшего сравнения аппаратурных затрат известного и предлагаемого уст- ройств рассматриваем введенные трехвходовые элементы И-НЕ как совокупности из одного двухвходового элемента И и одного двухвходового элемента И-НЕ. Тогда число исключенных инверторов равно Зт; число исключенных двухвходовых элементов И равно т2 + 4т + 4; число исключенных двухвходовых элеентов И-НЕ равно Ют; число исключенных трехвходовых элементов ИЛИ равно 2т; число исключенных

т-входовых сумматоров по модулю два равно т; число исключенных D-триггеров равно (m - log2m ; число введенных двухвходовых элементов ИЛИ равно (m+ log2m -1); число введенных двухвходовых элементов ИЛИ- НЕ равно единице; число введенных двухвходовых элементов И равно 6т и число введенных элементов И-НЕ равно 6т.

Физически, по технологическим параметрам выполнение по одной технологии, аппаратурные затраты на один двухвходовый элемент ИЛИ можно приравнять к аппаратурным затратам на один элемент И, а аппаратурные затраты на один элемент ИЛИ-НЕ можно приравнять к аппаратурным затратам на один двухвходовый элемент И-НЕ. Следовательно, с учетом вышесказанного, при реализации из известного предлагаемого устройства баланс аппаратурных затрат составляет экономию 3m + m+4m+4+10m + 2m + m + m- log2m m2 + 21m - log2m + 4 элементов против увеличения на m + одат - 1 + 1 + 6т + 6т 13т + 1од2т элементов, что в конечном счете дает общую экономию аппаратурных затрат на т2 + 21т - log2tn + 4 - 13т - 1од2т т2 + 8т - 2 log2m + 4 логических элементов.

Так, например, при m 8 экономия аппаратурных затрат составит 126 логических элементов без учета того, что т-входовые сумматоры по модулю два эквивалентны т- 1 двухвходовым сумматорам по модулю два, которые в свою очередь по минимальному составу эквивалентны трем двухвходовым элементам (по одному элементу И, ИЛИ и И-НЕ) каждый.

Таким образом, для реализации предлагаемого устройства умножения над полем GF(2m) необходимо иметь аппаратурных затрат на (т2 + 8 - 2 log2m + 4) логических элементов меньше, чем для реализации известного.

Хотя время выполнения предлагаемым устройством операции обращения элемента поля GF(2m) увеличивается по сравнению со временем выполнения этой операции известным устройством на т-3 тактов его работы, но значительное уменьшение аппаратурных затрат на реализацию предлагаемого устройства может во многих случаях оказаться решающим в выборе предлагаемого устройства для применения его в составе, например, декодирующих устройств умножения над полем GF(2m).

Формул а изо б ре тени я

1. Устройство для умножения элементов конечного поля GF(2m) при m 3, содержащее три регистра; два мультиплексора, группу блоков матричного преобразования,

группу блоков элементов И, блок сумматоров по модулю 2 и блок управления, причем выходы блоков матричного преобразования группы соединены соответственно с первыми входами блоков элементов И труп- пы, выходы которых соединены с соответствующими входами сумматоров по модулю 2 блока, информационные входы первой и второй групп устройства соединены соответственно с информационными входами первой и второй групп первого мультиплексора, выходы первого регистра соединены с соответствующими входами блоков матричного преобразования, первый и второй входы блока управления соединены соответственно с входами обращения и тактовым входом устройства, выход готовности которого соединен с первым выходом блока управления, отличающееся тем, что, с целью сокращения аппаратурных затрат, информационные входы первой группы устройства соединены с соответствующими установочными входами первого и второго регистров, выходы первого мультиплексора соединены соответственно с ус- тановочными входами третьего регистра, выходы которого соединены соответственно с информационными входами первой группы второго мультиплексора, информационные входы второй группы которого со- единены соответственно с выходами второго регистра, а выходы - соответственно с вторыми входами блоков элементов И группы, выходы сумматоров по модулю 2 блока соединены с информационными вхо- дами первого и третьего регистров и выходами результата устройства, вход сброса которого соединен с входами сброса первого и третьего регистров и третьим входом блока управления, первый вход которого со- единен с первым управляющим входом первого мультиплексора, второй управляющий вход которого соединен с вторым входом блока управления, третий выход которого

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

2. Устройство по п.1, отличающее- с я тем, что блок управления содержит элемент ИЛИ, элемент И, три элемента ИЛИ- НЕ, D-триггер, (1од2«п +1)-разрядный двоичный счетчик, (где 1од2гп -ближайшее целое, большее к Iog2m число, если Iog2m - нецелое) и элемент НЕ, вход которого соединен с первым входом блока управления и первым входом первого элемента ИЛИ-НЕ, выход которого соединен с первым входом второго элемента ИЛИ-НЕ, второй вход которого соединен с входом сброса D-тригге- ра, выходом элемента ИЛИ и четвертым выходом блока управления, второй вход которого соединен с тактовым входом D-триг- гера и первым входом элемента И, второй вход которого соединен с выходом D-триг- гера, информационный вход которого соединен с выходом второго элемента ИЛИ-НЕ, вторым входом первого элемента ИЛИ-НЕ и седьмым выходом блока управления, третий вход которого соединен с пер- вым входом элемента ИЛИ и входом установки в нуль 1од2т +1)-разрядного двоичного счетчика, счетный вход которого соединен с выходом элемента И и третьим выходом блока управления, второй выход которого соединен с выходом элемента НЕ, а четвертый и пятый выходы-соответственно с прямым и инверсным выходами младшего разряда (1од2т +1)-разрядного двоичного счетчика, прямые выходы Qlog2mD старших разрядов которого соединены с соответствующими входами третьего элемента ИЛИ-НЕ, выход которого соединен с шестым выходом блока управления и вторым входом элемента ИЛИ.

Л

f- 6

Изобретение относится к специализированным устройствам вычислительной техники и может быть использовано в кодирующих и декодирующих устройствах, работающих с элементами конечных полей полиномов GF(2m) при m S 3, например в устройствах системы компакт-диск. Цель изобретения - сокращение аппаратурных затрат. Устройство умножения элементов конечного поля GF(2m) состоит из первого и второго регистров с D-триггерами, третьего регистра с RS-триггерами, группы блоков матричного преобразования, первого и второго пультиплексоров, группы блоков элементов И, блока сумматоров по модулю два и блока управления, который состоит из элемента НЕ, двух двухвходовых элементов и элемента ИЛИ-НЕ, D-триггера, элемента И, 1од2т +1)-разрядного двоичного счетчика и элемента ИЛИ. 1 з.п. ф-лы, 9 ил. сл с

г

Z

I

гЗ

Г

II I

i

J

1

Фиг.З

Г

1

и

ФигЛ

Фиг. 6

Г

Фиг. 7

а S

г

д

ЩЩ----ЛЩ1П.

I 3 5 bffS

™М.ЛШ

П Г

1728858

...а

Фиг. 8

. П