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

25

1 131081

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

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

На фиг.1 представлена структурная хема генератора случайных чисел; на иг,2 - схема блока перезаписи; на иг.З - схема блока сравнения; на fO иг,4 - схема блока управления.

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

Блок 1 перезаписи (фиг«2) содержит элемент И 16 первой группы, элемент. И 17 Ёторой группы, сумматор 18 по модулю два группы, элемент ИЛИ 19 группы и элемент 2И-ИЛИ 20 группы.

Блок 6; сравнения (фиг.З) содержит элементы И 212;:.,и 212; четвертой эп группы, RS-триггеры и 222 группы.

Блок 4 управления (фиг,4) содержит генератор 23 импульсов, регистр 24 сдвига, семь элементов ИЛИ 25 - 25;, девять элементов И 26, - 26g и одно- вибратор 27,

Блок 3, 3 контроля содержит элемент И 28 третьей группы и счетный триггер 29 группы.

Рассмотрим работу генератора случайных чисел.

Перед началом работы производится запись информации в регистры 2 группы. Для этого на вход.задания режима генератора подается нулевой сигнал, который разрешает запись информации в регистры 2 группы, -За (га+Г) тактов сдвига (т -. разрядность кода вероятностей, (т+1)-й разряд - контрольный) происходит заполнение регистров 2, Затем на вход задания режима генератора подается единичный сигнал и регистры 2 группы начинают функционировать как циклические.

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

50

55

5

81

O

0

эп

50

55

32

следующим образом„ По сигналу Пуск сбрасывается регистр 24, который организован как циклический сдвиговый регистр. Этот же сигнал запускает генератор 23 импульсов, проходит через элементы ИЛИ 25 и 26б и производит начальньм сброс RS-триггеров 22 группы блоков 6 сравнения. По этому сигналу с задержкой С , необходимой для сброса RS-триггеров 22 груп-) пы, одновибратор 27 формирует единичный сигнал начальной установки, который через первьй элемент ИЛИ 25/поступает на информационный вход регистра 24 и вторым импульсом генератора 23 записьшается в младший разряд регистра 24. Далее в течение всего функциони1)ования устройства регистр 24 работает как циклический сдвиговый регистр, в котором перемещается единица,

С помощью элементов ИЛИ 25 вырабатывается разрешение на прохождение импульсов генератора 23 через соответствующие элементы И 26,

После окончания установочных операций начинается функционирование устройства, т,е, сравнение равномерно распределенного числа (РРЧ) с кодами вероятностей функции распределения, В каждый такт работы устройства происходит сравнение одного разряда РРЧ с соответствующими разрядами кодов вероятностей,

К началу цикла сравнения на выходах регистров 2 группы устанавливаются старшие разряды кодов вероятностей.

Блок 4 управления на первых п тактах обеспечивает выработку п синхронизирующих импульсов, которые сдвигают информацию в регистрах 2 группы и в регистре 13 (с выхода девятого элемента И 26,; блока 4 управления), а также синхронизацию j-x RS-триггеров группы 22 ц (k 1,3, 5,,,,, 2п-1) - с выхода восьмого элемента И-26д блока 4 управления, а также k-x RS-тртиггеров группы 22 (k 2, 4, 6,,,,, 2п) - с выхода седьмого элемента И 2()j блока 4 управления,

Единичнь й сигнал с выхода элемента ИЛИ 305 поступает на вход блока 5 элементов И и разрешает прохождение кодов вероятностей функции распределения через него, а также обеспечивает прохождение цифры РРЧ с выхода

ются в соответствии с информацией регистров 2 группы.

При возникновении одиночного сбоя единичный сигнал с выхода сумматора 9 по модулю два проходит через элемент И 10 и устанавливает триггер 12,. Сигналом с выхода первого элемента И 26) блока 4 управления, возникающим по окончании цикла сравне25

.генератора 15 на входы блоков 6 сравнения .

