Генератор случайных чисел Советский патент 1982 года по МПК G06F7/58 

(Sk) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ

1

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

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

Однако устройство имеет низкое быстродействие, так как в каждом так-is те его работы формируется только один разряд случайного числа с фиксирован- , ной запятой.

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

Устройство также имеет низкое быстродействие, так как т-разрядное случайное число с фиксиросанной запятой формируется в течение (т+1) тактов.

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

Известное устройство обладает ограниченными функциональными возможностями, поскольку не позволяет формировать нормализованные случайные числа С плавающей запятой с заданным законом распределения, что в конечном сче те снижает его точность. Цель изобретения - повышение точно сти за счет одновременного формирования случайных чисел с фиксированной запятой и нормализованных случайных чисел с плавающей запятой с заданным законом распределения. Поставленная цель достигается тем что в известный генератор случайных чисел, содержащий первый регистр памяти, дешифратор, блок памяти, информационный вход которого через дешифратор соединен с первым выходом первого регистра памяти, генератор тактовых импульсов, схему сравнения, пер вый и второй блоки элементов И, выход второго блока элементов И является первым выходом генератора, генератор равномерно распределенных случай ных чисел, первый выход которого соединен с первым входом схемы сравнения, введены второй, третий и четвертый регистры памяти, коммутатор, блок инверсии кода, сумматор, третий блок элементов И, причем первый и второй управляющие и информационные входы первого регистра памяти соединены с первым и вторым выходами генератора тактрвых импульсов и с выходом схемы сравнения соответственно, второй выход первого регистра памяти подключен к первому управляющему входу генератора тактовых импульсов, входы Пуск и Стоп которого являются соответственно входами Пуск и Стоп генератора, а второй управляющий вход генератора тактовых импульсов подключен к выходу схемы сравнения, третий выход генератора тактовых импульсов под-55 нальная схема блока инверсии кода; на ключен. к управляющему входу блока па- фиг. 5 - временная диаграмма работы мяти и первому входу второго регистра памяти, выход блока памяти соединей с информационным входом второго регистра памяти, выход которого подключен к второму входу схемы сравнения, третий вход которой соединен с четвертым выходом генератора тактовых импульсов, первый, второй и третий входы первого блока элементов И подключены соответственно к третьему выходу первого регистра памяти, к выходу схемы сравнения и к первому выходу генератора тактовых импульсов, выход первого блока элементов И является вторым выходом генератора, пятый выход генератора тактовых импульсов

