Генератор периодических псевдослучайных двоичных последовательностей сложной структуры с корреляционными свойствами, близкими к идеальным
GENERATOR OF PERIODIC PSEUDORANDOM BINARY SEQUENCES OF COMPLEX STRUCTURE WITH CORRELATION PROPERTIES CLOSE TO IDEAL

Изобретение относится к вычислительной технике и предназначено для генерации псевдослучайных двоичных последовательностей сложной структуры с корреляционными свойствами, близкими к идеальным, используемых в широкополосных системах связи, в радарах с непрерывным излучением, а также в криптографии.
В настоящее время известны различные генераторы псевдослучайных двоичных последовательностей (RU 2642351 (С1) - 2018-01-24, KR 20160067992 (А) - 2016-06-14, GB 1518997 (А) - 1978-07-26, ЕР 0492325 (А2) - 1992-07-01, RU2013802 (А) - 1994-05-30, SU1265973 (А1) - 1986-10-23, US 2018011691 (А1) - 2018-01-11, ES 2644485 (Т3) - 2017-11-29, CN 107683502 (А) - 2018-02-09, Ипатов В.И. Периодические дискретные сигналы с оптимальными корреляционными свойствами. - М.: Радио и связь, 1992, Fan P. and Darnell М. Sequence Design for Communications Applications.- RSP-John Wiley & Sons Inc., London, 1996, S. W. Golomb and G Gong, Signal Design for Good Correlation: for Wireless Communication, Cryptography, and Radar. Cambridge University Press, ISBN 0521821045, 2005 и др.) с хорошими корреляционными свойствами.
m
m
m
i
Известны также почти сбалансированные (ПС) почти идеальные двоичные последовательности (ПИДП) длины 2(p+1), где р>2 простое число, а m≥1 целое (Н.D. , Н.D. Schotten, Н. Hadinejad-Mahram. Binary and quadriphase sequences with optimal autocorrelation properties: survey. - IEEE Transaction on Information Theory, vol. IT-49, No. 12, pp. 3271-3282, 2003), и почти идеальные троичные последовательности (ПИТП) с алфавитом {1,-1,0} длины 4(p+1), (p-1)≡0 (mod 4), имеющие четыре нуля и равное число единиц и минус единиц (Кренгель Е.И. Конструирование почти идеальных и нечетно-идеальных троичных последовательностей. - журнал «Радиотехника», №9, 2006, стр. 8-12). Последовательность х={x} длины N называется почти идеальной, если ее периодическая автокорреляционная функция при всех ненулевых сдвигах, кроме одного, равна нулю. Двоичную последовательность четной длины называют сбалансированной, если число нулей (единиц) в ней равно числу единиц (минус единиц) и почти сбалансированной, если разность между числом единиц и нулей по модулю равно двум.
m
ПИТП длины 4(p+1) при замене нулей на последовательность 1 -1 1 -1 преобразуются по существу в сбалансированную ПИДП с малыми энергетическими потерями при обработке в несогласованном фильтре в приемнике. Полученные с помощью такого метода двоичные последовательности получили название несогласованных ПИДП (НПИДП) (Кренгель Е.И. Несогласованные почти идеальные двоичные последовательности. - журнал «Цифровая обработка сигналов», №4, 2006, стр. 44-47). НПИДП относятся к нелинейным псевдослучайным двоичным последовательностям и обладают сложной структурой, характеризуемой высокой линейной сложностью, что делает их привлекательными для использования в криптографических системах. Линейная сложность является одной из важных характеристик двоичных последовательностей и численно равна наименьшей длине регистра сдвига с обратными связями, генерирующего эту последовательность.
m
m
m
m
m
В работе (Кренгель Е.И., Иванов П.В. Новые троичные последовательности с двумя ненулевыми боковыми лепестками периодической автокорреляционной функции и пик-фактором, близким к единице. - Сборник докладов 18-й международной конференции «Цифровая обработка сигналов и ее применение (DSPA-2016)», 30 марта - 1 апреля 2016, Москва, стр. 183-187) на основе ПИТП длины N=2(p+1) и ПИТП длины 2N=4(p+1), p-1≡4 (mod 4) были построены новые троичные последовательности длины 8(p+1) с 8-ю нулями и нулевыми боковыми лепестками ПАКФ во всех точках, кроме N и 3N, в которых ПАКФ принимает значение -4p. Нулевая зона автокорреляции этих последовательностей равна D=N, т.е. составляет четверть их периода. Преимуществом полученных последовательностей по сравнению с ПИДП является то, что при их корреляционной обработке мы можем легко идентифицировать боковые лепестки по их временному положению, поскольку расстояние между ними 2N, а расстояние между ними и ближайшим основным лепестком - N. Эти последовательности обладают пик-фактором, близким к единице, и легко трансформируются в сбалансированные двоичные последовательности, которые при несогласованной фильтрации с незначительными потерями обеспечивают на выходе фильтра такую же ПАКФ, что и рассматриваемая троичная последовательность.
m
m
m
m
В работе (Edemskiy V., Minin A. About the linear complexity of the almost perfect sequences. - International Journal of Communications, Vol. 1, 2016, pp. 223-226) показано, что линейная сложность L образованных на основе ПИДП длины 2(p+1) и НПИДП длины 4(p+1) двоичных последовательностей длины 8(p+1) равна 6(p+1), что составляет 0,75 длины последовательности, ограничивающей сверху величину линейной сложности последовательности.
Математическое определение этих последовательностей дано в (Кренгель Е.И. Конструирование почти идеальных и нечетно-идеальных троичных последовательностей. - журнал «Радиотехника», №9, 2006, стр. 8-12, Кренгель Е.И. Несогласованные почти идеальные двоичные последовательности. - журнал «Цифровая обработка сигналов», №4, 2006, стр. 44-47, и Кренгель Е.И., Иванов П.В. Новые троичные последовательности с двумя ненулевыми боковыми лепестками периодической автокорреляционной функции и пик-фактором, близким к единице. - Сборник докладов 18-й международной конференции «Цифровая обработка сигналов и ее применение (DSPA-2016)», 30 марта - 1 апреля 2016, Москва, стр. 183-187).
n
m
n
m
m
Пусть р>2 есть простой, и а есть примитивный элемент поля GF(p), где n=2m, m≥1. Пусть β есть примитивный элемент поля GF(p) и Т=(p-1)/(p-1)=p+1. Тогда последовательность w, задаваемая правилом
где
m
m
есть ПИТП длины 2(p+1) с пиковыми значениями 2p и числом нулевых элементов 2.
n
m
m
β
Здесь  - след элемента х из GF(p) относительно GF(p), a indx - индекс (логарифм) х по основанию β. При замещении 2-х равноотстоящих на Т нулей в последовательности w единицами или минус единицами мы получим ПИДП длины 2(p+1).
m
Пусть р>2 - простое число, n=2m, а m≥1 такое, что p-1 кратно 4.
Тогда последовательность v, задаваемая правилом
где
m
m
есть ПИТП длины 4(p+1) с пиковыми значениями ACF(0)=-ACF(2T)=4p и числом нулевых элементов 4. Здесь  есть max {n| n≤u, n - целое}, т.е.  есть операция округления числа к меньшему. При замещении 4-х равноотстоящих на Т нулей в последовательности v на одну из трех двоичных последовательностей 1111,-1-1-1-1 или 1 -1 1 -1 мы получим НПИДП. Причем, в последнем случае последовательность будет сбалансированная, т.е. с равным числом -1 и 1, а при переходе к двоичному алфавиту {0,1} соответственно с равным числом 1 и 0.
m
m
n
m
m
m
В работе (Кренгель Е.И. Новые идеальные 4-фазные и 8-фазные последовательности с нулями. - журнал «Радиотехника», №5, 2007, стр. 3-8) описана схема генератора ПИТП длины 4(p+1) с 4-мя нулями. Вычисление символов НПИДП производится посредством генератора m-последовательности (ГМП) над GF(p) длины p-1, выход которого соединен с входом блока вычисления функции ψ(x). Основная сложность реализации генератора НПИДП связана с вычислением дискретного логарифма х по основанию примитивного элемента β. Поэтому наибольшее быстродействие достигается при использовании таблиц, содержащих логарифмы всех p элементов из GF(p). Объем таблиц в этом случае максимален и составляет p слов длиной приблизительно  бит, что почти в  раз превышает длину генерируемой двоичной последовательности. Здесь  есть min , т.е.есть  операция округления числа и к большему.
j
m
m
m
m
m
m
m
m
Для уменьшения объема памяти можно упростить блок вычисления функции ψ(x) за счет использования таблицы отображения p элементов х поля GF(p) в соответствующий двоичный символ последовательности  по следующему правилу: х→ψ(x), х≠0, а ψ(0) равно 1 или 0. В результате длина слова в таблице отображения равна 1 биту. Эта таблица может быть реализована с помощью ПЗУ объемом px1, адресным входом в которое является двоичное представление элемента x∈GF(p) на выходе ГМП над GF(p). В этом случае генератор НПИДП длины 4(p+1) состоит из последовательно соединенных ГМП над GF(p), блока преобразования (БП), отображающее выходной символ ГМП в виде mp-ичных коэффициентов в  двоичное число, являющееся адресным входом ПЗУ объемом px1 бит.
m
m
Аналогичную конструкцию имеет генератор ПИДП длины 2(p+1), отличающийся от генератора НПИДП длины 4(p+1) только содержанием ПЗУ.
m
m
k
Пусть y=w⋅w есть последовательность длины 2N, полученная конкатенацией ПИТП w длины N=2(p+1). Посредством перемешивания (интерливинга) элементов последовательностей у и ПИТП v, образуем последовательность f={ƒ} длины 8(p+1) с общим членом
и числом нулей, равным 8. ПАКФ последовательность f имеет трехуровневую ПАКФ вида:
*
*
*
*
m
m
*
*
m
n
m
m
m
*
*
Трансформация последовательности f в двоичную последовательность f достигается путем замены нулей на четных позициях единицами (минус единицами), а нулей на нечетных позициях минус единицами (единицами). В этом случае последовательность f является сбалансированной, т.е. имеет равное число единиц и минус единиц, и периодическая взаимно корреляционная функция (ПВКФ) последовательностей f и f совпадает с ПАКФ последовательности f. Очевидно, что в случае обработки двоичной последовательности f в фильтре, согласованном с троичной последовательностью f, энергетические потери будут незначительны, поскольку эффективность несогласованной фильтрации η=1/PF стремится к единице с ростом N. Преимуществом полученных последовательностей по сравнению с ПИДП является то, что при их корреляционной обработке мы можем легко идентифицировать боковые лепестки по их временному положению, поскольку расстояние между ними 2N, а расстояние между ними и ближайшим основным лепестком равно N. Заметим, что в построении последовательностей (3) могут участвовать произвольно составленные пары ПИТП (1) и (2), которые получаются на основе различных примитивных полиномов степени n над полем GF(p). В этом случае для генерации ПИТП (1) и (2) необходимо использовать два независимых ГМП и, соответственно, два блока преобразования элементов GF(p) в двоичный адрес. Однако при выборе одних и тех же полиномов для пары ПИТП (1) и (2) задача существенно упрощается. Платой за это является уменьшение общего числа генерируемых последовательностей f до числа ПИТП (2), равного  где ϕ - функция Эйлера, которое при больших р остается все еще достаточно большим. В этом случае для генерации двоичной последовательности f можно использовать один и тот же ГМП над GF(p) длины p-1 и один блок преобразования БП. ПЗУ будет также общим, но с объемом px2. Каждый первый бит двухразрядного слова ПЗУ по адресу i соответствует содержимому бита по адресу i ПЗУ генератора НПИДП длины 4(p+1), а каждый второй бит двухразрядного слова ПЗУ по адресу i соответствует содержимому бита по адресу i ПЗУ генератора ПИДП длины 2(p+1). Для формирования двоичной последовательности f необходимо двухразрядный двоичный код на выходе ПЗУ преобразовать из параллельного кода в последовательный. При этом по нулевому адресу в ПЗУ содержится двоичное число 10 или 10. Следует отметить, что при несогласованной фильтрации на вход коррелятора приемника поступает последовательность f с алфавитом {1,-1}, а в качестве весовой последовательности в нем используется ПИТП f с символами {1,-1,0}.
С учетом вышеизложенного технический результат, обеспечиваемый изобретением, состоит в генерации ансамбля двоичных последовательностей сложной структуры с корреляционными свойствами, близкими к идеальным, за счет перемежения символов известных последовательностей.
m
n
m
m
Указанный результат достигается генератором периодических псевдослучайных двоичных последовательностей сложной структуры с корреляционными свойствами, близкими к идеальным, содержащим последовательно соединенные ГМП над GF(p) длины p-1, где n=2m, (p-1)≡0 (mod 4), блок преобразования (БП) m-разрядногор-ичного числа в  двоичное число, ПЗУ, отличающимся тем, что объем ПЗУ равен px2 бит и дополнительно введен преобразователь из параллельного двоичного кода в последовательный, два входа которого соединены с соответствующими двумя выходами ПЗУ.
m
m
n
m
m
m
m
Блок-схема генератора периодических псевдослучайных двоичных последовательностей сложной структуры с корреляционными свойствами, близкими к идеальным, длины 8(p+1) представлена на Фиг. 1. Устройство содержит ГМП 1 над GF(p) длины p-1, БП m-разрядного p-ичного числа в двоичное 2, вход которого соединен с соответствующим m-разрядным выходом ГМП 1, ПЗУ 3 объемом px 2 бит, соединенное по своему адресному входу с выходом БП 3 и преобразователь 4 из параллельного двоичного кода в последовательный, два входа которого соединены с соответствующими двумя выходами ПЗУ 3. При этом каждый первый бит двухразрядного слова ПЗУ по адресу 0<i<p соответствует содержимому бита по адресу i ПЗУ генератора НПИДП длины 4(p+1), а каждый второй бит двухразрядного слова ПЗУ по адресу i соответствует содержимому бита по адресу i ПЗУ генератора ПИДП длины 2(p+1), а по нулевому адресу ПЗУ 10 содержит двоичное слово 10 или 01.
t
t
t
t
m
m
Генератор работает следующим образом. Первоначально в регистр сдвига 2 также записывается некоторое ненулевое число. Обычно это единица. На вход генератора 1 поступают тактовые импульсы с частотой ƒ. С частотой ƒ на выходе ГМП 1 формируется следующий p-ичный символ m-последовательности, который поступает на вход БП 2. В БП 2 этот символ из p-ичного числа преобразуется в двоичное число и является адресом, по которому из ПЗУ 3 считывается в параллельном виде двухразрядное двоичное число. С выхода ПЗУ 3 это число поступает на вход преобразователя 4, осуществляющего его преобразования из параллельного двоичного кода в последовательный, формируя таким образом два последовательных двоичных сигнала, каждый длительностью T=1/2ƒ. В результате на выходе преобразователя 4 формируется периодическая псевдослучайная двоичная последовательность сложной структуры длины 8(p+1) с частотой следования символов 2ƒ.
Заметим, что преобразователь 4 из параллельного двоичного кода в последовательный может быть выполнен с использованием мультиплексора.
Предлагаемое изобретение может быть реализовано на соответствующей элементной базе по типовым технологиям.