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

 

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

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

ЭИЦ

РЕСПУБЛИК

«9) 111) З(51) 6 06 F 7 58

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

К ABTOPGHOMY СВИДЕТЕЛЬСТВУ !

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPHTHA (21) 3252992/18-24 (22) 06.03.81 (46) 15.06.83. Бюл. 9 22 ,(72) В. Н. Ярмолик (71) Минский радиотехнический институт (53) 681.325(088.8) (56) 1. Яковлев В. В.,Федоров Р. Ф.

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

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

2. Яковлев В. В., Федоров Р. Ф.

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

1974, с. 254.

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

В 527012 а кл. Н 03 K 3/00, 1974 (прототип). (54)(57) . EHEPATOP ПСЕВДОСЛУЧАЙНЫХ

ПОСЛЕДОВАТЕЛЬНОСТЕЙ, содержащий генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов ЗАПРЕТ, дешифратор, выход которого соединен с вторым входом второго элемента

ЗАПРЕТ, выход которого соединен с входом счетчика, выход которого соединен с вторым входом первого элемента ЗАПРЕТ и с третьим входом вто-, рого элемента ЗАПРЕТ, регистр сдвига, инверсные выходы всех разрядов которого, кроме первого и последнего, соединены с соответствующими входа-. мн дешифратора, а прямые выходы всех разрядов регистра сдвига соединены соответственно с первыми входами элементов И группы, вторые входы которых являются группой входов генератора, а выходы элементов И группы соединены с соответствующими входами сумматора по модулю два, о т л ич а ю шийся тем, что, с целью упрощения. генератора, он содержит элемент И, элемент ИЛИ, блок индикации и генератор одиночного импульса, выход которого соединен с первым входом элемента ИЛИ, второй вход которого подключен к выходу первого элемента ЗАПРЕТ, а выход элемента

ИЛИ соединен с входом "Сдвиг" регист ра сдвига, информационный вход которого подключен к выходу элемента И, первый вход которого объединен с входом блока индикации н подключен к выходу счетчика, выход сумматора по модулю два соединен с вторым вхо1 дом элемента И и является выходом генератора

1023325

Изобретение относится к вычисли тельной технике и может быть использовано в качестве устройства для определения топологии связей многовхо дового сумматора по модулю два, на выходе которого формируются сдвинутые копии псевдослучайных последовательностей. Использоэание сдвинутых копий -псевдослучайных последователь ностей позволяет строить экономичные генераторы псевдослучайных чисел, ;а также организовать автономные устройства для иммитации случайных процессов с заданными характеристиКОМИ, Известен генератор псевдослучай- 15 ных чисел, содержащий регистр сдвига с сумматором по модулю два в це« пи обратной связи (1 ).

Недостатком этого устройства является невозможность получения ко« р пий псевдослучайной последовательности сдвинутых более, чем на Ю -так- тов, где и- разрядность регистра сдвига.

Известен параллельный генератор:

25 псевдослучайных чисел, позволяющий получать копии псевдослучайной последовательности, сдвинутые на значительно большее, чем на ви число тактов (2).

Однако данное устройство позволяет получать копки псевдослучайной последовательности только лишь для, частного случая, когда схема цепи обратной связи ° регистра сдвига состо- >5 ит только из одного полусумматора.

Наиболее близким к предлагаемому изобретению является устройство для формирования сдвинутых копий псевдослучайног сигнала, состоящее из ге- 4р нератора тактовых импульсов, первого элемента ЗАПРЕТ, регистра сдвига с обратной связью, дешифратора, второго элемента ЗАПРЕТ, счетчика, бгзков памяти, сумматоров по модулю два и индикаторов 3 .

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

1 миоговходовой сумматор по модулю два.

Недостатком данного устройства . 6О является сложность аппаратурного построения, которая в основном определяется наличием элементов памяти. Даже для сравнитель« но небольшой величины м = 20 дополнительное количество элементов памяти составит 171.элемент, что почти s

7 раэ больше, ;ем затраты оборудования, идущие на другие блоки устройства. Кроме того, наличие блоков памяти снижает быстродействие устройства в целом. Это объясняется тем, что в данном случае необходимо время для записи и считывания информации

-на блоке памяти.

Цель изобретения - сокращение аппаратурных затрат н- построение устройства для получения сдвинутых копий псевдослучайной последовательности, т.е. упрощение генератора.

