Генератор псевдослучайных чисел Советский патент 1981 года по МПК G06F1/02 G07C15/00 

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

Изобретение относится к вычислительной технике и может быть использовано в качестве устройства для получения случайных чисел при решении задач методом Монте-Карло, а также для построения генераторов случайных процессов с заданными характеристика ми. Известен генератор псевдослучайHfcJx чисел, содержащий регистр сдвига с сумматором по модулю два в цепи обратной связи l. Недостатком такого генератора является наличие периода в формулируемой последовательности. Известно также устройство, в кото ром для приближения свойств псевдослучайных чисел к свойствам истинно случайных, полученных физическими способами, период повторения последо вательности увеличен до величины . однако периодичность в указанном устройстве сохраняется. . Наиболее близким к предлагаемому является генератор псевдослучайных чисе.л, содержащий первую и вторую группы двухвходовых сумматоров по МО дулю два, первую и вторую группы эле ментов И, группу элементов ИЛИ, труп пу триггеров и генератор равновероятной двоичной цифры. Подобный генератор предназначен для генерирования за один такт двух т-разрядных псевдослучайных чисел 3 . Недостаток рписанного устройства отличие вероятности появления нуля или- единицы в. разрядах чисел от 0,5 по обоим каналам. Так, вероятность появления нуля или единицы в любом I разряда псевдослучайного числа по обоим каналам определяется из выражений. РСОк-О-- 2..,. j 1 (у,-0) Jг 2 Известно, что построение таких высокоэффективных устройств, какие приведены в 2, имеет смысл при небольших значениях величины..1п. В этеял случае выражение К характеризующее отклонение от равновероятности, принимает значение, величина которого в ряде случаев оказывается недопустимой. Даже при , ,001. Цель изобретения - повышение точности генератора за счет приближе7

ния вероятности нуля.или единицы в разрядах псевдослучайности чисел по первому и второму каналам к 0,5. Поставленная цель достигается тем, что генератор, содержащий первую и вторую группы двухвходовых сумматоров по модулю два, первую и вторую группы трехвходовых сумматоров по модулю два, первую и вторую группы элементов И, группу элементов ИЛИ, группу триггеров и генератор равновероятной двоичной цифры, ко входу которого подключен выход генератора тактовых импульсов, а единичный и нулевой выходы генератора равновероятной двоичной цифры подключены к первым входам первой и второй групп элементов И соответственно, второй вход m-j младших элементов И первой группы подключен к выходам m-j младших двухвходовых сумматоров по модулю два первой группы, второй вход j младших двухвходовых сумматоров по модулю два второй группы, выходы i-X элементов И первой и второй группы подключены ко входам i-го элемента ИЛИ, выход которого подключен ко входу i-го триггера, к первым входам i-x двухвходовых сумматоров по модулю два первой и второй групп подключены единичные выходы i-X триггеров, ко вторым входам m-2j младших двухвходовых сумматоров по модулю два первой группы подключены выходы m-2j . старших сумматоров по модулю два первой группы, выход генератора тактовых импульсов подключен к синхровходам триггеров, содержит первую группу из j трехвходовых сумматоров по модулю два и вторую группу из m-j трехвходовых сумматоров по модулю два, к первым входам, i-X трехвходовых сумматоров по модулю два первой и второй групп подключены единичные выходы (m-j+i)«x и {j+l)x триггеров, соответственно, вторые входы j трехвходовых сумматоров по модулю два первой группы подключены к выходам j младших триггеров, вторые входы m-j трехвходовых сумматоров по модулю два второй группы подключены к выходам m-j младших триггеров, третьи входы j трехвходовых сумматоров по модулю два первой группы подключены к нулевому выходу генератора равновероятной двоичной цифр1, третьи входы j трехвходовых сумматоров по модулю два второй группы подключены к единичным выходам генератора равновероятной цифры, выходы j трехвходовыЗс сумматоров по модулю два первой группы подключены соответственно ко вторым входам j старших двухвходовых сумматоров по модулю два первой группы, а выходы j старших трехвходовых сумматоров по модулю два второй группы подключены соответственно ко вторым входам j младших двухвходовых сумматоров по модулю два второй группы, кроме того, выход 1-го трехвходового сумматора по модулю два первой группы подключен ко второму входу (m-j+i)-ro элемента И первой группы, выход f-го трехвходового суммаJ тора по модулю два второй группы псздключен ко второму входу (j-H)-ro элемента И второй группы.

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

