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

 

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

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

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

РЕСПУБЛИН (51) 4 С 06 F 7/58

11

1м

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

Н АBTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3808996/24-24 (22) 02.11.84 (46) 15.05.87. Бюл. № 18 (71) Минский радиотехнический институт (72) M.À.Îðëîâ, !О.П.Попов, Л.А.Смирнова и А.В.Силин (53) 681.333(088.8) (56) Авторское свидетельство СССР № 1049904, кл. С 06 F 7/58, 1982.

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

¹ 1007104, кл. С 06 F 7/58, 1981. (54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано при моделировании случайных процессов. Задачей, решаемой изобреЛ » 1 10813 А1 тением, является генерирование многоразрядных случайных чисел с требуемым законом распределения. Цель изобретение — повышение быстродействия.

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

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

1 131081

Изобретение относится к вычислительной технике и может быть использовано при моделировании случайных про" цессов, Цель изобретения — повышение бы- 5 стродействия генератора.

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

Генератор случайных чисел (фиг.l) содержит блоки 1< — 1ц перезаписи, группу регистров 2 1 — 2, блоки

3 — 3 „ контроля, блок 4 управления, блок 5 элементов И, блоки 6 1 — 6> сравнения, коммутатор,7, блок 8 шифрации, сумматор 9 по модулю два, два элемента И 10 и 11, два триггера 12, и 12, регистр 13 контроля, элемент

И 14, генератор 15 равномерно распределенных чисел.

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

25 модулю два группы, элемент ИЛИ 19 группы и элемент 2И-ИЛИ 20 группы.

Блок 6 j сравнения (фиг.3) содержит элементы И 212 и 212 четвертой группы, RS-триггеры 22 2 и 222 груп2j-1 21 пы ф

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

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

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

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

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

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

4 управления, который функционирует

3 2 следующим образом. По сигналу "Пуск" сбрасывается регистр 24, который организован как циклический сдвиговый регистр ° Этот же сигнал запускает генератор 23 импульсов, проходит через элементы ИЛИ 256 и 266 и производит начальный сброс RS-триггеров

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

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

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

РРЧ с соответствующими разрядами кодов вероятностей.

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

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

И-26g блока 4 управления, а также

k x RS-триггеров группы 22„ (k = 2, 4, 6... °, 2п) — с выхода седьмого элемента И 267 блока 4 управления.

Единичный сигнал с выхода элемента ИЛИ 30 поступает на вход блока

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

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

Если на первые входы элементов 21 -, и 21 поступает одинаковая информа21 ция, они вырабатывают нулевой сигнал и RS-триггеры 22 q>, и 22 остаются в нулевом состоянии. Если разряд кода10 вероятности больше разряда РРЧ, то на выходе элемента 21<, появляется единичный сигнал, который устанавливает в единицу соответствующий триггер 22 ., . В противном случае в еди- 15 ницу устанавливается RS-триггер 22, группы. Поскольку операция .сравнения начинается со старших разрядов, то установление в единицу одного из триггеров 22 группы означает, что в дан- 20 ном j-м блоке 6 » сравнения операция сравнения завершена.

Цикл сравнения продолжается до тех пор, пока на выходах регистров

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

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

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

В режиме нормального функционирования информация с выходов регистров

2 группы проходит через элементы И

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

2 группы суммируется в блоке 9 с контрольным битом, дополняющим сумму до четной. Контрольные биты хранятся в регистре 13 и на каждом такте сдвига1310813 tj ются в соответствии с информацией регистров 2 группы.

При возникновении одиночного сбоя единичный сигнал с выхода сумматора

9 по модулю два проходит через элемент И 10 и устанавливает триггер

12». Сигналом с выхода первого элемента И 26» блока 4 управления, возникающим по окончании цикла сравнения, единица из RS-триггера 12» пере-: писывается в D-òðèããåð 12 . Появление единицы в триггере 12 означает начало режима коррекции.

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

Далее следует цикл коррекции. B этом случае элементы И 28 третьей группы закрыты сигналом с инверсного входа триггера 12 и на счетные входы триггеров 29 группы информация не поступает. Поскольку в счетном триггере 29 -го блока контроля 3„ зафиксирована единица, то на первом входе элемента И 17 второй группы блока 1, перезаписи присутствует единичный сигнал, свидетельствующий о том, что в соответствующем регистре

2 группы произошла ошибка. В момент, когда сбойный разряд поступает на выход i-го регистра 2 группы, на выходе сумматора 9 по модулю два возникает единичный сигнал, поступающий на второй вход элемента И 17 второй группы; далее он проходит через элемент И 17 и складывается сумматором 18 по модулю два группы с ошибочным битом, поступающим с выхода регистра 2 группы. Таким образом, ошибка исправляется и скорректированный бит поступает через элементы ИЛИ

19 группы и 2И-ИЛИ 20 группы на информационный вход регистра 2.

Сигнал с выхода сумматора 9 по

1 модулю два проходит также через элемент И 11 и сбрасывает RS-триггер

12» . Очередной сигнал об окончании цикла сравнения переписывает нулевое содержимое триггера 12» в триггер

12, и цикл коррекции заканчивается.

Этот же сигнал сбрасывает счетные триггеры 29 группы.

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

5 131081

Г к выходам регистров 2 группы, а вторые информационные входы служат в качестве входов генератора случайных чисел для занесения левой и правой границ усеченной функции распределения. В этом случае перед началом цикла сравнения информация о левой и правой границах .в два такта записывается соответственно в j-e u k-e

RS-триггеры 22 группы (j=1 3 5,...

2п-1, k = 2, 4, 6,..., 2n). Далее следует цикл сравнения, причем окончательный результат сравнения формируется в пределах определенных ранее границ.

f5 входом третьего элемента ИЛИ, выход (n+6)-ro разряда регистра сдвига соединен с прямым входом четвертого элемента И, (n+3)-м входом второго элемента ИЛИ и с вторым входом первого элемента ИПИ, инверсный вход четвертого элемента И соединен с первым входом пятого элемента И и подключен к выходу пятого элемента ИЛИ, выход шестого элемента ИЛИ соединен с первым входом шестого элемента И, выход второго элемента ИЛИ соединен с первым входом седьмого элемента И, выход третьего элемента ИЛИ соединен с первым входом восьмого элемента И, выход

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

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

ИЛИ, регистр контроля, первый и второй триггеры, блок элементов И, коммутаторы и блок управления, который содержит генератор импульсов, регистр сдвига, семь элементов ИЛИ, одновибратор, девять элементов И, причем в 35 блоке управления выход одновибратора соединен с первым входом первого элемента ИЛИ, выход которого соединен с информационным входом регистра сдвига, выходы разрядов с первого по и-й 40 регистра сдвига (где n — число интервалов квантования функции распределения) соединены .с одноименными входами второго, третьего, четвертого и пятого элементов ИЛИ, выход (n+1)-ro разряда регистра сдвига соединен с (n+1)-м входом четвертого элемента

ИЛИ, первым входом первого элемента

И, выход (n+2)-го разряда регистра сдвига соединен с первым входом второго элемнта И, выход (а+3)-го разряда сдвига соединен с первым входом третьего элемента И, выход (n+4)-ro разряда регистра сдвига соединен с первым входом шестого элемента ИЛИ и (n+2)-ми входами второго и третьего элементов ИЛИ, выход (n+5)-ro разряда регистра сдвига соединен с (n+3)-M четвертого элемента ИЛИ соединен с первым входом девятого элемента И, выход пятого элемента И соединен с первым входом седьмого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента И, вход одновибратора соединен с входом обнуления регистра сдвига, входом запуска генератора импульсов, вторым входом шестого элемента ИЛИ, с (п+1)-ми входами второго и третьего элементов ИЛИ и является входом "Пуск" генератора случайных чисел, выход генератора импульсов соединен с вторыми входами первого, второго, третьего, шестого, седьмого, восьмого и девятого элементов И и с входом синхронизации регист" ра сдвига, первые прямые входы элементов 2И-ИЛИ,группы и информационный вход регистра контроля подключены к разрядным входам задания закона распределения генератора, инверсные входы элементов 2И-ИЛИ группы соединены с вторыми прямыми входами элементов

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

И, выходов регистров группы соединены с прямыми входами одноименных элементов И первой группы и с первыми входами сумматоров по модулю два группы, инверсный вход каждого элемента И первой группы соединен с выходом соответствующего элемента И второй груп» пы и вторым входом одноименного сумматора по модулю два группы, выход которого соединен с первым входом соответствующего элемента ИЛИ груп1310813 пы, второй вход которого соединен с выходом соответствующего элемента

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

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

"Сброс" счетных триггеров группы, единичный и нулевой входы RS-тригге- 20 ра соединены с выходами соответственно первого и второго элементов И, вторые входы которых объединены и подключены к выходу сумматора по модулю два и к вторым прямым входам элементов И второй группы, выходы элементов 2И-ИЛИ группы соединены с соответствующими информационными входами регистров группы, входы синхронизации регистров группы соединены с входом ЗО синхронизации регистра контроля, входом опроса генератора равномерно распределенных чисел и подключены к выходу девятого элемента И блока управления, второй вход пятого элемен35 та И блока управления соединен .с выходом генератора равномерно распределенных чисел, выход шестого элемента

И блока управления подключен к нулевым входам RS-триггеров группы, вы- 4 ход седьмого элемента И блока управI ления соединен с входами синхронизации k-x RS-триггеров группы (где k =

2, 4, 6,..., 2n), выход восьмого элемента И блока управления соединен с входами синхронизации j-x RS-триггеров группы (где j = 1, 3,...,2п-1), выход седьмого элемента ИЛИ блока управления соединен с инверсными входами j-х элементов И четвертой группы н с первыми прямыми входами k-x элементов И четвертой группы, выход каждого элемента И четвертой группы подключен к единичному входу одноименного.,RS-триггера группы, второй прямой вход каждого (k-го элемента И четвертой группы подключен к инверсному выходу (k-1)-ro RS-триггера группы, а инверсный выход k-го RS-триггера группы соединены с вторым прямым входом (k+1)-го элемента И четвертой группы, третьи прямые входы j-x элементов И четвертой группы и инверсные входы k-x элементов И четвертой группы подключены к соответствующим k-м вьисодам блока элементов И, управляющий вход которого соединен с выходом пятого элемента И11И блока управления, выходы второго и третьего элементов

И 6яока управления подключены к первому и второму управляющим входам коммутатора соответственно, первая группа информационных входов которого подключена к прямым выходам j-x RSтриггеров группы соответственно, а вторая группа информационных входов коммутатора соединена с инверсными выходами k-x RS-триггеров группы соответственно, выходы коммутатора соедииеиы с соответстующими входами блока шифрации, выход которого является выходом генератора.

1310813

1310813

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

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

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

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

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

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

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