Поставленная цель достигается тем, что генератор псевдослучайных последовательностей, содержащий генератор тактовых имйульсов, выход которого соединен с первыми входами первого и второго Элементов ЗАПРЕТ, дешифратор, выход которого соединен с вторым входом второго элемента

ЗАПРЕТ, выход которого, соединен с входом счетчика, выход которого соединен с вторым входом первого элемента ЗАПРЕТ и с третьим входом второго элемента ЗАПРЕТ, регистр сдвига, инверсные выходы всех разрядов которого, кроме первого и последнего, соединены с соответствующими входами дешифратора, а прямые выходы. всех разрядов регистра сдвига соединены с первыми входами соответствующих элементов И группы, вторые входы которых образуют группу входов генератора, а выходы группы элементов И соединены с соответствующими входами сумматора по модулю два, введены элемент И, элемент

ИЛИ, блок индикации и генератор одиночного импульса, выход которого соединен с первым входом элемента

ИЛИ, второй вход которого подключен к выходу первого элемента ЗАПРЕТ, а выход элемента ИЛИ соединен с входом "Сдвиг" регистра сдвига, информационный вход которого подключен к выходу элемента И, первый вход которого объединен с .входом блока индикации и подключен к выходу счетчика, выход сумматора по модулю два соединен с вторым входом элемента

И и является выходом генератора.

На фиг. 1 изображена блок-схема генератора, на фиг. 2 — схема генератора для случая ю= 5; на фиг. 3 диаграмма, поясняющая,его работу, Генератор псевдослучайных последовательностей состоит из генератора 1 тактовых импульсов, первого элемента "ЗАПРЕТ" 2, регистра 3 сдвига с сумматором по модулю два в цепи обратной связи, 1 -двухвходовыми элементами И, дешифратора 4, второго элемента ЗАПРЕТ 5, счетчи1023325 ка 6, двухвходового элемента И 7, двухвходового элемента ИЛИ 8, генератора 9 одиночных импульсов и элемента индикации 10.

Генератор тактовых, импульсов 1, второй элемент ЗАПРЕТ 5, счетчик б и первый элемент ЗАПРЕТ 2 включены последовательно,.к вторым входам первого я второго элемента"ЗАПРЕТ 2 и 5,. подключены выходы генератора тактовых импульсов 1 и счетчика 6 соответственно, к третьему входу второго элемента"3At1PET 5, подключен выход; дешифратора 4, к входам которого подключены единичный выход первого разряда и нулевые выходы остальных 15 разрядов регистра 3 сдвига, к пер вым входам: -двухвходовых элементов И схемы обратной связи регистра

3 сдвига подключены единичные выхо-, ды разрядов регистра 3 сдвига, а 2О на вторые входы поданы постоянные коэффициенты, выходы ю двухвходовых элементов И схемы обратной связи регистра 3 сдвига подключены к вхсщам v-входового сумматора по мо-:- 2д дулю два цепи обратной связи регистра 3 сдвига, выход которого и выход счетчика б подключены к входам двухвходового элемента И 7, выход которого подключен к информационному вхаду первого разряда регистра 3 сдвига, а выходы генератора 9 одиночных импульсов и первого элемента

ЗАПРЕТ подключены к входам двухвходового элемента ИЛИ . 8, выход когорого подключен к синхровхо4ам разрядов регистра 3 сдвига, а выход счетчика б подключен к входу элемента 10 индикации.

Элемент ЗАПРЕТ"2 .подобно как и Щ блок 7 представляет собой двухвходовой элемент.И (фиг. 2). Генератор 1 тактовых импульсов выполнен по схе» ме с отрицательной обратной связью по току. Дешифратор 4 н двухвходовой элемент HJIH 8 представляют собой стандартные vn -входовой элемент И и двухвходовой элемент ИЛИ (Фиг.2), кроме того, ю-входовой сумматор по. модулю два и м -двухвходовых элемен» тов И в цепи. обратной связи регистр1 ра 3 (Фиг. 2) также являются стандартными элементами вычислительной техники. Второй элемент"ЗАПРЕТ"5 (Фиг. 2) состоит из,RS «триггера двухвходового элемента И и инвертора, которые также являются типовыми элементами, блок 10 представляет собой элемент ИЛИ-НЕ с индикационной.лампочкой (Фиг, 2).

Значения коэффициентов (6 0,1) б()