В общем случае генератор псевдослучайных чисел состоит из m триггеров 1, m элементов ИЛИ 2, первой группы Ki элементов И 3, второй группы m элементов И 4, генератора 5 равновероятной двоичной цифры, первой группы m-j двухвходовых сумматоров б по 1модулю два, второй группы j двухвходовых сумматоров 7 по модулю два, первой группы j трехвходовых сумматоров 8 по модулю 8, второй группы m-j трехвходовых сумматоров 9 по модулю два.

Количество двухвходовых сумматоров по модулю два в первой группе равняется m-j, а во второй группеJ . В тоже время количество трехвходовых сумматоров по модулю два в первой и второй группе равняется j и m-j соответственно. На выходах двухвходовых и трехвходовых сумматоров по модулю два первых групп получаются значения псевдослучайного числа 1 а , а2,...,а а на вы::одах вторых групп получаются значения псевдослучайного числа , , .. . ,а. Числа Ё1 и 2 представляют собой тразрядные коды или их инверсии Мпоследовательностей/ порождаемых слу-. чайными полиномами Ч(2) и Ч (г), причем периоды обо- их последовательностей одинаковы.

5 Последовательность следования кодов отлична и случайна как в первой, так и во второй М-последовательности. Появление прямого кода М-последовательности или его инверсии по первому и

0 второму каналу определяется значением очередного отсчета на выходе генератора равновероятной двоичной цифры. Выходы D-триггеров и генератора равновероятной цифры соединены со

5 входами трехвходовых сумматоров по моду;во два первой и второй группы согласно выражениям;

aw-i()--bw.it«)®b.it)® ©x(),(3)

«LH-

-b.W©b.()®

