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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (19) (11) (я)5 G 06 F 7/49, 7/52

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4798969/24 (22) 05.03.90 (46) 23.04.92. Бюл. ¹ 15 (71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72) И.И.Ковалив (53) 681.325 (088,8) (56) Блок Э.Л., Зяблов В.В. Обобщенные каскадные коды (Алгебраическая теория и сложность реализации) вып. 5.— М.: Связь, 1976, с. 106, рис. 3.37.

Авторское свидетельство СССР

¹ 1226445, кл, G 06 F 7/52, 1984. (54) УСТРОЙ СТВ О ДЛ Я УМНОЖЕНИЯ

ЭЛЕМЕНТОВ КОНЕЧНОГО ПОЛЯ GF(2 )

ПРИ т >3 (57) Изобретение относится к специализированным устройствам вычислительной техИзобретение относится к специализированным устройствам вычислительной техники и может использоваться в кодирующих и декодирующих устройствах, работающих с элементами конечных полей полиномов

GF(2 ) при m 3, например в устройствах системы "компакт-диск".

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

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

Известно устройство для деления элементов поля Галуа, содержащее первый и второй сдвиговые регистры, один элемент

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

1728858

10 умножителя соответственно, а тактовые входы объединены и подсоединены к выходу элемента И, первый вход которого является тактовым входом устройства, а второй вход подсоединен к выходу элемента ИЛИ—

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

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

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

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

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

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

"Занят" устройства.

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

ИЛИ вЂ” НЕ, О-триггер, ()logzm(+1)-разрядный двоичный счетчик (где )logzm(— ближайшее целое большее к logzm число, если logzm— нецелое) и элемент НЕ, вход которого соединен с первым входом блока управления и первым входом первого элемента ИЛИ вЂ” НЕ, выход которого соединен с первым входом второго элемента ИЛИ вЂ” НЕ, второй вход которого соединен с входом сброса D-триггера, выходом элемента ИЛИ и четвертым выходом блока управления, второй вход которого соединен с тактовым входом D"òðèãгера и первым входом элемента И, второй вход которого соединен с выходом D-триггера, информационный вход которого соединен с выходом второго элемента

ИЛИ вЂ” НЕ, вторым входом первого элемента

ИЛИ вЂ” НЕ и седьмым выходом блока управления, третий вход которого соединен с первым входом элемента ИЛИ и входом установки в нуль plogzm(+1)-разрядного двоичного счетчика, счетный вход которого соединен с выходом элемента И и третьим выходом блока управления, второй выход которого соединен с выходом элемента НЕ, а четвертый и пятый выходы — соответственно с прямым и инверсным выходами младшее го ра з ряда () I ogzm(+1)-разрядного двоичного счетчика, прямые выходы

PlogzmP старших разрядов которого соединены с соответствующими входами третьего элемента ИЛИ вЂ” НЕ, выход которого соединен с шестым выходом блока управления и вторым входом элемента ИЛИ.

На фиг.1 изображена структурная блоксхема устройства умножения над полем

G F(2 ); на фиг.2 — структурная схема регистра с 0-триггерами; на фиг.3 — структурная схема регистра с RS-триггерами; на фиг.4— структурная схема мультиплексора; на фиг.5 — структурная схема блока управле1728858 6 второй группы информационных входов первого мультиплексора 4> являются одноименными m входами второй группы информационных входов устройства, m выходов первого мультиплексора 4> подсоединены к одноименным m установочным входам второго регистра 1z, m выходов которого подсоединены к одноименным m входам первой группы информационных входов второго мультиплексора 42, m входов второй группы информационных входов которого подсоединены к одноименным m выходам регистра 2, а m выходов второго мультиплексора 4z подсоединены к одноименным m входам второй группы входов группы 5 блоков элементов И, причем m выходов блока 6 сумматоров по модулю два объединены с одноименными m информационными входами первого и второго регистров 11 и 12 и являются одноименными в информационными выходами устройства, 40

