Генератор псевдослучайных последовательностей Советский патент 1983 года по МПК G06F7/58 

геров регистра сдвига соединены с с

четвертыми входами i -х элементов

2 И-ИЛ И группы, ЙЗнвхоцы D --триггеров

и дополнительных D -триггеров регис ра сдвига и R5-триггера вюляются второй группой входов генератора.

ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, содержащий генератор тактовых импульсов, выход которого подключен к перво-. му входу элемента ЗАПРЕТ, к второму входу которого подключен выход счетчика, регистр сдвига, состоящий из D -триг геров, выход элемента ЗАПРЕТ подключен к первогиу входу элемента ИЛИ, к второму входу которого подключен выход генератора одиночных импульсов, а выход элемента ИЛИ подключен к С -входам гП (т - число разрядов генератора)D -триггеров регистра сдвига, единичные выходы которых подключены к первым входам соотеетствующих m элементов И группы, вторые входы которых $шляются первой группой входов генератора, выходы m элементов И группы подключены к соответ ствуюшим входам т-входового сумматора по модулю два, о тличающийся тем, что, с целью повышения бьютродействия, он содержит элемент задержки. элемент НЕ, группу из m элементов 2И-ИЛИ, RS-триггер, в регистр сдвига дополнительно введены m D -триггеров и m элементов 2И-ИЛИ, причем выход элемента задержки подключен к входу счз чика и к Снвходу R5 -триггера, а к входу элемента задержки подключен выход генератора одиночных импульсов, выход генератора тактовых импульсов подключен к входу счетчика, выход которого подключен к входу элемента НЕ и к первым входам m элементов 2И-ИЛИ регистра сдвига, вторые выходы которых подключены к выходу элемента НЕ, ; к третьему входу первого элемента 2 И-ИЛ И реI гистра сдвига подключен выход m -BxoEtового с мматора по модулю два, а третий (О вход ( П +1)-го (fi l,rn-l) элемента 2И-Щ1И регистра сдвига подключен к ничному выходу П -го D -триггера ре- 1 гистра сдвига, четвертый вход i -гоs ( { 1, m ) элемента 2H-W1H регистра сдвига подключен к выходу -j -го элемента 2И-ИЛИ группы, С - входы m дополн тельных D -трт1ггеров регистра сдвига Isd подключены к выходу элемента ИЛИ, а к D -входу (п +1)-го дополнительного 00 D -триггера регистра сдвига подключен ю выход И -го дополнительного D -триггера регистра сдвига, к D -входу первогч дополнительного Э- триггера регистра подключен единичный выход m - го О -триггера регистра сдвига, к первому и второму входам элементов 2И-НЛИ группы подключены единичный и нулевой выходы R5-триггера соответственно, вых« ды

Изобретение относится к вычислитепь ной технике и может быть использовано в качестве устройства для определения топологии связей многовходового суммат ра по модулю два, на выходе которого формируется сдвинутые копии дсевдослу- чайных последовательностей. Использование сдвинутых копий псевдослучайных последовательностей позволяет строить экономичные генераторы псевдослучайных чисел, а также организовать автономные устройства для имитации случайных про цессов с заданными характеристиками. Известен генератор псевдослучайных чисел, содержащий регистр сдвига с сумматором по модулю два в цепи обратной связи 1. Недостатком устройства является невозможность получения копий псевдослучайной последовательности сдвинутых более, чем на м тактов, где м - разрядность регистра сдвига, Известен параллельный генератор псев дослучайных чисел, который позволяет по лучать копиипсевдослучайной последова-. тел ьностй, с двинутые на значительно большее число тактов 2. Однако данное устройство позволяет получать копии псевдослучайной последовательности только тшшь для частного случая, когда схема цепи обратной с&язи регистра сдаигв состоит только из одного полусумматора. Известно устройство для формирования сдвинутых копий псевдослучайного сигнала, позволяющее определить топологию связей сумматора по модулю даа, на выходе которого получается крпия исходной псевдослучайной М - последоватепьнрсти сдвинутая на произволыюе количесгао тактов. Пригчем в данном устройстве эта задача решается для общего случая, т.е. для случая, когда в цепи обратной связи регистра сдвига включен многовходовой сумматор по модулю ава (sj. Однако устройство характеризуется сложностью йппаратурного Построения, кот рая в основном определяется наличием элементов памяти. Наиболее близким техническим решение ем к предлагаемому явлйется генератор псевдослучайных последовательностей, соо тоящий из генератора тактовых импулЕ сов, первого элемента ЗАПРЕТ, регистра сдвига с сумматором по модулю два в иепи обратной связи и элементами И, дешифратора, второго элемента ЗАПРЕТ, счетчика, двухвходового элемента И, д)вухвходового элемента ИЛИ, генератора одиночных импульсов н элемента индикации. Генератор отличается значительно уменьшенншыми аппаратурными затратами, что объясняется отсутствием элементов памяти IJ4. , Однако устройство обладает низким быстродействием. jQUffl определения топологии связей многсшходового сумматора по МОДУЛЮ два, на выходе которого формируется сдвинутая на о1 тактов копия севдо&лучайной последовательности, в рассмотренном устройстве необходимо выполнить fj тактов моделирования его , работы,. При больших значениях d напримёр d 2, задача определения топологни связей многхявходового сумматора на существующей алементной базе практически неразрешима. Цель изобретения - увеличение бьютродействия генератора псевдослучайных последовательностей и расширение его функциональных возможностей. Расширение нкциональных возможностей осуществляется за счет возможности определения топологии сумматора по модулю два, на выходе которого формируется копия поев- ; дослучайной последовательносги. ; Для достижения поставленной цели в генератор псевдослучарйных последовательностей, содержащий генератор тактовых голлульссш, выход которого подключен к ервому входу элемент-а ЗАПРЕТ, к второу входу которого подключен выход счет ика, регистр сдвига, состоящий изВ-трнгеров, выход элемента ЗАПРЕТ подключен к первому входу элемента ИЛИ, к второму BxoEiy которого подключен выход генератора одиночных импульсов, а выход элемента ИЛИ подключенк С-входам (п - число разрядов генератора)D -триггеров регистра сдвига, единичные вькоды которых подключены к первым входам сооч ечствуухикк m элементов И группы, вторые входы которых являются первой группой входов генератора, выходы ш эле ментов И группы подключены к соответствующим входам m-входного сумматора по модулю два, введены элемент задерижки, элемент НЕ, группа из m элементов 2И-ИЛИ и Ч5-триггер, в регистр сдвига дополнительно введены m D -триггеров и m элементов 2И-ИЛИ, выход элемента задержки подключен к входу и к С-вх ду RS -триггера, а к входу элемента задержки подключен выход генератора одиночных импульсов, выход генератора тактовых . импульсов подключен в входу счет чика, выход которого подключен к входу элемента НЕ и к первым входам m эле- ментов 2И-ИЛИ регистра сдвига, вторые входы которых подключены к выходу элемента НЕ, к третьему входу первого. элемента 2 И-ИЛ И регистра сдвига подключен 1эь1хс)Д m-Фходного сумматора по модулю два, а третий вход (и +1)-го (П 1, m - 1) элемента 2И-ИЛИ регистр сдвига подключен к единичному выходу Я-го D-триггера регистра сдвига, чет вертый вход -го ( i 1, in) элемента 2И-ИЛИ регистра сдвига подключен к выходу/ -го элемента 2И-ИЛЙ группы, С-входы дополнительных D -триггеров регистра сдвига подключены к выходу элемента ИЛИ, а кО -входу (Ц +1)-го дополнительного - Риггера регистра сдви га подключен выход п -го дополнительного Р -триггера регистра сдвига, к JD- входу первого допоянительногоD-триг гера регистра сдвига подключен единичный выход VTl-го D -триггера регистра сдвига, к первому и второму Входам элемента 2И-ИЛИ группы цодключёны ед ничный и нулевой выходы Р5-триггера соответственно, выходы (2л -1)-хр-три : геров н дополнительных D -триггеров ре;гютра сдвига соединены с третьими входами i -X элементов 2И-ИЛИ группы, выходы 2 1 -X D -триггеров и дополнительных D -триггеров регистра сдвига соединвлы с четвертыми входами t, -х элементов 2И-ИЛИ группы, RS -входы D -триггеров и дополнительных D -триг геров регистра сдвига и RS-Tpinrepa являются второй группой . входов генератора. На фиг. 1 и 2 приведена схема генератора для общего случая и для случая Г 5 с оответочвенно. Генератор псевдослучайных послсдова тельностей состоит из генератора 1 тактовых импульсов, элемента ЗАПРЕТ 2, счетчика 3, элемента 4 задержки, генератора S одиночных импульсов, элемента ИЛИ 6, элемента НЕ 7, D -триггеров 8 регистра сдвига, дополнительных)-триггеров 9 регистра сдвига, элементов И 10, сумматоры 11 по модулю два, элементов 2И-ИЛИ 12 регистра сдвига, элементов 2И-ИЛИ 13 и R3-триггера 14. Функционирование генератора псевдослучайных последовательностей происходит следующим образом. Перед началом работы генератора по входам D -триггеров 8 регистра сдв1а: заносится код начального состояния. Начальный код записьтается по R5-вxoдaм -триггеров 8 регист оа сдвига. По аналогичным входам триггеров счётчшш 3 на счетчик 3 записьшается код предуста- новки. Запись кодаобеспечивает получение коэффициента пересечения счетчика. И, наконец, на R5-тpиггef) 14 записывается значение двоичной цифрыб. При включении генератора 1 тактовых , импульсов через элемент ЗАПРЕТ. 2 и элемент ИЛИ 6 тактовые импульсы поступают на С-входы D -триггеров 8 и дополнительных триггеров 9. Единичный сиг. нал с выхода счетчика 3 поступает на первые выходы элементов 2И-ИЛИ 12, а нулевой сигнал с выхода элемента НЕ7 поступает щ третий вход элементов 2И-ИЛИ 12. Тактгм образом, D -триггеры 8, сумматор по модулю два 11 и элемен-. ты И 10 организуют регистр с сумматором по модулю два в цепи обратной свя зк, генерирующий М-последовательность, При поступлешш тактовых импульсов на регистр сдвггга генерируется М-последовательность, причем c пvmoлы М-последовательности с выхода последнего D -триггера 8 регистра сдвига вдвигаются в сдвиговой регистр сформированный дополнительными триггерами 9. По истечении Ш тактов, когда через элемент ЗАПРЕТ 2 пройдет m импульсов на выходе счетчика 3 сформтфуется нулевой сигнал, который прервет поступление тактовых latnynbcOB на С-входы D -трт геров 8 и 9 регистра сдвига. Нулевой уровень на выходе блока 3 размыкает межразрядные связи в регистре 8 сдв1гга и на вход i -го ( i l,m) триггера 8 регистра сдвтп а через i -ый 10 элемент 2И-ИЛИ 12 подкточает выход 1 -го.элемеота 2И-ИЛИ 13. В зависимости от состояния трт1ггера 14, т.е. от зна чения g на входы V -триггеров 8 подключаются ВЫХОДВ1 четных или нечетных трш геров rpymibi триггеров, состоящей из триггеров 8 и 9 регистра сдвига. При б(-, О на выход первого триггера буДет подключен выход второго триггера, на вход второго триггера будет подключен выход четвертого триггера и т.д., а на входт-го триггера выход 2йг-го. При на вход .первого триггера будет подключен выход первого триггера, на вход второго тирггера выход третьего триггера и т.д., а навход -го триггера выход 2 -1-по. Далее при нажаг н кнопки генерагора 5 оаиночных импульсов DntfHO4HHft импульс через элемент ЙЛЯ 6 поступает на С-вход D 1риггеров 8 и 9 регистра сдвига. По истечени71 времени S , определяемого временем задержки элемента 4 задержки, на С-вход RS-триггера 14 и управляющие входы счетчика 3 поступает управляющий сигнал, который записывает на R5-т-риггер 14 значение цифры ,, а на триггеры счетчика 3 код предустановки. После установки mj да г -т на триггеры счетчика 3 про21цесс функционирования полностью повторяется. Окончательно функционирование устройства прекращается только после выполнения п +2 подобных тактов. Увеличение быстродействия устройства позволяет расширить его функциональные возможности. Так оказьтается возможным определение ксеффицне1ггов, позволяющих получить копии М-последсжательностей, сдвинутых на астрономические число тактов, т.е. т.д. ПреИк ущества предлагаемого генератора по сравнению с известным заключается в возможности получения копий псевдослучайной последовательности на большее число тактов, что в конечном счете позволит существенно расширить функциональньте возможности базового объекта. Применение предлагаемого гелератора, позвсляющехю псвзучать сдвинутые котж псевдослучайной последовательности, отличающегося пОБЬпиенньтм быстродействием позволит строить высоконадежные, стабильные и высококачественные генераторы псевдослучайных чисел, тем самым повысить точность и достоверность решения задач методом Монте-Карло.