Устройство для умножения п-разрядных чисел

Устройство для умножения п-разрядных чисел

Иллюстрации

Показать все

Реферат

 

(iij65OO75

CQN3 Соеетскик

Социалистических

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 07.02.77 (21) 2450358/18-24 с присоединением заявки ¹ (51) М. Кл.

6 06F 7/39 (43) Опубликовано 28.02.79. Бюллетень № 8 (45) Дата опубликования описания 28.02.79 (53) УДК 681.325 (088.8) по делам изсбргтеиий и открытий (72) Авторы изобретения

Г. В. Добрис, В, Г. Корчагин, Д. Е. Лакийчук, Ю. Б. Садомов и Л. М. Хохлов

Государственное союзное конструкторско-технологическое бюро по проектированию счетных машин и Опытный завод (71) Заявители (54) УСТРО Й СТВО ДЛЯ УМНОЖЕНИЯ

Государстееииый комитет

23) Приоритет

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

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

Недостатками известного устройства являются низкие быстродействие и точность вычисления.

Наиболее близким по технической сущности к изобретению является устройство, содержащее четыре n/4-разрядных преооразователя код — вероятность, первый элемент И, n/2-разрядный, преобразователь код — вероятность, генератор псевдослучайных чисел, первый элемент задержки, два

n/4-разрядных счетчика результата, и/2-разрядный счетчик результата, блок анализа окончания операции, выход которого соединен со входом генератора псевдослучайных чисел, псрвый выход которого со-"динен со входами первого и второ.-о

nj4-разрядных преобразователей код †в=роятность, второй выход генератора псевдослучайных чисел соединен со входами третьего и четвертого п/4-разрядных,преобразователей код — вероятность и входом и/2-разрядного преобразователя код — вероятность, выход которого через первый

5 элемент задержки соединен с первым входом первого элемента И, второй вход которого соединен с выходом второго n/4-разрядного преобразователя код — вероятность, выход первого элемента И соединен со

10 входом первого n/4-разрядного счетчика результата (2).

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

Цель изобретения — повышение быст15 родействия устройства.

С этой целью в устройство введены третий п/4-разрядный счетчик результата, три сумматора, второй и третий элементы задержки, второй, третий, четвертый, пятый

20 и шестой элементы И, причем первые входы второго, третьего и четвертого элементов И соединены с выходом первого и/4-разрядного преобразователя код — вероятность, вторые входы второго и пятого

25 элементов И через второй элемент задержки соединены с вь.".одом третьего 11.,4-разрядиo;o прообразc âàòåëÿ код †вероятносгь, псрвые вхо;.ь: пятого и шестого элементов И соедпнень с выходом второго

30 тг/4-разрядного преобразователя код — ве650075

35 а эти части

В,, В2, В3.

Получим:

А=О, А,А,А„

В = О, В,В,В, 40

65 роятность, вторые входы третьего и шестого элементов И через третий элемент задержки соединены со входом четвертого п/4-разрядного преобразователя код — вероятность, вход четвертого элемента И соединен с выходом первого элемента задержки, выходы пятого и шестого элементов И соединены с первыми входами первого и второго сумматоров соответственно, вторые входы которых соединены с выходами третьего и четвертого элементов И соответственно, выход второго элемента И соединен с первым входом третьего сумматора, выход первого n/4-разрядного счетчика результата соединен с третьим входом первого сумматора, выход которого соединен со входом второго л/4-разрядного счетчика результата, выход которого соединен со входом третьего п/4-разрядного счетчика результата, выход которого соединен со вторым входом третьего сумматора, выход которого соединен со входом и/2-разрядного счетчика результата.

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

Устройство для умножения содержит первый n/4-разрядный преобразователь 1 код — вероятность, второй и/4-разрядный преобразователь 2 код — вероятность, первый элемент И 3, второй элемент И 4, третий элемент И 5, блок 6 анализа окончания операций, генератор 7 псевдослучайных чисел, третий п/4-разрядный преобразователь 8 код †вероятнос, четвертый и/4-разрядный преобразователь 9 код †вероятность, n/2-разрядный преобразователь