устройства для формирования случайных чисел. подключен к первому входу коммутатора, второй и третий входы которого соединены с выходом схемы сравнения и с первым выходом генератора тактовых импульсов соответственно, шестой выход генератора тактовых импульсов подключен к четвертому входу коммутатора, к входам третьего регистра памяти, второго и третьего блоков элементов И, к первому входу сумматора и к входу генератора равномерно распределенных случайных чисел, второй и третий выходы которого соединены с пятым входом коммутатора и с информационным входом блока инверсии кода соответственно, седьмой выход генератора тактовых импульсов подключен к первому управляющему входу блока инверсии кода, второй управляющий вход которого соединен с выходом коммутатора, группа выходов которого подключена соответственно к группе входов третьего регистра памяти, группа выходов последнего соединена соответственно «с группой входов второго блока элементов И, группа входов сумматора подключена соответственно к группе выходов блока инверсии кода, второй вход сумматора подключен к выходу четвертого регистра памяти, а группа выходов сумматора соединена соответственно с группой входов третьего блока элементов И, выход которого является третьим выходом генератора. На фиг. 1 приведена структурная схема устройства для формирования случайных чисел; на фиг. 2 - функциональная схема генератора тактовых импульсов; на фиг. 3 .функциональная схема коммутатора; на фиг. 4 - функциоУстройство для формирования случайных чисел содержит первый регистр 1 памяти, дешифратор 2, блок 3 памяти, генератор k тактовых импульсов, второй регистр 5 памяти, схему 6срав нения, первый блок 7 элементов И, ге нератор 8 равномерно распределенных случайных чисел, коммутатор 9 трети регистр 10 памяти, второй блок 11 эле ментов И, четвертый регистр 12 памяти, блок 13 инверсии кода, сумматор 1/4, третий блок 15 элементов И, входы 16 и 17, второй 18, первый 19 и третий 20 выходы. Генератор тактовых импульсов (фиг. 2) содержит элементы-И 21-23, импуль1;ный формирователь 2k, первый триггер. 25, генератор 26 импульсов, BTOpol 27 и третий 28 триггеры, 16, 17, 30, 31 29 элементов И, входы и группу выходов 32. Коммутатор 9 (фиг. 3) содержит ре гистр 33 сдвига, первый 3 и второй 35 блоки элементов И, импульсный фор мирователь 36, элемент НЕ 37,- элемен И 38, третий блок 39 элементов И, блок «0 элементов ИЛИ, входы , группу входов 45, выход 46 и группу выходов 47. Блок 13 (фиг. 4) содержит первый блок 48 элементов И, блок 49 элементов ЗАПРЕТ, второй блок 50 элементов И, блок 51 элементов ИЛИ-НЕ, входы 52 и 53, группу входов и группу выходов 55Генератор случайных чисел работает следующим образом. В каждом такте работы генератора (такт работы задается генератором 4 тактовых импульсов) формируется один разряд bj случайного числа с заданзаконом распределения путем сравнения равномерно распределенного случайного числа с значением функции распределения F(x) в узловой точке X. При этом число снимается с выхода генератора 8 равномерно распределенных случайных чисел, а в регистре 5 находится значение F(x:) функции распределения, которое поступает в регистр 5 из блока 3 памяти по сигналам с второй группы выходов регистра 1 и с второго выхода генератора 4 так товых импульсов. Сравнение равномерно распределенного числа с значением функции распределения F() осуществляется с помощью схемы 6 сравнения в момент времени, задаваемый си|- налом с третьего выхода генератора 4 блок тактовых импульсов. Если при этом окажется, что 7iF (), то на выходе схемы 6 сравнения появится единичный си|- нал . (х), то . Здесь j - текущий номер разряда случайного числа с заданным законом распределения. Сформированный таким образом си1- нал (разряд) bi, где ,ni поступает одновременно на вход младшего разряда регистра 1, на четвертый вход генератора Ц тактовых импульсов, на второй вход первого блока 7 элементов И и на первый вход коммутатора 9- Здесь т - разрядность формируемых случайных чисел. Случайное число с фиксированной запятой формируется в регистре 1, который одновременно является и адресным регистром блока 3 памяти. До начала каждого цикла формирования очередного случайного числа по сигналу с четвертого выхода генератора тактовых импульсов m разрядный регистр 1 в начальное состоя I. . 001, т. е. в Р °0 гистр 1 записывается двоичный код, имеющий единицу только в одном младшем разряде. По этому адресу в запоминающем устройстве 3 записано значение функции распределения при ,5, т. е. F(0,5). Поэтому в первом такте работы устройства формируется первый разряд t) случайного числа путем сравнения с F(0,5). Результат сравнения (т. е. сигнал Ь,) поступает в младший разряд регистра 1, содержимое которого в это же время по сигналу с перво/о выхода генератора 4 тактовых импульсов сдвигается на один разряд в сторону старших разрядов. Таким образом по окончании формирования первого разряда {i случайного числа в регистре 1 будет находиться код 00 ... ООЪф Во втором такте формируется второй разряд Ьл случайного числа. При этом в зависимости от значения сигнала Ь из блока памяти в регистр 5 будет считано либо значение F(0,25) функции распределения, либо F(0,75)Это объясняется тем, что по адресу 00...010 (т. е. при ) в блоке памяти записано значение F(0,25), а по адресу 00...011 (т. е. при ) Значение F(0,75). Поэтому, если Ь 0 (т. е. (0,5)), тоиз блока памяти в регистр 5 будет считано значение F(0,25) функции распределения, подсчитанное на середине интервала (0,05), а при Ь 1 (т, е. при / (0,5)) значение F(0,75) функции F(х ), подсчитанное на середине интервала (0.5,1). В результате сра&не ния k с значением функции распределения, находящимся в регистре 5, во вто ром такте будет сформирован второй разряд Ь-2, случайного числа. Сформированный сигнал Ьл с выхода схемы 6 сравнения поступит в младший разряд регистра 1, в результате чего в регистре 1 установится новый код 00...1 поскольку содержимое регистра 1 по сигналу с первого выхода генератора тактовых импульсов вновь сдвигается ни один разряд, а в освободивший ся при этом младший разряд записывается знамение сигнала Ьл- Описанный процесс сравнения равномерно распреде ленного случайного числа со срединными значениями функции F(x) будет продолжаться m тактов, примем в т-ом такте в регистре 1 будет находиться код ,... .. В m-OM такте содержимое регистра (за исключением старшего разряда, в котором записана единица), а также значение т-го разряда Ь снимаемое свыхода схемы 6 сравнения, через вый блок 7 элементов И по сигналу метвертого выхода генератора k тактовых импульсов поступает на первую группу 18 выходов устройства. Действи тельно, первая группа входов блока 7 элементов И соединена с выходами (т-1 ) младших разрядов регистра 1, т. е. с выходами тех разрядов регистра Г, е которых находится код . , . а второй вход блока 7 подключен к выходу схемы 6 сравнения,с которой снимается в т-ом такте сигнал Ь Таким Образом в т-ом такте на выход 18 устройства проходит т-разрядное случайно . фиксированчислоной запятой (запятая фиксирована ред старшим разрядом b/t)- При необходимости разрядность формируемых случайных чисел может быть увеличена за счет добавления к т-разрядному числу разрядов равномерно распределенного снимаемого с выхода случайного числа, генератора 8. Рассмотрим теперь процесс формирования нормализованного случайного числа с плавающей запятой. Как известно,

запятой представлячисло с плавающей

то М ется в следующем виде М-2, где

мантисса числа; Р - порядок числа 9 с

торый является обратным кодом отрицательного числа , ... 001 (работа блока 13 будет рассмотрена ниже). По38Число является нормализованным, если в старшем разряде мантиссы стоит единица. Использование нормализованных чисел ведет к повышению точности решения задач, так как любая величина представляется нормализованным числом с наибольшей точностью. В данном генераторе мантисса числа формируется в третьем регистре 10, а порядок числа - в сумматоре It. До начала формирования каждого случайного числа по сигналу с шестого выхода генератора 4 тактовых импульсов третий регистр 10 устанавливается в начальное с;остояние 100...00, а в сумматор 14 заносится код, который снимается с выхода четвертого регистра 12. Таким образом, до начала формирования случайного числа старший разряд регистра 10 всегда будет находиться в единимном состоянии, тогда как осталь- ные разряды регистра 10 будут находиться в нулевом состоянии. Поскольку выход схемы 6 сравнения мерез коммутатор 9 подключен к разрядным входам третьего регистра 10, то сформированные схемой 6 сравнения сигналы Ь; (разряды случайного числа) поступают на входы соответствующих разрядов регистра 10. Коммутатор работает таким образом, что если сигнал Ь. следующие за ним сигналы Ь ,Ь,, ...,Ьр равны нулю, то они не смогут пройти на входы регистра 10 (работа коммутатора 9 будет описана ниже). Таким образом, если все старшие 1 разрядов случайного числа, где Km, равны нулю, то регистр 10 не изменит своего начального состояния, равного 100...00. Однако каждый нулевой сигнал Ь; , входящий в начальную серию нулевых сигналов, будет вызывать появление в следующем такте на седьмом выходе генератора k тактовых импульсов единичного сигнала временная диаграмманафиг. 5, в которой числами обознамены номера соответствующих входов и выходов генератора тактовых импульсов). Сформированные таким образом единичные сигналы с седьмого выхода генератора ; тактовых импульсов поступают на второй вход блока 13, в котором формируются коды слагаемых, поступающих на входы сумматора 14. В частности, по сигналу с седьмого выхода генератора k тактовых импульсов в блоке 13 формируется k-разрядный код 11. ..110, ко99скольку группа выходов блока 13, по которой поддается k-разрядный код соединена с разрядными входами k-разрядного накапливающего сумматора 1, то в сумматоре будет происходить ело жение поступающего на его входы числа с содержимым данного сумматора. Таким образом, каждый единичный сигнал, поступающий на второй вход блока 13 (особый случай составляет рабо та блока 13 в т-ом такте), вызывает поступление на входы сумматора I ко да 11... 110. Поскольку накапливающий сумматор 1Ц работает в режиме суммирования чисел в обратном коде, то поqтyплeниe его на входы кода -11... 11 ведет к вычитанию из содержимого сумматора единицы, так как названный код является обратным кодом отрицательного числа ,.., 001. Таким образом каждый нулевой сигнал Ь .входящий в начальную серию, состоящую из нулевых сигналов, вызовет уменьшение содержимого накапливающего сумматора на единицу. Но сумматор k предназначен ДЛЯ формирования порядка числа с плавающей запятой. Следовательно, если все 1 старших разрядов случайного чис ла равны нулю, где Um, то порядок такого числа будет уменьшаться на 1 единиц. Поскольку нормализация чисел 1 старших разрядов мантиссы которых равны нулю, заключается в сдвиге мантиссы влево на 1 разрядов и уменьшении порядка на 1 единиц, то в результате предлагаемое устройство формирует нормализованное случайное число с плавающей запятой, так как по окончании начальной серии, состоящей из 1 нулевых сигналов , в m-l старшие разряды регистра 10 записываются оставшиеся разряды случайного числа. Коммутатор 9 как раз и предназначен для занесения в соответствующие разряды регистра 10 разрядов Ьд случайного числа. Эти разряды поступают на первый вход коммутатора 9 с выхода схемы 6 сравнения и проходят на входы соответствующих разрядов регистра 10. В 1 младшие разряды регистра 10 через коммутатор 9 поступает равномерно распреде ленное случайное число с второй группы выходов генератора 8. Пример. Пусть предлагаемое устройство сформировало шестиразрядное случайное число, с фиксированной запятой, равное 0,001001,, т. е. в рассматриваемом примере . Тогда старшие два нулевых разряда случайного 3 числа вызовут уменьшение содержимого сумматора 1 на две единицы, а код 1001 поступит в четыре старших разряда регистра 10. Таким образом, в случае нулевого состояния регистра 12 предлагаемое устройство за шесть тактов сформирует нормализованное случайное число с плавающей запятой, равное 0,1001 а,.а,- 2, так как в шестом такте в два младших разряда регистра 10 через коммутатор 9 с второй группы выходоа генератора 8 поступит двухразрядное равномерно распределенное (в рассматриваеслучаиное число а а мом примере регистр 10 является шестиразрядным и по истечении шести тактов в нем будет находиться код 1001 а-а, а в сумматоре k будет находиться порядок числа . .. 101 ). Очевидно, если в старшем разряде формируемого случайного числа уже имеется единица (т. е. случайное число уже является нормализованным), то содержимое сумматора k останется без изменения, а само случайное число поступит через коммутатор 9 в регистр 10 без сдвига. По сигналу с шестого выхода генератора тактовых импульсов сформированное случайное число с плавающей запятой с выходов регистра 10 и сумматора Т через блоки 11 и 15 элементов И поступит на выходы 19 и 20 устройства. При этом на группу выходов 19.проходит мантисса числа, а на выходы 20 - порядок числа. По заднему фронту импульса с шестого выхода генератора тактовых импульсов регистр 10 и сумматор 1Ц устанавливаются в начальное состояние и устройство начинает формировать следующее случайное число (запуск генератора 8 равномерно распределенных случайных чисел происходит по сигналам с шестого выхода генератора 4 тактовых имПульсов). Устройство будет продолжать работу до тех пор, пока на его вход 17 не .поступит сигнал Останов. По этому сигналу генератор t тактовых импульсов прекращает формировать управляющие импульсы и устройство заканчивает свою работу. Рассмотрим более подробно работу отдельных блоков генератора. Генератор k тактовых импульсов (фиг. 2) предназначен дляформирования сигналов, управляющих работой предлагаемого устройства. Работу генератора k поясняет, пример временной , 11 98 диаграммы (фиг. 5), в котором N и ht обозначают соответственно номер цикла и текущий номер такта внутри каждого цикла, а числами обозначены номера входов и выходов генератора k тактовых импульсов. На диаграмме Jti, Т„ и обозначают состояния триггеров 25, 27 и 28 соответственно. Диаграмма построена для случая . По сигналу с первого выхода 324 генератора 4 тактовых импульсов происходит сдвиг содержимого первого регистра 1 на один разряд в сторону старших разрядов. Поэтому импульсы на первом выходе генератора k формируются в каждом такте за исключейием последнего такта кёждого цикла. В, последнем т-ом такте каждого цикла проис ходит установка т-разрядного регистра 1 в начальное состояние, равное 00... 001, Названная установка происходит по сигналу с четвертого выхода 32 генератора и тактовых импульсов, который формируется в т-ом такте каждого цикла (пример временной диаграммы, приведенной на фиг. 5). В каждом цикле, состоящем из m тактов, в предлагаемом устройстве формируется одно случайное число с заданным законом , распределения,Момент окончания очередного цикла определяется по сигналу, поступающему на первый вход генератора t тактовых импульсов с .первого выхода регистра 1 Первый выход регистра 1 является выходом его старшего т-го разряда, Будем считать, что регистр 1 построен по двухступенчатой схеме (на основе двухступенчатых триггеров), исключающей возникновение неустойчивых состоя НИИ. Поэтому переходы регистра, из одного состояния в другое происходят по заднему фронту управляющих сигналов, поступающих на его первый или второй входы. Поскольку начальное состояние регистра 1 равно 00..,001, а в каждом такте его содержимое сдвигается на один разряд влево по заднему фронту сигнала с первого выхода генератора k тактовых импульсов, то едини ца, первоначально занесенная в младший разряд, достигнет старшего т-го рёзряда только через т-1 тактов, т, е. а начале т-го такта на первом выходе регистра 1 появится единичный сигнал Этот единичный сигнал поступит на, пер вый вход 30 генератора i тактовых импульсов и переведет триггер 25 в еди ничное состояние (на временной диагра 5, показано. на фиг. приведеннои ме, как изменяются состояния триггеров Т, ат работы предлагаемого устройства). Поскольку первый выход триггера 25 подключен к первым входам элементов И 29, то на выходе названных элементов И (т. е, на выходах . и 32 генератора t тактовых импульсов) импульс может появиться в тот момент времени, когда три1- гер 25 находится в единичном состоянии, т. е, в т-ом такте, либо в начале первого такта следующего цикла, так как триггер 25 по заднему фронту сигнала с первого выхода генератора 26 импульсов в первом такте следующе го цикла вернется в нулевое состояние. Таким образом, на четвертый 3 и шестой 32л выходы генератора 4 смогут пройти только по одному импульсу в каждом цикле. В свою очередь первый вход элемента И 29 подключен к втоорому (инверсному) выходу триггера 25. :Поэтому на выходе элемента И 29 (т.е, на первом выходе 32 генератора 4) импульсы появляются в те моменты времени, когда триггер 25 находится в нулевом состоянии, т. е. в течение всего цикла за исключением т-го такта. Генератор 26 импульсов вырабатывает на первом и втором своих выходах две серии импульсов, сдвинутых друг относительно друга на половину периода, которые проходят соответственно на второй 32 и третий 32 выходы генератора k тактовых импульсов. Запуск генератора 26 импульсов происхс/дит по сигналу, поступающему .на второй вход 16 генератора тактовых импульсов. В генераторе 4 тактовых импульсов используются три триггера, причем первый триггер 25 - синхронный двухступенчатый триггер 1К типа, второй триг ®Р 1 асинхронный триггер 1К типа, третий триггер 28 - синхронный триггер D типа. Кроме того, триггер 25 имеет асинхронный установочный вход в единичное состояние, а триггеры 27 и 28 имеют асинхронные установочные входы в нулевое состояние. Названные асинхронные входы подключены к входу 16 генератора тактовых импульсов. Поэтому в момент поступления сигнала Пуск на вход 16 триггер 25 перейдет в единичное состояние, а триггеры 27 и 28 - в нулевое состояние. Названные состояния триггеров являются их начальными состояниями.

