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

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

1

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

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

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

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

Однако указанный генератор имеет низкое быстродействие, так как в каждом

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

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

20 входов которой подключены к выхода.м схемы сравнения и генератора тактовых импульсов соответственно, выходы регистра через вторую группу элементов И соединены с выхода.ми устройства, последний выход генератора тактовых импульсов подключен ко второй группе входов второй группы элементов И 3. Известный генератор также имеет низкое быстродействие, поскольку т-разрядное случайное число с заданным законом распределения формируется за m тактов. Целью изобретения является повышение быстродействия генератора случайных чисел за счет формирования в одном такте нескольких разрядов случайного числа, Для достижения поставленной цели в генератор случайных чисел, содержащий генератор тактовых импульсов, блок памяти, дешифратор, первый регистр памяти, выход которого через дешифратор соединен с первым входом блока памяти, второй вход которого подключен к первому выходу генератора тактовых импульсов, первую схему сравнения, генератор равномерно распределенных случайных чисел, блок элементов И, выход которого является выходом генератора, введены второй и третий регистры памяти, вторая и третья схемы сравнения, блок формирования разрядов числа, блок анализа, коммутатор, причем первый и второй входы «Пуск генератора тактовых импульсов являются первым и вторым входами «Пуск устройства, а третий его вхой соединен с первым выходом блока анализа соответственно, первый выход блока памяти подключен к первому входу первого регистра памяти, второй вход которого соединен с первым выходом блока анализа, второй выход блока памяти подключен к первому входу второго регистра памяти, первый, второй и третий выходы которого соединены с первыми входами первой, второй и третьей схем сравнения соответственно, а выходы схем сравнения подключены к соответствующим входам блока формирования разрядов числа, третий выход блока памяти соединен с первым входом блока анализа, второй и третий выходы которого подключены к третьему и четвертому входам первого регистра памяти соответственно, первый выход генератора тактовых импульсов соединен с пятым входом первого регистра памяти и с вторыми входами второго регистра памяти и блока анализа, второй выход генератора тактовых импульсов подключен к вторым входам схем сравнения и к третьему входу блока анализа, четвертый и пятый входы которого соединены с выходами блока формирования разрядов числа, третий выход генератора тактовых импульсов подключен к первому входу коммутатора, второй, третий и четвертый входы которого соединены с первым выходом блока анализа и выходами блока формирования разрядов числа соответственно, четвертый выход генератора тактовых импульсов подключен к пятому входу коммутатора, к входу третьего регистра памяти. первому входу блока элементов Иик входу генератора равномерно распределенных случайных чисел, выход которого соединен с третьими входами схем сравнения, а группа выходов - с группой входов коммутатора, соответственно, выходы которого подключены к группе входов третьего регистра памяти соответственно, выходы которого соединены с вторым входом блока элементов И. Блок формирования разрядов числа содержит два элемента И, элемент НЕ и элемент ИЛИ, первый вход первого элемента И является первым входом блока, второй вход которого через элемент НЕ соединен с вторым входом первого элемента И и непосредственно с первым входом второго элемента И, второй вход которого является третьим входом блока, первый выход которого объединен с его вторым входом, выходы элементов И соединены с входами элемента ИЛИ, выход которого является вторым выходом блока. Кроме того, блок анализа содержит регистр памяти, два дешифратора, два формирователя импульсов, два элемента ЗАПРЕТ, восемь элементов И и пять элементов ИЛИ, первый и второй входы блока подключены соответственно к двум входам регистра памяти, выходы которого соединены с соответствующими входами первого дешифратора, выходы которого соединены с соответствующими входами первых трех элементов ИЛИ, выход первого элемента ИЛИ соединен с первыми входами первого и второго элементов И, вторые входы которых подключены к выходам первого и второго элементов ЗАПРЕТ соответственно, первые входы которых подключены к выходам первого и второго формирователей импульсов соответственно, выходы второго и третьего элементов ИЛИ соединены с первыми входами третьего и четвертого элементов И соответственно, вторые входы которых подключены к выходам первого и второго элементов ЗАПРЕТ соответственно, выходы второго, третьего и четвертого элементов И соединены с соответствующими входами четвертого элемента ИЛИ, третий, четвертый и пятый входы блока подключены соответственно к трем входам второго дешифратора, выходы которого соединены с первыми входами пятого, шестого, седьмого и восьмого элементов И соответственно, выходы которых соединены с соответствующими входами пятого элемента ИЛИ, выход которого соединен с вторыми входами элементов ЗАПРЕТ и является первым выходом блока, вторым и третьим выходами которого являются соответственно выходы первого элемента И и четвертого элемента ИЛИ, четвертый и пятый входы блока соединены с входами первого и второго формирователей импульсов соответственно, выходы регистра памяти соединены с вторыми входами

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

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

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

Выход первого регистра 1 через дешифратор 2 соединен с первым входом блока 3 памяти, первый, второй и третий выходы которого подключены к первым входам регистров I и 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, к второй группе входов третьего регистра 13 и блока 14 элементов И и к входу генератора 11 равномерно распределенных случайных чисел, вторая группа выходов которого соединена с шестой группой входов коммутатора 12. Выходы коммутатора 12 подключены к первой группе входов третьего регистра 13, выходы которого через первую группу входов блока 14 элементов И соединены с выходами 17 генератора случайных чисел.

