ГЛАВА 8. КОДЫ, ОСНОВАННЫЕ НА СПЕКТРАЛЬНЫХ МЕТОДАХ

Обработка дискретных сигналов основывается на применении преобразования Фурье. Исследование сигналов с непрерывным временем, принимающих вещественные и комплексные значения, существенно связано с преобразованием Фурье; в случае сигналов с дискретным временем аналогичную роль играет дискретное преобразование Фурье. Для многих значений существуют также преобразования Фурье на векторном пространстве последовательностей длины над полем Галуа Преобразования Фурье в поле Галуа могут играть важную роль в исследовании и обработке -значных сигналов, т. е. кодовых слов. Основываясь на преобразовании Фурье, можно построить теорию кодирования существенно отличным от использовавшегося ранее способом. Циклические коды можно определить как коды, в которых некоторые спектральные компоненты слов равны нулю. Декодирование кодов БЧХ и кодов Рида-Соломона также может быть описано на спектральном языке.

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

8.1. ПРЕОБРАЗОВАНИЯ ФУРЬЕ В ПОЛЕ ГАЛУА

В поле комплексных чисел дискретное преобразование Фурье вектора с комплексными компонентами определяется как вектор задаваемый равенствами

где Ядро преобразования Фурье равно корню степени из единицы в поле комплексных чисел. В конечном поле элемент а порядка равен корню степени из единицы. Проводя аналогию между и а, получаем следующее определение.

Определение 8.1.1. Пусть вектор над где делит при некотором и пусть а — элемент порядка в поле Преобразование Фурье в поле Галуа вектора определяется как вектор задаваемый равенствами

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

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

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

Теорема 8.1.2. Над полем характеристики вектор и его спектр связаны соотношгн иями

где интерпретируется как число поля, т. е. по модулю

Доказательство. В любом поле

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

если же по модулю то

что всегда отлично от нуля, если не кратно характеристике Комбинируя эти равенства, получаем

Наконец, кратно и поэтому не кратно Следовательно, Это доказывает теорему.

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

Теорема 8.1.3 (теорема о свертке). Предположим, что

Тогда

где двойные скобки означают, что индексы вычисляются в арифметике по модулю

Доказательство. Найдем преобразование Фурье вектора с компонентами

Заметим также, что выбор в формуле свертки

приводит к формуле типа равенства Парсеваля:

Теорема 8.1.4 (свойство сдвига). Если является парой преобразования Фурье, то парами преобразований Фурье являются также

Доказательство получается непосредственной подстановкой.

Иногда вектор задается многочленом С помощью преобразования Фурье в поле Галуа многочлен

может быть преобразован в многочлен

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

Теорема 8.1.5.

(i) Элемент а является корнем многочлена тогда и только тогда, когда частотная компонента равна нулю.

(ii) Элемент является корнем многочлена тогда и только тогда, когда временная компонента равна нулю.

Доказательство утверждения (i) очевидно, так как

Утверждение (ii) доказывается тем же путем.

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