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

(59 4 0 06 Г 7 49 ОПИСАНИЕ ИЗОБРЕТЕНИЯН д ВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(56) Авторское свидетельство СССРВ 1170450, кл. О 06 У 7/49, 1984.Авторское свидетельство СССРУ 1160398, кл. 0 06 Р 7/49, 1983.(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПО МО" ДУЛЮ 2 -1 (р-нечетное)Р(57) Изобретение относится к вычислительной технике и технической кибернетике и может быть использованов устройствах для цифровой обработки сигналов (в частности изображений), а также в системах кодирования,принцип действия которых базируетсяна теории полей Галуа. Цель изобретения - сокращение аппаратурных затрат. Поставленная цель достигаетсятем, что вводятся 31-разрядный 1=(р+1)/2 1 сдвиговый регистр, группа рмультиплексоров, р-разрядный регистробратной связи и блок синхронизации,что позволило организовать анализгрупп из одного, либо трех разрядовмножителя и последовательно накапливать сумму в регистре обратной связи. с4 ил.Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в устройствах для цифровой обработки сигналов (в частности, изображений), а также в устройствах кодирования, принцип действия которых базируется на теории конечных колец.Цель изобретения - сокращение аппаратурных затрат.10 1На фиг. 1 изображено устройство для умножения по модулю 2 в . 1; наРфиг. 2 - блок синхронизации; на фиг. 3 - блок коррекции результата; 15 на фиг. 4 - временная диаграмма работы блока синхронизации в устройстве для умножения по модулю 2 -1 в случае р=7.РУстройство для умножения по модутпо 20 2 -1 (фиг.1) содержит регистр 1 сдвига, группу элементов И 2,-2 сумматор 3, регистр 4 хранения, блок 5 коррекции результата и блок 6 синхронизации. 25Блок 6 синхронизации (фиг. 2) содержит КЯ-триггеры 7,8 и 9, элементы 10 И и элемент 11 ИЛИ, элемент 12 НЕ, элементы 13, 14 ИЛИ, регистр 15 сдвига, элемент 16 И, элемент 17 ИЛИ, 30 тактовый вход 18, вход 19 логического "О", вход 20 логической "1", входы 21,22 пуска и установки устройства, первый, второй и третий выходы 23,24 и 25 блока 6.35На чертежах обозначено 0 с индексом - информационные входы регистров сдвига и реГистра хранения; Я - выходы регистров сдвига, регистра хранения и прямые входы ВЯ-триггеров; В - 40 входы сброса регистров сдвига и регистра хранения; С - входы синхронизации регистров сдвига и регистра хранения; ВВ - вход разрешения сдви га регистров; ЯО - вход режима; А,В - 45 входы первого и второго слагаемых сумматоров; Я с индексом - выходы суммы сумматоров; Р и Р - соответственно вход и выход переноса сумматоров. 50Блок 5 коррекции результата (фиг,3)содержит элемент 26 И-НЕ и группуэлементов 27 И.На временной диаграмме (фиг. 4)21,24,23,25, и Гт, КО 15 (о),Т 7 (ц,), Т 8 (ц,), Т 9обозначаютэпюры напряжений в соответствующихточках .блока синхронизации,Устройство для умножения чисел помодулю 2 - 1 работает по алгоритму,Ркоторый заключается в следующем.Пусть А=2 а +2 -2 а+Р.1 Р-2 а, +ае - множимое, а В=2 Ь Р, ++2 Ь 2 Ь, +Ь - множитель,Запишем произведение А.В в виде:А В=А Ьа+2 Ь, А+2 Ь,А2 Ьр-гА+2Ь , А, (1)Таким образом, для того, чтобы умножить А на В необходимо А гдеА=2 А(3.=0,1, ,р), умножить соответственно на Ь, с последующим суммированием сформированных частичныхпроизведений. Поскольку Ь можетпринимать только два значения - 0 и11, то частичное произведение А,Ь;будет равно нулю при Ь; =О и А приЬ=1,Для сокращения аппаратурных затрат при реализации этого алгоритмаудобно произведение А.В с учетом раевенства 2.=1 шос 1(2 -1) представить ввиде:А В=А Во+2 АЬ 1+2 А Ь +,2 А Ь, +2(А.Ь., ДЯ. 2)1Устройство для умножения чисел по шой (2 -1) работает следующим образом.Множитель В, представляющий собой число, не превышающее 2 -1 и кодируеРмое двоичным кодом, т,е, представляемое в двоичной системе счисления р. - разрядным двоичным числом, подается на входы В 0 , сдвигового регистра 1. Множимое А, представляющее собой число, не превышающее 2 -1 иР кодируемое двоичным кодом, т.е. представляемое в двоичной системе счисления р-разрядным двоичным числом, подается на первые входы группы элементов И 22 Р, вторые входы которых объединены и соединены с выходом Осдвигового регистра 1. Таким образом, прохождением множимого А через группы элементов И управляют разряды множителя В начиная со старшего разряда, В начале работы устройства или после включения питания на вход 22 блока 6 необходимо подать импульс начальной установки, который сбрасывает (1+1)-разрядный сдвиговый регистр 15 блока 6 в нулевое состояние (в данном варианте 1=р), что включает за собой установку КЯ-триггеров 7 и 9 в состояние логического "0". После подачи разрядов множителя В и множимого А на со 1304019ответствующие входы устройства для выполнения их перемножения на вход 21 блока б необходимо подать импульс "Пуск". Импульс "Пуск" с выхода 24 блока 6 подается на вход ЯО установки 5 режима сдвигового регистра 1, а также подается непосредственно на вход БО установки режима сдвигового регистра 15 блока 6, Тот же импульс через элемент 17 ИЛИ с некоторой задержкой, позволяющей установиться режиму "Запись" в регистре 1, поступает с выхода 23 блока 6 на тактовый вход С регистра 1, производя тем самым запись разрядов множителя В в регистр 1, а также через элемент 14 ИЛИ он поступает на тактовый вход С сдвигового регистра 15, производя тем самым запись единицы в разряд Я и нулевой в разряды Ц,+Я регистра 20 15, так как вход Р регистра 15 соединен с шиной единичного потенциала, а входы В -В соединены с шиной нулевого потенциала. С выхода Я регистра 15 единичный потенциал подается на вход В ВБ-триггера 8, на вход которого подан потенциал логического "0" с выхода Я регистра 15, Тем самым, триггер 8 устанавливается в нулевое состояние и с него через выход 25блока 6 поступает сигнал сброса на регистр 4, имеющий нулевой уровень активности по выходу В. Импульс "Пуск" поступает также на вход Б триггера 7 и, включая его в ецинич ное состояние, разрешает прохождение инверсной тактовой частоты через элемент 10 И, с выхода которого она подается на первый вход элемента 14 ИЛИ.1 40В результате после подачи импуль 1са Пуск происходит запись множителя В в регистр 1, установка регистра 15 в состояние единицы только на выходе И 0, сброс регистра 4, а также 45г открывается прохождение инверсной тактовой частоты на тактовый вход С регистра 15. После окончания импульса "Пуск" регистры 1 и 15 переводятся в режим Сдвиг путем подачи на 50 их входы БО потенциала логического1 110 с шины , на которую поступает импульс "Пуск " . С выхода Ц, регистра1 на вторые входы группы элементовИ 2, ,. , 2подается разряд дмножителя В , и в зависимости от е го значения 0 или 1 на выходах этой группы элементов И появляются либо нули , либо разряды множимо го А , которые подаются на входы В,Всумматора 3, на входы А,.1которого поданы логические "0" с выхода регистра 4, Для обеспечения работы сумматора 3 по шой(2 - 1) его выРход р переноса соединен с входом Гпереноса, поскольку на выходе р появляется двоичное число с весом 2",а 2 1 шоц.(2 - 1),В случае подачи на вход Р переноса единицы с выхода Р переноса ещеодин перенос принципиально возникнуть не может. Это видно из следующего: максимально возможные по величине числа, суммируемые таким сумматором, равны 2 -1, при их сложении получается число 2(2 -1), представляемое в двоичном коде Р единицами и одним нулем в младшем разряде 110, и потому при переносе старшей единицы в младший разряд еще один перенос не возникает. В результате через интервал времени, равный сумме времени появления сигнала переноса на входе р сумматора 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 А.Ь , а на выходеЯ Р 1 регистра 1 появляется разрядЬ Р множителя Б, подающий на входыВ В ., сумматора 3 двоичный код, 1 Осоответствующий произведению ЬрА. С приходом следующего положительного перепаца инверсной тактовой частоты регистр 15 блока 6 переключа ется в состояние с присутствием логической "1" только на выходеа сумматор 3 в это время производит сложение кода ЬРА, поступающего с выходов элементов 7 И, и кода, соот ветствующего произведению 2 А Ь Рпоступающего с выходов регистра 4 на входы А А 2сумматора 3. С приходом положительного перепада прямой тактовой частоты на тактовый вход регистра 4 с выхода 23 блока 6 в регистр 4 записывается двоичный код, соответствующий значению 2(А ЬР. + +2 А ЬР.1 ), и по этому же перепаду в регистре 1 снова происходит сдвиг 30 кода множителя В и на выходе регистра 1 появляется разряд ЬРмножите-, ля В. Аналогично после переключения регистра 15 в состояние с логической "1" только на выходе Я 1, а затем 35 с приходом положительного перепада напряжения прямой тактовой частоты в регистр 4 происходит запись двоичного кода соответствующего значению 2(А Ь 1+2(А Ьт+ +2(А Ь- +2(А Ь40 , а на выходе И.,1 регистра 1 появляется разряд Ь множителя В. При поступлении положительного перепада инверсной тактовой частоты регистр 15 переключается в состояние 45 с присутствием единицы только на выходе Я, устанавливая через элемент 13 ИЛИ триггер 9 в состояние логического "О", блокируя тем самым прохождение прямой тактовой частоты. Сум матор 3 в это время производит сложение двоичного кода, соответствующего значению А Ь , и двоичного кода,осоответствующего значению 2 А.Ь, + +2 А Ь 2 А Ь, +2 А Ь 1 + +2(А ЬР.1 )1. . В результате на выходах сумматора 3Ю Р, 1 появляется значение двоичного кода, соответствующего значению произведения АВ, равного:А Ь 2 А В,+2(А Ь2 . Ь . 2(. Ь, Д .Этот двоичный код с выходовсумматора 3 поступает на входы блока 5, устраняющего неоднозначностьРпредставления нуля по модулю 2При необходимости умножить два числа нужно подать импульс Уст" затем подать на входы устройства двоичные коды множимого и множителя, а потом подать импульс Пуски. Описанная работа устройства повторяется.Формула изобретенияУ"тройство для умножения по модулю 2 в(р-нечетное), содержащее сумРматор и блок коррекции результата, причем выход суммы сумматора соединен с входом блока коррекции результата, выход которого является выходом результата устройства, о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, в него введены регистр сдвига, группа мультиплексоров, регистр хранения и блок синхронизации, причем -й инФормационный вход регистра сдвига (Где 1=0 1 С- С- ) являетсяр+1входом (р-1)-го разряда. множителя устройства, С-й информационный вход регистра сдвига является входом нулевого разряда множителя устройства, 1-й информационный вход регистра сдвига (где =С+ 1-.+2, , С) яв - ляется входом ( р(1-С)-2 разряда множителя устройства, 2 С-й информационный вход регистра сдвига соединен с входом нулевого разряда множителя устройства,к-й информационный вход регистра сдвига (где К=(2 С+1) х(21+2)(ЗС) является входомр(К-(2 С) - 1) разряда множителя устройства, выходы (С-)-го и (2 С- -1)-го и (ЗС)-го разрядов регистра сдвига соединены соответственно с первым, вторым и третьим управляющими входами Б-х мультиплексоров группы (где Б=23 р) первый инФормационный вход Я-го мультиплексора группы соединен с шиной логического нуля устройства, второй информационный вход первого мультиплексора группы является входом (р)-го инверсного разряда множимого устрой130401 ства, второй информационный вход О-го мультиплексора группы (где с= 2,3 р) является входом (Ч)-го инверсного разряда множимого устройства, третий информационный вход 5 Я-го мультиплексора группы является входом (Я)-го разряда множимого устройства, четвертый информационный вход Я-го мультиплексора группы является входом (Я)-го инверсного раз ряда множимого устройства, пятый информационный вход Я-го мультиплексора группы соединен с третьим информационным входом Я-го мультиплексора группы, шестой информационный вход которого соединен с четвертым информационным входом Я-го мультиплексора группы, седьмой информационный вход первого мультиплексора группы соединен с входом (р)-го разряда множимого устройства, седьмой информационный вход с 1-го мультиплексора группы соединен с входом (Ч)-го разряда множимого устройства, восьмой информационный вход Я-го мультиплексора группы соединен с первым входом Я-го мультиплексора группы и с входом разрешения сброса регистра сдвига, выход Я-го мультиплексора группы соединен с первым информационным входом Я-го разряда сумматора, второй информационный вход Я-го разряда которого соединен с выходом Я-го разФ 9 8ряда регистра хранения, информационный вход г-го разряда которого (где г=1,2,3 р) соединенс выходом суммы (г+2)-го разрядасумматора, выход первого и второгоразрядов суьщы которого соединенысоответственно с информационными входами (р)-го и р-го разрядов регистра хранения, выход переноса сумматора соединен с входом переноса сумматора, вход пуска устройства является входом пуска блока синхронизации,установочный вход которого являетсявходом установки устройства, первыйвыход блока синхронизации соединен свходом сброса мультиплексоров группыи входами синхронизации регистровсдвига и хранения, вход разрешениясдвига регистра сдвига соединен свторым выходом блока синхронизации,третий выход которого соединен с входом сброса регистра хранения, блоккоррекции результата содержит элемент И-НЕ и группу элементов И, причем 1-й вход элемента И-НЕ (где 1=1,2 р) является входом 1-го разря-да блока коррекции результата и соединен с первым входом 1-го элементаИ группы, второй вход которогосоединен с выходом элемента И-НЕ,выходы элементов И группы являются выходами блока коррекции.результата.1304019 Составитель Н. Маркелова Бандура Техред М.Ходанич Корректор И. Медакт Подпмитета СССРоткрытийская наб д аказ 16 о ВНИИПИ Гпо дел113035,5 Ужгород, ул. Проектная,водственно-полиграфическое предприя Тираж осударстве ам изобре Москва, Ж 673 ного ений 5, Р ЖЮ еЮ ю) ЖЖ) ГЮ%а) тзЮ тад