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

(61) Дополнительное к авт, саид-ву(22) Заявлено 210277 (21) 2454570/18-2 исоединением 0 07 С 15/О 0 06 Р 1/О и йо Госуварствеииый кои итет СССР ио деаам изобретений и открытий(54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕ Изобретен вычислительн применение и ровании в ци . числительныхИзвестны сел с задан к обл может ском анны ие относитсой техникири статистифровых злекмашинах.генераторыыми закона сти найтимоделислучайных чин ми распределения.Один из известных генераторов содержит датчик равномерно распределенных чисел, запоминающее устройство, схемы параллельного сравнения чисел, триггеры, схемы совпадения, выходное устройство и позволяет получать случайные числа эа один такт работы датчика, но имеет высокую сложность 1).Другой из известных генераторов содержит генератор равномерно распределенных случайных чисел, схему сравнении, запоминающее устройство, блбк логарифмического перебора, генератор тактовых импульсов н имеет низкое быстродействие, так как в каждом- Факте работы датчика формируется только один разряд случайногочисла (2).Наиболее б технической сущности реше ному изобретению являетс р случайных 25 лизким по наем к дан я генерато О(7) Заявитель казански ого Красноо Знамени авиационныйим. А,Н. Туполева чисел, содержащий генератор тактовых импульсов, регистр первых разрядов случайныхчисел, разрядные выходы которого являются выходами генератора, первый преобразователь 1 кодвероятность 1, счетчик тактовых им пульсов, вход которого подключен к первому выходу генератора тактовых импульсов, дешифратор номера такта, входы которого соединены с разрядными выходами счетчика тактовых импульсов, регистр кода закона распределения, вход которого подключен к первому входу генератора, дешифратор кода закона распределения, входы которого соединены с разрядными выходами регистра кода закона распределения, а выходы - со входом генератора тактовых импульсов, группу элементов И, выходы которых подключены к разрядным входам регистра первых разрядов случайных чисел, а первая и вторая группы входов - к выходам дешифратора номера такта н к выходу первого преобразователя кодвероятностьф, соответственно, дешифратор кодовых комбинаций, входы которого соединены с разрядными выходами регистра первых разрядов случайных чисел, с выходами дешифратора кодазакона распределения, дешифратораномера такта и со вторым выходом генератора тактовых импульсов соответственно, блок памяти, входы которогосоединены со вторым входом генератора, с разрядными выходами регистрапервых разрядов случайных чисел, свыходами дешифратора номера такта ис третьим выходом генератора тактовыхимпульсов соответственно (3).Известный генератор, реализующийметод условных вероятностей, облада- фет низким быстродействием так какв каждЬм такте работы, генератора фор. мируется только один старший разрядслучайного числа.Целью изобретения является повыше ние быстродействия генератора случайных чисел,Поставленная цель достигается тем,что генератор содержит коммутатор,второй и третий преобразователи код 9)вероятностьф; первую, вторую и третью группы элементов ИЛИ, входы которых соединены с выходами дешифраторакодовых комбинаций и с выходами блокапамяти соответственно, а выходы подключены к разрядным входам первого,второго и третьего преобразователейкод-вероятность, сооТветственно,тактовые входы которых объединеныи подключены к четвертому выходу генератора тактовых импульсов, выходкоммутатора соединен с третьей группой входов группы элементов И, авходы его подключены к выходам дешифратора номера такта и к выходам первого,второго и третьего преобразователей 5код-вероятность, соответственно.Блок-схема генератора приведенана фиг. 1. Фиг. 2 иллюстрирует методприближения заданной плотности Г (у)плотностью Г (у),40Генератор содержит регистр 1 кодазакона распределения, дешифратор 2кода закона распределения, счетчик3 тактовых импульсов, дешифратор 4номера такта, генератор 5 тактовых 45импульсов, блок б памяти, дешифратор7 кодовых комбинаций, группу 8 элементов И, регистр 9 первых разрядовслучайных чисел, группы 10, 11, 12элементов ИЛИ, преобразователи 13,14,15 код-вероятность, коммута-.тор 16, элемент 17 НЕ, элементы 18,19,20 И, элемент 21 ИЛИ,входы 22,23генератора и выходы 24 генератора.Вход регистра 1 кода закона распределения соединен с первым входом22 генератора, а раэрядныерыходы регистра 1 подключены ко входам дешифратора 2 кода зааона распределения,. выходы дешифратора 2 соединены совходами дешифратора 7 кодовых комбинаций и генератора 5 тактовых импуль-,совВход счетчика 3 тактовых импульсов подключен к одному иэ выходовгенератора 5 тактовых импульсов,другие выходы которого соединены со 65 входами блока б памяти, дешифратора 7 кодовых комбинаций, первого 13, вгорого 14 и третьего 15 преобразователей код-вероятность. Входы дешифратора 4 номера такта подключены к разрядным выходам счетчика 3 тактовых импульсов, а выходы дешифратора 4 соединены с управляющими входами дешифратора 7 кодовых комбинаций, группы 8 элементов И и коммутатора 16Выходы группы 8 элементов И соединены со входами регистра 9 первых разрядов случайных чисел, разрядные выходы которого подключены ко входам дЕшифратора 7 кодовых комбинаций, блока б памяти и к выходам 24 генератора. Входы блока б памяти соединеиы со вторым входом 23 генератора и с выходами дешифратора 4 номера такта. Входы первой 10, второй 11, третьей 12 групп элементов ИЛИ подключены к соответствующим выходам дешиф ратора 7 кодовых комбинаций и блока б памяти, а выходы названных групп элементов ИЛИ соединены со входами первого 13, второго 14 и третьего 15 преобразователей код-вероятность", соответственно. Выхбды первого 13, второго 14 и третьего 15 преобразователей код-вероятность подключе. ны ко входам коммутатора 16, выходы которого соединены со входами группы 8 элементов И,а .на другие входы группы 8 элементов И подключены к выходу первого преобразователя 13 кодвероятность.Генератор работает .следующим образом.Пусть константы условной вероятности хранятся в блоке б памяти. В первом такте (такт работы генератора задается генератором 5 тактовых импульсов и счетчиком 3 тактовых импульсов) из блока 6 памяти считываются константы Р (.1), Р 2(1/1) н Р 2(1/О), которые поступают через группы элементов ИЛИ на входы первого, второго и третьего преобразователей код-вероятность, соответственно, где Р (1) - вероятность появления единицы в первом разряде формируемого случайного числаР(1/1) и Р(1/О) - условные веро, ятности появлейия единицы во втором, разряде случайного числа при условии, что в первом разряде числа имеется единица или ноль соответственно,В момент времени,задаваемый генератором 5 тактовых импульсов,сраба" тывают первый, второй и третий преобразователи,код-вероятность, на выходах которых единичные символы могут появиться с вероятностями Р. (1), Р (1/1) и Р (1/О) соответственно.Если в первом разряде формируемого случайного числа появилась единица (первый разряд числа формируется пер" вым преобразователем 13 код-вероятность), то на выход элемента 21 ИЛИединичный символ с выхода второго преобразователя 14 код-вероятность пройдет через элемент,19 И. Если в первом разряде числа появился ноль, то единичный символ, вероятность по. явления которого равна Р 2(1/0), с выхода третьего преобразователя 155 код-вероятность пройдет через эле-,мент 20 И на выход элемента 21 ИЛИ,Таким образом, вероятность появления единичного символа на выходе Ьлемента 21 ИЛИ зависит от значения первого разряда случайного числа, 10 буричем, если 1 = 1, то вероятность появления единицы на выходе коммутатора 16 равна Р(1/1) а если ( = О, то Р 2(1/О). Здесь (.( значение (единица или ноль) первого разряда чис, ла. Выходкой сигнал первого преобразователя 13 является управляющим .сигналом коммутатора 16.Выходные сигналы преобразователя 13 и элемент 21 ИЛИ через соответствующие элементы И группы 8 элементов И пройдут на входы первого и второго разрядов регистра 9 соответственно. Заметим, что выход каждого элеМента И группы 8 соединен с соответствующим разрядным входом регистра 9, Причем, на вторые входы элементов И группы 8 поступают управляющие сиг.налы с выходов дешифратора 4 номера такта, коммутируя таким образом в зависимости от номера такта элементы30И, Следовательно, в первом такте будут одновременно сформированы с нужными вероятностями сразу два старших разряда случайного числа.Аналогично во втором такте будут одновременно сформированы третий и четвертый разряды случайного числа, в третьем такте - пятый и шестой разряды и т.д, Например, во втором такте из ЗУ одновременно будут считаны 1 н константы РЗ (1/11 х), Р 4 (1/3. 1 1) и Р 4 (1/1110), которые, поступят на входы первого, второго и третьего преобразователеЙ код-вероятность соответственно. Заметим, что в приведенном примере адресом ячейки ЗУ, в которой хранится нужная константа, является увеличенный на единицу цифровой код (1, который находится в первых двух разрядах регистра 9. Для простоты считаем, что блок 6 состоит из трех секций каждая иэ которых свяэана только с одним преобразователемкод-вероятность. Подобная структура блока 6 позволяет одновременно читать из памяти три числа,Таким образом, введение в схемугенератора дополнительно двух преобразователей код-вероятность, поэволило формировать в каждом тактесразу два разряда числа, что повышает быстродействие всего генератора по 60сравнению с известным в два раза.Заметим, что для работы второгои третьего преобразователей код1 65 вероятность достаточно иметь одингенератор раввномерно распределенныхслучайных чисел, который использует-ся в преобразователях 14 и 15 дляодновременного формирования единичных символов с заданными вероятностями. Это возможно потому, что в каждый момент времени используется сигналтолько с одного преобразователя (четырнадцатого или пятнадцатого) и,следовательно, взаимная корреляцияпотоков бернуллиевского типа с выходов названных преобразователей фкодвероятностьф не играет роли. Последнее обстоятельство позволяет строить экономичные преобразователи кодвероятность,Аналогично если число преобразователей код-вероятностьф увеличитьдо семи, то в каждом такте можноформировать сразу по три разряда случайного числа, если использовать пятнадцать преобразователей код-вероятность", то эа один такт можно получать по четыре разряда и т.д,Поясним теперь как может бытьсокращен объем блока 6 памяти.Известно, что с ростом номераформируемого разряда случайного числаусловные вероятности Р (01 у) иР (06 ( 1 ) стремятся к безусловнойвероятности, равной 0,5, причем предельные свойства условных вероятностей начинают сказываться при небольших ,Здесь ;( 1 у л,) и Р (О/( ( "(,)соответственно вероятности йоявленияв 1-ом разряде числа единицы или нуля при условии, что ( -1).-ые разрядычисла содержат набор Ц 1" 1).1 р 1 6(01)двоичная цифра формируемого числаНа основе названной выше закономерности в прототипе было предложено формировать по методу условныхвероятностей только В старших разрядовчисла, а младшие разряды генерироватьнезависимо друг от друга так, чтобывероятность появления единиц в этихразрядах была равна 0,5.Число в формируемых старших разрядов выбирают исходя иэ заданнойточности генерирования случайных чисел, под которой понимают степеньсоответствия заданной плотности распределения Й(у) плотности распределения Е(у), на реализацию которойфактически настроен генератор.Другими словами число ш определя-.ют иэ решения неравенстваЕ=тах 1(.з)-(ч фе. (1)здесь 6 - заданная погрешностьаппроксимации плотности й(у) плотностью Й (у) 7щ - наименьшее целое число,при котором выполняется неравенство,06034 аблица 2 0,0089111 208 тальных (-1)-ых разрядоВ числа.Для реализации таких законов по методу условных вероятностей требуется всего в констант (ячеек памяти),а не 2 -1, как в названном аналоге.Остановимся на некоторых особенностях работы предлагаемого ус рой-ства,Л Второй вход 23 устройства предназначен для записи в блок 6 констант условной вероятности.Первый вход 22 устройства необходим для записи кода закона распределения в регистр 1Предполагается, что кроме законараспределения, заранее подсчитанныеконстанты которого хранятся в блокепамяти, генератор может реализовать,так называемые, фиксированные эакоПод Фиксированными законами понимаются наиболее часто используемыезаконы распределения (нормальный,показательный и т.д,), константыусловных вероятностей которых схемным путем реализованы в устройстве.Это делается для удобстВа применения устройства, т.е, генератор заранее настроен на реализацию определенного набора законов расПределенияи потребителю нет необходимости самому записывать в память константыусловной вероятности,- Заметим, что если генератор реализует только Фиксированный наборзаконов, тр блок 6 не используетсяи его можно исключить иэ схемы фиг.1,Фиксированные законы реализуютсяследующим образом. Каждый выход дешифратора 7 кодовых комбинаций связанс соответствующей ему группой логических элементов ИЛИ, причем, соединение выхода дешифратора 7 с 1-ымэлементом ИЛИ группы будет тольков том случае, если в 1-ом разрядеконстанты Р (1/111) находитИз сравнения табчто для достижениявой точности аппрокраспределения Е(у)предлагаемого устроменьший объем памят. пользовании прототиИапример, еслистарших разрядов (зованни предлагаемобходимо иметь блоячеек (п=111), чтоние случайных чисепределения й(у) кчаться от нормальнне более, чем начто на получение ксматриваемом случачетыре такта работкаждом такте Формнчисла),лиц 1 и 2 видно, примерно одинакосимации плотности при использовании йства требуется и и, чем при испа.енерировать восемь п 1=8) то при исполього устройства:йепамяти объемом 11 обеспечит получел, плотность расоторых будет отлиой плотности Е(у)0,00897. Заметим аждого числа в рас" е требуется всего ы генератора (в руется два разряда т 35 вестсоот Аналогичные характеристики иэ ного генератора при п = 8 равны ветственно и = 255 и Е = 0,0077, а на получение каждого числа расходует ся восемь тактов работы генератора.Таким образом, данный генератор позволяет не только увеличить скорость Формирования случайных чисел, ио и значительно уменьшить объем па мяти (сократить оборудование) без заметного ущерба для качества генерирования случайных чисел.Обратим внимание также на то, что метод условных вероятностей, поло женный в основу при построении предлагаемого устройства, обладает известным преимуществом по сравнению с методом логарифмического перебора, на базе которого построен один иэ аналогов. Это преимущество заключается в том, что для некоторых законов распределения например, для показательного с плотностью й(у)=Ле , веро-лч ятность появления единицы в -ом разряде не зависит от значения ос; 65 9 ,664185 10мяти в зависимости от числа (в) Фор- вч= О, 3= 0,25 для прототипа и предмируемых старших разрядов для нормаль- полагаемого устройства соответстной плотности й(у) с параметрами венно.11664185 12ся единица, в противной случае наз- регистр первых разрядов случайныхванная связь отсутствует, чисел, разрядные выходы которого явНапримеН р р. Для нормального за- ляются выходами генератора, первыйкона распределения с параметра преобразователь код-вероятность,ми в=О, 6=О, 25 константа Р (1) ==0 045438 в в исчетчик тактовых импульсов, вход кония имеет ви Р (1) и,045438 в двоичной системе счисле- торого подключен к первому вывыходу0,000010111010001 тет вид Р(1) и Равна генератора тактовых импульсов дешйфт.е, единицы на-ратор номера такта, входы которого5Фходятся в 5 7 8 9 11 и 15-ом разря-соединены с разрядными выходами счетх импульсов, регистр кодах., Следовательно, первый выход де- чика тактовых им ушифратора 7 будет соедийен- Со входа- да закона распределениния, вход которопервой группы 10 элеи -го элементов ИЛИ го подключен к первому входу генератомейтов ИЛИ. Вы- О Ра, дешифратор кода закона. Распредеход каждого элемента ИЛИ группы ления входы которогосоединен с соответствующим ему ( с рядными выходами регистра кода закотем же индексом) разрядным входом на распределения, а выходы - со вхопреобразователя код-вероятность, дом генератора тактовых импульсов,Аналогично схемным путем прошива группу элементов И, выходы которыхются и остальные константы. Таким подключены к разрядным входам регистобразом, с помощью логических элемен- ра первых разрядов случайных чисел,атов ИЛИ задаются константы условных первая и вторая группы входов - к вы. вероятностей. ходам дешифратора номера такта и кЗаметим, что уменьшение числа выходу первого преобразователя кодконстант по методу описанному выше вероятность, соответственно, дешифведет к уменьшению количества логи- ратор кодовых комбинаций, входы коточеских элементов (объема оборудова- рого соединены с разрядными выходаминия) в первой, второй и третьей -груп- РегистРа первых разрядов случайныхпах логических элементов ИЛИ. Более25чисел с выходами дешифр тРтого, объем оборудования в названных закона распределения, дешифраторагруппах логических элементов ИЛИ номера такта и с вторым ывторым выходом генеможно минимизировать с помощью из-, Ратора тактовых импульсов соответствестных методов минимизации переклю- венно блок памяти, вти, входы которогочательных Функций,30соединены со вторым входом генератоПерестройка данного генератора сра, с разрядными выходами регистрареализации одного фиксированного за- первых разрядов случайных чисел, скона распределения на реализацию выходами дешифратора на ора номера такта идругого закона происходит путем за- с третьим выходом генергенератора тактонесения кода нового закона распреде- вых импульсов соответственно, о тления на регистр 1. ДешиФратор 2 ко л и ч а ю щ и й с ятем, что, сда закона распределения переключит целью повышения быстро йя ыстродействия геиевыходы дешифратора 7 кодовых комбина- Ратора, он содержит коммутатор, втоций такчтобы на входы всех трех ,рой и третий преобразователи фкодгрупп элементов ИЛИ стали поступать веРоятность, первую, вторую и треновые константы условной вероятности, 40 тью грУппы элементов ИЛИ входы коГенератор 5 тактовых импульсов торых соединены с выходами дешифраобеспечивает синхронную работувсех .тора кодовых комбинаций и с выходаблоков устройства. ми блока памяти соответственетственно, аВ данномгенераторе младшие раз- выходы подключены в разрядным вхо-ряды случайного числа (так же как и дам первого, второго и третьего преВ прототипе) Формируются с вероят- обраэователей шкод-вероятность 1," " ностью появления единицы в этих раз соответственно, тактовые входы которядах равной 0,5 ,(на схеме Фиг.1Рых объединены и подключены к четверблок Формирования младших разрядов тому выходу генератора тактовых имне приведен) . пульсов, выход коммутатора соединенИспользование новых элементов - с тРетьей группой входов группы злелогйческиХ элементов ИЛИ, второго 50 ментов И, а входы его подключены кИ тРетьего преобразователей код-веро- выхоДам дешйфратора номера такт ия ность, переключателя, выгодно отли- к выходам первого, второго и третьета акта иЧает предлагаемый генератор случайных го преобразователей код-вероятчйсел от указанного прототипа, так ность, соответственно.как йозволяет увеличить быстродействке и упростить. конструкцию запоми- Исгочники информаций, принятые во" нающего устройства.внимание при экспертизе1. Авторское свидетельство СССР9 213424, кл. О Об Г 1/02, 1967.Формула изобретения 2. Авторское свидетельство СССРГенератор случайных чисел, содер. Авторское свидетельство СССРжаций генератор тактовых импульсов 81 9 185569, кл, 0 Об р 1/02, 1965664185 Составитель Ь. КарасовТехред Н. Бабурка Корректор М, Вигул3 Редактор Б,Г ПодписСССР каз 3003 1130 лиал ППП Патент г.ужгород, ул.Проектная,Тираж ЦИИИПИ Государственн по делам изобретени Москва, Ж, Рау