10 код — вероятность, четвертый элемент И 11 пятый элсмент И 12, шестой элемент И 13, элементы задержки 14 — 16, п/2-разрядный счетчик 17 результата, первый сумматор 18, первый n/4-разрядный счетчик 19 результата, второй сумматор 20, второй и/4-разрядный каскад счетчика 21 результата, сумматор 22, третий и/4-разрядный счетчик 23 результата.

Предлагаемое устройство реализует метод умножения по частям. Коды сомножителей А = О, а а2 аз ... а„и В = 0, Ь1 bg bç ." b„, где а,, b; — двоичные разряды соответствующих сомножителей, разбиваются на три части, начиная со старших разрядов,— две по и/4 и одну по п/2 разрядов: Аь А2, А, и

В, В, Вз соответственно.

Операция разделяется на 2 цикла. В первом цикле в преобразователи 1 и 2 код — вероятность соответственно заносятся коды

А и А, а в преобразователи 8, 9 и 10 соответственно коды Вь В и В,. При работе устройства на выходах преобразователей 1, 2, 8 — 10 код — вероятность обр азуются стохастические последовательности бинарных символов с,вероятностями появления «1», численно равные значениям кодов А, А2, В, В2, Вз соответственно. Означенные последовательности перемножаются на соответствуюших элементах И 3, 4, 5, 11 — 13.

Стохастические последовательности с выходов элементов И 3, 4, 5, 11 — 13, образующие 6 произведений А, В; (i = l, 2, j = l, 2, 3), поступают через соответствующие дву.-.— и трехвходовые сумматоры на входы

17, 19, 21, 23 двоичного счетчика результата в соответствии с весовыми коэффициенТа м H° : 2 — и/л(1 -/ — 2)

Первый цикл заканчивается по истечении полного периода работы генератора 7

:псевдослучайных чисел.

Бо втором цикле в преобразователи 1, 2 код †вероятнос заносятся коды В1, В, в преобразователь 8 †к Аз, а остальные преобразователи 9 и 10 обнуляются. Вычисления повторяются. По окончании второго цикла с первых разрядов счетчика результата, т. е. с каскадов преобразователей 1, 19, 21 считывается результат произведения.

Операция закончена.

Для разъяснения сущности предлагаемого изобретения рассмотрим процесс умножения 20-разрядных чисел А и В.

Разобьем А и В на 3 части: две по 5 и одну по 10 разрядов, обозначив:

А=О, а,а,а,а,а, а,а,а,а,а„а„а„...а„

А, А, А, В, В, В, соответственно через А1 Аь Аэ

С=А B=OA, OB,+(ОА,.ОВ,+

+0,А,.0,В,) 2 — +(О,А, О В,-+O,Аз X

ХО Вз+0 А О В ) 2 o+(0 А,О В

-+O,A, 0,В,) 2-"+(О,А, O,В,).2 2 (2) Для простоты записи будем в дальнейшем опускать ноль при записи чисел О,А; и О,В;.

Основываясь на свойствах вероятностного умножения, предложенного в прототипе, можно указать, что произведения A i Bi, А В,, А В2, А1В вследствие того, что разрядность сомножителей равна половине разрядности генератора псевдослучайных чисел, будут вычисляться точно, в то время как остальные — с погрешностью

a,„. 2 1"+ц. Так как произведения А ВЗ и

А,В1 входят в выражение (2) с коэффициентом 2 — ", погрешность вычисления С, обусловленная этими составляющими, составит 2 — ". Следовательно, вычисление произведения теряет смысл.

650075 2 o 2 — 2þ )/ + = (3)

=0,765 2 0.

Для и-разрядных сомножителей

М(в) = 0,25 2 и.

a= :0,765 2 — ".

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