В каждом блоке 6 j сравнения с по- , мощью элементов И 21 четвертой груп- пь производится операция сравнения. Если на первые входы элементов и 212 поступает одинаковая информация, они вырабатывают нулевой сигнал и RS-триггеры 22 j., и 222J остаются в нулевом состоянии. Если разряд кодаШ ния, единица из RS-триггера 12 перевероятности больше разряда РРЧ, то на выходе элемента 2l2j-i появляется единичный сигнал, который устанавливает в единицу соответствующий триггер 22,j, . В противном случае в еди- 5 ницу устанавливается RS-триггер группы. Поскольку операция.сравнения начинается со старших разрядов, то установление в единицу одного из триггеров 22 группы означает, что в дан- 20 ном J-M блоке 6j сравнения операция сравнения завершена.

Цикл сравнеь ия продолжается до тех пор, пока на выходах регистров 2 группы не появятся младшие разряды кодов вероятностей, хотя для его завершения достаточно, чтобы во всех блоках 6 сравнения сработал хотя бы один из триггеров 22j или 22 к , и, соответственно, запретил срабатывание второгоо

После окончания цикла сравнения информация с выходов блоков 6 сравнения поступает через коммутатор 7 на входы блока шифрации и на выход уст- 35 ройства.

Дпя контроля и самовосстановления одиночных сбоев в предлагаемом уст- ройстве используются сумматор 9 по модулю два, а также блоки 3 контро- 0 . ля.

- 1

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

50

писывается в D-триггер 12. Появление единицы в триггере 12. означает начало режима коррекции.

ЕСЛИ сбой одиноч1а й, то в одном из счетных триггеров группы будет зафиксирована единица.

Далее следует цикл коррекции. В этом случае элементы И 28 третьей группы закрыты сигналом с инверсного входа триггера 12 и на счетные входы триггеров 29 группы информация не поступает. Поскольку в счетном триггере 29 i-ro блока контроля 3 i зафиксирована единица, то на первом входе элемента И 17 второй группы блока 1 перезаписи присутствует единичный сигнал, свидетельствуюш ий о том, что в соответствующем регистре 2 группы произошла ошибка. В момент, когда сбойный разряд поступает на выход i-ro регистра 2 группы, на выходе сумматора 9 по модулю два возникает единичный сигнал, поступающий на второй вход элемента И 17 второй группы; далее он проходит через элемент И 17 и складывается сумматором 18 по модулю два группы с ошибочным битом, поступаюшз м с выхода регистра 2 группы. Таким образом, ошибка исправляется и скорректированный бит поступает через элементы ИЛИ 19 группы и 2И-ИЛИ 20 группы на информационный вход регистра 2.

Сигнал с выхода сумматора 9 по модулю два проходит также через элемент И 11 и сбрасьтает RS-триггер 12,. Очередной сигнал об окончании цикла сравнения переписьшает нулевое содержимое триггера 12 в триггер 12,, и цикл коррекции заканчивается. Этот же сигнал сбрасывает счетные триггеры 29 группы.

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

ются в соответствии с информацией регистров 2 группы.

При возникновении одиночного сбоя единичный сигнал с выхода сумматора 9 по модулю два проходит через элемент И 10 и устанавливает триггер 12,. Сигналом с выхода первого элемента И 26) блока 4 управления, возникающим по окончании цикла сравнения, единица из RS-триггера 12 пере5

Ш ния, единица из RS-триггера 12 пере 50

5

0

0

0

писывается в D-триггер 12. Появление единицы в триггере 12. означает начало режима коррекции.

ЕСЛИ сбой одиноч1а й, то в одном из счетных триггеров группы будет зафиксирована единица.

Далее следует цикл коррекции. В этом случае элементы И 28 третьей группы закрыты сигналом с инверсного входа триггера 12 и на счетные входы триггеров 29 группы информация не поступает. Поскольку в счетном триггере 29 i-ro блока контроля 3 i зафиксирована единица, то на первом входе элемента И 17 второй группы блока 1 перезаписи присутствует единичный сигнал, свидетельствуюш ий о том, что в соответствующем регистре 2 группы произошла ошибка. В момент, когда сбойный разряд поступает на выход i-ro регистра 2 группы, на выходе сумматора 9 по модулю два возникает единичный сигнал, поступающий на второй вход элемента И 17 второй группы; далее он проходит через элемент И 17 и складывается сумматором 18 по модулю два группы с ошибочным битом, поступаюшз м с выхода регистра 2 группы. Таким образом, ошибка исправляется и скорректированный бит поступает через элементы ИЛИ 19 группы и 2И-ИЛИ 20 группы на информационный вход регистра 2.

