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

 

Союз Советских

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

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. саид-ву (22) Заявлено 070380 (21) 2893400/18-24 (5)) е. с присоединением заявки ¹ (23) Приоритет

G 06 F 7/58

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

СССР но делам изобретений и открытий

Опубликовано 0712.81 Бюллетень Йо45

Дата опубликования описания 07. 12, 81 (53) УДК 681. 325 (088.8) (72) Авторы изобретения

Э.А.Баканович, М.A.Îðëoâ, Л.A.Ñì и В.И.Новиков

Минский радиотехнический инсти (71) Заявитель (54) ДАТЧИК СЛУЧАЙНЫХ ЧИСЕЛ

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

Особенно. эффективны подобные устройства при построении испытательной аппаратуры, входящей в состав вычислительно-моделирующих комплексов. На выходе такой аппаратуры требуется получать до нескольких десятков потоков случайных величин (чисел), подаваемых на испытуемый объект.

Эффективны аппаратурные датчики случайных чисел и в качестве специализированного внешнего устройства к ЭВМ. При этом к датчикам предъявляется ряд часто противоречивых требований, например, необходимость достижения требуемого быстродействия и достаточно простая схемно-конструктивная реализация.

Одним из перспективных направлений в создании датчиков случайных чисел является разработка принципиально новых схемных решений, поз— воляющих снять противоречия в технических требованиях и повысить эффективность новых решений по сравнению с известными. 30.

Известны датчики случайных чисел, основными узлами которых являются блок памяти, генератор первичных равновероятностных двоичных чисел, вероятностные вентили, схемы сравнения, схемы дешифрации, элементы И и

ИЛИ, реализующие для получения чисел с требуемым распределением метод обратных функций, методы рекуррентного и минимаксного преобразований. Эти датчики, работающие по параллельному способу формирования всех цифр выходного случайного числа, сложны, хотя и обеспечивают наибольшее быстродействие.

Более просты схемы датчиков случайных чисел, реализующие метод условных вероятностей,по которому цифры выходного случайного числа формируются последовательно, начиная со старшей.

Рассмотрим эти схемы более детально.

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

888115 датчика. Недостатками этого датчика являются сложность организации цифрового управления характеристиками формируемых случайных чисел и невысокое быстродействие иэ-за большого .числа аналоговых элементов и операций (1) .

Известен датчик случайных чисел, содержащий генератор равномерно распределенных случайных чисел, регистр хранения случайных чисел, генератор тактовых импульсов, счетчик тактов, дешифратор кодовых комбинаций, деШифратор законов распределения, из-, бирательную схему, многоканальный генератор случайных импульсных потоков, вероятностный вентиль, элемен- 15 ты И и элементы ИЛИ, Датчик реализует генерирование случайных чисел по методу условных вероятностей последовательно — цифра за (ифрой (2) .

Недостатком устройства является 2О

его сложность иэ-за необходимости использования сложных генератора случайных импульсов и тактирующего генератора. Другим недостатком является невысокое быстродействие из -за поочередного многотактного формирования всех цифр старших разрядов случайного числа.

Наиболее близким техническим решением к изобретению является датчик случайных чисел, содержащий блок па- ЗО мяти, генератор тактовых импульсов, генератор равновероятных двоичных чисел, блок формирования двоичных случайных цифр (включающий вероятностный вентиль), регистр хранения И случайных чисел, дешифратор кодовых комбинаций, дешифратор номера разряда, избирательную схему. Недостатком устройства является его невысокое быстродействие из-за последовательного 4Q формирования цифр старших разрядов случайного числа (3) .

Целью изобретения является повышение быстродействия датчика случайных чисел.

Поставленная цель достигается тем, что датчик случайных чисел, содержащий первый ключ, к первому входу которого подключен выход первого блока памяти, первый регистр хранения случайного числа, включающий N основных триггеров и И дополнительных триггеров, выходы которых являются выходом датчика случайных чисел, генератор равйовероятных двоичных чисел, выход которого соединен с вторым входом ,первого ключа и установочными входами М дополнительных триггеров первого регистра хранения случайного числа, а также генератор тактовых импульсов, выход которого подключен к ц выходу генератора равновероятных двоичных чисел, к третьему входу первого ключа и входу синхронизации первого регистра хранения случайного числа, снабжен дополнительными (N-1) регистрами хранения случайного числа, разрядность которых возрастает соответственно на один от 1 до (N-1), (N, — 1) блоками памяти и (N-1) ключами, первые входы которых подключены к выходам соответствующих блоков памяти, вторые входы — к выходу генератора равновероятных двоичных чисел, третьи входы — к выходу генератора тактовых импульсов и ко входам синхронизации регистров хранения случайных чисел соответственно. Выход каждого иэ вероятностных вентилей подключен к установочному входу триггера младшего разряда соответствующего регистра хранения случайного числа. Выходы разрядных триггеров каждого предыдущего регистра хранения случайного числа, расположенного в порядке возрастания числа разрядов, подключены к установочным входам старших разрядных триггеров последующего регистра хранения случайного числа и к адресным входам последующего блока памяTH °

На чертеже изображена структурная схема датчика.

Датчик содержит Й блоков памяти (1 -1 (), 1/ ключей (2 -2н), регистры хранения случайного числа (34 -3 ) ), генератор равновероятных двоичных чисел 4 и генератор тактовых импульсов 5.

Первые входы ключей 2А-2 подключены к выходам соответствующих блоков памяти 1 -1„,, вторые входа — к выходу генератора 4 и установочным входам дополнительных триггеров ((И+1) ...,(N+M)) регистра 3)4, третьи входы — к выходу генератора 5 и ко входам синхронизации регистров

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

