Дополнительные последовательности - Complementary sequences

Дополнительные последовательности в биологии см. комплементарность (молекулярная биология).

В прикладной математике комплементарные последовательности (CS) являются парами последовательности с тем полезным свойством, что их противофазные апериодические автокорреляция Сумма коэффициентов равна нулю. Бинарные дополнительные последовательности были впервые введены Марсель Дж. Э. Голей в 1949 г. В 1961–1962 гг. Голей дал несколько методов построения последовательностей длины 2^N и привел примеры комплементарных последовательностей длиной 10 и 26. В 1974 г. Р. Дж. Турин дал метод построения последовательностей длиной млн из последовательностей длин м и п что позволяет строить последовательности любой длины вида 2^N10^K26^M.

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

Определение

Позволять (а₀, а₁, ..., а_N − 1) и (б₀, б₁, ..., б_N − 1) - пара биполярных последовательностей, что означает, что а(k) и б(k) имеют значения +1 или -1. Пусть апериодический автокорреляционная функция последовательности Икс определяться

${displaystyle R_{x}(k)=sum _{j=0}^{N-k-1}x_{j}x_{j+k}.,}$

Тогда пара последовательностей а и б является дополнительным, если:

${displaystyle R_{a}(k)+R_{b}(k)=2N,,}$

за k = 0 и

${displaystyle R_{a}(k)+R_{b}(k)=0,,}$

за k = 1, ..., N − 1.

Или используя Дельта Кронекера мы можем написать:

${displaystyle R_{a}(k)+R_{b}(k)=2Ndelta (k),,}$

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

Примеры

• В качестве простейшего примера у нас есть последовательности длины 2: (+1, +1) и (+1, −1). Их автокорреляционные функции - это (2, 1) и (2, −1), которые в сумме дают (4, 0).
• В качестве следующего примера (последовательности длины 4) у нас есть (+1, +1, +1, -1) и (+1, +1, -1, +1). Их автокорреляционные функции - это (4, 1, 0, -1) и (4, -1, 0, 1), которые в сумме дают (8, 0, 0, 0).
• Один из примеров длины 8: (+1, +1, +1, -1, +1, +1, -1, +1) и (+1, +1, +1, -1, -1, -1 , +1, −1). Их автокорреляционные функции: (8, −1, 0, 3, 0, 1, 0, 1) и (8, 1, 0, −3, 0, −1, 0, −1).
• Пример длины 10, данный Голеем: (+1, +1, −1, +1, −1, +1, −1, −1, +1, +1) и (+1, +1, −1 , +1, +1, +1, +1, +1, -1, -1). Их автокорреляционные функции: (10, −3, 0, −1, 0, 1, −2, −1, 2, 1) и (10, 3, 0, 1, 0, −1, 2, 1, −2 , −1).

Свойства дополнительных пар последовательностей

• Дополнительный последовательности имеют дополнительные спектры. Поскольку автокорреляционная функция и спектры мощности образуют пару Фурье, дополнительные последовательности также имеют дополнительные спектры. Но поскольку преобразование Фурье дельта-функции является константой, мы можем написать

${displaystyle S_{a}+S_{b}=C_{S},}$

куда C_S является константой.

S_а и S_б определяются как квадрат величины преобразование Фурье последовательностей. Преобразование Фурье может быть прямым ДПФ последовательностей, оно может быть ДПФ дополненных нулями последовательностей или может быть непрерывным преобразованием Фурье последовательностей, которое эквивалентно Z преобразование за Z = е^jω.

• Спектры CS ограничены сверху. В качестве S_а и S_б неотрицательные значения, мы можем написать

${displaystyle S_{a}=C_{S}-S_{b}<C_{S},}$

также

${displaystyle S_{b}<C_{S}.}$