4 1,м, определяются из известных таблиц. Так, для случая vn- =4, могут в,частном случае принимать . следующие значения с,, 1, (1, О(ъ 1 р О(+- 0 0/ =- 1 б5

1 устройство работает следукщим образом;

Из генератора 1 тактовые импульсы через элемент"ЗАПРЕТ"2 и блок В поступают на синхровходы регистра

3 сдвига, который генерирует.псевдослучайную последовательность.

В момент времени, когда в ячейках регистра 3 сдвига хранится комбинация 100 ... О, т.е. первый триггер находится в единичном состоянии, а все остальные - в нулевом, дешифратор 4 вырабатывает разрешающий сигнал для второго элемента"ЗАПРЕТ 5.

Это достигается тем, что дешифратор 4 представляет собой ь| -входной элемент И, к первому входу которого подключен прямой выход первого разряда регистра 3 сдвига, а к остальным (yn -1) входам, инверсные выходы оставшихся разрядов регистра сдвига. После того, как срабатывает элемент ЗАПРЕТ 5, тактовые импульсы е генератора 1 поступают на,вход счетчика б, на который .перед началом работы устанавливается код числа 2 -Я, где и - разрядность регист» ра 3 сдвига, а Е- число тактов, на которое необходимо получить сдвинутую последовательность. В момент времени, когда счетчик б хранит код 2н -1, т.е. по истечении

8-1 тактов, на выходе счетчика 6

Формируется сигнал, запрещающий прохождение импульсов счета через эле" мент 5 и элемент 2. Одновременно этим же выходным сигналом блокируется прохождение информации на первый разряд регистра 3 сдвига через двухвходовой элемент И 7 и включается элемент,10 индикации. По загоранию ,лампочки блока индикации оператор делает вывод о том, что информация, хранящаяся на регистре сдвига, является значениями символов Фи -последовательности через Р-1 такт. После этого на выходе устройства, т.е. на выходе сумматора по модулю два цепи обратной связи регистра 3 сдвига, фиксируется значение двойной цифры Ь (O) (0,1) равной Ь(0) = f„ya; (Е -1) - а, (Е ), где o,(Е-1) - содержимое i-го разряда регистра сдвига в Е -1 такт работы, а знак означает операцию суммирования по модулю два. Определив значение символа :Ф (О), содержимое регистра сдвига сдвигается на один разряд путем заьыкания контакта генератора 9 одиночных импульсов, с выхода которого единичный импульс через элемент ИЛИ

8 поступает на синхровходы регистра

3 сдвига. При этом на первый разряд регистра сдвига записывается значение нуля. После того как информация, хранящаяся в регистре сдвинется на один разряд, значение цифры ф (1) равняется

Ы1)-a,(Е1) Эа, ()а,(Е). (2), 4

Посде очередного замыкания контак«. та генератора 9 одиночных импульсов значение Ь(2) имеет вид

b(n) - a„(e.ÿ.) еа„(1) а, (е )еа„()а,(е). (э)

И в общем случае для j»»ro замыкания контакта генератора одиночных 10 импульсов 9 получим на выходе сумматора по модулю два, включенного в цепь обратной связи регистра сдви га 3, значение b(), определяемое согласно (4), где б (О, е-1) - ко-. личество импульсов, генерируемое генератором 9; 01(1 ) 6 1 0,1) - содержимое первого разряда регистра 3 сдвига, 20

b(j)=9, с„о„» (е-1>*а„(е+ >еаза„(4)сь,(е+ 1), qi j+q 1=1 1 в первые (Ь1-1 ) такты работы устройства. Значение коэффициентов Д„ (Е)

6 0,1,),q 1,vn, определяющих топо:логию связей многовходового сумматора по модулю два, являются решейием системы уравнений следующего вида

ЩЕ) =а, (О)о1 (Е)ва (ОМАРЕ...Еа(О)д„(Е);

a„(e 1)=а1(1) 6,(е)а а„(о) б (е)в...е а „(о) б„,(е); а1(+ -1)=а„(м-1)о1(е)ю." еа„(о)б(е).((s$

35 °

При начальных условиях 01(0) = 1 .и б;(О) = О, 1 Y vn, которые соответствуют начальным условиям ра боты предлагаемого устройства система логических уравнений (5)., примет, 40 следующий вид а„ е)-о„(е); а,(е 1}-а„(1) о„(е)М (е), а„(-1)=a„(v- )о„-(е)е... еа„(о)о„(е)(ь), решением системы (б) является выра;жение (7) б;(Е) =а„(Е- . )Е ха„(п>а„(+ 1-и) (7)

1-1 50 п 1

Значение O(j} равняется значению

Ь1 „(6}, что следует из тождественности уравнений (4) и (7). Таким образом, путем последовательного .замыкания контактов генератора 9 одиночных импульсов на выходе сумматора по модулю два, включенного в цепь обратной связи регистра 3 сдвига, последовательно получаются значения коэффициентов К; (e), опре деляющие топологию связей сумматора по модулю два; на выходе которого получается последовательноть, сдвинутая на е тактов. 65

Пример. На фиг. 2 приведена

- функциональная схема предлагаемого устройства при ю = 5 для случая, когДа Ы1 1 aL = 1 aLЗ= 1 а(4 0

dy = 1.

Допустим требуется определить топологию связей многовходового сумматора, на выходе которого получается сдвинутая на = 9 тактов исходная уп -последовательность. Предварительно на двоичный счетчик б записыается код числа 2 -9 = 23. Импульсы сдвига с блока 1 поступают на синхровходы триггеров регистра 3 через эле« мент И 2 и .элемент ИЛИ 8. В момент времени, когда в ячейках регистра

3 сдвига хранится комбинация 10000, дешифратор 4 вырабатывает единичный разрешающий сигнал, который устанавливает триггер ЭЛЕМЕНТА 5 в единичное состояние и,- таким .образом, разрешает прохождение импульсов с генератора 1 тактовых импульсов. через элемент И ЭЛЕМЕНТА 5 на вход, счетчика б. После восьми последующих тактов работы. устройства в целом на счетчике б хранится код числа 31, т.е. все триггеры счетчика б находятся в нулевом состоянии. Сигнал, формируеьый на выходе счетчика б, запрещает прохождение тактовых импульсов через ЭЛЕМЕНТ 5 и ЭЛЕМЕНТ 2. .()дновременно этим же сигналом блокируется прохождение информации на пер вый разряд регистра 3 сдвига через двухвходовый элемент И 7 и включается лампочка иьдикации блока 10.

В данный момент на резисторе сдвига

3 фиксируется двоичный код, равный

11001. На выходе сумматора по модулю два цепи обратной связи регистра 3 сдвига формируется значение первого коэффициента 01(9} = 1. После . того, как значение Ge (9) зафиксировано, содержимое регистра сдвига сдвигается на один разряд путем замыкания контакта генератора 9 одиночных импульсов, с выхода которого одиночный импульс через элемент ИЛИ 8 поступает на синхровходы регистра сдвига. В результате на регистре сдвига хранится код 01100 и соответственно на выходе сумматора по модулю два цепи обратной связи 6 .(9}0, После второго сдвига на регистре сдвига имеем код 00110 и на выходе сумматора по модулю два бз(9) = 1.

После третьего н четвертого сдвига на регистре имеем 00011 и 00001 и на выходе сумматора по модулю два соответственно(з4 (9) = 1 Gg (9} = 1

Таким образом, коэффициенты, определяющие тополргию связей многовходового сумматора по модулю два, на выходе которого получается сдвинутая на 9 тактов 1п-последовательность имеет следующий вид G1(9} = 1, 1023325 б

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

Редактор Н. Воловик Техред A.йч . Корректор д. Бокшан

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

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

113035) Иосква, Ж-35; Раушская наб., д. 4/5

Филиал ППЙ "Патент"., г. Ужгород, ул. Проектная, 4 (9) = Ор О (9) - 1, 6+ (9) = 1

4g (9) 1. На фиг. 3 приведена временная диаграмма последовательностей на выходе сумматора по модулю два, топология связей которого определяется коэффициентами 6 (9) и исходной ю -последовательности.

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

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

Предлагаемый генератор псевдослучайностей существенно окращает 15 аппаратурные затраты эа счет отсут- ствия элементов памяти. Так для

W = 20 необходимо было бы использовать 171 элемент памяти, что в семь раз больше, чем затраты обору дования, идущие на другие блоки устройства. Дополнительное оборудо- ванне составляет весьма незначительный объем. Длг любого m:он состоит из одного двухвходового элемента И, одного двухвходового элемента ИЛИ, одного одновходового элемента ИЯИ, одного одновходового элемента ИЛИНЕ, трех сопротивлений, емкости и лампочки индикации.

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