Устройство для умножения элементов конечных полей Советский патент 1986 года по МПК G06F7/52 

1

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

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

На фиг. 1 приведена блок-схема устройства для умножения элементов конечных полей; на фиг. 2 - функциональная схема блока синхронизации при на фиг. 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 сдвига, состоящий из двух ступенчатьпс тактируемых D-триггеров 30-34, элемент НЕ 35 блок 36 тактуемых элементов задержки, состоящий из элемента И 37 и двух двухступенчатых тактируемых D-триггеров 38 и 39. Блок 14 синхронизации содержит также первьй, второй, третий, четвертьм элементы И 40-43, первый и второй элементы ИЛИ-НЕ 44 и 45.

264452

Каждьш из мультиплексоров 15 и 16 содержит блоки 46-48 из т.элементов И 49 и блок 50 из m элементов ИЛИ 51. Первые входы элементов И 49

. блоков 46-48 являются группами пер- вык, вторых и третьих коммутируемых т-разрядных входов мультиплексоров 15 и 16, объединенные вторые входы элементов И 49 в каждом из блоков

И) являются группой 25 (26) уп-, равляющих входов мультиплексора 15 (16). Выходы элементов ИЛИ 51 являются выходами мультиплексоров 15 и 16. В качестве мультиплексора 17

j,j с двумя коммутируемыми т-разрядными входами можно применить мультиплексор 15 или 16. В этом случае один, из блоков 46-48 можно исключить с заменой элементов ИЛИ 51 на двух2Q входовЕ)1е элементы ИЛИ. Регистр сомножителей 1 (2) содержит та элементов НЕ 52 и тп 1К-триггеров 53, выходы которых объединены и подключены к тактовому входу регистра 1(2) и к

2г, входу 23 устройства, прямые выходы тригеров 53 являются выходами регистра 1(2), входы I и К триггеров подключены к входам регистра непосредственно и через элементы НЕ 52, а входы подключены к шине нулевого потенциала устройства. Выходной регистр 12 имеет такие же состав и схему, что и регистры 1 и 2.

Группа блоков матричного преобразования включает в себя (т-1) пере35 страиваемых блоков 4 матричного преобразования и коммутатор 54, коммутирующий в зависимости от значений коэффициентов ,1, ,..., m-1, порождающего многочлена F(x) х+

30

40

4S

1-П-1

...+f, +-к, сигналы О или 1 на выходы коммутатора 54. Блок 4 матричного преобразования содержит ш-1 двухвходовых элементов И 55 и ш-1 двухвходовых сумматоров 56 по модулю два.

Устройство может работать в двух режимах.

