Устройство для умножения @ -разрядных двоичных чисел Советский патент 1992 года по МПК G06F7/52 

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

Известно устройство для умножения чисел, содержащее регистры множимого, множителя и произведения, одноразрядный сумматор последовательного действия, триггер, логический элемент И, три логических элемента ИЛИ и вспомогательный регистр. Умножение n-разрядных чисел (здесь и далее n 2m, т 1 - целое) осуществляется за п циклов, в каждом цикле п тактов. Обозначив здесь и далее через Т период следования импульсов сигнала, синхронизирующего работу устройства, получим, что в данном случае умножение двух n-разрядных чисел осуществляется за время tyM п2-Т. Недостатком рассмотренного устройства является низкое быстродействие,

, Известно устройство для умножения последовательных n-разрядных двоичных кодов, содержащее регистры первого и второго сомножителей, распределитель, статический и сдвиговый регистр, одноразрядные последовательные сумматоры, элеVI00

со ел

ю

менты И и схему формирования сигнала переполнения. Это устройство вычисляет п старших разрядов 2п-разрядного произведения n-разрядных последовательных чисел, а п младших разрядов отбрасывается. Время вычисления произведения двух п- разрядных чисел составляет лТ. Недостатком указанного устройства является низкая точность. Возможна модификация данного устройства для получения произведений двоичной точности, однако в этом случае время умножения составит 2пТ, причем входные операнды должны будут поступать с интервалом в п тактов между старшим разрядом предыдущего и младшим разрядов последующего операнда. Кроме того, указанное устройство имеет низкое быстродействие, связанное с большой задержкой распространения сигнала от регистров сомножителей через элементы И и одноразрядные последовательные сумматоры на выход схемы.

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

перемножения (1 1п), вход множимого

устройства - с информационным входом регистра множимого, вход разрешения записи f-ro разряда которого соединен с i-м выходом распределителя сигналов (i 1п),

выход 1-го разряда регистра множимого соединен с t-м входом разрядов множимого блока перемножения, 1-й выход блока перемножения --с i-м входом коммутатора, 1-й выход первой группы выходов коммутатора - с 1-м информационным входом первого блока суммирования частичных произведений, 1-й выход второй группы выходов коммутатора - с 1-м информационным входом второго блока суммирования частичных

произведений (J 1п), выходы первого и

второго блоков суммирования частичных произведений соединены соответственно с первым и вторым выходами устройства, вход синхронизации которого соединен со входами запуска распределителя сигналов и коммутатора,

Недостатком указанного устройства является невозможность перемножения с его

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

Цель изобретения - расширение функциональных возможностей устройства для обработки чисел со знаками путем умножения чисел в дополнительном коде.

Поставленная цель достигается тем, что в известное устройство для умножения последовательных n-разрядных двоичных кодов, содержащее регистр множимого, сдвиговый регистр множителя, распределитель сигналов, блок перемножения, два бока суммирования частичных произведений

и коммутатор, причем вход множителя устройства соединен с информационным входом сдвигового регистра множителя, выход 1-го разряда которого соединен с f-м входом разрядов множителя блока перемножения

0 1п), вход множимого устройства соединен с информационными входами регистра Множимого, вход разрешения записи 1-го разряда которого соединен с f-м выходом распределителя сигналов, выход 1-го разряда регистра множимого соединен с i-м входом разрядов множимого блока перемножения, i-й выход которого соединен с 1-м входом коммутатора, 1-й выход первой группы выходов коммутатора соединен

с 1-м информационным входом первого блока суммирования частичных произведений, 1-й выход второй группы выходов коммутатора -с f-м информационным входом второго блока суммирования частичных

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

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

0 1 п-1), выход 1-го разряда регистра

задержки - с (1+1)-м дополнительным входом блока перемножения, первый дополнительный вход блока перемножения - с О, 1-й выход первой группы выходов управления коммутатора - с 1-м входом управления

первого блока суммирования частичных произведений, 1-й выход второй группы выходов управления коммутатора - с 1-м входом управления второго блока суммирования частичных произведений, первый и второй выходы установки коммутатора соединены соответственно со входами установки первого и второго блоков суммирования частичных произведений, 1-й вход управления блока перемножения соединен с 1-м выходом распределителя сигналов, который содержит п-разрядный сдвиговый регистр, информационный вход сдвигового регистра соединен со входом запуска распределителя сигналов, выход 1-го разряда сдвигового регистра распреДёЯЙте- ля соединен с i-м выходом распределителя 0 1,..., п). :;:::.

- При этом блок перемножения состоит из п модулей дешифрации, имеющих три информационных входа, вход управления и выход, первый информационный вход 1-го модуля дешифрации соединен с i-м входом разрядов множителя блока переможения, второй информационный вход 1-го модуля дешифрации - с 1-м входом разрядов множимого блока перемножения, третий информационный вход 1-го модуля дешифрации - с 1-м дополнительным информационным входом блока перемножения, вход управления 1-го модуля дешифрации - с i-м входом управления блока перемножения, выход 1-го модуля дешифрации - с 1-м; выходом блока перемножения. Каждый модуль дешифрации состоит из двух элементов И, элемента ИЛИ. сумматора.по modS и D-триггера с входом установки в 0й и входом блокировки, причем первые входы элементов И соединены с.выходом сумматора по mod2, первый выход которого соединен с третьим информационным входом модуля, второй вход сумматора по rfrodS соединен: со вторым информационным входом модуля и со входом блокировки D-трйггера, информационный вход которого соединен с первым информационным входом модуля, с вторым входом первого элемента И, с вторым инверсным входом второго элемента И, вход установки в О D-триггера соединен со входом управления модуля дешифрации; инверсный выход D-триггера - с третьим входом первого элемента И, прямой выход D-триггера - с третьим входом второго элемента И, выходы элементов И соединены со входами элемента ИЛИ, выход которого является выходом модуля дешифрации. Коммутатор содержит сдвиговый регистр и две группы элементов И, причем в него дополнительно ееед ены два триггера задержки и два дополнительных элемента И. при этом

