Генератор случайных чисел

 

Ф

У (72) Автор изобретения

В. M. Тарасов

Казанский ордена Трудового Красного Знамени" ", . авиационный институт им. А.Н. Туполева

Ф (7I ) Заявитель (54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ

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

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

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

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

Устройство также имеет низкое быстродействие, так как m-ðàçðÿäíîå случайное число с фиксированной запятой формируется в течение (m+1 ) тактов.

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

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

И соединены с выходами устройства, no" следний выход генератора тактовых импульсов подключен к второй группе входов второй группы элементов И (3 ).

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

На фиг. 1 приведена структурная схема устройства для формирования случайных чисел; на фиг. 2 - функциональная схема генератора тактовых импульсов; на фиг. 3 .- функциональная схема коммутатора; на фиг. 4 - функциональная схема блока инверсии кода; на фиг. 5. - временная диаграмма работы устройства для формирования случайных чисел.

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

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

0 «À генератора тактовых импульсов подключен к первому входу коммутатора, второй и третий входы которого соединены с выходом схемы сравнения и с первым выходом генератора тактовых импульсов соответственно, шестой выход генератора тактовых импульсов подключен к четвертому входу коммута1 тора, к входам третьего регистра памяти, второго и третьего блоков элементов И, к первому входу сумматора и к входу генератора равномерно распределенных случайных чисел, второй и третий выходы которого соединены с пятым входом коммутатора и с информационным входом блока инверсии кода соответственно, седьмой выход генератора тактовых импульсов подключен к первому управляющему входу блока инверсии кода, второй управляющий вход которого соединен с выходом коммутатора, группа выходов которого подключена соответственно к группе входов третьего регистра памяти, группа выходов последнего соединена соответственно с группой входов второго блока элементов И, группа входов сумматора подключена соответственно к группе выходов блока инверсии кода, второй вход сумматора подключен к выходу четвертого регистра памяти, а группа выходов сумматора соединена соответственно с группой входов третьего блока элементов И, выход которого является третьим выходом генератора.

3 6 тактовых импульсов. Если при этом окажется, что g?p F (х„ ), то на выходе схемы 6 сравнения появится .единичный сигнал Ь =.1. Если <а (х ), то b> 0. Здесь

7 текущий номер разряда случаиного числа с заданным законом распределения. Сформированный таким образом сигнал (разряд) Ь -, где j=l,m поступает одновременно на вход младшего разряда регистра 1, на четвертый вход генератора 4 тактовых импульсов, на второй вход первого блока 7 элементов И и на первый вход коммутатора 9. Здесь

m — разрядность формируемых случайных чисел.

Случайное число с фиксированнои запятой формируется в регистре 1, который одновременно является и адресным регистром блока 3 памяти. До начала каждого цикла формирования очередного случайного числа по сигналу с четвертого выхода генератора 4 тактовых импульсов m разрядный регистр 1 устанавливается в начальное состояние, равное 00 ... 001, т. е. в регистр 1 записывается двоичный код, имеющий единицу только s одном младшем разряде. По этому адресу в запоминающем устройстве 3 записано значение функции распределения при х=0,5, т. е. F (0,5). Поэтому в первом такте работы устройства формируется первый разряд ф случайного числа путем сравнения g с F(0,5). Результат сравнения (т. е. сигнал Ъ ) поступает в младший разряд регистра 1, содержимое которого в это же время по сигналу с первого выхода генератора 4 тактовых импульсов сдвигается на один разряд в сторону старших разрядов. Таким образом по окончании формирования первого разряда Q< случайного числа в регистре 1 будет находиться код 00 ...

00 ф4. Во втором такте формируется второй разряд Ь случайного числа. При этом в зависимости от значения сигнала Ь из блока памяти в регистр 5 бу1 дет считано либо значение F (0,25) функции распределения, либо F(0,75).

Это объясняется тем, что по адресу

00...010 (т. е. при Ь4- †0 ) в блоке памяти записано значение F (0,25), а по адресу 00...011 (т. е. при Ь1=1)— значение Е(0,75). Поэтому, если Ь =О (т. е. если 1 < Е (0,5) ), то из блока памяти в регистр 5 будет считано значение F(0,25) функции распределения,,l подсчитанное на середине интервала

5 98009

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

1 памяти, дешифратор 2, блок 3 памяти, генератор 4 тактовых импульсов, второй регистр 5 памяти, схему 6 срав- нения, первый блок 7 элементов И, генератор 8 равномерно распределенных случайных чисел, коммутатор 9, третий регистр 10 памяти, второй блок 11 эле ментов И, четвертый регистр 12 памя- 10 ти, блок 13 инверсии кода, сумматор

14, третий блок 15 элементов И, входы 16 и 17, второй 18, первый 19 и третий 20 выходы.

Генератор 4 тактовых импульсов ts (фиг. 2 ) содержит элементы .И 21-23, . импульсный формирователь 24, первый триггер. 25, генератор 26 импульсов, вторс"1 27 и третий 28 1риггеры, блок

29 элементов И, входы 16, 17, 30, 31 уо и группу выходов 32.

Коммутатор 9 (фиг. 3) содержит регистр 33 сдвига, первый 34 и второй

35 блоки элементов И, импульсный формирователь 36, элемент НЕ 37, элемент 2

И 38, третий блок 39 элементов И, блок 40 элементов ИЛИ, входы 41-44, группу входов 45, выход 46 и группу выходов 47.

Блок 13 (фиг. 4 ) содержит первый блок 48 элементов И, блок 49 элементов ЗАПРЕТ, второй блок 50 элементов

И, блок 51 элементов ИЛИ-НЕ, входы

52 и 53, группу входов 54 и группу выходов 55.

Генератор случайных чисел работает следующим образом.

В каждом такте работы генератора (такт работы задается генератором 4 тактовых импульсов) формируется один 4 разряд Ь случайного числа с заданнйм закойом распределения путем сравнения равномерно распределенного случайного числа с значением функции распределения F(x ) в узловой точке х . При этом число 1 снимается с выхода генератора 8 равномерно распре4 деленных случайных чисел, а в регистре 5 находится значение F(x ) функции распределения, которое поступает в регистр 5 из блока 3 памяти по сигналам с второй группы выходов регистра

1 и с второго выхода генератора 4 так товых импульсов. Сравнение равномерно распределенного числа 1 с значением функции распределения F(x„ ) осуществляется с помощью схемы Ь сравнения в момент времени, задаваемый сигналом с третьего выхода генератора 4

7 9800 (0,05), а при b4=1 (т, е. при

> F(0,5 )) - значение F(0,75) функции

F (x ), подсчитанное на середине интервала (0.5,1). В результате сравие ния с значением функции распределения, находящимся в регистре 5, во вто ром такте будет сформирован второй разряд Ь случайного числа. Сформированный сигнал Ь с выхода схемы 6 сравнения поступит в младший разряд регистра 1, в результате чего в регистре 1 установится новый код 00...1

Ь„ b, поскольку содержимое регистра 1 по сигналу с первого выхода генератора 4 тактовых импульсов вновь сдвига- ется на один разряд, а в освободившийся при этом младший разряд записывается значение сигнала b . Описанный процесс сравнения равномерно распределенного случайного числа g со средин- 20 ными значениями функции F(х ) будет продолжаться m тактов, причем в m-ом такте в регистре 1 будет находиться код 1b b>.. Ь Ь

В m-ом такте содержимое регистра 1 25 (за исключением старшего разряда, в котором записана единица ), а также значение m-ro разряда Ь снимаемое с выхода схемы 6 сравнейия, через первый блок 7 элементов И по сигналу с эв четвертого выхода генератора 4 тактовых импульсов поступает на первую группу 18 выходов устройства. Действительно, первая группа входов блока 7 элементов И соединена с выходами (m-1 ) младших разрядов регистра 1, т. е. с выходами тех разрядов регистра 1, в которых находится код Ь„ Ь ...Ь Ь а второй вход блока 7 подключен к выходу схемы 6 сравнения,с которой сни- 40 мается в m-ом такте сигнал Ь Таким образом в m-ом такте на выход 18 уст-, ройства проходит m-разрядное случайное" число Ь„ Ь ...Ь, Ь „Ь с фиксированной запятой (запятая фиксирована пе 45 ред старшим разрядом b4 ). При необходимости разрядность формируемых случайных чисел может быть увеличена за счет добавления к m-разрядному числу разрядов равномерно распределенного

1 случайного числа, снимаемого с выходе генератора 8.

Рассмотрим теперь процесс формирования нормализованного случа" íîãî числа с плавающей запятой. Как известно, 55 число с плавающей запятой представляется в следующем виде И 2, где Имантисса числа; Р - порядок числа.

93 8

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

В данном генераторе мантисса числа формируется в третьем регистре 10, а порядок числа — в сумматоре 14. До начала формирования каждого случайного числа по сигналу с шестого выхода генератора 4 тактовых импульсов третий регистр 10 устанавливается в начальное состояние 100...00, а в сум1 матор 14 заносится код, который снимается с выхода четвертого регистра

12. Таким образом, до начала формирования случайного числа старший разряд регистра 10 всегда будет находиться в единичном состоянии, тогда как осталь- . ные разряды регистра 10 будут находиться в нулевом состоянии. Поскольку выход схемы 6 сравнения через коммутатор 9 подключен к разрядным входам третьего регистра 10, то сформированные схемой 6 сравнения сигналы b. (разряды случайного числа) поступают на входы соответствующих разрядов регистра 10.

Коммутатор работает таким образом, что если сигнал b и следующие эа ним сигналы Li,,Ь . . .Ь равны нулю, то они не смогут пройти на входы регистра 10 (работа коммутатора 9 будет описана ниже). Таким образом, если все старшие 1 разрядов случайного числа, где 1Km, равны нулю, то регистр 10 не изменит своего начального состояния, равного 100...00. Однако каждый нулевой сигнал Ь входящий в начальную сеФ рию нулевых сигналов, будет вызывать появление в следующем такте на седьмом выходе генератора 4 тактовых импульсов единичного сигнала временная диаграмма на фиг. 5, в которой числами обозначены номера соответствующих входов и выходов генератора 4 тактовых импульсов).