Генератор 4 тактовых импульсов (фиг. 2) содержит генератор 18 импульсов, триггер 19, элементы И 20 и 21, входы 15, 16 и 22 и группу выходов 23, причем первый и второй входы генератора 18 импульсов соединены с входами 15 и 16 генератора 4 тактовых импульсов, а первый выход генератора 18 импульсов соединен с первым выходом 23i генератора 4 тактовых импульсов и с первым входом элементов И 20 и 21, вторые входы которых подключены со ответственно к первому и второму выхо дам триггера 19, второй выход генерато ра 18 импульсов соединен с вторым выходом 23i генератора 4 тактовых импульсов и с первым и вторы.м входами триггера 19, третий и четвертый входы которого подключены к третьему 22 и к первому 15 входам генератора 4 тактовых импульсов соответственно, выходы элементов И 20 и 21 соединены соответственно с третьим 23з и четвертым 23j выхода.ми генератора 4 тактовых импульсов.

Блок 9 формирования разрядов числа (фиг. 3) содержит элементы НЕ 24, И 25. 26 и ИЛИ 27, входы 28, 29, 30 и выходы 31 и 32, причем первый 28 и третий 30 входы блока 9 формирования разрядов числа соединены с первым входом элемента И 25 и с вторым входом элемента И 26 соответственно, а второй вход 29 - к первому выходу 31, к входу элемента НЕ 24 и к первому входу элемента И 26, выходы элементов И 25 и 26 через элемент ИЛИ 27 соединены с вторым выходом 32 блока 9 формирования разрядов числа.

