- Для дополнительных последовательностей в биологии см комплементарность (молекулярная биология) .
В прикладной математике дополнительные последовательности ( CS ) представляют собой пары последовательностей с полезным свойством, заключающимся в том, что их противофазные коэффициенты апериодической автокорреляции равны нулю. Бинарные комплементарные последовательности были впервые введены Марселем Дж. Э. Голеем в 1949 г. В 1961–1962 гг. Голей дал несколько методов построения последовательностей длиной 2 N и привел примеры комплементарных последовательностей длиной 10 и 26. В 1974 Р. Дж. Турин дал метод построения последовательностей длины mn из последовательностей длин m и n, что позволяет строить последовательности любой длины вида 2 N10 К 26 Мес .
Позже теория комплементарных последовательностей была обобщена другими авторами на многофазные комплементарные последовательности, многоуровневые комплементарные последовательности и произвольные сложные комплементарные последовательности. Также были рассмотрены дополнительные наборы ; они могут содержать более двух последовательностей.
Определение
Пусть ( a 0 , a 1 , ..., a N - 1 ) и ( b 0 , b 1 , ..., b N - 1 ) - пара биполярных последовательностей, что означает, что a ( k ) и b ( k ) имеют значения +1 или -1. Пусть апериодическая автокорреляционная функция последовательности x определяется выражением
Тогда пара последовательностей a и b комплементарна, если:
для 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).
Свойства дополнительных пар последовательностей
- Комплементарные последовательности имеют комплементарные спектры. Поскольку автокорреляционная функция и спектры мощности образуют пару Фурье, дополнительные последовательности также имеют дополнительные спектры. Но поскольку преобразование Фурье дельта-функции является константой, мы можем написать
- где C S - постоянная.
- S a и S b определяются как квадрат величины преобразования Фурье последовательностей. Преобразование Фурье может быть прямым ДПФ последовательностей, оно может быть ДПФ дополненных нулями последовательностей или может быть непрерывным преобразованием Фурье последовательностей, которое эквивалентно преобразованию Z для Z = e j ω .
- Спектры CS ограничены сверху. Поскольку S a и S b неотрицательные значения, мы можем написать
- также
- Если любая из последовательностей пары CS инвертируется (умножается на -1), они остаются комплементарными. В более общем смысле, если любая из последовательностей умножается на e j φ, они остаются дополнительными;
- Если любая из последовательностей инвертирована, они остаются комплементарными;
- Если какая-либо из последовательностей задерживается, они остаются комплементарными;
- Если последовательности меняются местами, они остаются комплементарными;
- Если обе последовательности умножаются на одну и ту же константу (действительную или комплексную), они остаются дополнительными;
- Если обе последовательности прореживаются во времени на K, они остаются комплементарными. Точнее, если из дополнительной пары ( a ( k ), b ( k )) мы формируем новую пару ( a ( Nk ), b ( Nk )) с отброшенными пропущенными выборками, тогда новые последовательности являются дополнительными.
- Если чередующиеся биты обеих последовательностей инвертируются, они остаются комплементарными. В общем, для произвольных сложных последовательностей, если обе последовательности умножаются на e j π kn / N (где k - константа, а n - временной индекс), они остаются дополнительными;
- Новая пара дополнительных последовательностей может быть сформирована как [ a b ] и [ a - b ], где [..] обозначает конкатенацию, а a и b - пара CS;
- Новая пара последовательностей может быть сформирована как { a b } и { a - b }, где {..} обозначает чередование последовательностей.
- Новая пара последовательностей может быть сформирована как a + b и a - b .
Голая пара
Дополнительная пара a , b может быть закодирована как полиномы A ( z ) = a (0) + a (1) z + ... + a ( N - 1) z N -1 и аналогично для B ( z ). Свойство дополнительности последовательностей эквивалентно условию
для всех z на единичной окружности, то есть | z | = 1. Если это так, то A и B образуют пару многочленов Голея . Примеры включают полиномы Шапиро , которые дают дополнительные последовательности длины, равной степени двойки .
Применение дополнительных последовательностей
- Мультищелевая спектрометрия
- Ультразвуковые измерения
- Акустические измерения
- сжатие радиолокационных импульсов
- Сети Wi-Fi ,
- Беспроводные сети 3G CDMA
- Системы связи OFDM
- Системы обнаружения колес поездов [1] [2]
- Неразрушающие испытания (NDT)
- Связь
- маски с кодированной апертурой разработаны с использованием двумерного обобщения дополнительных последовательностей.
Смотрите также
- Двоичный код Голея ( код с исправлением ошибок )
- Золотые последовательности
- Последовательности Касами
- Полифазная последовательность
- Псевдослучайные двоичные последовательности (также называемые последовательностями максимальной длины или M-последовательностями)
- Тернарный код Голея ( код с исправлением ошибок )
- Последовательности Уолша-Адамара
- Последовательность Задова – Чу
Рекомендации
- ^ Донато, PG; Ureña, J .; Mazo, M .; Альварес, Ф. "Обнаружение колес поезда без электронного оборудования вблизи железнодорожной линии". 2004. doi : 10.1109 / IVS.2004.1336500
- ^ JJ Гарсия; А. Эрнандес; Х. Уренья; JC Garcia; М. Мазо; JL Lazaro; MC Perez; Ф. Альварес. «Недорогое обнаружение препятствий для интеллектуальной железнодорожной инфраструктуры» . 2004 г.
- Голай, Марсель JE (1949). «Мультищелевая спектроскопия». J. Opt. Soc. Am . 39 (6): 437–444. DOI : 10.1364 / JOSA.39.000437 . PMID 18152021 .
- Голай, Марсель Дж. Э. (апрель 1961 г.). «Дополнительная серия». IRE Trans. Инф. Теория . 7 (2): 82–87. DOI : 10.1109 / TIT.1961.1057620 .
- Голай, Марсель JE (1962). «Примечание к« Дополнительной серии » ». Proc. IRE . 50 : 84. DOI : 10.1109 / JRPROC.1962.288278 .
- Турин, Р.Дж. (1974). «Матрицы Адамара, единицы Баумерта-Холла, четырехсимвольные последовательности, сжатие импульсов и кодирование поверхностных волн». J. Comb. ТЕОРИЯ . 16 (3): 313–333. DOI : 10.1016 / 0097-3165 (74) 90056-9 .
- Борвейн, Питер (2002). Вычислительные экскурсии по анализу и теории чисел . Springer. С. 110–9. ISBN 978-0-387-95444-8.
- Донато, PG; Ureña, J .; Mazo, M .; De Marziani, C .; Очоа, А. (2006). «Разработка и обработка сигналов матрицы магнитных датчиков для обнаружения колеса поезда». Датчики и исполнительные механизмы A: Физические . 132 (2): 516–525. DOI : 10.1016 / j.sna.2006.02.043 .