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

 

ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ, срдержащий генератор равномернораспределенных случайных «чисел, блок пачто , с целью .упрощения и повышения надежности, он содержит генератор Тактовых импульсов, регистр, сдвига и сумматор, первый вход которого соединен с выходом генератора равномерно распределенных случайных чисел, вход которого объединен с тактовым входом ре пестра сдвига и подключен к выходу генератора тактовых импульсов , выход регистра сдвига соеданеи со своим входом Установка, является выходом генератора и соединен с входом блока памяти, выход которого соединен с вторым входом сумматора , выход которого соединен с инфор§ мационным входом регистра сдвига, (Л управляющий вход которого является входом Пуск генератора.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

geoG06 F 8

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3351759/18-24 (22) 06.11.81 (46) 30.03..83, Бюл. М 12 (72) С.Ф.Костюк, А.И.Кузьмич и А.Г.якубенко (71) Иинский радиотехнический институт (53) 681.325(088.8) (56) 1. Авторское свидетельство СССР

N 378826, кл. G 06 F 7/58, 1973.

2. Авторское свидетельство СССР и 430368 кл. G 06 F 7/58, 1974, 3. Авторское свидетельство СССР

N, 488212, кл. G 06 F 15/20, 1975 (прототип). (54) (57) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ, содержащий генератор равномерно распределенных случайных чисел, блок па-

„„SU„„1008?38 А мяти, отличающийся тем, что, с целью.упрощения и повышения надежности, он содержит генератор так;.овых импульсов, регистр сдвига и сумматор, первый вход которого сое. динен с выходом генератора равномерно распределенных случайных чисел, вход которого объединен с тактовым входом регистра сдвига и подключен к выходу генератора тактовых имгульсов, выход регистра сдвига соединен со своим входом "Установка", является выходом генератора и соединен с входом блока памяти, выход которого соединен с вторым входом сумматора, выход которого соединен с инфор- д мационным входом регистра сдвига, управляющий вход которого является входом "Пуск" генератора.

1 10

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

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

Недостатком устроиства является

его сложность, в частности наличие специализированного дешифратора.

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

Недостатком устройства является его сложность, в частности сложность управления.

Наиболее близким по технической сущности к предлагаемому является устройство для вероятностного моделирования, содержащее блок управления, генератор равномерно распределенных чисел, вход которого соединен с первым выходом блока управления, блок сравнения, первый вход которого соединен с выходом генератора равномерно распределенных чисел, а второй вход " с вторым выходом блока управления, регистр адреса, разделенный на две части (старшую и младшую), первый вход которого соединен с первым выходом блока сравнения, а второй вход - с пятым вы- ходом блока управления, блок памяти, вход которого соединен с выходом ре- . гистра адреса, регистр числа, первый вход которого соединен с выходом блока памяти, а второй вход - с чет08738 2 вертым выходом блока управления, регистр маски, первйй,вход которого соединен с выходом регистра числа, второй с вторым выходом блока сравнения, третий вход — с третьим выходом блока управления, первый выход соединен с третьим входом блока сравнения, а второй выход с третьим входом регистра адреса. Устройство по16 зволяет формировать последовательности случайных чисел с .требуемыми законами распределения. В устройстве реализуется метод обратных функций, основанный на сравнении

1 равномерно распределенных случайных чисел со значениями F(x ) воспро1 из води мой фун кци и р аспредел ения, отыскании интервала, для которого выполняет ся у сло ви е

F(x„) 7, Г(„+, ( и выдаче соот вет ст аующе ro дан ному интервалу значения х Перебор последовательно расположенных F(х )

25 логарифмический.

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

: регистр маски из блока памяти в блок сравнения поступает группа значений

F(x ), В результате сравнения в младшую част ь реги стра посту пает код. По этому коду из блока памяти выбирается и подается в блок сравнения очередная группа значений Цх, .), после чего содержимое младшей части регистра сдвигается и записывается следующий результат сравнения. Цикл сравнения длит ся rh.1оя,зп тактoe (где m - коли че ство интервалов квантования воспроизводимого закона по области его существования, а - основание логарифма перебора, а=2, n - любое положителья ное число). По коду, полученному в результате сравнения, выбирается ячейка памяти, содержащая о. значений х;, из которой с помощью регистра маски выбирается требуемое значение.

Устройство позволяет моделировать

2 различных законов распределений

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

3 ей с помощью старшей части регистра адреса (3) °

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

Цель изобретения - упрощение устройства и повышение надежности работы.

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

"Пуск" генератора.

Упрощение устройства достигается эа счет того, что для формирования; адресов чтения памяти и дпя. формирования случайного числа используется один регистр последовательных приближений, в прототипе для этих целей используется три регистра, причем регистр адреса является сложным (составным). Упрощение устройства достигается также за счет управления работой устройства сигналами с выхода регистра последовательных приближений, при этом отсутствует . специальный блок управления. Кроме того, все блоки устройства, за исключением генератора равномерно рас-. пределенных чисел, существуют в инO8738- 4

50,приближений - информационный, вход

S 0

На чертеже приведена структурная схема устройства.

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

Генератор 1 тактовых импульсов предназначен для генерации регулярной последовательности импульсов синхронизации устройства, для его реализации можно использовать интегральную схему К155НГ1.

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

1 из известныхпи. описанных в литературе.

Сумматор 3 может быть выполнен на интегральных схемах К155ИПЗ и др.

В качестве регистра 5 последовательных приближений можно использовать регистр последовательных приближений ,аналого-цифровых преобразователей (интегральная- схема К155ИР17), либо регистр сдвига типа К155ИР1.

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

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

Рассмотрим работу устройства при использовании регистра последовательных приближений типа К155ИР17, предназначенного-для построения аналогоцифровых преобразователей. При этом вход 6 регистра 5 последовательных

7 - синхронизации работы, вход 8 " разрешения работы, вход 9 - задания режима, причем вход 9 соединен с вы- .г ходом младшего, разряда.

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

8738

10

Таблица 1

Р "7

Р10 б

Р, -13

Рооо 0,Ро(2

4 Р -6

50 41

5 100

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

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

Ilo сформированному на выходе регистра. 5 nrследовательных приближений новому адресу из блока 4 памяти считывается новый код, суммируется с новым случайным числом, по заднему фронту следующе го тактового импул ь са сформированный второй разряд выходного числа принимается во второй разряд регистра 5, нуль из второго разряда регистра 5 сдвигается в следующий (третий) разряд, генератор 2 равномерно распределенных случайных чисел формирует новое первичное слу-, чайное число. Последовательность описанных тактов идет до сдвига нуля в младший разряд регистра 5. Нуль в мпадшам разряде регистра 5 указывает, что число сформировано, поступая на вход 9 регистра, разрешает установку начального состояния. Код сформированного случайного числа находится в регистре последовательных при-: ближений.

Так как на первый вход 10 сумма" тора 3 поступают равномерно распре" деленные числа с интервалом от 0 до 1-2", где И - разрядНость сумматора, генератора 2 равномерно распределенных случайных чисел и блока

4 памяти, вероятность единицы на вы" ходе переноса сумматора, вырабатываемой, если сумма чисел больше единицы, равна поступающему на второй вход 11 сумматора 3 коду из блока 4 памяти„На первом такте иэ блока памяти читает ся код, равный вероя тности попадания случайной величины воспроизводимого закона распределения, во вторую половину области существования (вероятность единицы старшего разряда формируемых чисел), На втором такте читается код, задающий условную вероятность попадания во вторую четверть, если первый сформированный разряд равен нулю, или в четвертую четверть, если сформированный первый разряд равен единице, т.е. задается условная вероятность единицы Во втором разряде. На последующих тактах задаются в зависимости от полученных значений разрядов формируемого числа условные вероятности попадания случайной величины в соответствующие

1/2 части области существования, где - номер такта. Например, если на первых двух тактах получена комбинация 10, на третьем такте из блока памяти читается код условной вероятности попадания случайной величины воспроизводимого закона pac" пределения s интервал от 5/8 до 6/8 области существования.

На каждом такте задаются условные вероятности, отсюда и название

"Метод условных вероятностей", В табл. 1 показано расположение кодов условных вероятностей в блоке

4 памяти для случая, если устройство формирует четырехразрядные случайные числа. В каждой клетке табл.1 слева указывается обозначение кода вероятности, справа - адрес ячейки.

Нумерация адресов памяти с нуля.

Верхний индекс в обозначении кода вероятности - результат, полученный на предыдущих тактах.

7 10087

Если обозначить Р - вероятность

k-й кодовой комбинации формируемых случайных чисел (k=0-2 -1, где m разрядность формируемых чисел), ychaaные вероятности Р вычисляются по формуле где i =l,m; j =0-2" -1; r=2; =2 +j .:.

1, rA+1-1 О j-4

Устройство может формировать случайные числа и по методу обратных функций, для этого необходимо, чтобы )S гейератор 2 равномерно распределенТаблица 2

Г "3

F 13

F -8 F<0-10 F -12 F -14 тактового импульса содержимое резокгистра 5 последовательных приближе: ний сдвигается в сторону старших (35

F -O F-2 Х -4 Г-б о 4 6

Г

: 0 этом случае, как и в прототипе, осуществляется логарифмический перебор кодов вероятностей, если PKтребуемые вероятности .кодовых комбинаций.

Как говорилось выше, в качестве регистра 5 данного генератора случайных чисел можно использовать регистр сдвига с возможностью параллельного занесения кода, типа существующего интегрального регистра К155ИР17. При этом вход 6 регистра ; 5 последовательных приближений является входом последовательной записи регистра сдвига, вход 7 - синх-. ронизации сдвига, вход 8 - синхронизации параллельной записи, вход

9 - задания режима, соединенный со старшим выходом регистра.

Цикл формирования случайного чис" ла начинается при поступлении на вход 8 импульса запуска, если в старшем разряде регистра 6 единица.

При этом по входам параллельной за" писи в старший разряд записывается единица, во всех остальных — нули.

На каждом такте формируется аналогично (как описано выше) один разряд выходного числа; по заднему фронту

38 8

;ных случайных чисел формировал одно число на весь цикл формирования выходного числа, а не новое на каждом такте. Для этого выходной регистр генератора 2 равномерно распределенных случайных чисел можно синхрони- зировать выходом мпадшего разряда регистра 5, а не.импульсами генератора 1 тактовых импульсов. При этом в блок памяти последовательно записываются значения интегральной функции распределения F, начиная с нулевой ячейки. Расположение кодов в блоке памяти для случая формирования четырехразрядных случайных чисел показано в табл. 2., разрядов, значение, сформированного разряда принимается в младший разряд регистра 5. формирование числа заканчивается при сдвиге единицы в старший разряд регистра 5. Единица на входе 9 регистра 5 последовательных приближений запрещает даЛьнейший сдвиг и разрешает начальную усвания числа.

Единица с выхода старшего разряда регистра 5 является указателем готовности числа, сформированное число находится в регистре. Как и в рассмотренном выше случае, при использовании в качестве регистра 5 последовательных приближений регистра сдвига, можно формировать алучайные числа как по методу условных вероятностей, так и по методу обрат- ных функций, причем расчет кодов настройки выполняется по тем же фор- мулам. Расположение кодов в памяти при методе условных вероятностей для случая формирования четырехраз-. рядных случайных чисел показано в табл. 3.

1008738

Таблица 3

P -1

Р" -3

Р -г оо

Рц -4

ff, Р -7 т

Таблиц а 4

F7 -1

F -2

F1„-3 (F "6

Fg 5

ГВ-12 F(() 13 F12 14 Е14 15

9 F "10 2 4

Fá

Иэ табл. 1-4 видно, что при методе условных вероятностей в случае использования регистра последователь- Зв ных приближений набазе регистра сдвига, расположение кодов в памяти сов падает с порядком их расчета, при ме тоде обратных функций расположение кодов в памяти и порядок их расчета совпадают в случае использования регистра последовательных приближений, применяемэго в аналого-цифровых преобразователях. Если датчик случайных чисел используется совместно с ЭВМ, которая осуществляет расчет кодов настройки и их загрузку, при совпа-. дении порядка расчета кодов и их разгрузке системе оказывается более эффективной, так как не требуется дополнительной перестановки кодов.

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

Расположение кодов в памяти при методе обратных функций для случая формирования четырехразрядных aiyчайных чисел показано в табл. 4.

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

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

В табл. 5 показано расположение кодов вероятностей в блоке памяти при использовании метода условных вероятностей, при объеме блока памяти 16 ячеек, для случая моделирования двух законов распределения.

1008738

12 Т а блц,ц а 5

««««

Р -4

8 (Р, (Р, -5 (Ру з-7

Р„6

ОО (О И Оо 1 О(1о

Р - -9 Р1,6 -10 Р -11 Рг,1 -12) Ру -13, 4) Рг у-15

Таблиц а 6

Й

Р„6 о

2,Ъ

Р -10 P "11

Р1 12 Рэ 13 Р,-14 Рз 15

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

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

В первой строчке табл ° 6 коды, определяющие вероятность переходов в одно из старших состояний, в нижней строчке - коды условных вероятностей.

Так, например, P - вероятность пео рехода цепи в состояние 2 или 3, если она находится в состоянии 1, Р Ф вероятность перехода цепи из состояния 1 в состояние 2, если на предыдущем такте определилось, что цепь переходит в состояние 2 или 3. В начале цикла генерации нового состояния в младшие два разряда регистра 5 заносится номер состояния цепи, в третий разряд единица. 3а два такта генерируется состояние, единица сдвигается в старший разряд регистра последовательных приближений.

Максимальное число состояний ИарKoBcKol o процесса и его максимальная связность с необходимым числом состояний, -количество моделируемых чисе((равна количеству разрядов регистра последовательных приближений в начальном состоянии равных нулю, начиная со старшего разряда до первого разряда устанавливаемого в единицу, номер распределения задается кодом, следующим за первой единицей. В„табл.5 первый нижний индекс в обозначении кода вероятности указывает на номер распределения.

В табл. 6 показано размещение кодов вероятностей переходов при моде-. лировании односвязной цепи Иаркова, описываемой матрицей, вероятностей перехода типа Р (), 1=0,1,2,3) для блока памяти объемом 16 слов. в режиме разделения времени процессов

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

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

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

Редактор Е. Папп Техред Т.Фанта

Корректор М.Шароши

Заказ 2339/59 Тираж 704 . Подписное

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

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

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

13. 1008738 14 рий, в системах управления испыта " в виде одной микросхемы, так как все ниями, в моделирующих системах. блоки устройства могут реализовыВажной предпосылкой для реально- ваться на микросхемах средней интегго широкого применения устройства рации, без и спользования специ али зиявляется воэможность его реализации рованных элементов.