Устройство для умножения по модулю 2 -1

Бюл. анич 914ский институт Р.Б в тельство СССР Р 7/49, 1984. льство СССР Р 7/49, 1983. ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ОПИСАНИЕ ИЗОБРЕ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(57) Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано вустройствах для цифровой обработкисигналов (в частности изображений),а также в системах кодирования, принцип действия которых базируется натеории полей Галуа. Целью изобретенияявляется сокращение аппаратурных затрат. Устройство содержит регистр сдвига 1, группу мультиплексоров 2, сумматор 3, регистр хранения 4, блок коррекции результата 5 и блок синхронизации 6. Введенные 3-разрядный регистр сдвига 1 и группа мультиплексоров 2 позволяют организовать анализгрупп из трех разрядов множителя ипоследовательно накапливать сумму врегистре хранения. 5 ил., 1 табл.1 130401Изобретение относится к вычислительной технике и технической кибернетике и может бЫть использовано в , устройствах для цифровой обработки сигналов (в частности, изображений), а также в устройствах кодирования, принцип действия которых базируется на теории конечных колец.Цель изобретения - сокращение аппаратурных затрат. 10На фиг,1 изображено устройство для умножения по модулю 2 -1; на фиг.2 - группа мультиплексоров; на фиг.З блок синхронизации; на фиг4 - блок коррекции результата; на фиг 5 - вре менная диаграмма работы блока синхронизации в устройстве для умножения, рпо модулю 2 -1 в случае р=7.Устройство для умножения по модулю 2 -1 (р - нечетное) содержит регистрО 1 сдвига, группу мультиплексоров 2, сумматор 3, регистр 4 хранения, блок 5 коррекции результата и блок 6 синхронизации. Р ррр 1 о р 1 2 -1-В=2 +2 2 +2 -2 Ь=2 Ьр,+2 Ь 2 Ь, +2 Ь, . (3) Биты Операция ь, ь, ь 0 0 0 0 0 1 Пропуск нуляПропуск множимого Блок 6 синхронизации (фиг.З) содержит КЯ-триггеры 7-9, элемент 10 И,элемент 11 ИЛИ, элемент 12 НЕ, элементы 13-14 ИЛИ, регистр 15 сдвига,элемент 16 И, элемент 17 ИЛИ, тактовый вход 18, вход 19 логического "0",вход 20 логической "1" входы 21,22пуска и установки устройства, первый,второй и третий выходы 23-25 блокасинхронизации,35Блок 5 коррекции результата (фиг.4)содержит элемент 26 И-НЕ и группуэлементов 27 И.На чертеже обозначено: Р с индексом - информационные входы регистровсдвига, мультиплексоров и регистрахранения; Ц - выходы регистров сдвига,регистра хранения и прямые выходы КЯтриггеров; К - входы сброса регистров сдвига, регистра хранения и входы 45синхронизации мультиплексоров; Свходы синхронизации регистров сдвигаи регистра хранения; РК-вход разрешения сдвига регистров; БО - вход режима; А,В - входы первого и второгослагаемых сумматоров; Б с индексом -выходы суммы сумматоров; Р, и Р - соответственно вход и выход переносасумматоров; Ч О, Ч 1, Ч 2 - первый,второй и третий входы управления муль типлексоров,На временной диаграмме (Фиг,5) 21,24,23,25 и 18, КС 15 (Я -Я), Т 7(4), Т 8 (Я), Т 9обозначают эпюры 8 2напряжений в соответствующих точкахблока синхронизации.Устройство для умножения чисел поРмодулю 2 -1 работает на основании модифицированного алгоритма Бута дляарифметики по модулю 2 -1Р Р 2Обозначим буквой А=2 а +2 а +Р 2=2 РЬ , +2 Ь 2 Ь +Ь - мноа Р.Р 21 0житель. При реализации этого алгоритма множитель разбивается на группыпо три бита каждая, причем соседниегруппы имеют один общий бит. Для этого множитель В представляют в следующем виде:В=2 (В -2 Ь+Ьр ) +2 (Ь зЬ +Ь ) +2 (Ьз+2 (Ь -2 Ь +Ь р, ), (1)где р - нечетное число.В справедливости (1) можно легкоубедиться, если раскрыть скобки иучесть равенство 2 =1 щос 1(2 -1),Таким образом, для того, чтобыумножить А на В.А В=(2 А)(Ь, -2 Ь +Й )+(2 зА)(ЬЗ -2 Ь +Ь 2)++(2 А) (Ь -2 Ь 6+Ь )++(2 А) (Ьр2 ЬР- +Ь р)+(2 А) (Ьо 2 Ьо+Ъ р необходимо А;, где А,=2 А (1.=1,3,5р), умножить на (Ь;-2 Ь,+,+Ь) споследующим суммированием сформированных частных произведений. Подставляя.в выражение (Ь,-2 Ь, +Ь ) все возможные комбинации значений Ь; Ь,;Ь и учитывая это обстоятельство,1 ь 1что операцию вычитания в арифметикепо модулю 2 -1 можно заменить операцией сложения с инвертированным кодомвычитаемого на основании тождеств (2)и (3), получим таблицу команд формирования частичных произведений с анализом трех разрядов множителя:3 1304018Продолжение таблицы Быты Операция ь,1 ь,.ь 0 1 0 Пропуск множимого 4Для сокращения аппаратурных затрат при реализации этого алгоритма произведение А В с учетом равенства 2 Р= =1 шой(2 -1) можно представить в виде А В=А(Ьо 2 Ь +Ь . )+2А(Ь 2 Ь + +Ър )+2А(Ь -2 Ь +Ь )++2+2 ЬР.+ +2 Ьр, . 0 1 1 Пропуск удвоенногомножимого 1 0 0 Пропуск инвертирован"ного кода удвоенногомножимого15 1 0 1 Пропуск инвертированного кода множимого 1 1 0 Пропуск инвертированного кода множимого 1 1 1 Пропуск нуля 25Умножение на степень двойки в арифметике по шо(1(2 -1) сводится к циклическому сдвигу кода умножаемого числа в сторону старших разрядов. Это показано в (4) и (5). дцЕсли В=2 Ь +2 Р Ь 2 РЬ +РР-УР-к - В 2"=2 Р- +2-"Ь 2 Ь +И Р-К +2 Ь, ,2 Ь +2 Ь,. (4)Учитывая 2 =1 шой (2 Р) и разместив члены (4) в порядке уменьшения весов, получимВ 2"=2" Ь 2Ь +2" В +2"Ь + 40Р-(К+1 ЬЮ РТаким образом, видно, что каждая операция .приведенной таблицы сводится 45 к элементарным действиям: пропуск ну" ля; пропуск множимого; пропуск циклически сдвинутого на один разряд множимого; пропуск циклически сдвинутого на один разряд инвертированного кода 5 О множимого; пропуск инвертированного кода множимого. Последний член множителя В в равенстве (1), равный Ь -2 Ь +Ъяв ляется корректирующим, для учета этого члена множитель слева искусственно дополняется двумя разрядами ЬЬОЬОЬР ( Ър-;"ь Ьр ьььЬ Ь е А(Ь,-2 Ь +Ь, ) 13 (6)В начале первого такта работы устройства на входы первого слагаемого сумматора поступает множимое А, переданное в зависимости от разрядов Ь Ь Ь, множителя, на входы второго слагаемого сумматора на первом такте поступают нули с выходов регистра 4. Через полтакта информация.с выходов сумматора с учетом циклического сдвига на (р) разрядов записывается в регистр обратной связи с записью по переднему фронту импульса. Таким образом, в конце первого такта на ьы" ходах регистра 4 появляется значение произведения, равное 2" А(Ъ, -2 Ъ + +Ь,). В начале второго такта на входы первого слагаемого сумматора поступает множимое А, переданное в зависимости от разрядов Ь,Ъ Ь с множителя "А(Ъ - "2 Ь +Ь ) а на входы второго слагаемого4 9 фсумматора с выходов регистра 4 поступает 2 -А(Ь -2 Ь +Ь,). Через полтакта1информация на выходах сумматора, равная А(Ь -2 Ь, +Ь )+2 ьА(Ь -2 Ь +Ь, ) с учетом циклического сдвига на (р) разрядов, записывается в регистр об" ратной связи и к концу второго такта на выходах регистра 4 формируется значение суммы частичных произведений, равное2А(Ь -2 Ь +Ъ )+2 А(Ь -2 Ь +Ь)ьо+1Аналогично к концу (" -- 1)"го2 такта на выходах регистра 4 появляется значение суммы частичных произведений, равное2 А(Ь -2 Ь +Ь )+2А(Ь -2 Ь ++Ь, )+ +2"А(Ь, -2 Ь,+Ь, ).И р+1В начале - го такта на входы2первого слагаемого сумматора поступает множимое А, переданное в зависимости от разрядов Ь , Ь, Ь, множителя (корректирующие разряды), а на входы второго слагаемого сумматора с выходов регистра 4 поступает значение суммы частичных произведений, равное+Ь )2 1. А(Ь, -2 Ь +Ь) 11.1,и в результате через полтакта на вы 5ходах сумматора появляется значениепроизведения:АВ=А(Ь, -2 Ь +Ь )+2А(Ь -2 Ь, ++Ь, )+2А(Ь -2 Ъ, +Ь )+ +201( А(Ь 1 -2 Ь, +Ь, ) 3 .3Длительность полутакта определяется временем срабатывания сумматора,передачу множимого А в зависимости 15от разрядов множителя В можно выполнить с помощью мультиплексоров, а подачу следующей тройки разрядов В можно организовать с помощью сдвиговогорегистра. 20Устройство для умножения чисел поРмодулю (2 -1) работает следующим образом,Множитель В, представляющий собойРчисло, не превышающее 2 -1 и кодируемое двоичным кодом, т.е, представляемое в двоичной системе счисления рразрядным двоичным числом, подаетсяна входы Э, - Рсдвигового регистра 1 в следующем порядке: на входы З 0П П,О подаются все четныеразряды, начиная с Ь затем Ь,и кончая Ь,; на входы О Р ,1П 1 подаются Ь, и все нечетные разряды, начиная с Ъ затем Ь р, Ь 35и кончая Ь,; навходы О, 0+1П 1 подаются вновь все четные разряды, начиная с Ь , затем Ь , Ьс ф а. 1 фи кончая ЪМножимое А, представляющее собой 40Рчисло, не превышающее 2 -1 и кодируемое двоичным кодом, т,е. представляемое в двоичной системе счисления рразрядным двоичным числом, подаетсяв прямом и обратном кодах на входы 45группы мультиплексоров 2 в следующемпорядке (фиг.2): на входы Э, мультиплексоров 2, 2 ,, 2 подаются соответственно разряды а а а , т,е.Р 1 сР 2подается поразрядно сдвинутый на один 50разряд обратный код множимого А; навходы П мультиплексоров 2 ,2 ..21 Дподаются соответственно разряды аа,а, те, подается поразрядно1 ф ф ф с.1 фпрямои код множимого А; на входы Р 55мультиплексоров 22,2 подаютсясоответственно разряды а ,а .ана входы П мультиплексоров 2, 22 подаются соответственно разряды а а, ,а р на входы П мультиплексоров 2, 22 подаются соответственно разряды а , аа , т.е. сдвинутый на один разряд .прямой код множимого А; на входы О и Р, мультиплексоров 2 22подаются уровни напряжения, соответствующие логи 1ческому "О", Первый вход 70 выборки канала всех мультиплексоров подсоединен к выходу Ц регистра 1, второй вход Ч 1 управления мультиплексоров подсоединен к выходу Црегистра 1, третий вход Ч 2 управления всехмультиплексоров: подсоединен к выходу Я ., регистра 1. Таким образом, выборка каналов мультиплексоров осуществляется в зависимости от значения,трех последовательных разрядов множителей В, В начале работы устройства на вход 22 блока 6 необходимо подать импульс начальной установки, которыйосбрасывает (Т+1)-разрядный сдвиговый регистр 15 блока 6 в нулевое состояние, что влечет за собой установку КБ-триггеров 7 и 9 в состояние логического "О 1. После подачи разрядов множителя. В и множителя А на соответствующие входы устройства для выполнения их перемножения на вход 21 бло- ка 6 необходимо подать импульс "Пуск". Импульс "Пуск" с выхода 24 блока 6подается на вход БО установки режимарегистра 1, а также непосредственнона вход ЯО установки режима регистра15 блока 6. Тат же импульс через элемент ИЛИ с некоторой задержкой, позволяющей установиться режиму "Запись"в регистре 1, поступает с выхода 23 блока 6 на тактовый вход С регистра 1, производя тем самым запись разрядов множителя В в регистр 1, а такжечерез элемент 14 ИЛИ он поступает навход С сдвигового регистра 15, производя тем самым запись единицы в разряд Я, и нулей в разряды 0 - Я регистра 15, так как вход П, регистра 15 соединен с шиной единичного потен циала, а входы П, - Р, соединены с шиной нулевого потенциала. С выхода Я, регистра 15 единичный потенциал подается на вход К КЯ-триггера 9, на вход Я которого подан потенциал логического "О" с выхода Ц регистра115, тем самым КБ-триггер 9 устанавливается в нулевое состояние и с него через выход 25 блока 6 поступает сигнал сброса на регистр 4 хранения,име 13040ющий нулевой уровень активности входа К, Импульс "Пуск" поступает также на вход Б триггера 7 и, включая его в единич:;ое состояние, разрешает прохождение инверсной тактовой частоты через элемент 10 И, с выхода которого она подается на первый вход элемента 14 ИЛИ, В результате после подачи импульса "Пуски происходит запись множителя В в регистр 1, установка реги стра 15 в состояние единицы только на выходе О сброс регистра 4, а также открывается прохождение инверсной тактовой частоты на тактовый вход С регистра 15. После окончания импульса "Пуск" регистры 1 и 15 переводятся в режим "Сдвиг" путем подачи нулевого потенциала на их входы .БО. На вход группы мультиплексоров 2 поступает уровень логического 0, открывая тем 20 самым прохождение информации через мультиплексоры, а с выходов Ярегистра 1 подаются со.ответственно разряды Ь, Ь, Ъ множителя на входы выборки канала ЧО, Ч 1,25 72 группы мультиплексоров 2, пропуЬ- кая тем самым значение двоичного кода соответствующего произведения А(Ъ, - -2 Ь +Ь ) в соответствии с таблицей,оС выходовгруппы мультиплексоров 2 этот двоичный код поступает на входы В сумматора 3 на входы А поданы логические "0" с выхода регистра 4. Для обеспечения работы сумматора 3 по шос 1(2 -1) его выход Р переноса соединен с вхо дом Р переноса, поскольку на выходе.ор. появляется число с весом 2 ; а 2 =1 шос 1(2 -1), В случае подачи на вход Р переноса единицы с выхода Р пере- аноса еще один перенос принципиально возникнуть не может, Это видно из сле. дующего: максимально возможные по величине числа суммируемые таким сумУ рматором, равны 2 -1, при их сложении получается число 2(2 -1), представля емое в двоичном коде р единицами иодним нулем в младшем разряде 110,раз и поэтому при переносе старшей единицы в младший разряд еще один перенос не возникает, В результате чего интервал времени, равный сумме времени появления сигнала переноса на выходе Р сумматора. 55 (первое срабатывание), считая от момента подачи слагаемых на входы сумматора 3, и времени появления суммы этих слагаемых на выходах Б сумматора 18 83 (второе срабатывание сумматора 3), на выходах ББ сумматора 3Гпоявляется двоичный код, равный значению суммы по модулю 2 -1 двух слагаемых на входах сумматора 3.После окончания импульса "Пуск" через элемент 10 И и элемент 14 ИЛИ на тактовый вход С регистра 15 поступает положительный перепад напряжения инверсной тактовой частоты, переключающий регистр 15 в состояние с присутствием уровня логической " 1" только на выходе Ц , Уровень логической(на выходеустанавливает КБ-триггер 8 в единичное состояние, снимая тем самым режим "Сброс" с регистра 4 обратной связи, а также устанавливает триггер 9 в единичное состояние, открывая тем самым путь прохождения прямой тактовой частоты через элементы 16 И и 17 ИЛИ на выход 23 блока 6. С приходом положительного перепада напряжения прямой тактовой частоты этот перепад через элементы 16 И и 17 ИЛИ поступает на входы К сброса группы мультиплексоров 2, вход С тактовой частоты регистра 1 и вход С тактовой частоты регистра 4,.производя тем самым запись информации с выходов сумматора 3 с учетом циклического сдвига на (р) разрядов в регистр 4, который является регистром с записью информации по положительному перепаду с целью исключения гонок, сброс группы мультиплексоров 2 в ну 1 левое состояние на выходах, а также сдвиг на один разряд вправо слова, записанного в регистре 1. Таким образом, на выходах Я,Я регистра 4 появляется двоичный код, соответствующий произведению 2 А(Ь,-2 Ь +Ь,),р- да на выходах Ц ,т 1 ф Чзсстра 1 появляются соответственно разряды Ь Ь Ь, множителя В. С приходом следующего положительного перепада напряжения инверсной тактовой частоты регистр 15 блока 6 переключается в состояние с присутствием логической " 1" только на выходе Ц д, аотрицательный перепад прямой тактовой частоты с выхода 23 блока 6 открывает группу мультиплексоров 2 для прохождения кода, соответствующего произведению А(Ь -2 Ь, +Ь ). Эгот двоичный код, поступающий на входы В сумматора 3, суммируется с кодом, соответствующим произведению 2 А(Ь -2 Ь +Ь,), поступающим с выходов. регистра9 13040 4 на входы А сумматора 3. С приходом положительного перепада напряжения на тактовый вход С регистра 4 с выхода 23 блока 6 в регистр 4 записыва" ется по фронту двоичный код, соответ ствующий значению 2А(Ь -2 Ь +Ъ ) +зв +2 1 А(Ь -2 Ь +Ь, )33 и по этому же перепаду на вйходах (1 , ЯЯ регистра 1 появляется следующая тройка разрядов множителя А. Аналогично 10 после переключения регистра 15 в состояние с логической "1" только на выходе С 1, а затем с приходом положительного перепада напряжения прямой тактовой частоты на выходах регистра 15 4 появляется значение двоичного кода, ,соответствующегор 2А(Ь -2 Ь +Ь )+2А(Ь -2 Ь +Ь )++2 А(Ь,-2 Ь +Ь,) 33 3., 20Точно так же с приходом положительного перепада напряжения прямой тактовой частоты после переключения регистра 15 в состояние Я=1 на выхо 25 дах регистра 4 появляется значение двоичного кода, соответствующего значению2Г А(Ь, -2 Ь+Ъ, )+2 Р С А(Ь -2 Ь ++Ь)2 Г А(ЬЬ, +Ь) 333При переключении регистра 15 в состояние Я =1 открывается группа мультиплексоров 2Устанавливается через элемент 11 ИЛИ КБ-триггер 7 в состояние логического "0", блокируя про хождение инверсной тактовой частоты через элементы 10 И и 14 ИЛИ на тактовый вход С регистра 15, блокируя прохождение прямой тактовой частоты через элементы 16 И и 13 ИЛИ на так товый вход С регистров 1 и 4, а .также на вход сброса группы мультиплексоров. С выходов ЯЯЯ регистра1 поступают значения разрядов 1 р, Ь, Ь 6 множителя В соответственно и пода ются на входы ЧО, Ч 1, 72 выборки канала группы мультиплексоров 2, пропуская тем самым значение двоичного , кода, соответствующего произведению А(Ь, -2 Ъ, +Ь ) на входы В сумматора3, В результате на входах ББсумматора 3 появляется значение двоичного кода, соответствующего значению произведения А В, равного А(Ьо -- Ь,+Ьр )+2 А(Ьр -2 Ьр 1+Ьр,)+2 1 А (Ьр,-2 Ьр.+В р.г)+а+2 1 А(Ь,-2 Ь++Ь,Л 33,18 1 ОЭтот двоичный код с выходов БоБ сумматора 3 поступает на входыблока 5, служащего для устранения неоднозначности представления нуля попюй(2-1), появляющейся из-за того,что 2 -1=0 тосй(2 -1),При поступлении на входы блока 5двоичного кода, хотя бы с одним нулемв разрядах, он проходит на выходыблока 5 без измедения, а при поступлении на входы блока 5 Р. единиц навыходы блока 5 проходят нули.При необходимости умножить следую"щие два числа необходимо подать импульс "Уст,", затем подать на входыустройства двоичные коды умножаемыхчисел, а после этого подать импульс"Пуск". Описанная работа устройстваповторяется,Формула изобретенияРустройство для умножения по модулю 2 -1 (р - нечетное), содержащее сум" матор, блок коррекции результата, группу элементов И, причем первые входы -х элементов И группы (где =1,2 р)являются входами (1-1)-х разрядов множимого устройства, выходы суммы сумматора соединены с входом блока коррекции результата, выход которого является выходом результата устройства, о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, в него введены регистр сдвига, регистр хранения и блок синхронизации, причем информационный вход -го разряда регистра сдвига является входом (-1)-го разряда множителя устройства, выход р-го разряда регистра сдвига соединен с вторыми входами элементов И группы, выходы которых соединены с входами первого слагаемого сумматора, вход второго слагаемого которого соединен с выходом регистра хранения, информационный вход первого разряда которого соединен с выходом суммы р-го разряда сумматора, выход 1-го разряда суммы "которого (где 1= =1,2,р) соединен с входом Ц +1)"го разряда регистра хранения, выход переноса сумматора соединен с входом переноса сумматора, вход пуска устройства является входом пуска блока синхронизации, установочный вход которого является входом установки устройства, первый выход блока синхронизации соединен с входами синхронизации регистров сдвига и хранения, вход3040 Фи й разрешения сдвига регистра сдвига ивход сброса регистра хранения соединены соответственно с вторым и третьим выходами блока синхронизации, блоккоррекции результата содержит элемент 5И-НЕ и группу элементов И. причем 1-йвход элемента И-НЕ (где 1=1,2 р) 8 2является входом 1-го разряда блокакоррекции результата и соединен с пе рвым входом 1-го элемента И группы,второй вход которого соединен с выходом элемента И-НЕ, выходы элементовИ группы являются выходами блока коррекции результата.