Сформированные таким образом единичные сигналы с седьмого выхода генератора 4, тактовых импульсов поступают на второй вход блока 13, в котором формиру-. ются коды слагаемых, поступающих на входы сумматора 14. В частности, по сигналу с седьмого выхода генератора

4 тактовых импульсов в блоке 13 формируется k-разрядный код 11... 110, ко. торый является обратным кодом отрицательного числа A=-0, ... -001 (работа блока 13 будет рассмотрена ниже ). По980093 l0 скольку группа выходов блока 13, по которой подается k-разрядный код соединена с разрядными входами k-разрядного накзплчвающего сумматора 14, то в сумматоре будет происходить сложение поступающего на его входы числа с содержимым данного сумматора.

Таким образом, каждый единичный сигнал, поступающий на второй вход блока 13 (особый случай составляет рабо- to та блока 13 в m-ом такте), вызывает поступление на входы сумматора 14 кода 11...110. Поскольку накапливающий сумматор 14 работает в режиме .суммирования чисел в обратном коде,,то по- >5 ступление его на входы кода -11... 110 ведет к вычитанию из содержимого сумматора единицы, так как названный код является обратным кодом отрицательного числа A=-О,... 001. Таким обра".îè, gp каждый нулевой сигнал Ь,входящий в начальную серию, состоящую иэ нулевых сигналов, вызовет уменьшение содержимого накапливающего сумматора 14 на единицу. Но сумматор 14 предназначен для формирования порядка числа с плавающей запятой. Следовательно, если все 1 старших разрядов случайного числа равны нулю, где Ь;m, то порядок такого числа будет уменьшаться на 1 единиц. Поскольку нормализация чисел

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

