Дискретное преобразование Фурье

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

В поле комплексных чисел ДПФ вектора с комплексными компонентами определяется как вектор , компоненты которого вычисляются согласно соотношению

.

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

Пусть - вектор над , где n делит при некотором m и пусть - элемент мультипликативного порядка n в расширенном поле . Тогда ДПФ над полем вектора является вектор с элементами , задаваемыми равенствами

,

или в матричном представлении

.

Учитывая ранее указанную аналогию, дискретный индекс i естественно назвать дискретным временем, а вектор - временной функцией (последовательностью) или сигналом. Аналогично, индекс k можно назвать дискретной частотой, а вектор - частотной функцией (последовательностью) или спектром.называется ядром преобразования, а матрица в правой части равенства - матрицей Фурье.

Если спектр определяется прямым ДПФ, то с помощью обратного ДПФ по спектру может быть определен сам сигнал, т.е. компоненты вектора

.

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

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

Теорема 4.1.1. (Теорема о свертке)

Пусть - временные последовательности, причем . Тогда компоненты ДПФ могут быть определены как

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

Доказательство:

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

.

Можно сформулировать и обратную теорему, поменяв местами временную и частотную области.

Теорема 4.1.2.

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