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

Изобретение относится к вычислительной технике и может быть использовано для вероятностного моделирова ния случайных перестановок. Известен .генератор случайного пот ка импульсов, содержащий источник пуассоновского потока импульсов, вероятностный (1,К)-полюсник, элементы И, блоки прореживания, элемент ИЛИ 1 . Наличие в этом устройстве большог числа блоков прореживания неоправдан усложняет его. Наиболее близким техническим решением к предлагаемому является генератор случайных послед9вательносте содержащий генератор тактовых импуль сов, счетчик, блок прореживания, ре гистр сдвига, вероятностный (1,К)-по люсник, элементы И, ИЛИ 2 . Однако этот генератор не может ге нерировать случайные перестановки, что ограничивает его функциональные возможности. Цель изобретения - расширение фун циональных возможностей генератора путем получения требуемых перестановок с заданными вероятностями. Для достижения поставленной, цели в генератор случайных последовательностей, содержащий генератор тактовых импульсов, элемент задержки, регистр сдвига, вероятностный (1,К)-полюсник выходы которого соединень с первыми входами соответствующих элементов И группь, выходы которых соединены с соответствующими входами первого элемента ИЛИ, введены второй элемент задержки, группа триггеров, группа стробированных шифраторов, блок индикации, выключатель, группа элементов задержки и второй элемент ИЛИ, выход которого соединен с входом Пуск генератора тактовых импульсов, выход которого подключен к входу Пуск вероятностного (1,К)-полюсника, выходы элементов И группы соединены с нулевыми входами соответствующих триггеров группы, выходы которых через соответствующие элементы задержки группы подключены к вторым входам соответствующих элементов И группы, выходы которых соединены с соответствующими входами каждого стробированного шифратора группы, выход первого элемента,ИЛИ соединен с входом Сдвиг регистра сдвига, выходы которого подключены к стробирующим входам соот1402 ветствующих стробированных шифраторов группы, выходы которых являются груп{ пой выходов генератора и соединены с соответствующими информационными входами блока индикации, вход Сброс которого объединен с входЪм Сброс вероятностного (1,К)-полюсника, входом Установка регистра сдвига, единичными входами триггеров группы и входом первого элемента задержки и подключен к выходу второго элемента задержки, вход которого объединен с входом Стоп генератора тактовых импульсов и подключен к последнему выходу регистра сдвига, выход первого элемента задержки соединен через выключатель с первым входом второго э.лемента ИЛИ, второй вход которого является входом Пуск генератора. На чертеже приведена блок-схема генератора. Генератор содержит вероятностный (1,К)-полюсник 1, группу элементов И 2,22,... ,2|, группу элементов З.З,. .. ,3; задержки, группу триггеров +-,,2 К и второй элементы ИЛИ 5 и 6, генератор 7 тактовых импульсов, выключатель 8, первый и второй элементы 9 и 10 задержки, регистр 11 сдвига, группу стробированных шифраторов 12 ,12,.. с , 12i блок 13 индикации, содержащий группу цифровых индикаторов 1 , ,. .., . Генератор случайных последовательностей работает следующим образом. В исходном состоянии генератор 7 тактовых импульсов выключен, ни на одном из входов вероятностного (1,К)-полюсника единичного сигнала нет, все триггеры t .,42 ,... ,( находятся в единичном состоянии, вследствие чего элементы И 2 ,22,... ,2| открыты, в блоке 13 индикации никакая информация не индицируется и на первом выходе регистра 11 сдвига имеется единичный сигнал, который подготовляет к срабатыванию первый стробированный шифратор 12 . Генератор может работать в двух режимах - автоматическом (выключатель 8 замкнут) и неавтоматическом (выключатель 8 разомкнут), В автоматическом режиме работы генератора после завершения каждого очередного цикла формирования случайного кода перестановок автоматически начинается следующий цикл В неавтоматическом режиме работы каждый очередной цикл формирования кода перестановок начинается по сигналу, подаваемому на вход Пуск генератора. Рассмотрим работу генератора в автоматическом режиме. Выключатель 8 в этом режиме замкнут, Первоначальный пуск генератора осу ществляется подачей единичного импульса на вход Пуск генератора. Этот импульс через элемент 6 ИЛИ поступает на включающий вход генератора 7 тактовых импульсов и включает его. Генератор 7 начинает формировать последовательность тактовых импульсов, которая поступает на вход Пуск вероятностного (1-,К)-полюсника 1. После каждого тактового импульса вероятностный (1,К)-полюсник 1 формиру ет единичный сигнал на одном из своих выходов с вероятностью , где i номер выхода вероятностного (1,К)-по люсника, i 1,К. Этот импульс, пройдя через соответствующий элемент И 2- поступает на i-e информационные входы всех стр бируемых шифраторов 12, 12,..., 12|, через элемент ИЛИ 5 поступает на сдв говый вход регистра 11 сдвига и переключает соответствующий триггер k в нулевое состояние. Поскольку в первом цикле работы генератора единичным сигналом с первого выхода регистра 11 сдвига открыт по стробирующему входу первый стробированный шифратор 12, сигнал с i-ro выхода вероятностного (1,К)-п люсника 1 шифруется первым стробированным шифратором 12, вследствие чего натуральное число сх. отображает ся в блоке 13 индикации первым цифро вым индикатором 1 в течение цикла работы устройства. Первый цифрговой -индикатор 14-) инд цирует в натуральном ряде чисел число , выпавшее первым в данном цикл формирования случайной перестановки из К чисел а,-с номерами i,i 1,К. Вследствие переключения триггера А. В нулевое состояние исчезает единичный сигнал на выходе триггера - , которыи снимается с входа элемента 3 задержки. По истечении заданной задержки сигнала, необходимой для за вершения всех переходных процессов в.схеме, исчезает единичный сигнал на выхьде элемента 3- задержки, вслед ствие чего закрывается элемент 2 . И и единичный-сигнал на его выхоДе исчезает. По этой причине исчезает сигнал на i-м входе элемента ИЛИ 5 и, следовательно, на его выходе и, в конечном счете, на сдвигающем входе регистра 11 сдвига. Сдвиг информации в последнем происходит по заднему фронту сдвигающих импульсов, Тов, при исчезновении импульсов на его сдвигающем входе. Таким образом, ... вследствие исчезновения единичного сигнала на выходе элемента И 2 единичный сигнал с первого выхода регистра 1 1 сдвига перейдет на второй, благодаря чему подготавливается к срабатыванию второй стробированный шифратор 12 , который сработает аналогично описанному после второго тактового им-, пульса на выходе генератора 7 тактовых импульсоВо В конце второго такта розыгрыша в блоке 13 вторым цифровым индикатором It индицируется число с(,-, выпавшее вторым в формируемой в данном цикле случайной перестановке. В конце t-ro такта t-м цифровым индикатором индицируется число а, выпавшее t-м в данном цикле розыгры-. ша и т.д. до ,после чего цикл формирования одной случайной перестановки кончается. Порядок выпавших чисел. т.е. собственно перестановка, инди- цируется всеми цифровыми индикаторами ,Ц,,. ,k блока 13 индикации. Кроме того, этот же порядок выпадаю- . щих чисел имеет место на выходах генератораИзвестно, что в перестановках каждое число может выпадать только один раз. Это обеспечивает на каждом выходе вероятностного (1.,К)-полюсника элементами И 2- 3,- задержки и триггером . Посла первого появления сигнала на i-м выходе вероятностного {1,К)-полюсника 1 закрывается элемент И 2-, который остается закрытым до конца цикла и не пропускает все последующие импульсы. Они будут холостыми, так как не вызовут в схеме никаких переключений.. .В конце цикла единичным сигналом с К-го выхода регистра сдвига останавливается генератор 7 тактовых импульсов непосредственно и через элемент 10 задержки сбрасывается вероятностный (1,К)-полюсник 1, устанавливается в исходное состояние регистр 11 сдвига и в единичное состояние, все триггеры 4-| ,2 ° к На этом цикл формирования одной случайной перестановки полностью за-i канчивается. Очередной цикл начинается по истечении задержки .времени, задаваемой элементом 9 задержки, по- 5 ка дачей сигнала на второй вход элемен та ИЛИ 6. Общее число перестановок определяется по известной формуле X И fljt (1) Х«1 Пусть Х-ая перестановка вид ) Ш tKf ,о...оу.-... (/ 15 где c(7.c, . выпавшие соответственно первым, вторым, третьим,..., t-M,..., К-м по порядку в Х-й перестановке. Вероятность Р выпадания Х-й пе- . лю рестановки Пх определится по формуле РХ,- ...PhH..) гие р(1) р(((-Ь)plK). где г% ,г. ,Гр,...,г гJJ вероятность выпадания чисел ,017 , соответственно ig ..., в первом, втором третьем,..,,t-M, К-м тактах Х-й перестановки. . Все первоначальные вероятности рИ1 р{1) pC-f) р(1/ рЬ) по CVг . ,г. ,...,г,...,Г(, по су ществу, есть вероятности Рд ,Pj ,Pg .,.,Pj,...,Pj,..., Pj появления единичных сигналов на выходах вероятК(1 но но 20 Пр во но ве

РХ 0,2 «0,375 0,2- 1 0,015 Аналогично можно рассчитать вероятности для всех перестановок и построить закон распределения вероятностей f(Х) для любых значений Pj, р. р р р

J gl « г f, . о . Гр.

Эффектом предлагаемого генератора является то, что он позволяет осуществлять вероятностное моделирование принципиально новых явлений - перестанорок, которые известными техническими решениями не моделировались. Рассмотрим конкретный пример для для случаев равновероятностного ,К)-полюсника 1 и неравновероятностго (управляемого) (1,К)-полюсни1. .- Если в схеме применен равновероятстный (1 ,К)полюсник 1, то имеём Р Р2 РЗ р - 0,25; pf 0,25 ,,333 . .а5.М 0,25 - 0,5 р 4 025 + РХ - 0,,333.-0,5 : ,417 i Пп и К i 1.2.3..24 При равновероятноЬтном (1,К)-поснике вероятности всех перестано0,, к одинаковы, т.е. Предположим, что применен нераввероятностный (1,К)-полюсник с роятностями Р 0,2, Р 0,3, РЗ 0,1, о,ц .з..о,, 0,37 ,1.М.О., 0,2 рИ.0,.§.0,/.

нз

-чм

G

1