9 как раэ и предназначен для занесения в соответствующие разряды регистра 10 разрядов Ь . случайного числа.

Эти разряды поступают на первый вход коммутатора 9 с выхода схемы 6 сравнения и проходят на входы соответствующих разрядов регистра 10. В 1 младшие разряды регистра 10 через комму,50 татор 9 поступает равномерно распределенное случайное число с второй группы выходов генератора 8.

Пример. Пусть предлагаемое устрОйство сформировало шестиразряд55 ное случайное число. с фиксированнои запятой, равное 0,001001„ т. е. в рассматриваемом примере п =б. Тогда старшие два нулевых разряда случайного числа вызовут уменьшение содержимого сумматора 14 на две единицы; а код

1001 поступит в четыре старших разряда регистра 10. Таким образом, в случае нулевого состояния регистра 12 предлагаемое устройство за шесть тактов сформирует нормализованное случайное число с плавающей запятой, равное 0 1001 а а - 2-, так как в шестом

s ь такте в два младших разряда регистра

10 через коммутатор 9 с второй группы выходов, генератора 8 поступит двухразрядное равномерно распределенное случайное число а а (в рассматривае6 мом примере регистр 10 является шестиразрядным и по истечении шести тактов в нем будет находиться код 1001 а а а в сумматоре 14 будет находить6 ся порядок числа Р=-2=11...101).

Очевидно, если в старшем разряде формируемого случайного числа уже имеется единица (т. е. случайное число уже является нормализованным), то содержимое сумматора 14 останется без изменения, а само случайное число поступит через коммутатор 9 в регистр

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

10 и сумматора 14 через блоки 11 и

15 элементов И поступит на выходы 19 и 20 устройства. При этом на группу выходов 19 проходит мантисса числа, а на выходы 20 - порядок числа. По заднему фронту импульса с шестого выхода генератора 4 тактовых импульсов регистр 10 и сумматор 14 устанавлива- ются s начальное состояние и устроиство начинает формировать следующее случайное число {запуск генератора 8 равномерно распределенных случайных чисел происходит по сигналам с шестого выхода генератора 4 тактовых им,пульсов). устройство будет продолжать работу до тех пор, пока на его вход

17 не поступит сигнал "Останов". По этому сигналу генератор 4 тактовых импульсов прекращает формировать управляющие импульсы и устройство заканчивает свою работу.

Рассмотрим более подробно работу отдельных блоков генератора.

