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

(51) 6 06 Г 7 58 ГОСУД АРС ПО ДЕЛАМ РЕТЕНИУ.06.83.Н, Ярмонский р е г ик ио хнический нс 53) 681.325(088.8 даров Р. Ф,льные машины, 974, с. 247, доров Р. Ф.ельные машины. ельство СССР/00, 1974 (54) (57) .ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, содержащий генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов ЗАПРЕТ, дешиФраор, выход которого соединен с вторым входом второго элемента ЗАПРЕТ, выход которого соединен с входом счетчика,. выход которого соединен с вторым входом первого элемента ЗАПРЕТ и с третьим входом втоЕННЫЙ КОМИТЕТ СССРзоБРетений и ОтнРыть 9 ПИСАНИЕ ИЗАВТОРСКОМУ СВИДЕТЕЛ(56) 1. Яковлев В. В.,Фе Вероятностные вычислите Л., фМашиностроение"., 1 2. Яковлев В. В Фе Вероятностные вычислит 1974, с. 254. 3. Авторское свидет Е 5 г 7 О 12, кл. Н ОЗ К Зрого элемента ЗАПРЕТ, регистр сдвига, инверсные выходы всех разрядов которого, кроме первого и последнего, соединены с соответствующими входа-. ми дешиФратора, а прямые выходы всех разрядов регистра сдвига соединены соответственно с первыми входами эле. ментов И группы, вторые входы кото рых являются группой входов генератора, а выходы элементов И группы соединены с соответствующими входами сумматора по модулю два, о т л ич а ю щ и й с я тем, что, с целью упрощения. генератора, он содержит элемент И, элемент ИЛИ, блок индикации и генератор одиночного импульса, выход которого соединен с первым входом элемента ИЛИ, второй вход которого подключен к выходу первого элемента ЗАПРЕТ, а выход элемента ИЛИ соединен с входом фСдвигф регист ра сдвига, инФормационный вход которого подключгн к выходу элемента И, Я первый вход которого объединен с входом блока индикации н подключен к выходу счетчика, выход сумматора по модулюдва соединен с вторым входом элемента И и является выходомгенератора.Изобретение относится к вычисли 1 тельной технике и может быть использовано в качестве устройства для определения топологии связей многовходового сумматора по модулю два, на выходе которого формируются сдвинутые копии псевдослучайных последовательностей, Использоэание сдвинутых копий псевдослучайных последовательностей позволяет строить экономичные генераторы псевдослучайных чисел, 10 ,а также организовать автонс 6 чиые устройства для иммитации случайных процессов с заданными характеристиками.Известен генератор псевдослучай ных чисел, содержащий регистр сдвига с сумматором по модулю два в це пи обратной связи 1 3Недостатком этого устройства является невозможность получения ко р пий псевдослучайной последовательности сдвинутых более, чем на Ю -так- тов, где в- разрядность регистра сдвига.Известен параллельный генератор25псевдослучайных чисел, позволяющийполучать копии псевдослучайной последовательности, сдвинутые на значительно большее, чем на и числотактов 2,Однако данное устройство позволяет получать копки псевдослучайнойпоследовательности только лишь для,частного случая, когда схема цепиобратной связи. регистра сдвига состоит только из одного полусумматора.Наиболее близким к предлагаемомуизобретению является устройство дляФормирования сдвинутых копий псевдослучайного сигнала, состоящее из генератора тактовых импульсов, первогоэлемента ЗАПРЕТ, регистра сдвига собратной связью, дешифратора, второго элемента ЗАПРЕТ, счетчика, бгэковпамяти, сумматоров по модулю два ииндикаторов 3.Применение устройотва для Формирования сдвинутых копий псевдослучайного сигнала позволяет определитьтопологию связей й-ходового суммато 50ра по модулю два, на выходе которогополучается копия исходной псевдослучайной м-последовательности, сдвинутая иа произвольное количество,тактов. Причем, в данном устройствеэта задача решается для общего случая,т.е. для случая когда в цепи обрат-.ной связи регистра сдвига включенмиоговходовой сумматор по модулю два.Недостатком данного устройства . 60является сложность аппаратурного построения, которая в основном определяется наличием д аэлементов памяти. Даже для сравнитель но небольшой величины в = 20 дополнительное количество элементов памяти составит 171.элемент, что почти в 7 раэ больше, ;ем затраты оборудования, идущие на другие блоки устройства, Кроме того, наличие блоков па" мяти снижает быстродействие устройства в целом, Это объясняется тем, что в данном случае необходимо время для записи и считывания информации на блоке памяти.Цель изобретения - сокращение аппаратурных затрат н- построение устройства для получения сдвинутых копий псевдослучайной последовательнос. ти, т.е. упрощение генератора.Поставленная цель достигается тем, что генератор псевдослучайных последовательностей, содержащий генератор тактовых имйульсов, выход которого соединен с первыми входами первого и второго Элементов ЗАПРЕТ, дешифратор, выход которого соединен с вторым входом второго элемента ЗАПРЕТ, выход которого, соединен с входом счетчика, выход которого соединен с вторым входом первого элемента ЗАПРЕТ и с третьим входом второго элемента ЗАПРЕТ, регистр сдвига, инверсные выходы всех разрядов которого, кроме первого и последнего, соединены с соответствующими входами дешифратора, а прямые выходы. всех разрядов регистра сдвига соединены с первыми входами соответствующих элементов И группы, вторые входы которых образуют группу входов генератора, а выходы группы элементов И соединены с соответствующими входами сумматора по модулю два, введены элемент И, элемент ИЛИ, блок индикации и генератор оди" ночного импульса, выход которого соединен с первым входом элемента ИЛИ, второй вход которого подключен к выходу первого элемента ЗАПРЕТ, а выход элемента ИЛИ соединен с входом "Сдвиг" регистра сдвига, информационный вход которого подключен к выходу элемента И, первый вход которого объединен с,входом блока индикации и подключен к выходу счетчика, выход сумматора по модулю два соединен с вторым входом элемента И и является выходом генератора.На фиг, 1 изображена блок-схема генератора, на Фиг. 2 - схема генератора для случая ю= 5; на Фиг. 3 диаграмма, поясняющая,его работу,Генератор псевдослучайных последовательностей состоит из генератора 1 тактовых импульсов, первого элемента "ЗАПРЕТк 2, регистра 3 сдвига с сумматором по модулю два в цепи обратной связи, ю -двухвходовыми элементами И, дешифратора 4, втброго элемента ЗАПРЕТ 5, счетчика б, двухвходового элемента И 7, двухвходового элемента ИЛИ 8, генератора 9 одиночных импульсов и элемента индикации 10.Генератор тактовых, импульсов 1, второй элемент ЗАПРЕТ 5, счетчик 6 и первый элемент ЗАПРЕТ 2 включены последовательно,.к вторым входам первого я второго элементафЗАПРЕТф 2 и 5, подключены выходы генератора тактовых импульсов 1 н счетчика б соответственно, к третьему входу второго элементафЭАПРЕТ 5, подключен выход; дешифратора 4, к входам которого подключены единичный выход первого разряда и нулевые выходы остальных 15 разрядов регистра 3 сдвига, к пер вым входам:ю -двухвходовых элементов И схемы обратной связи регистра 3 сдвига подключены единичные выхо-, ды разрядов регистра 3 сдвига, а 20 на вторые входы поданы постоянные коэффициенты, выходы ю двухвходовых элементов И схемы обратной связи регистра 3 сдвига подключены к вхсщам л-входового сумматора по мо-:. 2 д дулю два цепи обратной связи регистра 3 сдвига, выход которого и выход счетчика б подключены к входам двухвходового элемента И 7, выход которого подключен к информационному входу первого разряда регистра 3 сдвига, а выходы генератора 9 одиночных импульсов и первого элемента ЗАПРЕТ подключены к входам двухвходового элемента ИЛИ 8, выход кого- рого подключен к синхровхо 4 ам разрядов регистра 3 сдвига, а выход счетчика б подключен к входу элемента 10 индикации.Элементф ЗАПРЕТ" 2 .подобно как и 4 фблок 7 представляет собой двухвходойой элемент,И (Фиг. 2). Генератор 1тактовых импульсов выполнен по схеме с отрицательной обратной связьюпо току. Дешифратор 4 и двухвходовой элемент ИЛИ 8 представляют собойстандартные ю -входовой элемент Ии двухвходовой элемент ИЛИ (Фиг.2),кроме того, щ-входовой сумматор по .модулю два и е -двухвходовых элементов И в цепи, обратной связи регистр 1ра 3 (Фиг. 2) также являются стандартными элементами вычислительнойтехники. Второй элемент"ЗАПРЕТ"5(Фиг. 2) состоит из,И триггерадвухвходового элемента И и инвертора, которые также являются типовымиэлементами, блок 10 представляетсобой элемент ИЛИ-НЕ с индикационной.лампочкой (Фиг, 2).Значения коэффициентов 0( б 01 1 бО4 1,м, определяютсяиз известныхтаблиц. Так, для случая чн= 4,могут в,частном случае приниматьследующие значения с 1 ю 1о(ъ= 1, с+= О,о/ = 165 Устройство работает следукщим образом;Из генератора 1 тактовые импульсы через элементфЗАПРЕТф 2 и блок В поступают на синхровходы регистра 3 сдвига, который генерирует.псевдослучайную последовательность.В момент времени, когда в ячейках регистра 3 сдвига хранится комбинация 100О, т.е. первый триггер находится в единичном состоянии, а все остальные - в нулевом, дешифратор 4 вырабатывает разрешающий сигнал для второго элемента"ЗАПРЕТ 5.Это достигается тем, что дешифратор 4 представляет собой ь -входной элемент И, к первому входу которого подключен прямой выход первого разряда регистра 3 сдвига, а к остальным (в -1) входам, инверсные выходы оставшихся разрядов регистра сдвига. После того, как срабатывает элемент ЗАПРЕТ 5, тактовые импульсыа генератора 1 поступают на,входсчетчика б, на который .перед нача"лом работы устанавливается код числа 2 фф -Я, где 1 ъ - разрядность регистра 3 сдвига, а В- число тактов, на которое необходимо получить сдвинутую последовательность. В момент времени, когда счетчик б хранит код 2 ф" -1, т.е. по истечении 8-1 тактов, на выходе счетчика б формируется сигнал, запрещающий прохождение импульсов счета через эле" мент 5 и элемент 2, Одновременно этим же выходным сигналом блокируется прохождение информации на первый разряд регистра 3 сдвига через двухвходовой элемент И 7 и включается элемент,10 индикации. По загоранию ,лампочки блока индикации оператор делает вывод о том, что информация, хранящаяся на регистре сдвига, является значениями символов Фи -последовательности через 0-1 такт. После этого на выходе устройства, т.е. на выходе сумматора помодулю два цепи обратной связи регистра 3 сдвига, фиксируется значение двойной цифры Ь (О) 0,1 равной Ь(0) = (0 ( Е -1) - а ( Е ), где 0( Е) - содержимое -го разрядарегистра сдвига в В -1 такт работы, а знак Е означает операцию суммирования по модулю два. Определив значение символа . (О), содержимое регистра сдвнга сдвигается на один разряд путем заьыкания контакта генератора 9 одиночных импульсов, с выхода которого единичный импульс через элемент ИЛИ 8 поступает на сннхровходы регистра 3 сдвига. При этом на первый разряд регистра сдвига записывается значение нуля. После того как информация, хранящаяся в регистре сдвинется на один разряд, значение цифры Ь (1) равняется1023325Ъ ьо).а,(е) ео, Иа,(е). (2),4Посде очередного замыкания контак.та генератора 9 одиночных импульсовзначение Ф(2) имеет вид5Ь(И- о(е а)еаюа,(е )еоо,(е).(э) И в общем случае для 1 "го зажкания контакта генератора одиночных 10 импульсов 9 получим на выходе сумматора по модулю два, включенного в цепь обратной связи регистра сдви га 3, значение Ф ( 3 ), определяемое согласно (4), где б 0, и- ко личество импульсов, генерируемое генератором 9; О(1) 6 1 0,1 - содержимое первого разряда регистра 3 сдвига,20Ъ =,%, со. ,(е) о(е 3)е %о(1)сце+-1),1=1 в первые ( в -1) такты работы устройства. значение коэффициентов д (Е) б0,1,),1 1,чм , определяющих топо,логию связей многовходового сумматора по модулю два, являются решейием системы уравнений следующего видаце) =а, (о)б 1 (е)еа 2,(омудеео,(о)о(е);30 ь(е 1) =о 1(1) б,(е) а а(о) б 1 (е.) ее а .(о) б,(е); а(е+-)=о 0-1)б(е)е" еа(о)о (е)(б35При начальных условиях О(0) = 1 .и Ь;(О) = О, 1 У,е , которые соответствуют начальным условиям ра. боты предлагаемого устройства система логических уравнений (5)., примет, 40 следующий вид аЕ)-о(е);а,(Ем)-о, 0)о(Е)ЕЮ(Е),аЕ+в)= о(ю)4(Е)Е Еа(О)6(Е)(б),решением системы (б) является выра;жение (7);(е)=а(Е-)ЕйаФа("-")50И 1Значение Ъ( ) равняется значению Ь (6), что следует из тождественности уравнений (4) и (7). Таким образом, путем последовательного ,замыкания контактов генератора 9 одиночных импульсов на выходе сумматора по модулю два, включенного в цепь обратной связи регистра 3 сдвига, последовательно получаются 60 значения коэффициентов К; (Е), определяющие топологию связей сумматора по модулю два; на выходе которого получается последовательноть, сдвинутая на В тактов. 65 П р и м е р. На фиг. 2 приведена -функциональная схема предлагаемого устройства при ю = 5 для случая, когда Ы 1, А = 1, а( = 1, а(А Ю, ау = 1. Допустим требуется определить топологию связей многовходового сумматора, на выходе которого получается сдвинутая на 0 = 9 тактов исходная рн -последовательность. Предваритель. но на двоичный счетчик б записыается код числа 2 -9 = 23, Импульсы сдвига с блока 1 поступают на синхровходы триггеров регистра 3 через эле мент И 2 и элемент ИЛИ 8. В момент времени, когда в ячейках регистра 3 сдвига хранится комбинация 10000, дешиФратор 4 вырабатывает единичный разрешающий сигнал, который устанавливает триггер ЭЛЕМЕНТА 5 в единичное состояние и, таким образом, разрешает прохождение импульсов с генератора 1 тактовых импульсов через элемент И ЭЛЕМЕНТА 5 на вход, счетчика б. После восьми последующих тактов работы устройства в целом на счетчике б хранится код числа 31, т,е. все триггеры счетчика б находятся в нулевом состоянии. Сигнал, формируеьый на выходе счетчика б, запрещает прохождение тактовыхимпульсов через ЭЛЕМЕНТ 5 и ЭЛЕМЕНТ 2. .Рдновременно этим же сигналом блокируется прохождение информации на пер вый разряд регистра 3 сдвига через двухвходовый элемент И 7 и включается лампочка иьдикации блока 10. В данный момент на резисторе сдвига 3 Фиксируется двоичный код, равный 11001. На выходе сумматора по модулю два цепи обратной связи регистра 3 сдвига Формируется значение первого коэффициента О(9) = 1. После того, как значение б (9) зафиксировано, содержимое регистра сдвига сдвигается на один разряд путем замыкания контакта генератора 9 одиночных импульсов, с выхода которого одиночный импульс через элемент ИЛИ 8 поступает на синхровходы регистра сдвига. В результате на регистре сдвига хранится код 01100 и соответственно на выходе сумматора по модулю два цепи обратной связи О (9)0, После второго сдвига на регистре сдвига имеем код 00110 и на выходе сумматора по модулю два бз(9) = 1. После третьего н четвертого сдвига на регистре имеем 00011 и 00001 и на выходе сумматора по модулю два соответственно 64 (9) = 1,0 (9) = 1.Таким образом, коэффициенты, определяющие тополргию связей многовходового сумматора по модулю два, на выходе которого получается сдвинутая на 9 тактов И 1-последовательность имеет следующий вид 0(9) = 1,1023325Составитель А. Карасо Редактор Н. Воловик Техред А.Ач . Корректор Подписное Бои 4213/33 Тираж 706ВНИИПИ Государственного комитета ССпо делам изобретений и открытий113035, Иосква, Ж; Раушская наб.,аказ д. 45 иал ППЙ "Патент"., г. Ужгород, Ул. Проектная, 4 дю (9) = О О (9) = 1, бд.(9) = 1, . (9 1. На Фиг. 3 приведена временная диаграмма последовательностей на выходе сумаатора по модулю два, топология связей которого определяется коэФфициентами 6(9) и исходной е-последовательности.Как видно из Фиг. 3 исходная и по- лученные последовательности сдвинуты на девять тактов.Преимущества предлагаемого гене ратора псевдослучайных последовательностей заклвчавтоя в следующем. Предлагаемый генератор псевдо- случайностей существенно окращает 15 аппаратурные затраты эа счет отсут-ствия элементов памяти. Так для Ф = 20 необходимо было бы использовать 171 элемент памяти, что в семь раз больше, чем затраты обору дования, идущие на другие блоки устройства. Дополнительное оборудо-ванне составляет весьма незначитель" ный объем. Длг любого ИЧ:он состоит из одного двухвходового элемента И, одного двухвходового элемента ИЛИ, одного одновходового элемента ИЯИ, одного одновходового элемента ИЛИНЕ, трех сопротивлений, емкости и лампочки индикации.Применение предлагаемого генерасора псевдослучайных последовательностей,отличающегося уменьшенными аппаратурными затраами, позволяет строить высоконадежные, стабильные и высококачественные генераторы псевдослучайных чисел, и тем савнм повысить точность и достоверность решения задач методом Монте-.Карло.