7.4. Линейные рекуррентные соотношения и генераторы с регистром сдвига

Рассмотрим рекуррентные соотношения или разностные уравнения

или

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

По известным значениям можно найти и т. д.

Поскольку уравнения линейны, то любая линейная комбинация их решений есть снова решение, а все решения образуют векторное пространство. Совокупность к решений, для которых один из символов равен 1, а остальные равны 0, порождает все пространство решений; следовательно, размерность пространства решений не превосходит

На рис. 7.14 изображена линейная последовательная переключательная схсма, которая может быть использована для вычисления суммы (7.26) и, следовательно, для вычисления величины по значениям предыдущих членов последовательности.

Рис. 7.14. Генератор с регистром сдвига.

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

Решения линейных рекуррентных соотношений характеризуются следующей теоремой.

Теорема 7.1. Пусть и пусть наименьшее целое положительное число, для которого многочлен делится на Пусть далее

Тогда решения рекуррентных соотношений

периодичны с периодом и совокупность, составленная из

первых периодов всех возможных решений, рассматриваемых как многочлен по модулю

совпадает с идеалом, порожденным многочленом в алгебре многочленов по модулю Заметим, что если при таком определении многочлена элементы вычисляются в порядке возрастания номеров, то коэффициенты многочлена вычисляются, начиная с коэффициентов при степенях высших порядков, в соответствии с соглашением, принятым в разд. 7.1.

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

является решением уравнений (7,2а). Рассмотрим произведение

где

и

Используя равенство (6.8), находим, что если то

а если , то

Из теоремы 6.12 следует, что если принадлежит идеалу то следовательно, для любого

Теперь рассмотрим последовательность (7.3). В этой последовательности для всех Поэтому каждое из рекуррентных соотношений, задаваемых равенствами (7.2а), в точности эквивалентно одному из равенств (7.4) или (7.5), и, следовательно, если принадлежит идеалу, порожденному многочленом то последовательность (7.3) является решением рекуррентных соотношений (7.2).

Поскольку степень многочлена равна то по теореме 6.11 размерность идеала равна Она совпадаете размерностью пространства решений, откуда по теореме 2.9 следует, что идеал должен содержать все решения.

Некоторые из решений могут иметь период меньший, чем но должны существовать и решения, для которых это неверно. В частности, решение, получаемое из имеет период, равный точно Это можно показать следующим образом. Если период этого решения меньше, чем то, очевидно, делится на и каждый блок из символов состоит из повторяющихся блоков из символов. В этом случае должно выполняться равенство

Тогда

и

что противоречит предположению о том, что наименьшее целое число, для которого многочлен делится на

Пример. Найдем период решений над полем GF (2) разностного уравнения, соответствующего многочлену Многочлен одновременно делится на многочлены и , однако для того, чтобы многочлен делился на многочлены необходимо выбрать равным 6. Следовательно, период решения должен быть равен 6. Период некоторых решений будет меньше 6, но должно найтись по крайней мере одно решение периода, равного 6. Многочлен, порождающий идеал, для которого получается такое решение, равен где и соответствует решению Другими решениями являются все векторы, образующие пространство строк матрицы

В частности, период суммы первых двух векторов в действительности равен 3, а период суммы первых трех векторов в действительности равен 2.

В качестве следующего примера на рис. 7.15 показан двоичный генератор с регистром сдвига, соответствующий многочлену Это примитивный многочлен, и, следовательно, на него делится многочлен однако никакой другой многочлен при любых меньших значениях на не делится. Таким образом, период выходной последовательности регистра сдвига равен 255, — это максимально возможная длина

для генераторов с регистром сдвига, содержащим 8 разрядов. (См. дальнейшие подробности в разд. 8.3.)

Рис. 7.15. Генератор с регистром сдвига для последовательностей максимальной длины.

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

Рассмотрим рекуррентное соотношение, соответствующее в смысле теоремы 7.1 многочлену Пусть а — любой корень многочлена вообще говоря, в расширении поля. Тогда последовательность

очевидно, удовлетворяет рекуррентному соотношению. Поскольку рекуррентное соотношение линейно, то любая линейная комбинация последовательностей возрастающих степеней корней является решением

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

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

Пример. Пусть а — корень многочлена над полем Тогда элементы расширения поля нредставимы в виде векторов-столбцов из трех компонент из GF (2):

Каждая строка этой матрицы удовлетворяет рекуррентному соотношению

соответствующему многочлену

Рассмотрим теперь многочлен и соответствующее ему рекуррентное соотношение Если корень многочлена то элементы удовлетворяют рекуррентному соотношению. Поскольку единственный корень многочлена равен 1, то ему соответствует последовательность

Используя представление элементов с помощью многочленов по модулю найдем, что последовательные степени элемента задают первые три строки матрицы М, а последняя строка составлена из степеней элемента 1:

Таким образом, каждая строка матрицы М определяет решение, и совокупность всех решений совпадает с пространством строк матрицы М. С другой стороны, рассмотрим алгебру многочленов по модулю и пусть 5 обозначает класс вычетов, содержащий Тогда поскольку то

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

и записывая классы вычетов в виде векторов-столбцов, получаем матрицу

Каждая строка этой матрицы является решением рекуррентного соотношения, и каждое решение принадлежит пространству строк этой матрицы.

Существует еще один подход к этим вопросам, основанный на концепции "поля частных" многочленов. Строгое изложение этой концепции было дано Цирлером [110]. Приведем здесь только содержание основной теоремы и пример. Теорема Цирлера утверждает, что если некоторый многочлен степени или меньше формально делить на многочлен то коэффициенты оказывающегося бесконечным рядом частного удовлетворяют рекуррентному соотношению

Пример. Пусть Тогда, провотя деление, получаем

и последовательность коэффициентов 11101001 1 10100 согласуется с любой строкой матрицы (7.9).

Схемы, разбираемые в этом разделе и в разд. 7.2, аналогичны линейным фильтрам и системам с обратной связью. Они являются, по существу, дискретными системами обработки информации, и единственное важное отличие от обычных систем состоит в том, что здесь используемые величины являются элементами конечного поля, а в обычных системах — действительными числами. Методы преобразований, применяемые для таких систем, применимы и здесь; соответствующие математические методы обсуждались в предыдущих разделах. Эти идеи развиваются далее в следующем разделе.