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

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

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

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

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

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

Двоичные кодовые комбинации N и К-1 подаются соответственно на информационные входы коммутаторов 9 и 15. Двоичный, код числа N определяет кодовое расстояние между разрядами эквива лентного регистра сдвига, подключаемыми к входам сумматора 13 по модулю два 13, выполняющего функции логической обратной связи. Двоичный код числ К соответствует общему количеству разрядов эквивалентного регистра сдвига и определяет ма чсимально возможную длину генерируемой последовательности при выбранной разрядности. Очевидно, что при подаче управляющих сигналов необходимо, чтобы соблюдалось NiK-1. Управляющая кодовая комбинация K-l подается на первые входы схем 6 и 7 сравнения. Схемы о и 7 сравнения формируют на своих выходах сигнал L-ак- тивного уровня при условии, если значение двоичных кодовых комбинаций, поступающих на вторые входы, превосходит по величине кодовый сигнал К-1.

В этих условиях схема 6 сравнения обе спечивает подачу на вход сброса счет- сигнала логического нуля в том случае, когда содержимое счетчика превысит К--1, чем достигается управление коэффициентом пересчета счетчика 8 в диапазоне 1-2 (т - разрядность счетчика 8), который в процессе работы проходит К состояний (0,1,2.. ...К-1).

0

5 0

5

Q .Q 45

5

,

50

55

В процессе раПогы гсисратор-т сигнал i -f с выхода генератора тактовых импупьсив 1 поступает на вход триг - герд 2. и входы элеме -1топ И-НЕ 3 - И -;. На поямом и инверсном р,(,1ходлх триггера 2 формируются сигиллы типа меандр, не совпадающие во времени. Каждый импульс частоты fт/ ня прямом выходе триггера 2 взаимодействует своим положительнь1м фронтом на вход синхронизации счетчика 8, увеличивает на единим.у код М H-I его выходе. Тот же сигнал Q с прямого выхода генератора 2 поступает на управляющий вход коммутатора 9. При О - 1 коммутатором 9 обеспечивается подача на вторые входы сумматора 10 сигнала логического нуля. Поскольку содержимое М счетчича 8 че может превзойти К-1 (М К-1), иначе 9 будет обнулен С1-1гнало -1 с выхода схемы 6 сравнения, на зыходе схемы 7 сравнения сохраняется сигнал 11-актианого уровня, который, поступая на управляющий вход коммутатора 15, обеспечивает подачу -.з вторые входы сумматора 1 1 сигналов логического нуля. Таким образом, в течение первого цикла работы триггера 2 на выходе сумматора 11, подключенного к адресному входу блока 12 памяти, формируется двоичная комбинация М, равная текущему значению содержимого счетчика 8.

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

Следующий импульс с выхода генератора 1 опрокидывает триггер 2, при этом на втором входе элемента И Ц формируется положительный импульс, а на управляющий вход коммутатора 9 поступает сигнал Q 0. В результате коммутатор 9 обеспечивает подачу на второй вход сумматора 10 двоичной кодовой комбинации N. Двоичный сигнал, равный по величине сумме М+л (в случае , m - число разрядов сумматоров 10, 11, счетчика 8, шины адреса блока 12 памяти и коммутаторов 9, 15) или остатку (N+M) (в

случае M+N , 2) , поступает на первый вход сумматора 11.

Дальнейшая работа узлов генератора зависит от соотношения величин чисел на входах схемы 7 сравнения, примем следует рассмотреть два основных случая. При условии, что значение сигнала на первом входе схемы 7 сравнения не превосходит значение К-1, на управляющем входе коммутатора 15 сохраняется сигнал Н-активно- го уровня, в результате чего на вторые входы сумматора 11 постоянно поступают сигналы логического нуля и адрес опрашиваемой ячейки блока 12 памяти определяется величиной сигнало на выходе сумматора 10, Следовательно, на адресных входах блока 12 памяти формируется код Л, равный результату суммирования M-t-N и определяющий адрес новой опрашиваемой ячейки. Благодаря наличию сигнала И-активно- го уровня на входе чтение - запись блока 12 памяти последний продолжает .функционировать в режиме чтения информации и на информационный вход триггера 17 поступает содержимое ячейки с адресом M+N. Элемент 14 задержки обеспечивает задержку подачи импульса записи на вход синхронизации триггера 17 на время Т, превосходящее суммарное время переключения первого 10 и второго 11 сумматоров и выборки из блока 12 памяти, по истечении которого сигнал с выхода блока 12 памяти запоминается триггером 17. На выходе сумматора 13 по модулю два формируется двоичное число, определяемое содержимым триггеров 1б и 17. Соответственно, по окончании импульса V2 на выходе элемента ИЛИ 5 формируется сигнал логического нуля; блок 12 памяти переводится в режим записи информации и происходит запись числа с выхода сумматора 13 по модулю доз в ячейку памяти с номером А, равным сумме 11 -- N.

Однако, поскольку К может быть представлено произвольным целым чис- лом в диапазоне - 2 , в случае К ч 2 содержимое счетчика 8, проходящего в процессе работы генератора последовательно К своих состояний,- принимает такое значение Н, что 1ч + + N7 К - 1. При этом, для сохранения кодового расстояния между разрядами эквивалентного регистра, формирующих сигналы обратной связи, необходимо.

0

0

чтобы сохранялось обращение к ячейкам блока оперативной памяти, расположенных в поле адресов О - К-1. Так, при М + N К обращение должно производится к ячейке с адресом А О, при M+N K+1-c адресом А 1, и так далее, до тех пор пока не произойдет переполнение разрядной сетки сумматоров.

В рассматриваемом случае (М -- N Ж - 1) на выходе схемы 7 сравнения формируется сигнал L-активного уровня, обеспечивающий подключение к вто5 рому входу сумматора 11 двоичной кодовой комбинации К-1, равной по величине инверсному значению управляющего кода К - 1. В результате адрес А ячейки блока 12 памяти опрашивают

0 в течение второго цикла (Q 1) работы триггера 2, что определяется результатом суммирования М + N + t- (К - 1). Представив сумму М + N для данного случая в виде М + N (К - 1)+

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

М + N + (К - 1) 2 -I- (В - 1) , а сигнал А на выходах сумматора 11,

0 определяющий адрес ограничиваемой ячейки блока 12 памяти составит А (В - 1), т.е. при М + N К(В-1) А О, при М + N К + 1 (В 2) А 1 и так далее. Запись сигналов с

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

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

0

помощью 2 вариантов эквивалентных регистров сдвига длиной К (К 1-2). При этом, с учетом симметрии свойств псевдослучаной последовательности. при подключении N-ro или ,K-N-ro разрядов генерирующего регистра к входу сумматора по модулю два число Рц ре-, гулироаок в каждом варианте составляет два четных К F

ных К Р

н.ч

int(|) -tК/2, 1, а

возможных вариантов Р эквивалентного регистра сдвига с подключением различных разрядов K-N в цепь обратной связи равно

т

И после преобразований окончательно

записывается в виде Р . (2 -Формула

-н 1). изобретения

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

0

5

о Q 5

5

вход которого соединен с выходом первого триггера и

ИЛИ, инверсньн соединен с И, выход ВТО- выходом генеля ющи и прямым

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

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