Последовательность максимальной длины

Последовательность максимальной длины ( MLS ) — это тип псевдослучайной двоичной последовательности .

Они представляют собой битовые последовательности, генерируемые с использованием регистров сдвига с максимальной линейной обратной связью , и называются так потому, что являются периодическими и воспроизводят каждую двоичную последовательность (кроме нулевого вектора), которая может быть представлена сдвиговыми регистрами (т. е. для регистров длины m они создают последовательность длины 2 ^м − 1). MLS также иногда называют n-последовательностью или m-последовательностью . MLS спектрально плоские , за исключением почти нулевого члена постоянного тока.

Эти последовательности могут быть представлены как коэффициенты неприводимых многочленов в кольце полиномов над Z/2Z .

Практическое применение MLS включает измерение импульсных характеристик помещения (например, реверберации или времени прихода от буксируемых источников в океане). ^[1]). Они также используются в качестве основы для получения псевдослучайных последовательностей в цифровых системах связи, которые используют расширенного спектра с прямой последовательностью и скачкообразной перестройкой частоты системы передачи , а также для эффективного планирования некоторых с фМРТ . экспериментов ^[2]

Поколение

MLS генерируются с использованием максимальных регистров сдвига с линейной обратной связью . MLS-генерирующая система со сдвиговым регистром длиной 4 показана на рис. 1. Ее можно выразить с помощью следующего рекурсивного соотношения:

{\begin{cases}a_{3}[n+1]=a_{0}[n]+a_{1}[n]\\a_{2}[n+1]=a_{3}[n]\\a_{1}[n+1]=a_{2}[n]\\a_{0}[n+1]=a_{1}[n]\\\end{cases}}

где n - индекс времени и $+$ представляет собой сложение по модулю 2 . Для значений битов 0 = ЛОЖЬ или 1 = ИСТИНА это эквивалентно операции XOR.

Поскольку MLS является периодическим, а сдвиговые регистры циклически перебирают все возможные двоичные значения (за исключением нулевого вектора), регистры могут быть инициализированы в любом состоянии, за исключением нулевого вектора.

Полиномиальная интерпретация

Полином . по GF(2) может быть связан с регистром сдвига с линейной обратной связью Он имеет степень длины сдвигового регистра и имеет коэффициенты, равные 0 или 1, соответствующие отводам регистра, которые подают сигнал на логический элемент xor . Например, полином, соответствующий рисунку 1, равен $x^{4}+x+1$ .

Необходимым и достаточным условием для того, чтобы последовательность, сгенерированная LFSR, была максимальной длины, является то, что соответствующий ей полином является примитивным . ^[3]

Выполнение

MLS недорого реализовать в аппаратном или программном обеспечении, а регистры сдвига с обратной связью относительно низкого порядка могут генерировать длинные последовательности; последовательность, сгенерированная с использованием сдвигового регистра длиной 20, равна 2 ²⁰ − Длина 1 сэмпла (1 048 575 семплов).

Свойства последовательностей максимальной длины

MLS обладают следующими свойствами, сформулированными Соломоном Голомбом . ^[4]

Балансовое свойство

Встречаемость 0 и 1 в последовательности должна быть примерно одинаковой. Точнее, в последовательности максимальной длины длины $2^{n}-1$ есть $2^{n-1}$ те и $2^{n-1}-1$ нули. Количество единиц равно количеству нулей плюс один, поскольку состояние, содержащее только нули, возникнуть не может.

Запустить свойство

«Прогон» представляет собой подпоследовательность последовательных «1» или последовательных «0» в соответствующем MLS. Количество прогонов — это количество таких подпоследовательностей. ^{[ нечеткий ]}

Из всех «серий» (состоящих из «1» или «0») в последовательности:

Половина прогонов имеет длину 1.
Четверть трасс имеют длину 2.
Одна восьмая часть пробега имеет длину 3.
... и т. д. ...

Свойство корреляции

Круговая автокорреляция MLS представляет собой Кронекера . дельта -функцию ^[5]^[6] (со смещением постоянного тока и выдержкой времени, в зависимости от реализации). Для соглашения ±1, т. е. присваивается значение бита 1. $s=+1$ и значение бита 0 $s=-1$ , сопоставляя XOR с отрицательным значением произведения:

$R(n)={\frac {1}{N}}\sum _{m=1}^{N}s[m]\,s^{*}[m+n]_{N}={\begin{cases}1&{\text{if }}n=0,\\-{\frac {1}{N}}&{\text{if }}0<n<N.\end{cases}}$

где $s^{*}$ представляет собой комплексно-сопряженное и $[m+n]_{N}$ представляет собой круговой сдвиг .

Линейная автокорреляция MLS приближается к дельте Кронекера.

Извлечение импульсных откликов

