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

,) 656075 Сокга Соеетскик Социалистических Республик06 Г 7/ с присоединением заявки ЛЪ дарстеениыи комите СССР(43) Опубликовано 28.02.79. Бюллетень Ме 8 (45) Дата опубликования описания 28.02.79Корчагин, Д, Е. Лакийчук, К, Б, Садомо и Л.М, Хохлов ное конструкторско-технологическое бюию счетных машин и Опытный завод. Добрис, В, Г. сударственно по проект со ов 4) УСТРОЙСТВО ДЛЯ УМНОЖЕН бласти вычисбыть испольустройствах счастотно-имия информаИзобретлительнойзовано ввероятностпульснойции. ние относится к техники и може вычислительных 10-импульсной и формой представ Гъь Известно устроиство, содержащее два разрядных преобразователя код - верояность, генератор псевдослучайных чсел, элемент И, счетчик результатов, блок синхронизации 1,Недостатками известного устройства являются низкие быстродействие и точность вычисления.Наиболее близким по технической сущности к изобретению является устройство, содержащее четыре и/4-разрядных преооразователя код - вероятность, первый элемент И, и/2-разрядный,преооразователь код - вероятность, генератор псевдослучайных чисел, первый элемент задержки, два и/4-разрядных счетчика результата, и/2-разрядный счетчик результата, блок анализа окончания операции, выход которого соединен со входом генератора псевдослучайных чисел, псрвый выход которого соединен со входами первого и второго и/4-разрядных преобразователей код - в:- роятность, второй выход генератора п дослучайных чисел соединен со входами третьего и четвертого и/4-разрядных преобразователей код - вероятность и входом и/2-разрядного преобразователя код в вероятность, выход которого через первый 5 элемент задержки соединен с первым входом первого элемента И, второй вход которого соединен с выходом второго и/4-разрядного преобразователя код в вероятнос, выход первого элемента И соединен со 10 входом первого и/4-разрядного счетчикарезультата 2.Недостатком известного устройства является низкое быстродействие.Цель изобретения - повышение быст родействия устройства.С этой целью в устройство введены третий и/4-разрядный счетчик результата, три сумматора, второй третий элементы задержки, второй, третий, четвертый, пятый 20 и шестой элементы И, причем первые входы второго, третьего и четвертого элементов И соединены с выходом первого и/4-разрядного преобразователя код - вероятость, вторые входы второго и пятого 25 элементов И через второй элемент задержи соедсы с вь:одом третьего гг,4-разрядого преобразователя код в вероятносгь, псрвые вхо;,ь: пятого и шестого элементов И соеднень с выходом второго 30 гг/4-разрядного преобразователя код в ве5 1 О 15 20 25 В, В,35 а эти части Получим: А=О, А,А,А В=О,В,В,В,40 45 50 55 60 65 роятность, вторые входы третьего н шестого элементов И через третий элемент задержки соединены со входом четвертого и/4-разрядного преобразователя код в вероятность, вход четвертого элемента И соединен с выходом первого элемента задержки, выходы пятого и шестого элементов И соединены с первыми входами первого и второго сумматоров соответственно, вторые входы которых соединены с выходами третьего и четвертого элементов И соответственно, выход второго элемента И соединен с первь)м входом третьего сумматора, выход первого и/4-разрядного счетчика результата соединен с третьим входом первого сумматора, выход которого соединен со входом второго и/4-разрядного счетчика результата, выход которого соединен со входом третьего и/4-разрядного счетчика результата, выход которого соединен со вторым входом третьего сумматора, выход которого соединен со входом и/2-разрядного счетчика результата.На чертеже представлена блок-схема устройства для умножения.Устройство для умножения содержит первый и/4-разрядный преобразователь 1 код - вероятность, второй и/4-разрядный преобразователь 2 код в вероятнос, первый элемент И 3, второй элемент И 4, третий элемент И 5, блок 6 анализа окончания операций, генератор 7 псевдослучайных чисел, третий и/4-разрядный преобразователь 8 код - вероятность, четвертый и/4-разрядный преобразователь 9 код - вероятность, и/2-разрядный преобразователь 10 код - вероятность, четвертый элемент И 11 пятый элсмент И 12, шестой элемент И 13, элементы задержки 14 - 16, и/2-разрядный счетчик 17 результата, первый сумматор 18, первый и/4-разрядный счетчик 19 результата, второй сумматор 20, второй и/4-разрядный каскад счетчика 21 результата, сумматор 22, третий и/4-разрядный счетчик 23 результата.Предлагаемое устройство реализует метод умножения по частям. Коды сомножителей А = О, а аг азаи В =О, Ь Ьг Ьз." Ьп, где аЬ; - двоичные разряды соответствующих сомножителей, разбиваются на три части, начиная со старших разрядов, - две по и/4 и одну по и/2 разрядов; А, Аг, Аз и В Вг, Вз соответственно.Операция разделяется на 2 цикла, В первом цикле в преобразователи 1 и 2 код в вероятность соответственно заносятся коды А, и А а в преобразователи 8, 9 и 10 соответственно коды В Вг и В,. При работе устройства на выходах преобразователей 1, 2, 8 - 10 код - вероятность обр азуются стохастические последовательности бинарных символов с,вероятностями появления 1, численно равные значениям кодов А Аг, В ВВз соответственно. Означенные последовательности перемножаются на соответствуюших элементах И 3, 4, 5, 11 - 13. Стохастические последовательности с выходов элементов И 3, 4, 5, 11 - 13, образующие 6 произведений А, В; (1=1, 2, 1=1, 2, 3), поступают через соответству.ющие двух - и трехвходовые сумматоры на входы 17, 19, 21, 23 двоичного счетчика результата в соответствии с весовыми коэффициента)ли 2-)к-/ г 1Первый цикл заканчивается по истечении полного периода работы генератора 7 :псевдослучайных чисел.Бо втором цикле в преобразователи 1, 2 код в вероятнос заносятся коды В В в преобразователь 8 в к Аз, а остальные преобразователи 9 и 10 обнуляются, Вычисления повторяются, По окончании второго цикла с первых разрядов счетчика результата, т. е. с каскадов преобразователей 1, 19, 21 считывается результат произведения. Операция закончена.Для разъяснения сущности предлагаемого изобретения рассмотрим процесс умножения 20-разрядных чисел А и В.Разобьем А и В на 3 части: две по 5 и одну по 10 разрядов, обозначив: А:О а аряряяр йрй)арара)р а )а)р юрр А, А, А,соответственно через Аь А Аз,С=А В=ОА, ОВ,+(ОА, ОВ,+Для простоты записи будем в дальнейшем опускать ноль при записи чисел 0,А; и О,В;.Основываясь на свойствах вероятностного умножения, предложенного в )прототипе, можно указать, что произведения А) В), АгВ АгВ А,Вг вследствие того, что разрядность сомножителей равна половине разрядности генератора псевдослучайных чисел, будут вычисляться точно, в то время как остальные - с погрешностью о,2 1"+1. Так как произведения А,Вз и А,В, входят в выражение (2) с коэффициентом 2 - ", погрешность вычисления С, обусловленная этими составляющими, составит 2 - ". Следовательно, вычисление произведения теряет смысл.= 0,765 2-ю.Для и-разрядных сомножителейМ(=) = О 25,2 - и.о. = 0,765 2 - ".Из выражения (3) видно, что,предло женное устройство с 10-разрядным генератором псевдослучайных чисел работает с той же точностью, что и устройство-прототип с генератором на 20 разрядов. Время умножения при этом, определяющееся какиТ=2 У, где У=2 - 1, а /= -- разрядность генератора, равно Т=2 (21 о - 1) = =2046 тактов.При умножении этих чисел на известном 20 устройстве Т=2" - 1.Таким образом, время умножения сокращается в 512 раз.О преимуществах, предложенного устройства по сравнению с .прототипом можно 25 судить из таблицы. Выигрыш вт,-- разТ,Время умножения на устройстве Разрядностьсомножителей предложенном (Т,) известном (Т,)(1 2 в (2 в (2 в (21 2 - 1 2 о 21 в 22 о 1 7101620 16 Устройство для умножения и-разрядных чисел, содержащее четыре а/4-разрядных преобразователя код - вероятность, первый 30 элемент И, и/2-разрядный преобразователь код - вероятность, генератор псевдослучайных чисел, первый элемент задержки, два и/4-разрядных счетчика результата, и/2-разрядный счетчик результата, блок анализа 35 окончаний операции, выход которого соединен со входом генератора псевдослучайных чиселпервый выход которого соединен со входами первого и второго л/4-разрядных преобразователей код - вероят ность, второй выход генератора псевдослучайных чисел соединен со входами третьего и четвертого и/4-разрядных преобразователей код - вероятность и входом и/2-разрядного;преобразователя код - вероятность, 45 выход которого через первый элемент задержки соединен с первым входом первого элемента И, второй вход которого соединен с выходом второго и/4-разрядного преобразователя код - вероятность, выход пер вого элемента И соединен со входом первоТаким образом, вычисление произведения С=А В можно производить по формулеС=А,(В, +В, 2-з+Вв 2-1 ю)++ А, (Ю, 2-ю+ В, 2-") Определим вероятностные характеристики погрешности произведения в.Математическое ожидание: М(з) = М(еА,В,)+М(еА,В,) 2 ю++М( Азв. ) + М(еАзвз) 2- - М(аА,В,) 2 - ", Пренебрегая членом с коэффициентом 2 - " и принимая гипотезу о равномерном распределении величин А; и В;, получим: М(е) =(0,25 2-"+ 0,25 2-зю).2-1 ю- Оз 25 2 - Яю = 0,25 2 - юСреднеквадратическое отклонение; 1 зА Вз зАзВз АзВз Формула изобретения го и/4-разрядного счетчика результата, о тличающееся тем, что, с целью повышения быстродействия, в устройство введены третий и/4-разрядный счетчик результата, три сумматора, второй и третий элементы задержки, второй, третий, четвертый, пятый и шестой элементы И, причем первые входы второго, третьего и четвертого элементов И соединены с выходом первого и/4-разрядного преобразователя код в вероятность, вторые входы второго и пятого элементов И через второй элемент задержки соединены с выходом третьего и/4-разрядного преобразователя код - вероятность, первые входы пятого и шестого элементов И соединены с выходом второго разрядного преобразователя код - вероятность, вторые входы третьего и шестого элементов И через третий элемент задержки соединены со входом четвертого а/4-разрядного преобразователя код - вероятность, выход четвертого элемента И соединен с выходом первого элемента задержки, выходы 1 пятого и шестого элементов И соединены спервыми входами первого и второго сумматоров соответственно, вторые входы которых650075 Составитель А. Уткин Редактор А. Купрякова Техред А. Камышникова Корректоры: И. Позняковскаяи 3. Тарасова Заказ 575/16 Изд. Мо 171 Тираж 779 Подписное НПО Государственного комитета СССР по делам изобпетений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5Типография, пр. Сапунова, 2 соединены с выходами третьего и четвертого элементов И соответственно, выход второго элемента И соединен с первым входом третьего сумматора, выход первого и/4-разрядного счетчика результата соединен с третьим входом первого сумматора, выход которого соединен со входом второго а/4-разрядного счетчика результата, выход которого соединен со входом третьего и/4-разрядного счетчика результата, выход которого соединен со вторым входом третьего сумматора, выход которого соединен со входом и/2-разрядного счетчика результата.5 Источники ин о ма ии ф р цпринятые во внимание при экопертизе1. Авторское свидетельство СССРМв 305482, кл. 6 06 Р 7/39, 1972,2. Заявка Мо 214125518-24, кл. б 06 Г10 7/39, 1977, по которой принято решение овыдаче авторского свидетельства.