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

 

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

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

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

РЕСПУБЛИН (19) (И) А1. (5D4 G 06F 7 49

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

H Д BTOPCHOMV СВИДЕТЕЛЬСТВУ

c > (!) * г

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21 ) 3957651/24-24 (22) 23.09.85 (46) 15.04.87, Бюл. № 14 (71) Физико-механический институт им. Г.B. Карпенко (72) О.И. Гречникова, P.Б. Попович и Г.С. Сварчевский (53) 681,325(088.8) (56) Авторское свидетельство СССР № 1170450, кл. G 06 F 7/49, 1984.

Авторское свидетельство СССР № 1160398, кл. G 06 F 7/49, 1983. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПО МО"

ДУЛЮ 2 -1 (р-нечетное)

Р (57) Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в устройствах для цифровой обработки сигналов (в частности изображений), а также в системах кодирования, принцип действия которых базируется на теории полей Галуа. Цель изобретения — сокращение аппаратурных затрат. Поставленная цель достигается тем, что вводятся 3t-разрядный (t= (р+1)/2) сдвиговый регистр, группа р мультиплексоров, р-разрядный регистр обратной связи и блок синхронизации, что позволило организовать анализ групп из одного, либо трех разрядов множителя и последовательно накапливать сумму в регистре обратной связи. с

4 ил.

1304019

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

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

На фиг. I изображено устройство для умножения по модулю 2 †. 1; на

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

Р

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

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

Блок 6 синхронизации (фиг. 2) содержит RS-триггеры 7,8 и 9, элементы 10 И и элемент ll ИЛИ, элемент 12

НЕ, элементы 13, 14 ИЛИ, регистр 15 сдвига, элемент 16 И, элемент 17 ИЛИ, 30 тактовый вход 18, вход 19 логического "0", вход 20 логической "1", входы 21,22 пуска и установки устройства, первый, второй и третий выходы

23,24 и ?5 блока 6.

На чертежах обозначено D с индексом — информационные входы регистров сдвига и регистра хранения; Q — - выходы регистров сдвига, регистра хранения и прямые Входы RS-триггеров R — 40 входы сброса регистров сдвига и регистра хранения; С вЂ” входы синхронизации регистров сдвига и регистра хранения; DR — вход разрешения сдви-га регистров; $0 — вход режима; А, — 45 входы первого и второго слагаемых сумматоров.; S с индексом — выходы суммы сумматоров; Р и Р— соответственно вход и выход переноса сумматоров. 50

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

На временной диаграмме (фиг. 4)

21,24,23,25, и fò q RG 15 (Q Я4) °

Т7 (Q), Т8 (Q), Т9 (Q) обозначают эпюры напряжений в соответствующих точках .блока синхронизации, Устройство для умножения чисел по модулю 2 — 1 работает по алгоритму, Р который заключается в следующем.

Пусть А=2 а +2 -2аР +...

Р- ... 2а, +а — множимое, а В=2 Ь Р, +

+2 Ьр-г + +2b +Ьо множитель

Запишем произведение А.В в виде:

А В=А bo+2b, A+2 Ь, А+... +2 Ь, " х A+2 P Ь, А. (1)

Таким образом, для того, чтобы умножить А на В необходимо А., где

I

А„=2 А(1=0, 1,...,р-1 ), умножить соответственно íà b, с последующим суммированием сформированных частичных произведений. Поскольку b„ может принимать только два значения — 0 и

1, то частичное произведение А;Ь; будет равно нулю при Ь; =0 и A„ при

b„=1.

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

A В=А Во+2(А Ь1+2 А Ь +

° +2 А Ь, +2 А ЬР- Д ° )) (2)

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

Г образом.

Множитель В, представляющий собой число, не превышающее 2 — 1 и кодируеP мое двоичным кодом, т.е. представляемое в двоичной системе счисления р.— разрядным двоичным числом, подается на входы D,...,D сдвигового регистра 1. Множимое А, представляющее собой число, не превышающее 2 -1 и

Р кодируемое двоичным кодом, т.е. представляемое в двоичной системе счисления р-разрядным двоичным числом, подается на первые входы группы элементов И 2,...,2, вторые входы которых объединены и соединены с выходом Q Р „сдвигового регистра 1.

