Генератор случайных чисел
Воес в,ная
Вэл бит но-техническая опись -иж
"("„)Е®4185 Союз Саеетсмих
Социалистически
Увсиублнк
ИЗОБРЕТЕНИЯ (61) Дополнительное к авт. саид-ву{22) Заявлено 210277 (21) 2454570/18-24 (51)М. Кл.2
G 07 С 15/00
G F 1/02 с присоединением заявки N9—Госуварствеииый комитет
СССР ио деаам изобретений и открытий (23) Приоритет
Опубликовано 250579 Бюллетень Ж 19 (53) УДК 681. 326 (088. 8) Дата опубликования описания 28.0579 (72) АВТОРЫ В.A.Ïecîøèí, В.И.Тарасов и Р.И.Иансуроэ изобретения (73) Заявитель казанский ордена трудового красного знамени авиационный институт им. A.Í. Туполева (54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ
Изобретение относится к области вычислительной техники и может найти применение при статистическом моделировании в цифровых электронных вы. числительных машинах.
Известны генераторы случайных чисел с заданными законами распределения.
Один из известных генераторов содержит датчик равномерно распределенных чисел, запоминающее устройство, схемы параллельного сравнения чисел, триггеры, схемы совпадения, выходное устройство H позволяет получать случайные числа эа один такт работы датчика, но имеет высокую сложность(1).
Другой из известных генераторов содержит генератор равномерно распределенных случайных чисел, схему сравнении, запоминающее устройство, блок логарифмического перебора, генератор тактовых импульсов н имеет низкое быстродействие, так как в каждом- такте работы датчика формируется только один разряд случайного числа (23.
Наиболее близким Во технической сущности решением к данному изобретению является генератор случайных чисел, содержащий генератор тактовых импульсов, регистр первых разрядов случайных чисел, разрядные выходы которого являются выходами генератора, первый преобразователь кодвероятность, счетчик тактовых им пульсов, вход которого подключен к первому выходу генератора тактовых импульсов, дешифратор номера такта, входы которого соединены с разрядными выходами счетчика тактовых импульсов, регистр кода закона распределения, вход которого подключен к первому входу генератора, дешифратор кода закона распределения, входы которого соединены с разрядными выходами регистра кода закона распределения, а выходы — со входом генератора тактовых импульсов, группу элементов И, выходы которых подключены к разрядным входам регистра первых разрядов случайных чисел, а первая и вторая группы входов — к выходам дешифратора номера такта и к выходу первого преобразователя кодвероятность, соответственно, дешифратор кодовых комбинаций, входы которого соединены с разрядными выходами регистра первых разрядов случайных чисел, с выходами дешифратора кода
664185 закона распределения, дешифратора номера такта и со вторым выходом генератора тактовых импульсов соответственно, блок памяти, входы которого соединены со вторым входом генератора, с разрядными выходами регистра первых разрядов случайных чисел, с выходами дешифратора номера такта и с третьим выходом генератора тактовых импульсов соответственно (3).
Известный генератор, реализующий метод условных вероятностей, облада- О ет низким быстродействием. так как в каждЬм такте работы, генератора фор. мируется только один старший разряд случайного числа.
Целью изобретения является повыше-(5 ние быстродействия генератора случайных чисел.
Поставленная цель достигается тем, что генератор содержит коммутатор, второй и третий преобразователи кодЯО вероятность ; первую, вторую и третью группы элементов ИЛИ, входы которых соединены с выходами дешифратора кодовых комбинаций и с выходами блока памяти соответственно, а выходы подключены к разрядным входам первого, второго и третьего преобразователей код-вероятность, соответственно, тактовые входы которых объединены и подключены к четвертому выходу генератора тактовых импульсов, выход коммутатора соединен с третьей группой входов группы элементов И, а входы его подключены к выходам дешифратора номера такта и к выходам первого,второго и третьего преобразователей " код-вероятность, соответственно.
Блок-схема генератора приведена на фиг. 1. Фиг. 2 иллюстрирует метод приближения заданной плотности f (у) плотностью f* {у) .
Генератор содержит регистр 1 кода закона распределения,-дешифратор 2 кода закона распределения, счетчик
3 тактовых импульсов, дешифратор 4 номера такта, генератор 5 тактовых 45 импульсов, блок 6 памяти, дешифратор
7 кодовых комбинаций, группу 8 элементов И, регистр 9 первых разрядов случайных чисел, группы 10, 11, 12 элементов ИЛИ, преобразователи 13, 1 4 15 код-вероятность, коммутатор 16, элемент 17 НЕ, элементы 18, 19,20 И, элемент 21 ИЛИ,входы 22,23 генератора и выходы 24 генератора.
Вход регистра 1 кода закона распределения соединен с первым входом
22 генератора, а разрядные выходы регистра 1 подключены ко входам дешифратора 2 кода зааона распределения, .выходы дешифратора 2 соединены со входами дешифратора 7 кодовых комбинаций и генератора 5 тактовых импуль-, сов ° Вход счетчика 3 тактовых импульсов подключен к одному иэ выходов генератора 5 тактовых импульсов, другие выходы которого соединены со 65 входами блока 6 памяти, дешифратора
7 кодовых комбинаций, первого 13, в горого 14 и третьего 15 преобразователей код-вероятность . Входы дешифратора 4 номера такта подключены к разрядным выходам счетчика 3 тактовых импульсов, а выходы дешифратора
4 соединены с управляющими входами дешифратора 7 кодовых комбинаций, группы 8 элементов И и коммутатора
16 ° Выходы группы 8 элементов И соединены со входами регистра 9 первых разрядов случайных чисел, разрядные выходы которого подключены ко входам дЕшифратора 7 кодовых комбинаций, блока 6 памяти и к выходам 24 генератора. Входы блока 6 памяти соединеиы со вторым входом 23 генератора и с выходами дешифратора 4 номера такта. Входы первой 10, второй 11, третьей 12 групп элементов ИЛИ подключены к соответствующим выходам дешиф ратора 7 кодовых комбинаций и блока
6 памяти, а выходы названных групп элементов ИЛИ соединены со входами первого 13, второго 14 и третьего 15 преобразователей код-вероятность", соответственно. Выхбды первого 13, второго 14 и третьего 15 преобразователей код-вероятность подключены ко входам коммутатора 16, выходы которого соединены со входами группы
8 элементов И,а .на другие входы группы 8 элементов И подключены к выходу первого преобразователя 13 кодвероятность .
Генератор работает следующим образом.
Пусть константы условной вероятности хранятся в блоке 6 памяти. В первом такте (такт работы генератора задается генератором 5 тактовых импульсов и счетчиком 3 тактовых импульсов) из блока 6 памяти считываются константы Р (.1), Р2 (1/1) и Р2 (1/О), которые поступают через группы элементов ИЛИ на входы первого, второго и третьего преобразователей код-вероятность, соответственно, где Р< (1)
- вероятность появления единицы в первом разряде формируемого случайного числа;
Р2(1/1) и P2(1/О) — Условные веро ятности появлейия единицы во втором, разряде случайного числа при условии, что в первом разряде числа имеется единица или ноль соответственно.
В момент времени,задаваемый генератором 5 тактовых импульсов,сраба" тывают первый, второй и третий преобразователи, код-вероятность, на выходах которых единичные символы могут появиться с вероятностями Р.„ (1), Р2(1/1) и Р (1/О) соответственно.
Если в первом разряде формируемого случайного числа появилась единица (первый разряд числа формируется первым преобразователем 13 код-вероятность), то на выход элемента 21 ИЛИ
664185 эана только с одним преобразователем код-вероятность . Подобная структура блока 6 позволяет одновременно читать из памяти три числа.
Таким образом, введение в схему генератора дополнительно двух преоб.5 разователей код-вероятность, поэволило формировать в каждом такте сразу два разряда числа, что повышает быстродействие всего генератора по 60 сравнению с известным в два раза.
Заметим, что для работы второго и третьего преобразователей код
t 65 единичный символ с выхода второго преобразователя 14 код-вероятность пройдет через элемент,19 И. Если в первом разряде числа появился ноль, то единичный символ, вероятность по. явления которого равна Р (1/О), с выхода третьего преобразователя 15
5 од-вероятность пройдет через эле-, мент 20 И на выход элемента 21 ИЛИ, Таким образом, вероятность появления единичного символа на выходе
Ьлемента 21 ИЛИ зависит от значения первого разряда случайного числа, 10 йричем, если 14 = 1, то вероятность появления единицы на выходе коммутатора 16 равна Р (1/1), а если i< — — 0, то Р9(1/О). Здесь 1 значение (единица или ноль) первого разряда чис- 1.5 ла. Выходкой сигнал первого преобразователя 13 является управляющим .сигналом коммутатора 16.
Выходные сигналы преобразователя
13 и элемент 21 ИЛИ через соответствующие элементы И группы 8 элементов И пройдут на входы первого и второго разрядов регистра 9 соответственно. Заметим, что выход каждого элемента И группы 8 соединен с соответствующим разрядным входом регистра 9, Причем, на вторые входы элементов И группы 8 поступают управляющие сиг.налы с выходов дешифратора 4 номера такта, коммутируя таким образом в зависимости от номера такта элементы
И. Следовательно, в первом такте будут одновременно сформированы с нужными вероятностями сразу два старших разряда случайного числа.
Аналогично во втором такте будут одновременно сформированы третий и четвертый разряды случайного числа, в третьем такте — пятый и шестой разряды и т.д. Например, во втором такте из ЗУ одновременно будут считаны 40 константы РЗ (1/i< i ), Р (1/i„ i 1) и Р4 (1/i< 1 0), которые, поступят на входы первого, второго и третьего преобразователеЙ код-вероятность соответственно. Заметим, что в приведенном примере адресом ячейки ЗУ, в которой хранится нужная константа, является увеличенный на единицу цифровой код (14 1 ), который находится в первых двух разрядах регистра 9. Для простоты считаем, что блок 6 состоит из трех секций„ каждая иэ которых свя- 50 вероятность достаточно иметь один генератор раввномерно распределенных случайных чисел, который использует- ся в преобразователях 14 и 15 для одновременного формирования единичных символов с заданными вероятностями. Это возможно потому, что в каждый момент времени используется сигнал только с одного преобразователя (четырнадцатого или пятнадцатого) и, следовательно, взаимная корреляция потоков бернуллиевского типа с выходов названных преобразователей кодвероятность не играет роли. Последнее обстоятельство позволяет строить экономичные преобразователи кодвероятность .
Аналогично если число преобразователей код-вероятность увеличить до семи, то в каждом такте можно формировать сразу по три разряда случайного числа, если использовать пятнадцать преобразователей код-вероятность, то эа один такт можно получать по четыре разряда и т.д.
Поясним теперь как может быть сокращен объем блока 6 памяти.
Известно, что с ростом номера формируемого разряда случайного числа условные вероятности Р (1!,1 ..1. ) и
Р..(
Здесь ; (1 (111z..ë>„) и Р> (О/1>>>. 1>, ) соответственно вероятности йоявления в )-ом разряде числа единицы или нуля при условии, что (-1).-ые разряды числа содержат набор Ц1 ...i>.1 р ц 6 (0 1) двоичная цифра формируемого числа.
На основе названной выше закономерности в прототипе было предложено формировать по методу условных вероятностей только й1старших разрядов числа, а младшие разряды генерировать независимо друг от друга так, чтобы вероятность появления единиц в этих разрядах была равна 0,5.
Число m формируемых старших разрядов выбирают исходя иэ заданной точности генерирования случайных чисел, под которой понимают степень соответствия заданной плотности распределения f(у) плотности распределения f*(y), на реализацию которой фактически настроен генератор.
Другими словами число m определя-. ют иэ решения неравенства
Е=тах11(з)- Е» (ч )(ь.. (1) здесь 6 > — заданная погрешность аппроксимации плотности f(у) плотностью f* (y);
m — наименьшее целое число, при котором выполняется неравенство (1) .
Очевидно что с ростом m погрешность аппроксимации 8 стремится к ну лю.
7 ",664185
Заметим, что в прототипе для Фо1 мирования m старших разрядов числа требуется =Е2 =2 -(j=o констайт условной вероятности,и, следовательно, с ростом m число n резко возрастает.
Как было сказано выше, с ростом )
УсловиЯ веРоЯтности Р) (1/1, г., j g ) стремятся к 0,5, причем степень влия-10 ния (1 -1) -oro разряда (f> -1) на величину Р> (1/i„i>...1 1) тем меньше, чем больше (. Другими словами с ростом 1 корреляционная связь между соседними разрядами ослабевает. l5
Например, для нормальной плотности
К(З)= — ехр - .(г.:
61/24 2 6 г с параметрами trt> = О, f = 0,25 при
5 условные вероятности Р (1/1 1г1ф и Р (1/i, i i 0) отличаются друг от друга не более чем на 0,009 °
Отсюда приходим к выводу, что "вли-28 янием (1-1)-ого разряда при формировании ) --oio разряда можно пренебречь и вместо двух констант условной вероЯтноети P (1/111г... » j Z f ) и P) (1/1. 1г.. ... 11 г0) использовать одну средневэве- 30
til6HH KoHcTBHTy P> (1/1, (г ., i z ), которую можно определить по .Формуле
" ""1"
Р11j 1. g+
Г
1H(О(112 1 „2) ((1 2.. 1 0) (2) 40
Очевидно что использование одной константы Р (1/1 1 ...1<-Z) вместо двух позволит применять при формировании
1-ого разряда вдвое меньше число констант", чем в известном генераторе. 48
Но объединять константы условной вероятности можно не только понарно, а (если это допустимо) и по четыре, восемь и т.д., что позволяет значительно сократйть объем блока 6 памя- 50 ти без ущерба для качества генерирования случайных чисел.
Например, условную. вероятность
Р (1/1. г... 1 «f ),. которая необходйма для Формирования j- ого разряда и заменяет сразу четыре константы вида P (1/111 ... 1..() можно определи ь
rio формуле
Р)(1 1 2 " J 3)
-Р -2(". l1 f" г "14-э}Р (+112 "" -з" }»
+Р г (ОI111z..." з)Р (1 t 112 1 з ) 8
Здесь условные вероятности 1И112 1 31)ИР (»11 1 1 .o) находятся по формуле (2).
Аналогичнб определяется условная вероятность Pj (1/111 ... 1 ) и т.д.
Уменьшение числа констант реализуется следующим образом. В блок 6 памяти записывается сокращенно число констант, которые в определенные моменты времени, задаваемые генератором
5 тактовых импульсов, поступают на вход второго преобразователя 14 кодвербятность . Случайный поток с выхода преобразователя 14 через элементы
18 И и 21 ИЛИ поступает на входы группы 8 элементов И. Элемент 18 И открыт только в течение тех тактов (это обеспечивается управляющими сигналами с
- выхода дешифратора 4 номера такта),для которых было проведено сокращение констант. Первый преобразователь 13 кодвероятность работает обычным обра. зом, с той лишь разницей, что при формировании соответствующего разряда может использоваться меньшее число констант, На вход третьего преобразователя код-вероятность константЫ условной вероятности не поступают т.к. соответствующий блок памяти отсутствует "й, следовательно, на выходе преобразователя 15 единичный символ появиться не может (третий преобразователь код-вероятность при этом практически не используется, т.к. ой необходим только при формироваиии самых старших разрядов числа). Поэтому в частном случае можно данный генератор строить только на основе двух преобраэователей код-напряжение (третий преобразователь из схемы, приведенной на фиг.l исключить). Увеличение быстродействия в этом частном случае достигается за счет того, что
При больших « (для которых было приведено сокращение констант) генерируется в каждом такте сразу два разряда числа с помощью преобразователей 13 и 14, При малых j в каждом такте формируется только один разряд числа с помощью преобразователя 13. Этот частный случай является промежуточным между схемой известного генератора и, схемой, приведенной на фиг.l. Заметим, что если увеличение быстродействия, достигаемое эа счет введения в схему устройства только .второго . преобразователя 14 код-вероятность достаточно для практических целей, то третий преобразователь 15 кодвероятность, а также элементы 12, 17, 19, 20, 21 можно из схемы фиг.1 убрать, как неиспользуемые в этом частном случае.
Проведем сравнение предлагаемого генератора и известного.
В таблицах 1 и 2 приведены значения погрешности аппроксимации Р"=пюВ И(у)-P Cs)f и объема (n) блока па9 . - 664185 10 мяти в зависимости от числа (m) фор- юч= О, 8 = 0,25 для прототипа и пред мируемых старших разрядов для нормаль- полагаемого устройства соответстной плотности f(у) с параметрами венно.
Таблица 1
0„03025 0,01518 0,0077
31 63 127 255
0,1198 и 15
Таблица2
7 ) 8
Е1
0,06958 0,03236 0,02089 0,00897 n 23 47 55 1)1
Из сравнения таблиц 1 и 2 видно, что для достижения примерно одинаковой точности аппроксимации плотности распределения f(v) при использовании 25 предлагаемого устройства требуется меньший объем памяти и, чем при ис. пользовании прототипа.
Иапример, если генерировать восемь старших разрядов (III=8) то при исполь-л зойании предлагаемого устройства:необходимо иметь блок памяти объемом 111 ячеек (п=111), что обеспечит получение случайных чисел, плотность распределения f*(у) которых будет отличаться от нормальной плотности f(у) не более, чем на = 0,00897. Заметим, что на получение каждого числа в рассматриваемом случае требуется всего четыре такта работы генератора (в каждом такте формируется два разряда 40 числа).
Аналогичные характеристики известного генератора при rn = 8 равны соответственно и = 255 и Я = 0,0077, а
На получение каждого числа расходует- 45 ся восемь тактов работы генератора.
Таким образом, данный генератор позволяет не только увеличить скорость формирования случайных чисел, но и значительно уменьшить объем ria- 50 мяти (сократить оборудование) без заметного ущерба для качества генерирования случайных чисел.
Обратим внимание также на то, что метод условных вероятностей, положенный в основу при построении предлагаемого устройства, обладает известным преимуществом по сравнению с методом логарифмического перебора, на базе которого построен один иэ аналогов. Это преимущество заключается в том, что для некоторых законов распределения например, для показательного с плотностью f(у)=Ле, веро-лч ятность появления единицы в -ом разряде не зависит от значения ос; 65 тальных (j-1) -ых разрядоВ числа, Для реализации таких законов по методу условных вероятностей требуется всего m констант (ячеек памяти), а не 2 -1, как в названном аналоге.
Остановимся на некоторых особенностях работы предлагаемого устройства.
Второй вход 23 устройства предназначен для записи в блок б констант условной вероятности.
Первый вхОд 22 устройства необходим для записи кода закона распределения в регистр 1.
Предполагается, что кроме закона распределения, заранее подсчитанные константы которого хранятся в блоке памяти, генератор может реализовать, так называемые, фиксированные законы.
Под фиксированными законами понимаются наиболее часто используемые„ законы распределения (нормальный, показательный и т.д.), константы условных вероятностей котбрых схемным путем реализованы в устройстве.
Это делается для удобства применения устройства, т.е. генератор заранее настроен на реализацию определенного набора законов расПределения и потребителю нет необходимости самому записывать в память константы условной вероятности.Заметим, что если генератор реализует только фиксированный набор законов, тр блок 6 не используется и его можно исключить иэ схемы фиг.1.
Фиксированные законы реализуются следующим образом. Каждый выход дешифратора 7 кодовых комбинаций связан с соответствующей ему группой логических элементов ИЛИ, причем, соединение выхода дешифратора 7 с 1-ым элементом ИЛИ группы будет только в том случае, если в 1-ом разряде константы P (1/1„1 ... 1„ „ ) находитll
664185 12 ся единица, в противной сл ом случае наз- регистр первых разрядов случайных ванная связь отсутствует. чисел, разрядные выходы которого явяапример. ппя
Н р р . пп нормального за- ляются выходами генератора, первый кона распределения с параметра» преобразователь код-нероятность ми а =О, 6 =0,25 константа Р (1) = счетчик тактовых импульсов, вход коt
4 3 в двоичной системе счисле- торого подключен к первому выхо ния имеет вид P (1) и а н выходу
0,000010111010001 т генератора тактовых импульсов дешйф.е. единицы на- ратор номера такта, входы которого
Ф ходятся в 5 7 8 9 11 и 5l5-ом разря- соединены с разрядными выходами счета *оных импульсов, регистр кодах., Следовательно, первый выход де- чика тактовы шифратора 7 будет соедийен- со входа- да закона Распределения, вход котороми 5,7,8,9,11 и 15-го элементов ИЛИ ro по ключе первой группы 10 элеме д чен к первому входу генерато« элементов ИЛИ. Вы- l0 Ра, дешифратор кода закона . Распредеход каждого элемента ИЛИ г ппы группы ления, входы которого соединены с разсоединен с соответств ующим ему (с рядными выходами регистра кода закотем же.индексом) разрядным входом на распределения, а выходы — со вхопреобразователя ко -ве д-вероятность. дом генератора тактовых импульсов, Аналогично схемным путем прошива- (5 группу элементов И-, выходы которых ются и остальные константы ные к нстанты. Таким . подключены к разрядным входам регисттов образом, с помощью логических элемен- ра первых разрядов случайных ч се
ИЛИ задаются константы условных первая и вторая группы входов — к выи л,а вероятностей. ходам дешифратора номера такта и к
Заметим, что уменьшение числа выходу первого преобразователя кодконстант по методу описанному вьме ведет к уменьшению количества логи- ратор кодовых комбинаций, входы кото- ческих элементов (объема оборудова- рого соединены с разрядными выходами ния) в первой, второй и третьей груп- Регистра первых разрядон случайных . пах логических элементов ИЛИ. Более
25 чисел с выходами деш фр
I дешифратора кода того, объем оборудования в названных :закона распределения ешиф группах логических элементов ИЛИ номерка такта и с вторым вы вторым выходом генеможно минимизировать с помощью из-, Ратора тактовых импульсов соответстI вестных методов минимизации переклю- венно блок памяти, памяти, входы которого чательных Функций.
30 соединены со вторым срым входом генератоПерестройка данного генератора с Ра с разрядными выходами регистра реализации одного Фиксированного за- первых РазРядов случайных чисел, с кона распределения на реализацию выходами дешифратора ном р а номера такта и другого закона происходит путем за- с третьим выходом ге дом генератора тактонесения кода нового закона распреде- вых импульсов соответственно, о тле«ния на регистр 1. Дешифратор 2 ко- 5 л и ч а ю щ и и да закона распределения переключит целью повышения быстр ия ыстродействия геиевыходы дешифратора 7 кодовых комбина- РатоРа, он содержит коммутатор, втоций так чтобы на входы всех трех,рой и третий преобразователи кодгрупп элементов ИЛИ стали поступать веРоятность первую
I ю вторую и треновые константы условной вероятности. 40 тью грУппы элементов ИЛИ входы коГенератор 5 тактовых импульсов торых соединены с выходами дешифраобеспечивает синхронную работу всех тора кодовых комбинаций и с выходаблоков устройства. ми блока памяти соответственно, а
В данном генераторе младшие раз- выходы подключены в разрядным вхо— ряды случайного числа (так же как и дам первого, второго и третьего преВ прототипе) формируются с вероят- обраэователей код-вероятность, ностью появления единицы в этих раз- 45 соответственно, тактовые входы которядах равной 0,5,(на схеме фиг.l Рых объединены и подключены к четверблок формирования младших разрядов тому выходу генератора тактовых имне приведен) . пульсовр выход коммУтатора соединен
Использование новых элементов — с третьей гРУппой входов группы эле логйческим элементов ИЛИ, второго 50 ментов И, а нходы его подключены к и третьего преобразователей код-веро- выходам дешйфратора номера такта и ятность, переключателя, выгодно отли-,к выходам первого, второго и третьечает предлагаемый генератор случайных го преобразователей код-вероятчйсел от указанного прототипа, так ность, соответственно. как йозволяет увеличить быстродейст- 55 вие и у«простить.конструкцию запоми- Ис гочники информаций, принятые во
" нающего устройства. внимание при экспертизе
1. Авторское свидетельство СССР
9 213424, кл. G 06 F 1/02, 1967.
ФормУла изобретения б(2. Авторское свидетельство СССР
9 309356, кл . G Об F 1/02, 1969.
Генератор случайных чиселу содер- 3. Авторское свидетельство СССР жаций генератор тактовых импульсовф 85 9 185569 кЛ. G 06 F 1/02 1965 кл е
6641,85
3i-1 у4 угttr
Фиг. 2
Составитель A. Карасов
Редактор Б.Герцен Техред Н. Бабурка Корректор M. Вигула
Заказ 3003/47 Тираж 668 Подписное
ЦИИИПИ Государственного комитета СССР по делам изобретениЯ и открытий
113035, Москва, Ж-35, Раушская наб.,д.4/5
Филиал ППП Патент,, г.ужгород, ул.Проектная,4
