Устройство для умножения по модулю 2 @ -1 Советский патент 1987 года по МПК G06F7/49 

113

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

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

t

На фиг. 1 изображено устройство

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

Устройство для умножения по модулю 2-1 (фиг,) содерх сит регистр 1 сдвига, группу элементов И 2,--2рэ сумматор 3, регистр 4 хранения, блок 5 коррекции результата и блок 6 синхронизации.

Блок 6 синхронизации (фиг, 2) содержит RS-триггеры 7,8 и 9j элементы 10 И и элемент I ИЛИ, элемент 12 НЕ, элементы 3э 14 ИЛИ, регистр 15 сдвига, элемент 16 И, элемент 17 ИЛИ тактовый вход 18, вход 19 логического О, вход 20 логической 1, входы 21,22 пуска и установки устройства, первый, второй и третий выходы 23,24 и 25 блока 6.

На чертежах обозначено D с индексом - информационные входы регистров сдвига и регистра хранения; Q - выходы регистров сдвига, регистра хранения и прямые входы RS-троиггеров; Е - входы сброса регистров сдвига и регистра хранения; С - входы синхронизации регистров сдвига -и регистра хранения; DR - вход разрешения сдвига регистров; SO - вход режима; А,Б входы первого и второго слагаемых сумматоров.; S с индексом - выходы суммы сумматоров; Р и Р - соответственно вход и выход переноса сумматоров.,

Блок 5 коррекции результата (фиг. содержит элемент 26 И-НЕ и группу элементов 27 И.

На временной диаграмме (фиг. 4) 21,24,23,25, и f , RG 15 (, 11 (Q), Т8 (Q), Т9 (Q) обозначают эпюры напряжений в. соответствующих точках.блока синхронизации.

192

Устройство для умножения чисел по модулю 2 -1 работает по алгоритму, который заключается в следующем.

Пусть А 2 Ер., +2 -2ap. +. . .

. ..2а|+ае - множимое, а Ъо. +

р-1

. а,) а.л - ivirtu J inuc , ct и Р-

+2 Ьр. +...+2Ъ,+Ъц - множитель. Запишем произведение А.В в виде:

р-г

А-В А Ъо+2Ь, А+2Ч2А+. . .+2 Ър.

хА+2 Ъ

р-1

1)

Таким образом, для того, чтобы умножить А на В необходимо А . , где (,1,...,р-), умножить соответственно на Ъ; с последующим суммированием сформированных частичных произведений. Поскольку Ъ; может принимать только два значения - О и 1, то частичное произведение А;Ъ будет равно нулю при и А- при Ц-.

Для сокращения аппаратурных затрат при реализации этого алгоритма удобно произведение А.В с учетом равенства 2.lmod.(2 -1) представить в виде:

.Во+2ГА-Ъ,+2ГА-Ъ + . ..

,...,,+2(А.Ър, )...lj. (2) I

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

Множитель В, представляющий собой число, не.превышающее 2 -1 и кодируемое двоичным кодом, т.е. представляемое в двоичной системе счисления р.- разрядныг двоичным числом, подается на входы DO,...,Dp., сдвигового регистра 1. Множимое А, представляющее собой число, не превьшающее 2 -1 и кодируемоедвоичным кодом, т.е. представляемое в двоичной системе счисления р-разрядным двоичным числом, подается на первые входы группы элементов И 2,...,2п, вторые входы которых объединены и соединены с вы ходом сдвигового регистра 1, Таким образом, прохождением множимого А через группы элементов И управляют разряды множителя В начиная со старщего разряда. В начале работы устройства или после включения питания на вход 22 блока 6 необходимо подать импульс начальной установки, который сбрасывает (t+1)-разрядный, сдвиговый регистр 13 блока 6 в нулевое состояние (в данном варианте ), что. включает за собой установку RS-триггеров 7 и 9 в состояние логического О. После подачи разрядов множителя В и множимого А на со15

20

ответствующие входы устройства для выполнения их перемножения на вход 21 блока 6 необходимо подать импульс Пуск. Импульс Пуск с выхода 24 блока 6-подается на вход SO установки 5 режима сдвигового регистра I, а также подается непосредственно на вход SO установки режима сдвигового регистра 15 блока 6. Тот же импульс через элемент 17 ИЛИ с некоторой за- О держкой, позволяющей установиться режиму Запись в регистре 1, поступает с выхода 23 блока 6 на тактовый вход С регистра 1, производя тем самым запись разрядов множителя В в регистр 1, а также через элемент