Генератор 4 тактовых импульсов (фиг. 2 ) предназначен для формирования сигналов, управляющих работой предлагаемого устройства. Работу reнератора 4 поясняет пример временнои

11 98009 ,диаграммы (фиг. 5), в котором. Й и Nz обозначают соответственно номер цикла и текущий номер такта внутри каждого цикла, а числами обозначены номера входов и выходов генератора 4 тактовых импульсов. На диаграмме Т в, Т и TzS обозначают состояния триггеров 25, 27 и 28 соответственно. Диаграмма построена для случая а=6.

По сигналу с первого выхода 32! генератора 4 тактовых импульсов происходит сдвиг содержимого первого регистра на один разряд в сторону старших разрядов. Поэтому импульсы на первом выходе генератора 4 формируют- 15 ся в каждом такте за исключением последнего такта каждого цикла. В, последнем m-ом такте каждого цикла происходит установка m-разрядного регистра 1 в начальное состояние, равное го

00..; 001. Названная установка проис-. хо ит по сигналу с четвертого выхода

32! генератора 4 тактовых импульсов, ко-. торый формируется в m-ом такте каждого цикла (пример временной диаграммы, 25 приведенной на фиг. 5). В каждом цикле, состоящем из m тактов, в предлагаемом устройстве формируется одно случайное число с заданным законом распределения. . 30

Момент окончания очередного цикла определяется по сигналу, поступающему на первый вход генератора 4 тактовых импульсов с,первого выхода регистра 1.

Первый выход регистра 1 является выходом его старшего m-го разряда. Будем считать, что регистр 1 построен по двухступенчатой схеме (на основе двухступенчатых триггеров ), исключающей возникновение неустойчивых состоя-40 ний. Поэтому переходы регистра 1 из одного состояния в другое происходят по заднему фронту управляющих сигналов, поступающих на его первый или второй входы. Поскольку начальное со- 45 стояние регистра 1 равно 00...001, а в каждом такте его содержимое сдвигается на один разряд влево по заднему фронту сигнала с первого выхода генератора 4 тактовых импульсов, то едини- „ ца, первоначально занесенная в младший разряд, достигнет старшего m"го разряда только через m-1 тактов, т. е. в начале m-го такта на первом выходе регистра 1 появится единичный сигнал.

„55

Этот единичный сигнал поступит на, первый вход 30 генератора 4 тактовых импульсов и переведет триггер 25 в единичное состояни е (на временной диаграм3 12 ме, приведенной на фиг. 5, показано, как изменяются состояния триггеров Т

Т « T< в процессе работы предлагаемого устройства). Поскольку первый выход триггера 25 подключен к первым входам элементов И 29 и 29А., то на выходе названных элементов И (т. е. на выходах 32, и 32 генератора 4 тактовых импульсов) импульс может появить- ся в тот момент времени,,когда триггер 25 находится в единичном состоянии, т. е. в m-ом такте, либо в начале первого такта следующего цикла, так как триггер 25 по заднему фронту сигнала с первого выхода генератора

26 импульсов в первом такте следующе го цикла вернется в нулевое состояние.

Таким образом, на четвертый 3Q и шестой 32 6 выходы генератора 4 смогут пройти только по одному импульсу в каждом цикле. В свою очередь первый вход элемента И 29„ подключен к второму (инверсному) выходу триггера 25. ,Поэтому на выходе элемента И 29 (т.е. на первом выходе 32 генератора 4 ) импульсы появляются в те моменты времени, когда триггер 25 находится в нулевом состоянии, т. е. в течение всего цикла за исключением m-ro такта.

Генератор 26 импульсов вырабатывает на первом и втором своих выходах две серии импульсов, сдвинутых друг относительно друга на половину периода, которые проходят соответственно на второй 32 и третий 32 выходы генератора 4 тактовых импульсов. Запуск генератора 26 импульсов происходит по сигналу, поступающему на второй вход

16 генератора 4 тактовых импульсов.

