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

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

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

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

Определение

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

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

за k = 0 и

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

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

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

Примеры

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

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

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

Голая пара

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

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

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

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

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

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

  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.