55 ния; на фиг.6- структурная схема двоичного счетчика блока управления; на фиг.7— структурная схема jlogzm(-входового элемента ИЛИ-НЕ блока управления; на фиг.8 — временные диаграммы работы блока уп- 5 равления, на фиг.9 — временные диаграммы работы устройства умножения над полем

GF(2 ) при выполнении им операции обращения элемента поля при m 3.

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

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

7 управления, причем m установочных входов первого регистра 1> являются одно- 20 именными m входами первой группы информационных входов устройства и объединены с одноименными m входами первой группы информационных входов первого мультиплексора 4> и с m информа- 25 ционными входами регистра 2, m прямых выходов первого регистра 1> подсоединены к одноименным m входам группы 3 блоков матричного преобразования, m выходов которого подсоединены к соответствующим 30 г

m входов первой группы входов группы 5 блоков элементов И, m выходов которой подсоединены к соответствующим m входам блока 6 сумматоров по модулю два, m выходов которого являются одноименным 35

m информационными выходами устройства и подсоединены к одноименным объединенным m информационным входам первого и второго регистров 11 и 1г, при этом m входов при этом первый и второй входы блока 7 управления, являющиеся соответственно входами "Обращение" и "Исходное состояние" устройства, подсоединены к первому управляющему входу первого мультиплексора 41 и к объединенным входам сброса в нулевое состояние первого и второго регистров 1> и 1z, а третий вх0д блока 7 управления является тактовым входом устройства, при этом с первого по пятый выходы блока

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

41, к объединенным тактовым входам первого и второго регистров 11 и 1z, к входу сброса в нулевое состояние регистра 2, к первому и к второму управляющим входам второго мультиплексора 4z соответственно; а шестой и седьмой выходы блока 7 управления— являются выходами "Готов " и "Занят" устройства. Регистр 1> (1z) (фиг.2) состоит из m

D-триггеров 8, причем входы установки в единичное состояние и информационные входы всех m D-триггеров 8 являются одноименными .с порядковыми номерами Dтриггеров 8 m установочными и и; информационными входами регистра 11 1z) соответственно, прямые выходы D-триггеров 8 являются одноименными с порядковыми номерами О-триггеров 8 m выходами регистра 11(1z), при этом объединенные тактовые входы всех m 0-триггеров 8 являются тактовым входом регистра 11(1z), а объединенные входы сброса в нулевое состояние всех m D-триггеров являются входом сброса в нулевое состояние регистра 1> (12).

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

RS-триггеров 9 являются входом сброса в нулевое состояние регистра 2.

Мультиплексор 41 (42) (фиг.4) состоит из

2m двухвходовых элементов И 10 и m двухвходовых элементов ИЛИ 11, причем первые входы первых по порядку счета m двухвходовых элементов И 10 являются одноименными с порядковыми номерами двухвходовых элементов И 10 m входами первой группы информационных входов мультиплексора 41(4z), первые входы следующих по порядку счета m двухвходовых элементов И 10 с порядковыми номерами от (m + 1) по 2m являются m входами второй группы информационных входов мультиплексора 41 (4z) номерами Hà m меньше порядковых номеров соответствующего двухвходового элемента И 10, при этом вторые объединенные входы первых по поряд1728858 ку счета m двухвходовых элементов И 10 объединены и являются первым управляющим входом мультиплексора 4> (4z), а вторые объединенные входы следующих по порядку счета m двухвходовых элементов И

10 с порядковыми номерами от (m + 1) по

