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

ОПИСАИЗОБРЕТЕННАЯ Совз Советских Социалистических Республик(51)М. КЛ.С 07 С 15/00 С 06 Г 1/02 Государственный комитет СССР по дедам изобретений и открытий(72) Авторы изобретения В,Н, Ярмолик и А,Н, Морозевич Минский радиотехнический институт(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ Изобретение относится к областивычислительной техники и можетбыть использовано в качестве устройства. для получения случайных чиселпри решении задач методом Монте-Карло, а также для построения гене -раторов случайных процессов с заданными характеристиками,Известен генератор псевдослучайных чисел, садержаший .регистр сдвигас сумматором по модулю два в цепиобратной связи 1,Недостатком этого генератора является наличие периода в формируемойпоследовательности,Наиболее близким по техническойсушности к данному изобретению является генератор псевдослучайных чисел, содержаший первую группу сумматоров по модулю два и группу триггеров, входы синхронизации которыхподключены к выходу генератора тактовых импульсов 2.Недостатком этого устройства является малый период псевдослучайнойпоследов ател ьн ости .Цель изобретения - расширениефункциональных возможностей генератора за счет устранения повторения последовательности кодов псевдослучайных чисел на выходах генератора,Для достижени я поставленной целигенератор содержит первую и вторуюгруппы элементов И, группу элементов ИЛИ, вторую группу сумматоровпо модулю два и генератор равновероятной двоичной цифры, ко входукоторого подключен выход генераторатактовых импульсов, а единичный инулевой выходы генератора равновероятной двоичной цифры подключены кпервым входам первой и второй группыэлементов И соответственно, ко второму входу 1-го элемента И первойгруппы подключен выход 1-го сумматора по модулю два первой группы,ко второму входу 1-го элемента И 2 О второй группы подключен выход 1-госумматора по модулю два второй группы, выходы 1-ых элементов И первойи второй групп подключены ко входам1-го элемента ИЛИ, выход которого 25 подключен ко входу 1-го триггера, кпервым входам 1-ых сумматоров помодулю два первой и второй группподключены единичные выходы 1-ыхтриггеров, ко вторым входамстарших сумматоров по модулю два первОЙ группы пОдключены ВыхОды 3 младших триггеров, к вторым входам щ мха,ших сумматоров по модулю два первой группы подключены выходы и старших сумматоров по модулю два первой группы, ко вторым входам щ5старших сумматоров по модулю двавторой группы подключены выходы щ младших триггеров, к вторым входаммладших сумматоров по модулю двавторой группы подключены выходы 3старших сумматоров по модулю двавторой группы,На фиг,1 приведена структурнаясхема генератора для случая, когдап 1 = 5; на фиг,2 - функциональнаясхема генератора рандомизированных.псевдослучайных чисел для щ = 3;на фиг,З - временная диаграмма егоработы, В общем случае генераторрандомизированных псевдослучайныхчисел состоит из в триггеров 1,20щ элементов ИЛИ 2, первой группыдвухвходовых сумматоров по модулюдва 3, первой группы элементов И 4,второй группы двухвходовых сумматоров по модулю два 5, второй группы элементов И б и генератора равно."вероятной двоичной цифры 7 (см.фиг.1,для щ = 5) . Количество сумматоровпо модулю два и элементов И в группе равняется щ (фиг,1) . Выходы 0- 30триггеров соединены со входами сумматоров по модулю два согласно следующей системы уравнений:35где Ь.; вединичный выход (щ) -готриггера, О ,+ , - выход (в+3-1) -го сумматора йо модулю два, 9означает операцию суммирования помодулю два, Причем для органиэациисвязей первой группы сумматоровпо модулю два используется системауравнений (1) при значении номераразряда регистра сдвига, выход которого соединен со входом сумма 45тора по модулю два в обычных структурах (1), равной 3, а для второйгруппы сумматоров по модулю двапри в. Так для случая в =5 навходы сумматоров по модулю два.первой группы 3 (фиг,1) заведены связивсоответствии с системой:о -Ъ ОЬэ;о Ь 4 ЕЬ - Ь ЕЬ а -Ь Вца-Ь фц 4а на,входы сумматоров по модулюдва второй группы 5 в соответствиисо следующей системой о =Ь ЭЪ5 5На выходах первой и второй группысумматоров по модулю два последовательно будут генерироваться п-разрядные коды псевдослучайных чиселМ-последовательностей, порождаемыхследующими полиномами Ч(х)х 5+ хз+ 1 и (х) = х 5+ х+ 1,причем периоды обоих последовательностей одинаковы, Последовательностьследования же кодов отлична и случайна как в первой, так и во второйМ-последовательностях, Таким образом,на выходах сумматоров по модулюдва обеих групп генерируются дверазные М-последовательности одинаковой длины, 0-триггеры и сумматорыпо модулю два (кроме связей второйгруппы сумматоров) представляют генератор псевдослучайных чисел, которые повторяют логику его работы.В зависимости от значения равновероятной двоичной цифры на выходегенератора 7 единичный выход которого подключен к первой группеэлементов И 4, а нулевой - ко второйгруппе б (фиг,1), Код псевдослучайного числа с первой или второй группы сумматоров по модулю два черезэлементы ИЛИ 2 записывается на 0 триггеры. Генератор 7 представляетсобой простейший датчик равновероятной двоичной цифры, построенный нафизических принципах,Фукционирование генератора псевдослучайных чисел происходит следующимобразом,В начальный момент на Р-триггеры1 записывается ненулевой код (фиг,1) .На выходах сумматоров по модулюдва первой группы 3 образуется очередной код псевдослучайного числапервой М-последовательности, а навыходе второй группы 5 - второй Мпоследовательности, В зависимостиот значения очередной двоичной цифры на выходе генератора 7 по приходутактового импульса на синхронизирующие входы триггеров 1 на их 0 входы через ту или иную группы элементов И и через элементы ИЛИ 2, объединяющие выходы обоих групп И, подается очередной код первой иливторой М-последовательности, С приходом очередного синхронизирующегоимпульса процесс повторяется,Более подробно процесс генерирования псевдослучайных чисел пояснимна конкретном примере, На фиг,2приведена функциональная схема генератора псевдослучайных чисел дляв = 3, а на фиг.З - временная диаграмма его работы, На фиг, За показана временная диаграмма синхронизирующих импульсов, по приходу которых триггеры устройства меняютсвое состояние; на фиг. Зб-временная диаграмма на единичном выходегенератора 7; на фиг, 3 в и 3 г приведены две последовательности, порождаемые полиномами Ч(х) = х + х + 1и Ч(х) = х+ х + 1, для 3 = 1 и- 2, Стрелки с цифрами в кружкахнад ними означают последовательностьпереходов состояний триггеров устройства, В первоначальный момент на40 триггерах записан код 101, тогда1 = 100, а 2 = 011, Так как в момент времени 1 на единичном выходегенератора 7 находится единица, топриходу синхроимпульса через верхнююгруппу элементов И и элементы ИЛИ 5на триггерах запишется код числа100, После прохождения переходныхпроцессов на выходах сумматоров установляются новые значения1 = 011и 2 = 110. В следующий момент времени на триггерах запишется код2 = 110, т.к, на единичном выходе генератора 7 находится нуль.Подобным образом триггеры меняют "свое состояние в зависимости от значения генератора 7 и по приходу последующих импульсов, На фиг. Зв и Згстрелками показана граф-схема переходов состояний триггеров для .(,2 3оИэ вышеприведенного описания20функционирования генератора псевдослучайных чисел следуют следующиефакты, Значения1 и2, генерируемые на выходах первой и второйгруппы сумматоров по модулю два в25каждый конкретный такт, являются значениями кодов из двух отличных М-последовательностей. Последующее значение 1 или 2 в худшем случаеявляется следующим кодом М-последовательности, получаемой при одномсдвиге в последовательном генераторепсевдослучайных чисел, Так,1 принимает последовательные значения,которые получались бы в последователь ном генераторе 100 через 3 такта после 101, 011 через 3 такта после 100,101 через 1 такт после 011, 111 через 4 такта после 101 (фиг,2,3) Отсюда очевидно, что1 и2 принимают значения иэ двух различных Мпоследовательностей (но,имеющих одинаковый состав кодов), порядок следования которых случаен, Нетрудно заметить, что при фиксировании на выходе генератора 7 нуля или единицыгенератор псевдослучайных чиселбудет функционировать как обычный генератор псевдослучайных чисел, Атак как состояние его случайно, тои порядок следования кодов М-последовательности будет абсолютно случаен.В силу этого такой недостаток,какпериодичность,в данном устройствеустраняется, что,в свою очередь,означает, что автокорреляционные55функции выходных последовательностейимеют ненулевое значение только при1 (С,где С - длительность выходного сигнала между очередными синхроимпульсамИ, Такой вид автокорреля- бОционной функции полностью удовлетворяет требованиям, поедъявляемым кслучайным числам,Преимущества генератора заключаются в следующем, Природа выхолных б 5 псевдослучайных последов ат ел ь наст еймаксимально приближена к истиинослучайным числам, В данном устройстве нарушено жесткое условие, имеющее место во всех генераторах псевдослучайных чисел и приводящее к такому недостатку, что после опредепенного (-1; должно следоватьт 11. заранее точно известное, Вданном генераторе псевдослучайныхчисел такое условие не соблюдается,так как (-;1+ может принять равновероятно одно из двух значений, Заметим, что в физических генераторахслучайных чисел Ц(1+ может принимать любое значение из всего набора возможных кодов,Предлагаемый генератор отличается простотой технической реализации,Удельные аппаратурные затраты на одинразряд псевдослучайного числа составят один двухвходовой сумматорпо модулю два, одну схему И, - схемы ИЛИ в , Р-триггера и - генерато 12 ера 7,Данный генератор псевдослучайныхчисел позволяет получать числа подвум каналам,Генератор 7, примененный в устройстве, может быть построен по самойпростейшей схеме (например триггерс коммутируемым питанием), так кактребования к равновероятности выходной двоичной цифры являются оченьнизкими. Даже при отказе этого генератора, т,е, когда на его выходе будет зафиксировано значение нуляили единицы, устройство в целом будетфункционировать, но в этом случаепериод будет равен 2 - 1, а не бесйконечности. Этот факт говорит о надежности функционирования предлагаемого устройства и стабильности еговероятностных характеристик.Применение подобного генераторапсевдослучайных чисел позволит повысить качество псевдослучайныхпоследовательностей а тем самымточность и достоверность решения задач методом Монте-Карло, Кроме того,подобные устройства позволят получать истинно Белый шу. для построения генераторов случайных процессов,Формула изобретения Генератор псевдослучайных чисел, содержащий первую группу сумматоров по модулю два и группу триггеров, входы синхронизации которых подключены к выходу генератора тактовых импульсов, о т л и ч а ю щ и йс я тем, что, с целью расширения функциональных зозчоюностей геиератора за счет устранения повтэреция последовательности кодов псевдослучайных чисел на выходах генератора,он содержит первую и вторую группуэлементов И, группу элементов ИЛИ,вторую группу сумматоров по модулюдва и генератор равновероятнойдвоичной цифры, ко входу которогоподключены выход генератора тактовых импульсов, а единичный и нулевойвыходы генератора равновероятнойдвоичной цифры подключены к первымвходам первой и второй групп элементов И соответственно, ко второмувходу 1-го элемента И первой группы подключен выход 1-го сумматорапо модулю два первой группы, ковторому входу 1-го элемента И второй группы подключен выход 1-го сумматора по модулю два второй группы,выходы 1-ых элементов И первой ивторой групп подключены ко входам1-го элемента ИЛИ, выход которогоподключен ко входу 1-го триггера,к первым входам 1-ых сумматоров помодулю два первой и второй групп подключены единичные выходы 1-ыхтриггеров, ко вторым входам 3 старших сумматоров по модулю два первойгруппы подключены выходы 3 младшихтриггеров, к вторым входам щ 5 младших сумматоров по модулю двапервой группы подключены выходывстарших сумматоров по модулю двапервой группы, ко вторым входам в старших сумматоров по модулю двавторой группы подключены выходы в младших триггеров, ко вторым входаммладших сумматоров по модулю двавторой группы подключены выходы 3старших сумматоров по модулю двавторой группы,Источники информации,принятые во внимание при экспертиэе1, Яковлев В,В Федоров Р,Ф,Вероятностные вычислительные машины,Л Машиностроение, 1974, с,344.2. Авторское свидетельство СССРпо эаявке М 2415584/24 от 20 апреля1977 г. (прототип),Составитель А, Карасовакто Д. 3 лбов ТехредМ .Келемеш Корректор И. Михеев илиал ППП Патент, г. Ужгород, улПроектная,РЗаказ 8492/46 Тираж ЦНИИПИ Госу по делам 3035 Москвб 41 По арственного коа зобретений и .отЖРаушска пи оноетета Ср 1 тийнаб,