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

 

ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, содержащий генератор тактовых импульсов , выход которого подключен к перво-. му входу элемента ЗАПРЕТ, к второму входу которого подключен выход счетчика , регистр сдвига, состоящий из 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-триггера соответственно, вых« ды

„„SU„„1020821

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

3 (51) 06 7/58

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3393501/18-24 (22 ) 12.02.82 (46) 30.05.83. Бюл. J4 20 (72) В. Н, Ярмолик (71) Минский радиотехнический институт (53 ) 68 1.32 5(088. 8) (56) 1. Яковлев В. В., Федоров P. Ф.

Вероятностные вычислительные машины.

Л., "Машиностроение", 1974, с. 247.

2. Там же, с, 254.

3. Авторское свицетельство СССР

No 5270 l2, кл. Н 03 К 5/13, 1972.

4. Авторское свидетельство СССР по заявке Уа 3252992/18-24, кл. 06 F 7/58, 1981 (прототип). (54) (57) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, содержащий генератор тактовых импульсов, выхоц которого подключен к первому вхоцу элемента ЗАПРЕТ, к второму вхоцу которого подключен выход счетчика, регистр сцвига, состоящий из D -триггеров, выхоц элемента ЗАПРЕТ подключен к первому входу элемента ИЛИ, к вто рому вхоцу которого поцключен выхоц генератора оциночных импульсов, а выход элемента ИЛИ поцключен к С -вхоцам rtl (П1 число разряцов генератора).)3 -триггеров регистра сдвига, единичные выхоцы которых поцключены к первым входам соответствующих rn элементов И группы, вторые вхоцы которых являются первой группой входов генератора, выходы й) элементов И группы поцключены к соотве1 ствующим входам п-вхоцового сумматора помоцулюцва, о тличающийся тем, что, с целью повышения быстроцействия, он содержит элемент зацержки, элемент НЕ, группу из N элементов

2И-ИЛИ, R5-триггер, в регистр сдвига дополнигельно введены гп D -триггеров и (п элементов 2И-ИЛИ, причем выход элемента зацержки поцключен к вхоцу счет чика и к -axon P5-триггера, а к входу элемента задержки подключен выход генератора одиночных импульсов, выход генератора тактовых импульсов поцключен к входу счетчика, выход которого поцключен к вхоцу элемента НЕ и к первым входам п1 элементов 2И-ИЛИ регистра сдвига, вторые выхоцы которых подключены к выходу элемента НЕ,; к третье му вхоцу первого элемента 2И-ИЛИ ре гистра сдвига подключен выхоц m -входовогосумматора по моцулю два, а третий вход (rl +i)-го (rl =i,m- 1) еаемента (/)

2И-HJ1H регистра сдвига поцключен к еци ° ничному выходу Д -го D -триггера регистра сцвига, четвертый вхоц у -го (1 = 1,m ) элемента 2И-ИЛИ регистра сцвига подключен к выходу g -го элемен- Owe та 2И-ИЛИ группы, С вЂ” вхоцы Nцополнии» тельных Х3 -триггеров регистра сцвига подключены к выходу элемента ИЛИ, а к ее

D -входу (П +1)-го цополнительного О©

I) -триггера регистра сцвига поцключен выход 0 -го дополнительного 33 -триггера регистра сдвига, к 0 -вхоцу первого дополнительного D- триггера регистра сдви:га подключен единичный выход щ - го

Q -триггера регистра сдвига, к первому и второму вхоцам элементов 2И-ИЛИ группы подключены ециничный и нулевой выходы R5-триггера соответственно, выхэ. ды (2 4 -1)-х D -триггеров и цополнительных Q -триггеров регистра сцвига соединены с третьими входами < -х эле.ментов 2И-ИЛИ группы, выхоцы 2 i -х

Ц -триггеров и дополнительных I3 -триг

1020821 и цополнительных D триггеров регист ра сдвига ИЯ5-триггера являются второй группой вхоцов генератора. геров регистра сцвига соединены с с четвертыми входами i -х элементов

2И-ИЛИ группы,Р5-вхоцы 2 «триггеров

1 2

Изобретение относится к вычислитель- рая в основном определяется наличием ной технике и может быть использовано элементов памяти, в качестве устройства для опрецеления На более близким m K pe%em топологии связей многовходового суммато ем к предлагаемому является генератор ра по модулю цва, на выходе которого 5 псевцослучайных послецовательностей, сосформируется сдвинутые копии,псевцослу . ° тоящий иэ генератора тактовых импул чайных последовательностей. Использова- сов, первого элемента ЗАПРЕТ, регистра ние "сдвинутых копий псевдослучайных cltsara с сумматором по модулю два В последовательностей позволяет строить - цепи обратной связи и элементами И, цээкономичные генераторы псевдослучайных 10 шифратора, второго элемента ЗАПРЕТ, чисел, а также организовать автономные счетчика, цвухвходового элемента И, устройства для имитации случайных про двухвходового элемента ИЛИ, генератора цессов с заданными характеристиками. одиночных импульсов и элемента инцикаИзвестен генератор псевдослучайных пии. Генератор отличается значительно чисел, содержащий регистр сдвига с сум . 15 уменьшеннными аппаратурными затратами, матором по моцулю цва s цепи обратной что объясняется отсутствием элементов связи (1) . памяти $4) .

