Генератор случайных чисел Советский патент 1979 года по МПК G07C15/00 G06F1/02 

. V Изобретение относится к области вычислительной техники и может найт применение при статистическом модел ровании В цифровых электронных вычислительных машинах. Известны генераторы случайных чи сел с заданными за-конами распределе ния. Один из известных генераторов со держит датчик равномерно распределенных чисел, запоминающее устройст во, схемы параллельного сравнения чисел, триггеры, схемы совпадения, выходное устройство и позволяет получать случайные числа за один такт работы датчика, но имеет высокую сложиость 1. .Цругой из известных генераторов содержит генератор равномерно распределенных случайных чисел, схему сравнения, запоминающее устройство, блОй логарифмического перебора, генератор тактовых импульсов и имеет низкое быстродействие, так как в каждом Тактеработы датчика формиру ется только один разряд случайного числа 21. Наиболее близким по технической сущности решением к данному изобретению является генератор случайных чисел, содержащий генератор тактовых импульсов, регистр первых разрядов случайных чисел, разрядные выходы которого ЯВЛЯЮТСЯ выходами генератора, первый преобразователь кодвероятность, счетчик тактовых им пульсов, ВХОД которого подключен к первому ВЫХОДУ генератора тактовых импульсов, дешифратор номера такта, ВХОДЫ которого соединены с разряд- . нымй выходами счетчика тактовых импульсов, регистр кода закона распределения , вход которого подключен к первому ВХОДУ генератора, дешифратор кода закона распределения, входаа которого соединены с разрядными выходамирегистра кода закона распределения, а ВЫХОДЫ - со ВХОДОМ генератора тактовых импульсов, группу элементов И, выхода которых подключены к разрядным рвходам регистра первых разрядов случайных чисел, а первая и вторая группы входов к выходам дшмфратора номера такта и к выходу первого преобразователя кодвероЯтность , соответственно, до1Шфратор КОДОВЫХ комбинаций, входы которого соединены с разрядными выходами регистра первых разрядов случайных чисел, с выходами дешифратора кода закона распределения, дешифратора номера такта и со вторым выходом генератора тактовых импульсов соответственно, блок памяти, входы которого соединены со вторым входом генератора, с разрядными выходами регистра первых разрядов случайных чисел, с выходами дешифратора номера такта и с третьим выходом генератора тактовы импульсов соответственно 3. Известный генератор, реализующий метод условных вероятностей, обладает низким быстродействием, так как в каждом такте работы, генератора фор мируется только один старший разряд случайного числа. Целью изобретения является повыше ние быстродействия генератора случай ных чисел. Поставленная цель достигается тем что генератор содержит коммутатор, второй и третий преобразователи ко вероятность , первую, вторую и третью группы элементов ИЛИ, входы кото рых соединены с выходами дешифратора кодовых комбинаций и с выходами блок памяти соответственно, а выходы подключены к разрядным входам первого, второго и третьего преобразователей код-вероятнохзть , соответственно, тактовые входы которых объединены и пбЬключены к четвертому выходу генератора тактовых импульсов, выход коммутатора соединен с третьей группой входов группы элементов И, а входы его подключены к выходам дешиф ратора номера такта и к выходам перво го, второго и третьего преобразователе код-вероятность, соответственно. Блок-схема генератора приведена на фиг. 1. Фиг, 2 иллюстрй руёт метод приближения заданной плотности f (у) Плотностью f (у). Генератор содержит регистр 1 кода закона распределения, дешифратор 2 кода закона распределения, счетчик 3 тактовых импульсов, дешифратор 4 номера такта, генератор 5 тактовых импульсов, блок 6 памяти, дешифратор 7 кодовых комбинаций, группу 8 элементов И, регистр 9 первых разрядов случайных чисел, группы 10, 11, 12 элементов ИЛИ, преобразователи 13, 14,15 код-вероятность, коммутатор 16, элемент 17 НЕ, элементы 18, 19,20 И, элемент 21 ИЛИ,входы 22,23 генератора и выходы 24 генератора. Вход регистра 1 кода закона распределения соединен с первым входом 22 генератора, а разрядные(ВЫходы регистра 1 подключены ко входам дешифjpatopa 2 кода закона распределения, выходы дешифратора 2 соединены со входами дешифратора 7 кодовых комбинаций и генератора 5 тактовых импульсов. Вход счетчика 3 тактовых импульсов подключен к одному из выходов генератора 5 тактовых импульсов. другие выходы которого соединены со

664185 входами блока 6 памяти, дешифратора 7 кодовых комбинаций, первого 13, aVoрого 14 и третьего 15 преобразователей код-вероятность. Входы дешифратора 4 номера такта подключены к разрядным выходам счетчика 3 тактовых импульсов, а выходы дешифратора 4 соединены с управляющими входами дешифратора 7 кодовых комбинаций, группы 8 элементов И и коммутатора 16. Выходы группы 8 элементов И соединены со входами регистра 9 первых разрядов случайных чисел, разрядные выходы которого подключены ко входам дешифратора 7 кодовых комбинаций, блока 6 памяти и к выходам 24 генератора. Входы блока 6 памяти соединены со вторым входом 23 генератора и с выходами дешифратора 4 номера такта. Входы первой 10, второй 11, третьей 12 групп элементов ИЛИ подключены к соответствующим выходам дешифратора 7 кодовых комбинаций и блока 6 памяти, а выходы названных групп элементов ИЛИ соединены со входами первого 13, второго 14 и третьего 15 преобразователей код-вероятность-V соответственно. ВыхОды первого 13, второго 14 и третьего 15 преобразователей код-вероятность подключены ко входам коммутатора 16, выходы которого соединены со входами группы 8 элементов И,а,.на другие входы группы 8 элементов И подключены к выходу первого преобразователя 13 кодвероятность . Генератор работает .следующим о.браэом. Пусть константы условной вероятности хранятся в блоке б памяти. В первом такте (такт работы генератора задается генератором 5 тактовых импульсов и счетчиком 3 тактовых импульсов) из блока 6 памяти считываются константы Р (1) , Р2(1/1) и Pjd/O), Которые поступают через группы элементов ИЛИ на входы первого, второго и третьего преобразователей код-вероятность, соответственно, где Р.у (1) - вероятность появления единицы в первом разряде формируемого случайного числа; ) и Pgd/O) - условные веро-, ятности появления единицы во втором , разряде случайного числа при условии, что в первом разряде числа имеется единица или ноль соответственно. В момент времени,задаваемый генератором 5 тактовых импульсов,срабатывают первый, второй и третий преобразователи /код-вероятность , на выходах которых единичные символы могут появиться с вероятностями Р (1), Pgfl/l) и ) соответственно. Если в первом разряде формируемого случайного числа появилась: единица ( разряд числа формируется первым преобразователем 13 код-вероятность) , то на выход элемента 21 ИЛИ