первый триггер сдвигового регистра является счетным, вход первого триггера задержки соединен с входом коммутатора, выход первого триггера задержки - с входом второго 5 триггера задержки и с информационным входом сдвигового регистра, выход второго тригера задержки - с первыми входами первого и второго дополнительных элементов И, первые входы 1-х элементов И первой и

0 второй групп соединены соответственно с прямыми и инверсными выходами 1-го триггера сдвигового регистра, второе входы 1-х элементов И первой и второй групп - с 1-м входом коммутатора, выход 1-го элемента И

5 первой группы является I-м выходом первой группы выходов коммутатора, выход i-ro элемента И второй группы - Ни выходом второй группы выходов коммутатора, второй вход первого дополНйтельнбгбэлемен0 та И соединен с прямым выходом первого триггера сдвигового регистра, второй вход второго дополнительного элемента И - с инМёрсНым выхоДом пёрвбго три ггёрй сдвигового регистра, прямой выход 1-го триггера

5 сдвигового регистра - с 1-м выходом первой группы выходов управления коммутатора, инверсный выход 1-го триггера сдвигового регистра - с t-м выходом второй группы выходов управления коммутатора, выходы

о первого и второго дополнительных элементов И соединены соответственно с первым

: и вторым выходами установки коммутатора: Каждый блок суммйрЬвания частичных произведений содержит о$2 п групп однораз5 РЯДНЫХ полных сумматоров по п/2 одноразрядных сумматоров в; каждой группе р 1, 2..... tog2 п -номер группы). ogz п групп промежуточных триггеров по промежуточных триггеров в каждой группе

QV и IOQ2 п групп триггеров переноса по n/2J триггеров переноса в каждой группе, при-, чем вход 1-го промежуточного триггера пер . вой группы соединен с i-м информационным входом блока суммирования (i 1, 2, ..., п),

5 выход (2k-1)-ro промежуточного триггера первой группы - с первым входом k-ro одноразрядного сумматора первой группы (k 1, 2..... п/2), второй вход которого соединен с выходом 2k-ro промежуточного триггера,

,, выход суммы (2q-1)-ro и 2q-ro одноразрядных сумматоров гп-й группы (т 1, 2Iog2

п-1, q 1, 2,..., п/2 ) соединены с информационными входами (2q-1)-ro M 2qn-o промежуточных триггеров (т+ 1)-й группы,

выход (2q-1)-ro промежуточного триггера (т+1)-й группы соединены с первым входом - q-ro одноразрядного сумматора (т+ 1)-й группы, второй вход которого соединен с выходом 2q-ro промежуточного триггера (т+ 1)-й группы, выход переноса каждого

одноразрядного сумматора соединен с входом соответствующего триггера переноса, выход которого соединен с третьим входом этого же сумматора, выход суммы одноразрядного сумматора logz n-й группы соединен с выходом блока суммирования частичных призведений. При этом в блок суммирования частичных произведений дополнительно введено Iog2 п-1 триггеров задержки, причем вход разрешения записи i-ro промежуточного триггера первой группы соединен с 1-м входом управления блока

суммирования (1 1,2п), вход установки

блока суммирования частичных произведений - с входом установки в О триггеров

переноса первой группы, с входом первого триггера задержки и с входами установки в О промежуточных триггеров первой группы, выход k-го триггера задержки - со входами установки в 0я триггеров переноса (к+1)-й группы и со входом (к+1)-го триггера

задержки (к 1,2logz n-1).

Сущность изобретения состоит в том, что обработка чисел со знаками выполняется в дополнительном коде на основе алгоритма Бута, реализованного с помощью модулей дешифрации, которые формируют и выдают в блоки суммирования очередные частичные произведения в Јависимости от значений разрядов сомножителей. При этом очередные частичные произведения формируются и суммируются также в дополнительном коде, что обеспечив ёется соответствующей организацией приема данных в блоки суммирования частичных произведений.

Новым признаком в предложенном устройстве является наличие в блоке перемножения модулей дешифрации, состоящих из двух элементов И, сумматора no mod2, элемента ИЛИ и D-триггера. Модули дешифрации выполняют дешифрацию значений разрядов множимого в соответствии с алгоритмом Бута и преобразование поступающих в них разрядов множители в зависимости от результатов дешифрации, в результате чего формируются частичные произведения.

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

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

, Сущность изобретения поясняется с помощью фиг. 1-10.

На фиг. 1 представлена общая структурная схема устройства для умножения 8-разрядных двоичных чисел ().

0 На фиг. 2 представлена схема модуля дешифрации.

Таблица состояния выходов модулей дешифрации при работе устройства представлена на фиг. 3.

5 Схема блока суммирования частичных произведений показана на фиг. 4, при этом на фиг. 5 представлена схема сумматора первого яруса дерева сумматоров, на фиг.

6- схема остальных сумматоров.

0 На фиг. 7 показана схема коммутаторов, на фиг. 8 - схема модуля коммутации MKI, входящего в состав коммутатора на фиг. 7.

Временная диаграмма работы устрой5 ства, временная диаграмма работы распределителя сигналов и временная диаграмма работы коммутатора представлены на фиг. 9,10.11 соответственно. Таблица состояний выходов коммутатоо ров при работе устройства, представленная на фиг. 12, поясняет работу коммутатора.

Устройство для умножения 8-разрядных двоичных чисел (фиг. 1) включает регистр множимого 1, сдвиговый регистр множите5 ля 2, распределитель 3 сигналов, блок перемножения 4., два блока суммирования частичных произведений 5 и б, коммутатор

7и 7-разрядный регистр 8 задержки, причем вход множителя 9 устройства соединен с

