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

 

СОЮЭ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

„„SU„„1038940 А з(ю G 06 F 7/58

1 4:, Ф2йй3иЮ4;Ю,ц . !

1

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

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ГЮ ДЕЛАМ ИЗОБРЕТЕНИЙ И Отнятий (21) 3385540/18-24 (22) 20.01.82 (46) 30.08.83., Бюл. и 32 (72) А.С."Б. Карасов . (71) Центральное проектно-конструкторское бюро по лифтам Всесоюзного промышленного объединения "Союзлифтмаш" (53) 681.3(088.8) (56) 1. Авторское свидетельство СССР

N 504196, кл. G 06 F 7/58, 1974, 2. Авторское свидетельство СССР

М 543004, кл. G 06 F 7/58, 1975 (прототип) . (54)(57) ГЕНЕРАТОР СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, содержащий генератор тактовых импульсов, элемент задержки, регистр сдвига, вероятностный(1,К)-по. люсник, выходы которого соединены с первыми входами соответствующих элементов И группы, выходы которых соединены с соответствующими входами первого элемента ИЛИ, о т л и ч а юшийся тем, что, с целью расширения функциональных возможностей генератора за счет.гюлучения требуемых перестановок с заданными вероятностями, он содержит второй элемент задержки, группу триггеров, группу стробированных шифраторов, блок индикации, выключатель, группу элементов задержки и второй элемент ИЛИ, выход

/ которого соединен с входом "Пуск" генератора тактовых импульсов, выход которого подключен к входу "Пуск" вероятностного (l Ê)-полюсника, выходы элементов И группы соединены с нулевыми входами соответствующих триггеров группы, выходы которых через соответствующие элементы задерж" ки группы подключены к вторым входам соответствующих элементов И группы, выходы которых соединены с соответствующими входами каждого стробированного шифратора группы, выход первого элемента ИЛИ соединен с входом

"Сдвиг" регистра сдвига, выходы которого подключены к стробирующим вхо" дам соответствующих стробированных шифраторов группы, выходы которых являются группой выходов генератора и соединены с соответствующими ин« формационными входами блока индикации, вход "Сброс" которого объединен с входом "Сброс" вероятностного (1,К)-полюсника, входом "Установка" регистра сдвига, единичными входами триггеров группы и входом первого элемента задержки и подключен к выходу второго элемента задержки, вход которого объединен с входом "Стоп" генератора тактовых импульсов и гюдключен к последнему выходу регистра сдвига, выход первого элемента,задержки соединен через выключатель с первым входом второго элемента ИЛИ, второй вход которого является входом

"Пуск" генератора.

1038940

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

Известен генератор случайного пото-5 ка импульсов, содержащий источник пуассоновского потока импульсов, вероятностный (1,К)-полюсник, элементы И, блоки прореживания, элемент

ИЛИ (1

Наличие в этом устройстве большого числа блоков прореживания неоправдано усложняет его.

Наиболее близким техническим решением к предлагаемому является ге. нератор случайных последовательностей, содержащий генератор тактовых импульсов, счетчик, блок прореживания, ре- гистр сдвига, вероятностный (1,К)-полюсник, элементы И, ИЛИ (2 ). 0

Однако этот генератор не может генерировать случайные перестановки, что ограничивает его функциональные возможности.

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

Для достижения поставленной цели в генератор случайных последователь- 30 ностей, содержащий генератор тактовых импульсов, элемент задержки, регистр сдвига, вероятностный (1,К)-полюсник, выходы которого соединены с первыми входами соответствующих элементов И группы, выходы которых соединены с соответствующими входами первого элемента ИЛИ, введены второй элемент задержки, группа триггеров, группа стробированных шифраторов, блок инди-40 кации, выключатель, группа элементов задержки и второй элемент ИЛИ, выход которого соединен с входом "Пуск" генератора тактовых импульсов, выход которого подключен к входу "Пуск" 45 вероятностного (1,К)-полюсника, выходы элементов И группы соединены с нулевыми входами соответствующих триггеров группы, выходы которых через соответствующие элементы задержки50 группы подключены к вторым входам соответствующих элементов И группы, выходы которых соединены с соответствующими входами каждого стробированного шифратора группы, выход первого элемента ИЛИ соединен с входом ",Сдвиг регистра сдвига, выходы которого подключены к стробирующим входам соответствующих стробированных шифраторов группы, выходы которых являются груп1 пой выходов генератора и соединены с соответствующими информационными входами блока индикации, вход "Сброс" которого объединен с входом "Сброс" вероятностного (1,К)-полюсника, входом "Установка" регистра сдвига, единичными входами триггеров группы и входом первого элемента задержки и подключен к выходу второго элемента задержки, вход которого объединен с входом "Стоп" генератора тактовых импульсов и подключен к последнему выходу регистра сдвига, выход первого элемента задержки соединен через выключатель с первым входом второго элемента ИЛИ, второй вход которого является входом "Пуск" генератора.

На чертеже приведена блок-схема генератора.

Генератор содержит вероятностный (1,К)-полюсник 1, группу элементов

И 2,22...,,2, группу элементов

3,32,...,3 задержки, группу триггеров 41,42,...,4k первый и второй элементы ИЛИ 5 и б, генератор 7 тактовых импульсов, выключатель 8, первый и второй элементы 9 и 10 задержки, регистр 11 сдвига, группу стробированных шифраторов 12„,12 ...,12 блок 13 индикации, содержащий группу цифровых индикаторов 14<, 14 >...., 14 ., Генератор случайных последовательностей работает следующим образом.

В исходном состоянии генератор 7 тактовых импульсов выключен, ни на одном из входов вероятностного (1,К)-полюсника единичного сигнала нет, все триггеры 4,42,...,4к находятся в единичном состоянии, вследствие чего элементы И 21,22,...,2K открыты, в блоке 13 индйкации никакая информация не индицируется и на первом выходе регистра 11 сдвига имеется единичный сигнал, который подго товляет к срабатыванию первый стробированный шифратор 12

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

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

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

Этот импульс через элемент 6 ИЛИ по- 1р ступает на включающий вход генератора 7 тактовых импульсов и включает

его.

Генератор 7 начинает формировать последовательность тактовых импульcos, которая поступает на вход "Пуск" вероятностного (1., К) -полюсни ка 1.

После каждого тактового импульса вероятностный (1,К)-полюсник 1 формирует единичный сигнал на одном из своих 2р выходов с вероятностью Р;, где номер выхода вероятностного (1,К)-по-. люсника, i = 1,К.

Этот импульс, пройдя через соответствующий элемент И 2. поступает

1 на 1-е информационные входы всех стробируемых шифраторов 12,12 ...,,12,, У через элемент ИЛИ 5 поступает на сдви. говый вход регистра 11 сдвига и переключает соответствующий триггер 4 в нулевое состояние.

Поскольку в первом цикле работы генератора единичным сигналом с первого выхода регистра 11 сдвига открыт по стробирующему входу первый стробированный шифратор 121, сигнал

35 с i-го выхода вероятностного (1,К)-полюсника 1 шифруется первым стробированным шифратором 121, вследствие чего натуральное число а.отображает- .

1 4Р ся в блоке 13 индикации первым цифровым индикатором 14„в течение цикла работы устройства.

Первый цифровой индикатор 141 индицирует в натуральном ряде чисел число с -, выпавшее первым в данном цикле

1У формирования случайной перестановки из К чисел с „- с номерами 1,i = 1,К.

Вследствие переключения триггера

4- в нулевое состояние исчезает еди1 ничный сигнал на выходе триггера 4;, который снимается с входа элемента

3- задержки, llo истечении заданной

1 задержки сигнала, необходимой для завершения всех переходных процессов в схеме, исчезает единичный сигнал на выходе элемента 3. задержки, вследствие чего закрывается элемент 2 „. И и единичный .сигнал на его выхоДе исчеэает. По этой причине исчезает сигнал на i-м входе элемента ИЛИ 5 и, следовательно, на его выходе и, в конечном счете, на сдвигающем входе регистра 11 сдвига. Сдвиг информации в последнем происходит по заднему фронту сдвигающих импульсов, т.е. при исчезновении импульсов на его сдвигающем входе. Таким образом, ! вследствие исчезновения единичного сигнала на выходе элемента И 2„ единичный сигнал с первого выхода регистра 11 сдвига перейдет на второй., благодаря чему подготавливается к срабатыванию второй стробированный шифратор 12, который сработает аналогично описанному после второго тактового им-. пульса на выходе генератора 7 тактовых импульсов. В конце второго такта

1 розыгрыша в блоке 13 вторым цифровым индикатором 14 индицируется число выпавшее вторым в формируемой в данном цикле случайной перестановке.

В конце й-го такта t ì цифровым индикатором индицируется число а выпавшее t-м в данном цикле розыгры- . ша и т.д. до t=K,после чего цикл фор" мирования одной .случайной перестановки кончается. Порядок выпавших чисел, т.е. собственно перестановка, инди-. цируется всеми цифровыми индикаторами

14, у14 e ° ° 14 блока 13 индикации.

Кроме того, этот же порядок выпадаю- .. щих чисел имеет место на выходах гене" ратора.

Известно, что в перестановках каждое число может выпадать только один раз. Это обеспечивает на каждом выходе вероятностного (1,К)-полюсника элементами И 2- 3; задержки и триггером 4..

После первого появления сигнала на i-м выходе вероятностного (1,К)-полюсника 1 закрывается элемент И 2., который остается закрытым до конца цикла и не пропускает все последующие импульсы. Они будут холостыми, так как не вызовут в схеме никаких переключений..В конце цикла единичным сигналом с К-го выхода регистра сдвига оста" навливается генератор 7 тактовых импульсов непосредственно и через элемент 10 задержки сбрасывается вероятностный (1,К)-полюсник 1, устанавливается в исходное состояние регистр

11 сдвига и в единичное состояние все триггеры 41,42..., 4, .

1038940

П К

На этом цикл формирования одной случайной перестановки полностью заканчивается. Очередной цикл начинается по истечении задержки .времени, задаваемой элементом 9 задержки, по- 5 дачей сигнала на второй вход элемент.а ИЛИ 6.

Общее число перестановок определяется по известной формуле

Х 10

Е (1)

Х 1

Пусть Х-ая перестановка имеет вид (1) (2). (Э) (Ц (К)

X l> j I e ." n -" In1.

Рассмотрим конкретный пример для

K 4 для случаев равновероятностного (1,К)-полюсника 1 и неравновероятностного (управляемого) (1,К)-полюсника 1. . Если в схеме применен равновероятностный (1,К полюсник 1, то имеем:

Р.) = Р2 РЭ Р4 0,25

Р2 0,25 + 0 75 . 0,25 0,333 (2) 0 25

Ф 1 (Э) 0 5

Р Э - 0,25 + 0 5 0,25 - 0,5

Ф (4) 0 75

Р4 = 0,25+--.0,25 - 1 ь (Э) ре p,.

1=1 рп+ -2. Р.

1=1 1p + - -; — - i (7) 45 (6) (), Pï (K) р

С1(1) д(2) с1® ц() а(") - числа, где С1 ., с ., с1...,,ц„...,, а чи сла,, е выпавшие соответственно первым, вторым, третьим,..., t-м,..., К-м по порядку в Х"й перестановке.

Вероятность Р„выпадания Х-й перестановки Пх определится по формуле

Р„. Р(+):. Р(2 . Р(Э) рф ..Рф (3) гд, р(1) р (2) Р(э) р(Ч . Р(к) (р) 25

0I 1,»»рcI » ° oI соответственно () (tI (к) и в первом„втором, третьем,..., t-м, К-м тактах розйгрыша Х-й перестановки

Все первоначальные вероятности

Р,р.,ре,...,рп,...,р к, по су (1! (,) („) (1),)

> ществу, есть вероятности Р1 Pj 1Pe, ...,Р,...,Рщ,...,РК появления еди" ничных сигналов на выходах вероят" ностного (1,K)-полюсника. З5 (К)

Вероятности Р .,Р . . .Р,,..., (2) (3 ) (t)

Р,„определяются соответственно по формулам (4) Рх - 0,25 0,333 0,5 ". 1 o,417

При К 4 -П х 1 2.3..4 24

При равновероятно тном (1,К)-полюснике вероятности всех перестановок одинаковы, т.е. — 4 0,417й Р

Предположим, что применен нерав- новероятностный (1,К)"полюсник с вероятностями

Р, = 0,2, Р 0,3, РЗ (2) 0,2

= 0 3 + - †Г- o,3 - o,375

Ф

Р4 =04+ - 04 1 (4) 0 6

Px = 0,2 0,375 ° 0,2 1 0,015

Аналогично можно рассчитать вероятности для всех перестановок и построить закон распределения вероятностей f(X) для любых значений Р„, Рj i Рею ° ° ° э Рпэ ° ° э Рп1»

Эффектом предлагаемого генератора является то, что он позволяет осуществлятb вероятностное моделирование принципиально новых явлений - перестановок, которые. известными техничес" кими решениями не моделировались.

1038940

Заказ 6231/55

Тираж 706 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4.Составитель В. Фукалов

Редактор И. Дубинин Техред И.Кузьма Корректор M. Демчик