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

(19) (11) 8738 151) С 06 Г ГОСУДАРСТВЕННЫЙПО ДЕЛАМ ИЗОБРЕТЕН МИТЕТ СССР ИЙ И ОТНРЫТИ ИСАНИЕ ИЗОБРЕТЕНИ ЕТЕЛ ТОРСИ л. 11 12А.И.Кузь)еч ехнический инсти.8)е свидетель06 Г 7/58,свидетельстОб Р 7/58,свидетельст06 Г 15/20,ство ССС1973.во СССР1974,во СССР1975 3. АвторскоеУ 488212, кл. 6(54) (57) ГЕНЕРАсодержащий генерпределенных слу ОР СЛУЧАЯ тор равно йных чисе ЧИСЕЛ, но расблок па.)1 378826, кл. О2. Авторское430368, кл. 6 мяти, о т л и ч а ю щ и й с я тем,что, с целью. упрощения и повышениянадежности, он содержит генератортак; овых импульсов, регистр сдвигаи сумматор, первый вход которого соединен с выходом генератора равномерно распределенных случайных чисел,вход которого объединен с тактовымвходом регистра сдвига и подключенк выходу генератора тактовых импульсов, выход регистра сдвига соединенсо своим входом "Установка", является выходом генератора и соединенс входом блока памяти, выход которого соединен с вторым входом сумматора, выход которого соединен с информационным входом регистра сдвига,управляющий вход которого являетсявходом "Пуск" генератора.1 ОИэобоетение относится к вычислительной технике и предназначено длягенерации потоков случайных чисел сзаданным законом распределения. Может быть использовано в качествеспецийпи зированного ст ахости чес кого блока, подключенного к вычислительным машинам общего назначения,а также в качестве задающего блокав имитаторах случайных процессов.Известен генератор случайных чисел, содержащий генератор равномерно распределенных чисел, схему сравнения, блок памяти, генератор тактов, специализированный дешифратор,регистр формирования случайного числа, входные и выходные, вентили. Устройство позволяет формировать потоки случайных чисел с требуемыми за 9конами. распределения по методу обратных функций с логарифмическимспособом перебоРа 11.Недостатком устроиства являетсяего сложность, в частности наличиеспециализированного дешифратора,Известно устройство для генерации случайных чисел с заданным зако-.ном распределения, содержащее мно-,гоканальный генератор случайных им-пульсных токов, схемы И, схему ИЛИ,вероятностный вентиль, регистр формирования случайного числа, схемы Ирегистра, устройство формированияадреса памяти и генератор-распределитель тактовых импульсов 2 .Недостатком устройства являетсяего сложность, в частности сложностьуправления,Наиболее близким по техническойсущности к предлагаемому являетсяустройство для вероятностного моделирования, содержащее блок управления, генератор равномерно распределенных чисел, вход которого соединен с первым выходом блока управления, блок сравнения, первый вход которого соединен с выходом генератора равномерно распределенных чисел,а второй вход " с вторым выходом блока управления, регистр адреса, разделенный на две части (старшую имладшую), первый вход которого соединен с первым выходом блока сравнения, а второй вход - с пятым выходом блока управления, блок памяти,вход которого соединен с выходом ре- .гистра адреса, регистр числа, первыйвход которого соединен с выходомблока памяти, а второй вход - с чет 08738 2вертым выходом блока управления, регистр маски, первйй,вход которогосоединен с выходом регистра числа,второй с вторым выходом блока сравнения, третий вход - с третьим выходом блока управления, первый выходсоединен с третьим входом блока сравнения, а второй выход с третьим входом реги стра адреса. Устройство по 16 з воляет формировать последовательности случайных чисел с .требуемымизаконами распределения. В устройстве реализуется метод обратныхфункций, основанный на сравнении1 З равномерно распределенных случайныхчиселсо значениями Г(х) воспро 1из води мой фун кци и р аспредел ения,отыскании интервала, для котороговыполняет ся у сло ви е( )(ср( +,и вы да че соот вет ст ау юще го дан номуинтервалу значения х. Перебор последовательно расположенных Г(х )125 логарифмический.Устрой ст во р абот ает по следующему алгоритму: блок управления вырабатывает команду, по которой генератор равномерно распределенных слуЗО чайных чисел формирует и передаетв блок сравнения случайное числоодновременно через регистр числа ирегистр маски из блока памяти в блоксравнения поступает группа значенийГ(х,), В результате сравнения в младшую част ь реги стра посту пает код. Поэтому коду из блока памяти выбираетсяи подается в блок сравнения очереднаягруппа значений Г(х,), после чегосодержимое младшей части регистрасдвигается и записывается следующийрезультат сравнения. Цикл сравнениядлится й 1 оя и тактов (Где В количество интервалов квантования воспроизводимого закона по области его существования, а - основание логарифмаперебора, а=2 , и - любое положительяное число), По коду, полученному врезультате сравнения, выбирается ячей.ка памяти, содержащая о, значений х;,из которой с помощью регистра маскивыбирается требуемое значение,Устройство позволяет моделировать2различных законов распределенийИ(где 0 - разрядность старшей частирегистра адреса). Информация о закс.нах располагается в 2 областях памяти. Выбрр требуемого закона осуществляется соответствующей адресаци.О М 20 2 30 35 40 4 3 10 ей с помощью старшей части регистра адреса 3.Недостатком устройства является сложность технической реализации изэа наличия блока управления и сложного составного регистра адреса, ограниченные воэможности программного управления из-за жесткого распределения поля памяти и относительно низкая надежность работы из-за сложных цепей управления, что является существенным, так как сбой и отказы стохастических блоков трудно различимы.Цель изобретения - упрощение устройства и повышение надежности работы.Для достижения поставленной цели в известный генератор случайных чисел, содержащий генератор равномерно распределенных случайных чюсел, блок памяти, вводится генератор тактовых импульсов, регистр сдвига и сумматор, первый вход которого соединен с выходом генератора равномерно распределенных случайных чисел, вход которого объединен с тактовым входом регистра сдвига и подключен к выходу генератора тактовых импульсов, выход регистра сдвига соединен со своим входом "Установка", является выходом генератора и соединен с входом блока памяти, выход которого соединен с вторым входом сумматора, выход которого соединен с информационным входом регистра сдвига, управляющий вход которого является .входом "Пуск" генератора.Упрощение устройства достигается эа счет того, что для формирования: адресов чтения памяти и дпя. формиро-вания случайного числа используется один регистр последовательных приближений, в прототипе для этих целей используется три регистра, причем регистр адреса является сложным (составным). Упрощение устройства достигается также за счет управления работой устройства сигналами с выхода регистра последовательных приближений, при этом отсутствует , специальный блок управления, Кроме того, все блоки устройства, за исключением генератора равномерно рас; пределенных чисел, существуют в ин 08738. 4 На чертеже приведена структурная схема устройства. Генератор содержит генератор 1 тактовых импульсов, генератор 2 рав номерно распределенных случайных чисел, сумматор 3, блок М памяти, регистр 5 сдви га.Генератор 1 тактовых импульсов предназначен для генерации регулярной последовательности импульсов синхронизации устройства, для его реализации можно использовать интегральную схему К 155 НГ 1Генератор 2 равномерно распределенных случайных чисел предназначен для формирования потока первичных равномерно распределенных случайных чисел, может быть использован любой из известныхпи.описанных в литературе.Сумматор 3 может быть выполнен на интегральных схемах К 155 ИПЗ и др, В качестве .регистра 5 последовательных приближений можно использовать регистр последовательных приближений .аналого-цифровых преобразователей (интегральная схема К 155 ИР 17), либо регистр сдвига типа К 155 ИР 1.Блок 4 памяти служит для хранения кодов, задающих законы распределения формируемых потоков случайных чисел, Для обеспечения- возможности формирования произвольных законов распределения необходимо применить оперативное запоминающее устройство. Если датчик случайных чисел ориентирован на формирование потока случай- ных чисел одногоили нескольких задан. ных законов распределения, можно применить постоянное запоминающее устрой ство. В интегральном исполнении существует большое количество элементов запоминающих устройств различной емкости и быстродействия.Рассмотрим работу устройства при использовании регистра последовательных приближений типа К 155 ИР 17, предназначенного для построения аналогоцифровых преобразователей. При этом вход 6 регистра 5 последовательных 50,приближений - информационный, вход 17 - синхронизации работы, вход 8 "разрешения работы, вход 9 - заданиярежима, причем вход 9 соединен с вы" гходом младшего, разряда.тегральном исполнении, что определяет простоту технической реализации устройства, его высокую надежность, компактность. Цикл формирования случайного числа начинается, когда в младшем разряде регистра 5 нуль и на вход 8 регистра поступает разрешающий сигнал.1 РОО 4 Р 01 10 41 5 100По заднему фронту очередного тактового импульса в старший разряд регистра последовательных приближенийзаписывается нуль, во все остальныеразряды - единицы. Из блока 4 памя"ти 4 считывается код и суммируетсясо случайным числом. С выхода переноса сумматора 3 на вход б регистра5 поступает значение первогоразряда формируемого случайного числа(нуль иди единица). По заднему фрон.ту следующего тактового импульсазначение первого разряда формируе",мого (случайного) числа принимаетсяв старший разряд регистра 5, нульиз первого разряда сдвигается вовторой, генератор 2 равномерно распределенных случайных чисел формирует новое случайное число,По сформированному на выходе регистра. 5 псследовательных приближенийновому адресу из блока 4 памяти считывается новый код, суммируется с новым случайным числом, по заднемуфронту следующего тактового импульсасформированный второй разряд выходного числа принимается во второй разряд регистра 5, нуль из второго разряда регистра 5 сдвигается в следующий (третий) разряд, генератор 2равномерно распределенных случайныхчисел формирует новое первичное слу-,чайное число. Последовательность описанных тактов идет до сдвига нуля вмладший разряд регистра 5. Нуль вмладшем разряде регистра 5 указывает, что число сформировано, поступаяна вход 9 регистра, разрешает установку начальногр состояния. Код сфор.мированного случайного числа находит.ся в регистре последовательных при-:ближений.Так как на первый вход 10 сумма"тора 3 поступают равномерно распре"деленные числа с интервалом от 0до 1-2", где И - разрядность сумматора, генератора 2 равномерно распределенных случайных чисел и блока памяти, вероятность единицы на вы"ходе переноса сумматора, вырабатываемой, если сумма чисел больше единицы, равна поступающему на второйвход 11 сумматора 3 коду из блокапамятиНа первом такте иэ блокапамяти читается код, равный вероятности попадания случайной величинывоспроизводимого закона распределения, во вторую половину области существования (вероятность единицыстаршего разряда формируемых чисел),На втором такте читается код, задающий условную вероятность попадания во вторую четверть, если первый сформированный разряд равен нулю, или в четвертую четверть, если сформированный первый разряд равенединице, т.е. задается условная вероятность единицы во втором разряде. На последующих тактах задаются в зависимости от полученных значений разрядов формируемого числаусловные вероятности попадания случайной величины в соответствующие1/2части области существования,где- номер такта, Например, еслина первых двух тактах получена комбинация 10, на третьем такте изблока памяти читается код условнойвероятности попадания случайной величины воспроизводимого закона рас"пределения в интервал от 5/8 до 6/8области существования.На каждом такте задаются условные вероятности, отсюда и название"Метод условных вероятностей",В табл, 1 показано расположениекодов условных вероятностей в блоке4 памяти для случая, если устройство формирует цетырехразрядные случайные числа, В каждой клетке табл.1слева указывается обозначение кодавероятности, справа - адрес ячейки,Нумерация адресов памяти с нуля.Верхний индекс в обозначении кодавероятности - результат, полученныйна предыдущих тактах,7 10087Если обозначить Р - вероятность М-й кодовой комбинации формируемых случайных чисел (1=О"2-1, где п 1- разрядность формируемых чисел), усйовнце вероятности Р вычисляются по формуле где 1=1 н Д=О"-1 г:2д 2а+1-1 аУстройство может формировать случайные числа и по методу обратных функций, для этого необходимо, чтобы 15 гейератор 2 равномерно распределен.Таблица 2 гс гд -9агагог -12 -1 Й тактового импульса содержимое ре 30 кгистра 5 последовательных приближе: ний сдвигается в сторону старших35 в, тановку регистра, т.е. устройствоможет начинать новый цикл фор.мирог -0 г -2 гг -бО 4 6 Г " В этом слу ч ае, как и в прот от ипе, осуществляется логарифмический перебор кодов вероятностей, если РК- требуемые вероятности .кодовых комбинаций. Как говорилось выше, в качестве регистра 5 данного генератора случайных чисел можно использовать регистр сдвига с возможностью параллельного занесения кода, типа существующего интегрального регистра К 155 ИР 17. При этом вход б регистра 5 последовательных приближений является входом последовательной записи регистра сдвига, вход 7 - синх-. ронизации сдвига, вход 8 - синхронизации параллельной записи, вход 9 - задания режима, соединенный со старшим выходом регистра,Цикл формирования случайного чис" ла начинается при поступлении на вход 8 импульса запуска, если в старшем разряде регистра 5 единица, При этом по входам параллельной за" писи в старший разряд записывается единица, во всех остальных - нули, На каждом такте формируется аналогично (как описано выше) один разряд выходного числа; по заднему фронту 36 8;ных случайных чисел формировал одночисло на весь цикл формирования выходного числа, а не новое на каждомтакте, Для этого. выходной регистргенератора 2 равномерно распределен"ных случайных чисел можно синхрони-зировать выходом мпадшего разрядарегистра 5, а не.импульсами генератора 1 тактовых импульсов. При этомв блок памяти последовательно записываются значения интегральной функции распределения ГК, начиная с нулевой ячейки, Расположение кодов вблоке памяти для случая формирования четырехразрядных случайных чиселпоказано в табл. 2.,разрядов, значение, сформированного разряда принимается в младший разряд регистра 5, формирование числа заканчивается при сдвиге единицы в старший разряд регистра 5. Единица на входе 9 регистра 5 последовательных приближений запрещает даЛьнейший сдвиг и разрешает начальную усвания числа.Единица с выхода старшего разряда регистра 5 является указателем готовности числа, сформированноечисло находится в регистре. Как и врвссмотренном выше случае, при использовании в качестве регистра 5последовательных приближений регистра сдвига, можно формировать алучайные числа как по методу условныхвероятностей, так и по методу обрат-ных функций, причем расчет кодовнастройки выполняется по тем же фор-мулам. Расположение кодов в памятипри методе условных вероятностейдля случая формирования четцрехраз-. рядных случайных чисел показано втабл, 3,Р" -3 9 Р -г ю юеооРц 11,Р -7 т гТаблицаиГ -26 ГвГ -13 ГгГ 14-15ю жГ "11 Иэ табл. 1-ь видно, что при методе условных вероятностей в случае использования регистра последователь- ЗО ных приближений набазе: регистра сдви" га, расположение кодов в памяти сов- падает с порядком их расчета, при методе обратных функций расположение кодов в памяти и порядок их расчета совпадают в случае использования регистра последовательных приближений, применяемэго в аналого-цифровых преобразователях. Если датчик случайных чисел используется совместно с ЭВМ, которая осуществляет расчет кодов настройки и их загрузку, при совпа". дении порядка расчета кодов и их разгрузке системе оказывается более эффективной, так как не требуется дополнительной перестановки кодов.Метод обратных функций отличается простотой процедуры расчета кодов настройки генератора случайных чисел и требует меньше исходных равномерно-распределенных случайных чисел, чем метод условных вероятностей, что позволяет применить менее быстродействующий и простой генератор 2 рав" номерно распределенных случайных чи 55 сел. Однако метод условных вероятностей обладает в общем более высокой точностью воспроизведения заданных законов распределения. Расположение кодов в памяти приметоде обратных функций для случая формирования четырехразрядных случайных чисел показано в табл. 4,При использовании в качестве регистра 5 регистра сдвига, предлагаемое устройство позволяет как и прототип, моделировать в режиме разделения времени несколько законов распределения, а также цепи Маркова различной связности, При этом по сравнению с прототипом предлагаемое уст- . ройство имеет более гибкое программное управление, позволяющее варьирование количеством воспроизводимых законов распределений и разрядностью случайных чисел, связностью цепей Маркова и количеством их состояний при постоянном объеме блока памяти и разрядности регистра последовательных приближений. Задание режима формирования требуемого распределения иэ группы распределений, информации о которых записаны в блок памяти, задание разрядности формруеиих чисел, сходности цепи Маркова и количества состояний осуществляется путем задания соответствующего кода начального состояния регистра последовательных приближенийВ табл. 5 показано расположение кодов вероятностей в блоке памяти при использовании метода условных вероятностей, при объеме блока памяти 16 ячеек, для случая моделирования двух законов распределения.тате тав тащившие те ещитв Р -10 Р "11 4 3 Р 12Р,13 Р,-14Р,-1тавав тт е ищи и ав витти тт ища Запрос на генерацию чисел первого закона распределения осуществля- О ется при записи в начале каждого цикла генерации в регистр последова" тельных приближений кода двойки, запрос на генерации чисел второго распределения - кода тройки. По окончат нии цикла геНерации в старшем раэрят де регистра последовательных прибли" жений находится единица, в следующем . разряде - нуль или единица, указывающая номер распределения, в осталь- О ных разрядах сформированное случайное число,В общем случае, при моделировании группы распределений, разрядность фор мируемых в данный момент случайных верхний индекс в обозначении кодов вероятностей указывает состояние, из которого переходит цепь, нижнййсостояниев которое переходит цепь. В первой строчке табл6 коды, определяющие вероятность переходов в одно из старших состояний, в нижней строчке " коды условных вероятностей. Так, например,Р- вероятность пеорехода цепи в состояние 2 или 3, если она находится в состоянии 1, Р- Ф вероятность перехода цепи из состояния 1 в состояние 2, если на пре" дыдущем такте определилось, что цепь переходит в состояние 2 или 3, 8 начале цикла генерации нового состояния в младшие два разряда регистра 5 заносится номер состояния цепи, в третий разряд единица. За два такта генерируется состояние, единица сдвигается в старший разряд регистра по" следовательных приближений.Максимальное число состояний Иар" ковского процесса и его максимальная связность с необходимым числом состояний, количество моделируееюх чисел равна количеству разрядов регистра последовательных приближенийв начальном состоянии равных нулю,начиная со старшего разряда до первого разряда устанавливаемого в единицу,номер распределения задается кодом,следующим за первой единицей, Втабл,5первый нижний индекс в обозначениикода вероятности указывает на номерраспределения. В табл. 6 доказано размещение ко"дов вероятностей переходов при моде-.лировании односвязной цепи Иаркова,описываемой матрицей , вероятностейперехода типа Р (1, 1=0,1,2,3)для блока памяти объемом 16 слов,в режиме разделения времени процессовИаркова и законов распределения слу"чайных чисел требуемой разрядности,т.е, функциональные возможности устройства определяются объемом блокапамяти устройства.Технико-зкономическая эффективностьизобретения определяется упрощением устройства, что снижает его стоимость и повышает надежность; обеспечением возюжности программного управления, что позволяет оперативноуправлять устройством вплоть до егоприменения для генерации нестационарных потоков чисел,г Устройство имеет, высокую досто.верность работы что вызваноупрощением в первую очередь цепейуправлейия, при сохранении функциональных возможностей. 8 совокупности с просто" той реализации это позволяет широко использовать предлагаемое устройство в микропроцессорных системах контроля и дйагностики цифровых схем в качестве генератора тестовых се 13. 1008738 14рий, в системах управления испыта" в виде одной микросхемы, так как все ниями, в моделирующих системах. блоки устройства могут реализовыВажной предпосылкой для реально- ваться на микросхемах средней интегго широкого применения устройства рации, без использования специализиявляется возможность его реализациированных элементов,Составитель А.КарасовРедактор Б.Папп Техред Т.фантаКорректор М.ШарошиЗаказ 2339/59 Тираж 704 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб д. 4/5Филиал ППП "Патент". г. Ужгород, ул. Проектная, 4