Т=2 N, где N=2 — 1, à 1= — — разрядность генератора, равно Т=2 . (2" — 1) =

=2046 тактов.

При умножении этих чисел на известном

20 устройстве Т= 2" — 1.

Таким образом, время умножения сокращается в 512 раз.

О преимуществах, предложенного устройства по сравнению с .прототипом можно

25 судить из таблицы.

Выигрыш в

Т, — — раз

Т, Время умножения на устройстве

Разрядность сомножителей предложенном (Т,) известном (TI) (12 (2в

<2 (2"

2 — 1

2 о 1

21в

22о 1

16

16

Устройство для умножения и-разрядных чисел, содержащее четыре n/4-разрядных преобразователя код — вероятность, первый 30 элемент И, n/2-разрядный преобразователь код — вероятность, генератор псевдослучайных чисел, первый элемент задержки, два и/4-разрядных счетчика результата, и/2-разрядный счетчик результата, блок анализа 35 окончаний операции, выход которого соединен со входом генератора псевдослучайных чисел,,первый выход которого соединен со входами первого и второго n/4-разрядных преобразователей код †веро- 40 ность, второй выход генератора псевдослучайных чисел соединен со входами третьего и четвертого и/4-разрядных преобразователей код — вероятность и входом и/2-разрядного;преобразователя код — вероятность, 45 выход которого через первый элемент задержки соединен с первым входом первого элемента И, второй вход которого соединен с выходом второго и/4-разрядного преобразователя код — вероятность, выход пер- 50 вого элемента И соединен со входом первоТаким образом, вычисление произведения С=А В можно производить по формуле

C" = А, (В, +В,.2-з+Вв 2- 0)+

+А,(В, 2 — +В, 2-"+В,.2 — ")+

+ Аз (P,2 Io -+ В 2 Is) Определим вероятностные характеристики погрешности произведения в.

Математическое ожидание:

М(е) = 1М(ел,в,) + М(ел,вз)J 2 — 0+

+1М(ел,в,) + М(ел,в,) 2 зо — М(вл,в.).2 20

Пренебрегая членом с коэффициентом

2 —" и принимая гипотезу о равномерном распределении величин А; и В;, получим:

М (е) = (О 25. 2-10 + 0 25. 2 — Io) . 2 — 10 — 0,25 2-" = 0,25.2-".

Среднеквадратическое отклонение; A iBç A âВз ЛзBç

Формула изобретения го n/4-разрядного счетчика результата, отличающееся тем, что, с целью повышения быстродействия, в устройство введены третий и/4-разрядный счетчик результата, три сумматора, второй и третий элементы задержки, второй, третий, четвертый, пятый и шестой элементы И, причем первые входы второго, третьего и четвертого элементов И соединены с выходом первого и/4-разрядного преобразователя код †вероятность, вторые входы второго и пятого элементов И через второй элемент задержки соединены с выходом третьего и/4-разрядного преобразователя код — вероятность, первые входы пятого и шестого элементов

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

650075

Составитель А. Уткин

Редактор А. Купрякова Техред А. Камышиикова Корректоры: И. Позняковская и 3. Тарасова

Заказ 575/16 Изд. Кз 171 Тираж 779 Подписное

НПО Государственного комитета СССР по делам изобпетений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Типография, пр. Сапунова, 2 соединены с выходами третьего и четвертого элементов И соответственно, выход второго элемента И соединен с первым входом третьего сумматора, выход первого и/4-разрядного счетчика результата соединен с третьим входом первого сумматора, выход которого соединен со входом второго

n/4-разрядного счетчика результата, выход которого соединен со входом третьего и/4-разрядного счетчика результата, выход которого соединен со вторым входом третьего сумматора, выход которого соединен со входом n/2-разрядного счетчика результата.

5 Источники ин о ма ии ф р ц принятые во внимание при экспертизе

1. Авторское свидетельство СССР

М 305482, кл. G 06 F 7/39, 1972.

2. Заявка Мв 2141255!18-24, кл. G 06 F

10 7/39, 1977, по которой принято решение о выдаче авторского свидетельства.