5

единичный символ с выхода второго преобразователя 14 код-вероятность пройдет через элемент,19 И. Если в. первом разряде числа появился ноль, То единичный символ, вероятность почвления которого равна ), с хода третьего преобразователя 15 код-вероятность пройдет через элеteHT 20 И на выход элемента 21 ИЛИ, Таким образом, вероятность появ1ения единичного символа на выходе Элемента 21 ИЛИ зависит от значения hepBoro разряда случайного числа, йричем, если i 1, то вероятность hoявлeния единихда на выходе коммутагора 16 равна Pgd/l), а если -1 О, го PQ(I/O). Здесь 1 значение (единица или ноль) первого разряда числа. Выходной сигнал первого преобразователя 13 является управляющим сигналом коммутатора 16.

Выходные сигналы преобразователя 13 и элемент 21 ИЛИ через соответствующие элементы И группы 8 элементов И пройдут на входы первого и второго разрядов регистра 9 соответствено. Заметим, что выход каждого элемента И группы 8 соединен с соответствующим разрядным входом регистра 9 Причем, на вторые входы элементов И группы 8 поступают управляющие сигналы с выходов дешифратора 4 номера такта,коммутируя таким образом в зависимости от номера такта элементы И. Следовательно, в первом такте будут одновременно сформированы с нужными вероятностями сразу два старших разряда случайного числа. Аналогично во втором такте будут одновременно сформированы третий и четвертый разряды случайного числа, в третьем такте - пятый и шестой разряды и т.д. Например, вовтором такте из ЗУ одновременно будут; считаны

константы РЗ U/ij i) г 4 ) и Р (l/ijijO), которые поступят на входы первогб, второго и третьего преобразователей код-вероятность соответственно. Заметим, что в приведеном примере адресом ячейки ЗУ, в котрой хранится нужная константа, является увеличенный на единицу цифровой код (), который находится в первы двух разрядах регистра 9. Для простоты считаем, что блок 6 состоит из трех секций, каждая из которых связана только с одним преобразователем код-вероятность. Подобная структура блока 6 позволяет единовременно читать из памяти три числа.

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