В первом режиме производится умножение элементов конечного поля, вво- 50 димых в устройство по входу первого сомножителя V(V ,. . . ,У„0 и входу второго сомножителя V(V, ,...,V

Z(Z, ,...,.

Во втором режиме производится обращение (по умножению) элемента конечного поля, вводимого в устройство по входу первого сомножителя, при .наличии сигнала Обращение на входе 21, т.е. нахождение элемента , обратного заданному элементу В по умножению .

вв в в 1

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

U,o(.U,o(2U,

,i-i,, , тт cL и, . . . , Ы. и ,

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

,Z , соответствуюцще сумме

1-п | .

Z Ц у (of. и) ,

1 1

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

и,ыи,.

,.

.. . , о. и

В результате этого на выходе второго блока сумматоров получается сумма элементов гл

Ц Z. (1-1

и),

равная величине

ZU(VU)

, -1

Нахождение значения В осуществляется в устройстве путем вычисл - ния (2 -2)-ой степени элемента В,

0 Т

которая равна В , так как В 1 для всех ненулевых элементов конечных полей характеристики два и порядка 2 .Вычисления производятся в соот- ветст вии с соотношением

(в) ... в

Реализация этих вычислений в устройстве осуществляется (т-1)-кратным выполнением операции вида

10

(J+ т)

состоящей в возведении в квадрат величины и умножения Г Z -

J

В

при начальных условиях

„(1) „ „(.11

на (j 1)

В.

в

и текущих условиях

;.j ГВ, при ,3,. -

L1, при ,

При этом операнд В в регистр первого сомножителя, а операнд - в регистр второго сомножителя при каждом новом значении ,2,...,т-1. Это обеспечивает получение на выходах первого блока сумматоров произведения

т-2,

вводится

( (J .,

.) g (.)

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

) (J-ч) (j)

Г7 ril-V/

,„, -Z -Z.

B

(1)

„() „(j)

Z Z

(J) , U J

z-b

.Выполнение (m-l) раз вычислений Z Z J учетом начальных

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

маторов величины В , равной зна чению элемента конечного поля В , обратного заданному.

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

Сигналы тактовой частоты подаются постоянно через вход 23 устройства на регистры 1 и 9 и блок 14 синхронизации. С выхода блока 14 синхронизации инвертированные сигналы тактовой частоты поступают на тактовый вход регистра 12.

В исходном положении и после окончания вычислений по обращению элементов конечного поля триггер 28 блока 14 находится в нулевом состоянии и с его инверсного выхода выдается сигнал Единица, соответствующий Готовности устройства к работе. Сигнал Готовность снимается на m тактов лишь при переводе устройства в режим работы Обращение при поступлении на вход 21 сигнала признака режима работы Обращение. При отсутствии на входе 21 устройства сигнала Обращение и при

наличии на выходе 22 устройства сиг- is дается О

нала Готовность устройство переводится в режим Умножение,

В режиме Умножение триггер 28, триггеры 30-34 и 38 и 39 находятся в нулевом состоянии. Это определяет появление по одному единичному сигналу в каждой из групп выходов 25-27 блока 14 управления.

Такая комбинация сигналов в группах выходов 26-27 блока 14 синхрони- 25 вторые входы сумматоров 56 через

зации обеспечивает прохождение на выход каждого из мультиплексоров 16-17 сигналов по следующим ко1 мути- руемым входам:

для ryльтиплeкcopa 15 - сигналы первого сомножителя по первым коммутируемым входам;

для мультиплексора 16 - сигналы второго сомножителя по вторым коммутируемым входам;

для мультиплексора 17 - сигналы с выходов первого блока 9 многовхо- довых сумматоров по первым тируемым входам,

Сигналы с выходов мультиплексоров о ка 9 через те блоки 7 элементов

15-17 записываются по заднему фронту сигналов тактовой частоты соответственно в регистры 1, 2 и 12. При этом в регистр 1 вводится первый сомножитель V, в регистр 2 - второй сомно-. первые входы элементов И 8 какогожитель и в регистр 12 - результат вычислений в предьщущем такте работы.

Сигналы с выходов регистра 2 второго сомножителя поступают на входы группы 3 блоков 4 матричного преобразования, включенных последовс1тель- но друг за другом. В блоке 4 матричного преобразования производится умножение поступившего на его вход операнда на примитивный элемент с конечного поля. На га ВЕлходах группы 3 блоков 4 образуются сигналы, соот50

либо блока 7 подается, нулевой сигнал с выхода регистра 1, то нули с выхода элементов И 8 данного бло-. ка 7 не изменяют результата суммиро вания на выходе блока 9 сумматоров, который равняется произведению первого V и второго и сомножителей

л

55

Z(Z,..,,ZJ V. (oi U)VU

iСигналы с выхода сумматоров 11 поступают через открытые первые ком

ветствующие следуюпщм значениям элементов поля:

U,ci и,о1 и,

т-1 , , 0(. и

Схема блока 4 матричного преобразования является перестраиваемой в зависимости от вида порождающего многочлена F(x), Перестройка блока 4 обеспечивается с коммутатором 54. С j-ro выхода коммутатора 54 вьщает- ся 1, если соответствующий ему по порядку коэффициент f . заданного многочлена F(x) равен единице, и выдается О

если f,0. Вследствие

этого сигналы с тех i-x входов блока 4, ,,.., т-1, для которых 5 проходят через вход и выход сумматора 56 на (1+1)-й выход блока 4 без изменений, а сигналы с входов, для которых f.1, проходят на (1+1)-й выход блока 4 в виде суммы их с сигналом на т-м входе блока 4. Сигнал с га-го входа поступает на.

первые входы и выходы тех элементов И 55, на вторые входы которьгх поступает единица из коммутатора 54. Сигнал с т-го входа блока 4 всегда

подается также на выход первого разряда этого блока. Такая схема блока 4 матричного преобразования обеспечивает умножения входного операнда на примитивный элемент oi конечкого поля, задаваемого многочленом F(x).

Сигналы с выходов группы 3 блоков 4 матричного преобразования поступают на входы сумматоров 11 блоИ 8 группы 5, в которьгх на первые входы элементов И 8 подается единичный сигнал с выхода соответствующего разряда регистра 1. Если же на

либо блока 7 подается, нулевой сигнал с выхода регистра 1, то нули с выхода элементов И 8 данного бло-. ка 7 не изменяют результата суммирования на выходе блока 9 сумматоров, который равняется произведению первого V и второго и сомножителей

л

Z(Z,..,,ZJ V. (oi U)VU

iСигналы с выхода сумматоров 11 поступают через открытые первые коммутируемые входы и выходы мультиплексора 17 на входы выходного регистра, в который они записываются по заднему фронту сигнала тактовой частоты следующего такта и далее подаются на выход 20 результата устройства. Кроме того, сигналы с выхода сумматоров 11 поступают такж на первые входы элементов И 8 блоков 7.

Сигналы с выходов группы 3 блоков 4 матричного преобразования поступают также на входы.блока 10 сумматоров через те блоки 7 элементов, которым соответствует .единичньш сигнал на первых входах элементов И В результате на выходах блока 10 сумматоров образуется произведение, равное

t-n

ZU Ц Z of U)(VU)

i : 1

Коммутируемым входом мультиплексоры 16 и 17 соединяются с выходами своих мультип 1ексоров в соответстви с временной диаграммой (фиг. 6) только в режиме Обращение и остаются всегда отключенными от выходов мультиплексоров при выполнении устройством операции умножения.

Перевод устройства в режим работы Обращение задается подачей единичного сигнала на вход 21 устройства. Этот сигнал поступает на установочный вход S триггера 28 .блока 14 управления и переводит триггер в единичное состояние, снимая тем самым сигнал Готовность устройства к ряботе на выходе 22. Единичный сигнал с триггера 28 поступает на вход регистра 29. В результате этого и под воздействием сигналов тактовой частоты триггеры 30, 31-34, 38, 39 регистра 29 и блока 36 тактируемых элементов задержки начинаю последовательно переключаться в единичное состояние. Совпадение единичных сигналов на входах элементов И 42 и 43 в группах выходов 25 и 26 а также 27 происходит изменение состояний отдельных выходов с нулевого на единичный и обратно. При этом в единичном состоянии всегда будет не более одного выхода из группы.

Сигналы в группах выходов 25-27, поступающие на управляющие входы мультиплексоров .15-17, обеспечивают прохождение сигналов с одного из

5

0

5

0

5

0

5

0

5

трех (.для мультиплексоров 15 и 16) или двух (для мультиплексора 17) коммутируемых т-разрядных входов на выход мультиплексоров в соответствии с временной диаграммой (фиг. 6). При этом в мультиплексоре 15 в течение первого такта цикла обращения производится подключение на выходы первых входов, по которым с выхода 18 уст- poficTBa поступает обращаемый элемент В. Б течение последующих т-З тактов на выход мультиплексора 15 коммутируются его третьи входы, подключенные к выходу регистра 1 первого сомножителя. В результате с выхода регистра 1 в течение первых т-2 тактов цикла обращения на входы группы 5 блоков 7 элементов И 8 будет выдаваться элемент В. На время (m-l)-ro такта через мультиплексор 15 разрешается прохождение в регистр 1 сигналов с датчика 13 единицы, соответствующих элементу конечного поля единица (комбинация двоичных сигналов: 1, О, ..., Ос одной 1 в младшем разряде и т-1 О в остальных разрядах).

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

Через мультиплексор 17 во время первых (тп-2) тактов цикла обращения запрещается выдача сигналов с выходов блока 9 и 10, так как ни на одном из выходов 27 в течение всего указанного времени не будет единичного сигнала, а на (т-1)-м также на мультиплексор 17 подается управляющий сигнал, разрешающий прохождение на выходной регистр 12 сигналов с выхода блока 10 сумматоров, которые будут соответствовать элементу

.

в начале т-го такта цикла обращения единичный сигнал с выхода триггера 39 блока 36 поступает на установочные входы триггера 28 и всех триггеров регистра 29 и переводит их в нулевое состояние. В результате этого на .выходе 22 появляется сигнал Готовность устройства к работе

9

и производится переключение мультиплексоров 15-17 в исходное положение соответствующее режиму Умножение, Введение в состав устройства для умножения элементов конечных полей дополнительных указанных блоков расширяет функциональные возможности устройства умножения путем реализации операции обращения элементов конечных полей. Это 1юзволяет строить универсальное вычислительное устройство, обеспечивающее выполнение всех возможных вычислительных операций (умножения, обращения и сложения), необходимость в которых возникает, например, при кодировании и декодировании кодов, построенных надконеч- ными полями характеристики два, без применения дополнительного сложного оборудования для обращения элементов конечных полей.

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

1. Устройство для умножения элементов конечных полей, содержащее регистры первого и второго сомнояште- лей, тактовые входы которых подключены к тактовому входу устройства, группу блоков матричного преобразования, первый блок сумматоров, первую группу jm .блоков элементов И, первые входы m блоков элементов И первой группы подключены к соответствующим выходам регистра первого сомножителя, выход i-ro (,2,...,m) блока элементов И первой группы подключен к i-му входу первого блока сумматоров, выход j-ro блока матричного преобразования (,2,..,т-1) соединен с входом (j+1)-ro блока матричного преобразования и с вторым входом (l-H)-ro блока элементов И первой группы, отличающееся тем, что, с целью расширения функциональных возможностей устройст ва за счет реализации операции обращения элементов конечных полей, оно дополнительно содержит блок синхро1Ш зации, вход здания режима которого подключен к входу признака режима работы устройства, тактовый вход блока синхронизации соединен с тактовым входом устройства, первый выход блока синхронизации подключен к выходу признака готовности устройства, второй блок из m сумматоров, вторую группу из га блоков элементов И, первые входы i-ro блока (, 2,

2644510

,,i, m) элементов И второй группы подключены i-му выходу первого блока сумматоров, выход j-ro блока матричного преобразования соединен с вторым входом (l-i-l)-ro блока элементов И второй группы, выходной регистр тактовый вход которого подключен к . второму выходу блока синхронизации, три m разрядных мультиплексора,

«О группы управляющих входов первого, второго, третьего мультиплексоров подключены к выходам соответственно первой, второй и третьей групп блока синхронизации, первая группа инфор 5 мационных входов первого мультиплексора соединена с первой группой информационных входов второго мультиплексора и подключена к группе входов первого сомножителя устройства, вто-20 рая группа информационн{ 1х входов первого мультиплексора подключена к выходам регистра первого сомножителя, информационные входы которого подключены к выходам первого мультиплексо25 ра, третья группа информационных входов которого подключена к шине единичного потенциала устройства, информационные входы регистра второго сомножителя подключены к выходам

30 второго мультиплексора,вторая группа информационных входов которого подключена к группе входов второго сомножителя устройства, третья группа И15формационных входов второго мультиj,; плексора подключена к выходам второго блока сумматоров и к первой группе информационных входов третьего мульти- плекс;ора, которого подключены к информационным входам выходного ре.40 гистра, выход которого подключен к выходу результата устройства, вы- ходь элементов И j-ro блока второй группы подключены к соответствующим i-M входам второго блока сумматоров,

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

2„ Устройство по П.1, о т л.и - чающееся тем, что блок синхронизации содержит триггер, (га-1)- 55 разрядный регистр сдвига, блок тактирующих элементов задержки, четыре элемента И, два элемента ИЛИ-НЕ, элемент НЕ, вход которого подключен

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

0

5

0

5

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

3,Устройство по П.1, отличающееся тем, что блок матричного преобразования содержит (т-1) элементов И, (т-1) сумматоров по модулю два и коммутатор, первый информационный вход которого подключены к шине единичного потенциала, второй информационный вход - к шине нулевого потенциала, а управляющий вход - к входу задания порождающего полинома поля, первые входы j-x сумматоров по модулю два подключены соответственно к входам блока, вторые входы j-x сумматоров по модулю два подключены к выходам j-x элементов И, первые входы которых подключены к соответствующему j-му информационному выходу коммутатора, вторые входы элементов И подключены к т-му входу и к первому выходу блока, остальные (т-1) выходы блока образуют соответ ственно выходы (т-1) сумматоров по модулю два.

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

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

0

ч

oi и

Фиг. 5

Составитель В. Смирнов Редактор Т. Кугрьшева Техред В.Кадар

Заказ 2134/48 Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

.6

Корректор С.Шекмар

Изобретение относится к области вычислительной техники. Цель изобретения - расширение функциональных возможностей за счет реализации вычислительной операции обращения элементов конечных полей. Для этого устройство содержит дополнительно блок синхронизации, блок m сумматоров, группу ш элементов И, т-разряд- ные мультиплексоры, блоки трактируе- мых элементов задержки и матричного преобразования. Все блоки и-элементы соединены в соответствии с решаемой задачей, при этом блок синхронизации, блок трактуемых элементов задержки и блок матричного преобразования имеют свою схемную реализацию. Изобретение может быть применено при построении специализированных вычислителей для кодирования и декодирования кодов, корректирующих ошибки. 3 з.п. ф-лы, 6 ил. i (Л го ю Oi 4 4 СЛ