Сигнал с выхода сумматора 9 по модулю два проходит также через элемент И 11 и сбрасьтает RS-триггер 12,. Очередной сигнал об окончании цикла сравнения переписьшает нулевое содержимое триггера 12 в триггер 12,, и цикл коррекции заканчивается. Этот же сигнал сбрасывает счетные триггеры 29 группы.

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

.-

5 .13

к выходам регистров 2 группы, а вторые информационные входы служат в качестве входов генератора случайных чисел для занесения левой и правой границ усеченной функции распределе ния, В этом случае перед началом цикла сравнения информация о левой и правой границах .в два такта записывается соответственно в j-e и k-e RS-триггеры 22 группы (, 3, 5,..., 2п-1, k 2, 4, 6,..., 2п). Далее следует цикл сравнения, причем окончательный результат сравнения формируется в пределах определенных ранее границ.

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

Генератор случайных чисел, содержащий генератор равномерно распреде- ленных чисел, группу регистров, блок шифрации, отличающийся тем, что, с целью повышения быстродействия, он содержит четыре группы элементов И, группу счетных- тригге ров, группу RS-триггеров, три элемента И, сумматор по модулю два, группу элементов 2И-ИЛИ, группу сумматоров по модулю два, группу элементов ИЛИ, регистр контроля, первый и вто- рой триггеры, блок элементов И, ком- мутаторы и блок управления, который содержит генератор импульсов, регистр сдвига, семь элементов ИЛИ, одновиб- ратор, девять элементов И, причем в блоке управления выход одновибратора соединен с первым входом первого элемента ИЛИ, выход которого соединен с информационным входом регистра сдвига, выхода разрядов с первого по п-й регистра сдвига (где п - число интервалов квантования функции распределения) соединены с одноименными входами второго, третьего, четвертого и пятого элементов ИЛИ, выход (п+1)-го разряда регистра сдвига соединен с (п+1)-м входом четвертого элемента ИЛИ, первым входом первого элемента И, выход (п+2)-го разряда регистра сдвига соединен с первьм входом вто- рого элемнта И, выход (п-ьЗ)-го разряда сдвига соединен с первым входом третьего элемента И, выход (п+4)-го разряда регистра сдвига соединен с первым входом шестого элемента ИЛИ и (п+2)-ми входами второго и третьего элементов ИЛИ, выход (п+5)-го разряда регистра сдвига соединен с (п+3)36

