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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНРЕСПУБЛИН ЯО 10208 САНИЕ ИЗОБРЕТЕНИЯ инс в Р. ф,машины,с 247 СССР3, 1972.СССР тотип УДАРСТВЕННЫЙ НОМИТЕТ СССРДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬПИЙ ТОРСНОМУ СВИДЕТЕПЬСТ(56) 1, Яковлев В, В., федорВероятностные вычислительныеЛ., "Машиностроение", 1974,2. Там же, с, 254.3, Авторское свицетельствоИо 527012, кл. Н 03 К 5/4. Авторское свицетельствпо заявке % 3252992/18-24кл,06 Р 7/58, 1981 (про(54) (57) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ,содержащий генератор тактовых импульсов, выхоц которого подключен к перво-.му вхоцу элемента ЗАПРЕТ, к второмувхоцу которого подключен выход счетчика, регистр сцвига, состоящий из 1) -триггеров, выхоц элемента ЗАПРЕТ подключен к первому входу элемента ИЛИ, к второму вхоцу которого поципочен выхоц генератора оциночных импульсов, а выходэлемента ИЛИ поцключен к С -вхоцам ГО( Щ число разряцов генератора) 3 -триг.геров регистра сдвига, единичные выхоцыкоторых поцключены к первым входам соответствующих й 1 элементов И группы,вторые входы которых являются первойгруппой входов генератора, выходы т элементов И группы поцключены к соответствующим входам Ф-вхоцового сумматорапомоцулюцва, о тличающийсятем, что, с целью повышения быстроцействия, он содержит элемент зацержки,элемент НЕ, группу из п 1 элементов2 И-ИЛИ, Й 5-триггер, в регистр сдвига цополнигельно введены п 0 -триггеров и п элементов 2 И-ИЛИ, причем выход элемента зацержки поцключен к вхоцу счегчика и к С-входу Р 5-триггера, а к входу элемента задержки подключен выход генератора одиночных импульсов, выход генератора тактовых импульсов подключен к входу счетчика, выход которого подключен к вхоцу элемента НЕ и к первым входам п элементов 2 И-ИЛИ регистра сдвига, вторые выхоцы которых подключены к выходу элемента НЕ,; к третье му вхоцу первого элемента 2 И-ИЛИ ре гистра сдвига подключен выхоц щ -входовогосумматора по моцулю два, а третийвход ( д +1)-го (д 1,дт) адаманта Я 2 И-ИЛИ регистра сдвига поцключен к еци баев яичному выходу ц -го П -триггера ре- ффф гистра сцвига, четвертый вхоц 1 -го( 1 = 1,п) ) элемента 2 И-ИЛИ регистра сцвига подключен к выхоцу 1-го элемен- вел та 2 И-ИЛИ группы, С - входы Й) дополнительных Ю -триггеров регистра сдвига подключены к выходу элемента ИЛИ, а к (ее О -входу ( и +1)-го цополнительного О О -триггера регистра сцвига поцключен выход О -го цополнительного Х) -триггера регистра сдвига, к 0 -вхоцу первого цоаай полнительногоЭ- триггера регистра сдви:га подключен единичный выход щ - го 3 -триггера регистра сдвига, к первому и второму вхоцам элементов 2 И-ИЛИ группы подключены ециничный и нулевой файф выходы 5-триггера соответственно, выхэ ды (2 1 -1)-х ).) -триггеров и цополнительных З -триггеров регистра сцвига соединены с третьими входами-х эле.ментов 2 И-ИЛИ группы, выхоцы 21 -х ) ) -триггеров и дополнительных Э -триг1020821 и цополнительных Э триггеров регистра сдвига иЯ 5-триггера являются второй группой вхоцов генератора. геров регистра сцвига соединены с счетвертыми входами-х элементов2 И-ИЛИ группы,Р 5-входы 2 -триггеров2Изобретение относится к вычислитель- рая в основном определяется наличиемной технике и может быть использовано элементов памяти,в качестве устройсжа для опрецеления Наиболее близким техническим решенифтопологии связей многовходового суммато ем к предлагаемому является генераторра по модулю цва, на выходе которого 5 псевдослучайных послецовательностей, сосформируется сдвинутые копии,псевцослу, тоящий иэ генератора тактовых импулчайных последовательностей, Использова- сов, первого элемента ЗАПРЕТ, регистрание "сдвинутых копий псеВдослучайных сдвига с сумматором по модулю два впоследовательностей позволяет строить цепи обратной связи и элементами И, цеэкономичные генераторы псевдослучайных 10 шифратора, второго элемента ЗАПРЕТ,чисел, а также организовать автономные счетчика, цвухвхоцового элемента И,устройства для имитации случайных про двухвходового элемента ИЛИ, генераторацессов с заданными характеристиками. одиночных импульсов и элемента инцикаИзвестен генератор псевдослучайных ции. Генератор отличается значительночисел, содержащий регистр сдвига с сум , 15 уменьшеннными аппаратурными затратами,матором по моцулю цва в цепи обратнойчто объясняется отсутствием элементовсвязи Я, памяти Я,Недостатком устройства является не-, Однако устройство облацает низкимвозможность получения копий псевцоспу- быстродействием.,Цля опрецеления топочайной последовательности сдвинутых 20 логии связей многовходового сумматораболее, чем на м тактов, гце м - разряд- по моцулю цва, на выходе которого форность регистра сдвига. мируется сдвинутая на д тактов копияИзвестен параллельный генератор поев- псевцослучайной последовательности, вцослучайных чисел, который позволяет по- рассмотренном устройстве необходимолучать копиипсевцослучайной послецова-. 25 вЫполнить 3- 1 тактов моцелирования его,тельности сдвинутые на значительно работы При больших значениях с 1, напри 50большее чи,ело тактов 2, мер Д ъ 25, задача определения тополоОцнако данное устройсщо позволяет гии связей многсвхоцового сумматора напол;учать копии псевцослучайной послецо-,существующей элементной базе практичес. вательности только лишь для частного З 0 ки неразрешима,спучая, когда схема цепи обратной связиБель изобретения - увеличение быстрорегистра сдвига состоит только из оцного действия генератора псмцослучайныхполусумма тора. последовательностей и расширение егоИзвестно устройство цля формирования Ф)ппсциональных возможностей. Расширениесдвинутых копий псевдослучайного сигна- функциональных возможностей осущесрла, позволяющее определить топологию вляется за счет возможности определения.связей сумматора по модулю цаа, на вы- топологии сумматора по модулю два, находе которого получается копия исходной выходе которого формируется копия псее- .псевдослучайной М - последовательности дослучайиой последовательности.сцвинутая на произвольное количество 40 . Йля цостижения поставленной цели втактов. Причем в данном устройстве эта генератор псевцосдучайных последовательзадача решается цля общего случая, т,е, ностей, содержащий генераюр тактовыхдля случая, когда в цепи обратной связи, импульсов, выхоц которого поцюпочен крегистра сдвига включен многовхоцовой первощ входу элемента ЗАПРЕТ, к второсумматор по модулю два з, 45 у входу которого подключен выход счетс 45 чика, регистр сдвига, состоящий из 0-тригОцнако устройство характеризуется геров, выход элемента ЗАПРЕТ поцклюсложностью аппаратурного йостроения, кото- чен к первому входу элемента ИДИ, к3 10 второму входу которого поцюпочен выход генератора оциночных импульсов, а выход элемента ИЛИ подключенк С-входам ( Е - число разрядов генератора) Ы -триггеров регистра сдвига, ециничные выходы которых подюпочены к первым входам соопретствуюших п 1 элементов И группы, вторые входы которых являются первой группой входов генератора, выходы В элементов И группы поцключены к соответствующим входам п 1 -входного: сумматора по модулю цва, введены элемент задержки, элемент НЕ, группа из а элементов 2 И-ИЛИ и ЯБ-триггер, в регистр сцвига дополнительно введены п 1 0-триггеров и В элементов 2 И-ИЛИ, выход элемента задержки подюпочен к входу и к С вхо цу Я 1 о -триггера, а к входу элемента задержки подключен выхоц генератора одиночных импульсов, выхоц генератора тактовых импульсов поцключен в вхоцу счеъ чика, выхоц которого подключен к входу элемента НЕ и к первым вхоцам П 1 элементов 2 И-ИЛИ регистра сдвига, вторые входы которых подключены к выходу элемента НЕ, к третьему входу первого элемента 2 И-ИЛИ регистра сцвига подключен выход щ -вхоцного сумматора по модулю цва, а третий вхоц (ц +1)-го (П = 1, П 1-1) элемента 2 И-ИЛИ регистра сдвига подключен к единичному выходу И го 0 -триггера регистра сцвига, четвертый вхоц 1-го (1 = 1, Ф) элемента 2 И-ИЛИ регистра сцвига поцключен к выхоцу / -го элемента 2 И-ИЛИ группы, С-входы цополнительных с) -триггеров регистра сцвига подключены к выходу элемейта ИЛИ, а к О -вхоцу (Д +1)-го дополнительногоЭ +триггера регистра сдвига подключен выход п -го дополнительного ) -триггера регистра сдвига, кД- входу первого дополнительногоО-триггера регистра сцвига поцключен единичный выход П-го 0 -триггера регистра сдвига, к первому и второму вхоцам элемента 2 И-ИЛИ группы подключены единичный и нулевой выходы Я 5-триггера соответственно, выходы2-1) -х 1.)-триг. геров и дополнительных З -триггеров реги;тра сдвига соединены с третьими вхоцами 1 -х элементов 2 И-ИЛИ группы, выхоцы 2 1 -х 0 -триггеров и цополнительных Э -триггеров регистра сцвига соединеь с четвертыми входами . -х элементов 2 И-ИЛИ группы, Я 5 -вхоцы О -триггеров и цополнительных 0 -триг геров регистра сдвига и Р 5-триггера являются второй группой . входов гене- раторае 2082 1 4На фиг. 1 и 2 приведена схема генератора цля общего случая и цля случаяРъ = 5 соответственно;Генератор псевцослучайньвс цослецовательностей состоит из генератора 1 тестовых импульсов, элемента ЗАПРЕТ 2,счетчика 3, элемента 4 задержки, генератора 5 одиночных импульсов, элементаИЛИ 6, элемента НЕ 7, Х) триггеров 8 10 регистра сдвига, дополнительных Э- тригге ров 9 регистра сцвига, элементовИ 10,сумматоры 11 по моцулю два, элементов2 И-ИЛИ 12 регистра сцвига, элементов2 И-ИЛИ 13 иЮ-триггера 14.15 фу нкционирование генератора псевдо- случайных последовательностей происходитследующим образом.Перец началом работы генератора повходам 0 -триггеров 8 регистрасцвща 20 заносится коц начального состояния. Начальный код записывается по КЬ-входам-триггеров 8 регистра сдвига, По аналогичным входам триггеров счетчика 3на счетчик 3 записывается коц прецуста новки. Запись коца обеспечивает получениекоэффициента пересечения счетчика. И,наконец, на В 5-триггер 14 записываешьсязначение цвоичной цифры фо.При включении генератора 1 тактовыхимпульсов через элемент ЗАПРЕТ 2 иэлемент ИЛИ 6 тактовые импульсы поступают на С-входы О григгеров 8 и дополнительных триггеров 9. Единичный сигнал с выхода счетчика 3 поступает на 35первые выходы элементов 2 И-ИЛИ 12Та нулевой сигнал с выхода элемента НЕ 7поступает на третий вход элементов2 И-ИЛИ 12, Таким образом,0 -триггеры8, сумматор по модулю два 11 и эдемы-.4 ты И 1 0 организуют регистр с сумматором по модулю два в цепи обратной свя 11зн, генерирующий М-последовательность., Прн поступлении тактовых импульсов нарегистр сдвига генерируется М-последова 45тельность, причем симвопы М-последовательности с выхода последнего 1) -триггера 8 регистра сдвига вдвигаются в сдвиговой регистр сформированный дополнительными триггерами 9. По истечении гОтактов, когда через элемент ЗАПРЕТ 25 пройдет %импульсов на выходе счетчика503 сформируется нулевой сигнал, которыйпрервет поступление тактовых импульсовна С-входы 0 -триггеров 8 и 9 регистрасдвига.Нулевой уровень на выходе блока 3размыкает межразрядные связи в регистре 8 сдвига и на вход 1 -го ( 1 =1,1 п)триггера 8 регистра сдвига через 1 -ый1020 элемент 2 И-ИЛИ 12 подключает выход 1 -го элемента 2 И-ИЛИ 13. В зависимости от состояния триггера 14, т.е. от зна. чения о на входы Х) -триггеров 8 подключаются выходы четных или нечетных триг геров группы триггеров, состоящей из триггеров 8 и 9 регистра сдвига. При о= О на выход первого триггера будет подключен выход второго триггера на вход второго триггера будет подключен 1 О выход четвертого триггера и т.д а навход щ-го триггера выход 2 и-го. При 1 на вход первого триггера будет подключен выход первого триггера, на вход второго тирггера выход третьеготриггера и т.да на вход -го триггера выход 2 -1-го.йалее при нажатии кнопки генератора 5 опииоч-, нык импульсов одиночный импульс через элемент ИЛИ 6 поступает на С-вход З триггеров 8 и 9 регистра сдвига. По истече нин времени с, определяемого временем задержки элемента 4 задержки, на С-вход ВБ -триггера 14 и управляющие входы счетчика 3 поступает управляющий сигнап, который записывает на К 5-триггер 14 значение цифрыа на триггеры счетчика 3 код предустановки. После установки коЕоР е 1да 2-п 1 на триггеры счетчика 3 про 821 Фцесс , функционирования полностью повторяется. Окончатепьно функционирование устройства прекращается только после выполнения О +2 подобных тактов,Увеличение быстродействия устройства позволяет расширить его функциональные возможности. Так оказывается возможным определение квффициентов позвопяюших псцтучить копии М-последовательностей , сдвинутых на астрономические число тактов т,е. длясь 2 и т.д. Преимущества предпагаем ого генератора по сравнению с известным заключается в возможности получения копий псевдослучайной поспедоватепьности на большее число тактов, что в конечном счете позволит существенно расширить функциональные возможности базового объекта.Применение предлагаемого генератора, позволяющего приучать сдвинутые копии псевдослучайной поспедоватепьности, отличающегося повышенным быстродействием позволит строить высоконадежные, стабкпьные и высококачественные генераторы псевдослучайных чисел, тем самым повыоить точность и достоверность решения задач методом Монте-Карло.1020821 6, Подписноенного комитета СССРретений и открытий-35, Раушская наб., д. 4/5 каз 3898/41 Тираж 70 ВНИИПИ Государстве по делам ызоб 113035, Москва, Ж