ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ (ВАРИАНТЫ) Российский патент 2001 года по МПК G06F7/58 

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

Известно устройство, генерирующее псевдослучайную последовательность [1] . Генератор псевдослучайной последовательности (ПСП) содержит регистр сдвига, дешифратор, мультиплексор, счетчик импульсов, D-триггер, генератор тактовых импульсов, три элемента ЗАПРЕТ, коммутатор и блок сумматоров по модулю два. Выход генератора тактовых импульсов одновременно подключен к прямому входу первого элемента ЗАПРЕТ, синхровходу D-триггера и входу счетчика импульсов. Выход первого элемента ЗАПРЕТ подключен к входу регистра сдвига, информационный выход которого подключен к прямому входу второго элемента ЗАПРЕТ. Соответствующие выходы регистра сдвига одновременно подключены к n-входам дешифратора и через коммутатор - к входам блока сумматоров по модулю два. Выходы дешифратора подключены к соответствующим входам мультиплексора, на V-входы которого подключены n-выходов счетчика импульсов. Выходы мультиплексора подключены к прямому входу третьего элемента ЗАПРЕТ. На инверсный вход которого подключен выход D-триггера. Выход третьего элемента ЗАПРЕТ одновременно подключен к D-входу D-триггера и инверсному входу первого элемента ЗАПРЕТ. Выход второго элемента ЗАПРЕТ является выходом генератора, а выход D-триггера подключен к инверсному входу второго элемента ЗАПРЕТ.

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

