Стохастическое устройство для деления двоичных чисел
Союз Соеетскнх
О Il И С А Н И Е
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Социалистических
Республик (б1) Дополнительное к авт. свид-ву (22) Заявлено 26.09.78 (21) 2666396/18-24 (51) M.Кл.з G 06 F 15/36 с присоединением заявки (23) Приоритет—
Государственный комитет по делам изобретений и открытий (43) Опубликовано 07.10.80. Бюллетень № 37 (53) УДК 681.3 (088.8) (45) Дата опубликования описания 28.10.80 (72) Авторы изобретения
В. М. Ерухимович и Б. М. Зелкин (71) Заявители (54) СТОХАСТИЧЕСКОЕ УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ
ДВОИЧНЫХ ЧИСЕЛ
Изобретение относится к области вычислительной техники и может быть использовано в различных вычислительных устройствах и в стохастических вычислительных машинах.
Известно устройство для деления аналоговых величин l(1), в котором иапользуется датчик случайных чисел. Однако это устройство не может быть,применено для деления чисел, представленных в двоичной форме.
Наиболее близким по технической сущности к изобретению является устройство для функционального преобразования !величин, представленных,в двоичной форме (2).
Это устройство содержит регистр делимого, генератор случайных чисел, преобразователь распределения и блок сравнения, выход которого является выходом устройства, первые входы соединены с выходами регистра делимого, а вторые входы — с выходами преобразователя-распределителя, входы которого соединены с выходами генератора случайных чисел.
Для,выполнения операции деления двоичных чисел в преобразователе распределения осуществляется преобразование последовательности случайных чисел, равномерно распределенных в интервале (0„1), в последовательность чисел, функция распределения которой зависит от значения делителя.
При требуемой точности порядка 2
5 преобразователь распределения содержит 2" регистров для хранения значений а ппроксимираванной фунюции распределения (где и — число разрядов случайных чисел) 2" регистров для хранения значений последо10 вательности двоичных чисел и 2" цифровых схем сравнений.
Недостатком такого преобразователя распределения при использовании его для выполнения операции деления являе ся
15 аппаратурная сложность и отсутствие униВерсальности, так как для каждого з начения делителя необходимо изменять содержимое 2" регистров хранения значений фунюции распределения.
20 Целью изобретения является упрощение устройства. ,Постановленная цель достигается тем, что в устройство для деления двоичных чисел, содержащее рвгистр делимого, генератор
25 случайных чисел, блок, сравнения, выход которого является выходом устройства, первая группа входов блока сравнения соединена с выходами регистра делимого, введены регистр делителя, рекуррентный регистр
З0 сдвига, первая и вторая группы элементов
769550. корреляции последовательностей на входах элемента И 10 порядка" " .",рямой выход каждого разряда, начиная с первого рекуррентного регистра-сдвига 4, соединен с первыми входами соответствующих элементов
И первой группы 5 (начнная,с первого) и элементов .И второй группы б (начиная с последнего), а инверсный выход каждого разряда рекуррентного регистра сдвига 4 (начиная с первого) соединен со вторыми
60 входами соответствующих элементов И первой группы 5 (начиная с последнего) и элементов И второй группы б (начиная с первого).
Выход элемента И 10 подключен.ко входу и-разрядного, счетчика 11.
И, первый и второй коммутатор, элемент И и счетчик. Выходы регистра делителя соединены с первой группой входов первого «оммутатора, выход которого соединен с первым входом элемента И..Выходы разрядов рекуррентного регистра сдвига соединены с соответствующими входам и элементов И пер вой группы в прямой, а со входами элементов И второй группы — в о братной IIQследавательности. Выходы элементов И первой группы, соединены со вторыми входами первого коммутатора, а выходы элементов
И второй группы — с первой группой входов второго коммутатора, вторая группа входов которого соединена с выходами ге- 15 нератора случайных чисел, а выход соединен со,вторым;входом элемента И, выход которого соединен со входом счетчика. Выходы разрядов счетных соединены со второй группой входов блока сравнения. 20
На чертеже представлена структурная схема устройства.
Оно содержит регистр делимого 1, блок сравнения 2, генератор случайных чисел 8, рекуррентный регистр сдвига 4, первую 5 и 25 вторую б группы элементов И, регистр делителя 7, первый 8 и второй 9 коммутаторы, элемент И 10 и,счетчик .11.
Рекуррен пный регистр сдвига 4 и генератор 8 представляют собой идентичные 30 и-разрядные сдвиговые регистры с линейной обратной связью, реализованной на сумматорах по модулю два.
Регистр сдвига 4 с выходами, подключе нными ко входам группы элементов И 5, 35 выходы которых (присоединены к первым входам коммутатора 8, на,вторые входы <оторого подключены выходы разрядов регистра 7, составляют преобразователь дво-, ичного числа регистра 7 в псевдослучайную 4О последовательность. С аналогичными связями регистр сдвига 4, группа элементов И б, коммутатор 9, генератор 8 составляют преобразователь двоичных чисел генератора 8 в псевдослучайные последовательности. 45
Выходы коммутаторов 8 и 9 соединены со входами элемента И,10, выполняющего роль умножителя.
Для обеспечения модуля коэффициента
Выходы и разрядов регистра 1 делимого соединены с первыми входами блока сравнения 2, вторые входы которого подключены к .выходам разрядов счетчика 11. Выход блока сравнения 2 является;выходом устройства.
Устройство работает следующим образом..
С момента подачи тактовых им пульcoB на шину сдвита рекуррентного регистра 4 на выходах каждого его разряда образуются псевдоелучай ные последовательности (М-пОследовательности) импульсов, которые поступают на входы элементов И групп
5 и б. С выходов элементов И групп 5 и б последовательности, имеющие математические, ожида ния, пропорциональные 2, U — 1, 2,..., n, поступают на первые входы коммутаторов 8 и 9, вторые входы которых подклю чены соответственно к выходам разрядов регистра делителя 7 и генератора 8. На выходах коммутаторов образуются псевдослучайные последовательности, математические ожидания которых пропорциональны соответственно значению делителя В и одного из псевдослучайных чисел Х, генерируемых регистром 3 с йнтервалом 2" — 1 тактов.
Эти последовательности, имеющие коэффициент взаимной корреляции порядка 2 — ", поступают на входы, элемента И 10. На выходе И 10 .образуется последовательность с математическим ожиданием, пропорцио.нальным произведению В . Х, которая декодируется счетчиком,11 за время, равное периоду М-последовательности, т. е. за 2" — 1 тактов. В счетчике 11 через каждые 2" — 1 тактов образуются двоичные коды чисел
Y = В Х, которые подаются на вторые входы блока сравнения 2.
Таким образом, для получения требуемой фуниции раопределейия последовательности двоичных чисел t Y (ii),I над последовательностью равномерно распределенных чисел (Х (l1 выполняется преобразование, обратное заданному, т. е. умножение, В блоке. сравнения 2, на первые входы которого поступает разрядный код делимого А, выполняется преобразование
На выходе блока сравнения 2 образуется последовательность импульсов (2 (i)), математическое ожидание кОторой пропорционально значению частного. Применение в устройстве для деления вместо преобразователя распределения рекуррентного рвгиспра сдвига, двух групп элементов И, двух коммутаторов элемента
И и счетчика 4 позволяет отказаться от сложного (по аппаратурной насыщен ности) преобразователя ра определения. Кроме того, структура. схемы предложенного устройства является неизменной
769550
Формула изобретения
Составитель О. Майоров
Техред И. Заболотнова Еорректор И. Осиновсакя
Редактор Л. Утехина
Заказ 1288/1296 Изд. № 485 Тираж 772 Подписное
НПО «Поиск» Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5
Тип. Харьк. фил. пред. «Патент» при любом з начении делителя, что обеспечивает его универсальность.
Стохастическое устройство для деления двоичных чисел, содержащее регистр делимого, генератор случайных чисел, блок сравнения, выход которого является выходом устройства, первая группа входов блока сравнения соединена с выхода ми регистра делимого, отличающееся тем, что, с,целью упрощения устройства, в него введены регистр делителя, рекуррентный регистр сдвига, первую и вторую группу элементов И, первый и,второй коммутаторы, элемент И и счетчик, причем выходы регистра делителя соединены с первой группой входов первого коммутатора, выход которого соединен с первым .входом элемента И, выходы разрядов рекуррентного регистра сдвига соединены с соответствующими входами элементов И первой группы в прямой, а со входами элементов И второй группы в обрапной последовательности,,выходы элементов И первой группы соединены со второй группой входов первого коммутатора, а выходы элементов И второй группы соединены с первой группой входов второго коммутатора, вторая группа входов которого соединена с выходами генератора слу10 чайных чисел, а выход соединен со вторым входом элемента И, выход которого соединен со входом счетчика, выходы разрядов счетчика соединены со второй группой входов блока сравнения, 15
Источники информации, IlpHIHHòûå во внимание при экспертизе:
1. Авторское свидетельство СССР № 321822,. кл. G Об F 7/16, 1970.
20 2. Яковлев В. В., Федоров P. Ф. Стохастические вычислительные машины. Л., 1974, с. 95 — 97, рис. 43, 45 (прототип).
