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

 

Изобретение относится к вычислительной технике и может быть использовано для решения вероятности задач. Цель изобретения - расширение функциональных возможностей за счет формирования псевдослучайной последовательности чисел заданной длины. Генератор 1 тактовых импульсов, триггер 2, элемент И-НЕ 3, элемент И 4, элемент ИЛИ 5, схему 6 сравнения, схему 7 сравнения, счетчик 8, коммутатор 9, сумматор 10, сумматор 11, блок 12 памяти, сумматор по модулю два 13, элемент 14 задержки, коммутатор 15, триггер 16 и триггер 17. Цель достигается за счет введения новых блоков и функциональных связей. 2 ил.

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

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

РЕСПУБЛИК (я) 4 G 06 F 7/58

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

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4307706/24-24 (22) 18.09.87 (46) 15. 12. 89. Бюл. N 46 (71) Вологодский политехнический институт (72) А.Н Андреев, А.Н.Водовозов, Т.В.Воробьева и В.Н.Лабичев .(53) 681 ° 3 (088.8) (56) Авторское свидетельство СССР

524175, кл. G 06 F 7/58, 1975.

Авторское свидетельство СССР 1 959076, кл. С 06 1 7/58, 1982.

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

N 1013954, кл. G 06 F 7/58, 1983. (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАйНОй ПОСЛЕДОВАТЕЛЬНОСТИ (57) Изобретение относится к вычислиÄÄSUÄÄ 1528770 А1

; ельной технике и может быть использовано для решения вероятности задач.

Цель изобретения - расширение функциональных возможностей за счет формирования псевдослучайной последовательности чисел заданной длины. Генератор содержит генератор 1 тактовых импульсов, триггер 2, элемент И-НЕ 3, элемент И 4, элемент ИЛИ 5, схему 6 сравнения, схему 7 сравнения, счетчик 8, коммутатор 9, сумматор 10, сумматор 11, блок 12 памяти, сумматор 13 по модулю два, элемент 14 задержки, коммутатор 15, триггер 16 и триггер 17. Цель достигается за счет введения новых блоков и функциональф ных связей. 1 ил.

1528770

Изобретение относится к вычислительной технике и может быть использовано для решения вероятностных задач.

5>

Цель изобретения — ра сширение функциональных возможностей генератора за счет формирования псевдослучайной последовательности заданной длины. 10

На ч-ртеже приведена структурная схема генератора.

Генератор содержит генератор 1 тактовых импульсов, триггер 2, элемент 3 И-НЕ, элеме.<т 4 И, элемент

5 ИЛИ, хемы 6 и 7 сравнения, счетчик

3, коммутатор 9, сумматоры 10 и 11, блок 12 памяти, сумматор 13 по модулю два, элемент 14 задержки, коммутатор 15, триггеры 16 и 17, 18 — выход устройства, 19 и 20 входы устройства.

Генератор псевдослучайностей последовательности работает следующим образом.

Двоичные кодовые комбинации N u

К- 1 подаются соответственно на информационные входы коммутаторов 9 и 15.

Двоичный, код числа N определяет кодовое расстояние между разрядами эквива- 0 лентного регистра сдвига, подключаемыми к входам сумматора 13 по модулю два 13, выполняющего функции логической обратной связи. Двоичный код числа

К соответствует общему количеству раз35 рядов эквивалентного регистра сдвига и определяет максимально возможную длину генерируемой последовательности при выбранной разрядности. Очевидно, что при подаче управляющих сигналов необходимо, чтобы соблюдалось N -< K- 1.

Управляющая кодовая комбинация K-1 подается на первые входы схем 6 и 7 сравнения. Схемы 6 и 7 сравнения формируют на своих выходах сигнал L c3K д5 тивного уровня при условии, ес.<и значение двоичных кодовых комбинаций, поступающих на вторые входы, превосходит по величине кодовый сигнал К-1.

В =-тих условиях схема 6 сравнения обе50 спечивает подачу на вход сброса счетчика 8 сигнала логического нуля в том случае, когда содержимое счетчика превысит К-1, чем достигается управление коэффициентом пересчета счетчика 8 в диапазоне 1-2 (m — разряд55 ность счетчика 8), который в процессе работы проходит К состояний (0,1,2... ...К-1) . р процессе раГ>огы ген<.ратора сигнал „, с выхода генератора т.-<кт<>вь<>< импупьс<>в 1 поступает на вход тр.>;— гера ? и входы эле«е.-то И-НЕ 3

И -" . На пг я ом и инверсном яых >дах триггера 2 формируются сигналы т «>а меандр, не совпадающие во вре,ени, Каждый импульс частоты f т,> на прямом выходе триггера ? взаимодействует своим положиTåëьным фронтом на вход синхронизации счетчика 8, увеличивает н» едини»у код М н его выходе.

Тот же сигнал <) с прямого выхода генератора 2 поступает на управляющий вход коммутатора 9. При