Недостатком устройства является не-, Однако устройство облацает низким возможность получения копий псевцоспу- быстродействием.,Цля опрецеления топочайной последовательности сдвинутых 20 логии связей многовходового сумматора более, чем на м тактов, гце м - разряд- по модулю цва, на выходе которого форность регистра сдвига. мируется сдвинутая на d тактов копия

Известен параплельный генератор поев- псевцослучайной последовательности, в цослучайных чисел, который позволяет по- рассмотренном устройстве необходимо лучать копиипсевдослучайной последоВа-. 25 выполнить Д- f тактов моцелирования его, тельности сдвинутые на значительно работы,, При больших значениях d, напри1 о большее число тактов (2). мер Д > 2 ., задача определения тополоОцнако данное устройсиэо позволяет гии связей многсвходового сумматора на пол;учать копии псевцослучайной послецо-,существующей элементной базе практичес, вательности только лишь для частного g0 ки неразрешима. случая, когда схема цепи обратной связи j Бель изобретения - увеличение быстро регистра сдвига состоит только из одного действия генератора псевдослучайных полусумма тора. последовательностей и расширение его

Известно устройство для формирования ф ппсциональных возможностей. Расширение сдВинутых копий псевдослучайного сиГна 3 ф нкциОнальных Возможностей осущест« ла, позволяющее Определить топологию вляется за счет Возможности определения .Связей сумматора по модулю цва, на вы топологии сумматора по модулю два, на ходе которого попучается копия исходной выходе которого формируется копия псев- . псевдослучайной М - последовательности дослучайиой последовательности. сдвинутая на произвольное количестъо 40 . Йля достижения поставленной цели В тактов. Причем В данном устройстве эта генератор псевцосдучайных последователь= задача решается для общего случая, т.е. Иостей, содержащий генераюр тактовых для случая, коГда В цепи Обратной связи, импульсов, shnog KoToporo подключен z регистра сдвига включен многовходовой первому Входу элемента 3AIIPE7, к Второ сумматор по модулю два 3 . 4:му Входу которого поцключен выход счетсчика Регистр сдвига, состоящий из 0 трщ

Однако устройство характеризуется Геров, Выход элемента ЗАПРЕТ поцклю сложностью аппаратурного йостроения, кото- чен к первому входу элемента ИдИ, z

3 10 второму входу которого подключен выход генератора оциночных импульсов, а выход элемента ИЛИ подключен к С-входам (m — число разрядов генератора)13 -триггеров регистра сдвига, ециничные выходы которых подключены к первым входам соопретствующих т элементов И группы, вторые входы которых являются первой группой входов генератора, выходы m элементов И группы поцключены к соответствующим входам т -входного: сумматора по модулю gsa, введены элемент задержки, элемент НЕ, группа из rA элементов

2И-ИЛИ и ЯБ-триггер, в регистр сцвига дополнительно введены m 0-триггеров и

N элементов 2И-ИЛИ, выход элемента задержки подключен к входу и к С вхо

qy RG -триггера, а к входу элемента задержки подключен выхоц генератора одиночных импульсов, выхоц генератора тактовых импульсов поцключен в вхоцу сче чика, выхоц которого подключен к входу элемента НЕ и к первым вхоцам m эле- - . ментов 2И-ИЛИ регистра сдвига, вторые входы которых подключены к выходу элемента НЕ, к третьему вхоцу первого элемента 2И-ИЛИ регистра сцвига подключен выход m -вхоцного сумматора go модулю цва, а третий вхоц (rl +1)-го (П = 1, П)-1) элемента 2И-ИЛИ регистра сдвига подключен к единичному выходу и го 0 -триггера регистра сцвига, четвертый вхоц j -го (j = 1, Ф } элемента

2И-ИЛИ регистра сцвига поцключен к выхоцу / -го элемента 2И-ИЛИ группы, C-входы цополнительных D -триггеров регистра сцвига поцкпючены к выходу элемейта ИЛИ, а к D -вхоцу (Д +.1)-rn дополнительногоЭ +триггера регистра сдвига подключен выход д -го дополнительного 3 -триггера регистра сдвига, к

Q- входу первого дополнительного13-триггера регистра сцвига поцключен ециничный выход m-го D -триггера регистра сдвига, к первому и второму вхоцам элемента 2И-ИЛИ группы подключены единичный и нулевой выходы Р5-триггера соответственно, выходы (2 1 -1) -х D-триг. геров и дополнительных 9 -триггеров реги:тра сдвига соецинены с третьими вхоцами i -х элементов 2И-ИЛИ группы, выхоцы 2 -х D òðèããåðîâ и цополнительных D -триггеров регистра сцвига соединен| с четвертыми BxollBMH -х элементов 2И-ИЛИ группы, RS -вхоцы

Q -триггеров и цополнительных D -триг геров регистра сдвига иР5-триггера являются второй группой . входов генератор&

2082 1 4

