ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Полезная модель относится к вычислительной технике и может быть использована в цифровых вычислительных устройствах для формирования кодовых последовательностей.
Известны генераторы псевдослучайной последовательности (ПСП), например, в [1] на с.146, фиг.4.2.1. (генератор М-последовательностей), содержащий селектор двоичных импульсов, первый и второй регистры с обратными связями, формирователь синхроимпульсов и генератор тактовых импульсов.
1
1
1
Известен генератор псевдослучайных последовательностей, приведенный в книге [1] на с.147, фиг.4.2.3 (генератор М-последовательностей), выбранный в качестве прототипа, содержащий генератор тактовых импульсов, регистр сдвига с синхровходом, с последовательным входом и с выходом на n, разряд, n умножителей и сумматор по модулю два на n вход.
Устройство-прототип имеет следующие функциональные связи.
1
1
1
Выход генератора тактовых импульсов соединен с синхровходом регистра сдвига, а n разряд с выхода регистра сдвига через n умножителей соединены с n входами сумматора по модулю два, выход которого соединен с последовательным входом регистр сдвига и, кроме того, является выходом устройства.
1
Работает устройство-прототип следующим образом. С генератора тактовых импульсов импульсы поступают на синхровход регистра сдвига. Разряды выхода регистра сдвига, сигналы поступают на выход устройства, а также через n умножителей поступают на соответствующие входы сумматора по модулю два, с выхода которого сигнал поступает на последовательный вход регистра сдвига, а также на выход устройства.
n
Недостатком данного устройства является небольшая сетка периодов. Например, для 10-разрядного регистра можно сформировать 60 шт. М-последовательностей. Данное обстоятельство ограничивает функциональные возможности данного генератора псевдослучайных последовательностей, что обусловлено следующей особенностью. При фиксированной разрядности сдвигового регистра устройство позволяет формировать возможное количество различающихся М-последовательностей с периодом N=2-1 (под различающимися М-последовательностями понимаются последовательности, каждую из которых нельзя было бы представить в виде циклического сдвига любой другой), определяемые по формуле вида [2, с.33.]
,
1
1
n
где φ(N) - функция Эйлера. Например, при n=13, Q=60. Величина Q является сравнительно небольшой по отношению к возможному количеству 2-1 двоичных последовательностей, различие которых определяется обратными связями и-разрядного регистра сдвига. Существенные различия объясняются применением линейных операций (сложения по модулю два) в цепи обратной связи. Эти недостатки устранены в предлагаемом устройстве.
Техническим результатом предлагаемого устройства является расширение функциональных возможностей - увеличение объема формируемых максимальных последовательностей, путем подключения двух двоичных регистровых генераторов псевдослучайных последовательностей (ГПСП) с обратной связью (линейного генератора М-последовательности и нелинейного генератора с нелинейной обратной связью с максимальными взаимно простыми периодами) через функциональный цифровой преобразователь, формирующий систему классов вычетов по формуле
,
i
2
i
1
где х - двоичные n - разрядные числа, формируемые нелинейным ГПСП, у - двоичные n - разрядные числа, формируемые линейным генератором М-последовательности.
Нелинейный генератор описывается нелинейным рекуррентным уравнением вида [3, с.51-52.]
j
i
2
-
где q(t) - двоичный символ на выходе j-го разряда регистра сдвига на t-м такте, , с - двоичные константы, определяющие вид обратной связи,  - операция инверсии двоичного значения, вычисляемого схемой операции логического «И», ⊕ и  - операции поразрядного сложения по модулю два. Количество Q нелинейных последовательностей, формируемых нелинейным ГПСП при заданном n определяется по формуле [2, с.32-33]
2
2n-1-n
Q=2.
2
4083
Например, при n=13, Q=2.
1·
2
n
n
Предлагаемое устройство позволяет увеличить объем формируемых максимальных последовательностей до величины Q=QQ. При этом максимальный период получаемых последовательностей на выходе устройства равен величине 2·(2-1).
1
1
1
1
1
1
2
2
1
2
1
2
1
2
1
2
1
2
1
1
2
2
1
2
1
2
1
2
1
2
1
2
2
2
2
2
2
2
2
2
2
1
2
Технический результат в генераторе псевдослучайных последовательностей, содержащем генератор тактовых импульсов, n умножителей на два входа и выход каждый и сумматор по модулю два на n вход, достигается тем, что в него введены регистр сдвига с синхровходом, с последовательным входом, с параллельным входом на n разряд, входом асинхронной установки и с выходом на n разряд, параллельный регистр обратной связи генератора М-последовательности на n разряд с информационным входом, синхровходом и выходом на n разряд, нелинейный генератор с входом начального состояния на 2·n разрядов, входом инициализации, синхровходом и выходом на n разряда, параллельный (n+n)-разрядный регистр с информационным входом, синхровходом и выходом, (n+n) буферных элементов, каждый из которых имеет информационный вход, управляющий вход и выход, параллельный регистр коммутации с информационными входом на (n+n) разрядов, выходом на (n+n) разрядов и с синхровходом, причем синхровходы регистра сдвига, нелинейного генератора и параллельного (n+n)-поразрядного регистра соединены с генератором тактовых импульсов, k-й разряд выхода регистра сдвига соединен с первым входом k-го умножителя соответственно, k-й разряд выхода параллельного регистра обратной связи генератора М-последовательности соединен с вторым входом k-го умножителя соответственно, выход которого соединен с k-м входом сумматора по модулю два соответственно, , выход которого соединен с последовательным входом регистра сдвига, вход инициализации нелинейного генератора, вход асинхронной установки регистра сдвига, синхровход параллельного регистра обратной связи генератора М-последовательности и синхровход параллельного регистра коммутации соединены с входом инициализации генератора псевдослучайных последовательностей, параллельный вход регистра сдвига на n разряд и информационный вход параллельного регистра обратной связи генератора М-последовательности на n разряд соединены с первой группой разрядов входа начального состояния генератора псевдослучайных последовательностей (данная группа включает 2·n разрядов), вход начального состояния нелинейного генератора на 2·n разряда соединен с второй группой разрядов входа начального состояния генератора псевдослучайных последовательностей, информационный вход параллельного регистра коммутации на (n+n) разряда соединен с третьей группой разрядов входа начального состояния генератора псевдослучайных последовательностей (вход начального состояния генератора псевдослучайных последовательностей содержит 3·(n+n) двоичных разрядов), выходы нелинейного генератора и регистра сдвига соединены с младшими и старшими разрядами входа параллельного (n+n)-разрядного регистра соответственно, l-й разряд выхода параллельного (n+n)-разрядного регистра соединен с информационным входом l-го буферного элемента соответственно, управляющие входы которого соединены с l-м разрядом выхода параллельного регистра коммутации соответственно, , выходы (n+n) буферных элементов представляют собой разряды выхода генератора псевдослучайных последовательностей, нелинейный генератор содержит n мультиплексоров с двумя информационными входами, управляющим входом и выходом каждый, n одноразрядных регистра с информационным входом, синхровходом и выходом каждый, схему операции логического «И», имеющую n входов и выход с инверсией, схему операции логического «ИЛИ», имеющую два входа и выход, n буферных элемента с информационным входом, управляющим входом и выходом каждый, а также параллельный регистр обратной связи с n - разрядным информационным входом, n - разрядным выходом и с синхровходом, причем первый информационный вход первого мультиплексора соединен с выходом схемы операции логического «И», входы которой соединены с выходами n буферных элементов соответственно, при этом информационный вход i-го буферного элемента соединен с выходом i-го одноразрядного регистра соответственно, , управляющие входы каждого из n мультиплексоров соединены в входом инициализации генератора псевдослучайных последовательностей, а первый информационный вход j-го мультиплексора соединен с выходом (j-1)-гo одноразрядного регистра соответственно, , второй информационный вход i-го мультиплексора соединен с i-м разрядом первой подгруппы второй группы разрядов входа начального состояния генератора псевдослучайных последовательностей соответственно, , выход i-го мультиплексора соединен с входом i-го одноразрядного регистра соответственно, , синхровходы каждого из n одноразрядных регистров соединены с выходом схемы операции логического «ИЛИ», первый вход которой соединен с входом инициализации генератора псевдослучайных последовательностей, а второй ее вход является входом подключения к генератору тактовых импульсов, соответственно, каждый управляющий вход i-го буферного элемента соединен с i-м разрядом параллельного регистра обратной связи соответственно, , информационный вход которого соединен с второй подгруппой первой группы разрядов входа начального состояния генератора псевдослучайных последовательностей, а его синхровход соединен с входом инициализации генератора псевдослучайных последовательностей, каждый выход i-го одноразрядного регистра соединен с i-м разрядом выхода нелинейного генератора соответственно, , где n - количество двоичных разрядов чисел, снимаемых с выхода регистра сдвига, целое положительное число, n - количество двоичных разрядов чисел, снимаемых с выхода нелинейного генератора, целое положительное число, k, l, i, j - целые положительные числа.
Схема генератора псевдослучайных последовательностей в приведена на фиг.1, а схема блока нелинейного генератора - на фиг.2.
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
1
2
1
2
1
2
2
1
1
2
Генератор псевдослучайных последовательностей (фиг.1) содержит генератор 1 тактовых импульсов, умножители 2.k, , на два входа и выход каждый, сумматор 3 по модулю два на n вход, регистр 4 сдвига, параллельный регистр 5 обратной связи генератора М-последовательности, нелинейный генератор 6 с входом начального состояния на 2·n разряда, входом инициализации и синхровходом, параллельный (n+n)-разрядный регистр 7 с информационными входом на (n+n) разрядов, выходом на (n+n) разрядов и синхровходом, буферные элементы 8.l с информационным и управляющим входами, а также с выходом, , параллельный регистр 9 коммутации с (n+n)-разрядным информационным входом, с (n+n)-поразрядным выходом, а также с синхровходом; вход 10 является входом инициализации генератора псевдослучайных последовательностей и соединен с входом асинхронной установки регистра 4 сдвига, с синхровходом параллельного регистра 5 обратной связи генератора М-последовательности, с входом инициализации нелинейного генератора 6 М-последовательности, с синхровходом параллельного (n+n)-разрядного регистра 7 коммутации, и с управляющим входом для мультиплексоров 13.i (фиг.2), , вход 11 является входом начального состояния генератора псевдослучайных последовательностей, при этом первая подгруппа первой группы разрядов данного входа, содержащая n разряд, поступает на параллельный вход регистра 4 сдвига, вторая подгруппа первой группы разрядов данного входа, содержащая n разряд, поступает на информационный вход параллельного регистра 5 обратной связи генератора М-последовательности, вторая группа разрядов данного входа, содержащая 2·n разряда, является входом начального состояния нелинейного генератора 6, а третья группа разрядов данного входа, содержащая (n+n) разрядов, является информационным входом параллельного регистра 9 коммутации, выход 12 является (n+n)-разрядным выходом генератора псевдослучайных последовательностей. Причем группа из n разрядов, соединенная с выходом нелинейного генератора 6, является группой младших разрядов, а группа из n разрядов, соединенная с выходом регистра 4 сдвига, является группой старших разрядов, при этом данные две группы разрядов соединены с информационным входом параллельного (n+n)-разрядного регистра 7, i-и разряд с выхода которого поступает на информационный вход буферного элемента 8.i соответственно, , i-й разряд с выхода параллельного регистра 9 коммутации поступает на управляющий вход буферного элемента 8.i соответственно, , разряды, снимаемые с выходов буферных элементов 8.i, , являются разрядами выхода 12 генератора псевдослучайных последовательностей.
2
2
2
2
2
2
2
2
На фиг.2 представлен нелинейный генератор 6, который включает n мультиплексоров 13.i, , с двумя информационными входами, управляющим входом и выходом каждый, n одноразрядных регистра 14.i, , с информационным входом, синхровходом и выходом, схему 15 операции логического «И» на n входов и один выход с инверсией, схему 16 операции логического «ИЛИ» на два входа и один выход, n буферных элемента 17.i, , с информационным входом, управляющим входом и с выходом каждый, параллельный регистр 18 обратной связи, с n - разрядными входом, с n - разрядными выходом, а также с синхровходом; нелинейный генератор 1 имеет выход 20 на n разряда, причем первый информационный вход мультиплексора 13.1 соединен с выходом схемы 15 операции логического «И», входы которой соединены с выходами буферных элементов 17.i, , при этом информационный вход каждого буферного элемента 17.i соединен с выходом одноразрядного регистра 14.i соответственно, , а управляющий вход каждого буферного элемента 17.i - с i-ми разрядами параллельного регистра 18 обратной связи соответственно, . Управляющие входы каждого из n мультиплексоров 13.i, , соединены с входом 10 инициализации генератора псевдослучайных последовательностей, а первый вход мультиплексора 13.j соединен с выходом одноразрядного регистра 14.(j-1), , соответственно. Второй вход каждого мультиплексора 13.i соединен с i-м разрядом первой подгруппы второй группы 11.2. разрядов входа 11 начального состояния генератора псевдослучайных последовательностей соответственно, . Информационный вход параллельного регистра 18 обратной связи соединен со второй подгруппой второй группы 11.2. разрядов входа 11 начального состояния генератора псевдослучайных последовательностей, а синхровход параллельного регистра 18 обратной связи - с входом 10 инициализации генератора псевдослучайных последовательностей. Выход каждого мультиплексора 13.i соединен с входом информационным входом одноразрядного регистра 14.i соответственно, . Синхровходы одноразрядных регистров 14.i, , соединены с выходом схемы 16 операции логического «ИЛИ», первый вход которой соединен с входом 10 инициализации генератора псевдослучайных последовательностей, а второй ее вход является входом 19 подключения к генератору тактовых импульсов, соответственно. Выход каждого одноразрядного регистра 14.i соединен с i-м разрядом выхода 20 нелинейного генератора 6 соответственно, .
Все блоки, приведенные на фиг.1 и фиг.2, имеют стандартную и опубликованную в литературе реализацию, а также имеют входы электропитания, которые не изображены на фиг.1 и фиг.2.
1
1
1
1
2
2
1
2
1
2
1
2
1
2
1
2
Рассмотрим генератор псевдослучайных последовательностей в работе. В предлагаемом генераторе вычисление элементов псевдослучайных последовательностей производится на основе двух генераторов псевдослучайных последовательностей, один из которых, генератор М-последовательности, является линейным, а другой - нелинейным. По сравнению с прототипом ([1] на с.147, фиг.4.2.3,), в устройство введены: регистр 4 сдвига с синхровходом, с последовательным входом, с параллельным входом n разряд, входом асинхронной установки и с выходом на n разряд, параллельный регистр 5 обратной связи генератора М-последовательности на n разряд с информационным входом, синхровходом и выходом на n разряд, нелинейный генератор 6 с входом начального состояния на 2·n разрядов, входом инициализации, синхровходом и выходом на n разряда, параллельный (n+n)-разрядный регистр 7 с информационным входом, синхровходом и выходом, (n+n) буферных элементов 8.1,…,8.(n+n), каждый из которых имеет информационный вход, управляющий вход и выход, параллельный регистр 9 коммутации с информационными входом на (n+n) разрядов, выходом на (n+n) разрядов и с синхровходом.
Сущность полезной модели в том, что предлагаемый генератор реализует процедуру последовательного вычисления элементов псевдослучайных последовательностей согласно формуле
i
1
1
i
2
1
2
1
2
i
i
2
1
2
1
2
где x - элементы периодической последовательности с периодом m образующие полную систему наименьших неотрицательных вычетов по модулю m [4, с.86], у - элементы периодической последовательности с периодом, равным m, где m и m - натуральные числа, m>2, m>2. При фиксированном x, при использовании элементов у по формуле (2) формируется класс вычетов мощностью m. При условии, что m и m - взаимно простые, последовательность, образованная согласно (2), имеет период, равный произведению m·m.
При этом блок нелинейного генератора позволяет получить периодическую последовательность согласно формуле вида (1)
Технический результат выражен в увеличении объема формируемых максимальных последовательностей путем применения нелинейного генератора, объединенного с генератором М-последовательности через функциональный цифровой преобразователь на основе параллельного регистра.
1
2
i
i
i
i
1
2
i
i
1
2
Значения элементов псевдослучайных периодических последовательностей, n - и n - разрядные числа х и у соответственно, формируемые по синхросигналу, подаваемому с генератора 1 тактовых импульсов на синхровход регистра 4 сдвига и синхровход нелинейного генератора 6, поступают с выходов регистра 4 сдвига (старшие разряды, у) и нелинейного генератора 6 (младшие разряды, х) на вход параллельного (n+n)-разрядного регистра 7. По синхросигналу, поступающему с генератора 1 тактовых импульсов, значения х и у заносятся в параллельный (n+n)-разрядный регистр 7.
При этом каждый i-й разряд, снимаемый с выхода регистра 7, поступает на информационный вход буферного элемента 8.i соответственно, , буферный элемент 8.i коммутируется путем подачи на его управляющий вход i-го разряда параллельного регистра 9 коммутации соответственно, , выход буферного элемента 8.i является i-м разрядом выхода 12 генератора псевдослучайных последовательностей соответственно, .
При подаче напряжения питания происходит инициализация генератора псевдослучайных последовательностей.
i
На этапе инициализации на вход асинхронной установки регистра 4 сдвига, на синхровход параллельного регистра 5 обратной связи генератора М-последовательности, на вход инициализации нелинейного генератора 6 и на синхровход параллельного регистра 9 коммутации с входа 10 инициализации генератора псевдослучайных последовательностей поступает сигнал (значение логической «1»), согласно которому в регистр сдвига заносится информация, поступающая с первой подгруппы первой группы разрядов входа 11 начального состояния генератора псевдослучайных последовательностей, в параллельный регистр 5 обратной связи генератора М-последовательности - информация со второй подгруппы первой группы разрядов входа 11, в нелинейный генератор 6 - информация со второй группы разрядов входа 11, а в параллельный регистр 9 коммутации - информация с третьей группы разрядов входа 11. На управляющий вход каждого мультиплексора 13.i поступает значение логической «1» с входа 10, тем самым обеспечивая прохождение на выход каждого мультиплексора 13.i значения, поступающего на его второй вход с i-го разряда первой подгруппы второй группы 11.2 разрядов входа 11 соответственно, . Значение логической «1» с входа 10 поступает также на один из входов схемы 16 операции логического «ИЛИ», а, затем, через схему 16, поступает на синхровходы каждого из одноразрядных регистров 14.i соответственно, , тем самым обеспечивая сохранение значений с выхода каждого мультиплексора 13.i в одноразрядном регистре 14.i соответственно, . Генерирование псевдослучайной последовательности нелинейным ГПСП с заданными свойствами согласно (1) осуществляется путем приведения соответствующих буферных элементов 15.i в открытое либо закрытое состояние в соответствии со значениями величин с - двоичных констант, определяющих вид обратной связи и поступающими на управляющий вход соответствующего буферного элемента 15.i с i-го разряда параллельного регистра 18 обратной связи, .
1
2
1
2
i
i
На этапе функционирования, с генератора 1 тактовых импульсов поступает синхросигнал на синхровход регистра 4 сдвига, на синхровход нелинейного генератора 6 и на синхровход параллельного (n+n)-разрядного регистра 7. В данной связи, в регистре 4 сдвига производится логический сдвиг двоичных значений его разрядов, а значение, формируемое на его последовательном входе при использовании сумматора 3 по модулю два, заносится в младший разряд регистра 4 сдвига, в нелинейном генераторе 6 (фиг.2) синхросигнал с генератора 1 тактовых импульсов поступает, через схему 16 операции логического «ИЛИ», на синхровходы каждого из одноразрядных регистров 14.i, , а также в параллельный (n+n)-разрядный регистр 7 заносятся значения х (младшие разряды) и у (старшие разряды), снимаемые с выходов нелинейного генератора 6 и регистра 4 сдвига, соответственно. В соответствии с информацией, записанной в i-й разряд параллельного регистра 9 коммутации, который соединен с управляющим входом буферного элемента 8.i, значение с выхода i-го разряда регистра 7 поступает на информационный вход буферного элемента 8.i, а, затем, проходит (или не проходит) с выход/буферного элемента 8.i как i-й разряд выхода 12 генератора псевдослучайных последовательностей, . На управляющий вход мультиплексора 13.i, поступает значение логического «0» с входа 10, тем самым обеспечивая прохождение сигналов с первого информационного входа мультиплексора 13.i, , на его выход. Значение с выхода мультиплексора 13.i поступает на вход одноразрядного регистра 14.i, , и заносится в него по синхросигналу, поступающему с генератора 1 тактовых импульсов (через вход подключения 19 к генератору 1) на вход схемы 16, а, затем, с выхода схемы 16, на синхровходы каждого из одноразрядных регистров 14.i, . Значения с выхода каждого одноразрядного регистра 14.i, поступают на информационные входы буферных элементов 17.i соответственно, . В случае, если в i-м разряде параллельного регистра 18 обратной связи записана логическая «1», то она будет подана на управляющий вход буферного элемента 17.i и значение, поступившее на информационный вход буферного элемента 17.i поступает на i-й вход схемы 15, , а в случае, когда i-м разряде регистра 18 записан логический «0», то на i-й вход схемы 15 поступает логический «0», , тем самым обеспечивая запрет на прохождение информации, поступившей на информационный вход буферного элемента 17.i. Значение, снимаемое с выхода схемы 15, поступает на первый информационный вход мультиплексора 13.1, а на первый информационный вход каждого мультиплексора 13.i поступает значение, снимаемое с выхода одноразрядного регистра 14.(i-1) соответственно, . На i-й разряд выхода 20 нелинейного генератора поступают значения, снимаемые с выхода одноразрядного регистра 14.i соответственно, , вычисляемые согласно (1),.
1. Шумоподобные сигналы в системах передачи информации/В.Б.Пестряков, В.П.Афанасьев, В.Л.Гурвич и др. М.: Сов. радио, 1973. 424 с.
2. Свердлик М.Б. Оптимальные системы и сигналы. М.: Сов. радио, 1975. 200 с.
3. Иванов М.А. Чугунков И.В. Теория применения и оценка качества генераторов псевдослучайных последовательностей. М.: «КУДИЦ-ОБРАЗ». 2003. 240 с.
4. Бухштаб А.А. Теория чисел. М.: Просвещение, 1966. 384 с.