Наиболее близким к предлагаемым вариантам заявленных устройств по технической сущности является известный генератор n-значной псевдослучайной последовательности [2] , содержащий n элементов И, блок управления, снабженный n выходами, первые входы которых соединены с соответствующими выходами блока управления, n сумматоров по модулю два и n регистров сдвига, причем выходы j-го (где и i-го разрядов первого регистра сдвига подключены соответственно к первому и второму входам первого сумматора по модулю два, выход k-го и (i+1)-го (где разрядов 1-го регистра сдвига подключены соответственно к первому и второму входам 1-го сумматора по модулю два, выход первого сумматора по модулю два соединен с информационным входом одноименного регистра сдвига и с одноименным выходом блока управления, выход каждого регистра сдвига подключен к второму входу одноименного элемента И, выходы элементов И являются выходами генератора.

Однако данный генератор имеет недостатки.

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

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

Поставленная цель в первом варианте достигается тем, что в генератор псевдослучайной последовательности, содержащий n элементов И, где n=2,3,..., n сумматоров по модулю два, n регистров сдвига, а выход i-го сумматора по модулю два, где соединен с информационным входом i-го регистра сдвига, тактовый вход которого соединен с вторым входом i-го элемента И, выход i-го регистра сдвига подключен к первому входу i-го элемента И, дополнительно введены генератор импульсов, формирователь сетки частот, генератор ключевой последовательности, регистр и узел свертки. Выходы j-го, где а m=2,3,..., и m-го разрядов первого регистра сдвига подключены соответственно к первому и второму входу первого сумматора по модулю два. Выход k-го и (m+l)-го, где разрядов 1-го регистра сдвига, где подключен соответственно к первому и второму входам 1-го сумматора по модулю два. Первый выход формирователя сетки частот подключен к тактовому входу первого регистра сдвига, а l-выход подключен к тактовому входу 1-го регистра сдвига, n-й выход формирователя сетки частот подключен к входу генератора ключевой последовательности. Выход генератора ключевой последовательности подключен к входу регистра. К третьим входам n элементов И подключены выходы n-ячеек регистра. Выходы n элементов Т подключены к n-входам узла свертки. Выход генератора импульсов подключен к входу формирователя сетки частот. Выход узла свертки является выходом генератора псевдослучайной последовательности.

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

Поставленная цель во втором варианте достигается тем, что в генератор псевдослучайной последовательности, содержащий n элементов И, где n=2,3,..., n сумматоров по модулю два, n регистров сдвига, а выход i-го сумматора по модулю два, где соединен с информационным входом i-го регистра сдвига, тактовый вход которого соединен с вторым входом i-го элемента И, выход i-го регистра сдвига подключен к первому входу i-го элемента И, дополнительно введены генератор импульсов, формирователь сетки частот, блок выбора ключа, узел свертки. Выходы j-го, где а m=2,3,... и m-го разрядов i-го регистра сдвига подключены к первому и второму входу i-го сумматора по модулю два. В формирователе сетки частот i-й выход подключен к тактовому входу i-го регистра сдвига, к третьим входам n элементов И подключены n-выходов блока выбора ключа. Выходы n элементов И подключены к n-входам узла свертки. Выход генератора импульсов подключен к входу формирователя сетки частот. Выход узла свертки является выходом генератора псевдослучайной последовательности.

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

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

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

Заявляемый генератор псевдослучайной последовательности поясняется чертежами, на которых:
на фиг. 1 представлена схема заявляемого генератора по первому варианту;
на фиг. 2 - схема заявляемого генератора по второму варианту;
на фиг. 3 - схема формирователя сетки частот по первому и второму вариантам;
на фиг. 4 - временные диаграммы, поясняющие принцип формирователя сетки частот;
на фиг. 5 - схема блока выбора ключа по второму варианту.

Заявляемое устройство по первому варианту содержит (фиг. 1): генератор импульсов (ГИ) 1, сумматоры по модулю два 2.1-2.n; регистры сдвига (РС) 2.1-3. n; элементы И 4.1-4.n; формирователь сетки частот (ФСЧ) 5; генератор ключевой последовательности (ГКП) 6; регистр 7; узел свертки (УС) 8; выход генератора псевдослучайной последовательности 9. Выход i-го сумматора по модулю два 2.i соединен с информационным входом i-го РС 3.i, тактовый вход которого соединен с вторым, входом i-го элемента Т 4.i. Выход i-го РС 3.i подключен к первому входу i-го элемента И 4.i. Выходы j-го, где j=1,m, и m-го разрядов первого РС 3.1 подключены соответственно к первому и второму входам первого сумматора по модулю два 2.1. Выход k-го и (m+1)-го, где k=1, m+1, 1= 2,n, разрядов 1-го регистра сдвига 3.1, подключены соответственно к первому и второму входам 1-го сумматора по модулю два 2.1. Первый выход ФСЧ 5 подключен к тактовому входу первого РС 3.1. l-й выход ФСЧ 5 подключен к тактовому входу i-го РС 3.i. N-й выход ФСЧ 5 подключен к входу ГПК 6. Выход ГПК 6 подключен к входу регистра 7. К третьим входам n элементов 4.1-4.n подключены выходов n-ячеек регистра 7, а выходы n элементов И 4.1-4.n подключены к n-входам УС 8. Выход ГИ 1 подключен к входу ФСЧ 5. Выход УС 8 является выходом 9 генератора псевдослучайной последовательности.

ГИ 1 в первом варианте предназначен для формирования импульсов со скважностью T/t= 2, где T - период следования импульсов, а t - длительность импульсов. Такие генераторы известны и описаны например в [3, с. 240, рис. 7.9].

ФСЧ 5 в первом варианте предназначен для формирования, в зависимости от входной частоты следования импульсов F=1/T скважности 2, на своих m выходах импульсов с частотами следования
F,F²,F⁴,...F^2(m-1). (1)
Схема построения ФСЧ 5 в первом варианте, реализующая такие задачи в заявляемом устройстве, приведена на фиг. 3 и состоит из блоков удвоения (БлУ) 5.1-5. m. При этом каждый блок удвоения 5.1-5.m содержит: элементы задержки (33) 5.12-5.m2, 5.18-5.m8, элементы НЕ 5.11-5.m1, 5.13-5.m3, 5.17-5.m7, элементы И 5.14-5.m4, 5.15-5.m5, 5.19-5.m9, элементы ИЛИ 5.16-5.m6.

УС 8 в первом варианте представляет собой многовходовой сумматор по модулю два. Схема УС 8 с учетом решаемых задач известна, принцип работы и варианты ее реализации описаны например в [3, с. 74, Рис. 2.12].

Генератор ключевой последовательности 6 представляет собой полиномиальный счетчик, формирующий псевдослучайные последовательности. Схема и принцип работы такого счетчика известны и описаны в [3, с. 290-294].

Регистры сдвига 3.1-3.n представляют собой сдвигающие регистры, схема и принцип работы которых известны и описаны, например, в [3, с. 276-277].

Заявляемое устройство (первый вариант) работает следующим образом.

С выхода ГИ 1 последовательность импульсов скважности T/τ = 2 поступает на вход ФСЧ 5 (фиг. 3). Каждый БлУ 5.1-5.m осуществляет удвоение частоты следования импульсов с сохранением скважности - 2 (фиг. 4b). В БлУ 5.1 удвоение частоты следования входной последовательности импульсов осуществляется следующим образом. Последовательность импульсов (фиг. 4a) поступает на 33 5.12, время задержки которой t_ла1 = τ/2 (фиг. 4z), и элемент НЕ 5.11 (фиг. 4v), где они соответственно задерживаются и инвертируются. В момент одновременного присутствия на обеих входах элемента И 5.14 на его выходе будет сформирован импульс (фиг. 4g). Аналогичный импульс будет сформирован и на выходе элемента И 5.15 в момент присутствия на первом входе последовательности инвертированных и задержанных импульсов, поступающих с входа БлУ 5.1, и входной последовательности импульсов (фиг. 4a). На выходе элемента ИЛИ 5.16 будет сформирована удвоенная частота следования импульсов из последовательностей импульсов, поступающих на его вход, - с выходов элементов И 5.14 и 5.15 (фиг. 4b). Если частота следования входной последовательности импульсов равна F= 1/T при скважности, равной 2, то выходная удвоенная частота следования импульсов будет суммой последовательностей удвоенной скважности с той же частотой следования импульсов.

T/(0.5t)+T/(0.5t)-2(T/0.5t), (2)
или
F=1/2T, 2F=1/T. (3)
Сформированная последовательность импульсов удвоенной частоты следования скважности 2 одновременно поступает на очередной вход БлУ 5.2 и на входы элементов НЕ 5.17 и 33 5.18 и в двух последних элементах, соответственно, инвертируется (фиг. 4x) и задерживается (фиг. 4y). В момент одновременного присутствия на входах элемента И 5.19 данных импульсов будут сформированы короткие импульсы (фиг. 4d) с частотой следования 2F и длительностью, равной 50...100 нс. Длительность определяться временем задержки в 33 5.19 t_ла2, которая достаточна для формирования импульсов на выходе элемента И 5.19 и их использования в качестве импульсов тактовой частоты при функционирования РС 2.1-3. n в качестве генератора порождающих псевдослучайных последовательностей.

Принцип работы следующих БлУ5.2-5.m аналогичен изложенному выше. Таким образом, входная последовательность импульсов, поступающая на вход ФСЧ 5, будет преобразована в сетку частот (1).

Последовательности тактовых импульсов с частотами (1) с соответствующих выходов ФСЧ 5 поступают на тактовые входы РС 3.1-3.n и на вторые входы элементов И 4.1-4. n. Учитывая, что первый РС 3.1 содержит i-ячеек, а каждый последующий РС 3.2-3.n на 2 ячейки больше предыдущего регистра сдвига, на их выходах будут формироваться порождающие псевдослучайные последовательности со следующими периодами:
iT,(i+2)T,...,(i+1)T. (7)
Как известно [4, с. 191], если из последовательности случайных чисел g(t), генерируемой с частотой F, формировать n последовательностей случайных чисел со следующими частотами следования:
g₁(t) 2^oF, g₃(t) 2¹F, g₃(t) 2²F,...,g_n(t) 2^n-1F, (4)
в которой n-й разряд (самый старший) формируется с частотой 2^n-1F, (n-1)-й разряд с частотой 2^n-2F и т.д., а 1-й разряд (самый младший) с частотой 2^oF, то в результате получится n-значная последовательность случайных чисел с равновероятным законом распределения

В предлагаемом генераторе время формирования порождающих псевдослучайных последовательностей в каждом РС 3.1-3. n будет одинаковым, т.к. частоты следования тактовых импульсов относительно входной удваиваются от первого РС 3.1 к последующему, согласно (1). Для случайного выбора порождающих псевдослучайных последовательностей ГПК 6 генерирует псевдослучайную последовательность, которая поступает на вход регистра 7. С n-выходов ячеек регистра 7 значения псевдослучайной последовательности в виде значений логического "0" и "1" поступают на третьи входы соответствующих элементов И 4.1-4. n, которые являются управляющими сигналами для случайного выбора псевдослучайных последовательностей.

Исходя из свойств псевдослучайной последовательности, полученной на основе двух регистров сдвига [4, с. 264], период таких последовательностей равен наименьшему общему кратному значений периодов исходных последовательностей T=[M,N], где M и N - периоды исходных псевдослучайных последовательностей, значения которых представляют собой взаимно простые числа.

Таким образом, на выходах элементов И 4.1-4.n будут формироваться всевдослучайные числа, разрядность которых зависит от потактного внутреннего состояния ГКП 6, т.е. от однозначного до n-значного [4, с. 244-245].

Далее полученные j-ичные псевдослучайные числа, где поступают на УС 8, в котором происходит их преобразование в псевдослучайную последовательность повышенной структурной скрытности.

Заявляемое устройство по второму варианту содержит (фиг. 2): генератор импульсов (ГИ) 1; сумматоры по модулю два 2.1-2.n; регистры сдвига (РС) 3.1-3.n; элементы И 4.1-4.n; формирователь сетки частот (ФСЧ) 5; блок выбора ключа (БВК) 6; узел свертки (УС) 7; выход генератора псевдослучайной последовательности 8. Выход i-го сумматора по модулю два 2.1 соединен с информационным входом i-го РС 3.i, тактовый вход которого соединен с вторым входом i-го элемента И 4.i, на первый вход элемента И 4.1 подключен выход i-го РС 3. i. Выходы j-го, где и m-го разрядов i-го РС 3.1-3.n подключены соответственно к первому и второму входу i-го сумматора по модулю два 2.1. I-й выход ФСЧ 5 подключен к тактовому входу i-го РС 3.i. К третьим входам n элементов И 4.1-4.n подключены соответствующие n выходы БВК 6. Выходы n элементов И 4.1-4. n подключены к n входам УС 7. Выход ГИ 1 подключен к входу ФСЧ 5. Выходом 8 генератора псевдослучайной последовательности является выход УС 7.

БВК 6 предназначен для выдачи на своих выходах логических двоичных величин "1" или "0". С учетом решаемых задач может быть реализован в виде набора переключателей П₁-П_n, коммутирующих на третьи входы элементов И 4.1-4.n уровень напряжения логической единицы или нуля (U_лог"1"; U_лог"0") (фиг. 5).

Схемы, назначение ГИ 1, сумматоры по модулю два 2.1-2.n, РС 3.1-3.n, элементы И 4.1-4.n, ФСЧ 5, УС 7 во втором варианте аналогичны схемам и назначениям в первом варианте.

Заявляемое устройство во втором варианте работает аналогично устройству в первом варианте. За исключением, во-втором варианте РС 3.1-3.n имеют одинаковое число ячеек, а занчит и формируемые ими псевдослучайные последовательности имеют одинаковый период. Учитывая, что на их тактовые входы поступают последовательности тактовых импульсов с частотами (1) с соответствующих выходов ФСЧ 5, то время формирования первой порождающей псевдослучайной последовательности будет в два раза больше времени формирования второй порождающей псевдослучайной последовательности и т. д. , а n-ой псевдослучайной последовательности - в n-раз больше.

Выбор порождающих псевдослучайных последовательностей происходит путем выбора ключа - подачи уровней напряжения, равных уровню логического "0" или "1", на третьи входы элементов И 4.1-4.n. При подаче "1" соответствующий элемент И пропускает порождающую псевдослучайную последовательность и не пропускает в случае подачи "0".

Далее в зависимости от выбора ключа в БВК 6 с соответствующих выходов элементов И 4.1-4. n порождающие последовательности поступают на УС 8, в котором происходит их преобразование в ПСП повышенной структурной скрытности.

Если, например, изменить ключ в БВК 6, то уровни напряжения логической "1" будут поданы на третьи входы других элементов И 4.1-4.(m-j). В этом случае будет пропущен на входы УС 7 другой набор порождающих псевдослучайных последовательностей. Т. о. на выходе УС 7 будет сформирована другая псевдослучайная последовательность повышенной структурной скрытности.

По сравнению с прототипом заявляемый генератор в первом и во втором вариантах может формировать на своем выходе ПСП повышенной структурной скрытности. Техническая реализация таких генераторов не вызывает практических затруднений т.к. не требуется решать задачу синтеза генераторов ПСП и нахождения аналитических решений при определении их оптимальной структуры [4]. Кроме того, в генераторе можно легко изменять закон или правило формирования псевдослучайной последовательности, что позволяет использовать такие устройства в качестве зашумляющих устройств различных каналов связи.

Список использованных источников:
1. А.с. 1661975, H 03 K 3/84.

2. А.с. 2081450, G 06 F 7/58.

3. Потемкин И.С. Функциональные узлы цифровой автоматики. - М.: Энергоатомиздат, 1988. - 300 с.: ил.

4. Яковлев В. В. Стохастические вычислительные машины. - Л.: Машиностроение, 1974., с. 191.

Изобретения относятся к области вычислительной техники и могут быть использованы для формирования сложных сигналов в радиосистемах. Техническим результатом является формирование сигналов повышенной структуры скрытности. Генератор содержит элементы И, сумматоры по модулю два, регистры сдвига, формирователь сетки частот, генератор импульсов и узел свертки. Согласно первому варианту генератор дополнительно содержит генератор ключевой последовательности и регистр. Согласно второму варианту генератор содержит блок выбора ключа, 2 c.п. ф-лы, 5 ил.

1. Генератор псевдослучайной последовательности, содержащий n элементов И, где n = 2, 3, ... , n сумматоров по модулю два, n регистров сдвига, выход i-го сумматора по модулю два, где соединен с информационным входом i-го регистра сдвига, тактовый вход которого соединен с вторым входом i-го элемента И, выход i-го регистра сдвига подключен к первому входу i-го элемента И, отличающийся тем, что в него дополнительно введены формирователь сетки частот, генератор импульсов, который предназначен для формирования импульсов с определенной скважностью, последовательность которых поступает на вход формирователя сетки частот, генератор ключевой последовательности, регистр, узел свертки, выходы j-го, где а m = 2, 3, ..., и m-го разрядов первого регистра сдвига подключены соответственно к первому и второму входам первого сумматора по модулю два, выход k-го и (m + l)-го, разрядов l-го регистра сдвига, где подключены соответственно к первому и второму входам l-го сумматора по модулю два, первый выход формирователя сетки частот подключен к тактовому входу первого регистра сдвига, l-й выход формирователя сетки частот подключен к тактовому входу l-го регистра сдвига, к входу генератора ключевой последовательности подключен n-й выход формирователя сетки частот, выход генератора ключевой последовательности подключен к входу регистра, n выходов регистра подключены к третьим входам соответствующих n элементов И, выходы n элементов И подключены к соответствующим n входам узла свертки, выход узла свертки является выходом генератора псевдослучайной последовательности. 2. Генератор псевдослучайной последовательности, содержащий n элементов И, где n = 2, 3, ... n, сумматоров по модулю два, n регистров сдвига, выход i-го сумматора по модулю два, где соединен с информационным входом i-го регистра сдвига, тактовый вход которого соединен с вторым входом i-го элемента И, выход i-го регистра сдвига подключен к первому входу i-го элемента И, отличающийся тем, что в него дополнительно введены формирователь сетки частот, генератор импульсов, который предназначен для формирования импульсов с определенной скважностью, последовательность которых поступает на вход формирователя сетки частот, блок выбора ключа, узел свертки, выходы j-го, где а m = 2, 3 ..., и m-го разрядов i-го регистра сдвига подключены к первому и второму входам i-го сумматора по модулю два, i-й выход формирователя сетки частот подключен к тактовому входу i-го регистра сдвига, к третьим входам n элементов И подключены n выходов блока выбора ключа, выходы n элементов И подключены к n входам узла свертки, выход узла свертки является выходом генератора псевдослучайной последовательности.