14.2. ПСЕВДОШУМОВЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ

Слова (за исключением векторов 0 и 1) циклического симплексного кода или расширенного циклического кода Рида — Маллера первого порядка похожи на случайные последовательности из нулей и единиц (рис. 14.1). Мы увидим, что, действительно, если с — некоторое ненулевое слово кода 9, то оно обладает многими свойствами, характерными для последовательностй, которые получаются при случайном подбрасывании монеты раз. Например, число единиц и нулей в с примерно равно друг другу,

Рис. 14.1. Слова циклического симплексного -кода

как это и должно быть. Далее назовем серией максимальный отрезок последовательных равных символов. Тогда половина серий в с будет иметь длину, равную 1, четверть — длину, равную восьмая часть — длину, равную 3, и т. д. В каждом случае число серий нулей равно числу серий единиц. Пожалуй наиболее важное свойство вектора с состоит в том, что его автокорреляционная функция равна для рис. 14.4).

Случайность, задаваемая кодовыми словами такого типа, оказывается очень полезной во многих приложениях, таких как радиолокация, синхронизация, модуляция, фильтрация и др.

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

Рассматриваемые кодовые слова можно генерировать при помощи регистров сдвигов, и сейчас мы перейдем к описанию того, это делается, и приведем свойства этих последовательностей.

Пусть неприводимой примитивный многочлен над степени (см. гл. 4). Согласно § 8.3 h(x) является проверочным многочленом симплексного кода Построим регистр сдвигов, линейные обратные связи которого описываются многочленом так, как это показано на рис. 14.2.

Рис. 14.2. Регистр сдвигов с обратной связью, задаваемой многочленом

Например, если то регистр имеет вид, показанный на рис. 14.3.

Предположим, что начальное содержимое (или состояние) регистра сдвигов равняется (рис. 14.2). Выход считывается с правого конца регистра и равен бесконечной двоичной последовательности

Определение. При любом ненулевом начальном состоянии выход а называется псевдошумовой (или ПШ)

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

Рис. 14.3. Регистр сдвигов, соответствующий многочлену и соответствующая последовательность состояний

Выходная последовательность равна четвертому столбцу таблицы, т. е. равна

и имеет период, равный 15.

Свойства ПШ-последовательности. Свойство Для всех ПШ-последовательность удовлетворяет рекуррентному соотношению

Свойство II. При некотором начальном состоянии последовательность а является периодической с периодом т. е. для всех и представляет собой наименьшее целое число с таким свойством.

Доказательство. Заметим, что для произвольной последовательности а из свойства I вытекает, что

Обозначим эту -матрицу через Тогда

Так как сопровождающая матрицы многочлена (см. § 4.3), то согласно упражнению (20) гл. является наименьшим целым числом таким, что Следовательно, найдется такой вектор что для всех —1. Следовательно, если выбрать в качестве начального состояния, то последовательность а будет периодической с периодом

Свойство III. При таком начальном состоянии регистр сдвигов принимает все возможных ненулевых состояний, прежде чем состояния начинают повторяться.

Доказательство. Очевидно, так как период равен

Заметим, что, за исключением последовательности а, тождественно равной нулю, нулевое состояние регистра не наступает никогда и что является максимально возможным значением периода для линейного регистра сдвигов с ячейками.

Свойство IV. Для любого ненулевого начального состояния регистра период выходной последовательности равен и действительно, выходная последовательность может быть получена из последовательности а путем выбрасывания нескольких первых ее символов.

Доказательство. Вытекает из свойства III.

Теперь рассмотрим свойства произвольного отрезка с длины последовательности

Свойство с является словом симплексного кода с проверочным многочленом

Доказательство. Так как вектор с удовлетворяет уравнению (7.12), то он, очевидно, принадлежит коду с проверочным многочленом Согласно § 8.3 этот код является симплексным, так как многочлен примитивен.

Свойство VI. (Свойство «сдвиг-сложение».) Сумма произвольного отрезка с длины последовательности а со своим циклическим сдвигом равна некоторому другому циклическому сдвигу с.

Доказательство. Вытекает непосредственно из свойства (V).

Упражнения. (1). (Свойство скользящего окна.) Показать, что если вдоль ПШ-последовательности скользит окно шириной в символов, то в течение одного периода каждая ненулевая -последовательность из возможных встречается точна один раз.

(2). Рассмотреть регистр сдвигов длины обратные связи которого описываются не обязательно примитивным многочленом h(x) (как на рис. 14.2). Показать, что при начальном состоянии период выходной последовательности а равен наименьшему положительному числу такому, что делит

(3). Если неприводим, но не обязательно примитивен, то делит

(4). Если -последовательность, то для всякого взаимно простого с последовательность также является псевдошумовой.

(5.). Некоторый сдвиг последовательности а, скажем, обладает тем свойством, что для всех состоит в точности из повторений идемпотента симплексного кода, см. § 8.4).

Псевдослучайные свойства. Свойство VII. Произвольный отрезок с длины последовательности а содержит единиц и нулей.

Доказательство. Вытекает из свойства (V)

Свойство VIII. В отрезке с половина серий имеет длину, равную 1, четверть — длину, равную восьмая часть — длину, равную 3, и т. д. до тех пор, пока эти доли дают целое число серий. Во всех случаях число серий из нулей равно числу серий из единиц.

Упражнение. (6). Доказать это утверждение.

Автокорреляционная функция. Мы переходим к наиболее важному свойству — к автокорреляционной функции. Автокорреляционная функция бесконечной последовательности действительных или комплексных чисел с периодом определяется для всех равенством

где черта обозначает комплексное сопряжение. Эта функция периодична: Автокорреляционная функция двоичной последовательности периода определяется как автокорреляционная функция последовательности действительных чисел которая получается из исходной путем замены 1 на —1 и 0 на 1. Таким образом,

Иначе, пусть А — число совпадений символов у -последовательности и ее циклического сдвига число несовпадений (так что Тогда

Например, автокорреляционная функция ПШ-последовательности (14.1), как показано на рис. 14.4, равна:

Рис. 14.4 Автокорреляционная функция ПШ-последовательности

Свойство IX. Автокорреляционная функция ПШ-последовательности периода равна:

Доказательство. Из (14.4) имеем

где для некоторого о (по свойству VI). Тогда результат сразу вытекает из свойств V и VII.

Упражнения. (7). Показать, что функция (14.5) является наилучшей возможной среди всех автокорреляционных функций для всех двоичных последовательностей с периодом если в качестве критерия выбрать минимум функции

(8). (Тест для отличия ПШ-последовательности от последовательности случайных бросаний «на Пусть - последовательные двоичные символы из ПШ-последовательности периода Для построим матрицу

Доказать, что ранг матрицы над меньше чем [Указание. В коде имеется только линейно независимых последовательностей ] С другой стороны, доказать, что если отрезок последовательности случайных бросаний, где каждый символ принимает значения 0 и 1 с вероятностями то вероятность того, что не превосходит что при дает очень малое значение.

Таким образом, вопрос «Имеет место равенство является тестом для различия малой выборки символов из ПШ-последовательности и выборки из действительно случайной последовательности. Например, если тест будет давать отрицательный ответ для любой выборки из

последовательных символов ПШ-последовательности, в время как вероятность отрицательного ответа для последовательности случайных бросаний монеты не превышает .