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

 

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

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

Республик

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

СССР йо делам каобретений и аткрытий (72) Автор изобретения

В. М. Тарасов

Казанский ордена Трудового Красного Знамени авиационный институт им. А. Н. Туполева (71) Заявитель (54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ

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

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

Известный генератор отличается высокой сложностью.

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

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

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

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

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

10

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

15 которого подключен к первому выходу генератора тактовых импульсов, первую схему сравнения, генератор равномерно распределенных случайных чисел, блок элементов И, выход которого является выходом генератора, введены второй и третий регистры памяти, вторая и третья схемы сравнения, блок формирования разрядов числа, блок анализа, коммутатор, причем первый и второй входы «Пуск» генератора тактовых импульсов являются первым и вторым входами «Пуск» устройства, а третий его вход соединен с первым выходом блока анализа соответственно, первый выход блока памяти подключен к первому входу первого регистра памяти, второй вход которого соединен с первым выходом блока анализа, 25

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

40 пульсов соединен с пятым входом первого регистра памяти и с вторыми входами второго регистра памяти и блока анализа, 45 второй выход генератора тактовых импульсов подключен к вторым входам схем сравнения и к третьему входу блока анализа, четвертый и пятый входы которого соедирядов числа, третий выход генератора тактовых импульсов подключен к первому входу коммутатора, второй, третий и четвертый входы которого соединены с первым выходом блока анализа и выходами блока формирования разрядов числа соответственно. четвертый выход генератора тактовых импульсов подключен к пятому входу коммутатора, к входу третьего регистра памяти, нены с выходами блока формирования раз- 5о первому входу блока элементов И4к входу генератора равномерно распределенных случайных чисел, выход которого соединен с третьими входами схем сравнения, а группа выходов — с группой входов коммутатора, соответственно, выходы которого подключены к группе входов третьего регистра памяти соответственно, выходы которого соединены с вторым входом блока элементов И.

Блок формирования разрядов числа содержит два элемента И, элемент НЕ и элемент ИЛИ, первый вход первого элемента И является первым входом блока, второй вход которого через элемент НЕ соединен с вторым входом первого элемента И и непосредственно с первым входом второго элемента И, второй вход которого является третьим входом блока, первый выход которого объединен с его вторым входом, выходы элементов И соединены с входами элемента ИЛИ, выход которого является вторым выходом блока.

Кроме того, блок анализа содержит регистр памяти, два дешифратора, два формирователя импульсов, два элемента

ЗАПРЕТ, восемь элементов И и пять элементов ИЛИ, первый и второй входы блока подключены соответственно к двум входам регистра памяти, выходы которого соединены с соответствующими входами первого дешифратора, выходы которого соединены с соответствующими входами первых трех элементов ИЛИ, выход первого элемента

ИЛИ соединен с первыми входами первого и второго элементов И, вторые входы которых подключены к выходам первого и второго элементов ЗАПРЕТ соответственно, первые входы которых подключены к выходам первого и второго формирователей импульсов соответственно, выходы второго и третьего элементов ИЛИ соединены с первыми входами третьего и четвертого элементов И соответственно, вторые входы которых подключены к выходам первого и второго элементов ЗАПРЕТ соответственно, выходы второго, третьего и четвертого элементов И соединены с соответствующими входами четвертого элемента ИЛИ, третий, четвертый и пятый входы блока подключены соответственно к трем входам второго дешифратора, выходы которого соединены с первыми входами пятого, шестого, седьмого и восьмого элементов И соответственно, выходы которых соединены с соответствующими входами пятого элемента ИЛИ, выход которого соединен с вторыми входами элементов ЗАПРЕТ и является первым выходом блока, вторым и третьим выходами которого являются соответственно выходы первого элемента И и четвертого элемента ИЛИ, четвертый и пятый входы блока соединены с входами первого и второго формирователей импульсов соответственно, выходы регистра памяти соединены с вторыми входами

970359

50

55 пятого, шестого, седьмого и восьмого элементов И.

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

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

Выход первого регистра 1 через дешифратор 2 соединен с первым входом блока 3 памяти, первый, второй и третий выходы которого подключены к первым входам регистров и 5 и блока 10 анализа соответственно. Первый, второй и третий входы генератора 4 тактовых импульсов подключены к первому 15 и второму 16 входам генератора случайных чисел и к третьему выходу блока 10 анализа соответственно. Первый выход генератора 4 тактовых импульсов соединен с третьим входом первого регистра 1 и с вторыми входами блока 3 памяти, второго регистра 5 и блока 10 анализа, первый, второй и третий выходы которого подключены к четвертому., пятому и второ. му входам первого регистра 1 соответственно. Первая, вторая и третья группы выходов второго регистра 5 подключены к первой группе входов соответственно первой 6, второй 7 и третьей 8 схем сравнения, вторая группа входов и третий вход которых соединены с первой группой выходов генератора 11 равномерно распределенных случайных чисел и вторым выходом генератора 4 тактовых импульсов соответственно.

Пятый, третий и четвертый входы блока 10 анализа подключены соответственно к второму выходу генератора 4 тактовых импульсов и к выходам блока 9 формирования разрядов числа, входы которого соединены с выходами схем сравнения. Третий выход генератора 4 тактовых импульсов соединен с четвертым входом коммутатора 12, первый, второй и третий входы которого подключены к третьему выходу блока 10 анализа и выходом блока 9 формирования разрядов числа соответственно. Четвертый выход генератора 4 тактовых импульсов подключен к пятому входу коммутатора 12, к второй группе входов третьего регист5

З5 ра 13 и блока 14 элементов И и к входу генератора 11 равномерно распределенных случайных чисел, вторая группа выходов которого соединена с шестой группой входов коммутатора 12. Выходы коммутатора

12 подключены к первой группе входов третьего регистра 13, выходы которого через первую группу входов блока 14 элементов И соединены с выходами 17 генератора случайных чисел.

Генератор 4 тактовых импульсов (фиг. 2) содержит генератор 18 импульсов, триггер

19, элементы И 20 и 21, входы 15, 16 и 22 и группу выходов 23, причем первый и второй входы генератора 18 импульсов соеди.нены с входами 15 и 16 генератора 4 тактовых импульсов, а первый выход генератора 18 импульсов соединен с первым выходом 231 генератора 4 тактовых импульсов и с первым входом элементов И 20 и

21, вторые входы которых подключены со ответственно к первому и второму выхо дам триггера 19, второй выход генерато ра 18 импульсов соединен с вторым выходом 23 генератора 4 тактовых импульсов и с первым и вторым входами триггера 19, третий и четвертый входы которого подключены к третьему 22 и к первому 15 входам генератора 4 тактовых импульсов соответственно, выходы элементов И 20 и 21 соединены соответственно с третьим 23 и четвертым 23 выходами генератора 4 тактовых импульсов.

Блок 9 формирования разрядов числа (фиг. 3) содержит элементы НЕ 24, И 25.

26 и ИЛИ 27, входы 28, 29, 30 и выходы

3I и 32, причем первый 28 и третий 30 входы блока 9 формирования разрядов числа соединены с первым входом элемента

И 25 и с вторым входом элемента И 26 соответственно, а второй вход 29 — к первому выходу 31, к входу элемента НЕ 24 и к первому входу элемента И 26, выходы элементов И 25 и 26 через элемент ИЛИ 27 соединены с вторым выходом 32 блока 9 формирования разрядов числа.

Блок IO анализа (фиг. 4) содержит регистр 33 памяти, дешифратор 34, блок 35 элементов ИЛИ, блок 36 элементов И, элемент ИЛИ 37, импульсные формирователи

38 и 39, элементы ЗАПРЕТ 40 и 41, импульсный дешифратор 42, блок 43 элементов И, элемент ИЛИ 44, входы 45 — 49 и выходы

50 — 52, причем входы регистра 33 соединены с первым 45 и вторым 46 входами блока 10 анализа, а выходы регистра 33 подключены ко входам дешифратора 34 и к первой группе входов блока 43 элементов

И, вторая группа входов которого соединена с выходами импульсного дешифратора 42, а входы импульсного дешифратора

42 подключены к третьему 47, четвертому

48 и пятому 49 входам блока 10 анализа.

При этом третий 47 и четвертый 48 входы

970359

Коммутатор 12 (фиг. 5) содержит регистр 53 сдвига, первый 54, второй 55 и третий 56 блоки элементов И, блок 57 элементов ИЛИ, входы 58 — 62, группу входов

63,и группу выходов 64, причем первый вход 58 коммутатора 12 подключен к первой группе входов третьего блока 56 элементов И, вторая группа входов которого соединена с шестой группой входов 63 коммутатора 12, второй 59 и третий 60 входы

25 зо коммутатора 12 подключены к первым входам соответственно нечетных и четных элементов И блока 55, четвертый вход 61 коммутатора 12 соединен с первым и вторым входами регистра 53 сдвига, третий вход которого подключен к пятому входу 62 коммутатора 12, первая и вторая группы выходов регистра 53 сдвига соединены с первой и второй группами входов блока 54 элементов И соответственно, выходы блока 54 элементов И подключены к вторым входам соответствующих элементов И блока 55, вторые входы двух последних эле40 ментов И блока 55 соединены с предпоследним выходом регистра 53 сдвига, вторая группа выходов регистра 53 сдвига соединена с третьей группой входов блока 56 элементов И, выходы которого подключены к первой группе входов блока 57 элементов ИЛИ, вторая группа входов блока 57 элементов ИЛИ соединена с последними (п-2)-ми выходами блока 55 элементов

И, первые два выхода которого подклю45

50 чены к первым двум выходам 64 и ба группы выходов 64 коммутатора 12, последние (n-2) выхода группы выходов 64 коммутатора 12 соединены с выходами блока 57 элементов ИЛИ.

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

55 блока 10 соединены через импульсные формирователи 38 и 39 с первыми входами

ЗАПРЕТ 40 и 41 соответственно, выходы блока 43 элементов И подключены к входам элемента ИЛИ 44, выход которого соединен с вторыми входами элементов ЗАПРЕТ 40 и 41 и с третьим выходом 52 блока 10 анализа, первая, вторая и третья группы выходов дешифратора 34 подключены к входам первого 35, второго 35> и третьего

35з элементов ИЛИ соответственно, выход 10 первого элемента ИЛИ 35 соединен с первыми входами элементов И 36> и 36>, а выходы элементов ИЛИ 35> и 35з подключены к первым входам элементов И 36> и 364 соответственно, выход элемента

ЗАПРЕТ 40 соединен с вторыми входами элементов И 361 и Збз, а вторые входы элементов И 36 и 36.1 подключены к выходу элемента ЗАПРЕТ 41, вьВод элемента

И 36» соединен с первым выходом 50 блока

10 анализа, второй выход 51 которого че- 20 рез элемент ИЛИ 37 соединен с выходами элементов И 36г, 36> и 36д.

После поступления сигнала «Пуск» по входу 15 происходит запуск генератора 4 тактовых импульсов, который вырабатывает сигналы, управляющие работой предлагаемого устройства.

Будем считать, что перед началом работы предлагаемого генератора случайных чисел в регистре 1 установлен начальный адрес, т. е. адрес ячейки памяти, в которой хранится первое слово. Поэтому в первом такте по сигналу с первого выхода генератора 4 тактовых импульсов происходит считывание первого слова из блока 3 памяти и прием отдельных составных частей этого слова в первый 1 и второй 5 регистры и в блок

10 анализа. Одновременно со считыванием первого слова из блока 3 памяти по сигналу с четвертого выхода генератора 4 тактовых импульсов происходит запуск генератора 11 равномерно распределенных случайных чисел и установка в исходное состояние коммутатора 12 и третьего регистра 13.

В предлагаемом устройстве принято, что каждое слово, хранящееся в блоке 3 памяти, состоит из трех частей: в первой части слова записан адрес ячейки памяти, хранящей слово, которое будет считано из памяти в следующем такте; во второй части слова записаны значения функции распределения F(x) в трех узловых точках, т. е. F(X > ), Г(Х 1) и Г(Хз,); в третьей части слова записан четырехразрядный код Z1, который из памяти поступает в блок 10 анализа. Например, в первом слове во второй части записаны следующие значения функции распределения: F(0,25), F(0,5) и F(0,75). Вторая часть слова из блока 3 памяти поступает во второй регистр 5, первая, вторая и третья группы выходов которого соединены с первой группой входов первой 6, второй 7 и третьей 8 схем сравнения соответственно. Поэтому в первом такте на первую группу входов первой схемы 6 срав нения поступает из регистра 5 значение функ ции F (X) при Х = 0,25, на первые входы второй схемы 7 сравнения — F (0,5) и на первые входы третьей схемы 8 сравнения—

F(0,75). Поскольку на вторую группу входов всех трех схем сравнения поступает число с первой группы выходов генератора 11 равномерно распределенных случайных чисел, то с помощью схем сравнения определяется, в какой из четырех возможных интервалов попадает равномерно распределенное число (фиг. 7).

На втором выходе генератора 4 тактовых импульсов в каждом такте формируются импульсы, которые сдвинуты во времени на половину периода относительно импульсов, снимаемых с первого выхода генератора 4 (фиг. 6). Поэтому в каждом такте по сигналу со второго выхода гене970359 ратора 4 происходит срабатывание всех трех схем сравнения, в результате чего равномерно распределенное случайное число сравнивается со значениями функции распределения, находящимися в регистре 5.

На выходе j-ои схемы сравнения (где j =

=1,3 сигнал S принимает единичное значение только в том случае, если ) > Р(Х11).

Если $ (F(X" ), то Sj = О. Сформирован.,ые таким образом сигналы S> поступают на входы блока 9 формирования разрядов числа.

Например, в течение первого такта в регистре 5 находятся значения F (0,25), F(0,5) и F (0,75) функции распределения, которые сравниваются с равномерно распре деленным числом, и в результате опреде- 15 ляются значения первых двух разрядов Ъ1 и b> формируемого числа Х с заданным законом распределения. Если а F (0,25), то формируемое число Х принадлежит интервалу О (Х < 0,25 и, следовательно, два старших разряда числа Х равны нулю, т. е. Ъ| = bz = О. Если F (0,25) C. 1 (F (0,5), то XE(0,25; 0,5) и, следовательно, b =

= О, а Ь = 1. Если F(0,5) w $ aF(0,75), то XE.(0,5; 0,75) и b> — — 1, а Ь = О. Наконец, если $ > F (0,75), то XE(0,75; 1) и

b< = bz — — 1. Блок 9 формирования разрядов

Зо

35 числа, на входы которого поступают сигналы Sj, т. е. результаты сравнения 1 с

F(X)1 ), как раз и предназначен для формирования сигналов b и Ь2 (разрядов числа Х). Таким образом, в первом и в каждом последующих тактах одновременно формируются два разряда числа Х с заданным законом распределения. Сформированные таким образом разряды числа Х с выходов блока 9 поступают на выходы блока 10 анализа, а через коммутатор 12 — в очередные два разряда выходного регистра 13.

Назначение коммутатора 12 — подключать в каждом такте очередные два разряда регистра 13 к выходам блока 9 формирования разрядов так, чтобы два старших разряда числа Х попадали в два старших разряда регистра 13, следующие более младшие разряды числа Х вЂ” в два следующих по порядку разряда регистра 13 и т. д.

Кроме того, по окончании формирования очередного случайного числа Х через коммутатор 12 по сигналу с третьего выхода блока 10 анализа в младшие разряды регистра 13 записывается равномерно распределенное число с второй группы выходов генератора 11. Назначение блока 10 анализа — определять момент окончания формирования очередного случайного числа с заданным законом распределения, а также формировать младшие разряды адреса слова, которое в следующем такте будет считано из блока 3 памяти.

Таким образом, процесс формирования числа Х с заданным законом распределе40

55 ния в предлагаемом устройстве проходит следующим образом. В каждом такте из блока 3 памяти считываются в регистр 5 очередные три значения F(X>), Г(Х,.), Г(Х51) функции распределения, которые в схемах

6, 7 и 8 сравнения сравниваются с равномерно распределенным числом, снимаемым с первой группы выходов генератора 11.

Блок 9 на основании результатов сравнения формирует очередные два разряда Ь< и Ь числа Х, которые через коммутатор 12 поступают в регистр 13.Описанная процедура получения разрядов числа Х продолжается до тех пор, пока на третьем выходе блока 10 анализа не появится сигнал R = 1, извещающий об окончании формирования очередного случайного числа. Этот сигнал R поступает в регистр 1 и устанавливает в нем начальный адрес. Кроме того, сигнал R поступает на третий вход генератора 4 тактовых импульсов и устанавливает трипер 19 в нулевое состояние (фиг. 2). Поэтому по сигналам с выходов генератора 4 тактовых импульсов начинается цикл формирования следующего случайного числа, а число, сформированное в предыдущем цикле, по сигналу с четвертого выхода генератора 4 из регистра 13 через блок 14 элементов И поступает на выход 17 устройства. Одновременно с этим по заднему фронту сигнала с четвертого выхода генератора 4 коммутатор 12 и регистр 13 устанавливаются в исход ное состояние и происходит запуск генератора 11 равномерно распределенных случайных чисел.

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

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

Входящий в его состав генератор 18 импульсов вырабатывает сдвинутые друг относительно друга на половину периода две серии импульсов, которые проходят на первый 23 и второй 23 выходы генератора 4 соответственно (фиг. 6). Вход 15 генератора 4 тактовых импульсов является пусковым, а по входу 22 поступает сигнал К с третьего выхода блока 10 анализа. Этот сигнал R = 1 переводит триггер 19 в нулевое состояние, в результате чего импульс с первого выхода генератора 18 проходит через элемент И 21 на четвертый выход

234 генератора 4 тактовых импульсов. Выработкой сигнала на четвертом выходе генератора 4 начинается каждый цикл формирования очередного случайного числа.

В свою очередь, каждый цикл состоит из нескольких тактов, а в течение каждого из которых формируются два разряда случайного числа Х. В каждом цикле происходит формирование одного случайного числа с заданным законом распределения. Работа генератора 4 тактовых импульсов пре970359! г кращается при поступлении сигнала по входу 16.

В первом такте каждого цикла по сигналу со второго выхода генератора 18 импульсов триггер 19 возвращается в единичное состояние, так как второй выход генератора 18 соединен как со входом установки триггера 19 в единичное состояние (первым входом триггера 19), так и со входом синхронизации (входами 1 и С синхронного двухступенчатого I K-триггера 19) . Поэтому начиная со второго такта импульсы с первого выхода генератора 18 проходят через элемент И 20 на третий выход 23з генератора 4 тактовых импульсов. Эти импульсы проходят на выход 23з до тех пор, пока по сигналу R = 1, поступающему на вход 22 генератора 4, триггер 19 не перейдет в нулевое состояние. Поступлением сигнала

R = 1 на вход генератора 4 тактовых импульсов и заканчивается очередной цикл формирования случайного числа.

По сигналу с первого выхода генератора

4 тактовых импульсов происходит считывание очередного слова из блока 3 памяти и прием составных частей этого слова в регистры 1 и 5 и блок 10 анализа, по сигналу со второго выхода — срабатывание всех 25 схем сравнения и блока 10 анализа, по сигналу. с третьего выхода генератора 4 тактовых импульсов коммутатор 12 переходит в следующее состояние, по сигналу с четвертого выхода происходит срабатывание генератора 11 равномерно распределенных слу30 чайных чисел, установка в исходное состояние коммутатора 12 и регистра 13 и считывание сформированного в предыдущем цикле случайного числа на выход !7 устройства. 35

Рассмотрим работу блока 9 формирования разрядов числа Х (фиг. 3). На входы блока 9 поступают сигналы 8 (j = 1,3) с выходов соответствующих схем сравнения, а на выходах блока 9 вырабатываются сиг40 налы Ъ, и bz. Рассмотрим работу блока 9 на примере формирования двух старших разрядов числа Х, когда в регистре 5 находятся значения F(0,25), F(0,5) и F(0,75) функции распределения F(X). Поскольку 4 первый выход 31 блока 9 соединен непосредственно со вторым входом 29 блока 9 (т. е. с выходом второй схемы 7 сравнения), то единичный сигнал Ь вЂ” — 1 на выходе 31 появляется только тогда, когда сигнал $ =

= 1. Но сигнал Sz на выходе второй схемы 7 сравнения равен единице при 3 > F(0,5), т. е. в том случае, когда формируемое число Х > 0,5. Следовательно, при попадании числа Х в интервал (05; 1) на выходе 31 блока 9 формируется единичный сигнал

bI — — 1, а при Sz — — О, т. е. попадании числа Х в интервал (О; 0,5), сигнал Ь| равен нулю. Таким образом, если случайное число Х больше 0,5, то в его старший разряд записывается единица, а при Х (0,5 нуль, что и требуется для правильной работы генератора случайных чисел. Если

Sz —— О, т. е. если Х + 0,5, то на выходе элемента HE 24 присутствует единичный сигнал, и сигнал S! с первого входа 28 блока 9 через элементы И 25, ИЛИ 27 проходит на второй выход 32 блока 9. Следовательно, при Sz — — О, т. е. при b! = О, имеем Ь = Si . Поскольку сигнал S i = О при $ CF(0,25) и S! = 1 при (OF(0,25), то сигнал bz = О при Хб(0; 0,25), à b, = 1, если Хб(0,25; 0,5), что и необходимо. Аналогично, если сигнал Sz — — 1, т. е. если

Х > 0,5, то на выход 32 блока 9 через элементы И 26 и ИЛИ 27 проходит сигнал S с третьего входа 30 блока 9 (вход 28 блока 9 отключен нулевым сигналом, поступающим на второй вход элемента И 25 с выхода элемента НЕ 24. Таким образом, при

Sz = 1, т. е. при Ъ, = 1 имеем Ь = S . Поскольку сигнал 8 = О при $ (Г(0,75), то сигнал Ь = О при Хб(0,5; 0,75). Аналогично, сигнал bz — — 1 при Х :-(075; 1), что и требуется для правильной работы генератора случайных чисел. Аналогично блок 9 работает и при получении остальных разрядов числа Х, формируя в каждом такте два очередных разряда числа с заданным . законом распределения.

Ключевое место в предлагаемом генераторе случайных чисел занимает блок 10 анализа (фиг. 4). Этот блок на основании анализа сигналов b, и bz, поступающих на его третий 47 и четвертый 48 входы с выходов блока 9 формирования разрядов, а также в зависимости от значения цифрового сигнала Х!, который поступает по входу

45 в четырехразрядный регистр 33 из блока 3 памяти, формирует на первом 50, втором 51 и третьем 52 своих выходах сигналы а,, а и R соответственно. На второй 46 и пятый 49 входы блока 10 анализа поступают тактовые импульсы с первого и второго выходов генератора 4 соответственно.

В момент времени, задаваемый сигналом с первого выхода генератора 4 тактовых импульсов, происходит прием цифрового сигнала (кода) Z! в регистр 33, а по сигналам со второго выхода генератора 4 срабатывание импульсного дешифратора 42 и всего блока 10 анализа в целом. Код Z! в регистре 33 хранится в течение одного такта, поскольку в следующем такте в регистр 33 поступает новое значение сигнала Z! из блока 3 памяти.

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

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

970359

Введение в схему предлагаемого генера- 40 тора случайных чисел блока 10 анализа позволяет реализовать метод кусочно-линейной аппроксимации заданной функции распределения F(X) при неравномерном шаге hj разбиения области Х. Этот метод об45 ладает тем преимуществом перед известными, что позволяет повысить точность воспроизведения функции F (Х), используя меньший объем блока 3 памяти. Это объясняется тем, что с меньшим шагом h> проходятся не все участки области аргумента Х функции F(X), а только те, где погрешность аппроксимации велика. Например, с шагом h; = 1/16 проходится участок от

Х = 0,25 до Х = 0,5, тогда как на остальных участках шаг h> равен 1/4. Поскольку для хранения каждых трех узловых точек

F(X>.,) требуется одна ячейка памяти, то уменьшение количества узловых точек ведет к сокращению объема запоминающего устройства без ущерба для точностных

33 говорит о том, что замаскированы все четыре интервала. Если интервал замаскирован, то это означает, что при попадании формируемого числа Х в данный интервал его формирование заканчивается.

На фиг. 7 изображена функция распреде5 ления F (Х), которая разбита значениями

0 25; 0 5; 0,75 на четыре интервала. При формировании двух старших разрядов числ" Х в первом такте с помощью трех схем сравнения и блока 9 определяется, какому из четырех интервалов принадлежит число Х с заданным законом распределения. Если

XE(0; 0,25), т. е. если окажется в результате сравнения 1 с F (Х), что (CF (0,25), то число Х принадлежит первому интервалу. Аналогично, если Х E. (О 25;

0,5), т. е. если F (0,25) (f (F (0,5), то

Х принадлежит второму интервалу и т. д.

Блок 10 анализа в зависимости от значения цифрового сигнала Z(определяет, попало ли число Х в замаскированный интервал или нет. Если X попало в замаскированный интервал, то формирование числа Х на этом заканчивается и на третьем выходе 52 блока 10 анализа появляется сигнал R = 1 (сигнал окончания формирования очередного числа Х). Если Х попало в незамас- 25 кированный интервал, то в следующем такте формирование числа будет продолжено, т. е. будут получены следующие два разряда этого числа. На фиг. 7, в качестве примера показано, что первый, третий и четвертый интервалы замаскированы, а второй интер вал незамаскирован. Поэтому при попадании Х во второй интервал во втором такте формирование числа будет продолжено, т. е. получены еще два разряда путем сравнения равномерно распределенного числа со значениями F (5/!б), F (баб) и F (/16) функции распределения, которые будут считаны по сигналу с первого выхода генератора 4 тактовых импульсов из блока 3 памяти в регистр 5. характеристик предлагаемого генератора случайных чисел.

Таким образом, предлагаемое устройство позволяет замаскировать те интервалы, где точность аппроксимации отвечает заданным требованиям, а те участки, где погрешность велика, можно пройти с более мелким шагом h; так, чтобы погрешность аппроксимации не превышала заданного уровня.

Очевидно, в некоторых случаях (особенно в первых тактах каждого цикла), когда погрешность аппроксимации функции F (X) еще велика, ни один из интервалов не будет замаскирован. В этом случае в каждом разряде регистра 33 будет находиться нуль.

В дальнейшем, по мере формирования новых разрядов числа Х, точность аппроксимации функции F(X) будет возрастать и некоторые интервалы могут быть замаскированы с целью сокращения необходимого для работы генератора случайных чисел объема блока

3 памяти. Поскольку в каждом такте в регистр 33 будет из блока 3 памяти поступать новое значение цифрового сигнала Z>, то блок 10 анализа в каждом такте либо будет формировать сигнал R = 1 окончания формирования очередного случайного числа Х, либо будет позволять продолжить получение следующих разрядов числа Х, формируя на первом 50 и втором 51 своих выходах младшие разряды адреса слова, которое в следующем такте будет считано из блока памяти. Наличие во всех разрядах регистра 33 единиц говорит о том, что все интервалы замаксированы и попадание случайного числа Х в любой их этих интервалов ведет к появлению на третьем выходе блока

10 анализа сигнала R = 1.

Рассмотрим работу блока 10 анализа более подробно. Разрядные выходы четырех разрядного регистра 33 соединены с входами дешифратора 34 и с первой группой входов блока 43 элементов И, на вторую группу входов которого поступают сигналы с выходов импульсного дешифратора 42. В момент времени, задаваемый сигналом с второго выхода генератора 4 тактовых импульсов, на одном из выходов импульсного дешифратора 42 появляется единичный сигнал. Учитывая, что первый и второй входы импульсного дешифратора 42 подключены к выходам блока 9 формирования разрядов числа, получим. что единичный сигнал на первом выходе дешифратора 42 появляется при b, = b2 — — О, т. е. при попадании числа Х в первый интервал (в каждом такте при делении очередного интервала на четыре равные части счет новых интервалов идет слева направо в пределах данного интервала) . Аналогично, на втором выходе дешифратора 42 единичный сигнал появляется тогда, когда Ъ| = О, а b2 = 1, т. е. при попадании числа Х, во второй интервал, на третьем выходе — при попадании Х в третий интервал, и на четвертом выходе — при попа970359 дании Х в четвертый интервал. Поэтому, если К-ый интервал замаскирован (т. е. на первый вход К-го элемента И блока 43 подается единичный потенциал с К-го выхода регистра ЗЗ), а число Х попало в К-ый интервал, то на выходе К-го элемента И блока 43 появляется единичный сигнал.

Этот сигнал через элемент ИЛИ 44 проходит на третий выход 52 блока 10 анализа и одновременно запрещает прохождение сигналов через элементы ЗАПРЕТ 40 и 41 на выходы 50 и 51 блока 10. Таким образом, вырабатывается сигнал R = 1, говорящий о том, что формирование очередного случайного числа Х с заданным законом распределения закончено, при этом на первом 50 и втором 51 выходах блока

10 анализа появляются нулевые сигналы, т. е. 3. = 3 = О. Импульсные формирователи 38 и 39, используемые в блоке 10, необходимы для согласования параметров сигналов, поступающих на прямой и запрещающий входы соответствующих элементов ЗАПРЕТ. В качестве формирователей 38 и 39 используются стандартные импульсные формирователи, формирующие импульсы заданной формы и длительности.

Рассмотрим процесс формирования сиг- 25 налов а, и а2 на первом 50 и втором 51 выходах блока 10 анализа соответственно.

Эти сигналы поступают с выходов блока 10 на четвертый и пятый входы регистра 1, поэтому в зависимости от значения сигналов а, и а2 в регистре 1 устанавливается один из четырех возможных адресов. Если а2 — — 1, то в последнем (младшем) разряде регистра 1 будет записана единица. Аналогично, при а, = 1 в предпоследнем разряде регистра 1 будет записа на единица.

Если а, = az = О, то в названных разрядах сохранится прежде записанное в них значение (в регистр 1 поступает адрес из блока 3 памяти при считывании каждого очередного слова). Таким образом, если в процессе формирования рязрядов числа Х не- 4в обходимо обратиться к одному из четырех возможных слов, то исполнительный адрес

А, находяшийся в регистре 1, должен быть равен А1, az, а,, где А1 — код, находяШийся в (— 2) старших разрядов регистра 1; f.— разрядность регистра 1. Поскольку два циф- ровых сигнала а, и а> образуют четыре комбинации (комбинации 00, 01, 10 и 11), то в результате в регистре 1 устанавливается один из четырех возможных адресов А100, или А, 01, или Ai 10, или А111. Например, при формировании второй пары разрядов числа Х, если ни один из четырех интервалов не замаскирован, по адресу А100 должно быть записано слово, содержащее значения F(1/16), F(2/16) и Г(З/1б) функции разделения F(X); по адресу A101 — слово, 55 содержащее F(5/16), F(/1C) и F(jig); по адресу А, 10 —, слово, содержащее F(/16), F(0/L6) и F(11/l6); по адресу А,11 — слово, содержа шее F(/1 ) г(14/16) и F(16/16) . Поэтому при попадании в первом такте числа

Х, например, в третий интервал старшие разряды этого числа составляют b< = 1, а

bz — — 0. Тогда при условии а, = Ъ,, а2 = bg исполнительный адрес А равен А110 и из памяти во втором такте считывается слово содержашее значения F(/1á), F(/1 б) и F(1 /%), т. е. значения функции распределения на третьем интервале. Аналогично, при попадании числа Х в другие интервалы будет формироваться адрес нужного слова.

Таким образом, если ни один из четырех интервалов не замаскирован или замаскирован только один интервал, то необходимо, чтобы на выходы 50 и 51 блока 10 анализа проходили сигналы b> и Ь2 с выходов блока

9 формирования разрядов, т. е. чтобы а, =

= b1, а = bz. В блоке 10 анализа это достигается тем, что выходы дешифратора 34 соответствующие значениям кода Zj, в разрядах которого находится не более одной единицы (т. е. замаскирован не более чем один интервал), объединены с помощью элемента ИЛИ 351 в первую группу. Поэтому на выходе элемента ИЛИ 351 единичный сигнал появляется только тогда, когда цифровой код Z1, находящийся в регистре 33 маски, имеет значения 0000; 0001; 0010;

0100 или 1000. Сформированный таким образом на выходе элемента ИЛИ 351 единичный сигнал разрешает прохождение сигналов Ъ1 и bz через элементы И 36< и 36z на выходе 50 и 51 блока 10 анализа (сигнал с выхода элемента И 362 на выход 51 блока 10 проходит через элемент ИЛИ 37, т. е. в этом случае имеем а, = b>, а = bz, Аналогично формируется исполнительный адрес А и в тех случаях, когда необходимо в процессе работы генератора случайных чисел выбрать из блока 3 памяти одно слово из двух возможных. В этом случае а, = О, а2 равно либо нулю, либо единице в зависимости от значения сигналов b, и bz. При а — — О получается четный исполнительный адрес, а при а2 = 1 нечетный. Необходимость в формировании таких адресов возникает тогда, когда два интервала замаскированы, а два других интервала не замаскированы. Этому случаю соответствуют значения кода Z1, в разрядах которого имеется две единицы и два нуля. Поэтому выходы дешифратора, соответствующие значениям Z1, равным 1010, 1001, 0101, объединены с помощью элемента ИЛИ 35 во вторую группу, а выходы дешифратора, соответствующие значениям

Z1, равным 1100, 0110 и 0011, объединены элементом ИЛИ 35 в третью группу. Таким образом, на выходе либо элемента

ИЛИ 352, либо элемента ИЛИ 35з единичный сигнал появится только тогда, когда в регистре 33 будет находиться цифровой код Z;, содержаший ровно две единицы. В этом случае на выход 51 блока 10 анализа пройдет либо сигнал b, либо сигнал Ь .

970359

18

Сигнал Ь пройдет через элементы И 36, и ИЛИ 37 на выход блока 10 анализа при наличии разрешающего единичного сигнала на выходе элемента ИЛИ 35>. В обоих последних случаях прохождение сигнала на первый выход 50 блока 10 анализа будет запрещено нулевым сигналом с выхода элемента ИЛИ 35!, т. е.

= О. Таким образом, происходит формирование исполнительного адреса А в регистре 1 при наличии двух замаскированных интервалов.

В тех случаях, когда замаскировано три интервала (т. е. в регистре 33 находится код Z1, содержащий один нуль и три единицы), возможно считывание из блока 3 памяти только одного слова и поэтому исполнительный адрес А равен адресу, поступающему из блока 3 памяти в регистр 1.

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

34, соответствующие данному случаю не показаны, так как эти выходы в схеме не используются) и, следовательно, сигналы

Ь, и Ь не могут пройти на выходы блока

10, т. е. а, = а — — О. Поскольку нулевые значения сигналов а, и а не могут изменить значение адреса А, то этот адрес и равен адресу, поступающему в регистр 1 из блока 3 памяти.

В случае, когда замаскированы все четыре интервала, на выходе элемента ИЛИ 44 всегда присутствует единичный сигнал R = 1, который запрещает прохождение сигналов

Ь, и Ь на выходы 50 и 51 блока 10 анализа, т. е. а — — а = О.

Таким образом, блок 10 анализа формирует сигналы а! и а>, которые поступают в младшие разряды регистра 1 и сигнал R об окончании формирования очередного случайного числа.

Рассмотрим работу коммутатора 12 (фиг. 5). Коммутатор содержит регистр 53 сдвига, первая и вторая группы выходов которого подключены к первой и второй группам входов блока 54 элементов И соответственно. В первую группу выходов регистра 53 сдвига входят прямые выходы всех разрядов регистра 53,исключая выход последнего (самого младшего) разряда, а во вторую группу выходов регистра 53 входят инверсные выходы всех разрядов регистра 53, исключая выход первого (старшего) разряда. Исходное состояние регистра 53 устанавливается по сигналу с четвертого выхода генератора 4 тактовых импульсов. Этот сигнал поступает на вход

62 коммутатора 12 и записывает в старший разряд регистра 53 сдвига единицу, а в остальные разряды — нули, т. е. исходное состояние регистра 53 сдвига равно 100...00. Поэтому в первом такте каждого цикла единичный сигнал появля5 ! о

25 зо

55 ется только на выходе элемента И 54>, так как первый и второй входы элемента

И 54!соединены с прямым выходом первого разряда и с инверсным выходом второго разряда регистра 53 соответственно. Единичный сигнал с выхода элемента И 54 разрешает прохождение сигналов Ь, и b „ поступающих на второй 59 и третий 60 входы коммутатора 12 через элементы И

55, и 55 на выходы 64! и 642 соответственно. Поскольку группа выходов 64 коммутатора 12 соединена с разрядными входами регистра 13, то в первом такте два старших разряда числа X поступают в старшие разряды регистра 13. Во втором такте по сигналу с третьего выхода генератора 4 тактовых импульсов, поступающему на четвертый вход 61 коммутатора

12, регистр 53 сдвига переходит в следующее состояние 110...00, так как названный сигнал сдвигает содержимое регистра 53 на один разряд в сторону младших разрядов и одновременно записывает в старший разряд регистра 53 единицу. Поэтому во втором такте единичный сигнал появляется только на выходе элемента И 54z, и, следовательно, сигналы Ь,и Ь через элементы

И 55> и 55 и элементы ИЛИ 57, и 57 проходят на выходы 64> и 64! коммутатора 12 соответственно. Таким образом, во втором такте очередные два разряда числа Х поступают в третий и четвертый разряды регистра 13. Аналогично, в третьем такте регистр 53 сдвига переходит в состояние 1110...00 и разрешает прохождение сигналов Ь, и Ь на пятый 645 и шестой 64в выходы коммутатора 12 и т. д. Описанный процесс продолжается до тех пор, пока на первый вход коммутатора 12 не поступит сигнал R = 1 с третьего выхода блока 10 анализа. Этот сигнал поступает на первую группу входов блока 56 элементов И и разрешает прохождение равномерно распределенного числа, поступающего со второй группы выходов генератора 11 на группу входов 63 коммутатора 12, на те выходы коммутатора 12, которым соответствует нулевое состояние разрядов регистра 53.

Это обьясняется тем, что инверсные выходы регистра 53 подключены к третьей группе входов блока 56 элементов И, и, следовательно, открытыми для прохождения равномерно распределенного числа являются те элементы И блока 56, третьи входы которых подключены к выходам разрядов регистра 53, находящихся в нулевом состоянии. Таким образом, после поступления сигнала К = 1 в старших разрядах регистра

13 находятся разряды числа Х, полученные с помощью блока 9 формирования разрядов, а в младших разрядах — равномерно распределенное число, поступившее со второй группы выходов генератора 11. В первом такте следующего цикла число К через

970359 го

19 блок 14 элементов И б дет подано на выход ! 7 устройства.

Таким образом, за гп тактов предлагаемое устройство формирует 2 m разрядное случайное число Х, а недостающие (п — 2m) разряды числа Х на входы и разрядного регистра 13 подаются через коммутатор 12 со второй группы выходов генератора 11 равномерно распределенных случайных чисел. В прототипе за m тактов формируется m-разрядное случайное число, так как в нем в каждом такте формируется только один разряд числа Х с заданным законом распределения. Следовательно, предлагаемое устройство имеет более высокое быстродействие по сравнению с прототипом, поскольку в предлагаемом генераторе в каж дом такте формируется два разряда числа

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

Использование изобретения позволяет повысить быстродействие устройства.

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

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

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

2. Генератор по и. 1, отличающийся тем, что блок формирования разрядов числа содержит два элемента И, элемент HE и элемент ИЛИ, первый вход первого элемента И является первым входом блока, второй вход которого через элемент НЕ соединен с вторым входом первого элемента И и непосредственно с первым входом второго элемента И, второй вход которого является третьим входом блока, первый выход которого объединен с его вторым входом, выходы элементов И соединены с входами элемента ИЛИ, выход которого является вторым выходом блока.

3. Генератор по п. 1, отличающийся тем, что блок анализа содержит регистр памяти, два дешифратора, два формирователя импульсов, два элемента ЗАПРЕТ, восемь элементов И и пять элементов ИЛИ, первый и второй входы блока подключены соответственно к двум входам регистра памяти, выходы которого соединены с соот970359

22 ветствующими входами первого дешифратора, выходы которого соединены с соответствующими входами первых трех элементов ИЛИ, выход первого элемента ИЛИ соединен с первыми входами первого и второго элементов И, вторые входы которых подключены к выходам первого и второго элементов ЗАПРЕТ соответственно, первые входы которых подключены к выходам первои второго формирователей импульсов соответственно, выходы второго и третьего

1О элементов ИЛИ соединены с первыми входами третьего и четвертого элементов И соответственно, вторые входы которых подключены к выходам первого и второго элементов ЗАПРЕТ соответственно, выходы второго, третьего и четвертого элементов И 15 соединены с соответствующими входами четвертого элемента ИЛИ, третий, четвертый и пятый входы блока подключены соответственно к трем входам второго дешифратора, выходы которого соединены с первыми входами пятого, шестого, седьмого и восьмого элементов И соответственно, выходы которых соединены с соответствующими входами пятого элемента ИЛИ, выход которого соединен с вторыми входами элементов

ЗАПРЕТ и является первым выходом блока, вторым и третьим выходами которого являются соответственно выходы первого элемента И и четвертого элемента ИЛИ, четвертый и пятый входы блока соединены с входами первого и второго формирователей импульсов соответственно, выходы регистра памяти соединенис вторыми входами пятого, шестого, седьмого и восьмого элементов И.

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

l. Авторское свидетельство СССР № 213424, кл. G 06 F 7/58, 1966.

2. Авторское свидетельство СССР № 185569, кл. G 06 F 7/58, 1964.

3. Авторское свидетельство СССР № 378826, кл.G 06 F 7/58, 1971 (прототип) .

970359

22 гз

2 г

23>

Фиг. б

F(/ г(г/

/(г/

F(%

Ц фгб б/гб Ч)1б г/ г

Фиг. 7

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

Редактор И.Михеева Техред И. Верес Корректор В. Бутяга

Заказ 7411/59 Тираж 731 Подписное

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

113035, Москва, )К вЂ” 35, Раушская наб., д. 4/5

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