Блок памяти 1„ служит для хранения и выдачи кодов вероятностей появления единичного значения соответствующей разрядной цифры выходного случайного числа с требуемым законом распределения. Ключи 2 реализуют поразрядное логическое перемножение кодов с выходов генератора 4 и блоков памяти 1 и выделения хотя бы одного единичного результата. Регистры 3 реализуют хранение частично сформированных случайных чисел, полностью сформированное (N+M) -разрядное число, распределенное по требуемому закону, образуется íà N-м регистре 3)1.

Генератор 4 формирует первичные слу чайные числа, используемые для формирования разрядных цифр выходного случайного числа с требуемым законом распределения. Генератор 5 вырабаты888115

P tP +Р +Р

P(a =<)(O = <) 1ъ 14 1в 16

5 P(a1 4) при а =О л

Р5 6 Я ,Р(О2=1) А1=0)"- Р((0)

Аналогично вероятности, появления нуля во втором разряде

Рр i Р1О+Р„„+Р l2 (=« „=") = Р(< .) )

Р1 +Р2.iP +P4

Р(а,=О4а„=o) = Р(а =о)

01=0)

Для нормального функционирования датчика достаточно хранить в блоках памяти следующие условия вероятности: в первом блоке памяти — P(a4 —— 1) во втором блоке памяти Р(аг=1) Р(аг=1/ „ =0) в третьем блоке памяти — P (а —— 1/Q — — 1, а =1)

P (а —— 1/а., =1, а — — О)

P (a3 =1/а„= О, a2=1) (аЗ=1/a =0,a =0) в четвертом блоке памяти — P(а1=1/а =l,а =l,а =1)

Р(а =1/а =l,a2=l,а =О)

P (а4=1/а4 — — 1, а =О, a =i )

Р (а4 — — 1/а4 — — 1, а — — О, a> — — О)

Р (а4=1/а =О,а2=1, а =.1)

Р(а4=1/а =О,а — — l,а =0)

Р(а4=1/а =o а =О,аз=l)

У

P (а4=1/а4 =Î, а2 =О, a> — — 0), Итого в блоках памяти хранится 15 значений вероятности вместо 16 (т.е. (N-l) значений вместо N) . Значения уже сформированных старших разрядов выходного случайного числа служат адресом выборки иэ i-го блока памяти вероятности появления единицы в очередном i-м разряде выходного случайного числа. Таким образом, значительно упрощена система адресации блоков памяти.

Рассмотрим функционирование устройства в динамике.

