Введение

Тип псевдослучайной двоичной последовательности

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

Поколение

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

где n – индекс времени, а обозначает сложение по модулю 2. Для битовых значений 0 = ЛОЖЬ или 1 = ИСТИНА это эквивалентно операции XOR. Поскольку MLS являются периодическими, а регистры сдвига проходят через все возможные двоичные значения (за исключением нулевого вектора), регистры могут быть инициализированы в любое состояние, кроме нулевого вектора.

Интерпретация полиномов

Многочлен над GF(2) может быть сопоставлен с линейным регистром сдвига с обратной связью. Его степень равна длине регистра сдвига, а коэффициенты принимают значения 0 или 1, соответствующие точкам подключения регистра, подающим сигнал на элемент XOR. Например, многочлен, соответствующий рисунку 1, является [многочленом]. Необходимым и достаточным условием для того, чтобы последовательность, генерируемая LFSR, имела максимальную длину, является примитивность соответствующего многочлена.

Реализация

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

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

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

Собственность баланса

Появление 0 и 1 в последовательности должно быть примерно одинаковым. Точнее, в последовательности максимальной длины *n* содержится *n/2 + 1* единиц и *n/2 - 1* нулей. Количество единиц равно количеству нулей плюс один, поскольку состояние, содержащее только нули, не может возникнуть.

Собственность корреляции

Круговая автокорреляция МПСШ является дельта-функцией Кронекера (со смещением по постоянной составляющей и временной задержкой, в зависимости от реализации). Для соглашения ±1, то есть, битовому значению 1 присваивается +1, а битовому значению 0 – -1, отображение XOR соответствует отрицательному произведению:

где обозначает комплексное сопряжение, а – круговой сдвиг. Линейная автокорреляция МПСШ аппроксимирует дельта-функцию Кронекера.

Отношение к трансформации Хадамара

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