14ИЛИ он поступает на тактовый вход С сдвигового регистра 15, производя тем самым запись единицы в разряд Q и нулевой в разряды Qf+Q. регистра 15, так как вход D регистра 15 соединен с шиной единичного потенциала, а входы соединены с шиной нуле вого потенциала. С выхода Q регистра

15единичный потенциал подается на вход R RS-триггера 8, на вход которого подан потенциал логиче ского

с выхода Q, регистра 15. Тем самым, триггер 8 устанавливается в нулевое состояние и с него через выход 25 блока Ь поступает сигнал сброса на регистр 4, имеющий нулевой уровень активности по выходу R. Импульс Пуск поступает также на вход S триггера 7 и, включая его в единичное состояние, разрешает прохождение инверсной тактовой частоты через элемент 10 И, с выхода которого она подается на первый вход элемента 14 ИЛИ.

с40

В результате после подачи импульса Пуск происходит запись множителя В в регистр 1, установка регистра 1 5 в состояние единицы только на

30

35

рые подаются на входы В(,,...,Вр.

А

17

tin

сумматора 3, на входы А,,...,Л

р-1 с выкоторого поданы логические О хода регистра 4. Для обеспечения работы сумматора 3 по mod(2 -1) его выход р переноса соединен с входом Г переноса, поскольку на выходе р появляется двоичное число с весом 2 , а 2 -lmod(2 -l).

В случае подачи на вход Р., переноса единицы с выхода Р переноса еще один перенос принципиально возникнуть не может. Это видно из следующего: максимально возможные по величине числа, суммируемые таким сумматором, равны 2-1, при их сложении получается число 2(2 -1), представляемое в двоичном коде Р единицами и одним нулем в младшем разряде 1....10, и потому при переносе старшей единицы в младший разряд еще один перенос не возникает. В-результате через интервал времени, равный сумме времени появления сигнала пере- носа на входе р сумматора 3 (первое срабатывание), считая от момента подачи слагаемых на входы сумматора 3, и времени появления суммы этих слагаемых на выходах S ,. . . ,Sp., сумматора 3 (второе срабатывание сумматора 3), на выходах Sg,...,Sp., сумматора 3 появляется двоичный код, равный значён5те1 суммы по модулю 2°-} двух слагаемых на входах сумматора 3

После окончания импульса Пуск через-элементы 10 И, 14 ИЛИ на тактовый вход регистра 15 поступает положительный перепад напряжения инверти рованной тактовой частоты, переклю- регистр 15 в состояние с присутствием уровня логической 1 толь ко на выходе Q,, который устанавливает триггер 8 в единичное состояние

выходе QP , сброс регистра 4, а также ,е. снимая тем самым режим Сброс с реf. -5f

открывается прохождение инверсной тактовой частоты на тактовый вход С регистра 15. После окончания импульса Пуск регистры 1 и 15 переводятся в режим Сдвиг путем подачи на

50

гистра 4, а также устанавливает триггер 9 в единичное состояние, открывая тем самым путь прохождения прямой тактовой частоты через элементы 16 И, 17 ИЛИ.на выход 23 блока 6. С приходом положительного перепада напряжения прямой тактовой частоты перепад через элементы 16 И, 17 ИЛИ поступает на входы тактовой частоты

их входы 80 потенциала логического с шины, на которую поступает им50

О

гистра 4, а также устанавливает триггер 9 в единичное состояние, открывая тем самым путь прохождения прямой тактовой частоты через элементы 16 И, 17 ИЛИ.на выход 23 блока 6. С приходом положительного перепада напряжения прямой тактовой частоты перепад через элементы 16 И, 17 ИЛИ поступает на входы тактовой частоты

пульс Пуск. С выхода Qp., регистра

I на вторые входы группы элементов

И 2,,...,2р подается разряд Ьр, мно-гг регистров 4 и 1, производя этим самым

жителя В, ив зависимости от его . запись информации с выходов сумматора

значения О или 1 на выходах этой 3 с учетом циклического сдвига на

группы элементов И появляются либо

