Генератор псевдослучайных чисел Советский патент 1982 года по МПК G06F7/58 

is) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

Изобретение относится к вычислительной технике и может быть использовано в качестве устройства для получения случайных чисел при решении задач методом Монте-Карло, а также для построения генераторов случайных процессов с заданными характеристиками. Известен генератор псевдослучайны чисел, содержащий регистр сдвига с сумматором по модулю два в цепи обратной связи tl 1. Недостатком данного генератора является наличие периода в формируемой последовательности и, кроме того, невозможность получения нулевого кода псевдослучайного числа. Параллельный генератор псевдослучайных чисел позволяет получать нулевой код-псевдослучайного числа и отличается максимальным быстродействием. В качестве основного недостатка гене ратора отмечается сложность схем фор мирования сдвинутых поеледовательностей, определяемая числом входов сумматоров по модулю два. Каждый сумматор в среднем имеет т/2 входа. При этом затраты оборудования,необходимые для построения схем формирования сдвинутых последовательностей, в несколько раз превышают затраты, идущие на построение кольцевого регистра сдвига, состоящего из m разрядов. Наиболее близким по технической сущности к предлагаемому является генератор псевдослучайных чисел, состоящий из m триггеров, группы элементов ИЛИ, первой и второй группы двухвходовых сумматоров по модулю два, первой и второй группы двухвходовых схем И и генератора равновероятной двоичной цифры. Количество сумматоров по модулю два, элементов И и ИЛИ в группах равняется m. Все узлы устройства соединены соответствующими СВЯЗЯГ«1.

Преимущества известного генератора заключаются в том, что природа псевдослучайных чисел максимально приближена к истинно случайным числам, техническая реализация осуществляется при малых удельных аппаратурных затратах, кроме того, оказывается возможным получение псевдоч случайных чисел по двум каналам 2

Недостатком описанного устройства во-первых, является невозможность получения на его выходе т-разрядного псевдослучайного числа ...0. Отсутствие комбинации 000...О приводит к искажению равномерного закона распределения, которое увеличивается с уменьшением величины

Вторым весьма существенным недостатком генератора псевдослучайных чисел является ограниченность его функциональных возможностей. При практической реализации генератора оказывается возможным построение такого генератора для весьма узкого класса неприводимых примитивных характеристик многочленов. Поэтому для некоторых значений m построение генератора оказывается невозможным. Так, например, для m 8, 16, 2k, 32 отсутствуют порождающие многочлены требуемо го вида, таким образом, нет возмож-ности реализации генератора в разрядность, согласованной с разрадностью ЭВМ семейства ЕС. Кроме того, генератор отличается жесткостью структуры и неуниверсальностью, что объясняется невозможностью изменения вида порождающего многочлена для фиксированного m в процессе его эксплуатации.

Цель изобретения - расширение функциональных -возможностей генератора и повышения качества выходных последовательностей за счет введения нулевой комбинации в последовательность кодов и реализации подобных устройств для любого неприводимого примитивного характеристического многочлена.

Для достижения поставленной цели в генераторе, содержащем т-три1- герое, группу элементов ИЛИ, первую и вторую группы двухвходовых элементов И, генератор равновероятной двоичной цифры, группу (т + 1) входовых сумматоров по мощулю два, группу (т - 1 ) входовых элементов ИЛИ-НЕ, третью группу из m подгрупп по m двухвходовых элементов И, причем

К С-входам m триггеров и входу генератора равновероятной двоичной цифры подключен выход генератора тактовых импульсов, а единичный и нулевой выходы генератора равновероятной двоичной цифры подключены к первым входам первой и второй групп элементов И, выходы i-x элементов И первой и второй групп подключены ко входам I-го элемента ИЛИ, ко вторым входам первой и второй групп элементов И поданы значения коэффциентов принимающих величину нуля или единицы, выход i-ro элемента ИЛИ подключен к первому входу i-ro элемента И 1-й подгруппы третьей группы, выходы элементов И Е-Й подгруппы третьей группы и выход Е-го элемента ИЛИ-НЕ подключены ко входам В-го (т + 1) входового сумматора по модулю два, выход f-ro триггера подключен ко второму входу +1-1 -го элемента И m+E-1-ой подгруппы третьей / группы и к E+i-1-му входу т+1-Е-го элемента ИЛИ-НЕ, выход Е-го(т+1)входового сумматора по модулю два подключен к D входу В-го триггера ко второму входу В-i-ro элемента И i-ой подгруппы третьей группы и к i-ому входу -i-ro элемента ИЛИ-НЕ.

На фиг. 1 приведена функциональна схема генератора рандомизированных псевдослучайных чисел для случая, когда m 5, на фиг. 2 - функциональная схема генератора для m 3; на фиг. 3 - временная диаграмма работы генератора; на фиг. Ц - генератор равновероятной двоичной цифры.