• Если любая из последовательностей пары CS инвертируется (умножается на -1), они остаются дополнительными. В более общем смысле, если любую из последовательностей умножить на е^jφ они остаются взаимодополняющими;
• Если любая из последовательностей инвертирована, они остаются комплементарными;
• Если какая-либо из последовательностей задерживается, они остаются комплементарными;
• Если последовательности меняются местами, они остаются дополнительными;
• Если обе последовательности умножаются на одну и ту же константу (действительную или комплексную), они остаются дополнительными;
• Если обе последовательности прореживаются во времени на K они остаются взаимодополняющими. Точнее, если из дополнительной пары (а(k), б(k)) формируем новую пару (а(Nk), б(Nk)) с отброшенными пропущенными сэмплами новые последовательности дополняют друг друга.
• Если чередующиеся биты обеих последовательностей инвертируются, они остаются дополнительными. В общем случае для произвольных сложных последовательностей, если обе последовательности умножаются на е^jπкн/N (куда k является константой и п - временной индекс) они остаются дополнительными;
• Новая пара дополнительных последовательностей может быть сформирована как [а б] и [а −б], где [..] означает конкатенацию, а а и б пара CS;
• Новую пару последовательностей можно сформировать как {а б} и {а −б} где {..} означает чередование последовательностей.
• Новую пару последовательностей можно сформировать как а + б и а − б.

Голая пара

Дополнительная пара а, б могут быть закодированы как полиномы А(z) = а(0) + а(1)z + ... + а(N − 1)z^N−1 и аналогично для B(z). Свойство комплементарности последовательностей эквивалентно условию

${displaystyle vert A(z)vert ^{2}+vert B(z)vert ^{2}=2N,}$

для всех z на единичной окружности, то есть |z| = 1. Если так, А и B сформировать Голая пара многочленов. Примеры включают Полиномы Шапиро, которые приводят к дополнительным последовательностям длины a сила двух.

Применение дополнительных последовательностей

• Мультищелевая спектрометрия
• Ультразвуковые измерения
• Акустические измерения
• радар сжатие импульса
• Вай фай сети,
• 3G CDMA беспроводные сети
• OFDM системы связи
• Системы обнаружения колес поездов^[1][2]
• Неразрушающие испытания (NDT)
• Связь
• кодированная апертура маски разработаны с использованием двумерного обобщения дополнительных последовательностей.

Смотрите также

• Двоичный код Голея (Код исправления ошибок )
• Золотые последовательности
• Последовательности Касами
• Полифазная последовательность
• Псевдослучайные двоичные последовательности (также называемый последовательности максимальной длины или M-последовательности)
• Тернарный код Голея (Код исправления ошибок )
• Последовательности Уолша-Адамара
• Последовательность Задова – Чу

Рекомендации

1. Донато, П.Г .; Ureña, J .; Mazo, M .; Альварес, Ф. "Обнаружение колес поезда без электронного оборудования вблизи железнодорожной линии". 2004.Дои: 10.1109 / IVS.2004.1336500
2. J.J. Гарсия; А. Эрнандес; Х. Уренья; Дж. К. Гарсия; М. Мазо; J.L. Lazaro; M.C. Перес; Ф. Альварес.«Недорогое обнаружение препятствий для интеллектуальной железнодорожной инфраструктуры».2004.

• Голай, Марсель Ж. (1949). «Мультищелевая спектроскопия». J. Opt. Soc. Являюсь. 39 (6): 437–444. Дои:10.1364 / JOSA.39.000437. PMID  18152021.
• Голай, Марсель Дж. Э. (апрель 1961 г.). «Дополнительная серия». IRE Trans. Инф. Теория. 7 (2): 82–87. Дои:10.1109 / TIT.1961.1057620.
• Голай, Марсель J.E. (1962). «Примечание о» Дополнительная серия"". Proc. IRE. 50: 84. Дои:10.1109 / JRPROC.1962.288278.
• Турин, Р.Дж. (1974). «Матрицы Адамара, единицы Баумерта-Холла, четырехсимвольные последовательности, сжатие импульсов и кодирование поверхностных волн». J. Comb. Теория А. 16 (3): 313–333. Дои:10.1016/0097-3165(74)90056-9.
• Борвейн, Питер (2002). Вычислительные экскурсии по анализу и теории чисел. Springer. С. 110–9. ISBN  978-0-387-95444-8.
• Донато, П.Г .; Ureña, J .; Mazo, M .; De Marziani, C .; Очоа, А. (2006). «Разработка и обработка сигналов матрицы магнитных датчиков для обнаружения колеса поезда». Датчики и исполнительные механизмы A: физические. 132 (2): 516–525. Дои:10.1016 / j.sna.2006.02.043.