Если импульсная характеристика системы с линейным инвариантом времени (LTI) должна быть измерена с использованием MLS, ответ может быть извлечен из измеренного выходного сигнала системы y [ n ] путем взятия его круговой взаимной корреляции с MLS. Это связано с тем, что автокорреляция MLS равна 1 для нулевой задержки и почти равна нулю (-1/ N , где N — длина последовательности) для всех остальных задержек; другими словами, можно сказать, что автокорреляция MLS приближается к единичной импульсной функции по мере увеличения длины MLS.

Если импульсная характеристика системы равна h [ n ], а MLS равна s [ n ], то

y[n]=(h*s)[n].\,

Принимая взаимную корреляцию по s [ n ] обеих сторон,

{\phi }_{sy}=h[n]*{\phi }_{ss}\,

и предполагая, что φ _ss — импульс (справедливо для длинных последовательностей)

h[n]={\phi }_{sy}.\,

Для этой цели можно использовать любой сигнал с импульсной автокорреляцией, но сигналы с высоким пик-фактором , такие как сам импульс, создают импульсные характеристики с плохим соотношением сигнал/шум . Принято считать, что MLS в этом случае будет идеальным сигналом, поскольку он состоит только из полномасштабных значений, а его цифровой пик-фактор составляет минимум 0 дБ. ^[7]^[8] Однако после аналоговой реконструкции резкие разрывы сигнала создают сильные межвыборочные пики, ухудшающие коэффициент амплитуды на 4–8 дБ или более, увеличиваясь с длиной сигнала, что делает его хуже, чем синусоидальная развертка. ^[9] Другие сигналы были разработаны с минимальным пик-фактором, хотя неизвестно, можно ли его улучшить выше 3 дБ. ^[10]

Связь с преобразованием Адамара

Кон и Лемпель ^[11] показал связь MLS с преобразованием Адамара . Это соотношение позволяет корреляцию вычислять MLS с помощью быстрого алгоритма, аналогичного БПФ .

См. также

Ссылки

Голомб, Соломон В.; Гуан Гун (2005). Проектирование сигналов для хорошей корреляции: для беспроводной связи, криптографии и радаров . Издательство Кембриджского университета . ISBN 978-0-521-82104-9 .

^ Гемба, Кей Л.; Васкес, Эриберто Х.; Фиалковски, Джозеф; Эдельманн, Джеффри Ф.; Дзечух, Мэтью А.; Ходжкисс, Уильям С. (октябрь 2021 г.). «Сравнение производительности m-последовательностей и линейных частотно-модулированных разверток для оценки времени прохождения с движущимся источником» . Журнал Акустического общества Америки . 150 (4): 2613–2623. Бибкод : 2021ASAJ..150.2613G . дои : 10.1121/10.0006656 . ПМИД 34717519 . S2CID 240355915 .
^ Buracas GT, генеральный директор Boynton (июль 2002 г.). «Эффективное планирование событийно-связанных экспериментов с использованием МРТ с использованием М-последовательностей». НейроИмидж . 16 (3, часть 1): 801–13. дои : 10.1006/нимг.2002.1116 . ПМИД 12169264 . S2CID 7433120 .
^ «Регистры сдвига с линейной обратной связью - реализация, свойства M-последовательности, таблицы обратной связи» [1] , New Wave Instruments (NW), дата обращения 2013.12.03.
^ Голомб, Соломон В. (1967). Последовательности сдвиговых регистров . Холден-Дэй. ISBN 0-89412-048-4 .
^ Якобсен, Финн; Юл, Питер Моллер (4 июня 2013 г.). Основы общей линейной акустики . Джон Уайли и сыновья. ISBN 978-1118636176 . Последовательность максимальной длины — это двоичная последовательность, круговая автокорреляция которой (за исключением небольшой ошибки постоянного тока) является дельта-функцией.
^ Сарвате, Д.В.; Персли, МБ (1 мая 1980 г.). «Свойства кросскорреляции псевдослучайных и родственных последовательностей». Труды IEEE . 68 (5): 593–619. дои : 10.1109/PROC.1980.11697 . ISSN 0018-9219 . S2CID 6179951 .
^ «Небольшое руководство по MLS (последовательность максимальной длины) | dspGuru.com» . dspguru.com . Проверено 19 мая 2016 г. его среднеквадратичное и пиковое значения равны X, что делает его пик-фактор (пик/RMS) равным 1, самому низкому значению, которое он может получить.
^ «Другие методы электроакустических измерений» . www.clear.rice.edu . Проверено 19 мая 2016 г. Пик-фактор для MLS очень близок к 1, поэтому имеет смысл использовать этот тип входного сигнала, когда для наших измерений требуется высокое соотношение сигнал/шум.
^ Чан, Ян Х. «Синусоидальные импульсы с качающейся частотой для измерения импульсного отклика» (PDF) . thinksrs.com . Проверено 19 мая 2016 г.
^ Фризе, М. (1 октября 1997 г.). «Многотональные сигналы с низким коэффициентом амплитуды» (PDF) . Транзакции IEEE по коммуникациям . 45 (10): 1338–1344. дои : 10.1109/26.634697 . ISSN 0090-6778 .
^ Кон, М.; Лемпель, А. (январь 1977 г.). «О быстром преобразовании M-последовательности». IEEE Транс. Инф. Теория . 23 (1): 135–7. дои : 10.1109/TIT.1977.1055666 .

