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

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

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

.ЭВМ, что позволит увеличить производительность вычислительных средств; при решении определенного круга задач .

Известен генератор псевдослучайных чисел, содержи.щий два регистра сдвига и группу сумматоров по модулю два С1Д.

Недостатками генератора псевдо10случайных чисел являются сложность аппаратурного построения, а также усложненная методика синтеза. Кроме Того, в ряде случаев построения подобных генераторов псевдослучай15ных чисел оказывается невозможным, так структура исходных генераторов псевдослучайных чисел используемых при построении генератора, должна быть такой, чтобы их пег

20 риоды являлись взаимно простыми числами, что далеко не всегда выполняется.

Паргшлельный генератор псевдослучайных чисел Cl отличается.максимаЛь

25 ным быстродействием. .

Сложность схем формирования сдвинутых последовательностей определяется числом входов сумматоров по модулю два. Каждый сумматор в сред30нем имеет т/2 входов. При этом

затраты, идущие на построение схем формирования сдвинутых последовательностей, в несколько раз превышают затраты, идущие на построение кольцевого регистра сдвига, состоящего из m разрядов i

Известен также генератор псевдослучайных чисел, позволяющий получать последовательности: псевдослучайных чисел, максимально близкие по природе к истинно случайным числам. Его техническая реализация осушествляется при малых удельных аппаратурных затратах С2).

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

Известен генератор псевдослучайных чисел, который позволяет получить на выходе код псевдослучайного ;числа равного 000...О, что приводит iK %ыравни ванию математического ожи : Дания вероятности появления любого кода З .

Недостаток этого генератора заключается в большой аппаратурной сложности. Удельные аппаратурные затраты на- один разряд псевдослучайного числа составляют один (т+1)входовый сумматор по модулю два,, один триггер, одну схему ИЛИ-НЕ,од. ну схему ИЛИ, т + 2 схемы п и 1/т генератор равновероятной двоичной цифры. Кроме того, подобный генератор должен иметь в своем состав два регистра для хранения коэффициентов Ye Р еНаиболее близким к изобретению является генератор псевдослучайных чисел, содержащий tn триггеров, первую и вторую группы по т-2 элементов ИЛИ, первый и второй элемент НЕ, группу из гп - 2 элементов ИЛИ-Н группу из m сумматоров по модулю два 4.