Q информационным входом сдвигового регистра множителя 2, выходы 2,1-2.8 сдвигового регистра множителя 2 соединены соответственно со входами 4.1-4.8 разрядов множителя блока перемножения 4, вход

5 множимого 10 устройства соединен с информационными D-входами триггеров 1.1- 1.8 регистра множимого 1, входы V разрешения записи которых соединены соответственно с выходами 3.1-3.8 распреде0 лителя сигналов 3, выходы триггеров 1.1-1.8 регистра множимого - соответственно с входами 4,9-4.16 разрядов множимого блока перемножения 4, выходы 4.17-4,24 блока перемножения 4 - соответственно со входа- ми 7.1-7.8 коммутатора, восемь выходов первой группы 7.9 коммутатора 7 - с соответствующими входами 5.1 первого блока суммирования частичных произведений 5, восемь выходов второй группы 7.10 коммутатора 7 - с соответствующими входами 6.1

второго блока суммирования частичных произведений 6, выходы 5.2 и 6.2 первого 5 и второго 6 блоков суммирования частичных произведений - соответственно с первым 11 и вторым 12 выходами устройства, входы запуска 3.9 и 7.11 распределителя сигналов

3и коммутатора 7 соответственно - с входами синхронизации устройства. Блок перемножения 4 имеет 8 дополнительных входов 4.25-4.32, 8 входов управления (на фиг. 1 не показаны) и состоит из восьми модулей дешифрации 14.1-14.8, коммутатор имеет две группы 7.12 и 7.13 выходов управления во восемь выходов в каждой, и два выхода установки 7.14 и 7.15, блоки суммирования частичных произведений 5 и б имеют каждый по 8 входов управления 5.3 и 6.3 соответственно, и входы установки 5.4 и 6.4 D-входы триггеров 8,1-8.7 регистра задержки 8 соединены с выходами триггеров 1.1- 1.7 регистра множимого 1 соответственно, выходы триггеров 8.1-8.7 - с входами 4.26432 блока перемножения 4, вход 4.25 блока перемножения соединен с О. Выходы 7.12 первой группы выходов управления коммутатора 7 соединены с соответствующими входами 5.3 управления первого блока 5 суммирования частичных произведений, выходы 7.13 второй группы выходов управления коммутатора 7 - с соответствующими входами 6.3 управления второго блока 6 суммирования частичных произведений, первый 7.14 и второй 7.15 выходы установки коммутатора 7 - соответственно со входами установки 5.4 и 6.4 первого 5 и второго 6 блоков суммирования частичных, произведений. Блок перемножения 4 состоит из восьми модулей дешифрации 14.1-14.8. первые информационные входы А модулей дешифрации 14,1-14.8 соединены соответственное входами 4.1-4.8 разрядов множителя блока перемнохсения 4, вторые информационые входы В модулей дешифрации 14.1-14.8 - соответственно с входами 4.9-4.16 разрядов множимого блока перемножения 4, третьи информационные входы С модулей дешифрации 14.1-14.8- соответственно с дополнительными информационными входами 4.25-4.32 блока перемножения 4, входы управления D (см. фиг. 2) модулей дешифрации 14.1-14.8 - соответственно с выходами 3.1-3.8 распределителя сигналов 3, выходы F модулей дешифрации 14.1-14.8 - соответственно с выходами 4.17-4.24 блока перемножения. Каждый модуль дешифрации 14 1-14,8 в блоке перемножения 4 состоит из двух элементов И 15 и 16, элемента ИЛИ 17, D-триг- гера 18с входом установки в О и входом блокировки и входом блокировки и сумматора по mod2 19 (см. фиг. 2). При этом первые входы 20 элементов И 15 и 16 соединены с выходом сумматора nomod2 19, первый вход 21 которого соединен с третьим инфор5 мационным входом С модуля, второй вход 22 сумматора по mod2 - с вторым информационным входом В модуля и входом блокировки 23 D-триггера 18, информационный вход 24 которого соединен с первым инфор0 мационным входом А модуля-дешифрации, с вторым входом 25 первого элемента И 15 и с вторым инверсным входом 26 второго элемента И 16, вход R установки в 0й D- триггера 18 соединен с входом управления

5 D модуля дешифрации, инверсный выход D-триггера - с третьим входом 27 первого элемента I/115, прямой выход D-триггера - с третьим входом 28 второго элемента И 16, выходы элементов И 15 и 16 соединены со

0 входами элемента ИЛИ 17, выход которого является выходом модуля дешифрации.

Коммутатор 7 содержит сдвиговый регистр 29, два триггера задержки 30 и 31, два элемента И 32 и 33 и восесь модулей комму5 тации МК1-МК8 (фиг. 7), состоящий из двух элементов И 64 и 65 (фиг. 8) (элементы И 64 модулей коммутации МК1-МК8 образуют первую группу элементов И коммутатора, элементы Л 65 модулей коммутации МК1Q МК8 - вторую группу элементов И коммутатора) Первый триггер 34 сдвигового регистра 29 является счетным, вход первого триггера задержки 30 соединен с входом S2 запуска коммутатора, выход первого тригге5 ра задержки 30 - с входом второго триггера задержки 31 и с информационным входом сдвигового регистра (входом счетного триггера 34). Выход второго триггера задержки

31соединен с первыми входами первого 32 Q и второго 33 элементов И коммутатора. Первые входы 11 элементов И 64 и 65 модулей коммутации МК1-МК8 (см. фиг, 8) соединены соответственно с прямым и инверсным выходами триггеров 34-41 сдвигового регис стра 29, вторые входы элементов И 64 и 65 модулей коммутации - соответственно с входами 7.1-7,8 коммутатора, выходы элементов 64 модулей коммутации МК1-МК8 являются соответствующими выходами 7.9

