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

роятность, вторые входы третьего и шестого элементов И через третий элемент задерлски соединены со входом четвертого rt/4-pзарядного преобразователя код-вероятность, вход четвертого элемента И соединен с ВЫХОДОМ первого элемента задержкн, выходы пятого и шестого элементов И соединены с первыми входами первого и второго сумматоров соответственно, вторые ВХОДЫ которых соединены с выходами третьего и четвертого элементов И соответственно, выход второго элемента И соединен с первым входом третьего сумматора, выход первого n/4-разрядного счетчика результата соединен с третьим входом первого сумматора, выход которого соединен со входом второго л/4-разрядного счетчика реззльтата, выход которого соединен со входом третьего n/4-разрядного счетчика результата, выход которого соединен со вторым входом третьего сумматора, выход которого соединен со входом и/2-разрядного счетчика результата.

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

Устройство для умножения содержит первый /г/4-разрядный преобразователь 1 код-вероятность, второй г/4-разрядный преобразователь 2 код-вероятность, первый элемент И 3, второй элемент И 4, третий элемент И 5, блок 6 анализа окончания операций, генератор 7 псевдослучайных чисел, третий n/4-разрядный преобразователь 8 код-вероятность, четвертый л/4-разрядный преобразователь 9 код-вероятность, 72/2-разрядный преобразователь 10 код-вероятность, четвертый элемент И 11 пятый элемент И 12, шестой элемент И 13, элементы задержки 14 - 16, и/2-разрядный счетчик 17 результата, первый сумматор 18, первый n/4-разрядный счетчик 19 результата, второй сумматор 20, второй га/4-разрядный каскад счетчика 21 результата, сумматор 22, третий л/4-разрядный счетчик 23 результата.

Предлагаемое устройство реализует метод умножения ПО частям. Коды сомножителей Л 0, fli ... а-п. и B Q,b bzb... bn, где а,-, bi - двоичные разряды соответствуюших сомножителей, разбиваются иа три части, начиная со старших разрядов,- две по /г/4 и одну по л/2 разрядов; Ль А, АЗ и BI, BZ, BZ соответственно.

Операция разделяется на 2 цикла. В первом цикле в преобразователи 1 и 2 код-вероятность соответственно заносятся коды AI и 2, а в преобразователи 8, 9 и 10 соответственно коды BI, BZ и Вз- При работе устройства на выходах преобразователей 1, 2, 8-10 код-вероятность образуются стохастические последовательности бинарных символов с вероятностями появления «1, численно равные значениям кодов Ль AZ, BI, 82, BZ соответственно. Означенные последовательности перемножаются на соответствуюших элементах И 3, 4, 5, 11 -13. Стохастические последовательности с выходов элементов И 3, 4, 5, И -13, образующие 6 произведений Ai Bj (, 2, , 2, 3), поступают через соответствуюшие двух- и трехвходовые сумматоры на входы 17, 19, 21, 23 двоичного счетчика результата в соответствии с весовыми коэффициентами: (-/-2).

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

Во втором цикле в преобразователи 1, 2 код-вероятность заносятся коды BI, В, в

преобразователь 8-код Лз, а остальные преобразователи 9 и 10 обнуляются. Вычисления повторяются. По окончании второго цикла с первых разрядов счетчика результата, т. е. с каскадов преобразователей 1,

19, 21 считывается результат произведения. Операция закончена.

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

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

А-О, а,а,а, ., a a z-o-t

J L

а эти части соответственно через Ль Л г, А, Вь BZ, Вз. Получим:

, Aj/ijAs 5-0, В.,

и ,Г|

с А-в о,, + (::)Л,-,в +

+0,Л2-0,В,)(ОЛ-0,5з+ОЛ X ХОЗа+ОЛ 0,5,). 2-1о+(0,Л. 0,5, +

+0,Лз-0,5,)-2-15(о,Лз.О,5,). (2)

Для простоты записи будем в дальнейшем опускать ноль при записи чисел 0,Лг и 0,Bi.

Основываясь на свойствах вероятностного умножения, предложенного в прототипе, можно указать, что произведения Л1Вь

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

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

произведения теряет смысл.

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

С А, (5,+5,,-2-5+5з-2-1°)+

4- ЛЛ5,. 2-5 + 5,. 2-10 + 5, - 2-15) (

+ Аз(/,.2-1о + Б,.2-15).

Определим вероятностные характеристики «погрешности произведения г. Математическое ожидание:

M(s) 3.: 1М(лА} + М(гл,в,) +1М(вА,в,) + М (глзв. )1 -2-15-(353) 2-2°.

Пренебрегая членом с коэффициентом 2- и принимая гипотезу о равномерном распределении величин Ai и Bi, получим:

Ж (e) (0,25-2- +0,25-2-)-2-10-0,25-2-20: 0,25-2-20.

Среднеквадратическое отклонение:

O.-.

Е у АгВ, ЛзВ. АА

Х2-о 2-2о / + 4- + 4- (3) 0,765-2-20.

Для л-разрядных сомножителей Ж(5)гО,25-2- ; а 0,765-2-.

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

, где , а

-разряд7 2 ()

ность генератора, равно 2046 тактов.

При умножении этих чисел на известном устройстве 7 22-1.

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

О преимуществах предложенного устройства по сравнению с прототипом можно судить из таблицы.

Формула изобретения

Устройство для умножения «-разрядных чисел, содержащее четыре л/4-разрядных преобразователя код-вероятность, первый элемент И, л/2-разрядный преобразователь код-вероятность, генератор псевдослучайных чисел, первый элемент задержки, два л/4-разрядных счетчика результата, п/2-разрядный счетчик результата, блок анализа окончаний операции, выход которого соединен со входом генератора псевдослучайных чисел, первый выход которого соединен со входами первого и второго л/4-разрядных преобразователей код-вероятность, второй выход генератора псевдослучайных чисел соединен со входами третьего и четвертого /г/4-разрядных преобразователей КОД-вероятность и входом л/2-разрядного преобразователя код-вероятность, выход которого через первый элемент задержки соединен с первым входом первого элемента И, второй вход которого соединен с выходом второго /г/4-разрядного преобразователя код-вероятность, выход первого элемента И соединен со входом первого л/4-разрядного счетчика результата, о тличающееся тем, что, с целью повышения быстродействия, в устройство введены третий л/4-разрядный счетчик результата, три сумматора, второй и третий элементы задержки, второй, третий, четвертый, пятый и шестой элементы И, причем первые входы второго, третьего и четвертого элементов И соединены с выходом первого «/4-разрядного преобразователя код-вероятность, вторые входы второго и пятого элементов И через второй элемент задержки соединены с выходом третьего «/4-разрядного преобразователя код-вероятность, первые входы пятого и щестого элементов И соединены с выходом второго разрядного преобразователя код-вероятность, вторые входы третьего и шестого элементов И через третий элемент задержки соединены со входом четвертого «/4-разрядного преобразователя код-вероятность, выход четвертого элемента И соединен с выходом первого элемента задержки, выходы пятого и шестого элементов И соединены с первыми входами первого и второго сумматоров Соответственно, вторые входы которых

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

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

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

2.Заявка № 2141255/18-24, кл. G 06 F 7/39, 1977, по которой принято решение о выдаче авторского свидетельства.