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

(51) 4 С 06 Р 7/58 ИЗ САЯСАН ТЕН Ф ф р 4 ф л, Е"ГЕЛЬМУТ держки и блок па щ и й с я тем,пу из и элементов мяти, о т л и ч аГОСУДАРСТВЕННЫЙ КОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫ(56) 1. Яковлев В,В., Федоров РСтохастические вычислительные мЛ.: Машиностроение, 1974.2, Авторское свидетельство СССРВ 468231, кл. С 06 Р 7/58, 1973.3. Авторское свидетельство СССРУ 752769, кл. Н 03 К 3/84, 1977.(54)(57) ГЕНЕРАТОЧИСЕЛ, содержащийчисло разрядов геРов, группу из ииз и сумматоров и Р ПСЕВДОСЛУЧАЙНЫХ группу из и (и - нератора) 0-триггеэлементов И, группу о модулю два, групЯО 12806 что, с целью упрощения генератора, выход -го (=1,п) В-триггера соединен с входом 1-го элемента задержки, выход которого является выходом д-горазряда генератора и соединен с первыми входамиго элемента И и (д+1)-го сумматора по модулю два, входы блока памяти образуют группу управляющих входов генератора, а выходы блока памяти соединены с вторыми входами соответствующих элементов И группы, выходы которых соединены с вторыми входами соответствующих сумматоров по модулю два группы, выходы которых соединены с входами соответствующих П-триггеров группы, выход и-го элемента задержки соединен с первым входом первого сумматора по модулю два.Изобретение относится к вычислительной технике и может быть использовано при статистическом моделировании в электронных вычислительных машинах. 5Известен генератор псевдослучайных чисел (генератор М-последовательности), содержащий сдвиговый регистр с сумматором по модулю два в цепи обратной связи 11 1. 10Недостатком этого генератора явля" ется низкое быстродействие и отсутствие возможности формирования различных М-последовательностей,Известен также генератор псевдослучайных чисел (генератор М-последовательности), содержащий триггеры со счетными входами (Т-триггеры) и триггеры с установочными входами (П-триггеры) (23,.У 1 азанный генератор облада ет высоким быстродействием, однако отсутствует возможность формирования различных М-последовательностей.Наиболее близким к предлагаемому является генератор псевдослучайных чисел, содержащий П-триггеры, элементы задержки, сумматоры по модулю два, запоминающее устройство (состоящее из блока управления), элементы И и блок элементов согласования 3).Известный генератор обладает возможностью регулирования периода М-последовательности, однако недостатками его являются излишнее коли чество оборудования, невозможность получения различных М-последовательностей при одном и том же ее периоде и невозможность построения на основе данного устройства генераторов 40 псевдослучайных чисел любой разрядности. Цель изобретения - упрощение устройства и расширение его функцио нальных возможностей за счет формирования различных М-последовательностей и возможности построения генераторов псевдослучайных чисел любой разрядности на основе данного 50 устройства.Для достижения поставленной цели в генераторе псевдослучайных чисел, содержащем группу из и (и - число разрядов генератора) П-триггеров, 55 группу из и элементов И, группу из и сумматоров по модулю два, группу из п элементов задержки и блок памя ти, выход .-го (=1,) П-триггера соединен с входом -го элемента задержки, выход которого является выходом -го разряда генератора и соединен с первыми входами -го элемента И и (+1)-го сумматора по модулюдвавходы блока памяти образуютгруппу управляющих входов генератора, а выходы блока памяти соединеныс вторыми входами соответствующихэлементов И группы, выходы которыхсоединены с вторыми входами соответствующих сумматоров по модулю двагруппы, выходы которых соединены свходами соответствующих П-триггеровгруппы, выход и-го элемента задержки соединен с первым входом первогосумматора по модулю два.На фиг. 1, приведена блок-схемагенератора псевдослучайных чисел;на фиг. 2-7 - примеры выполнения генераторов псевдослучайных чисел,Генератор псевдослучайных чиселсодержит п П-триггеров 1,п элементов И2,п сумматоров 3, по модулю два,п элементов 4 задержки; блок 5 памяти, выходы генератора б;, вход 7 обратной связи,вход 8 управления, Т-триггер 9;,сумматор 10 по модулю два, 1-разрядную ячейку 11 генератора и Е-разрядную ячейку 12 генератора,П-триггер 2, элемент И 2 сумматор Зпо модулю два и элемент 4 задержки в совокупности представляютсобой управляемый триггер, которыйпри подаче на первый вход элементаИ 2 сигнала "1" с выхода блока 5памяти работает в режиме Т-триггера,а при подаче "О" - в режиме П-триггера,Элемент 4задержки служит для задержки сигнала с выхода П-триггера 1 на время, необходимое для записи в него новой информации (при конкретной технической реализации П-триггера 1 может отпасть необходимость в задержке сигнала элементом 4задержки) .Блок 5 памяти служит для хранения информации, управляющей элементамиГенератор работает следующим образом.На входы 8 подаются сигналы, опрашивающие блок 5 памяти, например на первые входы первых Ы элементов И 2 подаются сигналы "1", а на первые входы остальных элементов И 211сигналы О . При этом образуется 1 с(2) По матрице С построим схему гег 5нератора (фиг. 3), используя Р"триггеры и сумматоры по модулю два.Схему на фиг. 3 можно изобразитьв другом виде (фиг. 4).Схема на фиг. 4 с переупорядоченной нумерацией изображена на фиг.5.Так как 2 -1 и Е взаимно простыечисла (п=7, Е=4), то генератор псевдослучайных чисел, изображенный нафиг, 3, формирует М-последователь ность (2). 1,0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 О 0 0 0 1 0 0 0 Т=2 -1 1 или 32 или 3 31 1 или 5 1,3,4 или 6 4 или 563 127 1023 2047 32767131071 3 или 14 Т-триггеров и (и-О Р-триггеров. Эквивалентная схема генератора (при данных управляющих сигналах) представлена на фиг, 2, Данная схема реализует генератор псевдослучайных чисел с одновременным обновлением информации в Е разрядах за такт рабо:ы.Предварительно в генератор заносится начальное состояние (цепи синхронизации и установки в начальное Ю состояние на фиг. 1-7 не показаны). С приходом тактового импульса генератор псевдослучайных чисел переходит . в следующее состояние. Период смены1 Чсостояний Т=2 -1, т.е. генератор фор мирует последовательность максимальной длины (М-лоследовательность),Доказательство этого утверждения разберем на примере работы 7-разрядного (п=7) генератора псевдослучай ных чисел. Из таблицы выберем 1=4.Матрица А, описывающая работу генератора псевдослучайных чисел, бу, дет выглядеть следующим образом: 10 Зили 711 2 или 915 1,4,7 8,11 или 14 Построим 7-разрядный генератор псевдослучайных чисел с одновременным обновлением 4 разрядов за такт работы 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 О 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0(3 55 1 0 0 0 0 О Циклические своиства генератора псевдослучайных чисел полностью определяются характеристическим многочленом. Ксли характеристический многочлен примитивен и неприводим, то генератор формирует М-последовательность (1), причем каждому характеристическому многочлену соответствует своя М-последовательность и, наоборот, каждой М-носледовательности соответствует свой характерис" тический многочлен.Схемы, изображенные на фиг, 3 и 5, идентичны: формируют одну и ту же М-последовательность, следовательно, они описываются одним и тем же характеристическим многочленом, неприводимым и примитивным.Функционирование схемы, изображен ной на фиг. 5, описывается матрицей С Матрице С соответствует характеристический многочлен ч(х), который вычисляется через определитель (г). 45 Используем один из методов преобразования определителей, заключающийся в следующем; определитель не меняется, если к элементам одной из его строк (столбца) прибавить соответст вующие элементы другой строки (столбца). Преобразуем определитель (4). Сложим содержимое 6-го и 7-го столбцов (используя операцию суммирования по модулю два) и результат запишем в 7-й столбец, затем сложим содержимое 6-й и 7-й строк, результат запишем в 6-ю строку. Получим следующий определитель:х 0 0 0 0 О 1 11+хО 0 0 0 0 0 1+хО 0 0 0 0 0 1 х 0 0 0 0 0 0 11+хО 0 0 0 0 0 11+х 0 40 0 0 0 0 1 х 5 Ч(х)Применяя те же операции над 4-ми 5-м столбцами и 4-й и 5-й строками,а затем над 5-м и 6-м столбцами и5-й и 6-й строками, получим: х 0 0 0 0 0 1 11+хО 0 0 0 0 0 11+хО 0 0 0 0 0 11+хО 0 0 0 0 0 11+хО 0 0 0 0 0 1 х 0 0 0 0 0 0 1 х Я(х) =(7) 50 55 Матрице В соответствует схемана фиг, 6. Видно, что символ 1, расположенный на главной диагонали на пересечении 7-й строки и 7-го столбца, переместился на место пересечения 4-й строки и 4-го столбца.Определителю (6) соответствует матрица В, описывающая функционирование генератора псевдослучайных чисел: Схему на фиг. 6, используя Т-триггеры и Р-триггеры, можно преобразовать в схему, аналогичную изображенной на фиг. 2, в которой все Т-триггеры соединены последовательно другза другом и все Р-триггеры соединены последовательно друг за дрязгом(Р-триггер с сумматором по модулюдва на входе можно заменить Т-триггером),Такие же преобразования можносделать с и-разрядным генераторомпсевдослучайных чисел с одновременным обновпением информации вразрядах.Кроме того, используя описанныеоперации над определителями, можносимволы 1, присутствующие на главной диагонали определителя, перераспределить в любые места на главнойдиагонали, не изменяя их количества,следовательно, получать генераторыпсевдослучайных чисел с любым (удобным для разработчика) расположениемТ-триггеров и Р-триггеров, не изменяя их количества. Можно предложить следующую последовательность расчета генераторовпсевдослучайных чисел с одновременным обновлением информации в нескольких разрядах за такт: выбирают идлину регистра генератора псевдослучайных чисел; но и выбирают (например, из таблицы) Е - число одновременно обновляемых разрядов, соблюдая при этом условие взаимной простоты 2"-1 и Е, иначе генератор небудет формировать М-последовательность; берут Е Т-триггеров и (и-Е)Р-триггеров, соединяют последовательно друг за другом, причем выход последнего триггера соединяют с входомпервого триггера. Взаимное расположение Т-триггеров и Р-триггеров можно выбирать произвольно,Подавая соответствующие сигналыиз блока 5 памяти на входы элементовИ 2, можно при одном и том же и,но при разных 1 с получать различныеМ-последовательности,Устройство, представленное нафиг. 1, является ячейкой однороднойсреды (универсальной ячейкой) генератора псевдослучайных чисел. Можно соединить несколько таких устройств (например, два, фиг. 7) другс другом, подключая выход 6 предыдущего устройства к входу 7 обратнойсвязи последующего устройства, и получить генератор псевдослучайныхчисел большой разрядности. При этомобщее количество триггеров п=1+к иколичество Т-триггеров 1=+я должносоответствовать таблице, а такжедолжно соблюдаться условие взаимнойпросторны 2-1 и 1 с,Если отсутствует необходимость 10 получения различных М-последовательностей (при одном и том же и) блок 5 памяти будет работать в режиме постоянного опроса (на первые входы элементов И 2подаются постоянные сиг налы "0" или "1"). При этом блок 5 памяти и элементы И 2 вырождаются в набор перемычек, соединяющих выходы Р-триггеров 1 с входами сумматоров 3 по модулю два, а все устройство 20 представляет собой набор Т-триггеров и Р"триггеров (фиг, 2) . Предлагаемый и базовый 1.2 1 генера,торы, псевдослучайных чисел обладают одинаковыми статистическими характе ристиками выходных псевдослучайных процессов, однако предлагаемый генератор обладает расширенными функциональными возможностями, а именно позволяет получать различные М-последовательности, кроме того, на его основе возможно чрезвычайно простое построение генератора псевдослучайных чисел любой разрядности,(базовый образец является одним из возможных вариантов применения изобретения),Использование изобретения позволяет упростить устройство и расширить его функциональные возможности за счет получения различных М-последовательностей и возможности построения. генератора псевдослучайных чисел любой разрядности.1280619 з.7 Составитель А. Карадактор А. Лежнина Техред,Л.Олейник Корректор М, Максимишин 6 одписнР Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная,каз 7067/54 Тираж ВНИИПИ Государст по делам изоб 113035, Москва, Ж енного комитета С етений и открытий 5, Раушская наб