К-1 (М К вЂ” 1), иначе. 9 будет обнулен сигнало > ",. выхода схемы 6 сравнения, на выходе схемы 7 сравнения сохраня— еlся сигнал Н-активного уровня, который, поступая на управляюций вход комму-атора 15, обеспе <ивает подачу на вторые входы сумматора 11 сигналов логического нуля. Таким образом, в течение первого цикла работы триг— гера 2 на выходе сумматора 11, подключенного к адресному входу блока

12 памяти, формируется двоичная комбинация М, равная текущему значению содержимого счетчика 2.

По окончанию положительного потенциала импульса, длительность которого превосходит суммарное время переключения счетчика 8, сумматоров

1О и 11, а также выборки содержимого ячейки с адресом A-М блока 12 памяти, на входе синхронизации триггера 16 формируется положительный импульс, обеспечивающий запись в триггер

16 содержимого ограничиваемой ячейки бпока 12 памяти.

Следующий импульс с выхода генератора 1 опрокидывает триггер 2, при этом на втором входе элемента И 4 формируется положительный импульс, а на управляющий вход коммутатора 9 поступает сигнал Я = О. В результате коммутатор 9 обеспечивает подачу на второй вход сумматора 10 двоичной

><одовой комбинации N Двоичный сигнал, равный по величине сумме !+" (в случае M+N < 2, m — число разрядов сумматоров 10, 11, счетчика 8, шины адреса блока 12 памяти и коммутаторов 9, 15) или остатку 2 -(И+М) (в

1528770 случае .:1+N;- 2 "), поступает на первый вход сумматора 11.

Дальнейшая работа узлов генератора зависит от соотношения величин чисел на входах схемы 7 сравнения, причем следует рассмотреть два основных случая. При условии, что значение сигнала на первом входе схемы

7 сравнения не превосходит значение

K — 1, на управляющем входе коммутатора 15 сохраняется сигнал Н-активного уровня, в результате чего на вторые входы сумматора 11 постоянно поступают сигналы логического нуля и адрес опрашиваемой ячейки блока 12 памяти определяется величиной сигналов на выходе сумматора 10. Следовательно, на адресных входах блока 12 памяти формируется код Л, равный результату суммирования Г1+Г! и определяющий адрес новой опрашиваемой ячейки.

Благодаря наличию сигнала Н-активного уровня на вход чтение — запись блока 12 памяти последний продолжает .функционировать в режиме чтения информации и на информационный вход триггера 17 поступает содержимое ячейки с адресом M+N. Элемент 14 задержки обеспечивает задержку подачи импульса записи на вход синхронизации триггера 17 на время " ., превосходящее суммарное время переключения первого 10 и второго 11 сумматоров и выборки иэ блока 12 памяти, по истечении которого сигнал с выхода блока 12 памяти запоминается триггером 17. На выходе сумматора 13 по модулю "два" формируется двоичное число, определяемое содержимым триггеров 16 и 17, Соответственно, по окончании импульса Ч2 на выходе элемента ИЛИ 5 формируется сигнал логического нуля; блок 12 памяти переводится в режим записи информации и происходит запись числа с выхода сумматора 13 по модулю

"два" в ячейку памяти с номером А, равным сумме M +

Однако, поскольку K может быть представлено произвольным целым числом в диапазоне — 2 в случае

K С 2 содержимое счетчика 8, проходящего в процессе работы генератора последовательно K своих состояний, принимает такое значс.ние М, что 1i +

+ N 7 K — 1. При этом, для сохранения кодового расстояния между разрядами эквивалентного регистра, формирующих сигналы обратной связи, необходимо, 10 !

55 чтобы сохранялось обращение к ячейкам блока оперативной памяти, расположенных в поле адресов 0 — К- i. Так, при

М + Г = К обращение должно производится к ячейке с адресом А = "О", при M + N = К + 1 — с адресом А 1, и так далее, до тех пор пока не произойдет переполнение разрядной сетки сумматоров.

В рассматриваемом случае (M + N )

;К вЂ” 1) на выходе схемы 7 сравнения формируется сигнал L-активного уровня, обеспечивающий подключение к второму входу сумматора 1! двоичной кодовой комбинации К вЂ” 1, равной по величине инверсному значению управляющего кода К вЂ” 1. В результате адрес

