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

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

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

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

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

Поколение [ править ]

Рисунок 1: Следующее значение регистра на ₃ в регистр сдвига с обратными связями длиной 4 определяется суммой по модулю 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 = FALSE или 1 = TRUE это эквивалентно операции XOR. $+$

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

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

Многочлен над GF (2) может быть связано с регистром сдвига с линейной обратной связью. Он имеет степень длины сдвигового регистра и коэффициенты 0 или 1, соответствующие отводам регистра, которые питают логический элемент xor . Например, полином, соответствующий рисунку 1, равен x ⁴ + 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 и битовое значение 0 , сопоставляя XOR с отрицательным результатом произведения: $s=+1$ $s=-1$

$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 в быстром алгоритме, подобном БПФ .

См. Также [ править ]

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

Ссылки [ править ]

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

^ Пудель, Хем Нараян; Робертсон, Уильям М. (2018-10-15). «Многослойный диэлектрический отражатель максимальной длины последовательности» . OSA Continuum . 1 (2): 358–372. DOI : 10.1364 / OSAC.1.000358 . ISSN 2578-7519 .
^ Buracas GT, Бойнтон GM (июль 2002). «Эффективный дизайн экспериментов, связанных с событием, фМРТ с использованием M-последовательностей». NeuroImage . 16 (3 Pt 1): 801–13. DOI : 10.1006 / nimg.2002.1116 . PMID 12169264 .
^ «Регистры сдвига с линейной обратной связью - реализация, свойства M-последовательности, таблицы обратной связи» [1] , New Wave Instruments (NW), дата обращения 2013.12.03.
^ Голомб, Соломон В. (1967). Последовательности регистров сдвига . Холден-Дэй. ISBN 0-89412-048-4.
^ Якобсен, Финн; Джул, Питер Моллер (04.06.2013). Основы общей линейной акустики . Джон Вили и сыновья. ISBN 978-1118636176. Последовательность максимальной длины - это двоичная последовательность, круговая автокорреляция которой (за исключением небольшой ошибки DC) является дельта-функцией.
^ Sarwate, DV; Персли, МБ (1980-05-01). «Кросс-корреляционные свойства псевдослучайных и родственных последовательностей». Труды IEEE . 68 (5): 593–619. DOI : 10,1109 / PROC.1980.11697 . ISSN 0018-9219 .
^ "Небольшое руководство по MLS (последовательность максимальной длины) | dspGuru.com" . dspguru.com . Проверено 19 мая 2016 . его среднеквадратичное и пиковое значения равны X, что делает его пик-фактор (пик / среднеквадратичное значение) равным 1, наименьшему из возможных.
^ "Другие методы электроакустических измерений" . www.clear.rice.edu . Проверено 19 мая 2016 . Коэффициент амплитуды для MLS очень близок к 1, поэтому имеет смысл использовать этот тип входного сигнала, когда нам требуется высокое отношение сигнал / шум для наших измерений.
^ Чан, Ян Х. "Синусоидальные чирпы с разверткой для измерения импульсной характеристики" (PDF) . thinksrs.com . Проверено 19 мая 2016 .
^ Фриз, М. (1997-10-01). «Многотональные сигналы с низким коэффициентом амплитуды» (PDF) . Транзакции IEEE по коммуникациям . 45 (10): 1338–1344. DOI : 10.1109 / 26.634697 . ISSN 0090-6778 .
^ Кон, М .; Лемпель, А. (январь 1977 г.). «О быстрых преобразованиях M-последовательностей». IEEE Trans. Инф. Теория . 23 (1): 135–7. DOI : 10.1109 / TIT.1977.1055666 .

Внешние ссылки [ править ]

Бристоу-Джонсон, Роберт. "Небольшой учебник 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 бит

[1] Пудель, Хем Нараян; Робертсон, Уильям М. (2018-10-15). «Многослойный диэлектрический отражатель максимальной длины последовательности» . OSA Continuum . 1 (2): 358–372. DOI : 10.1364 / OSAC.1.000358 . ISSN 2578-7519 .

[buracas-2] Buracas GT, Бойнтон GM (июль 2002). «Эффективный дизайн экспериментов, связанных с событием, фМРТ с использованием M-последовательностей». NeuroImage . 16 (3 Pt 1): 801–13. DOI : 10.1006 / nimg.2002.1116 . PMID 12169264 .

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

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

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

[6] Sarwate, DV; Персли, МБ (1980-05-01). «Кросс-корреляционные свойства псевдослучайных и родственных последовательностей». Труды IEEE . 68 (5): 593–619. DOI : 10,1109 / PROC.1980.11697 . ISSN 0018-9219 .

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

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

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

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

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

[1]