Заметим, что для работы второго и третьего преобразователей код

664185

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

Аналогично если число преобразователей

код-вероятность

увеличить

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

Поясним Tenepib как может быть сокращен объем блока 6 памяти.

Известно, что с ростом номераJ формируемого разряда случайного числ условные вероятности PJ О ... i- ) и P-jfo/i i... Ij.) стремятся к безусловной вероятности равной 0,5, причем предельные свойства условных вероятностей начинают сказываться при небольших J .

Здесь РЗ (1/Vj.-.ij., и P.j(o/i,i2-.. i-j.,) соответственно вероятности появления в j-омразряде числа единицы или нуля при условии, что (1-1).-ые разряды числа содержат набор itij-.-ij./ ij €(0,1) двоичная цифра формируемого числа.

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

Число m формируемых старших разрядов выбирают исходя из заданной точности генерирования случайных чисел, под которой понимают степень соответствия.заданной плотности распределения f(yj плотности распределения f(y), на реализацию которой фактически .настроен генератор.

Другими словами число га определяют из решения неравенства

(ъ1|5е (l)

здесь jg - заданная погрешность аппроксимации плотности f (у) плотно

тью (у);

m - наименьшее целое число, при котором выполняется неравенство

(1).

Очевидно что с ростом m погрешность аппроксимации стремится к нлю. 7 , 1 Заметим, что в прототипе для фор мирования m старших разрядов числа требуется . т- J ( J-0 констант условной вероятности,и, следовательно, с ростом m число п резко возрастает. Как было сказано выше, с ростом условия вероятности PJ (l/itia...ij-i) ст1ремятся к 0,5, причем степень вли ния (j-l)-ого разряда (Ij-l) на вел чину (1/1 i.-.,) тем меньше, чем больше /. Другими словами с ростом корреляционная связь между соседним разрядами ослабевает. Например, для нормальной плотное ти (y)- -rexp/-i GVTT V 2 с параметрами itTyj О, 6 0,25 при j 5 условные вероятности Pfd/lVzi и Pg () отличаются друг от друга не более чем на 0,009, Отсюда приходим к выводу,чте вЙи янием {J-1)-огр разряда при формиро вании j-ot-o разряда можно пренебречь и вместо двух констант условной верр ЯТНОбТИ Р.- (l/1i2-- i J-2. 1 P|((2 ... ifiO) использовать одну средневзве щённую константу Pj ( .-ij-s которую можно определить по .. муле ) : -lO/i -v bOM-Va;) (ob 2---f2)P(i(VV2-id-2o) (2) Очевидно что использование однрй константы PJ {i/i.,12--- -2) вместр дву позволит применять при формировании д-ого разряда вдвое меньше число кон тант ,чбм и известном генераторе. Но объединять константы условной верря ностй можно не толькр попарно, а (еРли это допустимо) и по четыре, восемь и т.д., что позволяет значительно сократить объем блоКа б памяти бб|з увчёрба для качества генерирования случайных чисел. Например, условную вероятность PJ (l/iji.l. ij,/)/ которая необходима для формирования -ого разряда If заменяет сразу четыре крнстанты внДа Р (.-. ij--} ) можно определи по формуле PjC/Vr-W; - . I Vr--if 3)30IV2-d-3«h Pi-2(o/V2-V3)PiO/V2-b4o) (3) 5 Здесь условные вероятности i(VVr-b4)d(- V-V3o) находятся по формуле (2). Аналогично определяется условная вероятность Pj (,.. i, ) и т.д. Уменьшение числа констант реализуется следующим образом. В блок б памяти записывается сокращенно число констант, которые в определенные моменты времени, заДай аемые генератором 5 тактовых импульсов, поступают на вход второго преобразователя 14 кодвероятность . Случайный поток с выхода преобразователя 14 через элементы 18 И и 21 ИЛИ поступает на входы групП Ы 8 элементов И, Элемент 18 И открыт тбдько в течение тех тактов (это обеспечивается управляющими сигналами с выхода дешифратора 4 номера такта),для которых было проведено сокращение констант. Первый преобразователь 13 крдвероятность работает обычным образом, с той лишь разницей, что при формировании соответствующего разряда использоваться меньшее число констант. На вход третьего преобразователя код-вероятность Vконстанть условной вердятнЬсти не поступают,, т. к. соответствующий блок памяти отсутству ёт и, c.neSdBaTejibHO, на выходе преобразователя 15 единичный симврл появиться не может (третий преобразо- . ватель код-вероятность при этом практически не используется, т.к. оннеобходим только при формировании самых старших разрядов числа). Поэтому в частном случае можно данный генератор строить только на основе двух преобразователей код-напряжение (третий преобразователь из схемы, приведенной на фиг.1 исключить). Увеличение быстродёйстви.я в этом частном Случае достигается за счет того, что при больших J (для крторых было приведено сокращение констант) генерируется в каждом такте сразу два разряда числа с помощью преобразователей 13 и. 14. При малых j в каждом Такте формируется только один разряд числа с помощью преобразователя 13. Этот частный случай является промежуточным между схемой известного генератора и . схемой. Приведенной на фйг.1. Заметим, что если увеличение быстродействия, достигаемое за счет введения в рхему устройства трлько .второго преобразователя 14 код-вероятность дастаточно дйя практических целей, то третий преобразователь 15 кодвероятность , а также -элементы 12, 17, 19, 20, 21 можно из схемы фиг.1 брать, как неиспользуемые в этом частном случае. Проведем сравнение предлагаемого генератора и изв.естного. В таблицах 1 и 2 приведены значеия погрешности аппроксимации С max.fcfW)-f( и объема (п) блока па9 .664185iO

.Мити в зависимости от числа (т) фор- т о, Г 0,25 для прототипа и предмируемых старших разрядов для нормаль- полагаемого устройства соответстной плотности f(y) с параметрами венко. . .

.Таблица

Из сравнейия таблиц 1 и 2 видно, что для достижения примерно одинаковой точности аппроксимации ПЛОТНОСТИ распределения f(у) при использовании предлагаемого устройства требуется меньший объем памяти п , чем при использовании прототипа. Например, если генерировать восем старших разрядов () то при исполь зойании предлагаемого устройства /йеобходимо иметь блок памяти объемом 1 ячеек (), что обеспечит получение случайных чисел, плотность распределения f (у) которых будет отличаться от нормальной плотности f(у) не более, чем на 0,00897. Замети что на получение каждого числа в рас сматриваемом случае требуется всего четыре такта работы генератора (в каждом такте формируется два разряда числа). Аналогичные характеристики извест ного генератора при m 8 равны соот ветственно п 255 и 0,0077, а яа получение каждого числа расходует Ся восемь тактов работы генератора. Таким образом, данный генератор позволяет не только увели,чить скорость формирования случайных чисел, но и значительно уменьшить объем памяти (сократить оборудование) без заметного ущерба для качества генерирования случайных чисел. Обратим внимание также на то, что метод условных вероятностей, положенный в основу при построении предлагаемого устройст-эа, обладает известным преимуществом по сравнению с методом логарифмического перебора, н базе которого построен один из аналогов. Это преимущество заключается в том, что для некоторых законов рас пределения например, для прказательиогр с плотностью f{y), вероятность появления единицы в j-ом разряде не зависит от значения ос,,Т а б л и ц -а 2 тальных )-ых разрядов числа. Для реализаЦии- таких законов по методу условных вероятностей требуется всего m констант (ячеек памяти), а не , как в названном аналоге. Остановимся на некоторых особенностях работы предлагаемого устройства. Второй вход 23 устройства предназначен для записи в блок б констант условной вероятности, Первый вход 22 устройства необходим для записи кода закона распределения в регистр 1. Предполагается, что кроме закона распределения, заранее подсчитанные константы которого хранятся в блоке памяти, генератор может реализовать, так называемые, фиксированные законьз. Под фиксированными законами понимаются наиболее часто используемые законы распределения (нормальный, показательный и т.д.), константы условных вероятностей которых схем- , ным путем реализованы в устройстве. Это делается для удобства применения устройства, т.е. генератор заранее настроен на реализацию определенного набора законов распределения и потребителю нет необходимости самому записывать в память константы условной вероятности. Заметим, что если генератор реализует только фиксированный Набор законов, то блок 6 не используется и его можно исключить из схемы фиг.1. Фиксированные законы реализуются следующим образом. Каждадй выход дешифратора 7 кодовых комбинаций связан с соответствующей ему группой логических элементов ИЛИ, причем, соединение выхода дешифратора 7 с i-ым элементом ИЛИ группы будет только в том случае, если в 1-ом разряде константы Р; (1/1,1.J... i,j ) находится единица, в противной случае названная связь отсутствует. Например. Для нормального закона распределения с параметрамиту 0, i(0,25 константа ) 0,045438 в двоичной системе счйсле Нйя имеет вид Р(1) и равна 0,000010111010001, т.е. единицы находятся в 5,7,8,9,11 и 15-ом разрядах. Следовательно, первый выход де шифратора 7 будет соединён со входа ми 5,7,8,9,11 и 15-го элементов ИЛИ первой группы 10 элеме1Гтов ИЛИ. Выход каждого элемента ИЛИ группы соединен с соответствуюгоим ему ( с тем же-индексом) разрядным входом преобразователя код-вероятность. Аналогично схемным путем прошива ются и остальные константы. Таким образом, с помощью, логических элеме тов ИЛИ задаются константы условных вероятностей. Заметим, что уменьшение числа констант по методу описанному выйе ведет к уменьшению количества логических эйёмёйтов (объема оборудования) в первой, второй и третьей пах логических элементов ИЛИ. Более того, объём оборудования в названных группах логических элементов ИЛИ можно минимизировать с помощью из-. вестных Методов мйнимнзацйи переклю чательных функций. Перестройка данного генератора с реализации одного фиксированного за кона распределения на реализацию другогб закона происходит путем занес эНйЯ кода нового закона распрёде лёния на регистр 1. Дешифратор 2 ко да закона распределения переключит выходы дешифратора 7 кодовых комбин ций, так,чтобы на входы всех трех rpj/iin элементов ИЛИ стали поступать нсэвые константы условной вероятности Генератор 5 тактовыз ; импульсов обеспечивает синхронйую работу всех блоков устройства., . В данномгенераторе мйадййе случайного числа (так же как и S прототипе) формируются с вероятностью появления единицы в этих разрядах равной 0,5 (на схеме фиг.1 блок формирования младших разрядов не приведен). Исполь зрвание новых элементов кизГ элементов ИЛИ, второго и третьего преобразователей код-веро ятность, переключателя, выгодно отличает предлагаемый генератор случайны Чисел от указанного йрототипа, так как позволяет увеличить быстродействне й упростить .конструкцию эапомийайв1ёгс1 устройства. Формула изобретения Генератор случайных чисел, содержавдий генератор тактовых импульсов, регистр первых разрядов случайных чисел, разрядные выходы которого являются выходами генератора, первый преобразователь код-вероятность, счетчик тактовых импульсов, вход которого подключен к первому выходу генератора тактовых импульсов, дешифратор номера такта, входы которого соединены с разрядными выходами счётчика тактовых импульсов, регистр кожа закона распределения, вход которого подключен к первому входу генератора, дешифратор кода закона распределения, входы которого соединены с разрядными выходами регистра кода закоka распределения, а выходы - со входом генератора тактовых импульсов, группу элементов И-, выходы которых подключены к разрядным входам регистра первых разрядов случайных чисел,а первая и вторая группы входов - к выходам дешифратора номера такта и к выходу первого преобразователя кодвероятность, соответственно, дешифратор кодовых комбинаций, входы которого соединены с разрядными выходами регистра первых разрядов случайных . чисел, с выходами дешифратора кода закона распределения, дешифратора HOMejJa такта и с вторым выходом генератора тактовых импульсов соответственно, блок памяти, входы которого соединены со вторым входом генератора, с разрядными выходами регистра первых разрядов случайных чисел, с выходами дешифратора номера такта и с третьим выходом генератора тактовых импульсов соответственно, о тл и ч а-ю щ и и с я тем, что, с целью повышения быстродействия генератора, он содержит коммутатор, второй и третий преобразователи кодвероятность, первую, вторую и третью группы элементов ИЛИ, входы которых соединены с выходами дешифратора кодовых Комбинаций и с выходами блока памяти соответственно, а выходы подключены в разрядным входам первого, второго и третьего преобразователей код-вероятность, соответственно, тактовые входы которых объединены и подключены к четвертому выходу генератора тактовых импульсов, выход коммутатора соединен с третьей группой входов группы элементов И, а входаг его подключены к выходам дешифратора номера такта и к выходам первого, второго и третьего преобразователей код-вероятностьсоответственно. Источники информации, принятые во нимание при экспертизе 1.Авторское свидетельство СССР 213424, кл. G 06 F 1/02, 1967. 2.Авторское свидетельство СССР В 309356, КЛ. G 06 F 1/02, 1969. 3.Авторское свидетельство СССР 185569, кл. G 06 F 1/02, 1965. /J i rCZHZ Н - 1 I J Ёи г fM,f(y)