Четвертый вход 31 генератора товых импульсов подключен к выходу схемы 6 сравнения. Поэтому единичный 1 с выхода схемы 6 сравнесигнал Ь.

ния при условии, что триггер 25 нахо- s му на пятый вь1ход 32j- генератора 4 дится в нулевом состоянии, пройдет че рез элемент И 21 на первый вход (вход I ) триггера 27 и переведет его в единичное состояние. Следовательно триггер 27 будет находиться в начальном нулевом состоянии до прихода первого, отличного от нуля сигнала где , т. е. до тех пор, пока на вы ходе схемы 6 сравнения формируется начальная серия следующих друг задру гом нулевых сигналов. Поскольку вторые (инверсные) выходы триггеров 25 и 27 через элемент И 23 подключены к первому входу (входу О)триггера 28, то триггер 28 перейдет в единичное состояние в момент прихода на его вто рой вход (вход синхронизации С) импульса с первого выхода генератора 26 импульсов при условии, что триггеры 25 и 27 находятся в нулевйК состоянии. Если же триггер 25 или триггер 27 перейдут в единичное состояние, то это вызовет переход триггера 28 в нулевое состояние. Выход триггера 28 подключен к первому входу элемента И 29е- Поэтому на седьмой выход 32 генератора тактовых импульсов единичные сигналы с второго выхода генератора 26 через формирователь 2 и элемент И 29г смогут пройти только в те моменты времени, когда триггер 28 находится в единичном состоянии (т.е пока тр 1ггеры 25 или 27 не перейдут в единичное состояние). Но триггер 27 будет переведен в единичное состояние первым, отличным от нуля сигналом bg с°йыхода схемы 6 сравнения. Следовательно, на седьмой выход 32-j генератора смоисет пройти только 2 импульсов, где t количество нулевых сигналов, появившихся на выходе схемы 6 сравнения с момента начала формирования очередного случайного числа и до первого единичного сигнала ус ловии, что litm. Поскольку седьмой выход генератора k тактовых импульсов подключен к второму входу блока 13 логических элементов, то в результате содержимое сумматора по сигналам с седьмого выхода генератора будет уменьшено на Ц единиц, где Km. Если .т, то на седьмом выходе генератора k появится t-1 импульсов (работа пред9800931

Ц так- латаемого устройства в этом случае будет рассмотрена ниже).

