Матричное множительное устройство

)-го эле частнч - гй ед ен с выходИ блока фо оиэведе -ь 1+ 1 мен ний)Мой ОСУДАРСТВЕННЬЙ КОМИТЕТ СССПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ПИСАНИЕ ИЗО АВТОРСНОМУСВИДЕТЕЛЬ свидетельство СССР06 Р 7/52, 1978.Р 403093,опублик. 1977.свидетельство СССР06 Р 7/52, 1979 еР., Гоулд Б. Теорияровой обработки сиг1978, с. 574-575,(54) (5) МАТРИЧНОЕ МНОЖИТЕЛЬНОЕ УСТРОЙСТВО, содержащее блок формирования частичных произведений, выполненный в виде матрицы и х и элементов И ( 11 - разрядность множимого и множителя) и блок суммирования частичньи произведений, выполненный в виде древовидной матрицы 1 х 0 н - разрядных сумматоров (С1 о 8, и количество ярусов в матрице, 0, щ2 1 - количество и -разряднйхсумматоров в-м ярусе матрицы, где= 1,ь ), причем первые входы элементов И 1 -й строки матриФцы соединены с входом-го разряда множителя устройства (1 1, , л ), л 1-й разряд множимого которого соединен с вторыми входами ( 1, гй )-х элементов И блока формирования частичных произведений (1 п = 1, , й ),а в блоке суммирования частичных произведений выходы суммы (2 11)"го П-разрядного сумматора.г -го яруса матрицы (= 1, ,- 1, с а 1,." 2 ) соединены с входами перво го слагаемого 1 -го 11 -разрядного сумматора ( г + 1)-го яруса матрицы, входы второго слагаемого которого соединены с выходами суммы 2-го и-разрядного сумматора Г -го яруса. матрицы, входы переносов И -разрядных сумматоров первых ярусов матрицы соединены с шиной нулевого потенциала, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей эа счет обеспечения умножения О -разрядных двоичных чил сел по модулю 2 - 1, в него введены первый и второй О -разрядные сумматоры, блок коррекции переносов, выполненный в виде древовидной матрицы .р х 7 сумматоров ( - 1, 1 - 2 - количество ярусов в матрице,72- количество сумматоров в-м ярусематрицы), поичем-й ярус сумматоров матрицы состоит иэ-разрядных сумматоров и блок коррекции результата, содержащий 11 -входовый элемент И и 11 -разрядный сумматор, причем-й вход первого слагаемого-го Ь -разрядного сумматора первого яруса матрицы блока суммирования частичных произведений (В = 1.И /2 для. п четного, Р еД + 1 для л нечетного)0450 117 + 1 А, где А Мой и = й при кратном и, А Иод " и + Я при АО,Айова= А при ЯО), выход (1,Ф )-го элемента И которого (Ф = 2 Р,", (- П 1 + + 1)Иосип) соединен с 1 -м входом второго слагаемого-го н -разрядного сумматора первого яруса матрицы блока суммирования частичных про.изведений, выход переноса (2- 1)-го П-разрядного сумматора 1 -го яруса матрицы которого соединен с входом переноса-го 11 -разрядного сумматора (и + 1)-го яруса матрицы блока суммирования частичных произведений выходы переноса 21-х П -разрядных сумматоров первого и второго ярусов матрицы которого соединены с соответствующими входами одноразрядных сумматоров первого яруса матрицы бло 3 ка коррекции переносов, входы переноса-разрядных сумматоров -го1 яруса матрицы которого (= , 3,2) соединены с соответствующими выходами переноса 21-х й -разрядных сумматоров-го яруса матрицы блока суммирования частичных произведений ( Г = 3, ,- 1), выходы суммы и выход переноса-го яруса матрицы которого соединены соответственно с входами первого слагаемого и входом переноса первого и Ь -разрядного сумматора, первые2 выходы второго слагаемого и ( 1 - 1)-й вход второго слагаемого которого соединены соответственно с выходами суммы и переноса ( 1 - 2)разрядного сумматора ( 1 - 2)-го яруса матрицы блока коррекции переносов, выходы суммы (22 - 1)-го р -разрядного сумматора-го яруса матрицы которого соединены с входами перво 1го слагаемого-го ( + 1)-разряд 3ного сумматора (+ 1)-го яруса матрицы, блока коррекции переносов ( Х = 1, 2, , 2), входы второго слагаемого которого соеди иены с выходами суммы 27, -го-раз 1рядного сумматора-го яруса матрицы блока коррекции переносов, выходы суммы и выход переноса первого п -разрядного сумматора соединены соответственно с входами первого слагаемого и входом переноса второго и -разрядного сумматора, выходы суммы которого соединены с входази П -входового элемента И и входами первого слагаемого П -разрядного сумматора блока коррекции результата, выход И -входового элемента И соединен с входом переноса П -разрядного сумматора блока коррекции результата, выходы суммы которого соединены с выходами результата устройства, входы второго слагаемого ив разрядного сумматора блока коррекции результата,-е входы второго слагаемого первого- разрядного сумматора=, , П ) и входы второго слагаемого второго й - разрядного сумматора соединены с шиной нулевого потенциала.Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в устройствах для цифровой обработки сигналов, а также в системах кодирования, принцип действия которых базируется на теории конечных полей (полей Галуа).Известен матричный умножитель, содержащий матрицу элементов И и параллельные сумматоры 11.Известно матричное множительное устройство, содержащее регистры сомножителей, коммутаторы, регистр сдвига, регистр задержки, регистры слов первого и второго сомножителя, две матрицы умножения, сумматоры и блок управления 21 .Однако низкое быстродействие, а также невозможность выполнения операции умножения чисел по модулю, отличному от 2", снижает функциональные воэможности известных устройствИзвестно устройство для умножения в поле Галуа, содержащее и - 1 модульных блоков умножения 33 .Недостаток этого устройства заключается в отсутствии воэможности1170450производить умножение в полях, число соединены с входами первого слагаемо"элементов которых отлично от степе- го 1 -ого О -разрядного сумматорани двойки, а также невозможности ( Р + 1)-го яруса матрицы, входы втоего использования в качестве обычного рого слагаемого которого соединеныумножителя чисел. 5 с выходами суммы 21-го й -разрядногоИзвестно устройство для умножения сумматора г -го яруса матрицы, входыпроизвольных элементов полей Галуа переносов л -разрядных сумматоров пер"СР("), состоящее иэ и модульныхвых ярусов матрицы соединены с шинойблоков умножения, и блоков формиро- нулевого потенциала, введены первыйвания частичных произведений и10 и второй п -разрядные сумматоры, блокблоков суммирования 41. коррекции переносов, выполненный вНедостатком известного устройства виде древовидной матрицы о х 4является то, что оно базируется на сумматоров (= 1.- 2заданном устройстве умножения по мо- количество ярусов в матрице, Удулю простого числаМ2- количество сумматоров вНаиболее близким по технической "м ярусе матрицы), причем-йсущности к изобретению является мат- ярус сумматоров матрицы состоит изричный умножитель с древовидной -разрядных сумматоров, и блок корструктурой, содержащий схему форми- рекции результата, содержащий й -вхорования частичных произведений, . 2 О довой элемент И и О-разрядный сумпредставляющую собой матрицу из Е х П матор, причем ) -й вхоД первогоэлементов И, схему Формирования ре- слагаемого 1 -го 11 -разрядного сумэультата, представляющую собой дере-. матора первого яруса матрицы блокаво сумматоров Г 53,суммирования частичных произведеДанное устройство характеризуют 25 ний ( 61, , й/2 для 11 четного,низкие функциональные возможности, ,3 = 1, , п + 1 для п нечетногосвязанные с невозможностью умножения 2по модулю, отличному от степени соединен с выходом (, щ )-го эледвойки. мента И блока формирования частичЦель изобретения - расширение ЗО ных произведений (тй = 2 3 - 1,функциональных возможностей за счет( 1 - 1 п + 1)Иода, причем- е.+обеспечения умножения по модулю М щ + 1Д, где Д Иод ПР при А кратф 2 - 1ном и, А Иосип а+4 при А с 0,Поставленная цель достигается тем,; А Иод о1 при АО), выход (1, м ) -гочто в матричное множительное устрой- З 5 .элемента И которого (щ " 23фаЮство, содержащее блок формирования (,1 - Ф + ф 4 ойи) соединен с-мчастичных произведений, выполненный ,входом второго слагаемого 1 -го ив виде матрицы Ох л элементов И разрядного сумматора первого яруса( й - разрядность множимого и множи- матрицы блока суммирования частицтеля), и блок суммирования частичных 40 ных произведений, выход переноса,произведений, выполненный в виде (2 11)-го-разрядного сумматорадревовидной матрицы т,О и-разряд" Р "го яруса матрицы которого соединых сумматоров ( 1 1 оя п - коли; нен с входом переноса 1 -го П -разчество ярусов в матрице, Ц2- рядного сумматора (+ 1)-го ярусаколичество и-разрядных сумматоров М матрицы блока суммирования частичв 1-м ярусе матрицы, где 11. ,ных произведений, выходы переноса1), причем первые входы элементов И 21-х Ь -разрядных сумматоров перво-ой строки матрицы соединены с вхо- го и второго ярусов матрицы котородом-го разряда множителя устрой- го соединены с соответствующими вхоства (= 1, , и ), в -й разряд 50 дами одноразрядных сумматоров первомножимого которого соединен с вто- го яруса матрицы блока коррекциирыми входами (, в )-х элементов И переносов, входы переноса-разрядфблока формирования частичных произ- ных сумматоров-го яруса матриведений (Ф= 1, ,и ), а в блоке цы которого2, , 1 - 2)суммирования частичных произведений 55 соединены с соответствующими выходавыходы суммы (2 1 - 1)-го и -разрядно- ми переноса 21-х и -разрядных суммаго сумматора г -го яруса матрицы , торов г -го яруса матрицы блока сум( Р = 1.1 - 1, 1 с 1, ,2 ), мирования частичных произведений( " 5, , 1 - 1), выходы суммы и выход перекоса 1 -го яруса матрицы которого соединены соответственно с входами первого слагаемого и входом 5 переноса первого о -разрядного сумматора, первые 1 - 2 входы второго слагаемого и (1 - 1)-й вход второго слагаемого которого соединены соответственно с выходами суммы и переноса ( 1 - 2)-разрядного сумматора ( 1 " 2)-го яруса матрицы блока коррекции переносов, выходы суммь (211)-го-разрядного сумматора-го яруса матрицы которого соединены с входами первого слагаемого 2-го ( + 1)-разрядного сумматора (+ 1)-го яруса матрицы блока кр- рекции переносов (й = 1.2 ),Ч, . входы второго слагаемого которого соединены с выходами суммы 21-го-разрядного сумматора-го яруса матрицы блока коррекции переносов, выходы суммы и выход переноса перво 25 го О -разрядного сумматора соединены соответственно с входами первого слагаемого и входом переносавторого и-разрядного сумматора, выходы суммы которого соединены с входами-входового элемента И и входами первого слагаемого о -разрядного сумматора блока коррекции результата, выход й-входового элемента И соединен с входом переноса И -разрядного сумматора блока коррекции результата, 35 выходы суммы которого соединены с выходами результата устройства, входы второго слагаемого О -разрядного сумматора блока коррекции результата,-е входы второго слагаемого пер вого д -разрядного сумматора (С = , , п ) и входы второго слагаемого второго и -разрядного сумматора соединены с шиной нулевого потенциала.На Фиг 1 представлена структур ная схема матричного множительного устройствами на фиг. 2 - блок формнро" вания частичных произведений на фиг. 3 - блок суммирования частичных произведений, на Фиг. 4 - блок кор рекции переносов, на Фиг. 5 - блок коррекции результата.Матричное множительное устройство (фиг. 1) содержит блок 1 формирования частичных произведений, блок 55 2 суммирования частичных произведений, блок 3 коррекции переносов, первый 4 и второй 5 и -разрядные сумматоры, блок б коррекции результата.Блок 1 формирования частичных произведений (фиг. 2) содержит матрицу пхи элементов И 7.Блок 2 суммирования частичных произведений (фиг. 3) содержит древовидную матрицу 1 хи-разрядных сумматоров 8.Блок 3 коррекции переносов (Фиг4) содержит древовидную матрицух 1-разрядных сумматоров 9.Блок б коррекции результата (Фиг. 5) содержит и -входовый эле- мент И 10 и О -разрядный сумматор 11.Матричное множительное устройство работает следующим образом,На входы матричного множительного устройства поступают и -разрядное множимое Й = 0а, а, и о -разрядный множитель В = ЬЪЬБлок 1 Формирования частичных произведений образует попарные произведе- нияз,ь( 1, 2 о, в= 1, 2, .и )1Произведения разрядов множимого на младший разряд множителя Ощ,и) 1 образуют слово частичных произведений первой ступени 11, произведения разрядов множимого на второй разряд множителя щш 5, образуют слово частичных произведений второй ступе" ни 1,.произведения разрядов множимого на б -й (старший) разряд множителя а Ъобразуют слово частичных произведений п -й ступениСлово 1, сдвинуто относительно слова 11 на один разряд влево, слово , сдвинуто относительно слована два разряда влево, , словосдвинуто относительно слова 1Ина и - 1 разрядов влево.Выходы элементов И блока 1 формирования частичных произведений соединены с входами слагаемых сумматоров первого яруса матрицы блока 2 суммирования частичных произведений,иТак как 2 = 1 по рассматриваемому модулю М = 2" - 1, то умножение наФстепень двойки 2 равносильно циклическому сдвигу влево на л разрядов п-разрядной двоичной записи множимого, т. е. линейный сдвиг словзаменяется циклическим.Слово, полученное в результате циклического сдвига слова частичных;( 1 1, 2, , н ),Например, 1 г =С 3 еЬг,0.1 Ь г,0б .0, ЪЦ 1 г, Блок 2суммирования частичных произведенийосуществляет сложение слов ; . Слова опоступают на входы первого иая 10второго слагаемых сумматоров 8 ц. ОЕсли П2 , то на оставшиеся входыслагаемых сумматоров 8 первого ярусаматрицы подаются значения сигналов,соответствующие логическому "0"Такие же сигналы подаютсяи на входыпереносов всех суиматоров первогояруса дерева.Результаты попарного сложенияслов , р ,р о (без участия пер арреносов) поступают на входы слагаемых сумматоров второго яруса, Результаты попарного сложения укаэанных результатов (беэ учета переносов) поступают на входы слагаемыхсумматоров третьего яруса и т, д,Так как 2 = 1 по рассматриваемопому модулю М = 2 - 1, то переносыиз и -го в (у 1 + 1)-й разряд имеютвес, равный единице. Поэтому выходыпереносов (2 1 - 1)-х сумматоров 8 30г-го ( = 1, 2, , 1 - 1) яруса( ь = 1, 2, , 2" ) соединены свходом переноса 1 -го сумматора 8(г + 1)-го яруса матрицы. Остальныепереносы сумматоров 8 поступают вблок 3 коррекции переносов.Блок 3 коррекции переносов образует корректирующие слова путемсложения поступающих переносов, Переносы из сумматоров 8 первого ивторого ярусов матрицы блока 2 счетными номерами передаются на одноразрядные сумматоры 9 первого ярусаматрицы блока 3 коррекции переносов,причем на один сумматор поступаюттри переноса, Полученные в результате сложения двухразрядные слова передаются на входы слагаемых сумматоров второго яруса матрицы блока 3коррекции переносов. На входы переносов сумматоров 9 второго яруса матрицы блока 3 коррекции переносовпоступают переносы из третьего ярусаматрицы блока 2, Полученные в результате попарного сложения двухраз- урядных слов трехразрядные слова поступают на входы слагаемых сумматоров 9 третьего яруса матрицы блока.3 коррекции переносов. На входы переносов сумматоров 9 третьего ярусаматрицы блока 3 коррекции переносовпередаются переносы из четвертогояруса матрицы блока 2 и т. д. Навыходах сумматора 9 последнего ярусаблока 2 коррекции переносов образуется ( 1 - 1)-разрядное слово коррекции, состоящее иэ ( 1 - 2)-разрядногослова суммы 5" и переноса 0 , обозначающего (1 - 1)-й разряд слова.На выходах сумматора 8 последнегояруса матрицы блока 2 получается Ьразрядное слово суммы б 1 и переносимеющий вес, равный единице.(МРезультат сложения слова б корректирующего слова и переноса , , полу 1)чается на выходе первого П "разрядного сумматора 4.Если в результате сложения образуется перенос, то его необходимоприбавить к младшему разряду полученного слова сумм. Эту функцию выполняет сумматор 5. В результатеполучается произведение 18 по модуйлю М кя 2 - 1, представленное и -разрядным двоичным числом.Матричное множительное устройствоимеет два представления нуля:000 н 111, тяк как слов разрядов и разрядовво 111 сравнима с нулем яо моЛ разрядовдулюМ= 2 - 1,11Поэтому окончательный результатдолжен корректироваться, длячегослужит блок 6 коррекции результата.Результат умножения поступает наП-входовой элемент И 10 и одновременно на П -разрядный сумматор 11.При равенстве всех разрядов единицена выходе элемента И 10 появляетсяединица, которая поступает на входыпереноса сумматора 11.В результате на выходах сумматора 11 устанавливаются нулевые значения, т, е. нуль получает единственное представление.При использовании матричногомножительного устройства для обычного умножения значения сомножителейдолжны быть такими, чтобы А Э 2" -1,где А и В - положительные двоичныечисла. В этом случае результат уминожения по модулю 2 - 1 не отличается от результата обычного умножения.Таким образом, введенные связипозволяют расширить функциональные10 1170450 фгфП возмоаности матричного мноаительного устройства: мозно осуществлять обычное умножение и умножение по моду- люИ 2" -1Следовательно, расширяется область применения устройства, так как применение его в процессорах обработки сигналов позволяет реализовать алгоритмы, определенные надконечным кольцом, а также классичес"кие алгоритмы. Кроме того, устройство мокет применяться в системах кодирования, принцип действия которых базируется на теории полей Галуа.1170450 ий,ор В.Гир ИИПИ по дел035., Моск Редактор М.КелемеЗаказ 4705/46 оставитель Е.Захаренкоехред О.Ващишина Корр рак 730 Подписное сударственного комитета СССР ам изобретений и открытий а, Ж-З 5, Раушская наб., д. 4/5 Патент", г. Укгород, ул. Проектная