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

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

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

На чертеже дана структурная схема .J генератора.

Генератор содержит группу 0-триг- геров 1, коммутатор 2, генератор 3 равновероятного бинарного сигнала (ГРБС), генератор 4 тактовых импуль- 1 сов (ГТИ), сумматор 5 по модулю два, группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6, элемент 7 задержки, первый 8 и второй 9 элементы И-ИЕ и дополнительный D-триггер 10,2

Генератор работает следующим образом.

Пусть на n-м такте его работы в группе D-триггеров занесено двоичное число Хп, которое подается на инфор- 2 мационный вход коммутатора 2. Коммутатор 2 передает на выход сигналы Х/лу. ,... ,Х /h лишь с определенных D-триггеров группы, выбранных исходя

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

Сигналы Х(1„ , Х(е1( , Х(к.ь, где j, I, k могут быть найдены с помощью таблицы, с выхода коммутатора 2 посту-4 пают на входы сумматора 5 по модулю два, куда также подается сигнал В с прямого выхода дополнительного D-триг- гера 10. В результате на выходе сумматора по модулю два образуется сиг- 5 нал Z ,® x(g)t,® х(к)ц®й Сигнал В повторяет сигнал Q, образующийся на выходе генератора равновероятного би- нарского сигнала, формирующего случайную последовательность, принимающую $ в произвольный момент времени с равной вероятностью два взаимных значения Q 0 иО, 1, причем средняя частота их изменения должна быть несколь3

ко большей, чем период М-последова- тельности 2 -1. Сигнал с выхода сумматора по модулю два подается на D-вход первого триггера группы D-триггеров 1. Одновременно двоичный код, соответствующий записанному в группе D-триггеров числу X,,, подается на входы группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6, реализующего в обратном коде кусочно- линейную зависимость

4

, hiш-1

(2 -О-2ХИ при Xh 2

тm-1

2XH-(2 -1) при .

Учитывая сигнал с выхода сумматора 5 по модулю два, получают, что в момент появления очередного тактового импульса от ГТИ 4 на инверсных выходах D-триггеров группы 1 формируется очередное псевдослучайное число в соответствии с соотношением

Xyu,F X« -Zn+rF V- Xcin

Чет1

0 ..

5 0 5

5

©W

где РСХ) определяется формулой (1).

Если вместо сигнала В 0+., использовать непосредственно сигнал Q п+1 с выхода ГРБС 3, то время от времени воз- возможно возникновение сбойных ситуа- .)ций, связанных с появлением на выходе (группы D-триггеров запрещенной кодовой комбинации. Такая кодовая комбинация может появиться вследствие влияния ГРБС 3 (без ГРБС ее появление невозможно) . Появление подобной запрещенной кодовой комбинации, если к тому же на очередном такте работы ГРБС 3 меняет свой сигнал на противоположный, то защищенная кодовая комбинация сохраняется в течение достаточного большого количества тактов работы, пока вновь не изменится сигнал на выходе ГРБС 3. Для исключения подобных сбойных ситуаций используются вновь введенные элементы 7-10. Второй эле- мент И-НЕ 9 при появлении на его входе запрещенной кодовой комбинации формирует на своем выходе нулевой сигнал, закрывая тем самым первый элемент И-НЕ 8 и не пропуская задержанные элементом 7 задержки тактовые импульсы от ГТИ 4 на тактовый вход дополнительного D-триггера. В результате наличия запрещенной кодовой комбинации сигнал на выходе дополнительного D-триггера 10 не изменяется, даже если изменился сигнал на выходе ГРйС 3. В такой ситуации на очередном такте работы запрещенная кодовая комбинация на выходе группы D-триггеров исчезает. Более того, изменяется состояние первого 8 и второго 9 элементов И-НЕ, в результате чего тактовые импульсы начинают проходить на тактовый вход дополнительного триггера 10, этот триггер вновь начинает повторять

вероятного бинарного сигнала, генератор тактовых импульсов, выход которого соединен с тактовыми входами D-триггеров группы, сумматор по модулю два, первый вход которого подключен к выходу коммутатора,а выход - к D-входу первого триггера группы, группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ,. первый вход каждого 1-го элемента

ИСКЛЮЧАЮЩЕЕ ИЛИ (где m - число разрядов формируемого числа) группы соединен с инверсным выходом 1-го D-триггера группы, а выход - с D-вхо

Изобретение относится к вычислительной технике и может быть использовано при решении задач методом МонтеКарло, имитации случайных процессов, статистическом моделировании. Цель изобретения - повышение надежности pa-i боты генератора за счет устранения сбойных ситуаций. Генератор содержит группу 1 D-триггеров, коммутатор 2, генератор 3 равновероятного бинарного сигнала, генератор 4 тактовых импульсов, сумматор 5 по модулю два, группу 6элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент 7задержки, первый 8 и второй 9 элементы И-НЕ и дополнительный D-триг- гер 10. Цель изобретения достигается введением элемента задержки, первого и второго элементов И-НЕ, дополнительного D-триггера с соответствующими связями. 1 ил., 1 табл.

сигнал с выхода ГРБС 3. Элемент 7 за- Д°м (i+1)ro D-триггера группы, вто- держки необходим для устранения влия- рые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ ния задержки в появлении запрещающего группы соединены с инверсным выходом сигнала на выходе второго элемента га-го D-триггера группы, о т л и - И-НЕ 9, обусловленной переходными про- чающийся тем, что, с целью цессами в блоках 1 и 9.20 повышения надежности в работе генераВ конечном итоге на инверсных вы- тора за счет устранения сбойных ситу- ходах D-триггеров группы 1 образуются псевдослучайная апериодическая последовательность независимых равномерно распределенных га-разрядных двоичных чисел, защищенная от появлеаций, в него введены элемент задержки, первый и второй элементы И-НЕ и

дополнительный D-триггер, причем вход 25 элемента задержки подключен к выходу генератора тактовых импульсов, а выход соединен с первым входом первого элемента И-НЕ, второй вход которого соединен с выходом второго элемента 30 И-НЕ, входы которого подключены к инверсным выходам (га-1)-го и (тп-З)-го D-триггеров группы, выход первого элемента И-НЕ связан с тактовым входом дополнительного D-триггера, информационный вход которого подключен к выходу генератора равновероятного бинарного сигнала, а прямой выход - к второму входу сумматора по модулю два.

ния аномальных участков, обусловленных появлением сбойных ситуаций.

Формула изобретения

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

ли 2

1,9, 10 или 1, 2, 3, или 5

4,8, 9 или 5, 8, 9, или 5, 6,

2,3, 5 или 1, 2, 13, или 1

2,11, 13 или 9, 12, 13, или 6,8,14 1,14,15 или 7,8, или 1,4,5, или 1,8,

9,или 2, или 14

1,11, 16 или 6, или 3, 6, 15, или 4,

6,12

или 14

или 6, или 3, 6, 15, или 4,

тора за счет устранения сбойных ситу-

аций, в него введены элемент задержки, первый и второй элементы И-НЕ и

тора за счет устранения сбойных ситу-

дополнительный D-триггер, причем вход элемента задержки подключен к выходу генератора тактовых импульсов, а выход соединен с первым входом первого элемента И-НЕ, второй вход которого соединен с выходом второго элемента И-НЕ, входы которого подключены к инверсным выходам (га-1)-го и (тп-З)-го D-триггеров группы, выход первого элемента И-НЕ связан с тактовым входом дополнительного D-триггера, информационный вход которого подключен к выходу генератора равновероятного бинарного сигнала, а прямой выход - к второму входу сумматора по модулю два.

15

31

63

127

255

511

1023

2047

4095

8191

16383

32767

65535

16548188

Продолжение таблицы

17 18 19 20 21 22 23

24 23 26 27 28

29 Ю Я 2 i3

13107Т

262143

524287

2048575

2097151

4194303

8388607

16777216

33554431

67108863

134217727

268435455

536870911 1073741823 2147483647 4294967295 858 934591