2m включительно являются вторым управляющим входом мультиплексора 41 (42), причем выходы первых по порядку счета m двухвходовых элементов И 10 подсоединены к первым входам всех m одноименных двухвходовых элементов ИЛИ 11, вторые входы которых подсоединены к выходам следующих по порядку счета m двухвходовых элементов И 10 с порядковыми номерами на m больше порядковых номеров двухвходовых элементов ИЛИ 11 соответственно, а выходы являются одноименными m выходами мультиплексора 4> (4 ), Блок 7 управления (фиг.5) состоит из инвертора 12, первого и второго двухвходовых элементов ИЛИ-НЕ 131 и 132, D-триггера 14, элемента И 15, ()logjam(+1)-разрядного двоичного счетчика 16, где символом )!оцге( обозначено натуральное число, полученное при округлении числа logjam до ближайшего целого, если число !о9гт — нецелое, ()logzmpвходового элемента ИЛИ вЂ” НЕ 17 и элемента

18 ИЛИ, причем, вход инвертора 12 является первым входом блока 7 управления и объединен с первым входом первого двухвходового элемента ИЛИ вЂ” НЕ 13, выход которого подсоединен к первому входу второго двухвходового элемента ИЛИ вЂ” НЕ

13, первый вход элемента ИЛИ 18 является вторым входом блока 7 управления и объединен с входом установки в исходное состоя н ие ()logjam(+1)-разрядного двоичного счетчика 16, прямой вход D-триггера 14 подсоединен к первому входу элемента И 15, а тактовый вход D-триггера 14 объединен с вторым входом элемента И 15 и является третьим входом блока 7 управления, при этом выход инвертора 12 является первым выходом блока 7 управления, выход элемента И 15 объединен со счетным входом ()!о9гт(+1)-разрядного двоичного счетчика

16 и является вторым выходом блока 7 управления, выход элемента ИЛИ 18 объединен с вторым входом двухвходового элемента ИЛИ вЂ” НЕ 13г, с входом сброса в нулевое состояние D-триггера 14 и является третьим выходом блока 7 управления, причем инверсный и прямой выходы самого младшего разряда ()logjam(+1)-разрядного двоичного счетчика 16 являются четвертым и пятым выходами блока 7 управления соответственно, выход Plogzm()-входового элемента ИЛИ-НЕ 17 объединен с вторым входом элемента ИЛИ 18 и является шестым

55 выходом блока 7 управления, выход второго двухвходового элемента ИЛИ-НЕ 13 является седьмым выходом блока 7 управления и объединен с вторым входом первого двухвходового элемента ИЛИ вЂ” НЕ 13> и с информационным входом D-триггера 14, при этом прямые выходы )!092т(старших разрядов ()!оцупа(старших разрядов ()logjam(+1)-.разрядного двоичного счетчика 16 подсоединены соответственно к входам ()log2mP-входового элемента ИЛИ—

HE 17.

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

)logjam(обозначено натуральное число, получаемое в результате округления до ближайшего целого числа logjam, если оно не целое, причем тактовый вход первого D-триггера

19> памяти является счетным входом двоичного счетчика 16, инверсный выход каждого из 0-триггеров 19 подсоединен к собственному информационному входу, прямой выход предыдущего D-триггера 19ь где = 1, 2, ..., )logjam(, подсоединен к тактовому входу последующего D-триггера 19н-, при этом инверсный и прямой выходы первого Dтриггера 19> являются первым и вторым выходами двоичного счетчика 16, а прямые выходы остальных )logjam(D-триггеров 19!, где j = 2, 3, ..., )logjam(+1, являются остальными )logjam(выходами двоичного счетчика 16 с порядковыми номерами начиная с третьего, причем вход сброса в нулевое состояние первого D-триггера 19! является входом установки в исходное состояние двоичного счетчика 16 и подсоединен к входам установки в единичное состояние тех D-триггеров 191, где j = 2, 3, .„, )logjam(+1, для которых соответствующие (!-1)-е разряды двоичного представления числа (2 (— m + 2) равны единице; и к входам сброса в нулевое состояние тех D-триггеров 19>, для которых соответствующие азояды двоичного представления числа (2 — m + 2) равны нулю, ()logjam()-входовый элемент ИЛИ вЂ” НЕ 17 (фиг.7) блока 7 управления состоит из двухвходового элемента ИЛИ вЂ” НЕ 20 и из

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

Plogzm()-входового элемента ИЛИ вЂ” HE 17 при m = 3 или 4 либо подсоединен к выходу первого двухвходового элемента 211 при

m > 4, при этом первые входы ()logjam(— 2) 1728858

10 двухвходовых элементов ИЛИ 21 являются последующими входами ()logjam()-входового элемента ИЛИ вЂ” НЕ 17 с порядковыми номерами на единицу больше порядковых номеров двухвходовых элементов ИЛИ-НЕ 17, 5 вторые входы предыдущих двухвходовых элементов ИЛИ 21ь где l = 1, 2, ..., )logzm(—

3, подсоединены к выходам следующих двухвходовых элементов ИЛИ 21 +>, при этом второй выход последнего двухвходово- 10 го элемента 21 )log2m (-2 ИЛИ является последним, )log2m(, sxopoMglogzm(l-входового элемента ИЛИ вЂ” НЕ 17.

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

7 управления на входах и выходах блока 7 управления и его элементов.

Буквенные обозначения временных ди- 20 аграмм работы блока 7 управления устройства умножения над полем GF(2 ) (фиг.8) соответствуют изменениям во времени сигналам на следующих входах и выходах блока 7 управления и его элементов (фиг.5): а — 25 первый, вход блока 7 управления; б — первый выход блока 7 управления; в — выход второго двухвходового элемента ИЛИ вЂ” НЕ 132 блока 6 управления (седьмой выход блока 7 управления); г — второй вход блока 7 управ- 30 ления; д — выход двухвходового элемента

ИЛИ 18 (третий выход блока 7 управления); е — прямой выход элемента 14 памяти блока

7 управления; ж — третий вход блока 7 управления; з — выход двухвходового элемен- 35 та И 15 (второй выход блока 7 управления); и — четвертый выход блока 7 управления; к . — пятый выход блока 7управления; л — входы

)logjam(-входо ваго элемента ИЛ И вЂ” Н Е 17 блока 7 управления; м — выход ()logjam()-вхо- .40 довс го элемента ИЛИ вЂ” Н Е 17 (шестой выход блока 7 управления).

Временные диаграммы работы устройства над полем GF(2m) при выполнении им операции обращения элемента поля при m 45

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

Буквенные обозначения временных диаграмм работы устройства умножения над . полем GF(2 ) при выполнении им операции 55 обращения элемента поля (фиг.9) соответствует изменениям во времени сигналам на следующих входах и выходах устройства умножения над полем GF(2"), его блоке 7 управления и функциональных элементах (фиг.1): а — первая группа информационных входов устройства; б — вход "Обращение" устройства; в — вход "Исходное состояние" устройства; г — тактовый вход устройства; д — первый выход блока 7 управления; е— второй выход блока 7 управления;ж — третий выход блока 7 управления; з — четвертый выход блока 7 управления; и — пятый выход блока 7 управления; к- шестой выход блока

7 управления (выход "Готов" устройства); л — седьмой выход блока 7 управления (выход

"Занят" устройства); м- группа информационныхых выходов устройства.

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

"положительной логики". Таким образом, будем считать, что высокий уровень сигнала на входе или выходе функционального weмента или устройства определяет истинное значение величины приписываемой этому входу или выходу, в нулевой алгебре, а низкий уровень — ложное.

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

Прежде чем приступить к описанию принципа действия устройства умножения над полем GF(2 ) (фиг.1), опишем сначала принцип действия -()log2m()-входового элемента ИЛИ вЂ” НЕ 17 и двоичного счетчика 16 блока 7 управления устройства умножения над полем GF(2 ) (фиг.7 и 6 соответственно), опишем принцип действия блока 7управления устройства умножения над полем G F(2") (фиг.5), а также принцип действия мультиплексора 41(42), регистра 2 с RS-триггерами и регистра 1> (1г) с 0-триггерами устройства умножения над полем GF(2 ) (фиг.4, 3 и 2 соответственно).

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

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

Если на всех входах()logzmP-входового элемента ИЛИ вЂ” НЕ 17 будут сформированы сигналы низких уровней, то на выходах всех его элементов 21 ИЛИ формируются сигналы низких уровней, а значит на оба входа двухвходового элемента ИЛИ-НЕ 20 под1728858

5

35

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

ИЛИ вЂ” НЕ 17 будет сформирован сигнал высокого уровня, то на его выходе сформируется сигнал низкого уровня. ()!оцга(+1)-разрядный двоичный счетчик 16 блока 7 управления устройства умножения над полем GF(2 ) (фиг.6) работает следующим образом.

B исходном состоянии двоичного счетчика 16 его первый 0-триггер 191 сброшен в нулевое состояние, а состояния остальных

0-триггеров 19 соответствуют двоичному представлению числа 2 — m + 2. При

)log2m( этом на оба входа двоичного счетчика 16 подаются сигналы низких уровней. Если счетчик 16 находится не в исходном состоянии, то при подаче на вход установки в исходное состояние двоичного счетчика 16 импульсного сигнала высокого уровня первый D-триггер 191 сбросится в нулевое состояние, а остальные D-триггеры 19i, где

i = 2, 3, „„)logjam(+ 1, установятся в состояния, соответствующие (i — 1)-м разрядам двоичного представления натурального числа

2)log2m(гп + 2

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

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

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

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

При этом на первом и четвертом выходах блока 7 управления сформированы сигналы высоких уровней каксигналы на выходе инвертора 12, на вход которого подан сигнал низкого уровня, и на инверсном выходе сброшенного в нуль первого D-триггера 191 двоичного счетчика 16 (фиг.5 и 6), а на остальных выходах блока 7 управления сформированы сигналы низких уровней: на втором выходе — как на выходе двухвходового элемента И 15, на первый вход которого подан сигнал низкого уровня; на шестом выходе, как на выходе Plog2mP-входового элемента ИЛИ вЂ” НЕ 17, не на всех входах которого сформированы сигналы низких уровней, ибо число 2) (— п1 + 2 не равно нулю при m > 2; на третьем выходе, как на выходе элемента И 18, на все входы которого подаются сигналы низких уровней; на пятом выходе, как на прямом выходе сброшенного в нуль первого D-триггера 191 ()logjam(+1)-разрядного счетчика 16 (фиг.5 и

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

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

13г, а значит и на информационном входе элемента 14 памяти, сформирован сигнал низкого уровня.

При подаче сигнала высокого уровня на первый вход блока 7 управления на выходе первого элемента ИЛИ вЂ” НЕ 131 и на первом выходе блока 7 управления формируются сигналы низких уровней, а на выходе второго элемента ИЛИ вЂ” НЕ 13г и, значит, на информационном входе D-триггера 14 и седьмом выходе блока 7 управления формируется сигнал высокого уровня, По переднему фронту очередного тактового импульса, поступающего на третий вход блока 7 управления, а значит и на тактовый вход D-триггера 14 и второй вход элемента И 15, D-триггер 14 установится в единицу, на первом входе элемента И 15 сформируется сигнал высокого уровня, и тактовые импульсы начнут формироваться на выходе элемента

И 15, а значит и на втором выходе блока 7 управления и на счетном входе ()logjam(+1)разрядного двоичного счетчика 16 (фиг.5 и

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

13

1728858

14 ()log2mp-входового элемента ИЛИ-НЕ 17 на его выходе формируется сигнал высокого уровня, который поступает на шестой выход блока 7 управления и на второй вход элемента ИЛИ 18, на выходе которого тоже 5 формируется сигнал высокого уровня, который поступает на третий выход блока 7 управления, на вход сброса в нулевое состояние элемента памяти 14 и на второй вход второго элемента ИЛИ-НЕ 132. При 10 этом на выходе второго элемента ИЛИ-НЕ

132, а значит на седьмом выходе блока 7 управления и на информационном входе Dтриггера, формируются сигналы низкого уровня, на первом входе элемента И 15 фор- 15 мируется сигнал низкого уровня и, следовательно, на выходе элемента И 15, а значит на счетном входе двоичного счетчика и на втором выходе блока 7 управления, формируется сигнал низкого уровня (фиг.5 и 8), а 20 состояние блока 7 управления может измениться только при поступлении сигнала высокого уровня на его первый или второй выходы.

При подаче сигнала высокого уровня 25 на второй вход блока 7 управления при сигнале низкого уровня на его первом входе Ц(од2гп(+1)-разрядный двоичный счетчик

16 устанавливается в свое исходное состоя- . ние и на выходе двухвходового элемента 30

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

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

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

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

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

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

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

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

В исходном состоянии регистра 2 все

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

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

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

В исходном состоянии регистра 1 его

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

1728858

5

25

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

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

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

CF(2 ) работает следующим образом.

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

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

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

При выполнении устройством .операции умножения двух элементов поля

GF(2 ) на входы первой и второй групп информационных входов устройства умножения над полем GF(2 ) подаются сигналы, соответствующие коэффициентам первого и второго полиномов-сомножителей соответственно. При этом на выходах первого и второго регистров 11 и 12 (фиг.1 и 2) формируются сигналы, равные сигналам на установочных входах, а значит и на входах первой и второй групп информационных входов устройства соответственно, Сигналы с выходов первого регистра 1> с D-триггерами, преобразуясь в группе 3 блоков матричного преобразования, подаются на входы первой группы информационных входов группы 5 блоков элементов И, на входы второй группы информационных входов которой поступают через второй мультиплексор

4г сигналы с выходов второго регистра 1г.

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

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

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

При этом на выходах обоих регистров 1> и

1 и на выходах регистра 2 формируются сигналы, соответствующие коэффициентам обращаемого полинома, на выходе "Занят" устройства формируется сигнал высокого

1728858

20

25 мого полинома

35

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

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

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

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

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

m — 2 пар тактовых сигналов.

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

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

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

При m< Зчислоk1=2m — 4=2(тактовых импульсов) и С1 = (В B) = В = В = В

При mz=4k2=2 4-,4=4и С2=(С1 B) = (В6, В)2 В14 У ">

1728858

При вз = 5 ka = 2 5 — 4 = 6 и. Сз = „, (Сг B)ã = (В 14 B) = Bçî = ф;с Bõ -.

Пусть при пц, где l6 N, 6, С! = В-",гпричем, ki = 2 пц — 4.

Определим значение С!+ при 5

mi+1 = ml+1.

Вычислим:

ki+1= 2 mi+) — 4=2(mi+1) — 4=

=2 пц + 2 — 4 = 2 пц — 4 + 2 = ki + 2.

Тогда „«„„, „, „10

С+1 =(С, . В) =(B - w) = В - авала что и требовалось доказать. Другими словами,прив>2,m N,Cm=B

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

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

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

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

Кроме того, по импульсному сигналу, 45 поступающему на вход "Исходное состояние" устройства, его оба регистра 11 и 1г сбросятся в нулевое состояние, после чего возможно выполнение очередной операции умножения или обращения над полем 50

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

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

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

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

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

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

Аппаратурные затраты предлагаемого устройства составляют три m-разрядные регистра, из которых два с D-триггерами и один

c RS-триггерами, два мультиплексора на две группы по m информационных входов каждый, одну группу блоков матричного преобразования, одну группу из m элементов И, один г блок из m m-входовых сумматоров по модулю два и блок управления, содержащий один инвертор, один двухвходовый элемент И, один ()logjam()-входовый элемент ИЛИ вЂ” НЕ, один двухвходовый элемент ИЛИ, два элемента

ИЛИ вЂ” НЕ и ()!осгт(+2) D-триггеров, где сим- . волом )logjam(обозначено натуральное число, полученное в результате округления до ближайшего большего целого числа logjam, если logjam число не целое.

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

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

IK-триггер содержит четыре двухвходовых

1.728858

22 дятся два m-разрядные регистра с

0-триггерами, один m-разрядный регистр с

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

Для сравнения исключенных из известного устройства и введенных в него аппаратурных затрат приведем аппаратурные затраты функциональных элементов типа регистров, мультиплексоров, блоков синхронизации и управления через их синтез на логическихэлементахтипа И, И вЂ” НЕ и ИЛИ—

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

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

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

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

Схема ()logjam()-входового элемента

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

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

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

Для реализации схемы предлагаемого устройства из известного исключаются три

m-разрядн ые регистра с К-триггерами, два мультиплексора на три группы по m входов 20 каждая, одна группа из m двухвходовых элементов И, один блок из m m-входовых сумматоров по модулю два и блок синхронизации, кроме того, в известную схему вводвухвходовых элементов ИЛИ и ИЛИ вЂ” НЕ не был бы свободным и чтобы ни один из входов двухвходовых элементов ИЛИ и ИЛИ—

НЕ не соединялись. Значит, при m 4 нет необходимости применять элементы ИЛИ, так как два входа двухвходового элемента

ИЛИ вЂ” НЕ будут являться входами Piog>m()входового элемента ИЛИ-НЕ. Для преобразования двухвходового элемента ИЛИ вЂ” НЕ в трехвходовый элемент ИЛИ вЂ” HE один из входов элемента ИЛИ-НЕ присоединим к выходу двухвходового элемента ИЛИ, два входа которого будут являться входами трехвходового элемента ИЛИ-НЕ, третий вход которого подсоединен к другому входу двухвходового элемента ИЛИ-HE. Следовательно, при v cne )logjam(= 3 число двухвходовых элементов ИЛИ в трехвходовом элементе ИЛИ вЂ” НЕ равно единице.

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

Следовательно, при )logjam(= 4 число двухвходовых элементов ИЛИ в четырехвходовом элементе ИЛИ вЂ” НЕ равно двум.

Допустим, что k-входовый элемент

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

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

2 + 1 = k — 1. Отсюда ()logjam()-входовый элемент ИЛИ-Н Е содержит Qlogzm(— 2) двухвходовых элемента ИЛИ и один двухвходовый элемент ИЛИ-НЕ, что и требовалось доказать.

Таким образом, для реализации схемы предлагаемого устройства из известной схемы исключаются в составе трех m-разрядных регистров 3 mинверторов,,12m двухвходовых элементов И вЂ” НЕ и 6m трехвходовых элементов И-НЕ, в составе двух мультиплексоров на три группы по m входов — 6m двухвходовых элементов И и 2m трех23

1728858

24 входовых элементов ИЛИ, в составе группы из m элементов И вЂ” m двухвходовых элег 2 ментов И, в составе блока из m m-входовых сумматоров по модулю два — m m-входовые сумматоры по модулю два и в составе блока 5 синхронизации — пять двухвходовых элементов И, один инвертор, два двухвходовые элемента ИЛИ вЂ” НЕ и (m+2) D-триггеров, при этом в известную схему вводятся в составе двух m-разрядных регистров с D-триггера- 10 ми 12m трехвходовых элементов И вЂ” НЕ, в составе m-разрядного регистра с RS-триггерами вводятся 2m двухвходовых элементов

И вЂ” Н Е, в составе мультиплексора на две группы по m входов вводятся 2m двухвходо- 15 вых элементов И и m двухвходовых элементов ИЛИ, и в составе блока управления вводятся один инвертор, один двухвходовый элемент И, один двухвходовый элемент

ИЛИ, два двухвходовых элемента ИЛИ вЂ” НЕ, 20 один )logjam(-входовый элемент WIN — НЕ, эквивалентный ()logjam(— 2 двухвходовым элементам ИЛИ и одному элементу ИЛИ—

НЕ, а также (2 + )logjam() D-триггеров где

)logjam(— число, полученное в результате ок- 25 ругления числа log2m до ближайшего большего целого, если число logjam есть число не целое.

При подсчете алгебраической суммы числа однотипных логических элементов, 30 исключенных (со знаком "минус") и введенных (со знаком "плюс") в известное устройство и из него соответственно, при реализации предлагаемого устройства имеем: число исключенных инверторов равно 35

3m; число исключенных двухвходовых элементов И равно(т +4m+4); число исклюг ченных двухвходовых элементов И вЂ” НЕ равно 10m; число исключенных трехвходовых элементов ИЛИ равно 2m; число исклю- 40 ченных m-входовых сумматоров по модулю два равно m; число исключенных D-триггеров равно (m — )logjam(); число введенных двухвходовых элементов ИЛИ равно (m +

)logjam(— 1); число введенных двухвходовых 45 элементов ИЛИ вЂ” НЕ равно 1; число введенных трехвходовых элементов И вЂ” НЕ равно

6m.

Для дальнейшего сравнения аппаратурных затрат известного и предлагаемого уст- 50 ройств рассматриваем введенные трехвходовые элементы И вЂ” НЕ как совокупности из одного двухвходового элемента И и одного двухвходового элемента И вЂ” НЕ.

Тогда число исключенных инверторов равно 55

3m; число исключенных двухвходовых элементов И равно m + 4m+ 4; число исключенных двухвходовых элеентов И-НЕ равно

10m; число исключенных трехвходовых элементов ИЛИ равно 2m; число исключенных

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

Физически, по технологическим параметрам выполнение по одной технологии, аппаратурные затраты на один двухвходовый элемент ИЛИ можно приравнять к аппаратурным затратам на один элемент И, а аппаратурные затраты на один элемент

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

3m+ m + 4m+ 4+ 10m+ 2m+ m+ m — )logjam(=

= m + 21m — )logjam(+ 4 элементов против увеличения на m+jlogzm(— 1+1+6m+6m

= 13m + )logjam(элементов, что в конечном счете дает общую экономию аппаратурных затрат на m + 21m — )!оцуп (+ 4 — 13m—

)logjam(= m + 8m — 2)logjam(+ 4 логических элементов.

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

И-НЕ) каждый.

Таким образом, для реализации предлагаемого устройства умножения над полем

GF(2 ) необходимо иметь аппаратурных затрат на (m + 8 — 2)!оягв(+ 4) логических

2 элементов меньше, чем для реализации известного.

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

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

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

1728858

5

15

40

50

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

2. Устройство по п.1, о т л и ч а ю щ е ес я тем, что блок управления содержит элемент ИЛИ, элемент И, три элемента ИЛИН Е, Р-триггер, ()I ogzm(+1)-разрядный двоичный счетчик, (где )logjam(-ближайшее целое, большее к logjam число, если logzm— нецелое) и элемент НЕ, вход которого соединен с первым входом блока управления и первым входом первого элемента ИЛИ вЂ” НЕ, выход которого соединен с первым входом второго элемента ИЛИ-НЕ, второй вход которого соединен с входом сброса 0-триггера, выходом элемента ИЛИ и четвертым выходом блока управления, второй вход которого соединен с тактовым входом D-триггера и первым входом элемента И, второй вход которого соединен с выходом D-триггера, информационный вход которого соединен с выходом второго элемента

ИЛИ вЂ” НЕ, вторым входом первого элемента

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

Plogzm() старших разрядов которого соединены с соответствующими входами третьего элемента ИЛИ-НЕ, выход которого соединен с шестым выходом блока управления и вторым входом элемента ИЛИ.

1728858

1728858

1728858

1728858

171

Фиг. 7

1728858

Составитель И.Коваляв

Техред М.Моргентал Корректор Н.Ревская

Редактор Е.Папп

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101

Заказ 1409 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5