Матричное устройство для умножения чисел (его варианты)

(56) Карцев М.А. Арифметика цифровыхмашин. М "Наука", 1969, с. 438.Авторское свидетельство СССРВ 600554, кл. С 06 Р 7/52, 1978.Патент США Р 4037093,кл. С 06 Р 7/52, опублик. 1977.Авторское свидетельство СССРВ 900281, кл. С 06 Г 7/52, 1979.Рабинер Л,Р., Гоулд Б. Теорияи применение цифровой обработкисигналов, М., "Мир", 1978, с,572573.(54) МАТРИЧНОЕ УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ (ЕГО ВАРИАНТЫ) .(57) 1. Матричное устройство дляумножения чисел, содержащее блокФормирования частичных произведений, выполненный в виде матрицы и виэлементов И (11-разрядность множителя и множимого) и блок суммирования частичных произведений, виполненный в виде матрици 11 Ф) одноразрядных сумматоров, причем первые. входы элементов И 1 -й строкиматрицы соединены с входом 4 -горазряда множителя устройства,-йразряд множимого которого соединенс вторыми входами (1,)-х элементов И Й =1,2О, -1,2 11),виход переноса (1, )-го одноразрядного сумматора соединен с первымвходом (4 +1, ф +1)"го одноразрядно"го сумматора, выход суммы (1,)-гоодноразрядного сумматора соединен.с вторым входом (1+1)-го одноразрядного сумматора, кроме выходов сумми переноса одноразрядных сумматоров последнего столбца и выходов переноса одноразрядных сумматоров последней строки, о т л и ч а ю - щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения умножения И разрядных двоичных чисел по модулю я2 -1, в него введены первый и вто-рой И -разрядные сумматоры и блок коррекции результата, содержащий 11-входовый элемент И и И -разрядный сумматор, а выход переноса (Л, К )-го одноразрядного сумматора соединен с первим входом (1, К +1)-го одноразрядного сумматора (К =1,2 И-З), выход ( 1,1-го элемента И соединен с первым входом (1, 1)-го одноразрядного сумматора (где 1) соответственно, выход (2,-го элемента И соединен с вторым входом (1,1)-го одноразрядного сумматора соответственно, где 1 (+ 1)Модп, К(А)Иодам= и при А О и (А)Модп равен . остатку А/л при АФ И, выход (б,р)-го элемента И (б 3П) соединен с третьим входом (1,4)-го одноразряд, ного сумматора, где 1 (ф+ -1)Модп, ,0=6-2, выход суммы (1, и -2)-го одноразрядного сумматора соединен с входом 1 -го разряда первого слагаемого первого П -разрядного сумматорасоответственно, выход переноса (1, и)-го одноразрядного сумматора кро ме (11, О -2)-го одноразрядного сумматора соединен с входом Г.-го ра я да второго слагаемого первого Л -ра рядного сумматора Ф 2,3 ,И), выМод переноса 1 Л -2)-го .одноразряд150398 Составитель Е.Захарченкоедактор О.йрковецкая Техред Л,Иикещ Корректор А Тяско Зак о ное лЮвФилиал ППП "Патент", г. Ужгород, ул. Проектная,4 779/46 ВНИИПИ Госу по делам 13035, Москв1160 Цель иэббретения - расширениефункциональных возможностей за счетобеспечения умножения,е-разрядныхЪ Пдвоичных чисел по модулю М=2 -1,На Лиг.1 представлена структурнаясхема матричного устройства для умножения чисел, первый вариант; наЛиг.2 - то же, второй вариант; наЛиг. 3 - то же, третий вариант; нафиг.4 в . схема блока Аормирования 0частичных произведений; на Лиг,5 -схема блока суммирования;частичныхпроизведений; первый вариант; наЛиг.б - то же, второй вариант; наЛиг. 7 в . то же, третий вариант; наФиг,8 - схема блока коррекции результата,Устройство (Аиг. 1- 3) содержитблок 1 Ьормирования частичных произведений, блок 2 суммирования частич-,ных произведений, пер,ый 3 и второй4 и -разрядные сумматоры и блок 5коррекции результата.Блок 1 Формирования частичныхпроизведений (Фиг,4) содержит матрицу из гак П элементов И 6,Блок 2 суммирования частичных произведений по первому варианту(Лиг.5) содержит матрицу из 0 (и)одноразрядных сумматоров 7.Блок 2 суммирования частичныхпроизведений по второму варианту(Лиг,б) содержит матрицу иэ К (и -1)гп-разрядных сумматоров 8.Блок 2 суммирования частичных произведений по третьему варианту .(Лиг.7) содержит матрицу из 1 (и)щ-разрядных сумматоров 9.Блок 5 коррекции результата(Лиг.Я) содержит и -входовый элементИ 10 и П -разрядный сумматор 11.40 Блок Аормирования частичных про,изведений образует произведения 0 6 Произведения разрядов множимого на младщий разряд множителя О 61 45 образуют слово частичных произведений первой ступени 1, а произведения разрядов множимого на второй разряд множителя О 5 - слово частичных произведений второй ступении т,д.50 произведения разрядов множимого на старший. (и-й) разряд множителя О; 5 п образуют слово частичных произведений И -й ступени 7" . СловосдвиЙнуто относительно слована один Ы разряд влево, слово 7"З сдвинуто относительно слова К 1 на два разряда влево и т.д., слово т сдвинуто от 398 4 носительно слована (и) раэря-. дов влево. Устройство работает следующим образом. йи Множимое Л= О 2 +а, 2 и- + а 2+ а. и множитель В=ба 2 +и+бц 2 6 2+ 5 поступают на входы, блока Аормирования частичных произведений, где формируются слова , п. Выходы элементов И блока Аормирования частичных произведений соединены с входами сумматоров блока 2 суммирования частичных произведений. Так как 2 =1 по модулю М= =2 в .1, то умножение на степень двойки 2 равносильно циклическому сдвигу влево на т разрядов и -разрядной двоичной записи множимого, т.е. ли-. нейный сдвиг слов 1 , заменяется циклическим. Блок суммирования. частичных произведений осуществляет суммирование циклически сдвинутых слов частичных произведений. Слово частичных произведений первой ступени , поступает на входы суммы сумматоров первого столбца без сдвига. Слово частичных произведений второй ступенипоступает на вторые входы сумматоров первого столбца, причем это слово поступает с циклическим сдвигом на один разряд влево, словопоступает на третьи входы сумматоров первого столбца с циклическим сдвигом на два разряда влево, слово Г 4- на третьи входы сумматоров второго столбца с циклическим сдвигом на. три разряда влево и т.д. слово с циклическим сдвигом на г 1 -1 разряд поступает на третьи входы сумматоров последнего столбца,В результате суммирования циклически сдвинутых слов частичных про. - изведений блоком 2 на выходах суммы матрицы сумматоров Б ,. ., бп получается и -разрядное слово, принадлежащее кольцу вычетов по модулю М= 2 -1, а на выходах переноса Р Рп - й -разрядное слово, сдвинутое линейно по отношению к слову на выходах суммы на один разряд влево. Линейный сдвиг заменяется циклическим путем соединения выхода переноса сумматора р (и) Р с младшим разрядом входа второго слагаемого первого Л -разрядного сумматора 3. Разряды слова переносов,Р Р 1 подаются на входы второго слагаемого первого и -разрядного сумматора 3, начиная с второго разряда. Разряды П -разрядного слова суммы подаются на входы первого слагаемого первого 11 -разрядного 5 сумматора 3. Суммирование слов суммы 5 = 5 , 5 Ьл и циклически сдвинутого слова переносов Р = Р, Рр р Р 2, рР, 1 осуществляется с помоцью сумматора 3, На выходе этого сумматора образуется слово суммы. Если в результате суммирования образуется перенос, то его необходимо просуммировать со словом суммы сумматора 3, подавая в младший разряд. 15 Эту функцию выполняет сумматор 4. В результате получается произведение АВ (год М), М=2 - 1, представи ленное в двоичном коде.При построении матрицы сумматоров 21 р в качестве элементарного сумматора можно использовать одноразрядный сумматор (первый вариант) либо ги - разрядный. сумматор с обработкой переноса; причем тогда матрица суммато- р 5 ров содержит К (Л) сумматоров, где К =1 л/сл +1, в случае если л не делится нацело на е (третий вариант), и К = Л /щр если Р делится нацело на ЛЧ (второй вариант), 30На каждый сумматор (для второго и третьего вариантов) поступает группа из Гп разрядов У( , где а( =1,2, К - номер п 1 -разрядного сумматора в столбце, У =1,2, Л - номер ступени слова частичных произведений.В третьем варианте устройства сумматоры последней строки матрицы используются не полностью. В ка-. честве выходов переносов сумматоров последней строки выступают выходый К суммь: Ят 1 р З,и+1 рв+1" ре эультате суммирования на выходах Э-разрядных сумматоров последнего столбца получаются значения разрядов суова сумм 5 щ, 5, 5"т р П рвер т где 5 щ - группа из й разрядов сумматора. Выходы переносов(с учетомк, переноса бщ 11) образуют слововида ОО ОР 1 00 ОРрр 1 00 ОБщ+1 е-раэря- т -разря- ю -разрядов дов дов которое поступает иа входы второго слагаемого Л -разрядного сумматорак (за исключением переноса 5 тс+1, который поступает на вход переносасумматора, на входы первого слагаемого которого поступает слово сумм 5 р 5.р р 5,"1 (иг 2 и 3)Матричное устройство для умножения чисел имеет представления нуля ООО . и 111 и-разря- и -разрядов дов так как слово 111 сравнимо П -рааридови с нулем по модулю М=2 -1. В случае использования этого устройства для. обычного умножения чисел последнее обстоятельство не имеет значения, так как число 111 не должно Л -разрядов восприниматься как нуль. Для вычислений в конечном поле или в конечноми кольце с модулем вида М=2 -1 в связи с наличием двойного представления нуля окончательный результат необходимо корректировать. Коррекция результата умножения происходит в блоке 5 коррекции результата (фиг,8). Результат умножения или ряда умножений и сложений по юой(2"-1) поступает на Л -входовый элемент И 10 и одновременно на Л -разрядный сумматор 11 (на входы одного из слагаемых на входы другого слагаемого подаются нулевые значения), При равенстве всех разрядов единице на выходе элемента И 10 появляется единица, кото-. рая поступает на вход переноса Л разрядного сумматора 11. В результа- те на выходах этого сумматора устанавливаются нулевые значения, т.е. нуль получает единственное представление,При использовании матричного устройства для умножения чисел для обычного умножения значения сомножителей должны удовлетворять условиюАч В 2 -1 где А и В - положительные двоичные числа. В этом случае результат умножения по вод (2 -1) ке отличается от результата обычного умножения. На" пример, если число разрядов сомножителей не превышает Й(2, то результат умножения таких сомножителей по шод(2 -1) ке отличается от результат.та обычного умножения.