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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСсщналистическихРеспублик(22) Заявлено 1812.81 21) 3365888/18-24 Р 1 М К з с присоединением заявки Нов 6 06 Г 7/58 Государственный комитет СССР по делам изобретений и открытий(23) Приоритет -Опубликовано 150383. Бюллетень М 10 Дата опубликования описания 15. 03. 83 1 И) УДК 681,325. 088. 8)Минский радиотехнический институ 71) Заявитель ЙНЫХ ЧИС 4) ГЕНЕРАТОР ПСЕ ЭВМ,водитпри рдач.Из ратор псевдослучайж щий два регистрасумматоров по модутен генл, содег пп ных чисе Рсдвига и ру улю два 1.Недостатками генератслучайных чисел являютсаппаратурного построениусложненная методика ситого, в ряде случаев поподобных генераторов псных чисел оказывается нным, так как структуранераторов псевдослучайпользуемых при построенра, должна быть такой,риоды являлись взаимночислами, что далеко неняется.Параллельный генерчайных чисел 13 отлиным быстродействием.Сложность схем фонутых последовательнется числом входов смодулю два. Каждый сЗО нем имеет е/2 вход ора псевдоя сложность я, а также нтеэа. Кроме строения евдослучай- евозможисходных геых чисел исии генерато" чтобы их пе, простыми всегда выполатор псевдослучается.максимальрмирования сдвостей определумматоров поумматор в среов При этом Изобретение относится к вычислительной технике и может быть использовано в качестве устройства для получения случайных чисел при решении задач статистическими методами, а также для построения генераторов случайных процессов с заданными характеристиками.Генератор псевдослучайных чисел, позволяющий получать случайные числа с равномерным распределением, часто используется как составной блок для построения генераторов случайных чисел с произвольным законом распределения. При этом весьма важным оказывается качество первичных равномерно распределенных чисел, которое, в первую очередь, определяется законом распределения и автокорреляционной функцией. Подобное устройство целесообразно использовать для целей решения задач статистического моделирования, для построения систем связи шумоподобными сигналами, для решения задач криптографии и т.д. В качестве кон.кретной технической реализации рассмотренного устройства целесообразно использовать автономный блок, используемый как внешнее устройство что позволит увеличить произельнасть вычислительных средствешении определенного круга эа 1005045затраты, идущие на построение схемФормирования сдвинутых последовательностей, в несколько раз превышают затраты, идущие на построениекольценого регистра сдвига, состоящего из щ разрядов;Известен также генератор псевдослучайных чисел, позволяющий получать последовательности: псевдослучайных чисел, максимально близкиепо природе к истинно случайным числам. Его техническая реализация осу"щестнляется при малых удельных .аппаратурных затратах Г 2 .Недостатком данногб устройстваявляется ненозможность получения на 15его выходе щ-разрядного псевдослучайного числа= ОООО, отсутстниекоторого приводит к искажению равномерного закона распределения, которое увеличивается с уменьшением ве- р 0личины юИзвестен генератор псевдослучайных чисел, который позволяет получить на выходе код псевдослучайногочисла равного 0000, что приводит 25;к выравниванию математического ожи,дания вероятности появления любогокода 3 ).Недостаток этого генератора заключается н большой аппаратурнойсложности. Удельные аппаратурныезатраты на один разряд псевдослучайного числа составляют один (гп+1) -нходоный сумматор по модулю два,.один триггер, одну схему ИЛИ-НЕ,од.ну схему ИЛИ, ь + 2 схемы ь и 1/гпгенератор ранновероятной двоичнойцифры. Кроме того, подобный генератор должен иметь в своем составедна регистра для хранения коэффициентов ни /ье. 40Наиболее близким к изобретениюявляется генератор псевдослучайныхчисел, содержащий тл триггеров,первую и вторую группы по тэле.ментов ИЛИ, первый и второй элементНЕ, группу из в - 2 элементов ИЛИ-НЕгруппу из м сумматоров по модулюдва 43.В данном устройстве предусмотрена возможность получения на выходегенератора комбинации 000.;О,чтоприводит к выравниванию вероятностипоявления кода к, Р Як) , котоРаядля любого к равняется 1/2Таким образом, закон распределениявыходных последовательностей в данном устройстве является равномерным, так как вероятность появленияна его выходе любого кода одинаковаи равняется 1/2. Последовательности, генерируемые на выходе рассмотренного устройства, относятся к классу так называемых последовательностей де Брюйна (де Вгцп) или циклами де Брюйна. Введение нулевой 65 комбинации н М-последовательность ухудшает корреляционные свойства последовательности, причем этот недостаток присущ всем последовательностям, относящимся к последовательностям де Брюйна. Кроме того, недостатком рассмотренного устройства является наличие периода в Формируемой последовательности, который ограничивается величиной е где гп - количество триггеров, идущее на построение устройства.Цель изобретения - расширение ,Функциональных возможностей, генератора путем устранения повторения последовательности кодов псевдослучайных чисел на выходе генератора, .что, в гвою очередь, приводит к улучшению корреляционных свойств выходных последовательностей.Поставленная цель достигается тем, что генератор псевдослучайных чисел, содержащий генератор тактовых импульсов, группу из щ(п = 1,2, число разрядов генератора ) О-триггеров, первую группу из т сумматоров по модулю два и первую группу из двух элементов НЕ, причем выход генератора тактовых импульсов подключен к С-входам О-трнггеров группы, а выход 1 -го (=1 в ) О-триггера группы подключен к первому вхо- ду 1 -го сумматора по модулю два первой группы, введены дне группы по щ элементов И, вторая группа из т сумматоров по модулю дна, вторая группа из гп - 1 элементов НЕ, группа из тп элементов 2 И-ИЛИ, генератор равновероятной двоичной цифры, кроме того, н первую группу элементов, НЕ дополнительно введено упэлементов НЕ, причем к О-входу 1.-го О-триггера подключен выход 1-го элемента 2 И-ИЛИ группы, нулевой выход 1"го ( )= 1, в в 1) О-триггера подключен к входам щ - ,) старших элементов И первой группы, выход (+1)- го элемента НЕ первой группы подключен соответственно к входам ) младших элементов И первой группы, выход 1-го элемента И первой группы подключен к второму входу -го сумматора по модулю два первой группы, к третьим входам.п( 1 п:7,.3/2 п ) старших сумматоров по модулю два первой группы подключены единичные выходы младших О-триггеров группы соответственно, а к третьим входам младших сумматоров по модулю два первой группы подключены выходы Л 1-у 1 старших сумматоров по модулю два первой группы соответственно, выхо-, ды ю трехвходовых сумматоров по модулю два первой группы подключейы к входам т элементов НЕ первой группы соответственно, выход ) -го элемента НЕ первой группы подключен к соответствующим входам т- ) старших элемент ц Н второй группы, выход-го элемента НЕ второй группы под-. ключен к соответствующим входам ,младших элементов И второй группы, выход .-го элемента И второй груп-. пы подключен к первому входу 1-го сувеатора по модулю два второй группы, к второму входу которого подключен выход .1-го сумматора по модулю два первой группы, к третьии входам и старших сумматоров по модулю два второй группы подключены выходы к младших сумматоров по модулю два первой группы соответственно, а к третьим входам т -и младших сумматоров по модулю два второй 15 группы подключены выходы щ - и старших сумматоров по модулю два первой группы соответственно, выходы в - 1 старших сумматоров по модулю два второй группы подключены квходам 20 1 п - 1 элементов НЕ второй группы соответственно, кроме того, к первому и второму входам 1"го элемента 2 И.-.ИЛИ группы подключены выходы 1-го суюатора по модулю два первой и я 5 второй групп соответственно, к третьему и четвертому входу элементов ,2 И-ИЛИ группы подключены единичный и нулевой выходы генератора равно- вероятной двоичной .цифры соответственно, к входу которого подключен выход генератора тактовых импульсов, выходы сумматоров по модулю два второй группы являются выходами генератора.35На Фиг. 1 приведена Функциональная схема генератора, на Фиг. 2 и 3- ,схемы генератора тактовых импульсов и.генератора равновероятной двоичной цифры, на Фиг. 4 - временная диаграмма его работы.Генератор псевдослучайных чисел содержит в=5 2 -триггеров 1, две группы по е элементов И 2 и 3, две группы по Ю сумматоров по модулю два 4 и 5, первую, группу из ю элементов НЕ 6, вторую 45 группу из тп - 1 элемента НЕ 7 группу из щ элементов 2 И-ИЛИ 8, генератор 9 равновероятной двоичной цифры, генератор 10 тактовых импульсов. . 50функционирование генератора псевдослучайных чисел происходит следующим образом.В начальный момент на Р -тригге.ры 1 записывается произвольный код55в том числе и нулевой. На вы- ходах сумматоров по модулю два первой группы 4 Формируется щ-разрядный код , который является продолжением.кода р в соответствии с за данной. М-последовательностью вид .М-последовательности определяется полиномом Ч(х) 1+х 3 + хщ), а на выходах элементов 5 - код являющийся продолжением кодаф . По ,65 приходу тактового импульса на синхронизирующие входы Р -триггеров 1выходов элементов В на 9 -триггеры 1 записывается код, полученный на выходе сумматоров 4 или 5, т.е.или . С прйходои очередного сйнхронизирующего импульса процесс повторяется.Более подробно процесс генерированияпсевдослучайных чисел поясняется на конкретном примере, На фкг.1 приведена функциональная схема генератора псевдослучайных чисел для п = 5 и для а(,1= 0, = О, еббр= 1, с 6,= О, с 65= 1, а на Фиг. 3 - временная диаграмма его работы.На фиг. 3 показана последователь" ность, генерируемая на выходе обычного последовательного генератора псевдослучайных чисел построенного согласно следующему пораждающеку полиному 9(х) 1+ х + х. Фигур-. ными скобками обозначены сегменты М-последовательности, которые могли быть сформированы на выходе рассматриваемого генератора псевдослучайных чисел в зависимости от значений равновероятной двоичной цифры. Сплошнами стрелками с подписями показана последовательность состояний на выходе устройства в зависимости от конкретных значений х и штриховьиик стрелками - возможные значения на выходе устройства в случае инверсных значений х(1 с).В первоначальный момент времени на триггерах записан код 11011. В соответствии с кодом 11011 на выхо" дах сумматоров, 4 формируется код 10101 и на выходе устройства (сумматор. 5) в .код= 16000. Так как, например, значение х(0) в нулевой момент равняется 1, по приходе синхроимпульса на В-триггеры записывается код 10101. После прохождения переходных процессов на выходах сумматоров 4 . Формируется код 10000, а на выходе устройства - Код=10100, В следующем такте на Э -триггеры запишется код 10100, так как значение х(11 О. Подобным образом Выстриг геры меняют свое состояние в зави-. симости от значения,на выходе генератора 9 равновероятности двоичной цифры и по приходе последующих тактовых импульсов, На фиг. 3 сплошными стрелкаии.показана последовательность выходных кодов рассматриваемого устройства для х(0) . 1, х(1) О, х(2) 1, х(3) 1.Поскольку состояние генератора равноверояткой двоичной цифры случайнопоряДок следования кодов М- последовательностей .также абсолютно случаев, причем выходным значением устройства с равной вероятностьюможет быть любой п-разрядный код, втом числе и нулевой.Преимущество предлагаемого генератора псевдослучайных чисел заключается в следующем.Природа выходных псевдослучайных чисел, подобно как и в устройствах 2 3 и (33 максимально приближена к истинно случайным числам. В данном устройстве также нарушено жесткое условие, что после опреде ленного,; должно следовать 1 заранее точно известное, так как в данном случае+1 может принимать равновероятное одно из двух значений. 15В отличие от устройства (2) на выходе рассматриваемого генератора псевдослучайных чисел возможно получение кода 0000 что приводит к выравниванию математического ожида ния вероятности появления любого ,кода , которая в данном случае равняется Р = щ . Отсутствие запрещенных кодовпозволяет повы 2сить надежность генератора псевдо случайных чисел, так как, подобно ,устройствам (3 ) и (4 , наличие нулевого кода на триггерах не срывает генерирования псевдослучайной последовательности.30Предлагаемый генератор псевдослучайных чисел отличается простотой технической реализации. Удельные аппаратурные затраты на один разряд псевдослучайного числа составят один Р-триггер, один элемент 2 И-ИЛИ, два 35 трехвходовых сумматора по модулю два, два (я - 1)-входовых элементов И два элемента НЕ и - генератор равновероятной двоично 3 цифры, что. значительно меньше соответствующих 40 затрат в устройстве (4 1.В сравнении с базовым объектом генератором псевдослучайных чисел (1)- предлагается устройство, отличающееся рядом преимуществ. Во-первых, 45 свойства выходной последовательности, получаемой на выходе рассматриваемого. генератора, значительно лучше свойств последовательностей, получаемых на выходе базового объекта. Так 5 О период выходных последовательностей в предлагаемом автором устройстве равен со, а вероятность появления1любого кодаРавняется Р= щ2 Во-вторых, введение нулевой комбинации позволяет существенно увеличить надежность предлагаемого устройства в сравнении с базовым объектом.Применение подобного генератора 60 псевдослучайных чисел, отличающегося широкими функциональными воэможностями, высокой надежностью функционирования и стабильностью его вероятностных характеристик, позволит по высить качество псевдослучайных последовательностей, а тем самым точность и достоверность решения задач методом Монте-Карло. Кроме того, подобные устройства позволяют получать истинно белый шум для построения генераторов случайных процессов и могут быть использованы в качестве внешнего устройства серийно выпускаемых ЭВМ.Формула изобретенияГенератор псевдослучайных чисел, содержащий генератор тактовых импульсов, группу из в(п - число разрядов генератора) Р - триггеров, первую группу иэ тп сумматоров по модулю два и первую группу иэ двух элементов НЕ, причем выход генератора тактовых импульсов подключен к С-входам Э -триггеров группы, а выход 1 -го1,т )3-триггера группы подключен к первому входу 1-го сумматора по модулю два первой группы, о т л и ч а ю щ и й с я тем, что, с целью расширения функциональных воэможностей эа счет улучшения корреляционных свойств генератора, дополнительно введены две группы по в элементов И, вторая группа из т сумматоров по модулю два, вторая группа иэ щ - 1 элементов НЕ, группа из п элементов 2 И-ИЛИ, генератор равновероятной двоичной цифры, кроме того,в первую группу элементов НЕ дополнительно введено тп - 2 элементов НЕ,- причем к Р -входу 1 -го Р -триггера подключен выход 1 -го элемента 2 И-ИЛИ группы, нулевой выход )-го= 1,м - 1 ) Й -триггера подключен к входам щ- ) старших элементов И первой группы, выход (1 + 1) -го элемента НЕ первой группы подключен к соответствующим входам ) младших элементов И первой группы, выход 1-го элемента И первой группы подключен к второму входу 1 -го сумматора по модулю два первой группы, к третьим входам н(и1/2 в) старших сумматоров по модулю два первой группы подключены единичные выходы и младших В -триггеров группы соответственно, к третьим входам Эта- и младших сумматоров по модулю два первой группы подключены выходы п - и старших сумматоров по модулю два первой группы соответственно, выходы В трехвходовых сумматоров по модулю два первой группы подключены к входам тп элементов НЕ первой группы соответственно, выход 1 -го элемента НЕ первой группы подклю" чен к соответствующим входам В -) старших элементов И второй группы, выход ) "го элемента НЕ второй группы подключен к соответствующим: входаммладших элементов И второйгруппы, выход 1.-го элемента И второй группы. подключен к первому входу 1-го сумматора по модулю двавторой группы, к второму входукоторого подключен выход 1 -го.сумматора по модулю два первой группы,к третьим входам и старших сумматоров по модулю два второй группы подключены выходы п младших сумматоровпо модулю два первой группы соответственно, а к третьим входам щ-имладших сумматоров по модулю двавторой группы подключены выходы щ- Мстарших сумматоров по модулю двапервой. группы соответственно, выходы 35е - 1 старших суяиатаров по модулюдва второй группы подключены к входам е .элементов НЕ второй группы соответственно, кроме того, кпервому и второму входам 1 -го эле Омента 2 И-ИЛИ группы подключены выходы 1-го сумматора по модулю два первой и второй групп" соответствен.но, к третьему и четвертому входамэлементов 2 И-ИЛИ группы подключеныединичный и нулевой выходы генератора равновероятной двоичной цирысоответственно, Я входу которогоподключен выход генератора тактовыхимпульсов, выходы сумматоров по модулю два второй группы являютсявыходами генератора,Источники информации,принятые во внимание при экспертизе1, Яковлев В,В. и федоров Р,ф.Вероятные вычислительные машины,Л.,"Машиностроением, 1974, с. 344.2. Авторское свидетельство СССРР 708381;кл. 6 07 С 15/00 19803. Авторское свидетельство СССРпо заявке У 2988394/18-24,кл. С 06 Г 7/58, 16.04.80,4. Авторское свидетельство СССРпо заявке 9 2920810/18-24,кл, С 06 Г 7/58, 26,11.80 (прототип).Составитель А,КарасевРедактор Л.Алексеенко Техред Л,Пекарь Корректор М,Демчи а пиал ППП "Патент", г. Ужгород, ул. Проектная,1900/64 Тираж 704 ВНИИПИ Государственно по делам иэобретени 113035, Москва, Ж, РПодписноекомитета СССРи открытийушская наб., д. 4/5