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

Изобретение относится к вычисли(тельной технике и может быть использовано в качестве устройства для определения топологии связей многовходового сумматора по модулю два, на выходе которого формируются сдвинутые копии псевдослучайных последовательностей. Использование сдвинутых копий псевдослучайных последовательjнocтeй позволяет строить экономичные генераторы псевдослучайных чисел, а также организовать автономные устройства для иммитации случайных процессов с заданными характеристиками. Из.вестен генератор псевдослучайных чисел, содержащий регистр сдвига с сумматором по модулю два в цепи обратной связи 11. Недостатком этого устройства является невозможность получения коПИЙ псевдослучайной последовательнос ти сдвинутых более, чем на Ы-тактов, где Yn- разрядность регистра сдвига. .- . . Известен параллельный генератор псевдослучайных чисел, позволяющий получать копии псевдослучайной последовательности, сдвинутые на значительно большее, чем на ичисло тактов 2. Однако данное устройство позволяет получать копили псевдослучайной последовательности только лишь для частного случая, когда схема цепи обратной связи.регистра сдвига сост ит только из одного полусумматора. Наиболее близким к предлагаемому изобретению является устройство для формирования сдвинутых копий псевдослучайного сигнала, состоящее из ге нератора тактовых импульсов, первог элемента ЗАПРЕТ, регистра сдвига с обратной связью, дешифратора, второ го элемента ЗАПРЕТ, счетчика, бгэко памяти, сумматоров по модулю два и индикаторов /Сз. Применение устройства для формирования сдвинутых копий псевдослучайного сигнала позволяет определит топологию связей VYI-ХОДОВОГО суммат ра по модулю два, на выходе которог получается копия исходной псевдослу чайной м-последовательности, сдвинутая на произвольное количество. тактов. Причем, в данном устройстве эта задача решается для общего случ т.е. для случая когда в цепи обратНОЙ связи регистра сдвига включен многовходовой сумматор по модулю дв Недостатком данного устройства является сложность аппаратурного построения, которая в основном определяется наличием 4w-О (-l)f i l L-5ni КН, элементов памяти. Даже для сравнительно небольшой величины ж 20 дополнительное количество элементов памяти составит 171 элемент, что почти в 7 раз больше, ;ем затраты оборудования, идущие на другие блоки устройства. Кроме того, наличие блоков памяти снижает быстродействие устройства в целом. Это объясняется тем, что в данном случае необходимо время для записи и считывания информации на блоке памяти. Цель изобретения - сокращение аппаратурных затрат H-- построение устройства для получения сдвинутых ко.пий псевдослучайной последовательности, т.е. упрощение генератора. Поставленная цель достигается тем, что генератор псевдослучайных последовательностей, содержащий генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов ЗАПРЕТ, дешифратор, выход которого соединен с вторым входом второго элемента ЗАПРЕТ, выход которого.соединен с входом счетчика, выход которого соединен с вторым входом первого элемента ЗАПРЕТ и с третьим входом второго элемента ЗАПРЕТ, регистр сдвига, инверсные выходы всех разрядов которого, кроме первого и последнего, соединены с соответствующи1 ш входами дешифратора, а прямые выходы, всех разрядов регистра сдвига соединен с первыми входами соответствующих элементов И группы, вторые входы которых образуют группу входов генератора, а выходы группы элементов И соединены с соответствующими входами сумматора по модулю два, введены элемент И, элемент ИЛИ, блок индикации и генератор одиночного импульса, выход которого соединен с первым входом элемента ИЛИ, второй вход которого подключен к выходу первого элемента ЗАПРЕТ, а выход элемента ИЛИ соединен с входом Сдвиг регистра сдвига, информационный вход которого подключен к выходу элемента И, первый вход которого объединен с .входом блока индикации и подключен к выходу счетчика, выход сумматора по модулю два соединен с вторым входом элемента И и является выходом генератора. На фиг. 1 изображена блок-схема генератораj на фиг. 2 - схема генератора для случая У 5, на фиг. 3 диаграмма, поясняющая, его работу. Генератор псевдослучайных последовательностей состоит из генератора 1 тактовых импульсов, первого элемента ЗАПРЕТ 2, регистра 3 сдвига с сумматором по модулю два в цепи обратной связи, -двухвходовыми элементами И, дешифратора 4, .в.торого элемента ЗАПРЕТ 5 , счетчика б, двухвходового элемента и , двухвходового элемента ИЛИ В, генератора 9 одиночных импульсов и эле мента индикации 10. Генератор тактовых, импульсов 1, второй элемент ЗАПРЕТ 5 , с 1ётчик 6 и первый элемент ЗАПРЕТ 2 включены последовательно, к вторым входам пе вого и второго элемента ЗАПРЕТ 2 и подключены выходы генератора тактовых импульсов 1 и счетчика б соответственно, к третьему входу второг элемента ЭАПрЕТ 5, подключен выход дешифратора 4, к входам которого подключены единичный выход первого разряда и нулевые выходы остальных разрядов регистра 3 сдвига, к перBtfM входам -т -двухвходовых элементов И схемы обратной связи регистра 3 сдвига подключены единичные выхрт да разрядов регистра 3 сдвига, а на вторые входы поданы постоянные коэффициенты, выходы w двухвходо&ЫХ элементов И схемы обратнойсвязи регистра 3 сдвига подключены к входам ш-входового сумматора по мо Яуюо два цепи обратной связи регист ра 3 сдвига, выход которого и выход счетчика 6 подключены к входам двух входового элемента И 7, выход которого подключен к информационному зхаяу первого разряда регистра 3 сдвига/ а шлходэ генератора 9 одиНОЧ1ШХ импульсов и первого элемента ЗАПРЕТ подключены к входам двухвходового элемента ИЛИ ..8, выход котороро подключен к синхровхо ам разр здов регистра 3 сдвига, а выход C4eT4Kka б подключен к входу элемен та 10 индикации. Элемент ЗАПРЕТ2 подобно как и блок 7 представляет собой двухвходо вой элемент.И (фиг. 2). Генератор 1 тактовых импульсов выполнен по схеме с отрицательной обратной (Связью по току. Деотфратор 4 и двухвходовой элемент ИЛИ 8 представляют собой стандартные m-входовой элемент И и двухвходовой элемент КЛИ (фиг.2), того, гл-входовой сумматор по модулю два и 1 -двухвходовых элемен тов И в цепи, обратной связи регистр ра 3 (фиг. 2) также являются стандартными элементами вычислительной техники. Второй элемент ЗАПРЕТ 5 (фиг. 2) состоит из.Йб -триггера двухвходового элемента И и инвертора, которые также являются типовыми элементами, блок 10 представляет собой элементИЛИ-НЕ с индикационной, лампочкой (фиг. 2), Зн ачения коэффициентов 4 в О,1 j, i 1 ,n , определяются ЗДз известных таблиц. Так, для случая vn 4, могут в.частном случае принимать следующие значения i 1, 11 1, oi4 0, 1. Устройство работает следующим образом. Из генератора 1 тактояяе импуль с через элемент ЗАПРЕТ 2 и блок 8 поступают на синхровходы регис а 3 сдвига, который генерирует, псевдослучайную последовательность. В момент времени, когда в ячейках регистра3 сдвига хранится комбинация 100 ... О, т.е. первый триггер находится в единичном состоянии, а все остальные - в нулевом, дешифратор 4 вырабатывает разрешающий сигнал для второго элвмента ЗАПРЕТ 5. Это достигается тем, что дешифратор 4 представляет сюбой у« -входной элемент И, к первому входу которого подключен прямой выход первого разряда регистра 3 сдвига, а к остальным (vn-l) входам, инверсные выходы осташвихся разрядов регистра сдвига. После того, как срабатывает лемент ЗАПРЕТ 5 , тактовые импульсы ; генератора 1 поступают на .вход счетчика б, на который .перед началом работы устанавливается код числа -.6, где - разрядность регистра 3 сдвига, а 8- число тактов, на которое необходимо получить сдвинутую последовательность, В момент времени, когда счетчик 6 хранит код , т.е. по истечении 8-1 тактов, на выходе счетчика б формируется сигнал, запрещшощий прохождение импульсов счета через элемент 5 и элемент 2. Одновременно этим же выходным сигналом блокируется прохождение информации, на первый разряд регистра 3 сдвига через двухвходовой элемент И 7 и включается элемент ,10 индикации. По загоранию лашючки блока индикации оператор делает вывод о том, что информация, хранящаяся на регистре сдвига, является значениями символов tH -последовательности через 8-1 такт. После этого на выходе устройства, т.е. на выходе сумматора по модулю два цепи обратной связи регистра 3 сдвига, фиксируется значение двойной цифры 1 (0) 1о,1 равной t(0) (С-1) ОЛ С), где Qi(e-iy- содержимое Г-го разряда регистра сдвига в 6-1 такт работы, а знак TL означает операцию суммирования по модулю два. Определив значение символа :Ъ(0), содержимое регистра сдвига сдвигается на один разряд путем замыкания контакта генератора 9 бди ночных импульсов, с выхода которого единичный импульс через элемегнт ИЛИ 8 поступает на скнхровходы регистра 3 сдвига. При этом, на первый разряд регистра сдвига записывается значение нуля. После того как информация, хранящаяся в регистре сдвинется на один разряд, значение цифры t (l) равняется ,t(i)«a,())a,(e;. (2), Посде очередного эамыкандся конта та генератора 9 одиночных импульсов значение Ь(2) имеет вид ЪСЧ« QI ()фа, H)ai (, (1)оЛе). (3 и в общем случае для j -го siaMJхания контакта генератора одиночных импульсов 9 получим на выходе сумматора по модулю два, включенного в цепь обратной связи регистра сдвига 3, значение Ъ( j ), определяемое согласно {), где Зв io,w-l} - ко личество импульсов, генерируемое генератором 9; a(i)6 0,1J - содержимое первого разряда регистра 3 сдвига. Ci)-.|.oi,-Oi..j(c-i)«a,()®io,(4)a,( в первые (vn-l) такты работы устройства. Значение коэффициентов сГ; (б) 6 0,1, Vi 1,VM , определяющих топо (Логию связей многовходового сумматора по модулю два, являются решением системы уравнений следующего вида a,e)a,io)5i(e;®aa(o)6;j,te)®...®a«co)5;,(e); a,ten)-ai(i) бде)® а До)йг(е)® - © .(о;б,„( .ai(e+rti-H)))®... )5m(e;4 (5) . При начальньпс условиях 0(0) 1 и 0(0) О, i 2 ,ум , которые соответствуют начальным условиям работы предлагаемого устройства система логических уравнений (5), примет, следующий вид а,се)бде), аден)а 0)di(e e6ate), a e vyi-i)--Q(vn-i)5i(e)©- Фа(о)бп,(е),(б)| Решением системы (6) является выра|жение (7) )a,(,(«)a(e -i-yi). п) Значение b(j) равняется значению Ь;,./((в), что следует из тождественности уравнений С) и (7). Таким образом, путем последовательного эак«кания контактов генератора 9 одиночных импульсов на выходе сумматора по модулю два, включенного в цепь обратной связи регистра 3 сдвига, последовательно получаются значения Коэффициентов cCi (6), определяющие топологию связей сумматора по модулю два, на выходе которого получается последовательноть, сдвинутая на е тактов. Пример. На фиг. 2 приведена -функциональная схема предлагаемого устройства при ги 5 для случая, когда et l,(jL 1,с 1,. О Ol5 1. Допустим требуется определить топологию связей многовходового сумматора, на выходе которого получается сдвинутая на С 9 тактов исходная Y -последовательность. Предварительно на двоичный счетчик б записыается код числа 2-9 23. Импульсы сдвига с блока 1 поступают на сйнхровходы триггеров регистра 3 через элемент И 2 и элемент ИЛИ 8. В момент времени, когда в ячейках регистра 3 сдвига хранится комбинация 10000, дешифратор 4 вырабатывает единичный разрешающий сигнал, который устанавливает триггер ЭЛЕМЕНТА 5 в единичное состояние и,- таким -образом, разрешает прохождение импульсов с генератора 1 тактовых импульсов через элемент И ЭЛЕМЕНТА 5 на вход, счетчика 6. После восьми последующих тактов работы-устройства в целом на счетчике 6 хранится код числа 31, т.е. все триггеЕлл счетчика б находятся в нулевом состоянии. -Сигнал, формируемый на выходе счетчика б, запрещает прохождение .тактовых импульсов через ЭЛЕМЕНТ 5 и ЭЛЕМЕНТ 2. Одновременно этим же сигналом блоки- . руется прохождение информации на nep-i вый разряд регистра 3 сдвига через i двухвходовый элемент И 7 и включается лампочка индикации блока 10. В данный момент на резисторе сдвига 3 фиксируется двоичный код, равный 11001. На выходе сумматора по модулю два цепи обратной связи регистра 3 сдвига формируется значение первого коэффициента &1 (9) 1. После -того, как значение Gb (9) зафиксировано, содержимое регистра сдвига сдвигается на один разряд путем эапвлкания контакта генератора 9 одиночных импульсов , с выхода которого одиночный импульс через элемент ИЛИ 8 поступает на синхровходы регистра сдвига. В результате на регистре i сдвига хранится код 01100 и соответственно на выходе сумматора по модулю два цепи обратной связи C;j.(9)«0. После второго сдвига н.а регистре сдвига имеем код 00110 и на выходе сумматора по модулю два (9) 1. После третьего и четвертого сдвига на регистре имеем 00011 и 00001 и на выходе сумматора по -модулю два соответственно 64 (9) ,0 (Э) 1. Таким образом, коэффициенты, определяющие тополргию связей многовходового сумматора по модулю два, на выходе которого получается сдвинутая на 9Тактов vn-последователь-Чрсть имеет еле дующий вид (J (9) li

а (9) 0,04(9) 1,64(9) 1, % (9) 1. На фиг. 3 приведена временная диarpa 4мa последовательностей на выходе сукматора по модулю два, топология связей определяется коэффициентами ((9) и ИСХОДНОЙ т-последовательностн.

Как видно из фиг. 3 исходная и пр лученные последовательности сдвинуга на девять тактов.

Преимуиюства предлагаемого генератора псевдослучайных последовательност й эаключаютоя в слеруказ/вм

Пре;:№агаемый генератор псевдослучайностей cyioecTBeHHO сокращает аппаратурные затраты з,а счет отсутствия элементов памяти. Так для П) - 20 необходимо №ло бы использовать -171 элемент памяти, что в

№. „1

семь раз больше, чем затраты оборудования, идущие на другие блоки устройства. Дополнительное оборудование составляет весьма незначительный объем. Длг любого w он состоит из одного двухвходового элемента И, одного двухвходовосо элемента ИЛИ, одного одновходового элемента ИЛИ, одного одновходового элемента ИЛИНЕ, трех сопротивлений, емкости и лампочки индикации. , Применение предлагаемого генера3:сч а псевдОслучай1шх последовательностей, отличающегося уменьшенными аппаратурными затра ами, позволяет строить высоконадежные, стабилыше и высококачественные генераторы псев доспучайных чисел, и тем самым повысить точность и достоверность решения задач методом Монте-Карло.

.ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, содержащий генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов ЗАПРЕТ дешифратор, выход которого соединен с вторым входом второго элемента ЗАПРЕТ, выход которого соединен с входом счетчика, выход котор,рго соедданен с вторым входом первого элемента ЗАПРЕТ и с третьим входе вто рого элемента ЗАПРЕТ, регистр сдвига, инверсные выходы всех разрядов кото.рого, кроме пе:рвого и последнего, соединены с соответствующими входами дешифратора, а прямые выходы всех разрядов регистра сдвига соединены соответственно с первыми входг1ми элементов И группы, вторые входы которых являются группой входов генератора, а выходы элементов И группы соединены с соответствующими входами сумматора по модулю.два, отличающийся тем, что, с целью упрощения генератора, он содержит элемент Л, элемент ИЛИ, блок индикации и генератор одиночного импульса, выход которого соединен с первым входом элемента ИЛИ, второй вход ко- торого подключен к выходу первого элемента ЗАПРЕТ, а выход элемента ИЛИ соединен с входом Сдвиг оегистЧ, ра сдвига, информационный вход кото-I рого подключен к выходу элемента И, 2 первый вход которого объединен с входом блока индикации и подключен к выходу счетчика, выход сумматора по модулюдва соединен с вторьм вхо- щяг ,дом г лемента И и является выходом | генератора., .. fj