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

, 1038 А 58 ЕНИ госуддрственный номитет сссрго делдм изОБретений и открытий ОПИСАНИЕ ИЗ АВТОРСКОМУ СВИДЕТЕЛЬСТ(71) Центральное проектно-конструкторское бюро по лифтам Всесоюзногопромышленного объединения "Союзлифтмаш"(56) 1. Авторское свидетельство СССРй 504196, кл. 6 06 Г 7/58, 1974,2. Авторское свидетельство СССРй 543004, кл. 6 06 Р 7/58, 1975(54)(57) ГЕНЕРАТОР СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, содержащий генератортактовых импульсов, элемент задержки,регистр сдвига, вероятностный(1,К)-по.люсник, выходы которого соединеныс первыми входами соответствующихэлементов И группы, выходы которыхсоединены с соответствующими входамипервого элемента ИЛИ, о т л и ч а ющ и й с я тем, что, с целью расширения функциональных возможностей генератора за счет получения требуемыхперестановок с заданными вероятностями, он содержит второй элемент за"держки, группу триггеров, группу стробированных шифраторов, блок индикации, выключатель, группу элементовзадержки и второй элемент ИЛИ, выход/которого соединен с входом "Пуск" генератора тактовых импульсов, выход которого подключен к входу "Пуск" вероятностного (1,К)-полюсника, выходы элементов И группы соединены с .нулевыми входами соответствующих триггеров группы, выходы которых через соответствующие элементы задерж" ки группы подключены к вторым входам соответствующих элементов И группы, выходы которых соединены с соответствующими входами каждого стробированного шифратора группы, выход пер" вого элемента ИЛИ соединен с входом "Сдвиг" регистра сдвига, выходы которого подключены к стробирующим вхо" дам соответствующих стробированных шифраторов группы, выходы которыхФявляются группой выходов генератора ,и соединены с соответствующими информационными входами блока индика- " Сф ции, вход "Сброс" которого объединен с входом "Сброс" вероятностного (1,К)-полюсника, входом "Установка" регистра сдвига, единичными входами триггеров группы и входом первогоэлемента задержки и подключен к вы- СО ходу второго элемента задержки, вход Я) которого объединен с входом "Стоп" ф генератора тактовых импульсов и под" ф, ключен к последнему выходу регистра сдвига, выход первого элемента,задержки соединен через выключатель с первым входом второго элемента ИЛИ, второй вход которого является входом "Пуск" генератора.Йзобретение относится к вычислительной технике и может быть исполь" эовано для вероятностного моделирования случайных перестановок.Известен .генератор случайного потока импульсов, содержащий источник пуассоновского потока импульсов, вероятностный (1,К)-полюсник, элементы И, блоки прореживания, элемент ИЛИ 11 ОНаличие в этом устройстве большого числа блоков прореживания неоправдано усложняет его.Наиболее близким техническим решением к предлагаемому является ге. нератор случайных последовательностей, содержащий генератор тактовых импульсов, счетчик, блок прореживания, ре- гистр сдвига, вероятностный (1,К)-полюсник, элементы И, ИЛИ 2 , 20Однако этот генератор не может генерировать случайные перестановки, что ограничиваетего функциональные возможности.Цель изобретения - расширение фунн 25 циональных возможностей генератора путем получения требуемых перестановок с заданными вероятностями.Для достижения поставленной цели в генератор случайных последователь ностей, содержащий генератор тактовых импульсов, элемент задержки, регистр сдвига, вероятностный (1,К)-полюсник, выходы которого соединены с первыми входами соответствующих элементов И группы, выходы которых соединены с соответствующими входами первого элемента ИЛИ, введены второй элемент задержки, группа триггеров, группа стробированных шиФраторов, блок индикации, выключатель, группа элементов задержки и второй элемент ИЛИ, выход которого соединен с входом "Пуск" генератора тактовых импульсов, выход которого подключен к входу Пуск 45 вероятностного (1,К)-полюсника, выходы элементов И группы соединены с нулевыми входами соответствующих триггеров группы, выходы которых через соответствующие элементы задержки 50 группы подключены к вторым входам соответствующих элементов И группы, выходы которых соединены с соответствующими входами каждого стробированного шифратора группы, выход первого элемента ИЛИ соединен с входом ",Сдвиг регистра сдвига, выходы которого подключены к стробирующим входам соответствующих стробированных шифраторов группы, выходы которых являются груп 1 пой выходов генератора и соединены с соответствующими информационными входами блока индикации, вход "Сброс" которого объединен с входом "Сброс" вероятностного (1,К)-полюсника, входом "Установка" регистра сдвига, единичными входами триггеров группы и входом первого элемента задержки и подключен к выходу второго элемента задержки, вход которого объединен с входом "Стоп" генератора тактовых импульсов и подключен к последнему выходу регистра сдвига, выход первого элемента задержки соединен через выключатель с первым входом второго элемента ИЛИ, второй вход которого является входом "Пуск" генератора.На чертеже приведена блок-схема генератора.Генератор содержит вероятностный (1,К)-полюсник 1, группу элементов И 21,222 К, группу элементов 3,1,331 задержки, группу триггеров 4,424, первый и второй элементы ИЛИ 5 и б, генератор 7 тактовых импульсов, выключатель 8, первый и второй элементы 9 и 10 задержки, регистр 11 сдвига, группу стробированных шифраторов 12блок 13 индикации, содержащий группу цифровых индикаторов 141 142 14 кГенератор случайных последовательностей работает следующим образом.В исходном состоянии генератор 7 тактовых импульсов выключен, ни на одном из входов вероятностного (1,К)-полюсника единичного сигнала нет, все триггеры 4 ,424 К находятся в единичном состоянии, вследствие чего элементы И 21,222 К открыты, в блоке 13 индйкации никакая информация не индицируется и на первом выходе регистра 11 сдвига имеется единичный сигнал, который подгоТовляет к срабатыванию первый стробированный шифратор 12Генератор может работать в двух режимах - автоматическом (выключатель 8 замкнут) и неавтоматическом (выключатель 8 разомкнут), В автоматическом режиме работы генератора после завершения каждого очередного цикла Формирования случайного кода перестановок автоматически начинается следующий цикл. В неавтоматическом режиме работы каждый очеред40 4 3 10389яой цикл Формирования кода перестановок начинается по сигналу, подаваемому на вход "Пуск" генератора,Рассмотрим работу генератора вавтоматическом режиме. Выключатель 8в этом режиме замкнут.Первоначальный пуск генератора осуществляется подачей единичного импульса на вход "Пуск" генератора,Этот импульс через элемент 6 ИЛИ по оступает на включающий вход генератора 7 тактовых импульсов и включаетего.Генератор 7 начинает формироватьпоследовательност ь тактовых импуль-.сов, которая поступает на вход "Пуск"вероятностного (1,К)-полюсника 1.После каждого тактового импульса вероятностный (1,К)-полюсник 1 Формирует единичный сигнал на одномиз своих 2 Овыходов с вероятностью Р;, гденомер выхода вероятностного (1,К)-полюсникд,= 1 К.Этот импульс, пройдя через соответствующий элемент И 2 поступаетна 1-е инФормационные входы всех стробируемых шифраторов 12 ,12 12Учерез элемент ИЛИ 5 поступает на сдви. говцй вход регистра 11 сдвига и переключает соответствующий триггер 4в нулевое состояние,Поскольку в первом цикле работыгенератора единичным сигналом с первого выхода регистра 11 сдвига открыт по стробирующему входу первыйстробированный шифратор 121, сигнал35с 1-го выхода вероятностного (1,К)-полюсника 1 шифруется первым стробированным шифратором 121, вследствиечего натуральное число с отображает1 40ся в блоке 13 индикации первым цифровым индикатором 14 в течение циклаработы устройства.Первый цифровой индикатор 14 индицирует в натуральном ряде чисел число с, выпавшее первым в данном цикле451 фформирования случайной перестановкииз К чисел с. с номерами 1,1 = 1,К,Вследствие переключения триггера4 в нулевое состояние исчезает единичный сигнал на выходе триггера 4;,который снимается с входа элемента3. задержки, По истечении заданнойзадержки сигнала, необходимой для завершения всех переходных процессовв схеме, исчезает единичный сигнална выходе элемента 3 задержки, вследствие чего закрывается элемент 2Ии единичный,сигнал на его выхоДе исчезает, По этой причине исчезаетсигнал на 1-м входе элементаИЛИ 5 и,следовательно, на его выходе и, вконечном счете, на сдвигающем входерегистра 11 сдвига. Сдвиг инФормациив последнем происходит по заднемуФронту сдвигающих импульсов, т.е. при исчезновении импульсов на егосдвигающем входе. Таким образом, вследствие исчезновения единичного сигнала на выходе элемента И 2 единичный сигнал с первого выхода регистра 11 сдвига перейдет на второй., благодаря чему подготавливается к сраба" тыванию второй стробированный шиФратор 12 , который сработает аналогично описанному после второго тактового им-, пульса на выходе генератора 7 тактовых импульсов, В конце второго такта /розыгрыша в блоке 13 вторым циФровым индикатором 14 индицируется число с, выпавшее вторым в формируемой в данном цикле случайной перестановке,В конце С-го такта С-м циФровым индикатором индицируется число сп, выпавшее С-м в данном цикле розыгры-. ша и т.д. до С=К,после чего цикл Фор" мирования одной .случайной перестановки кончается, Порядок выпавших чисел, т,е. собственно перестановка, индицируется всеми цифровыми индикаторами 1414 ,14, блока 13 индикации. Кроме того, этот же порядок выпадаю-,. щих чисел имеет место на выходах гене" ратора.Известно, что в перестановках каж" дое число может выпадать только один раз. Это обеспечивает на каждом выходе вероятностного (1,К)-полюсника элементами И 2 3; задержки и триггером 4После первого появления сигнала на 1-м выходе вероятностного (1,К)-полюсника 1 закрывается элемент И 2 который остается закрытым доконца цикла и не пропускает все последующие импульсы. Они будут холостыми,так как не вызовут в схеме никаких переключений..В конце цикла единичным сигналом с К-го выхода регистра сдвига оста" навливается генератор 7 тактовых импульсов непосредственно и через элемент 10 задержки сбрасывается вероятностный (1,К)-полюсник 1, устанавливается в исходное состояние регистр 11 сдвига и в единичное состояние все триггеры 41,424 к.1038940 5На этом цикл Формирования одной случайной перестановки полностью за- канчивается. Очередной цикл начинается по истечении задержки, времени, задаваемой элементом 9 задержки, по дачей сигнала на второй вход элемент.а ИЛИ 6.Общее число перестановок определяется по известной ФормулеХ 10Е: (1)Хщ 1Пусть Х-ая перестановка имеет вид(Э 1 (Ч (ЧХРп" в). Рассмотрим конкретный пример для К4 для случаев равновероятностного (1,К)-полюсника 1 и неравновероятностного (управляемого) (1,К)-полюсни ка 1.. Если в схеме применен равновероятностный (1 Ктполюсник 1, то имеем1 2 Э 4Р 2 0)25 + - - 0,25 й 0,333(Р 1 25 с в ..с( , а, соответственно ( 1 (М (к 1и " в первом втором, третьемй"м К-м тактах розйгрыша Х-й перестановки, Все первоначальные веро(ятностиР Р еР иР кпо сУ (1 (1 (1) (1 1ществу есть вероятности Р, )Р ,Рв ,РРРК появления едй" ничных сигналов на выходах вероят" ностного (1,К)"полюсника, 35 (К 1 Вероятности Рр р(21 (31 Я 1 Р, определяются соответственно по Формулам(к 1рго Рх 0250,333 0,5 ". 1 х 0,417При К 4 Е П х 1.2.3424При равновероятно 1 тном (1,К)-по люснике вероятности всех перестановок одинаковы, т.е. 40,417 й РПредположим, что применен нерав-новероятностный (1,К)"полюсник свероятностямиР, = 0,2, Р = 0,3,РЗ 01, Р О(41 0 6Рх = 0,20,375 0,21 0,015Аналогично можно рассчитать вероятности для всех перестановок и построить закон распределения вероятностей т(Х) для любых значений Р, Р 1 Р еРР)пЭффектом предлагаемого генератора является то, что он позволяет осуществлять вероятностное моделирование принципиально новых явлений - перестановок, которые. известными техничес" кими решениями не моделировались.1038940 Составитель В. ФукаловРедактор И. Дубинин Техред И.Кузьма Корректор ИМе Заказ 6231/55 5"Патент", г. ктная, 4 ал ород, ул Тираж 706 ВНИИПИ Государственного ко по делам изобретений и о 13035, Москва, Ж, РаушскПодписимитета СССткрытийая наб д