В генераторе 4 тактовых импульсов используются три триггера, причем первый триггер 25 - синхронный двухступенчатый триггер !К типа, второй триггер 27 - асинхронный триггер )К типа, третий триггер 28 - синхронный триггер О типа. !(роме того, триггер 25 имеет асинхронный установочный вход в единичное состояние, а триггеры 27 и 28 имеют асинхронные установочные входы в нулевое состояние. Названные асинхронные входы подключены к входу

16 генератора 4 тактовых импульсов.

Поэтому в момент поступления сигнала

"Пуск" на вход 16 триггер 25 перейдет в единичное состояние, а триггеры 27 и 28 - в нулевое состояние. Названные состояния триггеров являются их нача-. льными состояниями.

13 9800

Четвертый вход 31 генератора 4 так.товых импульсов подключен к выходу схемы 6 сравнения. Поэтому единичный сигнал Ь- 1 с выхода схемы 6 сравнения при условии, что триггер 25 находится в нулевом состоянии, пройдет через элемент И 21 на первый вход (вход 1) триггера 27 и переведет его в единичное состояние. Следовательно; триггер 27 будет находиться в началь- 10 ном нулевом состоянии до прихода первого, отличного от нуля сигнала Ь., где jam, т. е. до тех пор, пока на выходе схемы 6 сравнения формируется начальная серия следующих друг за дру-1 гом нулевых сигналов. Поскольку вторые (инверсные ) выходы триггеров 25 и 27 через элемент И 23 подключены к первому входу (входу О) триггера 28, то триггер 28 перейдет в единичное 20 состояние в момент прихода на его второй вход (вход синхронизации С) импульса с первого выхода генератора

26 импульсов при условии, что триггеры 25 и 27 находятся в нулевом состо- 2> янии. Если же триггер 25 или триггер

27 перейдут в единичное состояние, то это вызовет переход триггера 28 в нулевое состояние. Выход триггера 28 подключен к первому входу элемента 30

И 29 . Поэтому на седьмой выход 32 генератора 4 тактовых импульсов едйничные сигналы с второго выхода генератора 26 через формирователь 24 и элемент И 29 смогут пройти только в те моменты времени, когда триггер 28 находится в единичном состоянии (т. е. пока триггеры 25 или 27 не перейдут в единичное состояние). Но триггер 27 будет переведен в единичное состояние 4р первым, отличным от нуля сигналом b<+< е с выхода схемы 6 сравнения. Следова-. тельно, на седьмой выход 32 генератора 4 сможет пройти только 7 импульсов, где В количество нулевых сигна- 4

1 лов, появившихся на выходе схемы 6 сравнения с момента начала формирования очередного случайного числа и до первого единичного сигнала Ь при усI

Я+4 ловии, что Ыа. Поскольку седьмой вы- Ю ход генератора 4 тактовых импульсов подключен к второму входу блока 13 логических элементов, то в результате содержимое сумматора 14. по сигналам с седьмого выхода генератора 4 будет S5. уменьшено на Й единиц, где i(m. Если, ф=м, то на седьмом выходе генератора

4 появится В- l импульсов (работа пред93 14 лагаемого устройства в этом .случае будет рассмотрена ниже ).

Первый выход триггера 27 подключен к первому входу элемента И 29 . Поэтому на пятый вь1ход 32 генератора 4 тактовых импульсов единичные сигналы с первого выхода генератора 26 через элемент И 29> смогут пройти лишь в те моменты времени, когда триггер 27 находится в единичном состоянии, т. е. после появления на выходе схемы 6 сравнения первого, отличного от нуля сигнала b +, +1<а. Заметим, что в каждом цикле количество импульсов на пятом выходе 32 генератора 4 равно

m-1-1Е. при )

Импульсы с пятого выхода генератора 4 поступают на третий вход коммутатора

9 и разрешают прохождение сигналов bj с выхода схемы 6 сравнения через коммутатор 9 на соответствующие входы регистра 10. Следовательно, если в g первых тактах очередного цикла, где

9

15 9800

Рассмотрим работу коммутатора 9, функциональная схема которого приведена на фиг, 3. Назначение коммутатора 9 - подключать поочередно в каждом такте входы регистра 10, начиная с 5 второго, .к выходу схемы 6 сравнения после окончания начальной серии, состоящей из .2 нулевых сигналов Ь.(в част1 ном случае может быть равно и нулю).

При этом разряды случайного числа, следующие за первым, отличным от нуля разрядом Ь, должен поочередно поступать на входы регистра 10 так, чтобы разряд Ьр+ попал во второй разряд регистра 10, разряд by+ — в третий и т. д., наконец разряд Ь -b(m- g)ый разряд. Кроме того, в m-ом такте . по сигналу, поступающему на второй вход 42, через коммутатор 9 в младшие

1 разрядов (1 m) регистра 10 проходит о равномерно распределенное случайное число с второй группы выходов генератора 8.

Коммутатор 9 содержит m-разрядный регистр 33 сдвига, первая и вторая группы выходов которого подключены к первой и второй группам входов блока

34 элементов И соответственно. В первую группу выходов, регистра 33 входят прямые выходы всех разрядов регистра 33, исключая выход последнего (самого младшего) разряда, а во вторую группу выходов регистра 33 входят инверсные выходы всех разрядов

- регистра 33, исключая выход первого (старшего) разряда. Исходное состояние регистра 33 сдвига устанавливается по сигналу с шестого выхода генератора 4 тактовых импульсов. Этот сиг-4О нал поступает ча четвертый вход 44 коммутатора 9 и записывает в регистр

33 код, равный 100...00. Поэтому в первом такте каждого цикла единичный сигнал появится только на выходе эле45 мента И 34<, так как первый и второй входы элемента И 34. соединены с прямым выходом первого разряда и с инверсным выходом второго разряда регистра 33 соответственно. По первому сигналу с пятого выхода генератора 4

50 тактовых импульсов, поступающему на третий вход 43 коммутатора 9, регистр

33 сдвига перейдет в следующее состояние 110...00, так как названный сигнал сдвигает содержимое регистра 33 на один разряд в сторону младших разрядов и одновременно записывает в первый (старший ) разряд регистра 33 еди93 16 ницу. Но первый сигнал на пятом выходе генератора 4 тактовых импульсов будет сформирован только после появле ния на выходе схемы 6 сравнения первого, отличного от нуля сигнала. be+4, т. е. в (1+2 )-ом такте. Следовательно, если в течение первых K тактов на выходе схемы 6 сравнения появится нулевых сигналов b., то регистр 33 сдвига не изменит своего начального состояния 100...00, а на выходе элемента И

34 в течение всего этого времени будет единичный сигнал. Если 1=m, т. е. если в течение всех m тактов на выходе схемы 6 сравнения не появится ни одного единичного сигнала, то регистр

33 сдвига будет сохранять свое начальное состояние в течение m тактов.

Первый 41 и второй 42 входы коммутатора 9 подключены соответственно к выходу схемы 6 сравнения и к четвертому выходу генератора 4 тактовых импульсов, на котором единичный сигнал появляется только в m-ом такте. Поскольку первый и второй входы элемента И 38 подключены через элемент НЕ 37 и формирователь 36 соответственно и входам 41 и 42 коммутатора 9, то-единичный сигнал на выходе элемента И 38 может появиться только в m-ом такте при условии, что на первый вход 41 коммутатора 9 поступил с выхода схемы 6 сравнения нулевой сигнал Ь, а на выходе элемента И 34 сформирован единичный сигнал, что возможно только при 1=m. Следовательно, единичный сигнал на первом выходе 46 коммутатора 9 появится только в уи-ом тлеете при условии 1=m. !

Если 1

При этом первый сигнал с пятого выхода генератора 4 тактовых импульсов переведет в (1+2)-ом такте регистр 33 сдвига в состояние 110...00 и поэтому на выходе элемента И 34 появится единичный сигнал. Этот единичный сигнал разрешит прохождение сигнала. Ь + с выхода схемы 6 сравнения, поступающего на вход 41 коммутатора 9 в (1+2)ом такте, через элементы И 351 и ИЛИ

404 на выход 47< коммутатора 9. Аналогично, второй сигнал с пятого выхода генератора 4 тактовых импульсов переведет в следующем (1+3 )-ем такте регистр 33 сдвига в состояние 1110...

17 98009

00 и на выходе элемента И 34 появится единичный сигнал, который разрешит прохождение сигнала Ь через элементы И 35 и ИЛИ 40 на выход 472 комЯ мутатора 9 и т. д. Описанный процесс будет продолжаться до тех пор, пока в в-ом такте сигнал Ь не пройдет на

И1 выход 47> 4 коммутатора 9. Кроме того, в m-ом такте на вход .42 коммутатора 9 с четвертого выхода генерато- 10 ра 4 тактовых импульсов поступит единичный сигнал. Этот сигнал поступит на первую группу входов блока 39 элементов И и разрешит прохождение равномерно распределенного случайного чис- 15 ла, поступающего на вторую группу вхо-. дов блока 39, через те элементы И блока 39, третий вход которых подключен к инверсному выходу разряда регистра

33, находящегося в нулевом состоянии. 20

Поэтому открыты для прохождения равномерно распределенного случайного числа, поступающего с второй группы выходов генератора 8 на группу входов 45 коммутатора 9, будут только те 25 элементы И блока 39, на третий вход которых подается единичный сигнал с инверсного выхода разряда регистра 33, находящегося в нулевом состоянии.

Группа выходов 47 коммутатора 9 подключена к разрядным входам регист,ра 10 так, что выход 47 соединен с входом второго разряда регистра 10, выход 472 - с входом третьего разря35 да и т. д., выход 47 „4 коммутатора

9 — с входом m-го разряда регистра 10.

Поэтому сигнал Ьр+ 2 с выхода .474 коммутатора 9 поступит во второй разряд регистра 10, сигнал Ьр+q- в третий

40 разряд и т. д., сигнал Ь„„- в (m-1)ый разряд. В оставшиеся 1 младшие разряды регистра 10 (им будут соответствовать разряды регистра 33, которые находятся в нулевом состоянии ) в m-ом такте по сигналу с входа 42 коммутатора 9 поступит равномерно распределенное случайное число с второй группы выходов генератора 8. Таким образом, в m-ом такте в регистре 10

50 будет находиться мантисса 1 Ь ЬЕ+,,...

842

Ь а„„ „...а случайного числа с заданнйм законом распределения, в старшем разряде которой всегда будет записана единица. Здесь а - значения раз9 55 рядов равномерно распределенного случайного числа, снимаемого с второй группы выходов генератора 8., Очевидно, при 1 = О в регистре 10 сформируется

3 18 код 1 Ь Ь ...Ь „Ь, а при 1 =mмантисса случайного числа, находящаяся в регистре 1 О, будет равна 1 а<а а а . При необходимости разрядность

lyl--4 Wl мантиссы может быть увеличена за счет добавления к коду, находящемуся в регистре 10, равномерно распределенного случайного числа, снимаемого с генератора 8.

Рассмотрим работу блока 13, функциональная схема которого приведена на фиг. 4. Назначение блока 13 — формировать коды слагаемых, которые поступают в накапливающий сумматор 14, где они суммируются с содержимым данного сумматора. Входы 52 и 53 блока

13 логических элементов подключены соответственно к первому выходу коммутатора 9 и к седьмому выходу генератора 4 тактовых импульсов. Выше бы ло показано, что единичный сигнал на первом выходе 46 коммутатора 9 появляется только в m-ом такте при условии 1=m, т. е. при условии, что в mразрядном случайном числе с фиксированной запятой во всех m разрядах записаны нули. В свою очередь, на седьмом выходе генератора 4 тактовых импульсов может появиться 1 единичных сигналов, если lcm, и l-1 единичных сигналов при 1=m. Здесь, как и прежде, 1 — количество нулевых сигналов

Ь, появившихся на выходе схемы 6 сравнения с начала формирования очередного случайного числа и до первого, отличного от нуля сигнала Ь р+4.

Группа выходов 55 блока 13 подключена к входам К разрядного сумматора 14, причем выход 55А блока 13 соединен с входом первого (младшего ) разряда сум- матора l4, а выход 55 — с входом Кго (самого старшего) разряда сумматора 14, т. е. по сигналу, снимаемому с выхода 55 „блока 13, к содержимому

I сумматора 14 прибавляется слагаемое, сформированное в блоке 13 логических элементов.

Рассмотрим работу блока 13 при 1 с . (m. В этом случае каждый единичный сигнал, поступивший на вход 53 блока, 13 с седьмого выхода генератора 4 тактовых импульсов, вызывает формирование в блоке 13 К-разрядного кода Л=

=11...110, который является обратным кодом отрицательного числа A=-0...001.

Действительно, в этом случае сигнал

f на входе 52 блока 13 равен нулю и поэтому единичный сигнал с входа 53

19 98009 проходит через элемент ЗАПРЕТ 49 на первый вход элемента ИЛИ-НЕ 51„, на выходе которого образуется нулевой сигнал. Это обьясняется тем, что второй вход элемента ЗАПРЕТ 49„ является запрещающим входом и единичный сигнал через элемент ЗАПРЕТ 49„ проходит только .при условии f=O. При f-=0 на выходе элемента ЗАПРЕТ 49 и на выходе всех элементов И блока 50 будут нуле- 10 вые сигналы, которые вызовут появление на выходе элементов 51 и 51З ИЛИНЕ единичных сигналов. На остальные выходы группы выходов 55 блока 13 проходит единичный сигнал с второго входа 53 блока 13. 8 результате имеем, что нулевой сигнал формируется только .на выходе 55,1 блока 13 (т. е. равен нулю самый младший разряд слагаемого), а на всех остальных выходах р0 блока 13 появится единичный сигнал, т. е. A=11... 110. Как отмечалось выше поступление кода Л/11... 110 на входы сумматора 14 вызывает уменьшение его содержимого на единицу. После поступ- 25 ления 1 единичных сигналов на вход 53 блока 13 в сумматоре 14 будет проведено 1 операций сложения, в результате чего содержимое сумматора умень- шится на Я единиц.

30 Рассмотрим случай 1=я. В этом случае работа блока 13 во всех тактах кроме m-го такта не отличается от ранее рассмотренного. B m-ом такте од35 новременно на входы, 52 и 53 блока 13 поступают единичные сигналы, т. е. в. этом случае. f-=1. Сигнал f--1 с входа

52 блока 13 поступит на первую группу входов блока 50 элементов И и раз- „ решит прохождение сигналов с выходов блока 49 элементов ЗАПРЕТ на входы блока 51 элементов ИЛИ-НЕ. Одновре-, менно единичный сигнал f--1 запретит прохождение сигнала с входа 53 блока

13 через элемент ЗАПРЕТ 49<. На выходе остальных элементов .ЗАПРЕТ блока49 будут Формироваться несовместимые случайные последовательности сигналов, вероятности появления единичного

-(.il Л) 50 сигнала в которых равны 2,. где

Ц порядковый номер элемента ЗАПРЕТ в блоке 49, q= 2 6. Например, на выходе элемента ЗАПРЕТ 49< вероятность появления единичного сигнала в m-ом 1 55 такте равна 2-, на выходе элемента

ЗАПРЕТ 49 - 2 и т. д. Это объясняется тем, что группа входов 54 блока

5 13 подключена,к третьей группе выхо3 20 дов генератора 8 равномерно распределенных случайных чисел, вероятность появления единичного сигнала на каждом выходе которого равна 2- На выходе элемента ЗАПРЕТ 49 единичный сигнал появится в m-ом такте в случае 1=в только при С„=О, где С - значение сигнала на входе 54„.. Поэтому вероятность появления в m-ом такте при 1=m единичного сигнала на выходе элемента ЗАПРЕТ 49 равна вероятности события С =О, которое наступает с вероятностью 2 так как вход 54 блока 13 подключен к разрядному выходу генератора 8 равномерно распределенных случайных чисел. На выходе элемента ЗАПРЕТ 49> единичный сигнал появится только при С =1 и С =,О, где л z; °

С вЂ” значение сигнала на входе 54 . 2

Вероятност,ь события С„С =1 равна 2- в силу отсутствия корреляции между выходными последовательностями генератора 8. Аналогично, единичный сигнал на выходе элемента ЗАПРЕТ 49 появится только при С„ С =1 и С вЂ -О, т. е. с вероятностью Р(С С С, =1 )=2 и т. д.

-3

Выход элемента ЗАПРЕТ 49 соединен с первым входом элемента ИЛИ-НЕ 51 .

Поэтому в m-ом такте при 1=m с вероятностью 2 " на выходах блока 13 будет сформирован код А=ll... 101„ который является обратным кодом отрицательного числа А= -0...010=-2. Выход элемента И 50л соединен с вторыми входами элементов ИЛИ-НЕ 51< и ИЛИ-НЕ 51 . Поэтому в m-ом такте при 1=m с вероятностью 2- на выходе блока 13 будет сформирован код А=ll... 100, который является обратным кодом отрицательного числа A=-0...011=-3 и т. д. Таким образом получили, что в случае 1=m в

m-ом такте содержимое сумматора 14 с вероятностью 2 будет уменьшено на

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

Иф по абсолютной величине меньше . Г . Известное устройство все числа, которые

-VH по абсолютной величине, меньше 2, где

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

Заметим, что нормализованные слу- чайные числа с плавающей запятой мож21 980093

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

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

Использование новых элементов - генератора тактовых импульсов, выход регистров, коммутатора, блока логичес- первого блока элементов И является ких элементов, сумматора, блока эле- 0 вторым выходом генератора, пятый выментов И выгодно отличает предлагае- ход генератора тактовых импульсов подмое устройство от прототипа, так как ключен к первому входу коммутатора, позволяет расширить его функциональ — второй и третий входы которого соединые возможности, повысить точность нены с выходом схемы сравнения и с представления случайных величин H no >5 первым выходом генератора тактовых высить скорость формирования случай- импульсов соответственно, шестой выных чисел с плавающей запятой. ход генератора тактовых импульсов подключен к четвертому входу коммутатоформула изобретения . Ра, к входам третьего регистра памяти, второго и третьего блоков элеменГенеРатоР слУчайных чисел, содеР- тов И к первому вхо к первому входу сумматора и к жащий первый регистр памяти, дешифравходу генератора равномерно распредетор, блок памяти, информационный вход ленных случайных чисел, второй и трекоторого через дешифратор соединен с тий выходы которого соединены с пяпеРвым выхоДом пеРвого РегистРа памЯ- тым входом комм тат тым входом коммутатора и с информацити, генератор тактовых импульсов, схе- онным входом блока онным входом лока инверсии кода сому сравнения, первый и второй блоки ответственно, седьмой выход генератоэлементов И, выход второго блока элера тактовых импульсов подключен к перментов И является первым выходом гене вому управляющему входу блока инверратора генератор равномерно распределенных случайных чисел, первый выход которого соединен с первым входом ра, группа выходов которого подключесхемы сравнения, о т л и ч а ю Ш " и на соответственно к групге входов с я тем, что, с целью повышения его третьего регистра памяти группа выхо1 точности, он содержит второи, третии дов последнего соединена соответсти четвертый регистры памяти, коммута венно,с группой входов второго блока

45 тор, блок инверсии кода, сумматор. элементов И группа входов сумматора сю

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

"Пуск" и "Стоп" генератора, а второй g 185569, кл.0 06 р уу58, )96у

23

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

309356, кл. G 06 F 7/58, 1970.

98О093

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

1 378826, кл. С 06 F 7/58, 1971 (лро тотил).

980093

И2, Тираж 731 Подписное

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

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

Заказ 9361/39

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

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

Редактор Н. Гришанова Техред И.Гергель Корректор M. Демчик