5.1. Преобразования над конечным полем

Поскольку кодовое слово с является последовательностью, то преобразование является дискретным по времени. Кроме того, каждый элемент этой последовательности лежит в некотором поле Галуа, так что преобразование также должно принимать значения в некотором конечном поле. Свойства таких преобразований подробно описаны Поллардом [38]. Похожее преобразование уже было использовано в гл. 4.

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

Определение. Пусть последовательность элементов поля делит для некоторого и пусть -элемент порядка, Преобразованием Фурье над конечным полем вектора с называется последовательность элементов поля задаваемых равенством

Это определение аналогично определению конечного преобразования Фурье вещественного вектора, которое получается при замене ядра Фурье а на корень степени из единицы в поле комплексных чисел. В соответствии с принятой в технике терминологией дискретный индекс будет называться «временем», а индекс «частотой». Таким образом, векторы с и С будут называться функциями времени и частоты (или спектром) соответственно. Эти два вектора образуют пару Фурье, т. е.

Они связаны между собой следующим образом.

Теорема. Пусть характеристика поля GF (q) равна Тогда вектор и его спектр связаны между собой равенствами

Доказательство этой теоремы не приводим.

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

Тогда преобразование Фурье вектора с можно записать как

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

Векторы с и С можно представить многочленами Из этого представления видно, что спектральный компонент

Таким образом, тогда, и только тогда, когда -корень Аналогично временной компонент

Следовательно, справедлива следующая теорема.

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

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

Пример. Рассмотрим вектор с элементами из Преобразование Фурье над конечным полем для этого вектора также определено над и его компоненты согласно (5.1)

В качестве элемента порядка 4 в поле выбран элемент 2. Таблицы умножения и сложения для этого поля приведены в табл. 2.3. Производя указанные операции, получаем

в качестве искомого преобразования Фурье. Заметим, что характеристика поля равна 5 и что Таким образом, обратное преобразование С, задаваемое формулой (5.3), равно

Снова производя указанные операции, получаем исходный вектор с. Заметим, что в этот вектор входят два нулевых компонента, Согласно предыдущей теореме преобразованный многочлен

должен иметь корни 2° и 2-1. Непосредственная подстановка этих значений в показывает, что они действительно являются корнями.