Q первой группы выходов коммутатора (выходами D1.1-D8.1 на фиг. 7), выходы элементов 65 модулей коммутации являются соответствующими вйхо Дами 7.10 второй группы выходов коммутатора (на фиг. 7 - выходами D1.2-D8.2), второй вход элемента

32соединен с прямым выходом первого триггера 34 сдвигового регистра 29, второй вход элемента 33 соединен с инверсным выходом первого триггера 34 сдвигового регистра, прямые выходы триггеров 34-41

5

сдвигового регистра 29 через модули коммутации МК1-МК8 (см. фиг. 8) соединен с соответствующими выходами 7.12 (фиг. 1) управления первой группы (на фиг. 7 - выходы С1 1-С8.1). инверсные выходы тригге- ров 34-41 сдвигового регистра 29 соединены с соответствующими выходами 7.13 (фиг. 1) управления второй группы коммутатора (на фиг. 8 - выходы С1.2-С8.2), выходы элементов И 32 и 33 - соответствен- но с первым 7.14 и вторым 7.15 выходами установки коммутатора. Каждый блок суммирования имеет древовидную структуру (фиг. 4), состоящую из Iog2 8-3 ярусов суммирующих модулей 42-48, каждый суммирую- щий модуль содержит одноразрядный полный сумматор 49, два промежуточный триггера 50, 51 и триггер переноса 52 (см. фиг. 5, 6). При этом информационные входы А 53, В 53 промежуточных триггеров 50, 51 первого яруса соединены с соответствующими информационными входами DO-D7 блока суммирования (см. фиг. 4 и 5), в каждом модуле суммирования выходы промежуточных триггеров 50, 51 соединены с первым 54 и вторым 55 входами одноразрядного полного сумматора 49, выходы суммы однноразрядных полных сумматоров первого и второго ярусов соединены с соответствующими входами 53 промежуточных триггеров 50,51 суммирующих модулей второго и третьего ярусов соответственно, выходы переноса 57 одноразрядных полных сумматоров 49 - с информационным входом 58 триггера лереноса 52 в этом же сумми- рующем модуле, выход триггера переноса 52 - с третьим входом одноразрядного полного сумматора 49 (см, фиг.-5, 6), выход суммы 56 одноразрядного полного сумматора в суммирующем модуле 48 третьего яруса яв- ляется выходом 60 блока суммирования, который содержит также два триггера задержки 61 и 62, причем входы разрешения записи 63 промежуточных триггеров 50 и 51 суммирующих модулей первого яруса 42-45 соединены с соответствующими входами СО-С7 управления блока суммирования (см. фиг. 4, 5), вход установки бб блока суммирования частичных произведений соединен с входом триггера задержки 61, с входами 66 установки в О промежуточных триггеров 50.51 и триггеров переноса 52 суммирующих модулей 42-45 первого яруса, выход первого триггера задержки 61 соединен со входом второго триггера задержки 62 и со входами 66 установки в О триггеров перенс са 52 суммирующих блоков 46, 47 второго яруса, выход второго триггера задержки 62 - с входом установки

в О триггера переноса 52 суммирующего модуля 48 третьего яруса.

В общем случае операцию умножения двух двоичных чисел а и b можно записать в виде

(ai)-b-2- .

I 0

(D

В случае, когда данные представлены в прямом коде f(al) al.

При обработке данных в дополнительном коде удобно использовать алгоритм Бута, когда

1 если аг 1, аи О,

1-(2)

(1 если аг 1, аи

ffal) - 1 1 если а| ° аиг 1 1 Оесли агам.

причем , т.е. функция f(ai) определяется путем дешифрации значений 1-го и (М)-го разрядов числа а (нумерация разрядов начинается с младшего). Из выражений (1) и (2) видно, что для умножения чисел в дополнительном коде необходимо обеспечить выполнение следующих микроопераций:

1. Дешифрация состояний 1-го и (1-1)-го разрядов числа а для всех I e 1, 2, ..., п и формирование функции f(ai).

2 Формирование величины, b1 b ffai).

3.Взвешивание величины Ь1, т.е. умножение Ь1 на 2 ,

4.Суммирование взвешенных значений.

Величина Ы равняется либо 0, либо величине Ь. либо величине -Ь в зависимости от значения функции f(ai). Поскольку используется дополнительный код. то величина -Ь может быть получена путем преобразования исходного дополнительного кода числа Ь в код числа с противоположным знаком. Умножение b на эквивалентно сдвигу кода Ь1 на f разрядов вправо, при этом старшие i разрядов полученного кода должны совпадать с знаковым разрядом кода Ь, поскольку используется дополнительный код. Таким образом, процедуру умножения чисел в случае, например, Ь 1.1101010, а 0.0110111 можно представить в следующем виде: исходные данные: Ьдоп- 1.1101010, аДОп 0.0110111;

множество значений функции fi : a 0101 1001; код величины -Ь 00010110.

1111011001000110- -1210-2

Таким образом, каждое 1-е взвешенное частичное произведение состоит из трех частей: необходимое количество младших разрядов (в зависимости от веса I) являются нулями (область А в примере 3 - правый нижний угол), затем идет п значащих цифр величины Ы в дополнительном коде (область В - центральная часть в примере 3), а оставшиеся I разрядов 2п-разрядного кода аполняются знаковым разрядом величины Ы (область С - верхний угол в примере 3). Суммирование частичных произведений удобно выполнять в последовательном коде с помощью дерева одноразрядных полных сумматоров с запоминанием переноса. При этом в момент завершения обработки частичных произведений, относящихся к текущей паре сомножителей а и Ь, и начала обработки частичных произведений, относящихся к следующей паре сомножителей, триггеры переносов в однобитовых сумматорах должны обнуляться.

Устройство работает следующим обра- зом.

