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

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Свез СоветсиикСоциалистическиеРвслублии(23) Приоритет 39 вударетееевй кюнтвт СССР йв делан нэебветекиЯ н еткрытнЯ(72) Авторы изобретения В.Н, Ярмолик, А.Е. Леусенко и А.Н. Морозевич Минский радиотехнический институт(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ 1Изобретение относится к вычислительной технике и может быть использовано в качестве устройства для получения случайных чисел при решении задач методом Монте-Карло, для построения генераторов случайных процессовс заданными характеристиками, а также для генерирования случайных процессов с равномерным спектром, используемых для идентификации системавтоматического управления,тоИзвестен генератор псевдослучайныхчисел, содержащий два регистра сдвигаи группу сумматоров по модулю два Щ,Недостатком этого генератора явля 15ется сложность структурного построения, методика синтеза подобного генератора псевдослучайных чисел значительно затруднена . Кроме того, дляпостроения генератора псевдослучай.ных чисел необходимо выбирать такиеструктуры исходных генераторов, у ко"торых периоды являются взаимно простыми числами. Известен также параллельный генератор псевдослучайных чисел, которыйотличается максимальной величинойбыстродействия и позволяет формироватьмногоразрядные псевдослучайные числа 121,Недостаток этого генератора заключается в сложности схем формированиясдвинутых прследовательностей, определяемой числом входов сумматоров помодулю два. Каждый сумматор в среднем имеет е/2 входов. При этом затраты оборудования, необходимые длясхем формирования сдвинутых последовательностей, в несколько раз превышают затраты, идущие на построениекольцевого регистра сдвига.Наиболее близким техническим решением к предлагаемому изобретениюявляется генератор псевдослучайныхчисел, содержащий в-разрядный регистрсдвига, два элемента И и элемент ИЛИ,которые реализуют операцию сложенияпо модулю два содержимого в-го и -горазряда регистра сдвига. Номер 1-го разряда в зависимости от разрядности регистра сдвига в выбирается из таблицы 3 .Недостатком этого устройства является отличие вероятности появления нуля или единицы на его выходе от 0,5Цель изобретения - повышение точности генератора. 10Пост а вленная цел ь дости гает ся т ем, что в генератор псевдослучайных чисел, содержащий щ-разрядный регистр сдвига, первый элемент И, к первому входу которого подключен инверсный 15 выход в-го разряда регистра сдвига ВС, второй элемент И, к первому входу которо го под ключе н прямой выход а- го разряд ре ги стра сдвига, элемент ИЛИ, выход которого подключен ко вхо-, 20 ду первого разряда регистра сдвига, дополнительно введены третий элемент И, четвертый элемент И и элемент ИЛИ-НЕ, причем ко вторым входам первого и второго элементов И подклюце- д 5 ны инверсный и прямой выходы 1-го разряда регистра сдвига соответственно, а выходы первого и второго элементов И пддключены к первому и второму входам элемента ИЛИ-НЕ, ко входам четвер- З 0 т о го эле мент а И под ключе ны и н версные выходы апервых разрядов регистра сдвига, а -выход четвертого элемента И подключен к третьему входу элемента ИЛИ-НЕ и к первому входу третьего эле. ме нт а И, ко второму входу которо го35 подключен инверсный выход в-го разря-да. ре ги стра сд ви га, выход элемент а ИЛИ-НЕ подключен .к первому входу элемента ИЛИ, ко второму входу которого40 подключен выход третьего элемента И.На фиг. 1 приведена функциональная схема генератора; на фиг. 2 - последовательность состояний известного (а) и предлагаемого (б) генераторов прищ=3 иГенератор состоит из регистра сдвига 1, первого, второго и третьего элементов И 2, 3, 4, четвертого элемента И 5, элемента ИЛИ-НЕ 6, и элемента ИЛИ 7. К первому входу первого элемента И 2 подключен инверсный выход в- го разряда регистра сдвига 1, к первому входу второго элемента И 3 подключен прямой выход а-го разряда регистра сдвига 1, а выход элемента ИЛИ 7 подключен ко входу первого разряда регистра сдвига 1, Ко вторым входам пер во го и второго зле ме нт а И 2 и 3 подключены инверсный и прямой выходы 1-го разряда регистра сдвига 1соответственно, а выходы первого ивторого элементов И 2 и 3 подключенык первому и второму входам элементаИЛИ-НЕ 6, ко входам четвертого элемента И 5 подключены инверсные выходы01-1 первых разрядов регистра сдвига 1,а его выход подключен к третьему входу элемента ИЛИ-НЕ 6 и первому входутретьего элемента И 4, ко второму входу которого подключен инверсный выходв-го разряда регистра сдвига 1, выходэлемента ИЛИ-НЕ 6 подключен к первомувходу элемента ИЛИ 7, а ко второмувходу элемента ИЛИ 7 подключен выходтретьего элемента И 4,Генератор работает следующим образом.В исходном состоянии регистр сдвига содержимое Е-го разряда может принимать значение нуля или единицы. Вотличие от известных генераторов вданном генераторе в первоначальныймомент в разрядах регистра 1 может находиться нулевой код. В зависимостиот начального кода на выходе комбинационной части, т.е, на выходе элемента ИЛИ 7, формируется символ, равный нулю или единице. По приходу тактового импульса содержимое регистрасдвига 1 сдвигается на один разрядвправо, а в первый разряд записывается символ, сформированный на выходеэлемента ИЛИ 7, При значениях содержимого первых вразрядов регистрасдвига 1, отличных от нуля, элементы 2, 3, 6 и 7 реализуют операцию суммирования по модулю два содержимого 1-го и щ-го разрядов регистров сдвига, В этом случае генерируется И-последовательность, как и в известном. Далее, при появлении в первых щ разрядах регистра 1 нулевой ко;бинации на выходе элемента 5 появляется единичный уро вен ь, который обеспе ци вает появление на входе первого разряда регистра сдвига 1 нуля.При поступлении очередного тактового импульса в регистре сдвига 1 находятся нулевые значения во всех разрядах. Появление нуля в в-ом разряде обеспечивает появление единицы на выходе элемента 4, которая через элемент 7 поступает на вход первого разряда ре,истра сдвига 1. Очередной тактовый импульс обеспечивает появление в регистре .сдвига 1 комбинации 1000, т,е. нулей во всех разрядах, кромеФормула изобретения 011 1 Р 1 01 д О 1 Р ОО 100 110 00 ОО 1 РО 110 Фи 2 ВНИИПИ Заказ 11007/78 Тираж 748 Подписно иал ППП"Патент", г. Ужгород,ул. Проектная,4 5 89039 первого. Далее, так же как и известном, генерируется М-последовательность. В этом случае содержимое первых вразрядов регистра сдвига 1 отлично от нуля и элементы 2, 3, 6 и 7 реализуют 3 операцию суммирования по модулю два,Как видно из фиг. 2 последовательность на выходе предлагаемого генератора отличается от М-последовательности, полученной на выходе известного толь ко кодом 000, следующим после кода 001. Введение нулевой комбинации в М- последовательность позволяет приблизить вероятность нуля и единицы к 0,5. В силу того, что количество нулей и единиц в выходной последова тельности генератора равняется 2 , а количество символов 2, вероятность нуля и единицы на выходе системы равняется 0,5. Кроме того, дополнительные затраты оборудования составляют всего три логических элемента.Применение подобного генератора псевдослучайных чисел позволит, повысить качество псевдослучайных последовательностей, а тем самым точность и достоверность решения задач методом Монте-Карло. Генератор псевдослучайных чисел, содержащий в-разрядный регистр сдвига, И первый элемент И, к первому входу ко 1 4т орого подключен инверсный выход в- горазряда регистра сдвига, второй элемент И, к первому входу которого подключен прямой выход в-го разряда регистра сдвига, элемент ИЛИ, выход которого подключен ко входу первого разряда регистра сдвига, о т л и ч а ющ и й с я тем, что, с целью повышения точности генератора, он содержиттретий элемент И, четвертый элементИ, элемент ИЛИ-НЕ, причем ко вторымвходам первого и второго элементов Иподключены инверсный и прямой выходы1-го разряда регистра сдвига соответственно, а выходы первого и второгоэлементов И подключены к первому ивторому входам элемента ИЛИ-НЕ, ковходам четвертого элемента И подключены инверсные выходы впервых разрядов регистра сдвига, а выход четвертого элемента И подключен к третьемувходу элемента ИЛИ-НЕ и к первому входу третьего элемента И, ко второмувходу которого подключен инверсный выход е-го разряда регистра сдвига, авыход элемента ИЛИ-НЕ подключен к первому входу элемента ИЛИ, ко второмувходу которого подключен выход третьего элемента И.Источники информации,принятые во внимание при экспертизеЯковлев В,В., Федоров Р,ф. Вероятностные вычислительные машины. Л.,