5 ©xU),bo.n«.j-i,(4) где b .(k) - значение на единичном выходе (m-i)-ro триггера в k-ый такт рабо ты устройства V x(k) иx(k) - значения на единичном и нулевом выходах генератора равновероятной двоичной цифры; а (k) и а (k) - значения на выходах У1И tn-4 трехвходовых сумматоров по модулю два пер вой и второй группы; знак ® означает операцию суммирования по модулю два. Выходы D-триггеров и выходы сумматоров по модулю два соединены со входами двухвходовых сумматоров по модулю два первой и второй групп со ласно выражениям ,-i((. ) °n,.iW-brt.iW®a2..w,i--K,q;T;r (ь При использовании выражений (3)(б) для организации связей в генераторе псевдослучайных чисел-для ну мерации сумматоров по модулю два пе вых групп и вторых групп используются единые сквозные нумерации.Для случая , на выходы сумматоров по модулю два. На фиг.1 представлены связи в соответствии с системой ,ЭЪ,©Я i Qg --Ьв®а а5- 5®%;а4-Ч® I . (7 по первому каналу и в соответствии с системой а1--ЦфЬб©X;ag--b6®b,.®x; а с|4Ь4©Ц®х, а5--Ь,,®ЬдФх, ©цех; а,--Ц©а {) по вторюму каналу, в зависимости от значения равновероятной двоичной цифры на выходе генератора 5 равновероятной двоичной цифры код псевдослучайного числа f 1 или t 2 с сумматоров по модулю два через элементы ИЛИ 2 записывается на О-триггеры Генератор 5 представляет.собой простейший датчик равновероятной двоичной цифры, построенной на физических принципах . Генератор псевдослучайных чисел работает следующим образом. Э начальный момент на D-триггеры 1 записывается ненулевой код (фиг.1 На выходах сумматоров 6 и 8 по модулю два образуется очередной код псевдослучайного числа первой М-последовательности в том случае, если x(k) в данный момент времени равияется О, а на выходе сумматоров 7 и 9 по модулю два образуется обратный код псевдослучайного числа. второй М-последовательности, так как xTk). В случае, когда x(k)l, на выходе блоков 6 и 8 образуется обратный код, в котором проинвертированы зна- чения разрядов псевдослучайного числа, а на выходе блоков 7 и 9, соответственно, прямой, так как xTk)0. В зависимости от значения очерёдной двоичной цифры на выходе генератора 5x(k),l по приходу тактЬвого импульса на синхронизирующие входы триггеров 1 на их входы через первую или вторую группы элементов И 3 и 4 и через элементы ИЛИ 2, объединяющие выходы обоих групп И, подается очередной код первой или второй М-последовательности . С приходом очередного тактового импульса процесс повторяется. На Фиг.3 для каждого такта работы k 1,10 показаны соответствующие значения выходных псевдослучайных чисел I 1 и 2 и содержимое триггерного регистра Ife(k). В первоначальный момент на триггерах записан код 0001,а значения 1(1)0000 и 2(1) 1001, причем felecTb инвертированный код первой М-последовательности, так как х(1)0. По приходу тактового импульса на триггеры записывается код числа &2 (1), таким образом во втором такте исходной информацией для формирования t1 (2) (2) является 1001. Так как х(, то 1( 2) принимает неинвертированное значение кода первой М-лоследовательности, а 2(2)инвертированное значение кода второй М-последовательности. В следующий момент (k) содержимое триггерного регистра принимает значение 1000. Подобным образом тригге-ры меняют свое состояние в зависимости от значения x(k) на выходе генератора равновероятной двоичной цифры по приходу последующих импульсов. Из описанного выше следует, что значения | 1 и 2, генерируемые на выходах первой и второй групп сутиматоров по модулю два, в каждый конкретный такт являются значениями кодов или их инверсий из двух отличных Мпоследовательностей. fel принимают значения из двух различных М-последовательностей ( но имеющих одинаковый состав кодов), порядок последования которых случаен. Автокорреляционная функция выходных последовательностей по обрим каналам имеет ненулевое значение только при , где Т - длительность выходного сигнала между очередными тактовыми импульсами. Вероятность появления нуля или единицы на выходе любого разряда псевдослучайного числа по любому канаду определяется вероятностью равенства единице суммы по модулю два псевдослучайной последовательности с последовательностью отсчетов равновероятной двоичной цифры.Это следует из такого факта, что выражение для формировани значения любого разряда выходного пс вдослучайного числа по обоим каналам на основании (3)-1б представляется в виде выражений a|(k) ac(k)e)x(k) , I 1m; (9) aV (k)ag(k)®x(k) , 1 П1,(10), где так, например, для a, b- ®bg©x ag©x . Здесь в преобразованиях используется свойство сдвига сложения М-последовательности. Таким образом, вероятность появле ния нуля или единицы на выходе любог разряда псевдослучайного числа по лю бому каналу определяется следующим о разом. р(аг-) --PCas©x--i) -Р{а5©к-1) PCQ4)- cigX: i) Cii) Учитывая, что ад их независимы, выражение (11)принимает вид Р((ав-о)Р(х-1)(ад--.1)Р{х-о --95Анализ выражения (12) показывает/ что вероятность появления единицы или нуля на выходе генератора отличается от 0,5 на величину где И„- отклонение от 0,5 вероятности появления единицы на выходе генератора равновероятной двоичнрй цифры. Так как величина Vjy 0, 01 - 0,001 для известных устройств tll то значение Р() незначительно отличается от 0,5. Таким образом, вероятност появления нуля или единицы в разряда псевдослучайных чисел по обоим кана лам в предлагаемом устройстве макси мально приближена к 0-, 5, Для случая , величина, характеризующая откло нение от 0,5, равна О ,00001-0,000001 Таким образом, природа выходных псевдослучайных последовательностей максимально приближена к истин но слу чайным числам. Предлагаемый генератор отличается простотой техйической реализации. Удельные аппаратные затраты на один разряд псевдослучайн го числа составляют один элемент И, элемента ИЛИ, двухвходового сумматора по модулю два, - трехвходового сумматора по модулю два, - тригге ра и - генератора равновероятной двоичной цифры.Предлагаемый генератор псевдослучайных чисел позволяет получать числа по двум каналам. Применение предлагаемого генератора псевдослучайных чисел позволяет повысить точность и достоверность решения задач методом Монте-Карло. Кроме того, подобные устройства позволяют получать истинно белый шум для построения генератора случайных процессов. Формула изобретения Генератор псевдослучайных чисел, содержащий первую группу из m-j двухвходовых сумматоров по модулю два, вторую группу из j двухвходовых сумматоров по модулю два, первую и вторую группы элементов И, группу элементов ИЛИ, группу триггеров и генератор равновероятной двоичной цифры, ко входу которого подключен выход генератора тактовых импульсов, а еди ничный и нулевой выходы генёратРора равновероятной двоичной цифры подключены к первым входам элементов И первой и второй групп соответственно вторые входы m-j младших элементов И первой группы подключены, соответственно, к выходам m-j двухвходовых сумматоров по модулю два первой группы, вторые входы j младших элементов И второй группы подключены соответственно к выходам j младших двухвходовых сумматоров по модулю два второй группы, выходы 1-X элементов И первой и второй групп подключены к соответствуквдим входам i-ro элемента ИЛИ, выход которого подключен ко входу i-ro триггера, к первым входам i-x двухвходовых сумматоров по модулю два первой и второй групп подключены соответственно единичные выходы i-x триггеров, вторые входы m-2j младших двухвходовых сумматоров по модулю два первой группы .подключены соответственно к выходам т-2j старших сумматоров по модулю два первой группы, выход генератора тактовых импульсов подключен к синхро входам триггеров, отличающийся тем, что, с целью повышения точности генератора, он содержит первую группу из j трехвходовых сумматоров по модулю два и вторую группу из m-j трехвходовых сумматоров по модулю два, к первым входам i-x трехвходовых сумматоров по модулю два первой и второй групп подключены единичные выходы (m-j+i}-x и (j+ +i)-x триггеров, соответственно, вторые входы j трехвходовых сумматоров по. модулю два первой группы подключены к выходам j млсшших триггеров, вторые входы m-j трехвходовых сумматоров по модулю два второй группы подключены к выходам m-j младших триггеров, третьи входы j трехвходовых сумматоров по модулю два первой группы подключены к нулевому выходу генератора равновероятной двоичной цифры, третьи входы j трехвходовых сумматоров по модулю два второй группы подключены к ieдиничнoму выходу генератора равновероятной двоичной цифры, выходы j трехвходовых сумматоров по модулю два первой группы подключены соответственно ко втором входам j старишх двухвходовых сумматоров по модулю два первой группы, а выходы j трехвходовых сумматоров по модулю два второй группы подключены соответственно ко вторым входам j младших двухвходовых сумматоров по модулю два второй группы, кроме того, выход -го трехвходового сумматора по модулю два первой группы подключен ко второму входу + u-ro элемента И первой группы, выход 1-го трехвходового сумматора по модулю два второй группы подключен ко второму входу (j+i)-ro элемента И второй группы.

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

с.344..

кл. G 06 F 1/02, 1978 (прототип).

Х() f/ГЛ) f2(k)