Блок 10 анализа (фиг. 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 входы блока 10 соединены через импульсные формирователи 38 и 39 с первыми входами ЗАПРЕТ 40 и 41 соответственно, выходы блока 43 элементов И подключены к входам элемента ИЛИ 44, выход которого соединен с вторыми входами элементов ЗАПРЕТ 40 и 4 и с третьим выходом 52 блока 10 анализа, первая, вторая и третья группы выходов дешифратора 34 подключены к входам первого 35i, второго 352 и третьего 35J элементов ИЛИ соответственно, выход первого элемента ИЛИ 35 соединен с первыми входами элементов И 36i и 36, а выходы элементов ИЛИ 352 г подключены к, первым входам элементов И 36 и 36 соответственно, выход элемента ЗАПРЕТ 40 соединен с вторыми входами элементов И 36j и 36, а вторые входы элементов И Збг и 36 подключены к выходу элемента ЗАПРЕТ 41, вьЛод элемента И 36 соединен с первым выходом 50 блока 10 анализа, второй выход 51 которого через элементИЛИ 37 соединен с выходами элементов И 36, Збз и Збд. Коммутатор 12 (фиг. 5) содержит регистр 53 сдвига, первый 54, второй 55 и третий 56 блоки элементов И, блок 57 элементов ИЛИ, входы 58-62, группу входов 63 ,и группу выходов 64, причем первый вход 58 коммутатора 12 подключен к первой группе входов третьего блока 56 элементов И, вторая группа входов которого соединена с шестой группой входов 63 коммутатора 12, второй 59 и третий 60 входы коммутатора 12 подключены к первым входам соответственно нечетных и четных элементов И блока 55, четвертый вход 61 коммутатора 12 соединен с первым и вторым входами регистра 53 сдвига, третий вход которого подключен к пятому входу 62 коммутатора 12, первая и вторая группы выходов регистра 53 сдвига соединены с первой и второй группами входов блока 54 элементов И соответственно, выходы блока 54 элементов И подключены к вторым входам соответствующих элементов И блока 55, вторые входы двух последних элементов И блока 55 соединены с предпоследним выходом регистра 53 сдвига, вторая группа выходов регистра 53 сдвига соединена с третьей группой входов блока 56 элементов И, выходы которого подключены к первой группе входов блока 57 элементов ИЛИ, вторая группа входов блока 57 элементов ИЛИ соединена с последними (п-2)-ми выходами блока 55 элементов И, первые два выхода которого подключены к первым двум выходам 64i и 642 группы выходов 64 коммутатора 12, последние (п-2) выхода группы выходов 64 коммутатора 12 соединены с выходами блока 57 элементов ИЛИ. Предлагаемый генератор случайных чисел работает следуюш,им образом. После поступления сигнала «Пуск по входу 15 происходит запуск генератора 4 тактовых импульсов, который вырабатывает сигналы, управляющие работой предлагаемого устройства. Будем считать, что перед началом работы предлагаемого генератора случайных чисел в регистре 1 установлен начальный адрес, т. е. адрес ячейки памяти, в которой хранится первое слово. Поэтому в первом такте по сигналу с первого выхода генератора 4 тактовых импульсов происходит считывание первого слова из блока 3 памяти и прием отдельных составных частей этого слова в первый 1 и второй 5 регистры и в блок 10 анализа. Одновременно со считыванием первого слова из блока 3 памяти по сигналу с четвертого выхода генератора 4 тактовых импульсов происходит запуск генератора 11 равномерно распределенных случайных чисел и установка в исходное состояние коммутатора 12 и третьего регистра 13. В предлагаемом устройстве принято, что каждое слово, хранящееся в блоке 3 памяти, состоит из трех частей: в первой части слова записан адрес ячейки памяти, хранящей слово, которое будет считано из памяти в следующем такте; во второй части слова записаны значения функции распределения F(x) в трех узловых точках, т. е. Р(Хц ), F(X2i) F(3i) в третьей части слова записан четырехразрядный код Zj, который из памяти поступает в блок 10 анализа. Например, в первом слове во второй части записаны следующие значения функции распределения: F(0,25), F(0,5) и F(0,75). Вторая часть слова из блока 3 памяти поступает во второй регистр 5, первая, вторая и третья группы выходов которого соединены с первой группой входов первой 6, второй 7 и третьей 8 схем сравнения соответственно. Поэтому в первом такте на первую группу входов первой схемы 6 срав нения поступает из регистра 5 значение функ ции F(X) при X 0,25, на первые входы второй схемы 7 сравнения - F(0,5) и на первые входы третьей схемы 8 сравнения - F(0,75). Поскольку на вторую группу входов всех трех схем сравнения поступает число с первой группы выходов генератора 11 равномерно распределенных случайных чисел, то с помощью схем сравнения определяется, в какой из четырех возможных интервалов попадает равномерно распределенное число (фиг. 7). На втором выходе генератора 4 тактовых импульсов в каждом такте формируются импульсы, которые сдвинуты во времени на половину периода относительно импульсов, снимаемых с первого выхода генератора 4 (фиг. 6). Поэтому в каждом такте по сигналу со второго выхода генератора 4 происходит срабатывание всех трех схем сравнения, в результате чего равномерно распределенное случайное число сравнивается со значениями функции распределения, находящимися в регистре 5. На выходе j-ой схемы сравнения (где j 1 сигнал S принимает единичное значение только в том случае, если F(Xji). Если F(Xji), то Sj 0. Сформирован..oie таким образом сигналы Sj поступают на входы блока 9 формирования разрядов числа. Например, в течение первого такта в регистре 5 находятся значения F(0,25), F{0,5) и F(0,75) функции распределения, которые сравниваются с равномерно распределенным числом , и в результате определяются значения первых двух разрядов Ь, и 2 формируемого числа X с заданным законом распределения. Если F(0,25), то формируемое число X принадлежит интервалу О $ X 0,25 и, следовательно, два старших разряда числа X равны нулю, т. е. bi Ь2 0. Если F(0,25) F(0,5), то Х€.(0,25; 0,5) и, следовательно, Ь; 0, а . Если F(0,5) F(0,75), то Хв(0,5; 0,75) и Ь, 1, а Ь 0. Наконец, если F(0,75), то Х6(0,75; 1) и bi 1. Блок 9 формирования разрядов числа, на входы которого поступают сигналы Sj, т. е. результаты сравнения с F(Xji), как раз и предназначен для формирования сигналов bj и Ь2 (разрядов числа X). Таким образом, в первом и в каждом последующих тактах одновременно формируются два разряда числа X с заданным законом распределения. Сформированные таким образом разряды числа X с выходов блока 9 поступают на выходы блока 10 анализа, а через коммутатор 12 - в очередные два разряда выходного регистра 13. Назначение коммутатора 12 - подключать в каждом такте очередные два разряда регистра 13 к выходам блока 9 формирования разрядов так, чтобы два старших разряда числа X попадали в два старших разряда регистра 13, следующие более младшие разряды числа X - в два следующих по порядку разряда регистра 13 и т. д. Кроме того, по окончании формирования очередного случайного числа X через коммутатор 12 по сигналу с третьего выхода блока 10 анализа в младшие разряды регистра 13 записывается равномерно распределенное число с второй группы выходов генератора 11. Назначение блока 10 анализа - определять момент окончания формирования очередного случайного числа с заданным законом распределения, а также формировать младшие разряды адреса слова, которое в следующем такте будет считано из блока 3 памяти. Таким образом, процесс формирования числа X с заданным законом распределения в предлагаемом устройстве проходит следующим образом. В каждом такте из блока 3 памяти считываются в регистр 5 очередные три значения F(Xj), F(X2j), F(X3i) функции распределения, которые в схемах 6, 7 и 8 сравнения сравниваются с равномерн но распределенным числом Ё, снимаемым с первой группы выходов генератора 11. Блок 9 на основании результатов сравнения формирует очередные два разряда U и bg. числа X, которые через коммутатор Г2 поступают в регистр 13. Описанная процедура получения разрядов числа X продолжается до тех пор, пока на третьем выходе блока 10 анализа не появится сигнал , извещающий об окончании формирования очередного случайного числа. Этот сигнал R поступает в регистр 1 и устанавливает в нем начальный адрес. Кроме того, сигнал R поступает на третий вход генератора 4 тактовых импульсов и устанавливает триггер 19 в нулевое состояние (фиг. 2). Поэтому по сигналам с выходов генератора 4 тактовых импульсов начинается цикл формирования следующего случайного числа, а число, сформированное в предыдущем цикле, по сигналу с четвертого выхода генератора 4 из регистра 13 через блок 14 элементов И поступает на выход 17 устройства. Одновременно с этим по заднему фронту сигнала с четвертого выхода генератора 4 ко.ммутатор 12 и регистр 13 устанавливаются в ис.ход ное состояние и происходит запуск генератора 11 равномерно распределенных случай.ных чисел. Рассмотрим более подробно работу отдельных блоков предлагаемого устройства. Генератор 4 тактовых импульсов (фиг. 2) формирует сигналы, управляющие работой предлагаемого генератора случайных чисел. Входящий в его состав генератор 18 импульсов вырабатывает сдвинутые друг относительно друга на половину перио.аа две серии импульсов, которые проходят на первый 231 и второй 232 выходы генератора 4 соответственно (фиг. 6). Вход 15 генератора 4 тактовых импульсов является пусковым, а по входу 22 поступает сигнал R с третьего выхода блока 10 анализа. Этот сигнал R 1 переводит триггер 19 в нулевое состояние, в результате чего импульс с первого выхода генератора 18 проходит через элемент И 21 на четвертый выход 234 генератора 4 тактовых импульсов. Выработкой сигнала на четвертом выходе генератора 4 начинается каждый цикл формирования очередного случайного числа. В свою очередь, каждый цикл состоит из нескольких тактов, а в течение каждого из которых формируются два разряда случайного числа X. В каждом цикле происходит формирование одного случайного числа с заданным законом распределения. Работа генератора 4 тактовых импульсов прекращается при поступлении сигнала по входу 16. В первом такте каждого цикла по сигналу со второго выхода генератора 18 импульсов триггер 19 возвращается в единичное состояние, так как второй выход генератора 18 соединен как со входом установки триггера 19 в единичное состояние (первым входом триггера 19), так и со входом синхронизации (входами I и С синхронного двухступенчатого 1К-триггера 19). Поэтому начиная со второго такта импульсы с первого выхода генератора 18 проходят через элемент И 20 на третий выход 23 генератора 4 тактовых импульсов. Эти импульсы проходят на выход 23 до тех пор, пока по сигналу R 1, поступающему на вход 22 генератора 4, триггер 19 не перейдет в нулевое состояние. Поступлением сигнала R 1 на вход генератора 4 тактовых импульсов и заканчивается очередной цикл формирования случайного числа. По сигналу с первого выхода генератора 4 тактовых импульсов происходит считывание очередного слова из блока 3 памяти и прием составных частей этого слова в регистры 1 и 5 и блок 10 анализа, по сигналу со второго выхода - срабатывание всех схем сравнения и блока 10 анализа, по сигналу с третьего выхода генератора 4 тактовых импульсов коммутатор 12 переходит в следующее состояние, по сигналу с четвертого выхода происходит срабатывание гене „ ..,„„„... ,„. ратора 11 равномерно распределенных случайных чисел, установка в исходное состояние коммутатора 12 и регистра 13 и считывание сформированного в предыдущем цикле случайного числа на выход 17 устройства. Рассмотрим работу блока 9 формирования разрядов числа X (фиг. 3) На входы блок) 9 поступают сигналы Sj (J - 1,3) с выходов соответствующих схем сравнения, а на выходах блока 9 вырабатываются сигналы bi и . Рассмотрим работу блока 9 на примере формирования двух старщих разрядов числа X, когда в регистре 5 находятся значения Р(0,25), Р(0,5) и F(0,75) J-r/vN г-г iri Jr.rrJl .я±-ТГ первый выход 31 блока 9 соединен непосредственно со вторым входом 29 блока 9 (т. е. с выходом второй схемы 7 сравнения), то единичный сигнал Ь 1 на выходе 31 появляется только тогда, когда сигнал S2 ,,си .шшли luiA.,, шдс. си.п... 02 1. Но сигнал S2 на выходе второй схемы 7 сравнения равен единице при F(0,5), т. е. в том случае, когда формируемое число ,5. Следовательно, при попадании числа X в интервал (0,5; 1) на выходе 31 блока 9 формируется единичный сигнал bi 1, а при S2 О, т. е. попадании числа X в интервал (0; 0,5), сигнал bj равен нулю. Таким образом, если случайное число X больще 0,5, то в его старщий разряд записывается единица, а при X 0,5 - нуль, что и требуется для правильной работы генератора случайных чисел. Если $2 О, т. е. если X 0,5, то на выходе элемента НЕ 24 присутствует единичный сигнал, и сигнал S) с первого входа 28 блока 9 через элементы И 25, ИЛИ 27 проходит на второй выход 32 блока 9. Следовательно, при Sz О, т. е. при Ь| О, имеем Ьг Si. Поскольку сигнал Si О при F(0,25) и S| 1 при (0,25), то сигнал Ьз О при Хв(0; 0,25), а DJ 1, если Х6(0,25; 0,5), что и необходимо. Аналогично, если сигнал S 1, т. е. если X i 0,5, то на выход 32 блока 9 через элементы И 26 и ИЛИ 27 проходит сигнал Sj с третьего входа 30 блока 9 (вход 28 блока 9 отключен нулевым сигналом, поступающим на второй вход элемента И 25 с выхода элемента НЕ 24. Таким образом, при 1, т. е. при bj 1 имеем Ъз Sg. Поскольку сигнал S О при F(0,75), то сигнал Ь2 О при Х€(0,5; 0,75). Аналогично, сигнал Ь 1 при Х6(0,75; 1), что и требуется для правильной работы генератора случайных чисел. Аналогично блок 9 работает и при получении остальных разрядов числа X, формируя в каждом такте два очередных разряда числа с заданным законом распределения. Ключевое место в предлагаемом генераторе случайных чисел занимает блок 10 анализа (фиг. 4). Этот блок на основании анализа сигналов bi и Ьг, поступающих на его третий 47 и четвертый 48 входы с выходов блока 9 формирования разрядов, а также в зависимости от значения цифрового сигнала Zj, который поступает по входу 45 в четырехразрядный регистр 33 из блока 3 памяти, формирует на первом 50, втоРом 51 и третьем 52 своих выходах сигналь, ь а и R соответственно На второй 46 « «™« 9 входы блока 10 анализа посту тактовые импульсы с первого и втоР«™ выходов генератора 4 соответственно. В момент времени, задаваемый сигналом с К AA/ lAfl itIT Dr Ci ilTrjtnnn-nf Cknriitl Гч11г 1глтт/- « - j- первого выхода генератора 4 тактовых импульсов, происходит прием цифрового сигнала (кода) Zi в регистр 33, а по сигналам со второго выхода генератора 4 - срабатывание импульсного дещифр ора 42 и всего блока 10 анализа в целом. Код Zj в регистре 33 хранится в течение одного такта, поскольку в следующем такте в регистр 33 поступает новое значение сигна2i из блока 3 памяти. i Четырехразрядный регистр 33 выполняет функции маски, т. е. наличие единицы в К-ом разряде регистра 33 говорит о том, что К-ый интервал замаскирован. Например, если в первом разряде регистра 33 находится единица, а в остальных трех разрядах регистра 33 записаны нули, то это означает, что замаскирован первый интервал. Наличие единиц во всех четырех разрядах регистра

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

На фиг. 7 изображена функция распределения F(X), которая разбита значениями 0,25; 0,5; 0,75 на четыре интервала. При формировании двух старших разрядов числ- X в первом такте с помощью трех схем сравнения и блока 9 определяется, какому из четырех интервалов принадлежит число X с заданным законом распределения. Если Х€(0; 0,25), т. е. если окажется в результате сравнения с F(X), что F(0,25), то число X принадлежит первому интервалу. Аналогично, если X 6 (0250,5), т. е. если F(0,25) (0,5), то X принадлежит второму интервалу и т. д. Блок 10 анализа в зависимости от значения цифрового сигнала Z определяет, попало ли число X в замаскированный интервал или нет. Если X попало в замаскированный интервал, то формирование числа X на этом заканчивается и на третьем выходе 52 блока 10 анализа появляется сигнал R 1 (сигнал окончания формирования очередного числа X). Если X попало в везамаскированный интервал, то в следующем такте формирование числа будет продолжено, т. е. будут получены следующие два разряда этого числа. На фиг. 7, в качестве примера показано, что первый, третий и четвертый интервалы замаскированы, а второй интер вал незамаскирован. Поэтому при попадании X во второй интервал во втором такте формирование числа будет продолжено, т. е. получены еще два разряда путем сравнения равномерно распределенного числа со значениями F(5/i6), F(6/j6) и FC/ie) функции распределения, которые будут считаны по сигналу с первого выхода генератора 4 тактовых импульсов из блока 3 памяти в регистр 5.

