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

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

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

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

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

Поколение

Рисунок 1: Следующее значение регистра на ₃ в регистр сдвига с обратными связями длиной 4 определяется суммой по модулю 2 в ₀ и в ₁ .

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 {case}}}

где n - временной индекс и представляет собой сложение по модулю 2 . Для битовых значений 0 = FALSE или 1 = TRUE это эквивалентно операции XOR. ${\ displaystyle +}$

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

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

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

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

Выполнение

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

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

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

Баланс собственности

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

Выполнить свойство

«Прогон» - это подпоследовательность из последовательных «1» или последовательных «0» в пределах рассматриваемого MLS. Количество прогонов - это количество таких подпоследовательностей.

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

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

Корреляционное свойство

Круговая автокорреляция MLS - это дельта- функция Кронекера (со смещением постоянного тока и временной задержкой, в зависимости от реализации). Для соглашения ± 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 {case} 1 & {\ text {if}} n = 0, \\ - {\ frac {1} {N}} & {\ text {if}} 0 <n <N. \ end {cases }}}$

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

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

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

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

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

{\ Displaystyle у [п] = (ч * з) [п]. \,}

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

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

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

{\ Displaystyle ч [п] = {\ phi} _ {sy}. \,}

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

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

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

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

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

Бристоу-Джонсон, Роберт. "Небольшой учебник MLS" . - Краткое интерактивное руководство, описывающее, как MLS используется для получения импульсной характеристики линейной системы, не зависящей от времени . Также описывает, как нелинейности в системе могут проявляться как ложные выбросы в кажущейся импульсной характеристике.
Привет, Йенс. «Измерение импульсной характеристики с помощью MLS» (PDF) . - Документ, описывающий генерацию MLS. Содержит C-код для генерации MLS с использованием до 18-ти ответвлений LFSR и соответствующего преобразования Адамара для извлечения импульсной характеристики.
Керр, Уэсли; Друкер, Дэниел. «Создание M-последовательностей» . Лаборатория Джеффри Агирре . Пенсильванский университет.
«Регистры сдвига с линейной обратной связью» . Инструменты новой волны. 2005 г. - Свойства последовательностей максимальной длины и подробные таблицы обратной связи для максимальной длины от 7 до 16 777 215 (от 3 до 24 этапов) и частичные таблицы для длин до 4 294 967 295 (от 25 до 32 этапов).
Шефер, Магнус (октябрь 2012 г.). «База данных импульсных откликов Аахена» . Институт систем связи и обработки данных, RWTH Aachen University. V1.4. База данных импульсных откликов (бинауральных) комнат, созданная с помощью последовательностей максимальной длины.
«Эффективные регистры сдвига, счетчики LFSR и генераторы длинных псевдослучайных последовательностей - устарело» (PDF) . Xilinx. Июль 1996 г. XAPP052 v1.1. - Реализация lfsr в ПЛИС включает в себя список ответвлений от 3 до 168 бит

Languages

In other projects