Первый выход триггера 27 подключен к первому входу элемента И 29. Поэтотактовых импульсов единичные сигналы с первого выхода генератора 26 через элемент И 29 смогут пройти лишь в те моменты времени, когда триггер 27 нав единичном состоянии, т. е. ходится после появления на выходе схемы 6 сравнения первого, отличного от нуля СИ1- нала Ьр , . Заметим, что в кажbtдом цикле количество импульсов на пятом выходе 32 генератора k равно т-1-Е.при и равно нулю при . Импульсы с пятого выхода генератора k поступают иа третий вход коммутатора 9 и разрешают прохождение сигналов с выхода схемы 6 сравнения через КОммутатор 9 на соответствующие входы регистра 10. Следовательно, если в первых тактах очередного цикла, где будет сформировано на выходе схе„у сравнения t нулевых сигналов, то эти нулевые сигналы Ь- не смогут пройти через коммутатор 9 на входы регистра 10, но содержимое сумматора 1 в этом случае будет уменьшено на f единиц, а в регистре 10 поступят разряды случайного числа, следующие за первым, отличным от нуля разрядом (сигналом) Ьп. Это объясняется тем, что т-1-1 младших разрядов случайного числа по сигналам с пятого выхода генератора тактовых импульсов пройдут через коммутатор 9 на соответствующие входы регистра 10,а первый, отличный от нуля разряд bg. случайного числа на первый вход регистра 10 через коммутатор 9 не поступает, так как при установке в начальное состояние в первый (старший) разряд регистра 10 уже была записана единица. Сигнал с второго выхода генератора 26 импульсов пройдет через элемент И 22 на второй вход триггера 27 и переведет его в нулевое состояние, если на первый вход элемента И 22 поступит единичный сигнал с первого входа 30 генератора тактовых импульсов. Сигнал, поступающий на первый вход 30 генератора Ц тактовых импульсов, пеpeвoдиt все три триггера в начальное состояние, после чего начинает цикл формирования следующего случайного числа и описанная выше последовательность действия повторяется. 159 Рассмотрим работу коммутатора 9, функциональная схема которого призедена на фиг, } Назначение коммутатора 9 подключать поочередно в каждом такте входы регистра 10, начиная с второго, к выходу схемы 6 сравнения после окончания начальной серии, состоящей из t нулевых сигналов Ь; (в мае ном случае Сможет быть равно и нулю При этом разряды случайного числа, следующие за первым, отличным от нуля разрядом Ьр, должен поочередно поступать на входы регистра 10 так, чтобы разряд Ь24-2.попал во второй разряд регистра 10, разряд bg+5 - в третий и т, д., наконец разряд b,--b(m- ый разряд. Кроме того, в т-ом такте . по сигналу, поступающему на второй вход k2, через коммутатор 9 в младшие 1 разрядов () регистра 10 проходит равномерно распределенное случайное число с второй группы выходов генератора 8. Коммутатор 9 содержит т-разрядный регистр 33 сдвига, первая и вторая rpynhbi выходов которого подключены к первой и второй группам входов блока 3 элементов И соответственно. В первую группу выходов,регистра 33 входят прямые выходы всех разрядов регистра 33, исключая выход последнего (самого младшего) разряда, а во вторую группу выходов регистра 33 входят инверсные выходы всех разрядов регистра 33, исключая выход первого (старшего) разряда. Исходное состояние регистра 33 сдвига устанавливается по сигналу с шестого выхода генератора 4 тактовых импульсов. Этот сиг нал поступает на четвертый вход kk коммутатора 9 и записывает в регистр 33 код, равный 100, . .0.0. Поэтому в первом такте каждого цикла единичный сигнал появится только на выходе элемента И З,, так как первый и второй входы элемента И соединены с выходом первого разряда и с инверсным выходом второго разряда регистра 33 соответственно. По первому сигналу с пятого выхода генератора 4 тактовых импульсов, поступающему на третий вход 43 коммутатора 9, регистр 33 сдвига перейдет в следующее состояние 110,..00, так как названный сигнал сдвигает содержимое регистра 33 на один разряд в сторону младших разрядов и одновременно записывает в пер вый (старший) разряд регистра 33 еди3 16 ницу. Но первый сигнал на пятом выходе генератора тактовых импульсов будет сформирован только после появления на выходе схемы 6 сравнения первого, отличного от нуля сигнала. Ь/ e+f т, е. в (1+2)-ом такте. Следовательно, если в течение первых 2. тактов на выходе схемы 6 сравнения появится нулевых сигналов bi, то регистр 33 сдвига не. изменит сбоего начального состояния 100...00, ана выходе элемента И 34. в течение всего этого времени будет единичный сигнал. Если , т, е, если в течение всех m тактов на выходе схемы 6 сравнения не появится ни одного единичного сигнала, то регистр 33 сдвига будет сохранять свое начальное состояние в течение m тактов. Первый k и второй k2 входы коммутатора 9 подключены сортветственно к выходу схемы 6 сравнения и к четвертому выходу генератора k тактовых импульсов, на котором единичный сигнал появляется только в т-ом такте. Поскольку первый и второй входы элемента И 38 подключены через элемент НЕ 37 и формирователь 36 соответственно к входам k и k2 коммутатора 9 то-единичный сигнал на выходе элемента И 38 может появиться только в ш-ом такте при условии, что на первый вход 1 коммутатора 9 поступил с выхода схемы 6 сравнения нулевой сигнал b/j , а на выходе элемента И З,} сформирован единичный сигнал, что возможно только при , Следовательно, единичный сигнал на первом выходе k6 коммутатора 9 появится только вки-ом такте при условии , I Если km, то на третий вход АЗ коммутатора 9 в течение одного цикла поступит m-1-t импульсов с пятого выхода генератора А. тактовых импульсов. При этом первый сигнал с пятого выхода генератора А тактовых импульсов переведет в (1+2)-ом такте регистр 33 сдвига в состояние 110.,,00 и поэтому на выходе элемента И 3 появится единичный сигнал. Этот единичный си|- нал разрешит прохожден 1е сигнала. Ь. с выхода схемы 6 сравнения, поступающего на коммутатора 9 в (1+2)ом такте, через элементы И 35-, и ИЛИ 0 на выход kj коммутатора 9- Аналогично, второй сигнал с пятого выхода генератора тактовых импульсов переведет в следующем (1+3)-ем такте регистр 33 сдвига в состояние 1110,,. 00 и на выходе элемента И З+з появится единичный сигнал, который разрешит прохождение сигнала bg через элементы И 35 и ИЛИ 40 на выход 7 коммутатора 9 и т. д. Описанный процесс будет продолжаться до тех пор, пока в т-ом такте сигнал Ь не пройдет на выход )в коммутатора 9- Кроме того, в т-ом такте на вход Л2 коммутатора 9 с четвертого выхода генератора тактовых импульсов поступит единичный сигнал. Этот сигнал поступит на первую группу входов блока 39 элементов И и разрешит прохождение равно мерно распределенного случайного числа, поступающего на вторую группу входов блока 39 через те элементы Иблока 39 третий вход которых подключен к инверсному выходу разряда регистра 33, находящегося в нулевом состоянии. Поэтому открыты для прохождения равномерно распределенного случайного числа, поступающего с второй группы выходов генератора 8 на группу входов 5 коммутатора 9. будут только те элементы И блока 39, на третий вход которых подается единичный сигнал с инверсного выхода разряда регистра 3 находящегося в нулевом состоянии, I Группа выходов коммутатора 9 подключена к разрядным входам регистIра 10 так, что выход 7 соединен с входом второго разряда регистра 10, выход 47i.. с входом третьего разряда и т. д., выход коммутатора 9 - с входом т-го разряда реги.стра 10 Поэтому сигнал выхода коммутатора 9 поступит во второй разряд регистра 10, сигнал bp,j- в третий разряд и т. д., сигнал в (т-1 )ый разряд. В оставшиеся 1 младшие разряды регистра 10 (им будут соответствовать разряды регистра 33, которые находятся в нулевом состоянии) в т-ом такте по сигналу с входа 2 коммутатора 9 поступит равномерно рас пределенное случайное число с второй группы выходов генератора 8. Таким образом, в т-ом такте в регистре.10 будет находиться мантисса 1 . bg.- m W-C-«-1 1 °° с задан ным законом распределения, в старшем разряде которой всегда будет- записана единица. Здесь а; - значения разрядов равномерно распределенного случайного числа, снимаемого с второй группы выходов генератора 8., Очевидно при 1 О в регистре 10 сформируется 98 3 код 1 . . ., а при 1 m мантисса случайного числа, находящаяся в регистре 10, будет равна 1 ... . При необходимости разрядность мантиссы может быть увеличена за счет добавления к коду, находящемуся в регистре 10, равномерно распределенного случайного числа, снимаемого с генератора 8.. Рассмотрим работу блока 13 функциональная схема которого приведена на фиг. А. Назначение блока 13 формировать коды слагаемых, которые поступают в накапливающий сумматор . где они суммируются с содержимым данного сумматора. Входы 52 и 53 блока 13 логических элементов подключены соответственно к первому выходу коммутатора 9 и к седьмому выходу генератора t тактовых импульсов. Выше быЗ ло показано, что единичный сигнал на первом выходе 46 коммутатора 9 появляется только в т-ом такте при условии , т. е. при условии, что в гпразрядном случайном числе с фиксированной запятой во всех m разрядах записаны нули. В свою очередь, на седьмом выходе генератора k тактовых импульсов может появиться 1 единичных сигналов, если Km, и -1 единичных сигналов при . Здесь, как и прежде, 1 - количество нулевых сигналов Ь.-, появившихся на выходе схемы 6 сравнения с начала формирования очередного случайного числа и до первого, отличного от нуля сигнала Группа выходов 55 блока 13 подключена к входам К разрядного сумматора I, причем выход 55н блока 13 соединен с входом первого (младшего) разряда сумматора k, а выход 551C с входом Кго (самого старшего) разряда сумматора 14, т. е. по сигналу, снимаемому с выхода 55у,блока 13. к содержимому сумматора 14 прибавляется слагаемое, сформированное в блоке 13 логических элементов. Рассмотрим работу блока 13 при 1 т. В этом случае каждый единичный сигнал, поступивший на вход 53 блока; 13 с седьмого выхода генератора 4 тактовых импульсов, вызывает формирование в блоке 13 К-разрядного кода Л 11... 110, который является обратным кодом отрицательного числа ...001. Действительно, в этом случае сигнал f на входе 52 блока 13 равен нулю и поэтому единичный сигнал с входа 53 199 проходит 1ерез элемент ЗАПРЕТ 3 на; ..п,. ,,г ,-1 ... первый вход элемента ИЛИ-НЕ , на выходе которого образуется нулевой сигнал. Это объясняется тем, что второй вход элемента ЗАПРЕТ Э является запрещающим входом и единичный сигнал через элемент ЗАПРЕТ Цд проходит толь ко.при условии . При на выходе элемента ЗАПРЕТ 9/х и на выходе всех элементов И блока 50 будут нулевые сигналы, которые вызовут появление на выходе элементов Sl/z. НЕ единичных сигналов. На остальные выходы группы выходов 55 блока 13 проходит единичный сигнал с второго входа 53 блока 13. В результате имеем, что нулевой -сигнал формируется только,на выходе блока 13 (т. е. равен нулю самый младший разряд слагаемого), а на всех остальных выходах блока 13 появится единичный сигнал, т. е. ...110. Как отмечалось выше поступление кода А/11...110 на входы сумматора Н вызывает уменьшение его содержимого на единицу. После поступления 1 единичных сигналов на вход 53 блока 13 в сумматоре будет проведено 1 операций сложения, в результате чего содержимое сумматора уменьшится на И единиц. Рассмотрим случай . В этом случае работа блока 13 во всех тактах кроме т-го такта не отличается от ранее рассмотренного. В т-ом такте одновременно на входы.52 и 53 блока 13 поступают единичные- сигналы, т. е. в. этом случае. . Сигнал с входа 52 блока 13 поступит на первую группу входов блока 50 элементов И и разрешит прохождение сигналов с выходов блока 9 элементов ЗАПРЕТ на входы блока 51 элементов ИЛИ-НЕ. Одноврет менно единичный сигнал запретит прохождение сигнала с входа 53 блока 13 через элемент ЗАПРЕТ k3. На выходе остальных элементов ЗАПРЕТ блока +9 будут формироваться несовместимые случайные последовательности сигналов, вepoятнoctи появления единичного сигнала в которых равны где q - порядковый номер элемента ЗАПРЕТ в блоке , q 2,6. Например, на выходе элемента ЗАПРЕТ 9. вероятность появления единичного сигнала в т-ом такте равна 2, на выходе элемента ЗАПРЕТ 9 - т. д. Это объясняется тем, что группа входов 5 блока 13 подключена iK третьей группе выхо320дев генератора 8 равномерно распределенных случайных чисел, вероятность появления единичного сигнала на каждом выходе которого равна 2-1 На выходе элемента ЗАПРЕТ . единичный сигнал появится в т-ом такте в случае 1 ттолько при , где С - значение сигнала на входе . Поэтому вероятность появления в т-ом такте при единичного сигнала на выходе элемента ЗАПРЕТ It) равна вероятности события , которое наступает с вероятностью так как вход 5 блока 13 подключен к разрядному выходу генератора 8 равномерно распределенных случайных чисел. На выходе элемента ЗАПРЕТ 9 единичный сигнал появится только при и С-тО, где значение сигнала на входе Вероятности события 1 равна 2 в силу отсутствия корреляции между выходными последовательностями генератора 8. Аналогично, единичный сигнал на выходе элемента ЗАПРЕТ k. появится только при Q, и , т. е. с вероятностью Р( )2и т. д, Выход элемента ЗАПРЕТ 9/1 соединен с первым входом элемента ИЛИ-НЕ 512.Поэтому в т-ом такте при с вероятност;ью выходах блока 13 будет сформирован код ...101, который является обратным кодом отрицательного числа А -0.... Выход элемента И 50/1 соединен с вторыми входами элементов ИЛИ-НЕ и ИЛИ-НЕ 51-2. Поэтому в ш-ом такте при с вероятностью выходе блока 13 будет сформирован код ...100, который является обратным кодом отрицательного числа ... и т. д. Таким образом получили, что в случае т в т-ом такте содержимое сумматора с вероятностью 2 будет уменьшено на две единицы, с вероятностью 2 - на три единицы и т. д. Это необходимо делать для того, чтобы более точно формировать случайные числа, которые по абсолютной величине меньше 2 Известное устройство все числа, которые по абсолютной величине, меньше 2 , где m - разрядность формируемых чисел, представляет нулевым кодом, т. е. с очень большой погрешностью. Поэтому использование предлагаемого устройства позволяет повысить точность представления случайных величин. Заметим, что нормализованные случайные числа с плавающей запятой мож219но получить из чисел с фиксированной запятой, применяя операции сдвига и корректируя соответствующим образом порядок числа. Однако это требует до полнительных затрат времени на прове дение названных выше операций. Поэто му предлагаемое устройство, в которо т-разрядная мантисса случайного числа с плавающей запятой и порядок чис ла формируются за m тактов одновременно с формированием т-разрядного случайного числа с фиксированной запятой, обладает более высоким быстро действием, так как не требует затрат времени на проведение дополнительных операций. Использование новух элементов регистров, коммутатора, блока логичес ких элементов, сумматора, блока элементов И выгодно отличает предлагаемое устройство от прототипа, так как позволяет расширить его функциональ ные возможности, повысить точность представления случайных величин и noвысить скорость формирования случайных чисел с плавающей запятой. Формула изобретения Генератор случайных чисел, содержащий первый регистр памяти, дешифратор, блок памяти, информационный вход которого через дешифратор соединен с первым выходом первого регистра памяти, генератор тактовых импульсов, схе му сравнения, первый и второй блоки элементов И, выход второго блока элементов И является первым выходом гене ратора, генератор равномерно распределенных случайных чисел, первый вы ход которого соединен с первым входом схемы сравнения, отличающийс я тем, что, с целью повышения его точности, он содержит второй, третий и четвертый регистры памяти, коммута тор, блок инверсии кода, сумматор, третий блок элементов И, причем первый и второй управляющие и информационный входы первого регистра памяти соединены соответственно с первым и вторым выходами генератора тактовых импульсов и с выходом схемы сравнения, второй выход первого регистра памяти подключен к первому управляющему входу, генератора тактовых импульсов, входы Пуск и Стоп которого являются соответственно входами Пуск и Стоп генератора, а второй 3 управляющий вход генератора тактовых импульсов подключен к выходу схемы сравнения, третий выход генератора тактовых импульсов подключен к управляющему входу блока памяти и управляющему входу второго регистра памяти, выход блока памяти соединен с инЧ формационным входом второго регистра памяти, выход которого подключен к второму входу схемы сравнения, третий вход которой соединен с четвертым выходом генератора тактовых импульсов, первый, второй и третий входы первого блока элементов И подключены соответственно, к третьему выходу первого регистра памяти, к выходу .схемы сравнения и к первому выходу генератора тактовых импульсов, выход первого блока элементов И является Iвторым выходом генератора, пятый выход генератора тактовых импульсов подключен к первому входу коммутатора, второй и третий входы которого соединены с выходом схемы сравнения и с пе{звым выходом генератора тактовых импульсов соответственно, шестой выход г,енератора тактовых импульсов подключен к четвертому входу коммутатора , к входам третьего регистра памяти, второго и третьего блоков элементов И, к первому входу сумматора и к входу генератора равномерно распределенных случайных чисел, второй и третий выходы которого соединены с пятым входом коммутатора и с информационным входом блока инверсии кода соответственно, седьмой выход генератора тактовых импульсов подключен к первому управляющему входу блока инверсии кода, второй управляющий вход которого соединен с выходом коммутатора, группа выходов которого подключена соответственно к группе входов третьего регистра памяти, группа выходов последнего соединена соответственно ,с группой входов второго блока элементов И, группа входов сумматора подключена соответственно к группе выходов блока инверсии кода, второй вход сумматора подключен к выходу четвертого регистра памяти, а группа выходов сумматора соединена соответственно с группой входов третьего блока элементов И, выход которого является третьим выходом генератора. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР / № 185569, кл.с 06 F 7/58, 196. 2. Авторское свидетельство СССР № 309356, кл. G Об F 7/58, 1970, 980093 t 3 Авторское свидетельство СССР № 378826. кл. G Об F 7/58. 1971 (прототип).

X

30

32

I

-

29

. /7.

1

3/

2/

v

22

2

7

23

2

фиг. 2.

52г

52,

32,

-

2%

29,

Л

f1

29,

32т

295

Мм

4

1 tt2

Л6

t