Генератор периодических псевдослучайных двоичных последовательностей сложной структуры с корреляционными свойствами, близкими к идеальным Российский патент 2019 года по МПК G06F7/58 

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

В настоящее время известны различные генераторы псевдослучайных двоичных последовательностей (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 и др.) с хорошими корреляционными свойствами.

Известны также почти сбалансированные (ПС) почти идеальные двоичные последовательности (ПИДП) длины 2(p^m+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^m+1), (p^m-1)≡0 (mod 4), имеющие четыре нуля и равное число единиц и минус единиц (Кренгель Е.И. Конструирование почти идеальных и нечетно-идеальных троичных последовательностей. - журнал «Радиотехника», №9, 2006, стр. 8-12). Последовательность х={x_i} длины N называется почти идеальной, если ее периодическая автокорреляционная функция при всех ненулевых сдвигах, кроме одного, равна нулю. Двоичную последовательность четной длины называют сбалансированной, если число нулей (единиц) в ней равно числу единиц (минус единиц) и почти сбалансированной, если разность между числом единиц и нулей по модулю равно двум.

ПИТП длины 4(p^m+1) при замене нулей на последовательность 1 -1 1 -1 преобразуются по существу в сбалансированную ПИДП с малыми энергетическими потерями при обработке в несогласованном фильтре в приемнике. Полученные с помощью такого метода двоичные последовательности получили название несогласованных ПИДП (НПИДП) (Кренгель Е.И. Несогласованные почти идеальные двоичные последовательности. - журнал «Цифровая обработка сигналов», №4, 2006, стр. 44-47). НПИДП относятся к нелинейным псевдослучайным двоичным последовательностям и обладают сложной структурой, характеризуемой высокой линейной сложностью, что делает их привлекательными для использования в криптографических системах. Линейная сложность является одной из важных характеристик двоичных последовательностей и численно равна наименьшей длине регистра сдвига с обратными связями, генерирующего эту последовательность.

В работе (Кренгель Е.И., Иванов П.В. Новые троичные последовательности с двумя ненулевыми боковыми лепестками периодической автокорреляционной функции и пик-фактором, близким к единице. - Сборник докладов 18-й международной конференции «Цифровая обработка сигналов и ее применение (DSPA-2016)», 30 марта - 1 апреля 2016, Москва, стр. 183-187) на основе ПИТП длины N=2(p^m+1) и ПИТП длины 2N=4(p^m+1), p^m-1≡4 (mod 4) были построены новые троичные последовательности длины 8(p^m+1) с 8-ю нулями и нулевыми боковыми лепестками ПАКФ во всех точках, кроме N и 3N, в которых ПАКФ принимает значение -4p^m. Нулевая зона автокорреляции этих последовательностей равна D=N, т.е. составляет четверть их периода. Преимуществом полученных последовательностей по сравнению с ПИДП является то, что при их корреляционной обработке мы можем легко идентифицировать боковые лепестки по их временному положению, поскольку расстояние между ними 2N, а расстояние между ними и ближайшим основным лепестком - N. Эти последовательности обладают пик-фактором, близким к единице, и легко трансформируются в сбалансированные двоичные последовательности, которые при несогласованной фильтрации с незначительными потерями обеспечивают на выходе фильтра такую же ПАКФ, что и рассматриваемая троичная последовательность.

В работе (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^m+1) и НПИДП длины 4(p^m+1) двоичных последовательностей длины 8(p^m+1) равна 6(p^m+1), что составляет 0,75 длины последовательности, ограничивающей сверху величину линейной сложности последовательности.

Математическое определение этих последовательностей дано в (Кренгель Е.И. Конструирование почти идеальных и нечетно-идеальных троичных последовательностей. - журнал «Радиотехника», №9, 2006, стр. 8-12, Кренгель Е.И. Несогласованные почти идеальные двоичные последовательности. - журнал «Цифровая обработка сигналов», №4, 2006, стр. 44-47, и Кренгель Е.И., Иванов П.В. Новые троичные последовательности с двумя ненулевыми боковыми лепестками периодической автокорреляционной функции и пик-фактором, близким к единице. - Сборник докладов 18-й международной конференции «Цифровая обработка сигналов и ее применение (DSPA-2016)», 30 марта - 1 апреля 2016, Москва, стр. 183-187).

Пусть р>2 есть простой, и а есть примитивный элемент поля GF(pⁿ), где n=2m, m≥1. Пусть β есть примитивный элемент поля GF(p^m) и Т=(pⁿ-1)/(p^m-1)=p^m+1. Тогда последовательность w, задаваемая правилом

где

есть ПИТП длины 2(p^m+1) с пиковыми значениями 2p^m и числом нулевых элементов 2.

Здесь - след элемента х из GF(pⁿ) относительно GF(p^m), a ind_βx - индекс (логарифм) х по основанию β. При замещении 2-х равноотстоящих на Т нулей в последовательности w единицами или минус единицами мы получим ПИДП длины 2(p^m+1).

Пусть р>2 - простое число, n=2m, а m≥1 такое, что p^m-1 кратно 4.