Операнды вводятся в последовательном дополнительном коде младшими разрядами вперед через вход 10 (операнд а) и 9 (операнд Ь) устройства в соответствии с в ре- менной диаграммой на фиг. 9, Прием разрядов операндов а и Ь в регистры устройства происходит по фронту синхросигнала S1, который поступает на входы синхронизации всех триггеров устройства (цепи разводки синхросигнала S1 на фигурах и в формуле изобретения не отражены, чтобы не загромождать изложение). Старшие (знаковые) разряды операндов сопровождаются высоким уровнем синхросигнала S2 (конец слова), который поступает через вход }3 устройства и служит для запуска распределителя 3 и сдвигового регистра 29 коммутатора 7 (см. фиг. 7). разряды операнда Ь последовательно задвигаются в триггеры сдвигового регистра 2, т.е. в каждом такте ранее загруженные разряды операнда Ь сдвигаются в регистре 2 на одну позицию, а в освободившийся триггер первого разряда регистра 2 заносится в очередной разряд

30

ii

15 20 25

35

ri

45

5

операнда. Разряды операнда а поступают с входа 10 устройства на D-входы одновременно всех триггеров 1.1-1.8 статического регистра 1, при этом распределитель сигналов 3 последовательно выдает на свои выходы 3.1-3.8 импульсы разрешения записи в соответствии с временной диаграммой на фиг. 10, которые поступают на входы V разрешения записи триггеров 1.1-1.8 регистра 1 таким образом, что в 1-м такте после прихода очередного импульса сигнала S2 (т.е. после завершения ввода предыдущей пары сомножителей) первый разряд операнда а записывается в триггер 1.1 и хранится там в течение восьми тактов, во втором такте после прихода импульса S2 второй разряд операнда а записывается в триггер 1.2 и т.д., в восьмом такте после прихода импульса S2 восьмой (знаковый) разряд операнда а записывается в триггер 1.8. при этом поступает очередной импульс S2 конец слова),

Разряды операнда Ь поступают с выходов триггеров регистра 2 на первые информационные входы А модулей дешифрации 14.1-14.8, при этом сдвиговый регистр .2 обеспечивает умножение кода числа Ь на (задержку на I тактов), где 1 1,2, .... 8 - номер выхода сдвигового регистра 2. Разря- д ы операнда а поступают с выходов триггеров 1.1-1.8 на вторые информационные входы В модулей дешифрации 14.1-14.8 и на входы триггеров 8.1-8.7 регистра задержки 8, откуда сигналы проходят на третьи информационные входы С модулей дешифрации 14.2-14.8 (на вход С модуля 14.1 все время поступает О).

Регистр задержки 8 обеспечивает одновременное поступление значений разрядов а и аи операнда а на входы В и С 1-го модуля дешифрации, который формирует частичные произведения в соответствии с выражением (2). Модуль дешифрации работает следующим образом (см. фиг. 2). Запись младшего разряда операнда Ь в 1-й разряд регистра 2 происходит одновременно с записью (И)-го разряда а операнда а в (М)-й триггер регистра задержки 8, и одновременно с записью 1-го разряда операнда а в 1-й триггер регистра 1. Последняя операция выполняется при высоком уровне сигнала раз- решения записи на 1-м выходе 3.1 распределителя сигналов 3. Этот же сигнал одновременно поступает через в ход управления D соответствующего модуля дешифрации 14.1 на вход R установки в О D-триггера 18 и обнуляет этот триггер. При ai аи 1 и ai аы О на выходе сумматора по mod2 формируется низкий уровень О, который закрывает элементы И 15 и 16, в результате чего на выход F модуля дешифрации выдается О независимо от значений разрядов операнда Ь, поступающих на вход А, и состояния триггера 18 модуля дешифрации. При ai О, аМ 1 низкий уровень на входе В модуля дешифрации проходит на вход блокировки 23 D-триггера 18 и запрещает его переключение из начального состояния логического О, в которое этот триггер установился в момент записи а по высокому уровню на управляющем входе D модуля дешифрации, соединенном с соответствующим выходом распределителя сигналов. В этом случае элемент И 16 будет все время закрыт низким уровнем на входе 27, а элемент И 15 будет все время открыт, т.к. при ai 0,аы 1 на выходе сумматора по mod2 сформируется высокий уровень. В результате этого на выход F модуля дешифрации через второй вход 25 элемента И 15 будут проходить разряды кода операнда b без изменений. При ai 1. аи- О на выходе сумматора по mod2 также формируется высокий уровень, в результате чего при начальном нулевом состоянии D-триггера 18 на выход F модуля дешифрации через вход 25 элемента 15 будут проходить без изменения младшие разряды кода b до тех пор включительно, пока не придет первая 1 В момент поступления первой 1 на вход А модуля дешифрации D-триггер 18 переключится в состояние входе блокировки 23 триггера - высокий уровень, т.к. ai 1). в результате чего элемент И 15 закроется, а элемент И 16 - откроется, и на выход F модуля все остальные разряды кода Ь, которые поступят после прихода первой 1 выдаваться с инверсией через второй инверсный вход элемента И 16. В этом случае модуль дешифрации выполняет преобразование дополнительного кода числа Ь, поступающего на вход А модуля, в дополнительный код числа с противоположным знаком -Ь по известному алгоритму, который состоит в том, что для преобразования кода числа в код числа с противоположным знаком необходимо все младшие нули этого кода и первую единицу, следующую за ними, оставить без изменений, а все остальные разряды кода проинвертировать. В таблице на фиг. 3 представлены состояния выходов модулей дешифрации в различные моменты времени при работе устройства, при этом BIK bifK, т.е. BIK является i-м разрядом величины, полученной умножением кода числа b на значение функции fK, полученной дешифрацией значений k-ro и (k-1)-ro разрядов операнда а1 в соответст- виии с выражением Ј2). Нумерация тактов в таблице ведется начиная с момента подачи высокого уровня сигнала S2 конец слова.

