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

ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советски кСфциалмстмчесиизРеспублик л 1903874(22) Заявлено 23.06.80 (21) 294с присоединением заявки И(23) П риоритет 51)М. Кл. 5038/1 8-2 606 Р 7 3 Ьвударстюай ком СССР ао делам изобрете к открытийублнкован Дата опубликования описания 07.02 8) Заявитель радиотехнический институ ПСЕВДОСЛУЧАЙНЫХ ЧИС 54) ГЕНЕР зависимостиио (от колиодом),начендляткриходуи - разИзобретение относится к вычислитель- ной технике и может быть использованов качестве устройства для получения случайных чисел при решении задач методомМонте-Карло, а также для построения генераторов случайных процессов с .заданными характеристиками. Весьма важнойобластью применения подобных устройствявляется область генерирования случайных процессов с равномерным спектром,используемых для идентификации системавтоматического управления,Известен генератор псевдослучайныхчисел, содержащий два регистра сдвигаи группу сумматоров по модулю цвай .Недостатком этого генератора является сложность структурного поСтроения,Кроме того, при построении генераторанеобходимо выбирать структуры исходныхгенераторов такими, чтобы их периодыявлялись взаимно простыми числами, чтоне всегда оказывается возможным,Наиболее близким по технической сущности к изобретению , вляется генератор псевдослучайных чисел, содержащий нтриггеров со счетным входом и м - сумматоров по модулю,два 1,21.Величина 1 выбирается вот разрядности регистра сдвигачества триггеров со счетным вхПодобный генератор предназгенерирования за один такт, потактового импульса, очередногорядного псевдослучайного числа, В отлита чие от известных устройств подобноготипа данный генератор отличается максимальным быстродействием и минимальными удельными аппаратурными затратами.В то же время он обладает одним сутдественным недостатком, который выражается в том, что не для любого ю оказывается известной величинаЦель изобретения - расширение функциональных возможностей генератора 20псевдослучайных чисел, что достигаетсявозможностью построения генератора длялюбого а и для любого неприводимогомногочлена при фиксированном ив .Поставленная цель достигается тем,что в генератор псевдослучайных чисел,содержащий м триггеров первой группы,дополнительновведены м триггеров второй группы,м групп элементов И и и 5ю-входовых сумматоров по модулю два,причем в каждой из и групп элементов Исодержится по м элементов И, выходыи элементов И -ой группы (1 =1, 2, ., м ) подключены к ивходам-госум- Оматора по модулю два, а к первому вхо ду 1-го элемента И-ой группы (=1,2, ,и) подключен единичный выход, -го триггера второй группы, а единич-.ный выход-го триггера первой группы 5подключен ко второму входу Я +.-1 )-гоэлемента И-ой группы, а выход 1-госумматора по модулю ава подключен ковторому входу -го элемента И ( +1) -ойгруппы; выход 1 -го сумматора по мо Одулю два подключен к 0 входу (ч.1-1)го триггера первой группы, к синхровходу которого подключен выход генераторатактовых импульсов, причем выходамиустройства являются выходысумматоров по модулю два, с которых по приходу тактового имлульса снимается очередНое псевдослучайное число, а 0, входытриггеров второй группы являются входом устройства. ЗОуНа фиг. 1 приведена общая функциональная схема генератора; на фиг. 2 -функциональная схема генератора прищ =3,=1, на фиг. 3 - последовательНость состояний триггеров известного и 35предлагаемого генераторов,Функциональная схема генераторапсевдослучайных чисел включает первуюгруппу ,из и триггеров 1, вторую группу из м триггеров ,и групп изавух 40входовых элементов И 3 и м ил -входовых сумматоров 4 по модулю ава, причемвыходы м элементов И.-ой группы 3подключены к м входам-го сумматора4 по модулю. два, к первому входу , -гоэлемента И 1 -ой группы 3 подключенединичный выход ( -го триггера второйгруппы 2, а выход 4-го триггера 1Первой группы подключен ко второму входу (а+ 8-1)-го элемента И 1 -ой группы3, а выход-го сумматора 4 по модулю два подключен ко второму входу 1 -гоэлемента И Я+1)-ой группы 3, выход-го сумматора 4" по модулю два подключен к Э входу (м+1-а)-го триггера 1 55первой группы, к синхровходу которогойодключен выход генератора тактовыхИмпульсов, причем выходами устройства являются выходы м сумматоров по модулю два, с которых по приходу тактового импульса снимается ,очередное псевдослучайное число, а ЙЗ входы триггероввторой группы 2 являются входами устройства,функционирование генератора псевдослучайных чисел происходит следующимобразом.В исходном состоянии на триггеры второй группы 2 по К 5 входам записываются значения коэффициентов, задающихструктуру цепи обратной связи регистрасдвига, а содержимое к-го разряда триггеров 1 первой группы может приниматьзначения нуля,или единицы. Запрещеннымявляется код, равный нулю, хранящийсяна триггерах первой группы 1, в противном случае последовательность кодов выражается в последовательность нулевыхкодов, В зависимости от коаов, хранящихся на триггервх 1 и 2 первой и второй группы на выходе комбинационнойчасти, состоящей из элементов И 3 исумматоров 4 по модулю ава формируется значение очередного кода. По приходутактового импульса значение очередногокоцо записывается на триггеры 1 первойгруппы. После прохождения переходныхпроцессов во всех цепях на выходе сумматоров 4 по модулю два получается значение очереаного. кода, таким образомна выходе устройства генерируется послеаовательность кодов м последовательности,На фиг. 3 приведена последовательность состояний триггеров первой группы.Анализируя эту последовательность можно заметить, что предлагаемый генератор1при=3 и=1 функционирует как иизвестный, В то же время структурагенератора, приведенного на фиг. 1 ифиг. 2,позволяет генерировать любыеипоследовательности на базе регистрасдвига определенной разрядности. Причем замена одной м последовательности на другую производится .путем перезаписи на триггерах второй группы новыхкоэффициентов, соответствующих новойпоследовательности, Возможность перезаписи коэффициентов позволяет генерировать произвольные ич последовательностии, таким образом, расширить функциональные возможности генератора псевдослучайных чисел.формула и з о б р е т е н и яГенератор псевдослучайных чисел, содержащий ич триггеров первой группы,5 903874 6о т л и ч а ю ш и й с я тем, что, с второму входу 3 -го элемента И ( + И- целью расширения функциональных возмож- ой группы, выход-го сумматора по ностей генератора за счет обеспечения модулю два подключен к О входу (и+1-) генерирования любой м последователь- -го триггера первой:группы,ксинхровходу ности, он содержиттриггеров второйкоторого подключен выход генератора группы, ю групп по и эпементов И в тактовых импульсов, причем выходами каждой группе и м сумматоров по моду- устройства являются выходы сумматоров лю два, выходы ю элементов И-ой, по модулю два, а входами 1,8 входы группы ( =1, 2, .,и) подключены к триггеров второй группы.ь входам Ф-го сумматора по модулю 1 О"два соответственно, к первому входу 1,- Ис точники информации,го элемента И-ой группы ( =1, 2 принятые во внимание при экспертизе и) подключен единичный выход-го 1. Яковлев В,В, и федоров Р.Ф. Ветриггера второй группы, единичный выход роятностные вычислительные машины, Л., 4-го триггера второй группы, единичный 15 "Машиностроение", 1974, с. 344., выход 1 -го триггера первой группы подключен ко второму входу ( + -1)-го 2.Авторское свидетельство СССР элемента И-ой группы, выход 1 -го % 572823, кл. 607 С 15/00, 1977 сумматора по модулю два подключен ко (прототип)903874 орректор А. Дзя Тираж 731 Пенного комитета СССРетений и открытийЖ, Раушская наб а, 4 оаписно 23/31 ВНИИПИ Госуаарств по аелам изоб 113035, Москва, ака П Патент", г, Ужг,"цул. Проектная, 4 и Составитель А. Карасоедактор Н. Лазаренко Техрел М. Надь