Введение в схему предлагаемого генератора случайных чисел блока 10 анализа позволяет реализовать метод кусочно-линейной аппроксимации заданной функции распределения F(X) при неравномерном щаге hj разбиения области X. Этот метод обладает тем преимуществом перед известными, что позволяет повысить точность воспроизведения функции F(X), используя меньщий объем блока 3 памяти. Это объясняется тем, что с меньщим щагом hj проходятся не все участки области аргумента X функции F(X), а только те, где погрешность аппроксимации велика. Например, с щагом h 1/16 проходится участок от X 0,25 до X 0,5, тогда как на остальных участках щаг hj равен 1/4. Поскольку для хранения каждых трех узловых точек F(Xji) требуется одна ячейка памяти, то уменьщение количества узловых точек ведет к сокращению объема запоминающего устройства без ущерба для точностных

характеристик предлагаемого генератора случайных чисел.

Таким образом, предлагаемое устройство позволяет замаскировать те интервалы, где точность аппроксимации отвечает заданным требованиям, а те участки, где погрешность велика, можно пройти с более мелким шагом hj так, чтобы погрешность аппроксимации не превыщала заданного уровня. Очевидно, в некоторых случаях (особенно в первых тактах каждого цикла), когда погрещность аппроксимации функции F(X) еще велика, ни один из интервалов не будет замаскирован. В этом случае в каждом разряде регистра 33 будет находиться нуль. В дальнейщем, по мере формирования новых разрядов числа X, точность аппроксимации функции F(X) будет возрастать и некоторые интервалы могут быть замаскированы с целью сокращения необходимого для работы генератора случайных чисел объема блока 3 памяти. Поскольку в каждом такте в регистр 33 будет из блока 3 памяти поступать новое значение цифрового сигнала Zj, то блок 10 анализа в каждом такте либо будет формировать сигнал R 1 окончания формирования очередного случайного числа X, либо будет позволять продолжить получение следующих разрядов числа X, формируя на первом 50 и втором 51 своих выходах младшие разряды адреса слова, которое в следующем такте будет считано из блока памяти. Наличие во всех разрядах регистра 33 единиц говорит о том, что все интервалы замаксированы и попадание случайного числа X в любой их этих интервалов ведет к появлению на третьем выходе блока 10 анализа сигнала R 1.