Из таблицы видно, что модуль дешифрации 14.1 начинает выдавать разряды первого частичного произведения Ъ - bi -ft во втором такте после подачи сигнала 31, модуль дешифрации 14.2 - разряды второго частичного произведения В e b -tz в третьем такте после подачи импульса S2 и т.д. В 9-м такте модуль 14.1 завершает выдачу первого частичного произведения предыдущей пары

сомножителей и в 10-м такте начинает выдачу первого частичного произведения следующей пары сомножителей. Модуль 14.2 завершает выдачу второго частичного произведения предыдущей пары сомножителей

в 10-м такте и в 11-м такте начинает выдачу второго частичного произведения следующей пары сомножителей и т.д.

С выходов модулей дешифрации 14.1- 14.8 частичные произведения поступают на

входы 7.1-7.8 коммутатора 7, который частичные произведения четных пар сомножителей выдает в первый блок суммирования частичных произведений 5, а частичные произведения нечетных пар сомножителей

выдает во второй блок суммирования частичных произведений б.

Коммутатор работает следующим образом (см. фиг. 7). Импульсы сигнала S2 конец слова задерживаются на один такт первым

триггером задержки 30 и приходят на вход запуска счетного триггера 34, который при подаче высокого уровня на этот вход переключается в противоположное состояние и запускает сдвиговый регистр 29 в соответствии с временной диаграммой на фиг. 11, где представлены сигналы на входе 7.11 (S2) коммутатора и сигналы на выходах всех триггеров коммутатора (триггеров задержки TD1, TD2, счетного триггера СТ и триггеров

35-41 (Т1-Т7) сдвигового регистра 29), Сигналы на прямых и инверсных выходах триггеров 34-41 проходят на первые входы элементов И 64 и 65 соответствен но модулей коммутации МК1-МК8 (см. фиг. 7,8), при

этом высокий уровень на прямом выходе триггеров сдвигового регистра 29 (триггер находится в состоянии Q 1) разрешает прохождение данных со входов 7.1-7.8 коммутатора через элементы И 64 модулей

коммутации МК1-МК8н,а выходы D1.1-D8.1 коммутатора, которые на фиг. 1 обозначены позицией 7.9 и соединены с входами данных 5.1 первого блока Суммирования, а высокий уровень на инверсном выходе триггеров

сдвигового регистра 29 (триггер находится в состоянии Q- 0) разрешает прохождение данных со входов 7.1-7.8 коммутатора через элементы И 65 модулей коммутации МК1- МК8 на выходы D1.2-D8.2 коммутатора, которые на фиг. 1 обозначены позицией 7.1б и соединены с входами данных 6.1 второго блока суммирования. Переключение триггеров сдвигового регистра 29 синхронизировано с потоками данных, поступающих в коммутатор 7 с выходов F модулей дешифрации 14.1-14.8 таким образом, что переключение 1-го триггера в регистре 29 происходит в момент завершения выдачи с выхода F модуля 14.1 последнего разряда Ьв 1-го частичного произведения предыдущей пары операндов и начала выдачи с выхода F модуля дешифрации 14.1 первого разряда TSi i-ro частичного произведения следующей пары операндов (см. табл. на фиг. 3 и временные диаграммы на фиг. 11). В результате этого на выход D1.1 в течение 8 тактов (со 2-го по 9;й) выдается код частичного произведения b , при этом на выход D1.2 в течение этих 8 тактов выдается 0, затем в течение следующих 8 тактов на выход D1.1 выдается 0, на выход D1.2 выдается код частичного произведения Ь1 следующей пары операндов. Аналогичным образом, но со сдвигом на 1 такт частичные произведения Ь2 выдаются с выходов D2.1 и D2.2, частичные произведения Ь3 выдаются с выходов D3.1 и D3.2 коммутатора 7 и т.д.. см. таблицу состояний выходов коммутатора при работе устройства (фиг. 12). строки О1.1-О8Л и D1.2-D8.2. Отметим, что коммутатор 7 совместно с модулями дешифрации 14.1-14.8 формирует данные, которые в примере (3) относятся к области В - центральной части массива битов частичных произведений. Формирование битов из областей А и С выполняется в промежуточных триггерах сумматоров первого яруса блоков суммирования частичных произведений, для чего необходимы специальные сигналы управления записью данных 7.12 и 7.13 (см. фиг. 1) и сигналы установки 7,14, 7.15.

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

, В момент начала обработки частичных произведений, сформированных разрядами очередной пары сомножителей, на вход установки 5,4 блока 5 USM1 поступает импульс сигнала установки R1 с выхода 7.14 коммутатора 7 (см. фиг. 7 и временную диаграмму на фиг. 11). Указанный импульс через входы RC сумматоров первого яруса 42-45 (фиг, 4) проходит на входы 66 установки в О промежуточных триггеров 50, 51, 52 этих

сумматоров (фиг. 5) и обнуляет эти триггеры. На входы разрешения записи RA, RB триггеров ТА. ТВ соответственно каждого сумматора в первом ярусе поступают сигналы с 5 выходов управления 7.12 коммутатора 7, причем 1 на входе разрешения записи разрешает прием в соответствующий триггер новой информации, поступающей на его информационный вход 53, О на входе раз0 решения записи обеспечивает работу триггера в режиме хранения, когда состояние триггера в каждом следующем такте совпадает с его состоянием в предыдущем такте. Из таблицы на фиг. 12 (строки С1.1-С8.1)

5 видно, что промежуточные триггеры первого яруса сумматоров принимают новую информацию только в периоды поступления на их входы разрядов Та1 частичных произведений в примере 3, что соответствует цент0 ральной части 3 множества частичных произведений в указанном примере, а в остальные моменты времени находится в режиме хранения. Таким образом, режим хранения обеспечивает формирование ну5 левых младших разрядов частичных произведений на входах дерева сумматоров (область А в примере 3), поскольку триггеры AT, ТВ после их устайовки в О сигналом R1 будут находиться в режиме хранения до тех