входом третьего элемента ИЛИ, выход (п+6)-го разряда регистра сдвига соединен с прямым входом четвертого элемента И, (п+3)-м входом второго элемента ИЛИ и с вторым входом первого элемента ИЛИ, инверсный вход четвертого элемента И соединен с первым входом пятого элемента И и подключен к выходу пятого элемента ИЛИ, выход шестого элемента ИЛИ соединен с первым входом шестого элемента И, выход второго элемента ИЛИ соединен с первым входом седьмого элемента И, выход третьего элемента ИЛИ соединен с первым входом восьмого элемента И, выход четвертого элемента ИЛИ соединен с первым входом девятого элемента И, выход пятого элемента И соединен с первым входом седьмого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента И, вход одно- вибратора соединен с входом обнуления регистра сдвига, входом запуска генератора импульсов, вторым входом шестого элемента ИЛИ, с (п+1)-ми входами второго и третьего элементов ИЛИ и является входом Пуск генератора случайных чисел, выход генератора импульсов соединен с вторыми входами первого, второго, третьего, шестого, седьмого, восьмого и девятого элементов И и с входом синхронизации регистра сдвига, первые прямые входы элементов 2И-ИЛИ .группы и информационный вход регистра контроля подключены к разрядным входам задания закона распределения генератора, инверсные входы элементов 2И-ИЛИ группы соединены с вторыми прямыми входами элементов 2И-ИЛИ группы, с тактовым входом регистра контроля и подключены к входу задания режима генератора, выходы регистров группы и выход регистра контроля подключены к соответствующим входам сумматора по модулю два, выходы регистров группы подключены к группе информационных входов блока элементов И, выходов регистров группы соединены с прямыми входами одноименных элементов И первой группы и с первыми входами сумматоров по модулю два группы, инверсный вход каждого элемента И первой группы соединен с выходом соответствующего элемента И второй группы и вторым входом одноименного сумматора по модулю два группы, выход которого соединен с первым входом соответствующего элемента ИЛИ группы, второй вход которого соединен с выходом соответствующего элемента И первой группы, инверсные первые входы элементов и третьей группы соединены с первыми входами первого и второго элементов И, с инверсными входами элементов И второй группы и подключены к инверсному выходу D-триг гера, первые прямые входы элементов И второй группы подключены к выходам соответствующих счетных триггеров группы, выход первого элемента И блока управления соединен с первым входом третьего элeмeнta И и входом синхронизации С-триггера, вход которого соединен с выходом RS-триггера Игвторым входом третьего элемента И, вйход которого подключен к входам Сброс счетных триггеров группы, единичный и нулевой входы RS-тригге- ра соединены с выходами соответственно первого и второго элементов И, вторые входы которых объединены и подключены к выходу сумматора по модулю два и к вторым прямым входам элемен- тов И второй группы, выходы элементов 2И-ИЛИ группы соединены с соответствующими информационными входами регистров группы, входы синхронизации регистров группы соединены с входом синхронизации регистра контроля, входом опроса генератора равномерно распределенных чисел и подключены к выходу девятого элемента И блока управления, второй вход пятого элемен та И блока управления соедииен .с выходом генератора равномерно распределенных чисел, выход шестого элемента И блока управления подключен к иуле- вым входам RS-триггеров группы, вы- ход седьмого элемента И блока управления соединен с входами синхронизации k-x RS-триггеров группы (где k 2, 4, 6,с.., 2п), выход восьмого элемента И блока управления соединен с входами синхронизации j-x RS-триггеров группы (где j 1, 3,...,2п-1) выход седьмого элемента ИЛИ блока управления соединен с инверсными входами j-x элементов И четвертой группы и с первьми прямыми входами k-x элементов И четвертой группы, выход каждого элемента И четвертой группы подключен к единичному входу одноименного-, RS-триггера группы, второй прямой вход каждого (k-ro элемента И четвертой группы подключен к инверсному выходу (k-l)-ro RS-триггера группы, а инверсный выход k-ro RS-триггера группы соединены с эторым прямым входом (k+l)-ro элемента И четвертой группы, третьи прямые входы j-x элементов И четвертой группы и инверсные входы k-x элементов И четвертой группы подключены к соответствующим k-м выходам блока элементов И, управляющий вход которого соединен с выходом пятого элемента ИЛИ блока управления, выхо0 1 второго и третьего элементов И блока управления подключены к первому и второму управляющим входам коммутатора соответственно, первая группа информационных входов которого подключена к прямым выходам j-x RS- триггеров группы соответственно, а вторая группа информационных входов коммутатора соединена с инверсными выходами k-x RS-триггеров грзгапы соответственно, выходы коммутатора соединены с соответстующими входами блока шифрация, выход которого является вводом генератора.

фиг. 2

Изобретение относится к вычислительной технике и может быть использовано при моделировании случайных процессов. Задачей, решаемой изобре тением, является генерирование многоразрядных случайных -чисел с требуемым законом распределения. Цель изобретение - повьшение быстродействия. Цель достигается за счет введения новых функциональных связей и блоко. Генератор содержит блоки 1 перезаписи, группу 2 регистров, блоки контроля 3, блоки сравнения 6, блок 5 элементов И, коммутатор 7, блок шифра- ции 8, сумматор по модулю два 9, два триггера 12, регистр контроля 13, элементы И 10, 11, 14, генератор равномерно распределенных чисел 15, блок управления 4. Одним из преимуществ генератора является введение в его с структуру средств контроля и самовос- становления одиночных сбоев. 4 ил. (Л PefKUfiJ Паск СО ОО СО Фи9.1

%/

t, J-l

R

%

фиг.З

Редактор М.Дылын

Составитель И.Столяров

Техред Л.Олейник Корректор Г.Решетник

Заказ 1892/45 Тираж 673Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4