Приведенная функциональная схема (фиг. 1) генератора для m 5, подобно как и в общем случае, состоящий изm D-триггеров 1, группы, элементов ИЛИ 2, первой и второй группы двухвходовых элементов И 3, . генератора 5 равновероятной двоичной цифры, группы (т+1) входовых сумматоров 6 по модулю два, группы (т-1) входовых элементов ИЛИ-НЕ 7 третьей группы из m подгрупп по m двухвходовых элементов И 8. Количество элементов ИЛИ 2, элементов И в первой и второй группах 3 и 4,(т + 1) входовых сумматоров 6 по модулю два, (т - 1) входовых элементов ИЛИ-НЕ 7 и триггеров 1 в группе равняется .т. Единичные выходы D-триггеров соединены со входами двухвходовых элементов И 8 третьей группы и входами элементов ИЛИ-НЕ. На выходах сумйаторов 6 по модулю два последовательно будут генерироваться т-разрядные коды псевдослучайных чисел двух М-последователь ностей, причем периоды обеих последовательностей одинаковы. Последовательность следования же кодов отлична и случайна как в первой,так и во второй М-последовательности. Таким образом, на выходе (пги-1)-входовых сумматоров 6 по модулю два (фиг. 1) генерируются тп-разрядные сегменты двух отличных М-последовательностей одинаковой длины. При фиксированном значении равновероятной двоичной цифры устройство представляет собой генератор псевдослучайных чисел, генерирующий на своем выходе m-разрядные псевдослучайные числа. При переменном значении двоич ной цифры в зависимости от -ее величины на выходе генератора равновероятной двоичной цифры, единичный выход которого подключен к первой группе элементов И 3, а нулевой - ко второй группе t (фиг. 1), код mразрядного псевдослучайного числа той или иной М-последовательности с выходов (т+ 1) входовых сумматоров 6 по модулю два записывается на Dтриггеры 1. Генератор 5 равновероятной двоичной цифры представляет собой простейший датчик равновероятной двоичной цифры, построенный на физических принципах. Устройство работает следующим образом. В начальный момент на D-триггеры 1 записывается произвольный код, в том числе и нулевой (фиг. 1) . На вы ходы элементов ИЛИ 2 проходят значе ния коэффициентов первого или второ го характеристического многочлена в зависимости от того, равняется единице или нулю величина (, на выходе генератора 5 в данный момент -време ни. В зависимости от значения вели чины с на выходах ( 1) входовых сумматоров по модулю два образуетс очередной m -разрядный код псевдослучайного числа первой или второй М-последовательности. По приходу та тового импульса на синхронизирующи входы триггеров 1 через их D входы на триггерах 1 запишется код, полученный на выходе сумматоров 6 по модулю два. С приходом очередного синхронизирующего импульса процесс повторяется. Подробный процесс генерирования псевдослучайных чисел рассмотрим на генераторе рандомизированных псевдослучайных чисел для т 3. Нь фиг.З а показана временная диаграмма синхронизирующих импульсов, по приходу которых триггеры устройства, меняют свое состояние; на фиг. 3 б - временная диаграмма на единичном выходе генератора; на фиг. ЗвиЗг приведены две М-последовательности. Стрелки с цифрами в кружках под ними означают последовательность переходов состояний триггеров 1 устройства. В первоначальный момент на триггерах записан код 101. Так как в момент времени t-i на единичном выходе генератора 5 находится единица (фиг. 3 б) , то через элементы И 3 и элементы ИЛИ 2 на входы элементов 8 подаются коэффициенты -jfg. С учетом конкретных значений коэффициентов Jg на выходах сумматоров 6 по модулю два очередное значение псевдослучайного числа убудет равняться 000.. По приходу тактового импульса в момент времени t/i на синхровходы -триггеров 1 и вход генератора 5 псевдослучайное число 6 запишется на триггеры 1 и равновероятная двоичная цифра с(, примет значение, равное нулю. После прохождения переходных процессов на выходах сумматорся 6 по модулю два устанавливается новое значение 2 101. В следующий момент времени на триггерах 1 запишется код 101, так как на единичном выходе генератора 5 находится ноль. Подобным образом триггеры меняют свое состояние в зависимости от значения на единичном выходе генератора 5 и по приходу последующих такТовых импульсов. На фиг. 3 в и 3 г стрелками показана граф-схема пере- , ходов состояний триггеров для моментов времени t,t,, t,... , ig. Из вышеприведенного описания функционирования генератора рандомизированных псевдослучайных чисел вытекают следующие факты. Значения псевдослучайных чисел на выходе генератора являются значениями кодов из двух отличных М-последовательностей. Нетрудно заметить, что при фиксированном значении нуля или единицы на выходе генератора 5. генератор рандомизированных псевдослучайных чисел будет функционировать как обычный генератор псевдослучайных чисел. А так как состояние генератора 5 случайно, то и порядок следо вания кодов М-последовательностей будет абсолютно случайным, причем выходным значением устройства с раз ной вероятностью может быть любой поразрядный код, в том числе и нуле вой. Подобный факт означает, что ав токорреляционная функция выходной последовательности имеет ненулевое значение только при i , где t - дли тельность выходного сигнала между очередными синхроимпульсами. Такой вид автокорреляционной функции полностью удовлетворяет требованиям, предъявляемым к последовательностям случайных чисел. Преимущества генератора рандомизированных псевдослучайных чисел заключается в следующем. Природа выходных псевдослучайных чисел максимально приближена к истинно случайным числам. В данном уст ройстве, подобно как и в прототипе, нарушего жесткое условие, что после определенного g должно следовать.заранее точно известное, так как f- может принимать равновероятно одно из двух значений. Возможность получения на выходе генератора кода псевдослучайн1рго числа равного 000...О приводит к выравниванию математического ожидания вероятности появления любого кода , которая в данном случае равняется P(f) 1/2 Таким образом, получение нулевой комбинации на выходе устройства расш ряет его функциональные возможности и обеспечивает повышение качества выходных последовательностей. Так автокорреляционная функция выходной последовательности при t f будет им

не значение равнулевое значение, а

ное 1/(2 - 1), что имеет место в прототие1е. Отсутствие запрещенных кодов € позволяет повысить надежность генератора, так как наличие нулевого кода на триггерах 1 не срывает генерирования псевдослучайной последовательности .

При практической реализации генератора рандомизированных псевдослучайных чисел оказывается возможным построение такого генератора для любого неприводимого примитивного характеристического многочлена. Поэтому для любого значения m, в том числе и для m 8, 12, 13, Н, 16, 19,

(Вероятностных характеристик.

Применение подобного генератора рандомизированных псевдослучайных чисел, отличающегося широкими функциональными возможностями, высокой надежностью функционирования и стабильностью его вероятностных характеристик, позволит повысить качество псевдослучайных последовательностей, а тем самым точность и достоверность решения задач методом Монте-Карло.

Кроме того, подобные устройства позволят получать истинно белый шум для построения генераторов случайных процессов. 68 , 26, 27, 29, 30, 32 и т.д., реализации генератора рандомизированных псевдослучайных чисел возможна. Кроме того, для конкретного значения TIB силу многообразия многочленов, позволяющих генерироватьМ-последовательности, войможно построение подобных устройств с одинаковой разрядностью выходных кодов равной т, что существенно расширяет его функциональные возможности. В процессе эксплуатации генератора рандомизированных псевдослучайных чисел возможно изменение М-последовательностей путем замены коэффициентов fg и Jg пораждающих их характеристических многочленов. Предлагаемый генератор отличается простотой технической реализации. Удельные аппаратурные затраты на один разряд псевдослучайного числа составят один (т+ 1) .входной сумматор по модулю два, один триггер, один элемент ИЛИ-НЕ, один элемент ИЛИ, m + 2 элементов И, и 1/т генератора равновероятной двоичной цифры. Генератор 5,применяемый в устройстве, может быть построен по самой простейшей схеме (например, триггер с коммутируемым питанием) , так как требования к равновероятности выходной двоичной цифры являются очень низкими. Пример подобного устройства, используемого изобретения, приведен на фиг. 4. Даже при отказе блока 5, т.е. когда на его выходе будет зафиксировано значение нуля или единицы, устройство в целом будет функционировать, но в этом случае будет равен 2 - 1, а не бесконечности. Этот факт говорит о надежности функционирования предлагаемого устройства и стабильности его формула изобретения Генератор псевдослучайных чисел, содержащий лп D -триггеров, группу элементов ИЛИ, первую и вторую груп пы элементов И, генератор равновероятной двоичной цифры, причем к синхровходам D-триггеров и входу генератора равновероятной двоичной цифры подключен выход генератора так товых импульсов, а единичный ,й нулевой выходы генератора равновероятной двоичной цифры подключены к первым входам элементов И первой и второй групп, выходы л-X ( 1, 2,..., т) элементов И первой и второй групп по ключены к входам л -го элемента ИЛИ, отличающийся тем, что, с целью расширения функциональных возможностей генератора за счет рас-,

ширения класса генерируемых псевдослучайных последовательностей чисел, он содержит группу (т+ 1) в ходовых сумматоров по модулю два, группу (on- 1) входовых элементов ИЛИ-НЕ и третью группу из m подгрупп по m элементов И, причем вторые входы элементов И первой и второй группы 9

Источники информации, принятые во внимание при экспертизе

Л., Машиностроение, 197t,

JjJLO

а

ti h Ь б fe 7 fe fff

92 706

п п п п п

-I-I-I-I-1-