нули, либо разряды множимого А, котоодин разряд в регистр 4, который является регистром с записью информа5

0

5 О

0

0

5

рые подаются на входы В(,,...,Вр.

А

17

tin

сумматора 3, на входы А,,...,Л

р-1 с выкоторого поданы логические О хода регистра 4. Для обеспечения работы сумматора 3 по mod(2 -1) его выход р переноса соединен с входом Г переноса, поскольку на выходе р появляется двоичное число с весом 2 , а 2 -lmod(2 -l).

В случае подачи на вход Р., переноса единицы с выхода Р переноса еще один перенос принципиально возникнуть не может. Это видно из следующего: максимально возможные по величине числа, суммируемые таким сумматором, равны 2-1, при их сложении получается число 2(2 -1), представляемое в двоичном коде Р единицами и одним нулем в младшем разряде 1....10, и потому при переносе старшей единицы в младший разряд еще один перенос не возникает. В-результате через интервал времени, равный сумме времени появления сигнала пере- носа на входе р сумматора 3 (первое срабатывание), считая от момента подачи слагаемых на входы сумматора 3, и времени появления суммы этих слагаемых на выходах S ,. . . ,Sp., сумматора 3 (второе срабатывание сумматора 3), на выходах Sg,...,Sp., сумматора 3 появляется двоичный код, равный значён5те1 суммы по модулю 2°-} двух слагаемых на входах сумматора 3.

После окончания импульса Пуск через-элементы 10 И, 14 ИЛИ на тактовый вход регистра 15 поступает положительный перепад напряжения инвертированной тактовой частоты, переклю- регистр 15 в состояние с присутствием уровня логической 1 только на выходе Q,, который устанавливает триггер 8 в единичное состояние.

f

гистра 4, а также устанавливает триггер 9 в единичное состояние, открывая тем самым путь прохождения прямой тактовой частоты через элементы 16 И, 17 ИЛИ.на выход 23 блока 6. С приходом положительного перепада напряжения прямой тактовой частоты перепад через элементы 16 И, 17 ИЛИ поступает на входы тактовой частоты

один разряд в регистр 4, который является регистром с записью информа513040

ции по положительному перепаду с целью исключения гонок; а также сдвиг на один разряд вправо кода, записанного в регистре 1. Таким образом, на

выходах Q,...,Qp., регистра 4 появ- ляется двоичный код, соответствующий произведению 2 А.Ър, , а на выходе Qp, регистра 1 появляется разряд множителя В подающий на входы Вд, . . . ,Вр., сумматора 3 двоичный код, соответствующий произведению Ър. А.