Внешние ссылки

Бристоу-Джонсон, Роберт. «Небольшой урок MLS» . — Краткое онлайн-руководство, описывающее, как MLS используется для получения импульсной характеристики линейной нестационарной системы . Также описывается, как нелинейности в системе могут проявляться в виде ложных всплесков видимой импульсной характеристики.
Привет, Йенс. «Измерение импульсной характеристики с помощью MLS» (PDF) . - Документ, описывающий создание MLS. Содержит C-код для генерации MLS с использованием до 18-отводных LFSR и соответствующего преобразования Адамара для извлечения импульсного отклика.
Шефер, Магнус (октябрь 2012 г.). «Аахенская база данных импульсных реакций» . Институт систем связи и обработки данных, RWTH Ахенского университета. В1.4. База данных (бинауральных) импульсных характеристик комнаты, созданная с помощью последовательностей максимальной длины.
«Эффективные регистры сдвига, счетчики LFSR и генераторы длинных псевдослучайных последовательностей — устаревшие» (PDF) . Ксилинкс. Июль 1996 г. XAPP052 v1.1. — Реализация lfsr в FPGA включает в себя список отводов от 3 до 168 бит.

[1] Гемба, Кей Л.; Васкес, Эриберто Х.; Фиалковски, Джозеф; Эдельманн, Джеффри Ф.; Дзечух, Мэтью А.; Ходжкисс, Уильям С. (октябрь 2021 г.). «Сравнение производительности m-последовательностей и линейных частотно-модулированных разверток для оценки времени прохождения с движущимся источником» . Журнал Акустического общества Америки . 150 (4): 2613–2623. Бибкод : 2021ASAJ..150.2613G . дои : 10.1121/10.0006656 . ПМИД 34717519 . S2CID 240355915 .

[buracas-2] Buracas GT, генеральный директор Boynton (июль 2002 г.). «Эффективное планирование событийно-связанных экспериментов с использованием МРТ с использованием М-последовательностей». НейроИмидж . 16 (3, часть 1): 801–13. дои : 10.1006/нимг.2002.1116 . ПМИД 12169264 . S2CID 7433120 .

[3] «Регистры сдвига с линейной обратной связью - реализация, свойства M-последовательности, таблицы обратной связи» [1] , New Wave Instruments (NW), дата обращения 2013.12.03.

[golumb-4] Голомб, Соломон В. (1967). Последовательности сдвиговых регистров . Холден-Дэй. ISBN 0-89412-048-4 .

[5] Якобсен, Финн; Юл, Питер Моллер (4 июня 2013 г.). Основы общей линейной акустики . Джон Уайли и сыновья. ISBN 978-1118636176 . Последовательность максимальной длины — это двоичная последовательность, круговая автокорреляция которой (за исключением небольшой ошибки постоянного тока) является дельта-функцией.

[6] Сарвате, Д.В.; Персли, МБ (1 мая 1980 г.). «Свойства кросскорреляции псевдослучайных и родственных последовательностей». Труды IEEE . 68 (5): 593–619. дои : 10.1109/PROC.1980.11697 . ISSN 0018-9219 . S2CID 6179951 .

[7] «Небольшое руководство по MLS (последовательность максимальной длины) | dspGuru.com» . dspguru.com . Проверено 19 мая 2016 г. его среднеквадратичное и пиковое значения равны X, что делает его пик-фактор (пик/RMS) равным 1, самому низкому значению, которое он может получить.

[8] «Другие методы электроакустических измерений» . www.clear.rice.edu . Проверено 19 мая 2016 г. Пик-фактор для MLS очень близок к 1, поэтому имеет смысл использовать этот тип входного сигнала, когда для наших измерений требуется высокое соотношение сигнал/шум.

[9] Чан, Ян Х. «Синусоидальные импульсы с качающейся частотой для измерения импульсного отклика» (PDF) . thinksrs.com . Проверено 19 мая 2016 г.

[10] Фризе, М. (1 октября 1997 г.). «Многотональные сигналы с низким коэффициентом амплитуды» (PDF) . Транзакции IEEE по коммуникациям . 45 (10): 1338–1344. дои : 10.1109/26.634697 . ISSN 0090-6778 .

[cohn-11] Кон, М.; Лемпель, А. (январь 1977 г.). «О быстром преобразовании M-последовательности». IEEE Транс. Инф. Теория . 23 (1): 135–7. дои : 10.1109/TIT.1977.1055666 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]