Тогда последовательность v, задаваемая правилом

где

есть ПИТП длины 4(p^m+1) с пиковыми значениями ACF(0)=-ACF(2T)=4p^m и числом нулевых элементов 4. Здесь есть max {n| n≤u, n - целое}, т.е. есть операция округления числа к меньшему. При замещении 4-х равноотстоящих на Т нулей в последовательности v на одну из трех двоичных последовательностей 1111,-1-1-1-1 или 1 -1 1 -1 мы получим НПИДП. Причем, в последнем случае последовательность будет сбалансированная, т.е. с равным числом -1 и 1, а при переходе к двоичному алфавиту {0,1} соответственно с равным числом 1 и 0.

В работе (Кренгель Е.И. Новые идеальные 4-фазные и 8-фазные последовательности с нулями. - журнал «Радиотехника», №5, 2007, стр. 3-8) описана схема генератора ПИТП длины 4(p^m+1) с 4-мя нулями. Вычисление символов НПИДП производится посредством генератора m-последовательности (ГМП) над GF(p^m) длины pⁿ-1, выход которого соединен с входом блока вычисления функции ψ(x). Основная сложность реализации генератора НПИДП связана с вычислением дискретного логарифма х по основанию примитивного элемента β. Поэтому наибольшее быстродействие достигается при использовании таблиц, содержащих логарифмы всех p^m элементов из GF(p^m). Объем таблиц в этом случае максимален и составляет p^m слов длиной приблизительно бит, что почти в раз превышает длину генерируемой двоичной последовательности. Здесь есть min , т.е.есть операция округления числа и к большему.

Для уменьшения объема памяти можно упростить блок вычисления функции ψ(x_j) за счет использования таблицы отображения p^m элементов х поля GF(p^m) в соответствующий двоичный символ последовательности по следующему правилу: х→ψ(x), х≠0, а ψ(0) равно 1 или 0. В результате длина слова в таблице отображения равна 1 биту. Эта таблица может быть реализована с помощью ПЗУ объемом p^mx1, адресным входом в которое является двоичное представление элемента x∈GF(p^m) на выходе ГМП над GF(p^m). В этом случае генератор НПИДП длины 4(p^m+1) состоит из последовательно соединенных ГМП над GF(p^m), блока преобразования (БП), отображающее выходной символ ГМП в виде mp-ичных коэффициентов в двоичное число, являющееся адресным входом ПЗУ объемом p^mx1 бит.

Аналогичную конструкцию имеет генератор ПИДП длины 2(p^m+1), отличающийся от генератора НПИДП длины 4(p^m+1) только содержанием ПЗУ.

Пусть y=w⋅w есть последовательность длины 2N, полученная конкатенацией ПИТП w длины N=2(p^m+1). Посредством перемешивания (интерливинга) элементов последовательностей у и ПИТП v, образуем последовательность f={ƒ_k} длины 8(p^m+1) с общим членом

и числом нулей, равным 8. ПАКФ последовательность f имеет трехуровневую ПАКФ вида:

Трансформация последовательности f в двоичную последовательность f^* достигается путем замены нулей на четных позициях единицами (минус единицами), а нулей на нечетных позициях минус единицами (единицами). В этом случае последовательность f^* является сбалансированной, т.е. имеет равное число единиц и минус единиц, и периодическая взаимно корреляционная функция (ПВКФ) последовательностей f и f^* совпадает с ПАКФ последовательности f. Очевидно, что в случае обработки двоичной последовательности f^* в фильтре, согласованном с троичной последовательностью f, энергетические потери будут незначительны, поскольку эффективность несогласованной фильтрации η=1/PF стремится к единице с ростом N. Преимуществом полученных последовательностей по сравнению с ПИДП является то, что при их корреляционной обработке мы можем легко идентифицировать боковые лепестки по их временному положению, поскольку расстояние между ними 2N, а расстояние между ними и ближайшим основным лепестком равно N. Заметим, что в построении последовательностей (3) могут участвовать произвольно составленные пары ПИТП (1) и (2), которые получаются на основе различных примитивных полиномов степени n над полем GF(p^m). В этом случае для генерации ПИТП (1) и (2) необходимо использовать два независимых ГМП и, соответственно, два блока преобразования элементов GF(p^m) в двоичный адрес. Однако при выборе одних и тех же полиномов для пары ПИТП (1) и (2) задача существенно упрощается. Платой за это является уменьшение общего числа генерируемых последовательностей f^* до числа ПИТП (2), равного где ϕ - функция Эйлера, которое при больших р остается все еще достаточно большим. В этом случае для генерации двоичной последовательности f^* можно использовать один и тот же ГМП над GF(p^m) длины pⁿ-1 и один блок преобразования БП. ПЗУ будет также общим, но с объемом p^mx2. Каждый первый бит двухразрядного слова ПЗУ по адресу i соответствует содержимому бита по адресу i ПЗУ генератора НПИДП длины 4(p^m+1), а каждый второй бит двухразрядного слова ПЗУ по адресу i соответствует содержимому бита по адресу i ПЗУ генератора ПИДП длины 2(p^m+1). Для формирования двоичной последовательности f^* необходимо двухразрядный двоичный код на выходе ПЗУ преобразовать из параллельного кода в последовательный. При этом по нулевому адресу в ПЗУ содержится двоичное число 10 или 10. Следует отметить, что при несогласованной фильтрации на вход коррелятора приемника поступает последовательность f^* с алфавитом {1,-1}, а в качестве весовой последовательности в нем используется ПИТП f с символами {1,-1,0}.

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