0 пор, пока на их не начнут поступать разряды величины b (см, фиг. 12, а также расширенных знаковых разрядов частичных произведений (область С в примере 3) на входах дерева сумматоров, поскольку триг5 геры ТА, ТВ сразу посл приема в них старших разрядов величин b , которые как раз и являются знаковыми, переходят в соответствии с таблицей на фиг. 12 в режим хранения и на входы комбинационных

Q сумматоров SM 49 в последующих тактах поступают только знаки соответствующих частичных произведений до тех пор, пока не поступит следующий импульс сигнала установки R1. Сумматоры первого яруса (42-45

5 на фиг, 4) из п частичных произведений, поступающих на их входы, формируют п/2 промежуточных результатов, которые с задержкой в 1 такт начинают поступать на входы А и В сумматоров 2-го яруса (46-47 на

фиг. 4). Одновременно на входы RC этих сумматоров поступает с выхода триггера задержки 61 задержанный на -1 такт сигнал установки R1 и обнуляет триггеры хранения переноса 52 этих сумматоров (см. фиг. 6). Сумматоры второго яруса из п/2 промежуточных результатов первого яруса формируют п/4 промежуточных результатов второго яруса и выдают их на входы третьего яруса. Все последующие ярусы блока сумматоров работают аналогично, сумматор последнего

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

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

Предложенное устройство целесообразно использовать в арифметических блоках параллельно-конвейерных систем цифровой обработки, предназначенных для вычисления выражений типа JJ а bi. В таких блоках операцию суммирования лучше всето выполнять в дополнительном коде, в связи с чем применение предложенного устройства взамен прототипа позволит использовать единый способ представления данных для всех узлов системы, исключить необходимость из дополнительного кода в прямой на входах умножителей и из прямого в дополнительный на их выходах, позволит сократить аппаратные затраты, номенклатуру элементной базы, упростить управление обработкой данных в арифметическом блоке системы и уменьшить задержку выдачи результатов

Формула изобретения 1 Устройство для умножения п-разряд- ных двоичных чисел, содержащее регистр множимого, сдвиговый регистр множителя, распределитель импульсов, блок перемножения, коммутатор и два блока суммирования, выходы которых соединены соответственно с первым и вторым выходами устройства, вход множителя которого соединен с информационным входом сдвигового регистра множителя, выход 1-го разряда которого соединен соответственно с i-м информационным входом первой груп-°

пы блока перемножения (1 1 п), вход

множимого устройства соединен с информационным входом регистра множимого, вход разрешения записи 1-го разряда которого соединен соответственно с 1-м выходом распределителя сигналов, выход 1-го разряда регистра множимого соединен с 1-м информационным входом второй группы блока перемножения, i-й выход которого соединен соответственно с i-м информационным входом коммутатора, 1-е выходы первой и второй групп которого соединены соответственно с i-м информационными входами первого и второго блоков суммирования, вход запуска распределителя сигналов и управляющий вход коммутатора соединены с входом синхронизации устройства, отличающееся тем, что, с целью расширения

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

разряда которого соединен с выходом j-ro

разряда регистра множимого (j 1п-1),

а выход j-ro разряда - с Q+ 1)-м информационным входом третьей группы блока перемножения, первый информационный вход

Q третьей группы которого соединен с входом .логического нуля устройства, 1-е выходы третьей и четвертой групп коммутатора соединены соответственно с Ьми входами разрешения записи первого и второго блоков

5 суммирования, входы установки в О которых соединены соответственно с первым и вторым управляющими выходами коммутатора, i-й управляющий вход блока перемножения соединен с 1-м выходом

Q распределителя сигналов.

1 2. Устройство поп. 1,отличающеес я тем, что блок перемножения содержит п

модулей дешифрации, каждый из которых

состоит из двух элементов И, элемента

5 ИЛИ, сумматора по модулю два и D-тригге- ра, причем выход элемента ИЛИ i-ro модуля дешифрации блока соединен с i-м выходом блока, 1-й информационны вход первой фуппы которого соединен с первым входом

0 первого элемента И, первым инверсным входом второго элемента И и информационным входом D-триггера каждого 1-го модуля дешифрации блока, i-й информационный вход второй группы которого соединен с

5 входом первого слагаемого сумматора по модулю два и входом блокировки D-триггера каждого 1-го модуля дешифрации блока, i-й информационный вход третьей группы которого соединен с входом второго слагаQ емого сумматора по модулю два каждого 1-го модуля дешифрации блока, i-й управляющий вход которого соединен с входом установки в нуль D-триггера каждого i-ro модуля дешифрации блока, а в каждом i-м модуле

5 дешифрации выход сумматора по модулю два соединен с вторыми входами первого и второго элементов И, третьи входы которых соединены соответственно с инверсным и прямым выходами D-триггера, а выходы - с

Q первым и вторым входами элемента ИЛИ.