A ячейки блока 12 памяти опрашивают в течение второго цикла ((1 = 1) работы триггера 2, что определяется результатом суммирования М + N +

+ (К вЂ” 1) . Представив сумму М+ N для данного случая в виде М + N = (К вЂ” 1)+

+ В, где В = 1, 2,..., нетрудно убедиться, что результат суммирования составит

M + N + (К вЂ” 1) = 2 + ( — 1), а сигнал А на выходах сумматора 11, определяющий адрес ограничиваемой ячейки блока 12 памяти составит А = ( — 1), т.е. при Г1 + N К(В1)

А = О, при Г1 + Г! = К + 1 (В = 2) А =

1 и так далее. Запись сигналов с выхода блока 12 памяти триггером 17, формирование сигнала обратной связи сумматором 13 по модулю два и запись результата в ячейку с адресом А происходит аналогично описанному выше случаю (М + N < К вЂ” 1) .

Таким образом, работа, выполняемая блоком 12 памяти, аналогична работе

К-разрядного регистра сдвига, охваченного обратной связью через сумматор по модулю два, подключеннный своими входами к последнему (К-му) и

К вЂ” N-му разрядам регистра . При этом эа счет изменения регулирующей кодовой комбинации K-1 может быть изменена общая длина К эквивалентного регистра сдвига, а с помощью регулирования комбинации N номер разряда, к которому подключен сумматор по модулю два. Следовательно, при общей разрядности m счетчика 8, коммутаторов 9, 15, блоков сравнения и шины адреса блока 12 памяти предлагаемый генератор позволяет формировать на своем выходе

18 последовательности, получаемые с

1528770

P - P к

Составитель И.Столяров

Техред Л.Олийнык Корректор В.Кабаций

Редактор Н.Киштулинец

За ка з 7613/22 Тираж 668 Подписное

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

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

Производственно-издательский комбинат "Патент, г. Ужгород, ул.Гагарина,111 помощью 2 вариантов эквивалентных регистров сдвига длиной К (К = 1-2 ).

При этом, с учетом симметрии свойств псевдослучаной последовательности.

5 при подключении И-го или,К-N-ro разрядов генерирующего регистра к входу сумматора по модулю два число PÄ регулировок в каждом варианте составляет два четных К P „ К/2, для нечетК ных К P int(-) + 1, а общее число й.и 2 возможных вариантов P эквивалентного регистра сдвига с подключением различных разрядов К-N в цепь обратной связи равно и после преобразований окончательно 2р записывается в виде

P 2 (2 + 1).

Формула изобретения

Генератор псевдослучайной последовательности, содержащий генератор тактовых импульсов, выход которого соединен с входом синхронизации первого триггера и первым входом элемента И, выход которого соединен с первым входом элемента ИЛИ, выход которого соединен с входом чтения записи блока памяти, выход которого соединен с информационными входами ,второго и третьего триггеров, выходы

iêîòîðûõ соединены соответственно с первым и вторым входами сумматора по модулю два, выход которого соединен с информационным входом блока памя- 40 ти, первый сумматор, первый коммутатор и счетчик, выход которого соединен с первым входом первого сумматора, .второй вход которого соединен с выходом первого коммутатора, управ.ляющий вход которого соединен с прямым выходом первого триггера и вторым входом элемента ИЛИ, инверснь, выход первого триггера соединен с вторым входом элемента И, выход второго триггера является выходом генератора, информационный вход первого коммутатора является входом задания кодового расстояния псевдослучайной последовательности генератора задания кодового расстояния, о т л и ч а ю— шийся тем, что, с целью расширения функциональных воэможностей эа счет формирования псевдослучайной последовательности заданной длины, а него введены две схемы сравнения, второй сумматор, элемент И-НЕ, элемент задержки и второй коммутатор, информационный вход которого являет— ся входом задания максимальной длины псевдослучайной последовательности генератора и соединен с первыми входами первой и второй схем сравнения, выход первого сумматора соединен с вторым входом первой схемы сравнения и первым входом второго сумматора, выход которого соединен с адресным входом блока памяти, второй вход второго сумматора соединен с инверсным выходом второго коммутатора, управляющий вход которого соединен с выходом первой схемы сравнения, выход второй схемы сравнения соединен с входом "Сброс" счетчика, вход синхронизации которого соединен с прямым выходом первого триггера и первым входом элемента И-НЕ, второй вход которого соединен с выходом генератора тактовых импульсов, выход элемента

И-HE соединен с входом синхронизации второго триггера, выход элемента И через элемент задержки соединен с входом синхронизации третьего триггера.