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

О П И С А Н И Е (в 924706ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик(5)М. Кд,О 06 т 7/58 3 Ъоударстюиый комитат СССР ао делам изобретений и открытий(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ Изобретение относится к вычисли- тельной технике и может быть исполь. зовано в качестве устройства для получения случайных чисел при решении задач методом Монте-Карло, а также для построения генераторов случайных процессов с заданными характеристиками.Известен генератор псевдослучайных чисел, содержащий регистр сдвига с сумматором по модулю два в цепи обто ратной связи 11Недостатком данного генератора является наличие периода в формируемой последовательности и, кроме того, невозможность получения нулевого35 кода псевдослучайного числа. Параллельный генератор псевдослучайных чисел позволяет получать нулевой код псевдослучайного числа и отли 20 чается максимальным быстродействием. В качестве основного недостатка генератора от меча ется сложнос т ь схем формирования сдвинутых последоеательностей, определяемая числом входовсумматоров по модулю два. Каждыйсумматор в среднем имеет тп /2 входа.При этом затраты оборудования,необходимые для построения схем формироаания сдвинутых последовательностей,в несколько раз превышают затраты,идущие на построение кольцевагорегистра сдвига, состоящего из птразрядов. Наиболее близким по технической сущности к предлагаемому является генератор псевдослучайных чисел, состоящий из тп триггеров, группы элементов ИЛИ, первой и второй группы двухвходовых сумматоров по модулю два, первой и второй группы двухвходовых схем И и генератора раеновероятной двоичной цифры, Количество сумматоров по модулю деа, элементов И и ИЛИ в группах равняется щ . Все узлы устройства соединены соответствующими связями.уо 6 1 о 15 20 25 30 55 ао 45 50 55 3 924Преимущества известного генератора заключаются в том, что природапсевдослучайных чисел максимальноприближена к истинно случайным чис -лам, техническая реализация осуществляется при малых удельных аппаратурных затратах, кроме того, оказывается возможным получение псевдослучайных чисел по двум каналам 2Недостатком описанного устройстваво-первых, является невозможность получения на его выходе п-разрядногопсевдослучайного числа=0000,Отсутствие комбинации ф -- 0000приводит к искажению равномерногозакона распределения, которое увеличивается с уменьшением величиныВторым весьма существенным недостатком генератора псевдослучайных чисел является ограниченность его функциональных возможностей. При практической реализации генератора оказывается возможным построение такогогенератора для весьма узкого классанеприводимых примитивных характеристик многочленов. Поэтому для некоторых значений т построение генератораоказывается невозможным. Так, например, для г = 8, 16, 24, 32 отсутствуют порождающие многочлены требуемого вида, таким образом, нет возмож ности реализации генератора в разрядность, согласованной с разрадностьюЭВМ семейства ЕС, Кроме того, генератор отличается жесткостью структуры и неуниверсальностью, что объясняется невозможностью изменения видапорождающего многочлена для .Фиксированного щ в процессе его эксплуатации.Цель изобретения - расширениефункциональных возможностей генератора и повышения качества выходныхпоследовательностей за счет введениянулевой комбинации в последовательность кодов и реализации подобныхустройств для любого неприводимогопримитивного характеристическогомногочлена,Для достижения поставленной целив генераторе, содержащем щ-триггеров, группу элементов ИЛИ, первуюи вторую группы двухвходовых элементов И, генератор рав нов ероят ной дв оичной цифры, группу (щ + 1) входовых сумматоров по мощулю два, группу (щ - 1) входовых элементов ИЛИ-НЕ,третью группу из щ подгрупп по щдвухвходовых элементов И, причем к С-входам щ триггеров и входу генератора равновероятной двоичной циФрыподключен выход генератора тактовыхимпульсов, а единичный й нулевойвыходы генератора равновероятнойдвоичной цифры подключены к первымвходам первой и второй групп элементов И, выходы 1-х элементов И первой и второй групп подключены ко входам-го элемента ИЛИ, ко вторымвходам первой и второй групп элементов И поданы значения коэффциентовпринимающих величину нуля или единицы, выход 1-го элемента ИЛИ подключен к первому входу 1-го элементаИ 2-й подгруппы третьей группы, выходы элементов И -й подгруппы третьей группы и выход 3-го элементаИЛИ-НЕ подключены ко входам В-го(щ + 1) входового сумматора по модулю два, выход- го триггера подключен ко второму входу 1+-1-го элемента И щ+ 1-1-ой подгруппы третьей группы и к 2+1-1-му входу щ+1-2-го элемента ИЛИ-НЕ, выход С-го (щ+1)- входового сумматора по модулю два подключен к О входу 0-го триггера ко второму входу В-го элемента И 1-ой подгруппы третьей группы и к 1-ому входу .Рго элемента ИЛИ-НЕ,На фиг. 1 приведена функциональная схема генератора рандомизированных псевдослучайных чисел для случая, когда щ = 5; на фиг, 2 - функциональная схема генератора для щ = 3; на фиг. 3 - временная диаграмма работы генератора; на фиг, 4 - генератор равновероятной двоичной цифры,Приведенная функциональная схема (Фиг. 1) генератора для щ = 5, подобно как и в общем случае, состоящий из щ О-триггеров 1, группы элементов ИЛИ 2, первой и второй группы двухвходовых элементов И 3, 4, генератора 5 равновероятной двоичной цифры, группы (щ + 1) входовых сумматоров 6 по модулю два, группы (щ) входовых элементов ИЛИ-НЕ 7, третьей группы из щ подгрупп по щ двухвходовых элементов И 8. Количество элементов ИЛИ 2, элементов И в первойи второй группах 3 и 4,(щ + 1) входовых сумматоров 6 по модулю два,(щ - 1) входовых элементов ИЛИ-НЕ 7и триггеров 1 в группе равняется щЕдиничные выходы О-триггеров соединены со входами двухвходовых элементов И 8 третьей группы и входамиэлементов ИЛИ-НЕ,5 92470На выходах сумматоров 6 по моду" лю два последовательно будут генерироваться щ-разрядные коды псевдослучайных чисел двух И-последовательностей, причем периоды обеих последовательностей одинаковы, Последовательность следования же кодов отлична и случайна как в первой,так и во второй М-последовательности. Таким образом, на выходе (пав)-вхо О довых сумматоров 6 по модулю два (фиг. 1) генерируются ю -разрядные сегменты двух отличных М-последовательностей одинаковой длины, При фиксированном значении равновероят з ной двоичной цифры устройство представляет собой генератор псевдослучайных чисел, генерирующий на своем выходе щ -разрядные псевяослучайные числа. При переменном значении двоич- що ной цифры в зависимости от ее величины на выходе генератора равновероятной двоичной цифры, единичный выход которого подключен к первой группе элементов И 3, а нулевой - ко д второй группе 4 (фиг. 1), код гаразрядного псевдослучайного числа той или иной И-последовательности с выходов т+ 1) входовых сумматоров 6 по модулю два записывается на 2- триггеры 1. Генератор 5 равновероятной двоичной цифры представляет со" бой простейший датчик равновероятной двоичной цифры, построенный на физических принципах,Устройство работает следующим образом.В начальный момент на Р -триггеры 1 записывается произвольный код, в том числе и нулевой (фиг, 1), На вы О ходы элементов ИЛИ 2 проходят зна чения коэффициентов первого или второго характеристического многочлена в зависимости от того, равняется единице или нулю величина Я, на выходе генератора 5 в данный момент времени. В зависимости от значения величины с на выходахг+ 1) входовых сумматоров по модулю два образуется очередной т -разрядный код псевдо 50 случайного числа первой или второй И-последовательности. По приходу тактового импульса на синхронизирующие входы триггеров 1 через их 0 входы на триггерах 1 запишется код, полученный на выходе сумматоров 6 по модулю два. С приходом очередного синхронизирующего импульса процесс повторяется. 6 6Подробный процесс генерирования псевдослучаиных чисел рассмотрим на генераторе рандомизированных псевдослучайных чисел для = 3. На фиг.3 а показана временная диаграмма синхронизиоующих импульсов, по приходу которых триггеры устройства меняют свое состояние; на фиг. 3 б - временная диаграмма на единичном выходе ге" нератора; на фиг. 3 в и 3 г приведены две М-последовательности. Стрелки с цифрами в кружках под ними означают последовательность переходов состояний триггеров 1 устройства.В первоначальный момент на триггерах записан код 101. Так как в момент времени 1 на единичном выходе генератора 5 находится единица (фиг. 3 б), то через элементы И 3 и элементы ИЛИ 2 на входы элементов 8 подаются коэффициенты р . С учетом конкретных значений коэффициентов Я на выходах сумматоров 6 по модулю два очередное значение псевдослучайного числа1 будет равняться 000.:ПО приходу тактового импульса в момент времени 1 на синхровходы-триггеров 1 и вход генератора 5 псевдослучайное числозапишется на триггеры 1 и равновероятная двоичная цифра с примет значение, равное нулю. После прохождения переходных процессов на выходах сумматоров 6 по модулю два устанавливается новое значение= 101. В следующий момент времени на триггерах 1 запишется код 101, так как на единиц" ном выходе генератора 5 находится ноль. Подобным образом триггеры меняют свое состояние в зависимости от значения на единичном выходе генератора 5 и по приходу последующих так" товых импульсов. На фиг. 3 в и 3 г стрелками показана граф-схема пере"ходов состояний триггеров для моментов времениИз вышеприведенного опйсания функционирования генератора рандомизированных псевдослучайных чисел вытекают следующие факты. Значения псевдослучайных чиселна выходе генератора являются значениями кодов из двух отличных М- последов ат ел ьностей, Нетрудно заметить, что при фиксированном значении нуля или единицы на выходе генератора 5, генератор рандомизированных псевдослучайных чисел будет функционировать как обычный генератор псевдослучайных06 35 Применение подобного генераторарандомизированных псевдослучайныхчис ел, отли чаюше гося ши р окими фу нк -циональными возможностями, высокой надежностью функционирования и стабильностью его вероятностных характеристик, позволит повысить качество решения задач методом Монте-Карло. Кроме того, подобные устройства позволят получать истинно белый шум для пост роения генераторов слу чайных процессов. 7 92 Мчисел, А так как состояние генератора 5 случайно, то и порядок следования кодов М-последовательностейбудет абсолютно случайным, причемвыходным значением устройства с равной вероятностью может быть любойп-разрядный код, в том числе и нулевой. Подобный факт означает, что автокорреляционная функция выходнойпоследовательности имеет ненулевоезначение только при т,(Т, где Г - дли-тельность выходного сигнала междуочередными синхроимпульсами. Такойвид автокорреляционной функции полностью удовлетворяет требованиям,предъявляемым к последовательностямслучайных чисел.Преимущества генератора рандомизированных псевдослучайных чиселзаключается в следующем.20Природа выходных псевдослучайныхчисел максимально приближена к истинно случайным числам. В данном устройств е, подобно как и в прототи пе,нарушего жесткое условие, что послеопределенного Й должно следоват ь1заранее точно известное, так как111может принимать равновероятно одМ 1но из двух значений,Возможность получения на выходегенератора кода псевдослучайнргочисла равного 0000 приводит к выравниванию математического ожиданиявероятности появления любого кода ,которая в данном случае равняетсяР = 1/2,Таким образом, получение нулевойкомбинации на выходе устройства расширяет его функциональные возможностии обеспечивает повышение качества40выходных последовательностей, Такавтокорреляционная функция выходнойпоследовательности при 1 7 Т будет иметьнулевое значение, а не значение равное 1/(2- 1) что имеет место в про"745тотиее. Отсутствие запрещенных кодовпозволяет повысить надежность генератора, так как наличие нулевого кодана триггерах 1 не срывает генерирования псевдослучайной последователь 50ности.При практической реализации генератора рандомизированных псевдослучайных чисел оказывается возможнымпостроение такого генератора для любого неприводимого примитивного характеристического многочлена. Поэтомудля любого значения го, в том числеи для г= 8, 12, 13, 1 Й, 16, 19,82, 26, 27, 29, 30, 32 и т. д, реализации генератора рандомизированных псевдослучайных чисел возможна.Кроме того, для конкретного значения т в силу многообразия многочленов, позволяющих генерировать М-последовательности, возможно построениеподобных устройств с одинаковой разрядностью выходных кодов равной п,что существенно расширяет его функциональные возможности.В процессе эксплуатации генератора рандомизированных псевдослучайных чис ел возможно изменение М-последовательностей путем замены коэффициентов )"В и р пораждающих их характеристи ческих многочленов,Предла га емый ге нера т ор отл и ча етс я простотой технической реализации, Удельные аппаратурные затраты на один разряд псевдослучайного числа составят один (ю + 1) .входной сумматор по модулю два, один триггер, один элемент ИЛИ-НЕ, один элемент ИЛИ, ч + 2 элементов И, и 1/п 1 генератора равно- вероятной двоичной цифры. Генератор 5,применяемый в устройстве, может быть построен по самой простейшей схеме (например, триггер с коммутируемым питанием) , так как требования к равновероятности выходной двоичной цифры являются оцень низкими. Пример подобного устройства, используемого изобретения, приведен на фиг, ч, Даже при отказе блока 5, т.е. когда на его выходе будет зафиксировано значение нуля или единицы, устройство в целом будет функционировать, но в этом случае будет равен 2 - 1, а не бесконечности. Этот факт говорит о надежности функционирования предлагаемого устройства и стабильности его вероятностных характеристик. псевдослучайных последоватеЛьностей, а тем самым точность и достоверностьФормула изобретения Генератор псевдослучайных чисел, содержащий п 0 -триггеров, группу элементов ИЛИ, первую и вторую груп пы элементов И, генератор равновероятной двоичной цифры, причем к синхровходам 2-триггеров и входу генератора равновероятной двоичной цифры подключен выход генератора так-О товых импульсов, а единичный и нулевой выходы генератора равновероятной двоичной цифры подключены к первым входам элементов И первой и второй групп, выходы -х (1= 1, 2 ю) элементов И первой и второй групп подключены к входам 1 -го элемента ИЛИ, отличающийся тем, что, с целью расширения функциональных возможностей генератора за счет рас ширения класса генерируемых псевдослучайных последовательностей чисел, он содержит группу (п+ 1) входовых сумматоров по модулю два, группу Ж) в ходовых элементов ИЛИ-НЕ и третью группу из п подгрупп по тп элементов И, причем вторые входы элементов И первой и второй группы образуют соответственно первую и вторую группы входов генератора, авыход 1-го элемента ИЛИ подключенк первому входу-го элемента И3 -й (1= 1, 2гп) подгруппы третьей группы, выходы элементов И 1-йподгруппы третьей группы и выход1-го элемента ИЛИ-НЕ подключеН квходу 6-го(у 1+ Ц входового сумматорпо модулю два, выход 1-го триггераподключен к второму входу + ч"гоэлемента И (ьз+ 1 -9)-й. подгруппытретьей группы и к ф+ 1 - 1) -му входу (н 1 + 1 - Ю-го элементов ИЛИ-НЕ,выход Р-го (ю+ 1) входсвого сумматорапо модулю два подключен к 2 -входу3-го триггера, к второму входу(-1)-гоэлемента И 1 -й подгруппы третьейгруппы и к 1 -му входу (1-1)-го элемента ИЛИ-НЕ,Источники информации,принятые во внимание при экспертизе1. Яковлев В.В. и Федоров Р.ф.Вероятностные вычислительные машины.Л., "Иашиностроение", 1971,2. Авторское свидетельство СССР708381, кл. Я 061/02, 197792470 б 4 6 Составитель А.Карасоведа ктор В . Пилипенко Техред С . Мигунова К орректо иценко Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4 Тираж 732осударственного кам изобретений иосква, ЖРаушс Заказ 2820/67ВНИИПИпо дел113035, М Подпис номитета СССРткрцтийая наб., д, 4/5