Рассмотрим работу блока 10 анализа более подробно. Разрядные выходы четырех разрядного регистра 33 соединены с входами дешифратора 34 и с первой группой входов блока 43 элементов И, на вторую группу входов которого поступают сигналы с выходов импульсного дешифратора 42. В момент времени, задаваемый сигналом с второго выхода генератора 4 тактовых импульсов, на одном из выходов импульсного дешифратора 42 появляется единичный сигнал. Учитывая, что первый и второй входы импульсного дешифратора 42 подключены к выходам блока 9 формирования разрядов числа, получим, что единичный сигнал на первом выходе дещифратора 42 появляется при Ь) 2 О, т. е. при попадании числа X в первый интервал (в каждом такте при делении очередного интервала на четыре равные части счет новых интервалов идет слева направо в пределах данного интервала). Аналогично, на втором выходе дещифратора 42 единичный сигнал появляется тогда, когда bi. О, а Ь 1, т. е. при попадании числа X, во второй интервал, на третьем выходе - при попадании X в третий интервал, и на четвертом выходе - при попаДании X в четвертый интервал. Поэтому, если К-ый интервал замаскирован (т. е. на первый вход К-го элемента И блока 43 подается единичный потенциал с К-го выхода регистра 33), а число X попало в К-ый интервал, то на выходе К-го элемента И блока 43 появляется единичный сигнал. Этот сигнал через элемент ИЛИ 44 проходит на третий выход 52 блока 10 анализа и одновременно запрещает прохождение сигналов через элементы ЗАПРЕТ 40 и 41 на выходы 50 и 51 блока 10. Таким образом, вырабатывается сигнал , говорящий о том, что формирование очередного случайного числа X с заданным законом распределения закончено, при этом rVVyn W 1V1IJCH t 1 l V /J Vi/lV- iiri/ltJd.,ill-/ri /l.4yivt на первом 50 и втором 51 выходах блока 10 анализа появляются нулевые сигналы, т. е. а. 3. 0. Импульсные формирователи 38 и 39, используемые в блоке 10, необходимы для согласования параметров сигналов, поступающих на прямой и запрещающий входы соответствующих элементов ЗАПРЕТ. В качестве формирователей 38 и 39 используются стандартные импульсные формирователи, формирующие импульсы заданной формы и длительности. Рассмотрим процесс формирования сигналов а; и а2 на первом 50 и втором 51 выходах блока 10 анализа соответственно. Эти сигналы поступают с выходов блока 10 на четвертый и пятый входы регистра 1, поэтому в зависимости от значения сигналов аГи а, в регистре 1 устанавливается один из четырех возможных адресов. Если а2 1, то в последнем (младщем) разряде регистра 1 будет записана единица. Аналогично, при а 1 в предпоследнем разряде регистра 1 будет записана единица. Если а; а2 О, то в названных разрядах сохранится прежде записанное в них значение (в регистр 1 поступает адрес из блока 3 памяти при считывании каждого очередного слова). Таким образом, если в процессе формирования рязрядов числа X необходимо обратиться к одному из четырех воз.можных слов, то исполнительный адрес А, находящийся в регистре 1, должен быть равен AI, а, а, где А) - код, находящийся в (Р-2) старших разрядов регистра 1; 1 - разрядность регистра 1. Поскольку два цифровых сигнала а, и а образуют четыре комбинации (комбинации 00, 01, 10 и 11), то в результате в регистре 1 устанавливается один из четырех возможных адресов AjOO, или AiOl, или AilO, или А,. Например, при формировании второй пары разрядов числа X, если ни один из четырех интервалов не замаскирован, по адресу AjOO должно быть записано слово, содержащее значения Е(1/1б), Е(2/1б) и F() функции разделения Е(Х); по адресу AiOl - слово, содержащее E(5/i6), Е(6/1б) и (/16); по адресу AI 10 - слово, содержащее Е(), Р(/1б) и F(4/L6); по адресу А,11 - слово, содержащее Р(), .) и Р(У|б). Поэтому при попадании в первом такте числа X, например, в третий интервал старщие разряды этого числа составляют Ь) 1, а Ь2 0. Тогда при условии а, Ь,, 32 Ь исполнительный адрес А равен AjlO и из памяти во втором такте считывается слово, содержащее значения Р(У1б), F(/i6) и Р(7 т. е. значения функции распределения на третьем интервале. Аналогично, при попадании числа X в другие интервалы будет формироваться адрес нужного слова. Таким образом, если ни один из четырех интервалов не замаскирован или замаскирован только один интервал, то необходимо, чтобы на выходы 50 и 51 блока 10 анализа проходили сигналы bi и b2 с выходов блока i-vi формирования разрядов т. е. чтобы а, Ь,, а Ь. В блоке 10 анализа это достигается тем, что выходы дещифратора 34 соответствующие значениям кода Zi,B разрядах которого находится не более одной единицы (т. е. замаскирован не более чем ВДин интервал) объединены с помощью элемента ИЛИ 35, в первую группу. Поэто У выходе элемента ИЛИ 35, единичный сигнал появляется только тогда, когда Цифровой код Zj, находящийся в регистре 33 nfnT:... Tnnn 1 1 1„„„ .:,..f 0100 или 1000. Сформированный таким образом на выходе элемента ИЛИ 35i единичный сигнал разрешает прохождение сигналов bj и Ьз через элементы И 36i и 36 на выходе 50 и 51 блока 10 анализа (сиг,, ,, нал с выхода элемента И Збг на вь1ход 51 блока 10 проходит через элемент ИЛИ 37, т. е. в этом случае имеем aj bi, а2 Ъ. Аналогично формируется исполнительный адрес Айв тех случаях, когда необходимо в процессе работы генератора случайных чисел выбрать из блока 3 памяти одно слово из двух возможных. В этом случае а, О, а равно либо нулю, либо единице в зависимости от значения сигналов Ь, и Ь. При а О получается четный исполнительный адрес, а при а2 1 - нечетный. Необходимость в формировании таких адресов возникает тогда, когда два интервала замаскированы, а два других интервала не замаскированы. Этому случаю соответствуют значения кода Zj, в разрядах которого имеется две единицы и два нуля. Поэтому выходы дешифратора, соответствующие значениям Zj, равным 1010, 1001, 0101, объединены с помощью во вторую группу, а выходы дещифратора, соответствующие значениям Zj, равным 1100, ОНО и ООП, объединены элементом ИЛИ 35, в третью гр.уппу. Таккм образом, на выходе либо элемента ИЛИ 35, либо элемента ИЛИ 35j единич ьш сигнал появится только тогда, когда в регистре 33 будет находиться цифровой код Z,, содержащий ровно две единицы. В этом случае на выход 51 блока 10 анализа пройдет либо сигнал bi, либо сигнал bg. Сигнал ba пройдет через элементы И Збд и ИЛИ 37 на выход блока 10 анализа при наличии разрешающего единичного сигнала на выходе элемента ИЛИ 35. В обоих последних случаях прохождение сигнала на первый выход 50 блока 10 анализа будет запрещено нулевым сигналом с выхода элемента ИЛИ 35, т. е. я 0. Таким образом, происходит формирование исполнительного адреса А в регистре 1 при наличии двух замаскированных интервалов. В тех случаях, когда замаскировано три интервала (т. е. в регистре 33 находится код Zj, содержащий один нуль и три единицы), возможно считывание из блока 3 памяти только одного слова и поэтому исполнительный адрес А равен адресу, поступающему из блока 3 памяти в регистр 1. Это достигается тем, что группа выходов дешифратора 34, соответствующая данному случаю, в схеме блока 10 анализа не задействована (на фиг. 4 выходы дешифратора 34, соответствующие данному случаю не показаны, так как эти выходы в схеме не используются) и, следовательно, сигналы bj и Ь2 не могут пройти на выходы блока 10, т. е. ai а2 0. Поскольку нулевые значения сигналов a и а2 не могут изменить значение адреса А, то этот адрес и равен адресу, поступающему в регистр 1 из блока 3 памяти. В случае, когда замаскированы все четыре интервала, на выходе элемента ИЛИ 44 всегда присутствует единичный сигнал R 1, который запрещает прохождение сигналов Ь, и Ь2 на выходы 50 и 51 блока 10 анализа, т. е. aj а2 0. т, , гч, Таким образом, блок 10 анализа формирует сигналы а, и а, , которые поступают в младшие разряды регистра 1 и сигнал R об окончании формирования очередного случайного числа Рассмотрим работу коммутатора 12 (фиг. 5). Коммутатор содержит регистр 53 сдвига, первая и вторая группы выходов которого подключены к первой и второй группам входов блока 54 элементов И соответственно. В первую группу выходов регистра 53 сдвига входят прямые выходы всех разрядов регистра 53,исключая выход последнего (самого младшего) разряда, а во вторую группу выходов регистра 53 входят инверсные выходы всех разрядов регистра 53, исключая выход первого (старшего) разряда. Исходное состояние регистра 53 устанавливается по сигналу с четвертого выхода генератора 4 тактовых импульсов. Этот сигнал поступает на вход 62 коммутатора 12 и записывает в старший разряд регистра 53 сдвига единицу, а в остальные разряды - нули, т. е. исходное состояние регистра 53 сдвига равно 100...00. Поэтому в первом такте каждого цикла единичный сигнал появляется только на выходе элемента И 54j, так как первый и второй входы элемента И 54iсоединены с прямым выходом первого разряда и с инверсным выходом второго разряда регистра 53 соответственно. Единичный сигнал с выхода элемента И 54 разрешает прохождение сигналов bj и Ь, поступающих на второй 59 и третий 60 входы коммутатора 12 через элементы И 55) и 552 на выходы 64i и 64 соответственно- Поскольку группа выходов 64 коммутатора 12 соединена с разрядными входами регистра 13, то в первом такте два старших разряда числа X поступают в старшие разряды регистра 13. Во втором такте по сигналу с третьего выхода генератора 4 тактовых импульсов, поступающему на четвертый вход 61 коммутатора 12, регистр 53 сдвига переходит в следующее состояние ПО...00, так как названный сигнал сдвигает содержимое регистра 53 на один разряд в сторону младщих разрядов и одновременно записывает в старший разряд регистра 53 единицу. Поэтому во втором такте единичный сигнал появляется только на выходе элемента И 54, и, следовательно, сигналы Ь,и Ъг через элементы и 55, и 55и и элементы ИЛИ 57, и 572 проходят на выходы 64,, и 64 коммутатора 12 соответственно. Таким образом, во втором такте очередные два разряда числа X поступают в третий и четвертый разр„ды регистра 13. Аналогично, в третьем такте регистр 53 сдвига переходит в состояние 1110...00 и разрешает прохождение сигналов bi и Ь2 на пятый 645 и шестой 64б выходы коммутатора 12 и т. д. Описанный процесс продолжается до тех пор, пока на первый вход коммутатора 12 не поступит п ij -, ,„ Г третьего выхода блока 10 анализа. Этот сигнал поступает на первую группу входов блока 56 элементов И и разР прохождение равномерно распреде ie oro числа, поступающего со второй группы выходов генератора 1 на группу ГПУППЫ RWYnTinR ГРНРПЯТППЯ НЯ входов 63 коммутатора 12, на те выходы коммутатора 12, которым соответствует нулевое состояние разрядов регистра 53. Это объясняется тем, что инверсные выхоДы регистра 53 подключены к третьей группе входов блока 56 элементов И, и, следовательно, открытыми для прохождения равномерно распределенного числа являются те элементы И блока 56, третьи входы которых подключены к выходам разрядов регистра 53, находящихся в нулевом состоя ии. Таким образом, после поступления сигнала к, 1 в старших разрядах регистра 3 находятся разряды числа X, полученные с помощью блока 9 формирования разряДОВ, а в младших разрядах - равномерно распределенное число, поступившее со второй группы выходов генератора 11. В первом такте следующего цикла число X через блок 14 элементов И подано на выход 17 устройства. Таким образом, за m тактов предлагаемое устройство формирует 2 m разрядное случайное число X, а недостающие (п-2т) разряды числа X на входы п разрядного регистра 13 подаются через коммутатор 12 со второй группы выходов генератора 11 равномерно распределенных случайных чисел. В прототипе за ш тактов формируется гп-разрядное случайное число, так как, в нем в каждом такте формируется только один разряд числа X с заданным законом распределения. Следовательно, предлагаемое устройство имеет более высокое быстродействие по сравнению с прототипом, поскольку в предлагаемом генераторе в каж дом такте формируется два разряда числа X. Поэтому при формировании чисел X, имеющих равное количество разрядов,предлагаемому устройству требуется в два раза меньше времени, чем прототипу. Заметим, что с целью еще большего повышения быстродействия в предлагаемом устройстве можно увеличить количество схем сравнения до семи. Тогда устройство -будет формировать в каждом такте три разряда случайного числа с заданным законом распределения. Аналогично, при увеличении количества схем сравнения до пятнадцати предлагаемое устройство будет формировать в каждом такте четыре разряда случайного числа и т. д. Использование изобретения позволяет повысить быстродействие устройства. Формула изобретения 1. Генератор случайных чисел, содержащий генератор тактовых импульсов, блок памяти, дещифратор, первый регистр памяти, выход которого через дешифратор соединен с первым входом блока памяти, второй вход которого подключен к первому выходу генератора тактовых импульсов, первую схему сравнения, генератор равномерно распределенных случайных чисел, блок элементов И, выход которого является выходом генератора, отличающийся тем, что, с целью повышения быстродействия, он содержит второй и третий регистры памяти, вторую и третью схемы сравнения, блок формирования разрядов числа, блок анализа, коммутатор, причем первый и второй входы «Пуск генератора тактовых импульсов являются первыми и вторыми входами «Пуск устройства, а третий вход генератора тактовых импульсов соединен с первым выходом блока анализа соответственно, первый выход блока памяти подключен к первому входу первого регистра памяти, второй вход которого соединен с первым выходом блока анализа, -второй выход блока памяти подключен к перво.му входу второго регистра памяти, первый, второй и третий выходы которого соединены с первыми входами первой, второй и третьей схем сравнения соответственно, а выходы схем сравнения подключены к соответствующим входам блока формирования разрядов числа, третий выход блока памяти соединен с первым входом блока анализа, второй и третий выходы которого подключены к третьему и четвертому входам первого регистра памяти соответственно, первый выход генератора тактовых импульсов соединен с пятым входом первого регистра памяти и с вторыми входами второго регистра памяти и блока анализа, второй выход генератора тактовых импульсов подключен к вторым входам схем сравнения и к третьему входу блока анализа, четвертый и пятый входы которого подключены соответственно к первым и вторым выходам блока формирования разрядов числа, третий выход генератора тактовых импульсов подключен к первому входу коммутатора, второй, третий и четвертый входы которого соединены с первым выходом блока анализа и первым и вторым выходами блока формирования разрядов числа соответственно, четвертый выход генератора тактовых и.мпульсов подключен к пятому входу коммутатора, к входу третьего регистра памяти, первому входу блока элементов И и к входу генератора равномерно распределенных случайных чисел, входы которого соединены с третьими входами схем сравнения, а группа выходов - с группой входов коммутатора соответственно, выходы которого подключены к группе входов третьего регистра памяти соответственно, выход которого соединен с вторым входом блока элементов И. 2.Генератор по п. 1, отличающийся тем, что блок формирования разрядов числа содержит два элемента И, элемент НЕ и элемент ИЛИ, первый вход первого элемента И является первым входом блока, второй вход которого через элемент НЕ соединен с вторым входом первого элемента И и непосредственно с первым входом второго элемента И, второй вход которого является третьим входом блока, первый выход которого объединен с его вторым входом, выходы элементов И соединены с входами элемента ИЛИ, выход которого является вторым выходом блока. 3.Генератор по п. 1, отличающийся тем, что блок анализа содержит регистр памяти, два дешифратора, два формирователя импульсов, два элемента ЗАПРЕТ, восемь элементов И и пять элементов ИЛИ, первый и второй входы блока подключены соответственно к двум входам регистра памяти, выходы которого соединены с соответствующими входами первого дешифратора, выходы которого соединены с соответствующими входами первых трех элементов ИЛИ, выход первого элемента ИЛИ соединен с первыми входами первого и второго элементов И, вторые входы которых подключены к выходам первого и второго элементов ЗАПРЕТ соответственно,первые входы которых подключены к выходам первоIU и второго формирователей импульсов соответственно, выходы второго и третьего элементов ИЛИ соединены с первыми входами третьего и четвертого элементов И соответственно, вторые входы которых подключены к выходам первого и второго элементов ЗАПРЕТ соответственно, выходы второго, третьего и четвертого элементов И соединены с соответствующими входами четвертого элемента ИЛИ, третий, четвертый и пятый входы блока подключены соответственно к трем входам второго дещифратора, выходы которого соединены с первыми входами пятого, щестого, седьмого и восьмого

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

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

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

/

/3

12

р

фм.2

Фиг.З

ФиеЛ

Фиг. 5