Указанный результат достигается генератором периодических псевдослучайных двоичных последовательностей сложной структуры с корреляционными свойствами, близкими к идеальным, содержащим последовательно соединенные ГМП над GF(p^m) длины pⁿ-1, где n=2m, (p^m-1)≡0 (mod 4), блок преобразования (БП) m-разрядногор-ичного числа в двоичное число, ПЗУ, отличающимся тем, что объем ПЗУ равен p^mx2 бит и дополнительно введен преобразователь из параллельного двоичного кода в последовательный, два входа которого соединены с соответствующими двумя выходами ПЗУ.

Блок-схема генератора периодических псевдослучайных двоичных последовательностей сложной структуры с корреляционными свойствами, близкими к идеальным, длины 8(p^m+1) представлена на Фиг. 1. Устройство содержит ГМП 1 над GF(p^m) длины pⁿ-1, БП m-разрядного p-ичного числа в двоичное 2, вход которого соединен с соответствующим m-разрядным выходом ГМП 1, ПЗУ 3 объемом p^mx 2 бит, соединенное по своему адресному входу с выходом БП 3 и преобразователь 4 из параллельного двоичного кода в последовательный, два входа которого соединены с соответствующими двумя выходами ПЗУ 3. При этом каждый первый бит двухразрядного слова ПЗУ по адресу 0<i<p^m соответствует содержимому бита по адресу i ПЗУ генератора НПИДП длины 4(p^m+1), а каждый второй бит двухразрядного слова ПЗУ по адресу i соответствует содержимому бита по адресу i ПЗУ генератора ПИДП длины 2(p^m+1), а по нулевому адресу ПЗУ 10 содержит двоичное слово 10 или 01.

Генератор работает следующим образом. Первоначально в регистр сдвига 2 также записывается некоторое ненулевое число. Обычно это единица. На вход генератора 1 поступают тактовые импульсы с частотой ƒ_t. С частотой ƒ_t на выходе ГМП 1 формируется следующий p^m-ичный символ m-последовательности, который поступает на вход БП 2. В БП 2 этот символ из p-ичного числа преобразуется в двоичное число и является адресом, по которому из ПЗУ 3 считывается в параллельном виде двухразрядное двоичное число. С выхода ПЗУ 3 это число поступает на вход преобразователя 4, осуществляющего его преобразования из параллельного двоичного кода в последовательный, формируя таким образом два последовательных двоичных сигнала, каждый длительностью T=1/2ƒ_t. В результате на выходе преобразователя 4 формируется периодическая псевдослучайная двоичная последовательность сложной структуры длины 8(p^m+1) с частотой следования символов 2ƒ_t.

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

Предлагаемое изобретение может быть реализовано на соответствующей элементной базе по типовым технологиям.

Изобретение относится к средствам генерации псевдослучайных двоичных сбалансированных последовательностей с автокорреляционными свойствами, используемым в широкополосных системах связи, в радарах с непрерывным излучением, а также в криптографии. Технический результат заключается в обеспечении корреляционных свойств близких к идеальным за счет перемежения символов известных последовательностей. Генератор периодических псевдослучайных двоичных последовательностей сложной структуры с корреляционными свойствами, близкими к идеальным, содержащий последовательно соединенные генератор m-последовательности над GF(p^m) длины рⁿ-1, где n=2m, (р^m-1)=0 (mod 4), блок преобразования выходного символа m-последовательности в виде m-разрядного p-ичного числа в разрядное двоичное число, двоичные выходы которого соединены с соответствующими адресными входами ПЗУ, отличающийся тем, что объем ПЗУ равен р^mх2 бит и дополнительно введен преобразователь из параллельного двоичного кода в последовательный, два входа которого соединены с соответствующими двумя выходами ПЗУ. 1 ил.

Генератор периодических псевдослучайных двоичных последовательностей сложной структуры с корреляционными свойствами, близкими к идеальным, содержащий последовательно соединенные генератор m-последовательности над GF(p^m) длины pⁿ-1, где n=2m, (p^m-1)≡0 (mod 4), блок преобразования (БП) выходного символа m-последовательности в виде m-разрядного p-ичного числа в разрядное двоичное число, двоичные выходы которого соединены с соответствующими адресными входами ПЗУ, отличающийся тем, что объем ПЗУ равен p^mx2 бит и дополнительно введен преобразователь из параллельного двоичного кода в последовательный, два входа которого соединены с соответствующими двумя выходами ПЗУ.