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

(51) 4 С 06 Р 7/58 ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Я 1ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(71) Минский радиотехнический институт(54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ(57) Изобретение относится к вычислительной технике и может быть использовано при моделировании случайныхпроцессов. Задачей, решаемой изобреЯО 1 10813 А 1 тением, является генерирование многоразрядных случайных чисел с требуемым законом распределения. Цель изобретение - повышение быстродействия. Цель достигается за счет введения новых функциональных связей и блоков. Генератор содержит блоки 1 перезаписи, группу 2 регистров, блоки контроля 3, блоки сравнения 6, блок 5 элементов И, коммутатор 7, блок шифрации 8, сумматор по модулю два 9, два триггера 12, регистр контроля 13, элементы И 10, 11, 14, генератор равномерно распределенных чисел 15, блок управления 4. Одним из преимуществ генератора является введение в его а структуру средств контроля и самовосстановления одиночных сбоев. 4 ил.1 131081Изобретение относится к вычислительной технике и может быть использовано при моделировании случайных про"цессов,Цель изобретения - повышение быстродействия генератора,На фиг.1 представлена структурнаясхема генератора, случайных чисел; нафиг.2 - схема блока перезаписи; наФиг.3 - схема блока сравнения; наФиг.4 - схема блока управления.Генератор случайных чисел (фиг.1)содержит блоки 1 - 1 п перезаписи,группу регистров 2 1 - 2, блоки3 1 - 3контроля, блок 4 управления,блок 5 элементов И, блоки 6 1 - бсравнения, коммутатор,7, блок 8 шифрации, сумматор 9 по модулю два, дваэлемента И 1 О и 11, два триггера 12,и 12, регистр 13 контроля, элемент 20И 14, генератор 15 равномерно распределенных чисел,Блок 1 перезаписи (фиг.2) содержитэлемент И 16 первой группы, элемент,И 17 Ьторой группы, сумматор 18 по25модулю два группы, элемент ИЛИ 19группы и элемент 2 И-ИЛИ 20 группы,Блок 6; сравнения (Фиг,3) содержит элементы И 21 и 21 г четвертойгруппы, КБ-триггеры 22 г и 22 групг 1пы еБлок 4 управления (фиг.4) содержитгенератор 23 импульсов, регистр 24сдвига, семь элементов ИЛИ 25 - 257,девять элементов И 26 - 26 и одно 9вибратор 27,Блок 3, - 3 контроля содержитэлемент И 28 третьей группы и счетныйтриггер 29 группы.Рассмотрим работу генератора слу 40чайных чисел.Перед началом работы производитсязапись информации в регистры 2 группы. Для этого на вход. задания режимагенератора подается нулевой сигнал,который разрешает запись информациив регистры 2 группы. За (ш+1) тактовсдвига (ш в . разрядность кода вероятностей, (в+1)-й разряд - контрольный)происходит заполнение регистров 2,Затем на вход задания режима генератора подается единичный сигнал и регистры 2 группы начинают функционироватькак циклические.Последовательность тактовых импульсов, обеспечивающих синхроннуюработу устройства, вырабатывает блок4 управления, который функционирует 3 2следующим образом. По сигналу "Пуск"сбрасывается регистр 24, который организован как циклический сдвиговыйрегистрЭтот же сигнал запускаетгенератор 23 импульсов, проходит через элементы ИЛИ 256 и 266 и производит начальный сброс КБ-триггеров22 группы блоков б сравнения, По этому сигналу с задержкой ь, необходимой для сброса КБ-триггеров 22 груп"11пы, одновибратор 27 формирует единичный сигнал начальной установки, который через первый элемент ИЛИ 25 поступает на информационный вход регистра 24 и вторым импульсом генератора 23 записывается в младший разряд регистра 24. Далее в течение всего функционирования устройства регистр 24 работает как циклическийсдвиговый регистр, в котором перемещается единица,С помощью элементов ИЛИ 25 вырабатывается разрешение на прохождениеимпульсов генератора 23 через соответствующие элементы И 26.После окончания установочных операций начинается Функционированиеустройства, т.е. сравнение равномерно распределенного числа (РРЧ) с кодами вероятностей функции распределения. В каждый такт работы устройствапроисходит сравнение одного разряда .РРЧ с соответствующими разрядамикодов вероятностей.К началу цикла сравнения на выходах регистров 2 группы устанавливаются старшие разряды кодов вероятностей,Блок 4 управления на первых и тактах обеспечивает выработку и синхронизирующих импульсов, которые сдвигают информацию в регистрах 2 группы и в регистре 13 (с выхода девятого элемента И 26 з блока 4 управления), а также синхронизацию 1-х КБ-триггеров группы 22(1 с = 1, 3, 5 2 п) - с выхода восьмого элемента И 268 блока 4 управления, а также 1 с-х КБ-триггеров группы 22 (1 с = 2, 4, 6, 2 п) - с выхода седьмого элемента И 267 блока 4 управления.Единичный сигнал с выхода элемента ИЛИ 30 поступает на вход блока 5 элементов И и разрешает прохождение кодов вероятностей функции распределения через него, а также обеспечивает прохождение цифры РРЧ с выходагенератора 15 на входы блоков 6 сравнения.В каждом блоке 61 сравнения с по.мощью элементов И 21 четвертой группы производится операция сравнения.Если на первые входы элементов 21и 21 поступает одинаковая информа 2ция, они вырабатывают нулевой сигнали КБ-триггеры 22, и 22 остаютсяв нулевом состоянии. Если разряд кода 10вероятности больше разряда РРЧ, тона выходе элемента 21 , появляетсяединичный сигнал, который устанавливает в единицу соответствующий триггер 22 1. В противном случае в единицу устанавливается КЯ-триггер 22 ,группы. Поскольку операция .сравненияначинается со старших разрядов, тоустановление в единицу одного из триггеров 22 группы означает, что в данном -м блоке 61 сравнения операциясравнения завершена,Цикл сравнения продолжается дотех пор, пока на выходах регистров2 группы не появятся младшие разрядыкодов вероятностей, хотя для его за-вершения достаточно, чтобы во всехблоках 6 сравнения сработал хотя быодин из триггеров 221 или 22 и,соответственно, запретил срабатывание второго.После окончания цикла сравненияинформация с выходов блоков 6 сравнения поступает через коммутатор 7 навходы блока шифрации и на выход устройства.Дпя контроля и самовосстановленияодиночных сбоев в предлагаемом устройстве используются сумматор 9 помодулю два, а также блоки 3 контро,ля. В режиме нормального функционирования информация с выходов регистров 2 группы проходит через элементы И 28 третьей группы на счетные входы триггеров 29 группы, которые определяют, является ли четным количество единиц в последовательностях, содержащихся в регистрах 2 группы (младший бит последовательности дополняет сумму его членов до четной), Одновременно с этим на каждом такте информация с выходов каждого из регистров 2 группы суммируется в блоке 9 с контрольным битом, дополняющим сумму до четной. Контрольные биты хранятся в регистре 13 и на каждом такте сдвига 1310813ются в соответствии с информациейрегистров 2 группы.При возникновении одиночного сбояединичный сигнал с выхода сумматора9 по модулю два проходит через элемент И 10 и устанавливает триггер12. Сигналом с выхода первого элемента И 26 блока 4 управления, возникающим по окончании цикла сравнения, единица из КБ-триггера 12 пере-писывается в -триггер 12. Появление единицы в триггере 12 означаетначало режима коррекции.Если сбой одиночный, то в одномиз счетных триггеров группы будетзафиксирована единица.Далее следует цикл коррекции. Вэтом случае элементы И 28 третьейгруппы закрыты сигналом с инверсноговхода триггера 12и на счетныевходы триггеров 29 группы информацияне поступает. Поскольку в счетномтриггере 29 -го блока контроля 3зафиксирована единица, то на первомвходе элемента И 17 второй группыблока 1, перезаписи присутствует единичный сигнал, свидетельствующий отом, что в соответствующем регистре2 группы произошла ошибка, В момент,когда сбойный разряд поступает навыход -го регистра 2 группы, навыходе сумматора 9 по модулю два возникает единичный сигнал, поступающийна второй вход элемента И 17 второйгруппы; далее он проходит черезэлемент И 17 и складывается сумматором 18 по модулю два группы с ошибочным битом, поступающим с выходарегистра 2 группы. Таким образом,ошибка исправляется и скорректированный бит поступает через элементы ИЛИ19 группы и 2 И-ИЛИ 20 группы на информационный вход регистра 2,Сигнал с выхода сумматора 9 по1модулю два проходит также через элемент И 11 и сбрасывает КЯ-триггер12. Очередной сигнал об окончаниицикла сравнения переписывает нулевоесодержимое триггера 121 в триггер12, и цикл коррекции заканчивается.Этот же сигнал сбрасывает счетныетриггеры 29 группы,Для генерирования случайных чиселс усеченной функцией распределения(или условных вероятностей) блок 5элементов И может быть заменен коммутатором. При этом первые информационные входы коммутатора подключаются5 131081 к выходам регистров 2 группы, а вторые информационные входы служат в качестве входов генератора случайных чисел для занесения левой и правой границ усеченной функции распределения, В этом случае перед началом цикла сравнения информация о левой и правой границах .в два такта записывается соответственно в 3-е и Е-е КБ-триггеры 22 группы (3=1, 3, 5,2 п, 1 с = 2, 4, 6,.., 2 п). Далее следует цикл сравнения, причем окончательный результат сравнения формируется в пределах определенных ранее границ.15 входом третьего элемента ИЛИ, выход(и+6)-го разряда регистра сдвигасоединен с прямым входом четвертогоэлемента И, (и+3)-м входом второгоэлемента ИЛИ и с вторым входом первого элемента ИПИ, инверсный вход четвертого элемента И соединен с первымвходом пятого элемента И и подключенк выходу пятого элемента ИЛИ, выходшестого элемента ИЛИ соединен с первым входом шестого элемента И, выходвторого элемента ИЛИ соединен с первым входом седьмого элемента И, выходтретьего элемента ИЛИ соединен с первым входом восьмого элемента И, выходФормула из о брет ения Генератор случайных чисел, содержащий генератор равномерно распреде ленных чисел, группу регистров, блок шифрации, о т л и ч а ю щ и й с я тем, что, с целью повышения быстродействия, он содержит четыре группы элементов И, группу счетных триггеров, группу КБ-триггеров, три элемента И, сумматор по модулю два, группу элементов 2 И-ИЛИ, группу сумматоров по модулю два, группу элементов ИЛИ, регистр контроля, первый и второй триггеры, блок элементов И, коммутаторы и блок управления, который содержит генератор импульсов, регистр сдвига, семь элементов ИЛИ, одновибратор, девять элементов И, причем в 35 блоке управления выход одновибратора соединен с первым входом первого элемента ИЛИ, выход которого соединен с информационным входом регистра сдвига, выходы разрядов с первого по и"й 40 регистра сдвига (где п - число интервалов квантования функции распределения) соединены .с одноименными входами второго, третьего, четвертого и пятого элементов ИЛИ, выход (и+1)-го разряда регистра сдвига соединен с (и+1)-м входом четвертого элемента ИЛИ, первым входом первого элемента И, выход (п+2)-го разряда регистра сдвига соединен с первым входом вто рого элемнта И, выход (и+3)-го разряда сдвига соединен с первым входом третьего элемента И, выход (и+4)-го разряда регистра сдвига соединен с первым входом шестого элемента ИЛИ и (и+2)-ми входами второго и третьего элементов ИЛИ, выход (и+5)-го разряда регистра сдвига соединен с (и+3)-м четвертого элемента ИЛИ соединен с первым входом девятого элемента И, выход пятого элемента И соединен с первым входом седьмого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента И, вход одновибратора соединен с входом обнуления регистра сдвига, входом запуска генератора импульсов, вторым входом шесто"го элемента ИЛИ, с (и+1)-ми входами второго и третьего элементов ИЛИ и является входом "Пуск" генератора случайных чисел, выход генератора импульсов соединен с вторыми входами первого, второго, третьего, шестого, седьмого, восьмого и девятого элементов И и с входом синхронизации регист"ра сдвига, первые прямые входы элементов 2 И-ИЛИ,группы и информационный вход регистра контроля подключены к разрядным входам задания закона распределения генератора, инверсные входы элементов 2 И-ИЛИ группы соединены с вторыми прямыми входами элементов 2 И-ИЛИ группы, с тактовым входом регистра контроля и подключены к входу задания режима генератора, выходы регистров группы и выход регистра контроля подключены к соответствующим входам сумматора по модулю два, выходырегистров группы подключены к группеинформационных входов блока элементовИ, выходов регистров группы соединены с прямыми входами одноименных элементов И первой группы и с первыми входами сумматоров по модулю два группы, инверсный вход каждого элемента Ипервой группы соединен с выходом соответствующего элемента И второй груп пы и вторым входом одноименного сумматора по модулю два группы, выход которого соединен с первым входом соответствующего элемента ИЛИ груп 1310813пы, второй вход которого соединен свыходом соответствующего элементаИ первой группы, инверсные первыевходы элементов И третьей группысоединены с первыми входами первого 5и второго элементов И, с инверснымивходами элементов И второй группы иподключены к инверсному выходу Р-тригГера, первые прямые входы элементовИ второй группы подключены к выходам 10соответствующих счетных триггеровгруппы, выход первого элемента И блока управления соединен с первым входом третьего элемента И и входомсинхронизации Ь-триггера, вход которого соединен с выходом КЯ-триггераи, вторым входом третьего элемента И,восход которого подключен к входам"Сброс" счетных триггеров группы,единичный и нулевой входы КЯ-триггера соединены с выходами соответственно первого и второго элементов И,вторые входы которых объединены и подключены к выходу сумматора по модулюдва и к вторым прямым входам элементов И второй группы, выходы элементов 2 И-ИЛИ группы соединены с соответствующими информационными входамирегистров группы, входы синхронизациирегистров группы соединены с входом ЗОсинхронизации регистра контроля, входом опроса генератора равномерно распределенных чисел и подключены квыходу девятого элемента И блокауправления, второй вход пятого элемен 35та И блока управления соединен .с выходом генератора равномерно распределенных чисел, выход шестого элементаИ блока управления подключен к нулевым входам КБ-триггеров группы, выход седьмого элемента И блока управ 1 ления соединен с входами синхронизации 1-х КБ-триггеров группы (где 1 =2, 4, 6 2 п), выход восьмого элемента И блока управления соединен с входами синхронизации 3-х КЯ-триггеров группы (где 3 = 1, 32 п-.1), выход седьмого элемента ИЛИ блока управления соединен с инверсными входами 1-х элементов И четвертой группы и с первыми прямыми входами Е-х элементов И четвертой группы, выход каждого элемента И четвертой группы подключен к единичному входу одноименного КЯ-триггера группы, второй прямой вход каждого (Е-го элемента И четвертой группы подключен к инверсному выходу (Е)-го КЯ-триггера группы, а инверсный выход Е-го КЯ-триггера группы соединены с вторым прямым входом (1+1)-го элемента И четвертой группы, третьи прямые входы 1-х элементов И четвертой группы и инверсные входы Е-х элементов И четвертой группы подключены к соответствующим Е-м вьисодам блока элементов И, управляющий вход которого соединен с выходом пятого элемента ИЛИ блока управления, выходы второго и третьего элементов И бяока управления подключены к первому и второму управляющим входам коммутатора соответственно, первая группа информационных входов которого подключена к прямым выходам 1-х ВЯ- триггеров группы соответственно, а вторая группа информационных входов коммутатора соединена с инверсными выходами Е-х КЯ-триггеров группы соответственно, выходы коммутатора соедииеиы с соответстующими входами блока шифрации, выход которого является выходом генератора.1310813 Составитель И.СтоляровТехред Л.Олейник аказ 1892/45 Тираж 673 ИИПИ Государственно по делам изобретен 3035, Москва, Ж, одписноР оизводственно-полиграфическ дприя дактор М,Дылын комитета СССи открытийушская наб.,орректор Г,Решетник жгород, ул. Проектная, 4