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

(19) 011 529218 06 Г 75 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЦТИПРИ ГКНТ СССР Г ПИСАНИЕ ИЗОБРЕТЕНИЯ с А ВТОРСНОМУ СВИД ЬСТ Сл Ю СО Ю т 1(71) Томский политехнический институт им. С. М. Кирова(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ(57) Изобретение относится к вычислительной технике и моЖет быть использова 2но при решении задач методом МонтеКарло, статистическом моделировании и т. д. Целью изобретения является повышение быстродействия. Генератор содержит группу 0-триггеров 1, коммутатор 2, генератор равновероятного бинарного сигнала 3, генератор тактовых импульсов 4, сумматор по модулю два 5, блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6. Генератор позволяет получать псевдослучайную апериодическую последовательность независимых равномерно распределенных т-разрядных случайных чисел Х в соответствии с рекуррентным соотношением, приведенным в описании изобретения. 1 ил, 1 табл.Изобретение относится к области вычислительной техники и может быть использовано при решении задач методом МонтеКарло, статистическом моделировании, имитации отчетных сигналов и т. д. 5Целью изобретения является повышениебыстродействия при получении многоразрядных псевдослучайных чисел.На чертеже представлена структурная схе -ма генератора.Генератор содержит группу 0-триггеров 1,коммутатор 2, генератор 3 равновероятного бинарного сигнала, генератор 4 тактовых импульсов, сумматор 5 по модулю два, группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6.Генератор работает следующим образом. 15 Пусть на и-м такте его работы в группе 0-триггеров 1 записано двоичное т-разрядное число Л,. Соответствующий этому числу двоичный код подается на информационные входы коммутатора 2. Коммутатор 2 передается на выход сигналы ХО)л,Х) лишь с определенных 0-триггеров группы, выбранных исходя из условия получения псевдослучайной последовательности максимальной длины при определенном виде порождающего полинома. В результате форми руется определенная структура обратной связи. Изменение этой структуры, т. е, переход к другому режиму работы генератора, отвечающему иному порождающему полиному, осуществляется после подачи соответствующего сигнала на управляющий вход ЗО коммутатора, являющийся тем самым входом задания режима работы генератора, Число выходных шин коммутатора 2, может изменяться от 1 до 3 в зависимости от используемого порождающего полинома.Сигналы ХО)л,Хи,)л с выхода коммута- Збтора 2, а также сигнал Я с выхода. генератора равновероятного бинарного сигнала 3 поступают на входы сумматора 5 по модулю два. Генератор равновероятного бинарного сигнала формирует случайную 40 последовательность, принимающую в произвольный момент времени с равной вероятностью два возможных значения: Я=О или Я=1, причем средняя частота изменений этих значений должна быть несколько большей, чем период М-последовательности, рав ный 2 л - 1. На выходе сумматора по модулю два образуется двоичный сигнал У=ХО)Р фХ)л Я, подаваемый на 0- вход первого триггера группы 0-триггеров 1.Двоичный код, соответствующий записанному в группе 0-триггеров 1 числу Л., подается также на входы блока ИСКЛЮЧАЮЩЕЕ ИЛИ, реализующего в обратном коде кусочно-линейную зависимость: д ,1 (2 - 1) - 2 Хл при Х(2(,2 Хл - (2 - 1) при Х)2 лДействительно, пусть Хл - двоичный код, снимаемый с инверсных выходов 0-триггеровна и-м такте Работы: Хл=ХлХ( - цл" ЛО)л где Х,)л - значение, имеющее место в с-м разряде кода, = 1,2, ,т; ХО)л=О или Х;)=1. Если Х )л= О, что соответствует выполнению условия Х(2 , то на вторых входах всех элементов ИСКЛЮЧАЮЩЕЕ ИЛИ блока 6 появится нулевой сигнал. Вследствие этого сигналы на выходах этих элементов будут повторять сигналы на их первых входах. Если пренебречь пока воздействием сигнала с выхода сумматора 5 по модулю два, это означает, что на 0-входах 0-триггеров будет иметь место кодовая комбинация: Х )лХ )лХцл 0. В момент появления тактового импульса от генератора 4 на тактовых входах 0-триггеров все они установятся в состояния, соответствующие сигналам на 0-входах. В результате на инверсных выходах 0-триггеров образует- сЯ кодоваЯ комбинациЯ Р(хе,) =,Х 1 ле,),Х Х Х( .,)ХрД 1, которую можно также представить в виде разноса двух кодов: Е(Х.) = В 1 - Х,Х .ХО. Так как первый.код соответствует значению 2 - 1, а второй 2 Л, то получаем, что в данном случае Р(Х.)=2 - 1 - 2 Лл. Если же У )л=1, что соответствует выполнению условия Х)2 , то на вторых входах всех элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6 появится единичный сигнал. Вследствие этого сигналы на выходах этих элементов будут инверсными по отношениюк сигналам на их первых входах. Опять временно пренебрегая сигналом с выхода сумматора 5 по модулю два, получим, чтос приходом тактового импульса от тактового генератора 4 на инверсных выходах 0- триггеров образуется кодовая комбинацияР(Хл)= Л(тл - )лЛ(тл - 2)л" ХО)л 1которую до бавляя еще один (т+М) разряд можно также представить в следующем виде:Е(Л л) = Л(л)лЛ(тл - )лЛ(а - 2)л".ЛО)лО -Х.)О О+ОО 1.Так как первая кодовая комбинация соответствует значению 2 Лл вторая равна 2 , а третья - единице, то в итоге получаем(Х.)=2 Х. - (2 - 1)Учитывая сигнал с выхода сумматора 5 по модулю два, получаем, что в момент появления очередного тактового импульса сгенератора 4 тактовых импульсов на инверсных выходах 0-триггеров группы 1 формируется очередное псевдослучайное число в соответствии с соотношением т=Р(Л,) -- Ел+ =Р(Хл) - (ХО)%Р)л Ял+ ГдЕ Р(Х) определяется указанной формулой.В результате на инверсных выходах 0-триггеров образуется псевдослучайная апериодичная последовательность независимых равномерно расположенных т-разрядных двоичных чисел.Ниже приведены некоторые вариантыподключения обратной связи.1529218 Формула изобретенияГенератор псевдослучайных чисел, содержит группу О-триггеров, инверсные выходы которых соединены с информационными входами коммутатора, управляющий вход кото рого является входом задания режима работы генератора, выход коммутатора подключен к первому входу сумматора по модулю два, генератор равновероятного бинарного сигнала и генератор тактовых импульсов, выход которого соединен с тактовыми входами б-триггеров группы, отличающийся тем, что, с целью повышения быстродействия, в него введена группа элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, причем первый вход каждого 1-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ группы соединен с инверсным выходом -го 0-триггера группы, а выход с 0-входом (+1) -го О-триггера группы (=1,2, т - 1) группы,т - число разрядов формируемого числа, вторые элементы ИСКЛЮЧАЮЩЕЕ ИЛИ групп соединены с инверсным выходом и-го 0-триггера группы, 0-вход первого триггера группы соединен с выходом сумматора по модулю два, второй вход которого соединен с выходом генератора равновероятного бинарного сигнала. У разрядов подключения обратной связи И=2 - 1 4 или 24 или 1, 2, 3 или 4 или 1, 2, 5били 2 или 2,4,61, 4, 5 или 1, 3, 4 или 2 или 45 или 1, 4, 7 или 3, 7, 86 или 1, 4, 5 или 78 или 1, 2, 3 или 810 или 1, 2, 3 или 59 или 5, 8, 9 или 5, 6, 95 или 1, 2, 13 или 1213 или 9, 12, 13 или б, 8, 1415 или 1, 7, 8 или 1, 4, 5 или 1, 8, 9 или1416 или б или 3, 6, 15 или 4, 6, 1215 или 1, 3, 4 или 71 1 или 1, 7, 8 или 127 или 3, 5, 6 или 618 или 1, 3, 4 или 2, 16, 1820 или 1, 2, Зили 4, 16, 2022 или 219 или 1, 14, 15 или 1, 9, 10 или 1, 5, 68 или 2, 3, 54 или 1, 18, 19 или 1, 7, 8 или 499 или 3, 5, 6и 20 или 1, 9 или 1, 7, 8 или 1, 3, 428 или 1,2,317 или 3, 23, 241, 7, 8 или 1, 6, 7 или 1, 3, 429 или 3, 22, 2321 или 1, 13, 14 15 31 63 127 255 511 1023 2047 4095 8191 16383 Составитель Г. ФиларетовРедактор О. Спесивых Техред И. Верес Корректор А. ОбручарЗаказ 7642/44 Тираж 668 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при 1 КНТ СССР113035, Москва, Ж - 35, Раушская наб., д. 4/5Производственно-издательский комбинат Патент, г. Ужгород, ул. Гагарина, 10 1, 3,1, 3,1 ф 57 или1, 2,1, 5,1, 7,1, 9,4, 8,2, 3,2, 11,1, 14,2 или1, 11,1, 14,1, 10,2, 5,1, 17,1, 19,1, 21,1, 18,3, 7,1, 3,2, 7,2, 7,1, 191, 27,2, 15,4 или2, 27,1, 20,32767655351310712621435242872048575209715141943038388607167772 1633554431671088631342177272684354555368709111073741823214748364742949672958589934591