В данном устройстве предусмотрена возможность получения на выходе генератора комбинации 000.,. .0 что приводит к выравниванию вероятности появления кода , (fuJ которая для любого ||j равняется . Таким образом, закон распределения выходных последовательностей в данном устройстве является равномерным, так как вероятность появления на его выходе любого кода одинакова и равняется 1/2. Последовательности, генерируемые на выходе рассмотренного устройства, относятся к клас су так называемых последовательностей де Брюйна (de Bruijn) или циклами де Брюйна. Введение нулевой

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

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

Поставленная цель достигается тем, что генератор псевдослучайных чисел, содержащий генератор тактовы импульсов, группу из тп(тп 1,2,... число разрядов генератора ) D-триггеров, первую группу из m сумматоров по. модулю два и первую группу из двух элементов НЕ, причем выход генератора тактовых импульсов подключен к С-входам Р-триггеров группы, а выход i-го ( ) D-триггера группы подключен к первому .входу 1 -го Сумматора по модулю два первой группы, введены две группы по m элементов И, вторая группа из m сумматоров по модулю два, вторая группа из т- 1 элементов НЕ, группа из m элементов 2И-ИЛИ, генератор равновероятной двоичной цифры, кроме того, в первую группу элементов, НЕ дополнительно введено т-2 элементов НЕ, причем к D-входу i-го D-триггера подклн)чен выход i-ro элемента 2 И-ИЛИ группы, нy Jeвoй выход 1-го ( ) 1,т- 1) D-триггера подключен к входам m- J старших элементов И первой группы, выход (j+1)го элемента НЕ первой группы подключен соответственно к входам j младших элементов И первой группы, выход i-го элемента И первой группы подключен к второму входу i-го сумматора по модулю два первой группы, к третьим входам п( Уп 7/.1/2 m ) старших сумматоров по модулю два первой группы подключены eд ничныe выходы младших D-триггеров группы соответственно, а к третьим входам младших сумматоров по модулю два первой группы подключены выходы ni-t старших сумматоров по модулю два первой группы соответственно, выходы m трехвходовых сумматоров по модулю два первой группы подключены к входам ш элементов НЕ первой группы соответственно, выход j-го элемента НЕ первой группы подключен к соответствующим входам т- j старших элементов И второй группы, выход j -го элемента НЕ второй группы под-. ключей к соответствующим входам j лшадших элементов И второй группы, выход i-ro элемента И второй группы подключен к первому входу i-го су№ атора по модулю два второй группы, к второму входу которого подключен выход 1 -го сумматора по модулю два первой группы, к третьим входам п старших сулотаторов по модулю два второй группы подключены выходы Т1 младших сумматоров по модулю два первой группы соответственно, а к третьим входам m -л младших сумматоров по модулю два второй группы подключены выходы m -п ста ших сумматоров по модулю два первой группы соответственно, выходы то - 1 ставших сумматоров по модулю два второй группы подключены квходам .т - 1 элементов НЕ второй группы соответственно, кроме того, к перво му и второму входам i-ro элемента 2 Иг-ЛЛИ группы подключены выходы -го сумматора по модулю два первой и второй групп соответственно, к трет ему и четвертому входу элементов . 2 И-ИЛИ группы подключены единичный и нулевой выходы генератЬра равновероятной двоичной цифры соответственно, к входу которого подключен выход генератора тгистовых импульсов выходы сукматоров по мсдулю два вто рой группы являются выходами генератора. На фиг. 1 приведена функциональная схема генератора; на фиг. 2 и 3 .схемы генератора тактовых импульсов и-ггенератора равновероятной двоичной цифры; на фиг. 4 - временная диаграмма его работы. Генератор псевдослучайнькчисел со держит D -триггеров 1, две группы по m элементов И 2 и 3, две группы по -п суъматоров по модулю два 4 и 5, первую группу из m элементов НЕ 6, вторую группу из m - 1 элемента НЕ 7., груп пу из m элементов 2 И-ИЛИ 8, генератор 9 ргшневероятней двоичной цифры, генератор. 10 тактовых импульсов. Функционирование генератора паев дослучайных чисел происходит следую ИЕим образом. В иачальнь1й момент на 1) -триггеры 1 записывается произвольный код .0 , в том числе и нулевой. На выходах сумматоров по модулю два первой группы 4 формируется m-разрядный код , который является продол жением кода §0 в соответствии с заданной м-последовательностыо зяд М-последовательиости определяется полиномом if(x) 1+XJ + х), а на выходах элементов 5 - код 2 являющийся продолжением кода . По приходу тактового импульса на синхронизирующие входы D -триггеров 1 ; выходов элементов 8 наD -триггеры 1 записывается код, полученный на выходе сумматоров 4 илн 5, т.е. или 2 приходом очередного синхронизирующего импульса процесс повтор яется, Более подробно процесс генерирования псевдослучс1йных чисел поябняется на конкретном примере. На фиг.1 приведена функциональная схема генератора псевдослучайных чисел для m 5 и для 0,ct.2 О, с.з 1, оСц. О, «365 1, а на фиг. 3 - временная диаграмма его работы. На фиг. 3 показана последователь- ность, генерируемая на выходе обычного последовательного генератора псевдослучайных чисел, построенного согласно следующему поражДакицему полиному f{x) 1+х + х. Фигурными скобками обозначены сегменты М-последовательности, которые могли быть сформированы на выходе рассматриваемого генератора псевдослучайных чисел в зависимости от значений равновероятной двоичной цифры.. Сплошными стрелками с подписякш показана последовательность состояний на выходе устройства в зависимости от конкретных значений х(1с} и штриховьвш стрелками - возможные значения на выходе устройства в случае инверсных значений х(1(). В первоначальный момент времени на триггерах записан код 11011. В соответствии с кодом 11011 на выходах сулматрров,4 формируется код 10101 и на выходе устройства (сумматор/. 5) -.код 0 10000. Так как, например, значение х(0) в нулевой момент равняется 1, по приходе синхроимпульса на D-триггеры записывается код 10101. После прохождения переходных процессов на выходах сумматоров 4 . Сформируется код 10000, а на выходе устройства - 1сод§,, 1.0100. В следующем такте на В -триггеры за- пишется код 10100, так как значение -х С 1 0. Подобным образом D-триг геры меняют свое состояние в зависимости от значения .на выходе генератора 9 рсшнрвероятности двоичной цифры и по приходе последую|цих тактовых импульсов. На фиг. 3 сплошными стрелками, показана последовательность выходных кодов рассматриваемого устройства для х(0) -I, х(1) - О, х(2) - 1, .х(3) - 1 . Поскольку состояние генератора равновероятной двоичной цифры случайно, .поряДок следования кодов Мпоследовательностей также абсолютно случаен, причем выходным значением устройства с равной вероятностью может быть любой т-разрядный код, том числе и нулевой. Преимущество предлагаемого генератора псевдослучайных чисел заключается в следующем. Природа выходных псевдослучайных чисел, подобно как и в устройс вах 23 и ГЗ, максимально прибл жена к истинно случайным числам. В данном устройстве также нарушено жесткое условие, что после определенного-1j должно следовать 1+ за ранее точно известное, так как в данном случае может принимать равновероятное одно из двух значе НИИ.. В отличие о устройства {.2 J На выходе рассматриваемого генератора псевдослучайных чисел возможно пол чение кода 000... О, что приводит к выравнр1ванию математического ожида ния вероятности появления любого ч кода 5 , которая в данном случае равняется Р() Отсутствие запрещенных кодов позволяет повысить надежность генератора псевдослучайныхчисел, так как, подобно -устройствам 3 и 4 J, наличие нул вого кода на триггерах не срывает нерирования псевдослучайной последовательности, Предлагаемый генератор псевдослу чайных чисел отличается простотой технической реализации. Удельные аппаратурные затраты на один разряд псевдослучайного числа составят оди D-триггер, один элемент 2 И-ИЛИ, дв трехвходовых сумматора по модулю два, два (т- 1)-входовых элементов два элемента НЕ и генератор равновероятной двоичной цифры, что. значительно меньше соответствующих затрат в устройстве С4. В сравнении с базовым объектом генератором псевдослучайных чисел предлагается устройство, отличающееся рядом преимуществ. Во-первых cBoflCTBa выходной последовательност получаемой на выходе рассматриваемого, генератора, значительно лучше СВОЙСТВ последовательностей, получа емых на выходе базового объекта. Т период выходных последовательностей в предлагаемом автором устройстве равен со, а вероятность появления любого кода равняется Р()-щВо-вторых, введение нулевой комбина ции позволяет существенно увеличить надежность предлагаемого устройства в сравнении с базовым объектом. Применение подобного генератора псевдослучайных чисел, отличающегос широкими функциональными возможностями, высокой Надежностью функционирования и стабильностью его вероя ностных характеристик, позволит повысить качество псевдослучайных последовательностей, а тем самым тгочность и достоверность решения задач методом Монте-Карло. Кроме того, подобные устройства позволяют получать истинно белый шум для построения генераторов случайных процессов и могут быть использованы в качестве внешнего устройства серийно выпускаемых ЭВМ. Формула изобретения Генератор псевдослучайных чисел, содержащий генератор тактовых импульсов, группу из m(m - число разрядов генератора) D - триггеров, первую группу из m (умматоров по модулю два и первую группу из двух элементов НЕ, причемвыход генератора тактовых импульсов подключен к С-входам р -триггеров группы, а выход i-го ( l,tn )1)-триггера группы подключен к первому входу i-го сумматора по модулю два первой группы, отличающийся тем, что, с целью расширения функциональных возможностей за счет улучшения корреляционных свойств генератора, дополнительно введены две группы по m элементов И, группа из гл сумматоров по модулю два, вторая Ipynna из m - 1 элементов НЕ, группа из m элементов 2 И-ИЛИ, генератор равновероятной двоичной цифры, кроме того,в первую группу элементов НЕ дополнительно введено т- 2 элементов НЕ,причем к D -входу i-го D-триггера подключен выход i -го элемента 2 И-ИЛИ группы, нулевой выход j-ro (j l,m- I)i3 -триггера подключен к входамш- j старших элементов И первой группы, выход (j + i)-то элемента НЕ первой группы подключен к соответствующим входам j младших элементов И первой группы, выход i-ro элемента И первой группы подключен к второму входу i-го сумматора по модулю два первой группы, к третьим входам h (п / 1/2 т) старших сумматоров по модулю два первой группы подключены единичные выходы п младших D-триггеров группы соответственно, к третьим входам .щ -п младших сумматоров по модулю два первой группы подключены выходы ш - п старших сумматоров по модулю два первой группы соответственно, выходы m трехвходовых сумматоров по модулю два первой группы подключены к входам тп элементов НЕ первой группы соответственно, выход j-го элемента НЕ первой группы подключен к соответствующим входам m -j старших элементов И второй группы, выход j -го элемента НЕ второй группы подключен к соответствующим ;входам J младших элементов и второй группы, выход 1-гЪ элемента И второй группы подключен к первому входу 1-го сумматора по модулю два второй группы, к второму входу которого подключен выход i-го сумматора по модулю два первой группы, к третьим входам п старших сумматоров по модулю два второй группы под ключены выходы п младших сумматоров по модулю два первой группы соответственно, а к третьим входам гп-п младших сумматоров по модулю два второй группы подключены выходы i-и старших сумматоров по модулю два первой труппы соответственно, выход m - 1 старших сукиаторов по модулю два второй группы подключены к вхо дам т- 1 элементов НЕ второй группы соответственно, кроме того, к первому и второму входам -то элемента 2 И-ИЛИ группы подключены выходы -го сумматора по модулю два первой и второй групп соответствен но, к третьему и четвертому входам элементов 2 И-ИЛИ группы подключены единичный и нулевой выходы генератора равновероятной двоичной цифры соответственно, ft входу которого подключен выход генератора тактовых импульсов, выходы сумматоров по модулю два второй группы являются выходами генератора. Источники информации, принятые во внимание при экспертизе 1.Яковлев В.В. и Федоров Р.Ф. Вероятные вычислительные машины.Л., Машиностроение, 1974, с. 344. 2.Авторское свидетельство СССР № 708381,-кл. GI 07 С 15/00, 1980. 3.Авторское свидетельст во СССР по заявке 2988394/18-24, кл. G 06 F 7/58, 16.04.80. 4.Авторское свидетельство СССР по заявке № 2920810/18-24, кл. G 06 F 7/58, 26.11.80 (прототип).

Xf2)f

X(

В J оп, .IJJL JJLM . j о о о ц, 1$ k h i 1 i

Фиг. 3

Ul.