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

Описание патента на изобретение RU2694439C1

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

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

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

В работе (Кренгель Е.И., Иванов П.В. Новые троичные последовательности с двумя ненулевыми боковыми лепестками периодической автокорреляционной функции и пик-фактором, близким к единице. - Сборник докладов 18-й международной конференции «Цифровая обработка сигналов и ее применение (DSPA-2016)», 30 марта - 1 апреля 2016, Москва, стр. 183-187) на основе ПИТП длины N=2(pm+1) и ПИТП длины 2N=4(pm+1), pm-1≡4 (mod 4) были построены новые троичные последовательности длины 8(pm+1) с 8-ю нулями и нулевыми боковыми лепестками ПАКФ во всех точках, кроме N и 3N, в которых ПАКФ принимает значение -4pm. Нулевая зона автокорреляции этих последовательностей равна 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(pm+1) и НПИДП длины 4(pm+1) двоичных последовательностей длины 8(pm+1) равна 6(pm+1), что составляет 0,75 длины последовательности, ограничивающей сверху величину линейной сложности последовательности.

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

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

где

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

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

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

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

где

есть ПИТП длины 4(pm+1) с пиковыми значениями ACF(0)=-ACF(2T)=4pm и числом нулевых элементов 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(pm+1) с 4-мя нулями. Вычисление символов НПИДП производится посредством генератора m-последовательности (ГМП) над GF(pm) длины pn-1, выход которого соединен с входом блока вычисления функции ψ(x). Основная сложность реализации генератора НПИДП связана с вычислением дискретного логарифма х по основанию примитивного элемента β. Поэтому наибольшее быстродействие достигается при использовании таблиц, содержащих логарифмы всех pm элементов из GF(pm). Объем таблиц в этом случае максимален и составляет pm слов длиной приблизительно бит, что почти в раз превышает длину генерируемой двоичной последовательности. Здесь есть min , т.е.есть операция округления числа и к большему.

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

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

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

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

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

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

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

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

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

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

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

Похожие патенты RU2694439C1

название год авторы номер документа
Генератор периодических псевдослучайных двоичных последовательностей сложной структуры 2018
  • Кренгель Евгений Ильич
  • Барков Илья Викторович
  • Иванов Павел Викторович
RU2690765C1
Генератор периодических идеальных троичных последовательностей 2017
  • Кренгель Евгений Ильич
RU2665290C1
СПОСОБ ПЕРЕДАЧИ ИНФОРМАЦИИ С ИСПОЛЬЗОВАНИЕМ ЗАМЕЩАЮЩЕГО ЛОГИЧЕСКОГО ТРОИЧНОГО ПОМЕХОУСТОЙЧИВОГО КОДА 2019
  • Кукушкин Сергей Сергеевич
  • Есаулов Сергей Константинович
  • Светлов Геннадий Валентинович
RU2724794C1
КОДИРОВАНИЕ МНОЖЕСТВЕННОГО ДОСТУПА С ИСПОЛЬЗОВАНИЕМ СВЕРНУТЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЛЯ СИСТЕМ ПОДВИЖНОЙ РАДИОСВЯЗИ 1995
  • Грегори Боттомли
  • Пол В. Дент
RU2160508C2
Цифровой многоканальный коррелятор периодических фазоманипулированных сигналов 1978
  • Бритин Сергей Николаевич
  • Ипатов Валерий Павлович
  • Коломенский Юрий Александрович
  • Корниевский Владимир Иванович
SU734716A1
КОДИРОВАНИЕ МНОЖЕСТВЕННОГО ДОСТУПА С ИСПОЛЬЗОВАНИЕМ СВЕРНУТЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЛЯ СИСТЕМ ПОДВИЖНОЙ РАДИОСВЯЗИ 1995
  • Боттомли Грегори Е.
  • Дент Пол В.
RU2242819C2
СПОСОБ АКУСТИЧЕСКОГО КАРОТАЖА 1990
  • Сиротенко П.Т.
  • Роман В.И.
RU2012018C1
СПОСОБ ПОВЫШЕНИЯ ПОМЕХОЗАЩИЩЕННОСТИ СИГНАЛОВ СИНХРОНИЗАЦИИ 2019
  • Кукушкин Сергей Сергеевич
  • Кузнецов Валерий Иванович
  • Оберемко Алексей Геннадьевич
  • Ногинов Денис Викторович
RU2757975C2
СПОСОБ ПЕРЕДАЧИ ИНФОРМАЦИИ В СИСТЕМАХ С КОДОВЫМ РАЗДЕЛЕНИЕМ КАНАЛОВ И УСТРОЙСТВО ДЛЯ ЕГО ОСУЩЕСТВЛЕНИЯ 2001
  • Косякин С.И.
  • Москвитин И.А.
  • Смирнов А.А.
RU2234191C2
СПОСОБ АКУСТИЧЕСКОГО КАРОТАЖА 1990
  • Сиротенко П.Т.
  • Роман В.И.
  • Шпортюк Г.А.
RU2012019C1

Иллюстрации к изобретению RU 2 694 439 C1

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

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

Формула изобретения RU 2 694 439 C1

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

RU 2 694 439 C1

Авторы

Кренгель Евгений Ильич

Барков Илья Викторович

Иванов Павел Викторович

Даты

2019-07-15Публикация

2018-07-27Подача