Преобразование Фурье в конечных полях

 

Наиболее прозрачное объяснение процедуры декодирования РС–кодов может быть дано в терминах гармонического анализа. Для понимания его особенностей в конечных полях первоначально вспомним основы обычного дискретного преобразования Фурье (ДПФ). Если – n– компонентный вектор комплексных или вещественных отсчетов сигнала, то его образ в частотной области (спектр) вычисляется с помощью прямого ДПФ:

. (9.4)

Ядром преобразования Фурье является , которое является примитивным корнем n –й степени из единицы в поле комплексных чисел: , но для любого . Исходный образ сигнала во временной области восстанавливается по его спектру с помощью обратного ДПФ:

. (9.5)

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

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

. (9.6)

Соотношение (9.6) может быть обращено как:

, (9.7)

что демонстрирует полное совпадение (9.6)–(9.7) соотношениям (9.4)–(9.5), которые отвечают вещественным или комплексным сигналам. Следовательно, вектор может трактоваться как ДПФ вектора над полем . Учитывая ранее указанную аналогию, дискретный индекс i естественно назвать дискретным временем, а вектор – временной функцией (последовательностью) или сигналом. Аналогично, индекс k можно назвать дискретной частотой, а вектор – частотной функцией (последовательностью) или спектром.

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

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

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

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

.

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

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

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

Отметим также, что выбор в теореме о свертке 9.2.1 приводит к формуле типа равенства Парсеваля

.

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

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