Таким образом, прохождением множимого А через группы элементов И управляют разряды множителя В начиная со старшего разряда. В начале работы устройства или после включения питания на вход 22 блока 6 необходимо подать импульс начальной установки, который сбрасывает (Ь+1)-разрядный сдвиговый регистр l5 блока 6 в нулевое состояние (в данном варианте

t=p), что включает за собой установку RS-триггеров 7 и 9 в состояние логического "0". После подачи разрядов множителя В и множимого А на со1304019 ответствующие входы устройства для выполнения их перемножения на вход

21 блока 6 необходимо подать импульс

"Пуск". Импульс "Пуск" с выхода 24 блока 6*подается на вход $0 установки 5 режима сдвигового регистра 1, а также подается непосредственно на вход

$0 установки режима сдвигового регистра 15 блока 6. Тот же импульс через элемент 17 ИЛИ с некоторой задержкой, позволяющей установиться режиму "Запись" в регистре 1, поступает с выхода 23 блока 6 на тактовый вход С регистра 1, производя тем самым запись разрядов множителя

В в регистр 1, а также через элемент

14 ИЛИ он поступает на тактовый вход

С сдвигового регистра 15, производя тем самым запись единицы в разряд Q и нулевой в разряды Q<+Q4 регистра 20

15, так как вход D регистра 15 соединен с шиной единичного потенциала, а входы D --D соединены с шиной нуле< вого потенциала. С выхода Я регистра

15 единичный потенциал подается на вход R RS-триггера 8, на вход которого подан потенциал логического "0" с выхода Я< регистра 15. Тем самым, триггер 8 устанавливается в нулевое состояние и с него через выход 25 ! блока 6 поступает сигнал сброса на регистр 4, имеющий нулевой уровень активности по выходу R. Импульс Пуск" поступает также на вход $ триггера 7 и, включая его в ецинич- 35 ное состояние, разрешает прохождение инверсной тактовой частоты через элемент 10 И, с выхода которого она подается на первый вход элемента 14 ИЛИ.

1 40

В результате после подачи импульll tt са Пуск происходит запись множителя В в регистр 1, установка регистра 15 в состояние единицы только на выходе Яо, сброс регистра 4, а также 45 открывается прохождение инверсной тактовой частоты на тактовый вход С регистра 15. После окончания импульса "Пуск" регистры 1 и 15 переводятся в режим Сдвиг" путем подачи на5О их входы SO потенциала логического

tt ll

0 с шины, на которую поступает импульс "Пуск " . С выхода Ц < регистра

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

И 2 2 р подается разряд д р „мно-55 жителя В, и в зависимости от его значения 0 или 1 на выходах этой группы элементов И появляются либо нули, либо разряды множимого А, которые подаются на входы В„ ...,В сумматора 3, на входы А„,...,А которого поданы логические "0" с выхода регистра 4. Для обеспечения работы сумматора 3 по шой(2 — 1) его выP ход р переноса соединен с входом Г переноса, поскольку на выходе р появляется двоичное число с весом 2", а 2 lmod(2 -1).

В случае подачи на вход Р переноса единицы с выхода P переноса еще один перенос принципиально возникнуть не может. Это видно из следующего: максимально возможные по величине числа, суммируемые таким суммаР тором, равны 2 — 1, при их сложении получается число 2(2 -1), представP ляемое в двоичном коде Р единицами и одним нулем в младшем разряде

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

После окончания импульса "Пуск" через элементы 10 И, 14 ИЛИ на тактовый вход регистра 15 поступает положительный перепад напряжения инвертированной тактовой частоты, переключающий регистр 15 в состояние с присутствием уровня логической "1" только на выходе <",<<, который устанавливает триггер 8 в единичное состояние, снимая тем самым режим "Сброс" с регистра 4, а также устанавливает триггер 9 в единичное состояние, открывая тем самым путь прохождения прямой тактовой чаСтоты через элементы

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

3 с учетом циклического сдвига на один разряд в регистр 4, который является регистром с записью информа1304019 ции по положительному перепаду с целью исключения гонок; а также сдвиг на один разряд вправо кода, записанного в регистре 1. Таким образом, на выходах !,,,".-),, регистра 4 появляется двоичный код, соответствующий произведению 2 A.Ü „, а на выходе

Я > регистра 1 появляется разряд

Ь множителя Б, подающий на входы