Двоичное число с выхода генератора 4 поступает на вторые входы ключей 2 4 — 2)(, на первый вход первого из которых .(24 ) поступает код вероятности появления единицы в старшем разряде выходного случайного числа

P(a„= )=-z Р

1=НЯМ где Р(безусловная вероятность появления i-го числа на выходе датчика, содержащего 1 в старшем разряде.

В результате этого на выходе вероятностного вентиля появляется сигнал 1 либо О,который поступает на установочный вхоц старшего триггера первого регистра З .

Безусловная вероят- 20 ность его появления

Двоичное число

1000

0001

0010

0011

0100

0101

0110

0ll1

1000

1001

1010

1011

1100

1101

50,1110

1 ill вает поток импульсов, синхронизирующих работу всего устройства.

Устройство функционирует следующим образом.

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

N тактов, после чего числа,с требуемым распределением получают на выходах датчика в каждом такте.

Например, при N=4 на выходе датчика с заданной вероятностью появляется одно четырехразрядное число иэ

16 возможных.

Каждому двоичному числу соответствует вероятность Pj его появления, которая определяется, исходя из требуемого закона распределения.

В соответствии с этим вероятность SS шоявления единицы в старшем разряде выходного случайного числа равна

Р(а4 l) P +Р +Р +Р +Р +Р +p +p

Вероятность появления нуля в старшем 60 разряде равна

4 .1 Я- 3 4 6 7 9

Вероятность появления единицы во втором разряде выходного числа зави6 сит от того, какое значение принял старший разряд.

Например, при а =l

888115

Ко второму такту информация, хра нящаяся в старшем триггере первого регистра 3, подается на установочный вход старшего триггера второго регистра 3 и на адресный вход второго блока памяти 1, что вызывает появление на его выходе кода вероятности появления единицы во втором разряде выходного случайного числа (с учетом условия, что а —— 1, либо а =0), Такие вероятности определяются следующими выражениями:

И(1

P(a=< (aÄ=o) = 7 P„(P(a„=b), 1= l

Р(с„=о)= (-P(o;-)), и

1(o = 1= >= K P;IP(a„=a).

1=М/4

Таким образом, младшие разряды

: выходного случайного числа формиру.ются в условной вероятности, опреде) ляемой значениями ранее полученных старших разрядов и требуемым законом распределения.

Двоичное одноразрядное число, полученное в результате поразрядного логического перемножения во втором вероятностном ключе 2,когда условная вероятность появления единицы во вто-. ром разряде выходного случайного числа и случайного числа с выхода генератора 4, поступает на установочный вход второго триггера второго регистра 3 .

Одновременно с этим в первый регистр 34 записывается значение старшего разряда очередного случайного числа, сформированного параллельно с получением второго разряда данного случайного числа.

Следовательно, до окончания первых И тактов работы датчика на выходе его отсутствует случайное число, а в регистрах 3 — 3 хранятся

k(j+1) -му такту частйчно сформированные случайных числа разрядностью соответственно от 1 до ) .

Процесс распространяется по регистрам 3,, — 3 (аналогично до тех пор, пока не будет сформирован младший разряд первого (с момента запуска) выходного случайного числа. Затем после окончания первых N тактов случайные числа поступают на выход устройства на каждом такте, так как старшие (N-1) разрядов формируются параплельно на предыдущих тактах и поступают в N-й регистр хранения случайного числа 3 из предыдущего (N"1) -го регистра, N-й разряд форми руется путем поразрядного логического перемножения кода условной вероятности появления единицы в младшем разряде выходного случайного числа из блока памяти 1 ) и случайного числа, поступающего с выхода генератора 4.

Реализованный в предлагаемом уст,ройстве способ формирования случайных чисел может быть назван конвейер ным, так как каждое отдельное число проходит от регистра к регистру формируясь по частям, как при конвейерной сборке, до получения полностью собранного числа через N тактов, где N — разрядность числа, определяющая его распределение.

Повышение быстродействия и выдача полноразрядных случайных чисел в каждом такте обеспечиваются параллельным и одновременным приформированием младших разрядов к частично сформированным числам в каждом регистре 3„. (на каждом рабочем месте конвейера) с последующей передачей полуфабриката в регистр 3„+,),из которого в свою очередь в этот момент аналогичный полуфабрикат был передан в регистр 3„. и т.д.

В последние М (младших) разрядов выходного регистра 3) могут быть д6записаны равномерно распределенные . числа, формируемые генератором 4, для уменьшения дискретности квантования по аргументу прн воспроизведении случайных величин с непрерывными функциями распределения.

Технико-экономическая эффективность предлагаемого датчика случайных чисел определяется высоким быстродействием, сочетающимся с достаточной простотой технической реализации.

Быстродействие устройства в установившемся режиме, т.е. через N тактов после запуска, равно быстродействию схем, работающих по методу обратных функций (1) или мини-максному (2-3) .

Структура высокорегулярна, что делает перспективным выпуск датчика в виде интегральной схемы специального назначения.

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

Датчик случайных чисел, содержащий первый ключ, к первому входу которого подключен выход первого блока памяти, первый регистр хранения случайного числа, включающий N основных триггеров и М дополнительных триггеров, выходы которых являются выходом датчика случайных чисел, генератор равновероятных двоичных чисел, выход которого соединен с вторым входом первого ключа и установочными входами М дополнительных триггеров первого регистра хранения случайного числа, а также генератор тактовых импульсов, выход которого подключен к входу генератора равновероятных двоичных чисел, к третьему входу первого ключа и входу синхронизации первого регистра хранения случайного числа, о т л и ч а юшийся тем, что, с целью повышения быстродействия датчика, он содер888115

Составитель А. Карасов

Редактор Л.утехина Техред A.À÷ Корректор С.Шекмар

Тираж 748 Подписное

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

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

Эаказ 10725/13

Филиал ППП Патент, г. Ужгород, ул. Проектная, 4 жит дополнительные (Н-1) регистры хранения случайного числа, разрядность которых возрастает соответственно на один от 1 до (N-l), (N-l). блоков памяти и (И-l} ключей, первые входы которых подключены к выходам соответствующих блоков памяти, вторые входы — к выходу генератора рав.— новероятных двоичных чисел, третьи входы — к выходу генератора тактовых импульсов и ко входам синхронизации регистров хранения случайных чисел соответственно,. а выход каждого из вероятностных вентилей подключен к установочному входу триггера младшего разряда соответствующего регистра хранения случайного числа, выходы разрядных триггеров каждого предыдущего регистра хранения случайного числа, расположенного в порядке возрастания числа разрядов, подключены к установочным входам старших разрядных триггеров последующего регистра хранения случайного числа р к адресным входам последующего блока памяти.

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

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

:М 351209, кл.;: G 06 F 7/58, 1970.

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

Р 430368, кл. G 06 F 7/58, 1972.

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

15 Р 185569, кл. G 06 F 7/58,1964 (прототип) .