3 Устройство по п. 1,отличающее- с я тем, что коммутатор содержит сдвиговый регистр, п модулей коммутации, два триггера задержки и два элемента И, причем пер5 вый триггер сдвигового регистра является счетным, вход первого триггера задержки соединен с управляющим входом коммутатора, а выход - с входом второго триггера задержки и информационным входом сдвигового регистра, выход второго триггера зайержки соединен с первыми входами первого и второго элементов И. выходы которых бвединены соответственно с первым и вторым управляющими выходами коммутатора, i вторые входы - соответственно с прямым и инверсным выходами первого триггера сдвигового регистра, первый и второй управляющие входы 1-го модуля коммутации соединены соответственно с прямым и инверсным выходами 1-го триггера сдвигового (регистра и 1-ми выходами третьей и четвертой групп коммутатора. 1-й информационный вход которого соединен с информационным входом 1-го модуля коммутации, первый и второй выходы которого соединены соответственно с 1-ми выходами первой и второй групп коммутатора.

4. Устройство поп. 1,отличающее- с я тем, что каждый блок суммирования содержит Iog2 n групп одноразрядных сумматоров по п/21 одноразрядных сумматоров в

каждой группе (J 1,2loga n - номер

группы), log n групп промежуточных триггеров по промежуточных триггеров в каждой группе, (092 n групп триггеров переноса по n/2J триггеров переноса с каждой группе и Iog2 п-1 триггеров задержки, причем вход 1-го промежуточного триггера первой группы соединен с i-м информационным входом блока суммирования (I 1, п), выход (2k-1)-ro промежуточного триггера первой группы соединен с первым входом k-ro

одноразрядного сумматора первой группы (к 1,2п/2), второй вход которого соединен с выходом 2k-ro промежуточного триггера, выход суммы (2q-1)-ro и 2q-ro

одноразрядных сумматоров m-й группы

(тп 1Iog2 n-1, q 1п/2) соединены с

информационными входами (2q-1)-ro и 2q-ro промежуточных триггеров (т+ 1)-й группы, выход (2q-1)-ro промежуточного триггера

(го+1)-й группы соединен с первым входом q-ro одноразрядного сумматора (т+ 1)-й группы, второй вход которого соединен с выходом 2q-ro промежуточного триггера (т-М)-й группы, выход переноса каждого одпоразрядного сумматора соединен с входом соответствующего триггера переноса, выход которого соединен с третьим входом этого же сумматора, выход суммы одноразрядного сумматора 1од2 n-й группы соединен с выходом блока суммирования, вход разрешения записи 1-го промежуточного триггера первой группы соединен с 1-м входом разрешения записи блоха суммирования ( 1, п), вход установки в О которого

соединен с входами установки в О триггеров переноса первой группы, промежуточных триггеров первой группы и входом первого триггера задержки, выход k-ro триггера задержки соединен с входами установки в О триггеров переноса (k+ 1)-й группы и с входом (k+ 1)-ro триггера задержки (k 1. og2 n-2).

11

Di

11

ы

4иг. ,#

52

го

, п тактов

Изобретение относится к области вычислительной техники и может быть использовано в арифметических устройствах конвейерных систем цифровой обработки сигналов для умножения двоичных чисел, представленных в последовательном дополнительном коде. Целью изобретения является расширение функциональных возможностей устройства за счет обработки чисел в дополнительном коде со знаками. Новым в устройстве, содержащем регистры множимого 1 и множителя 2, распределитель 3 импульсов, блок 3 перемножения, состоящий из модулей дешифрации, коммутатор 7 и два блока 5, 6 суммирования частичных произведений является введение (п-1) разрядного регистра 8 задержки. Сущность изобретения состоит в том, что обработка чисел выполняется на основе алгоритма Бута, реализованногос помощью модулей дешифрации, которые формируют и выдают в блоки суммирования очередные частичные произведения в зависимости от значений разрядов сомножителей. При этом очередные частичные произведения формируются и суммируются также в дополнительном коде, что обеспечивается соответствующей организацией приема данных в блоки суммирования частичных произведений, 3 с.п. ф-лы, 12 ил.

A,g И

SL

D1

г

I ЛГ.И Г . 1..& I 4MV1 АГ.вг I Л«.й j Л.()

„лтлл лда

ПТвКТ

п г п п п

Н JLZilEIflj TI п:

S.n такте/

/if-gf

/ir.gs

tА6-В6

.

:ii-i

лг

№1+ mil ШMalsl .b ..

4

si

в t .У У .f 9 a ft h 1 п- ,Ґ ft & ц; it гщ eS я ss

JimuiruiJiJiJiJi

it 1TL

тт.

JT

It

n

n

n

JT

JT

n

-П

JT

-PL

/ir.gs

:Фиг,Й-:;:

лг

4

II

n

n

n

TL

n

n

л

n

JT

n

JT

Фнг..У

CotrtfHut KtHHyrtrept

Ш.

Ff 34

джин

d33E

«ft

tflgyg

OltfRltf

Mfr Ty;iHf

fi...r ГГ7ПГ

UT{«T«ljrr7

РЖоППо

«ПРТ71П7

1ЩП

FS,

eiofolt TPH1

о

ff

«Н1ШГ«1Т|«

$

Ш

f7.y

DI.I

PloiPloloiglc

«1«ИГ«1«1«|

M -fr

я

1|о|Р|ОЦ Го17

и vi;

Ш

ifiz

t |o|g|p|o| l

FJ

Щ|Т1

pKlf|n|g|c|g

F«

0

4

o ti0i0ie fii

IFPTMT

ihlffilili

(e

g-lgl/l lofPT

(КП1МТГГГ7

F

g|f|i4g|p| Ttf

I1

in иитПТ

ff

g|e|gtP|olpF

Hl«J«MI (f|

flflirtflpl TcP

Редактор С.Козлова

виг. /2 .

Составитель О.Подрубный Техред М.Моргентал

lJ|otJ)gT

n

1/Гфи

fat

«ПГ

яаммг.и.ч

gMI

тгто1

fVft

оз

PlPlglPlPTgl

0|(ilg|y pjg|e

gltilojojoygp

«T lrjlgl

F«.g

мфтя ,

p| lPtg|pt l

T«T/T T«

F«

a

g|O|0|PlO|p|g

qflnfl

и

4«UI«HI«I

1«иг« М

Р|.Г

пУ|«т 1;|«

glPlO| l

«R

И1П«КИИ

g|01/ |fl|/ | |

ilMj

FS

.fr

на

F

/1 { 1 И1«ф1 1 1о|р| 1о| 1 |р

и

и

«I.Mf.lfMI

F7. ,

f|f |p|C|g|fJP|

fHI«Mlftfl

FfTu

i l 4glc|f c.l

ЖШШШШТ

lgH4g|g|r|

Корректор Н.Милюковыа