B,,...,B, сумматора 3 двоичный код, 10 соответствующий произведению b>z А.

С приходом следующего положительного перепаца инверсной тактовой частоты регистр 15 блока 6 переключа- 15 ется в состояние с присутствием логической "1 только на выходе Я., а сумматор 3 в это время производит .сложение кода Ьр z А, поступающего с выходов элементов 7 И, и кода, соот- 20 ветствующего произведению 2А Ь Р, поступающего с выходов регистра 4 на входы А,...,А < сумматора 3. С приходом положительного перепада прямой тактовой частоты на тактовый вход регистра 4 с выхода 23 блока 6 в регистр 4 записывается двоичный код, соответствующий значению 2(A b +

+2А bp ), и по этому же перепаду в регистре 1 снова происходит сдвиг кода множителя В и на выходе регистра 1 появляется разряд b> множите-. ля B. Аналогично после переключения регистра 15 в состояние с логической

"1" только на выходе Q 1, а затем 35 с приходом положительного перепада напряжения прямой тактовой частоты в регистр 4 происходит запись двоичного кода соответствующего значению

2(А Ь,+2(А Ь +...+2(A Ь +2(А Ь, )) 40 ...)), а на выходе И..„, регистра 1 появляется разряд Ь множителя B.

При поступлении положительного перепада инверсной тактовой частоты регистр 15 переключается в состояние 45 с присутствием единицы только на выходе Qg, устанавливая через элемент

13 ИЛИ триггер 9 в состояние логического "О", блокируя тем самым прохождение прямой тактовой частоты. Сум- 50 матор 3 в это время производит сложение двоичного кода, соответствующего значению А Ь, и двоичного кода, о соответствующего значению 2 (А.Ь, +

+2 А Ьг+ ..+2(А Ь, +2(A Ьр + 55

+2(А Ь .„ )J ...jj . В результате на выходах сумматора 3 „,...,Q,„,, появляется значение двоичного кода, соответствующего значению произведения

АН, равного:

А b +2(A В,+2(А b .«2(А Ь +2(Л Ь, lj ..,))

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

Р-1 представления нуля по модулю 2

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

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

У"тройство для умножения по модулю 2 — 1 (р-нечетное), содержащее сумР матор и блок коррекции результата, причем выход суммы сумматора соединен с входом блока коррекции результата, выход которого является выходом результата устройства, о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, в него введены регистр сдвига, группа мультиплексоров, регистр хранения и блок синхронизации, причем i-й информационный вход регистра сдвига (где =0,1...t-1; t,-- ) является

p+1 входом (р-2i-1)-го разряда. множителя устройства, 1-й информационный вход регистра сдвига является входом нулевого разряда множителя устройства, 1-й информационный вход регистра сдвига (где j=t+1 t+2 t-1) яв— ляется входом (р-2(1-t-1) — 2) разряда множителя устройства, 2t-й информационный вход регистра сдвига соединен с входом нулевого разряда множителя устройства, K-й информационный вход регистра сдвига (где k=(2t+1)» х(2t+2)...(3t-1) является входом (р-2(k-(2t-1) — 1)) разряда множителя устройства, выходы (t-1)-го и (2t-1}-го и (3t — 1)-го разрядов регист— ра сдвига соединены соответственно с первым, вторым и третьим управляющими входами $-х мультиплексоров группы (где 3=1„2,3...р), первый информационный вход $-ro мультиплексора группы соединен с шиной логического нуля устройства, второй информационный вход первого мультиплексора группы является входом (р-1)-го инверсного разряда множимого устройI

130401 ства, второй информационный вход

q-ro мультиплексора группы (где q=

2,3...р) является входом (q-2)-ro инверсного разряда множимого устройства, третий информационный вход 5

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

S-го мультиплексора группы соединен с первым информационным входом S-го разряда сумматора, второй информационный вход S-го разряда которо.го соединен с выходом S-го разЗФ

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

1,2...р) является входом 1-го разря- да блока коррекции результата и соединен с первым входом 1-го элемента

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

1304019

s5ltF, м(4Я ю(Я

s545)

ss(4 ) тзЮ

78Щ тл 4

Составитель H. Маркелова

Редактор М, Бандура Техред M.Õoäàíè÷ Корректор И, Муска

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

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

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

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