На фиг. 1 и 2 приведена схема генератора пня общего случая и цля случая

_#_ = 5 соответственно;

Генератор псевдослучайных ослецова» тельностей состоит из генератора 1 тактовых импульсов, элемента ЗАПРЕТ 2, счетчика 3, элемента d задержки, гене ратора 5 оцнночнык импульсов, элемента

ИЛИ 6, элемента НЕ 7, D « триггеров 8

10 регистра сдвига, дополнительных Э- тригге° ров 9 регистра сцвига, элементов И 10, сумматоры 11 по моцулю два, элементов

2И-ИЛИ 12 регистра сцвига, элементоя

2И-ИЛИ 13 иК9-триггера 14.

15 Фу нкционирование генератора псевдо случайных последовательностей происходит . следующим образом.

Перец начапом работы генератора по входам D -триггеров 8 регистра;сцвща

20 заносится код начального состояния. Начальный код записывается по R5-входам -триггеров 8 регистра сдвига. По agaлогичным входам триггеров счетчика 3 на счетчик 3 записывается коц прецустад новки. Запись коца обеспечивает получение коэффициента пересечения счетчика. И, наконец, на R5-триггер 14 записываешься значение двоичной цифрыф .

При включении генератора 1 тактовых импульсов через элемент ЗАПРЕТ 2 и элемент ИЛИ 6 тактовые импульсы поступают на С-входы D триггеров 8 и дополнительных триггеров 9. Единичный car» нал с выхода счетчика 3 поступает на

35 первые выходы элементов 2И-ИЛИ 12

Т а нулевой сигнал с выхода элемента НЕ7 поступает на третий вход элементов

2И-ИЛИ 12. Таким образом,O -триггеры

8, сумматор по модулю два 11 и элемен-.

4 ты И 10 организуют регистр с суммато ром по модулю два в цепи обратной свя зн, генерирующий М-последовательность., Прн поступлении тактовых импульсов на регистр сдвига генерируется М-последова45 тельность, причем симвопы М-последовательности с выхода последнего I3 -триггера 8 регистра сдвига вдвигаются в сдвиговой регистр сформированный дополнительными григгерами 9. По истечении г0 тактов, когда через элемент ЗАПРЕТ 2

5 пройдет и импульсов на выходе счетчика

3 сформируется нулевой сигнал, который прервет поступление тактовых импульсов на С-входы 0 -триггеров 8 и 9 регистра сдвига.

Нулевой уровень на выходе блока 3 размыкает межразрядные связи в регистре 8 сдвига и на вход -го (=1,rn) трштера 8 регистра сдвига через -ый

1020 элемент 2И-ИЛИ 12 подключает выход

q -ro элемента 2И-ИЛИ 13. В зависимости от состояния триггера 14, т.е. от зна чения g на входы Х) -триггеров 8 подключаются выходы четных или нечетных триггеров группы триггеров, состоящей из триггеров 8 и 9 регистра сдвига. При о= О на выход первого триггера будет подключен выход второго триггера, на вход второго триггера будет подкл?очев о выход четвертого триггера и т.д„а на вход щ-го триггера выход 2???-ro. При ?1 на вход первого триггера будет подключен выход первого триггера, на вход второго тирггера выход третьеготриггера и т.д., а навход -ro триггера выход 2 -1-го.lIaлее при нажатии кнопки генератора 5 одиноч- . ных импульсов одиночный импульс через элемент ИЛИ 6 поступает на С-вход D триггеров 8 и 9 регистра сдвига. По истече- О ни?? времени с,, определяемого временем задержки элемента 4 задержки, на С-вход

ЯБ -триггера 14 и управляк?щие входы счет п?ка 3 пос Гупйет у??р&в??яю???ий сигнал у который записывает на I? .5 -триггер 14 зна-> чение цифры,, а на триггеры счетчика

3 код предустановки. После установки ко РО 3 да2 -???на триггеры счетчика 3 про821 4 цесс, функционирования полностью повторяется. Окончательно функционирование устройства прекращается только после выполнения п +2 подобных тактов.

Увеличение быстродействия устройства позволяет расширить его функциональные возможности. Так оказывается возможным определение к?вффициентов, позволяющих пс?лучить копии М-последовательностей, . сдвинутых на астрономические число тактов, т.е. длясь 2 и т.д.

Преимущества предлагаемого генератора по сравнению с известным заключается в возможности получения копий псевдослучайной последовательности на большее число тактов, что в конечном счете позволит существенно расширить функциональные возможности базового объекта.

Применение предлагаемого генератора, позволяющего получать сдвинутые копии псевдослучайной последовательности, отличающегося повышенным быстродействием позволит строить высоконадежные, стабкпьнь?е и высококачественные генераторы псевдослучайных чисел, тем самым повыоить точность и достоверность решения задач методом Монте-Карло.

1020821

Составитель А. С. Карасов

Техред F Ðóáöîâà Корректор А. Лзятко

Редактор С. Юско

Филиал ППП Патеж, r. Ужгород, ул. Проектная,4

Заказ 3898/41 Тираж 706 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-З5, Раушская наб., д. 4/5