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

) (11) Р 749 ОПИСАНИЕ ИЗОБРЕТЕНИЯ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ К АВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство СССР В 9002811 кл. С 06 Г 7/52 ф 1979Авторское свидетельство СССР У 959068, кл. С 06 Р 7/52, 1980.Патент Японии В 54-20102, кл. С 06 Р 7/39, опублик. 1979.Авторское свидетельство СССР В 1160398, кл, С 06 Г 7/49, 1983. (54) МАТРИЧНОЕ УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО ЮДУЛЮ 2"-1(57) Изобретение относится к области вычислительной и технической кибернетики и может быть использовано в устройствах для цифровой обработки сигналов (в частности изображений), а также в системах кодирования, принципдействия которых базируется на теории полей Галуа. Целью изобретения является повышение быстродействия устройства. Поставленная цель достигается тем, что блок суммировайия частичных произведений выполнен в виде древовидной группы линеек, блок коррекции результата содержит и-входовой элемент И-НЕ и группу и элементов И, введены группа элементов И и группа сумматоров по модулю два. Введение группы элементов И и группы сумматоров по модулю два и новых связей, ас также новое выполнение блока суммиро вания частичных произведений и блока коррекции результата позволило повысить быстродействие устройства. С: 2 э. п. ф-лы, 6 ил.Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано вустройствах для цифровой обработкисигналов (в частности, иэображений), 5а также в системах кодирования, принцип действия которых базируется натеории полей Галуа.Целью изобретения является повыше ние быстродействия устройства. ОНа фиг,1 приведена схема матричного устройства для умножения чисел помодулю 2 - 1; на фиг,2 - блок формирования частичных произведений, нафиг.З - блок суммирования частичных 15произведений, на фиг.4 - блок коррекции результата; на Фиг.5 - групга линеек одноразрядных сумматоров; нафиг.б - примеры построения блока суммирования частичных произведений для 20конкретных значений п,Матричное устройство для умножениячисел по модулю 2 - 1 (фиг,1) содержит блок 1 Формирования частичныхпроизведений, блок 2 суммирования 25частичных произведений, п-разрядныйсумматор 3, блок .4 коррекции результата, группу (п) элементов И 5 игруппу сумматоров 6 по модулю два. Ви-разрядном сумматоре 3 р - вход пе- ЗОреноса, р - выход переноса, А - входыпервого слагаемого, В - входы второгослагаемого, Б - выходы суммы,Блок 1 Формирования частичных произведений (фиг,2) состоит из двухвхо- З 5довых элементов И 7.Блок 2 суммирования частичных произведений (фиг.З) состоит из группылинеек 8 одноразрядных сумматоров,Ч,Ч- входные слова блока сум Омирования частичных произведений, Ц,Ч - его выходные слова.Блок 4 коррекции результата(Фиг,4) состоит иэ и-входового элемента И-НЕ 9 и группы элементов И 10.Линейка длины п (Фиг.5) состоитиз одноразрядных сумматоров 11, ЬЬ , Ь - входы линейки, Ю - выходыслова суммы линейки, Ч - выходы словапереноса линейки, Я - вьгход суммь одноразрядного сумматора, р - выход переноса одноразрядного сумматора,Матричное устройство для умножениячисел по модулю 2 - 1 выполняет умножение двух и-разрядных двоичных чи 55сел по модулю 2" - 1. Устройство работает следующим обра.эом. Множимое А = а 2" + а"2"+ + а 2+ а, и множитель В = Ь 2"+ +Ь, 2" ++Ь 2+Ь, поступают на входы блока 1 формирования частичных произведений, Блок 1 образует попарные произведения а,Ъ; (11, 2.и; 3 = 1,и). Произведения разрядов множимого на младший разряд множителя аЬ образуют слово Ч, частичных произведений первой ступени, произведения разрядов множимого на второй разряд множителя а;Ъ обруэуют слово Ч частичных произведений второй ступени, , произведения разрядов множимого на старший (и-й) разряд множителя а;Ьобразуют слова Ч частичных произведений и-йоступени, причем в -м разряде словаЬ = 1,и) стоит произведение а Ъ где 1 с = (3 - 1 + 1) Мой,А) х х Мос 1 п .= п при й кратном и, (А) Модп равно целому положительному остатку от деления А на и при А не кратномп). Другими словами, блок 1 формирует циклически сдвинутые по сравнению со случаем обычного множителя слова, такФ как умножение на число вида 2 равносильно циклическому сдвигу влево на к разрядов и-разрядной двоичной записи множимого (потому что 2 сов- падает с единицей по модулю 2 - 1), Таким образом, блок формирования частичных произведений образует следующие слова:=аЬа,Ь аЬаЪ,;Ч = ,Ъ, аЬ аЪ,а" Ч = аЬ, а, Ъ, ,а Ь,а,Ь Ч =аЬ, аЬ аЬ, аЬ.Блок 2 суммирования частичных произведений представляет собой древовидную структуру из группы линеек 8 одноразрядных сумматоров, Число с линеек одноразрядных сумматоров в первой группе линеек задается соотноГ ишением с - - " где обоэнача 3 3ет целую часть числа. На первые третьи входы всех линеек первой группы линеек блока 2 суммирования частичных произведений поступают Зс слов с блока 1 формирования частичных произведений (по три слова на каждую линейку), Каждая линейка 8 состоит иэ и одноразрядных сумматоров 11. В ней происходит поразрядное сложение трех п-разрядных слов Ь Ь , Ь и обра 1254411эуется два и-разрядных результирующих слова У и Ч. Слово Б состоит из значений на выходах суммы одноразрядных сумматоров, причем 3-й разряд слова Ц = 1, 2, , П) совпадает со значением на выходе суммы 3-го сумматора, Слово Ч состоит из значений на выходах переноса одноразрядных сумматоров, причем 3-й разряд этого слова (3 = 2.П) совпадает с Означением на выходе переноса Ц)- го сумматора, а первый разряд - с значением на выходе переноса и-го сумматора (так как 2 совпадает слединицей по модулю 2 - 1), На выхо дах линеек первой группы в результате сложения формируется 2 с слов, Кроме того, имеем и - Зс входных слов, блока 2 суммирования частичных произведений, которые не поступили на вхо ды линеек первой группы. Общее число слов после прохождения первой группы линеек древовидной структуры равно 2 с + и - Зс, = и - с. Число сг линеек во второй группе линеек задается 25и - с,выражением с =--- т, е, навходы линеек второй группы поступаютЗс слов из числа и - с, слов, Навыходах линеек второй группы послесложения образуется 2 сг слов, Общеечисло слов после прохождения второйгруппы линеек равно 2 с + п - с, -Зсг = и - с, - с . Число сэ линеекв третьей группе задается соотношениП С Сгемс =- ------- т, е, на3:входы линеек третьей группы поступаютЗс слов из чистка и - с, - сг слов4 ОНа выходах линеек третьей группы после сложения образуется 2 с слов, Общее число слов после прохождения третьей группы линеек равно 2 с+ и --с -с -Зс =и - с -с -с452г ЭфЧисло с 4 линеек в четвертой группелинеек задается выражением с,Г и - с - с, - с= ----- - -- ит, д,350Число Е групп линеек выбираетсятаким образом, чтобы после прохождения Е группы образовалось два слова,которые являются выходными словами0 и Ч блока 2,55Результирующие слова П и Ч складываются с помощью и-разрядного сумматора 3. Если перенос при сложении не возникает, то на выходах всех элементовИ 5 в нулевые значения. На выходысумматоров 6 по модулю два пропускается код с выходов блока 4 коррекциирезультата, В случае, когда хотя быодин из разрядов суммы на выходахсумматора 3 отличен от единицы, навыходе элемента 9 И-НЕ логическаяединица, и полученная сумма проходитна выходы элементов И 10 и далее на,выходы устройства.В случае равенства всех разрядовсуммы на выходах сумматора 3 единицена выходе элемента И-НЕ 9 - логический нуль, и на выходах блока 4 всенули, которые проходят на выходы устройства.Таким образом, происходит устранение неоднозначности представления нуля в устройстве, возникающее из-заравенства слов 000 и 111и-разрядов и-разрядовпо модулю 2" -1,Если возникает перенос при сложении результирующих слов П и Ч, тоего необходимо прибавить в младшийразряд полученной суммы, Заметим,что, так как каждое из слагаемых, поступающих на сумматор 3 не превьппалУет 2 -1, то полученная сумма с учетом йереноса не больше 2" ++ (2 - 2), а сумма без учета пелреноса не больше 2 - 2. Это означает, что хотя бы один разряд сум-.мы отличен от единицы, и она проходитна выходы блока 4 коррекции результата. Элемент Б;(х = 1, , и - 1)формирует перенос из д-го в (+1)-йразряд при добавлении единицы к полученной на выходах сумматора 3 суммы,Перенос из х-го в (1+1)-й разряд равен единице, если разряды Б Я;суммы равны единице, Сумматорь б помодулю два прибавляют образованныепереносы к соответствующим разрядамполученной суммы.На выходах устройства получаемпроизведение А В по модулю 2"-1,Формула изобретения1. Матричное устройство для умнойкения чисел по модулю 2 -1, содержацее блок формирования частичных произведений, выполненный в виде матрицы и х и элементов И (и - разрядность множимого и множителя), блок суммирования частичных произведений, 5 1254и-разрядный сумматор, блок коррекциирезультата, причем первые входы элементов И 1-й строки матрицы (11, 2 и) соединены с входом 1-горазряда множителя устройства, вторыевходы (, 3)-х элементов И (3-номерстолбца матрицы, 1 = 1, 2и) соединены с -м разрядом входа множимогоустройства, где Е = (3 - 1 + 1) Мос 1 иА) Мой и = и при А кратном и, 10(А) Можаи равно положительному остатку от деления А/и при А не кратноми), выходы элементов И 1-й строки матрицы соединены с информационнымивходами 3-х разрядов -го слова блока 15суммирования частичных произведений,выходы разрядов первого и второго результирующих слов которого соединеныс информационными входами первого ивторого слагаемых и-разрядного сумма Отора, вход переноса которого соединен.с шиной логического нуля, группа выходов суммы которого соединена с группой входов блока коррекции результата, о т л и ч а ю щ е е с я тем, 25что, с целью повышения быстродействияустройства, в него введена группа из(и) элементов И, р-й (р = 1, 2и) элемент И имеет (р+1) входов игруппа и сумматоров по модулю два,причем и-й (ц = 1, 2 р) вход рго элемента И группы соединен с о-мвыходом суммы и-разрядного сумматора,выход переноса которого соединенс(р+1)-ми входами элементов И группыи первым входом первого сумматора помодулю два группы, выходы элементовИ группы соединены с первыми входамисумматоров по модулю два группы с второго по и-й соответственно, вторые 40входы которых соедннены соответственно с выходами блока коррекции результата, выходы сумматоров по модулю дваявляются выходами устройства,2. Устройство по п.1, о т л и ч аю щ е е с я тем, что блок коррекциирезультата содержит и-входовый элемент И-НЕ и группу и элементов И, причем входы элемента И-НЕ, являющиесявходами блока коррекции результата,соединены соответственно с первымивходами элементов И группы, вторыевходы которых соединены с выходомэлемента И-НЕ, а выходы элементов И:группы являются выходами блока кор-.рекции результата.3, Устройство по п.1, о т л и ч аю щ е е с я тем, что блок суммирова471 ния частичных произведений состоит из групп линеек длиной и одноразрядных треходовых сумматоров, причем число линеек с в а-й группе линеек задается соотношением(ш = 2 - 1 с), смвъвФ 3 где 1 ) - целая часть числа; 1 - число групп линеек, число, линеек в первой группеГ и 1линеек равно с, =-3-)"г-й вход (г = 1, 2, 3) З-го. (3 = 1, 2 и) трехвходового одно-разрядного сумматора 3-й линейки (1 - номер линейки) первой группы линеек соединен с входом 3-го разряда 1-го частичного произведения (где д = 3(т. - 1) + г) блока суммирования частичных произведений, первый вход 3-го (3 = 1,и) сумматора Р-й линейки (Р - нечетное) ш-й группы линеек соединен с выходом суммы31-1 3-го сумматора 2й линейки (ш-.1)-й группы линеек, второй вход первого сумматора 1-й линейки ( 1 - нечетное) ш-й группы линеек соединен с выходом переноса и-го сумматора 31 - 1 ---- -й линейки (а)-й группы2 линеек, второй вход р-го сумматора (ри) т,-й линейки (т, - нечетное) а-й группы линеек соединен с выходом переноса (р)-го сумматора 31-1линейки (ш)-й группы линеек, третий вход 3-го сумматора М-й (т, - нечетное) линейкн а-й группы линеек соединен с выходом суммы 3-гоЗт.-1 сумматора ----- -й линейки (ш)-й 2/ группы линеек, первый вход р-го сумматора 1-й линейки (2 - четное) ш-й группы линеек соединен с выходом пеЗР - 2 реноса (1-1) -го сумматора ---- -й2 линейки (а)-й группы линеек, первый вход первого сумматора т,-й линейки (Г - четное) и ш-й группы линеек соединен с выходом переноса иек, третий вход р-го сумматора 102-й линейки (Р - четное) щ-й группы линеек соединен с выходом переноса 1ЗР - 2го сумматора ---- -й линейки2(щ)-й группы линеек, второй вход 1-го сумматора 1-й линейки (0 - четное) щ-й группы линеек соединен с выходом суммы 1-го сумматора 31-- -й линейки (щ)-й группы лине ЗР(щ)-й группы линеек, третий входпервого сумматора 1-й ( Г - четное)линейки п 1-й группы линеек соединен свыходом переноса и-го сумматора 32-- -й линейки (щ)-й группы лине 254471 8ек, свободные входы сумматоров последней линейки щ-группы линеек соединены с выходами суммы или переносасумматоров линеек группы линеек предыдущих 1 (щ)-,й группе линеек, либос входами разрядов соответствующихслов (из оставшихся (и - Зс блокасуммирования частичных произведений,выход суммы 1-го сумматора линейки1-й группы линеек является выходом1-го разряда первого результата блокасуммирования частичных произведений,выход переноса р-го сумматора 1 с-йгруппы линеек является выходом (р+1)- 15 го разряда второго результата блокасуммирования частичных произведений,выход переноса и-го сумматора линейки,К-й группы линеек является выходомпервого разряда второго результатаблока суммирования частичных произведений..а ЬаЬ ад рЬф аеЬ аЬ,а,Ь а Ьд кЬ ап-Ьз аапЬ аЬ Ф Ф 1254471Ц аиЬ агмЬ . аЬю ать да Ь а ьаЬ аь д а.р Ь а.Ьа ва.ад1 254471 п 13 п=Я ктор Н,Сл н Заказ 4721/52 н 5 зводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная,%ПИ Госуда по делам и 35, Москва, оставитель Н.Маркелова,ехред Л.Сердюкова Корректор д.Патай ираж 671 По твенного комитета СССРбретений и открытий