Датчик случайных чисел

Союз Светских Социапистических РеспубликОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(22) Заявлено 070380 (21) 2893400/18-24 Р 1) М Сл с присоединением заявки йо(23) Приоритет 6 06 Г 7/58 Государственный комитет СССР но делам изобретений и открытийОпубликовано 0712,81. Бюллетень Йо 45 Дата опубликования описания 07. 12, 8172) Авторы изобретения Э.А.Баканович, М.А,Орлов, Л,А,Сми В.И.Новиков еский инс нский радисте(54) дАтчик случАйных чи 1е и случайных чисел, оторых являются атор первичных рав оичных чисел, вен, схемы сравнеции, элементы И идля получения чиселделением метод обтоды рекуррентногообразований. Эти е по параллельномуия всех цифр вычисла, сложны, т наибольшее быст 5 слу- условифры вы руются аршей. детально.Известен да содержащий мул тор случайных ные через элем дам соответств зующих регистр чисел, причем подключены к у чик слу тивибра мпульсо нты И к ющих тр хранени торые в тановоч чайных торы и в, под первы иггеро я случ ходы т ному в сел,нераченлю вхообр йных гге Изобретение относится к вычислительной технике и может быть исполь зовано при моделировании случайных процессов.5Особенно. эффективны подобные устройства при построении испытательной аппаратуры, входящей в состав вычислительно-моделирующих комплексов. На выходе такой аппаратуры требуется получать до нескольких десятков потоков случайных величин (чисел), подаваемых на испытуемый объект.Эффективны аппаратурные датчики случайных чисел и в качестве специализированного внешнего устройства к ЭВМ. При этом к датчикам предъявляется ряд часто противоречивых требований, например, необходимость достижения требуемого быстродействия 20 и достаточно простая схемно-конструктивная реализация,Одним из перспективных направлений в создании датчиков случайных чисел является разработка принципиально новых схемных решений, позволяющих снять противоречия в технических требованиях н повысить эффективность новых решений по сравнению с .известными. 30 Известны датчикосновными узлами кблок памяти, генерновероятностных двроятностные вентилния, схемы дешифраИЛИ, реализующиес требуемым распрератных функций, меи минимаксного предатчики, работающиспособу формированходного случайногохотя и обеспечиваюродействие.Более просты схемы датчикочайных чисел, реализующие метоных вероятностей,по которомуходного случайного числа формипоследовательно, начиная со сРассмотрим эти схемы болеедатчика, Недостатками этого датчика являются сложность организации цифрового управления характеристиками формируемых случайных чисел и невысокое быстродействие иэ-за большого .числа аналоговых элементов и операций 1) .Известен датчик случайных чисел, содержащий генератор равномерно распределенных случайных чисел, регистр хранения случайныхчисел, генератор тактовых импульсов, счетчик тактов, дешифратор кодовых комбинаций, деШифратор законов распределения, из-, бирательную схему, многоканальный генератор случайных импульсных потоков, вероятностный вентиль, элемен ты И и элементы ИЛИ, Датчик реализует генерирование случайных чисел по методу условных вероятностей последовательно - цифра за цифрой 2) .Недостатком устройства является 2 О его сложность иэ-за необходимости использования сложных генератораслучайных импульсов и тактирующего генератора. Другим недостатком является невысокое быстродействие из -за поочередного многотактного формирования всех цифр старших разрядовслучайного числа.Наиболее близким техническим решением к изобретению является датчик случайных чисел, содержащий блок па. мяти, генератор тактовых импульсов, генератор равновероятных двоичных чисел, блок формирования двоичных случайных цифр (включающий вероятностный вентиль), регистр хранения 35 случайных чисел, дешифратор кодовых комбинаций, дешифратор номера разряда, избирательную схему. Недостатком устройства является его невысокое быстродействие из-за последовательного 40 формирования цифр старших разрядов случайного числа 3 .Целью изобретения является повышение быстродействия датчика случайных чисел.Поставленная цель достигается тем,что датчик случайных чисел, содержащий первый ключ, к первому входу которого подключен выход первого блока памяти, первый регистр хранения случайного числа, включающий И основных триггеров и М дополнительных триггеров, выходы которых являются выходом датчика случайных чисел, генератор равйовероятных двоичных чисел, выход котфрого соединен с вторым входом 55 ,первого ключа и установочными входами М дополнительных триггеров первого регистра хранения случайного числа, а также генератор тактовых импульсов, выход которого подключен к ц выходу генератора равновероятных двоичных чисел, к третьему входу первого ключа и входу синхронизации первого регистра хранения случайного числа, снабжен дополнительными (И) регистрами хранения случайного числа, разрядность которых возрастает соответственно на один от 1 до (И), (И,-1) блоками памяти и (И) ключами, первые входы которых подключены к выходам соответствующих блоков памяти, вторые входы - к выходу генератора равновероятных двоичных чисел, третьи входы - к выходу генератора тактовых импульсов и ко входам синхронизации регистров хранения случайных чисел соответственно. Выход каждого иэ вероятностных вентилей подключен к установочному входу триггера младшего разряда соответствующего регистра хранения случайного числа. Выходы разрядных триггеров каждого предыдущего регистра хранения случайного числа, расположенного в порядке возрастания числа разрядов, подключены к установочным входам старших разрядных триггеров последующего регистра хранения случайного числа и к адресным входам последующего блока памятиеНа чертеже изображена структурная схема датчика.Датчик содержит й блоков памяти (1( -1 И), )( ключей (2 -2 И), регистры хранения случайного числа (34 -3) ), генератор равновероятных двоичных чисел 4 и генератор тактовых импульсов 5.Первые входы ключей 2(-2 подключены к выходам соответствующих блоков памяти 1 -1 вторые входы - к выходу генератора 4 и установочным входам дополнительных триггеров И+1) ,(И+М регистра 3)4, третьи входы - к выходу генератора 5 и ко входам синхронизации регистров 3( -ЗИ, выходы разрядных триггеров каждого предыдущего 3 из которых подключены к установочным входам старших разрядных триггеров последующего 3(+,( регистра хранения случайного числа и к адресным входам последующего Ц+ блока памяти. Блок памяти 1 служит для хранения и выдачи кодов вероятностей появления единичного значения соответствующей разрядной цифры выходного случайного числа с требуемым законом распределения. Ключи 2 реализуют поразрядное логическое перемножение ко" дов с выходов генератора 4 и блоков памяти 1 и выделения хотя бы одного единичного результата. Регистры 3 реализуют хранение частично сформированных случайных чисел, полностью сформированное (И+М) -разрядное число, распределенное по требуемому закону, образуется на И-м регистре 3)1. Генератор 4 формирует первичные слу чайные числа, используемые для формирования разрядных цифр выходного случайного числа с требуемым законом распределения. Генератор 5 вырабаты,1110 вает поток импульсов, синхронизирую.щих работу всего устройства.Устройство функционирует следующим образом.Для получения на выходе датчикапервого полностью сформированногослучайного числа, распределенногопо требуемому закону, при запускедатчика случайных чисел необходимоМ тактов, после чего числа,с требуемым распределением получают на выходах датчика в каждом такте.Например, при 0=4 на выходе датчика с заданной вероятностью появляется одно четырехразрядное число иэ16 возможных,каждому двоичному числу соответствует вероятность Р его появления,которая определяется, исходя из требуемого закона распределения. Безусловная вероятность его появления В соответствии с этим вероятность 55аоявления единицы в старшем разрядевыходного случайного числа равна Р(а 1 1) Р 9 в+1 +Р +Рз+ц + +Р Вероятность появления нуля в старшем 60 разряде равна 4 4 Я. 4 6 7 9 5 Вероятность появления единицы во втором разряде выходного числа зави6сит от того, какое значение принялстарший разряд.Например, при а=1 Р +Р +Р +РР 1 а =)(а:) =4Р(о= 1)при а =0л5 6 7 9Р(с(2 ")1 о) Р( =О)Аналогично вероятности,. появления нуля во втором разрядеРрР,о+Р+РР(а:оа=) = р аР(а=О(а=о) = Р(а -о)а=о)Для нормального Функционированиядатчика достаточно хранить в блокахпамяти следующие условия вероятности:в первом блокепамяти - Р(а =1),во втором блокепамяти - Р(а=1),Р(а=1/а =О)в третьем блокепамяти - Р(а=1/А =1,а 2=1)Р(аз=1/а=1,а -- 0)Р(а =1/а,- О,а =ЦР(а=1/а=О,а 2=0)в четвертом блокепамяти - Р(а 4=1/а =1,а =1,а =1)Р(а =1/а =1,а=1,а =0)Р(а 4=1/а=1,а =О,а=1)Р ( а 4 -- 1/а ( -- 1, а= О, а -- О )Р(а 4 -- 1/а =О,а 2=1,а=1)Р(а 4=1/а =О,а=1,а =0)Р(а 4=1/а =О,а=О,аз=1)УР(а 4=1/ал=О,а=О,а=О).Итого в блоках памяти хранится 15значений вероятности вместо 16(т.е. (И) значений вместо И) . Значения уже сформированных старших разрядов выходного случайного числа служат адресом выборки иэ 1-го блока памяти вероятности появления единицыв очередном 1-м разряде выходногослучайного числа. Таким образом, значительно упрощена система адресацииблоков памяти.Рассмотрим функционирование устройства в динамике.Двоичное число с выхода генератора 4 поступает на вторые входы ключей 2 4 - 2(, на первый вход первогоиз которых (2 поступает код вероятности появления единицы в старшем разряде выходного случайного числаР(а== Р1=К (2 ф 1где Р( безусловная вероятность появления 1-го числа на выходе датчика,содержащего ф 1 в старшем разряде,В результате этого на выходе вероятностного вентиля появляется сигнал 1 либо О,который поступает на установочный вхоц старшего триг.гера первого регистра З .35 45 50 55 бО 65 Ко второму такту информация, хранящаяся в старшем триггере первогорегистра 3, подается на установочный вход старшего триггера второгорегистра 3 и на адресный вход второго блока памяти 1 , что вызываетпоявление на его выходе кода вероятности появления единицы во второмразряде выходного случайного числа(с учетом условия, что а 4=1, либоа=О), Такие вероятности определяются следующими выражениями:иРР(о,=а=о) = 2 РР(а=а),-И 4+4Р(с: ОМ-РЬ;1),МИо = с(= )=.Е РР(а = )1=М/41 Таким образом, младшие разрядывыходного случайного числа формиру,ются в условной вероятности, опреде) ляемой значениями ранее полученных старших разрядов и требуемым законом распределения.Двоичное одноразрядное число, полученное в результате поразрядного логического перемножения во втором вероятностном ключе 2,когда условная вероятность появления единицы во втором разряде выходного случайного числа и случайного числа с выхода генератора 4, поступает на установочный вход второго триггера второго регистра 3.Одновременно с этим в первый регистр 34 записывается значение старшего разряда очередного случайного числа, сФормированного параллельно с получением второго разряда данного случайного числа.Следовательно, до окончания первых И тактов работы датчика на выходе его отсутствует случайное число, а в регистрах 3 - 3 хранятся )(3+1) -му такту частйчно сформированные случайных числа разрядностью соответственно от 1 до ) .Процесс распространяется по регистрам 3 - 3аналогично до тех пор, пока не будет сформирован младший разряд первого (с момента запуска) выходного случайного числа. Затем после окончания первых И тактов случайные числа поступают на выход устройства на каждом такте, так как старшие (И) разрядов Формируются параплельно на предыдущих тактах и поступают в И-й регистр храненияслучайного числа 3 из предыдущего (Б"1) -го регистра, И-й разряд Формируется путем поразрядного логического перемножения кода условной вероятности появления единицы в младшем разряде выходного случайного числа из блока памяти 1 Н и случайного числа, поступающего с выхода генератора 4. 5 10 15 20 25 30 Реализованный в предлагаемом уст,ройстве способ формирования случайных чисел может быть назван конвейерным, так как каждое отдельное число проходит от регистра к региструформируясь по частям, как при конвейерной сборке, до получения полностью собранного числа через И тактов, где Н - разрядность числа, определяющая его распределение.Повышение быстродействия и выдача полноразрядных случайных чисел в каждом такте обеспечиваются параллельным и одновременным приформированием младших разрядов к частично сформированным числам в каждом регистре 3 (на каждом рабочем месте конвейера) с последующей передачей полуфабриката в регистр 31,из которого в свою очередь в этот момент аналогичный полуфабрикат был передан в регистр 3и т.д.В последние М (младших) разрядов выходного регистра 3) могут быть дбзаписаны равномерно распределенные . числа, формируемые генератором 4, для уменьшения дискретности квантования по аргументу. прн воспроизведении случайных величин с непрерывными функциями распределения.Технико-экономическая эффективность предлагаемого датчика случайных чисел определяется высоким быстродействием, сочетающимся с достаточной простотой технической реализации.Быстродействие устройства в установившемся режиме, т.е. через Н тактов после запуска, равно быстродействию схем, работающих по методу обратных функций (1) или мини-максному 2-3) .Структура высокорегулярна, что делает перспективным выпуск датчика в виде интегральной схемы специального назначения.Формула изобретенияДатчик случайных чисел, содержащий первый ключ, к первому входу которого подключен выход первого блока памяти, первый регистр хранения случайного числа, включающий И основных триггеров и М дополнительных триггеров, выходы которых являются выходом датчика случайных чисел, генератор равновероятных двоичных чисел, выход которого соединен с вторым входом первого ключа и установочными входами М дополнительных триггеров первого регистра хранения случайного числа, а также генератор тактовых импульсов, выход которого подключен к входу генератора равно- вероятных двоичных чисел, к третьему входу первого ключа и входу синхронизации первого регистра хранения случайного числа, о т л и ч а ющ и й с я тем, что, с целью повышения быстродействия датчика, он содерВВВ 115 Составитель А.КарасовРедактор Л.утехина Техред А.Ач Корректор С.шекм Э 10725/13 Ти ВНИИПИ ло 113035, Иаж 748Государственного к елам изобретений и сква, Ж, Раушск дпис итет ткры наб еСССРйд. 4/ тент, г. Ужгород, ул. Проектная, 4 илиал ППП жит дополнительные (Н) регистрыхранения случайного числа, разрядность которых возрастает соответственно на один от 1 до (М), (Я),блоков памяти и (И) ключей, первыевходы которых подключены к выходамсоответствующих блоков памяти, вторые входы - к выходу генератора рав. -новероятных двоичных чисел, третьивходы - к выходу генератора тактовыхимпульсов и ко входам синхронизациирегистров хранения случайных чиселсоответственно,. а выход каждого извероятностных вентилей подключен кустановочному входу триггера младшего разряда соответствующего регистра хранения случайного числа, выходы разрядных триггеров каждого предыдущего регистра хранения случайного числа, расположенного в порядкевозрастания числа разрядов, подключены к установочным входам старшихразрядных триггеров последующего реГистра хранения случайного числа ик адресным входам последующего блока памяти. Источники информации,принятые во внимание при экспертизе1, Авторское свидетельство СССР9 351209, кл.;: 6 06 Г 7/58, 1970,2. Авторское свидетельство СССРР 430368, кл. 6 06 Р 7/58, 1972.3. Авторское свидетельство СССР15 9 185569, кл. 6 06 Р 7/58,1964 (прототип).