С приходом следующего положительного перепада инверсной тактовой частоты регистр 15 блока 6 перекл очается в состояние с присутствием логической 1 только на выходе Q,, а сумматор 3 в это время производит .сложение кода А, поступающего с выходов элементов 7 И, и кода, соот- ветствующего произведению 2А Ьр.( , поступающего с выходов регистра 4 на входы AQ,... ,А р.1 сумматора 3. С приходом положительного перепада прямой тактовой частоты на тактовый вход регистра 4 с выхода 23 блока б в регистр 4 записывается двоичный код, соответствующий значению 2(А Ър.2 + +2А Ър., ) , и по этому же перепаду в регистре 1 снова происходит сдвиг кода множителя В и на выходе регистра 1 появляется разряд Ър. множителя В. Аналогично после переключения регистра 15 в состояние с логической 1 только на выходе Q-t-i затем с приходом положительного перепада напряжения прямой тактовой частоты в регистр 4 происходит запись двоичного кода соответствующего значению 2(А Ь,+2(А Ъ + . . .+2(А Ьр, +2(А Ьр, ) ...)}., а на выходе Q.p-i регистра 1 появляется разряд Ъд множителя В. При поступлении положительного перепада инверсной тактовой частоты регистр 15 переключается в состояние с присутствием единицы только на выходе Q, устанавливая через элемент 13 ИЛИ триггер 9 в состояние логического блокируя тем самым прохождение прямой тактовой частоты. Сумматор 3 в это время производит сложение двоичного кода, соответствующего значению А-Ъ, и двоичного кода соответствующего значению . +2 А Ъг+... Ър, Ър + +2(А Ър. )1-3 результате на выходах сумматора 3 Q

О

р-1

появляется значение двоичного кода, соот

5

5 0 0 5 0 5

0

5

96

ветствующего значению произведения

АВ, равного:

А Ъ В,+2ГА Ь,н- + Ьр, +2(Л Ьр., )... . Этот двоичный код с выходов v,;..., Qp., сумматора 3 поступает на входы блока 5, устраняющего неоднозначность представления нуля по модулю 2

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

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

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

(где ,l...t-I; t является

входом (p-2i-)-ro разряда, мнолси- теля устройства, t-й информационный вход регистра сдвига является входом нулевого разряда множителя устройства, j-й информационный вход регистра сдвига (где , t+2,..., t-1) является входом р-2( j-t-1 )-2j разряда множителя устройства, 2 Ь-й информационный вход регистра сдвига соединен с входом нулевого разряда множителя устройства k-й информационный вход регистра сдвига (где k(2t+l)f X(2t+2)...(3t-l) является входом p-2(k-(2t-l)-1 )J разряда множителя устройства, выходы (t-l)-ro и (2t- -1 )-го и (3t-l)-ro разрядов регистра сдвига соединены соответственно с первым, вторым и третьим управляющими входами S-X мультиплексоров группы (где S-1,2,3...р), первый информационный вход S-ro мультиплейсо- ра группы соединен с шиной логического нуля устройства, второй информационный вход первого мультиплексора группы является входом (р-1)-го инверсного разряда множимого устрой

713

ства, второй информационный вход q.-ro мультиплексора группы (где q 2,3...р) является входом (q-2)-ro инверсного разряда множимого устройства, третий информационный вход S-ro мультиплексора группы является рходом (3-1)-го разряда множимого устройства, четвертый информационный вход S-ro мультиплексора группы является входом (S-l)-ro инверсного раз- ряда множимого устройства, пятый информационный вход S-ro мультиплексора группы соединен с третьим информационным входом S-ro мультиплексора группы, шестой информационньй вход которого соединен с четвертым информационным входом S-ro мультиплексора группы, седьмой ин формационный вход первого мультиплексора группы соединен с входом (p-l)-ro разряда множимого устройства, седьмой информационный вход q-ro мультиплексора группы соединен с входом (q-2)-ro разряда множнмо1 о устройства, восьмой информационный вход S-ro мультиплексора группы соединен с первым входом S-ro мультиплексора группы и с входом разрешения сброса регистра сдвига, выход S-ro мультиплексора группы соединен с первым информационным входом S-ro разряда су1«1матора, второй информационный вход S-ro разряда которого соединен с выходом В-го раз- «

5

40

5 О

0

5

0

198

ряда регистра хранения, информационный вход г-го разряда которого (где ,2,3...р-2) соединен с выходом суммы (г+2)-го разряда сумматора, выход первого и второго разрядов суммы которого соединены соответственно с информационными входами (p-l)-ro и р-го разрядов регистра хранения, выход переноса сумматора соединен с входом переноса сумматора, вход пуска устройства является входом пуска блока синхронизации, установочный вход которого является входом установки устройства, первый выход блока синхронизации соединен с входом сброса мультиплексоров группы и входами синхронизации регистров сдвига и хранения, вход разрешения сдвига регистра сдвига соединен с вторым выходом блока синхронизации, третий выход которого соединен с входом сброса регистра хранения, блок коррекции результата содержит элемент И-НЕ и группу элементов И, причем 1-й вход элемента И-НЕ (где 1 1,2...р) является входом 1-го разря- да блока коррекции результата и соединен с первым входом 1-го элемента И группы, второй вход которого соединен с выходом элемента И-НЕ, выходы элементов И группы яв- ляютСя выходами блока коррекции, результата.

JofJ

i

19

К

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

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

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

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

15

i

4i

Г

Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в устройствах для цифровой обработки сигналов (в частности изображений ), а также в системах кодирования, принцип действия которых базируется на теории полей Галуа. Цель изобретения - сокращение аппаратурных затрат. Поставленная цель достигается тем, что вводятся Зt-paзpядный t (p+l)/2j сдвиговый регистр, группа р мультиплексоров, р-разрядный регистр обратной связи и блок синхронизации, что позволило организовать анализ ГРУПП из одного, либо трех разрядов множителя и последовательно накапливать сумму в регистре обратной связи. 4 ил. со о 4