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

 

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

СОЮЗ СОВЕТСКИХ

-СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) П1) А1 (Si) S С 06 F 7/58

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

К А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ (21) 4688934/24 (22). 10.05.89 (46) 07.06.91. Бюл. Р 21 (71) Научно-исследовательский институт интроскопии Томского политехнического института им. С.М. Кирова (72) А.М. Носов (53) 681. 3 (088. 8) (56) Авторское свидетельство СССР

Ф 1529218, кл. С 06 F 7/58, 1987. (54) ГЕНЕРАТОР 11СЕВДОСЛУЧАЙНЫХ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано при решении задач методом МонтеКарло, имитации случайных процессов, статистическом моделировании. Цель изобретения — повышение надежности работы генератора за счет устранения соойных ситуаций. Генератор содержит группу 1 D-триггеров, коммутатор 2, генератор 3 равновероятного бинарного сигнала, генератор 4 тактовых импульсов, сумматор 5 по модулю два, группу

6 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент

7 задержки, первый 8 и второй 9 элементы И-НЕ и дополнительный D-триггер 10. Цель изобретения достигается введением элемента задержки, первого и второго элементов И-.НЕ, дополнительного 0-триггера с соответствующими а связями. 1 ил., табл. е

1654818

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

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

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

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

D-триггер 10. 20

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

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

Xg,)q ...,,Х „,лишь с определенных

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

Изменение этой структуры, т,е. пере35 ход к другому режиму работы генератора, отвечающему иному порождающему полиному, осуществляется путем подачи соответствующего сигнала на управлякМций вход коммутатора 2, являющегося 4 тем самым входом задания режима работы генератора.

Сигналы Х 1 „, X(8) Х(„) „, где

1, k могут быть найдены с помощью таблицы, с выхода коммутатора 2 посту-45 пают на входы сумматора 5 по модулю два, куда также подается сигнал В с прямого выхода дополнительного D-триггера 10. В результате на выходе сумматора по модулю два образуется сигнал Е = Х ) Э Хи) В Х< )

В повторяет сигнал Q образующийся на выходе генератора равновероятного бинарского сигнала, формирующего случайную последовательность, принймающую в произвольный момент времени с равной вероятностью два взаимных значения Q 0 и ) = 1, причем средняя частота их изменения должна быть несколько большей чем период M-последоваФ тельности 2 -1. Сигнал с выхода сумматора по модулю два подается на

D-вход первого триггера группы D-триггеров 1. Одновременно двоичный код, соответствующий записанному в группе

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

Ь rn -1 (2 -1)-2Х при Х (2

Щ (2Х -(2 — 1) при Х „2

F(x, ) Учитывая сигнал с выхода сумматора

5 по модулю два, получают, что в момент появления очередного тактового импульса от ГТИ 4 на инверсных выходах D-триггеров группы 1 формируется очередное псевдослучайное число в соответствии с соотношением хи+< =Р(х.)-z.+ =F(xï)-(xñ Охи) О

Q+X() ), где F (Х „) определяется формулой (1) .

Если вместо сигнала В + использовать непосредственно сигнал Q „+, с выхода ГРБС 3, то время от времени возвозможно возникновение сбойных ситуа.ций, связанных с появлением на выходе группы В-триггеров запрещенной кодовой комбинации. Такая кодовая комбинация может появиться вследствие влияния

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

Номер разрядов, подключения обратной связи (j 1, к) 4

7

9

11

12

13

14

1, 3, 4 или 2

1,3,4или1, 5, 6 или 2, 7 или 1, 4, 5, 1, 2, 5 или

1, 5, били 1, 1, 7, 8или1, 1, 9, 1Оили1

4, 8, 9 или 5, 2, 3, 5 или 1, 2, 11, 13 или

1, 14, 15 или 7, 9, или 2, или

1, 1 1, 16 или

6, 12

31

63

127

511

1023

2047

8191

16383

32767

2, 3, или 4, или 1,2,5 или2,4,6 или 1, 3, 4,или 2, или 4:.

4, 7, или 3, 7, 8

4, 5, или 7

2, 3, или 8

2, 3, или 5

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

2, 13, или 12

9, 12, 13, или 68,14

8, или 1,4,5, или 1,8, 14

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

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

ГРБС 3. В такой ситуации на очередном

5 такте работы запрещенная кодовая комбинация на выходе группы D-триггеров исчезает. Более того, изменяется состояние первого 8 и второго 9 элементов И-НЕ, в результате чего тактовые импульСы начинают проходить на тактовыц вход дополнительного триггера 10, этот триггер вновь начинает повторять сигнал с выхода ГРБС 3. Элемент 7 задержки необходим для устранения влияния задержки в появлении запрещающего сигнала на выходе второго элемента

И-НЕ 9, обусловленной переходными процессами в блоках 1 и 9. 20

В конечном итоге на инверсных выходах D-триггеров группы 1 образуются псевдослучайная апериодическая последовательность независимых равномерно распределенных m-разрядных 25 двоичных чисел, защищенная от появления аномальных участков, обусловленных появлением сбойных ситуаций.

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

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

D-триггеров группы,. а управляющий вход является входом задания режима работы генератора, генератор равно18 6 вероятного бинарного сигнала, генератор тактовых импульсов, выход которого соединен с тактовыми. входами

D-триггеров группы, сумматор по модулю два, первый вход которого под- . ключен к выходу коммутатора,а выход— к D-входу первого триггера группы, группу элементов ИСКЛЮЧАЮЦЕЕ ИЛИ, первый вход каждого i-ro элемента

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

D-триггера группы, а выход — с D-входом (i+1)-го D-триггера группы, вторые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ группы соединены с инверсным выходом тп-го 0-триггера группы, о т л и ч а ю шийся тем, что, с целью повышения надежности в работе генератора за счет устранения сбойных ситуаций, в него введены элемент задержки, первый и второй элементы И-НЕ и дополнительный D-триггер, причем вход элемента задержки подключен к выходу генератора тактовых импульсов, а выход соединен с первым входом первого элемента И-НЕ, второй вход которого соединен с выходом второго элемента

И-НЕ, входы которого подключены к инверсным выходам (m-1)-го и (m-3)-ro

D-триггеров группы,,выход первого элемента И-НЕ связан с тактовым входом дополнительного D-триггера, информационный вход которого подключен к выходу генератора равновероятного бинарного сиГнала, а прямой выход — к второму входу сумматора по модулю два °

1654818

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

17

18 19

21

22

1,14,15 или 1,З,ч, или 7

1, t0 11 или 1,7,8, или 12

2,5,7 или 3,5,6, или б

1,17,18 или t 3,4, или 2,16,18

1,19,20 или 1,2,3,или 4,16,20

1,21,22 или 2

1, 18, 19 или 1, 14, 15, или 1, 9, 10 ипи

3,7,8 или 2,3,5

1, 3, 4 или 1, 18, 19, или 1, 7, 8 > или 4

2,7,9 или 3, 5, 6

1,t9, и. 20 или 1,9, 10, или 1,7,8,или

1, 27, 28 или 1, 2, 3

2, 15, 17 или 3, 23, 24

4 или 1,7,8,или I 6,7,или 1,3,4

2,27, 29 или 3, 22, 23

20, 21 или 1, !3, 14

13107Т

262143

524287

2097151

4194303

8388607

24

26

27

16777216

33554431

67108863

134217727

268435455

53687091 t

1073741823

2147483647

8589934591

29

51

32

Составитель Г. Филаретов

Техред Л.Олийнык Корректор С.Шекмар

Редактор О. Головач

Заказ 1952 Тираж 399 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г Ужгород, ул. Гагарина,101