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

Type of pseudorandom binary sequence

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

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

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

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

Поколение

_{Рисунок 1} : Следующее значение регистра 3 в регистре сдвига с обратной связью длиной 4 определяется суммой по _{модулю 2} 0 и 1 .

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

${\displaystyle {\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. ${\displaystyle +}$

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

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

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

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

Выполнение

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}}}$

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

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

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

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

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

${\displaystyle y[n]=(h*s)[n].\,}$

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

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

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

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

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

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

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

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

• Код Баркера
• Дополнительные последовательности
• Федеральный стандарт 1037C
• Частотная характеристика
• Золотой код
• Импульсивный ответ
• Полиномиальное кольцо

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

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

1. Гемба, Кей Л.; Васкес, Эриберто Х.; Фиалковски, Джозеф; Эдельманн, Джеффри Ф.; Дзечух, Мэтью А.; Ходжкисс, Уильям С. (октябрь 2021 г.). «Сравнение производительности m-последовательностей и линейной частотно-модулированной развертки для оценки времени прохождения с движущимся источником». Журнал Акустического общества Америки . 150 (4): 2613–2623. Бибкод : 2021ASAJ..150.2613G. дои : 10.1121/10.0006656. PMID  34717519. S2CID  240355915.
2. Buracas GT, Boynton GM (июль 2002 г.). «Эффективное планирование событийно-связанных экспериментов по фМРТ с использованием М-последовательностей». НейроИмидж . 16 (3, часть 1): 801–13. дои : 10.1006/нимг.2002.1116. PMID  12169264. S2CID  7433120.
3. «Регистры сдвига с линейной обратной связью - реализация, свойства M-последовательности, таблицы обратной связи» [1], New Wave Instruments (NW), дата обращения 2013.12.03.
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.
11. Кон, М.; Лемпель, А. (январь 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 бит.