Быстрое преобразование Фурье длины 5

Для уменьшения числа умножений, как и для 5-точечного ДПФ, воспользуемся переходом к циклической свертке с последующей редукцией по следствию из утверждения 4.5.1. Сначала воспользуемся алгоритмом Рейдера для перехода к циркулянту. Так как 5 является примитивным элементом поля GF(17), то имеем:

Таким образом, без учета в нумерации одиночного окаймления, к циклической свертке приводит, например, такая перестановка строки столбцов матрицы Фурье в (17) (соответствующих координат преобразуемого вектора а и спектра А), которая дается второй строкой этой таблицы: единичное окаймление остается на месте, а первая строка циркулянта соответственно имеет вид:

получаем,

, (18)

где , - вектор, полученный из спектра А указанной перестановкой координат, а - вектор столбец, определяемый вторым равенством в (18).

Согласно утверждению 4.5.2, задача вычисления (18) эквивалентна задаче вычисления циклической свертки

(19)

Вычислять свертку (19) будем следующим образом. Пусть (так что ) и пусть

Так что

,

,

Сначала будем полагать переменную х параметром и найдем циклическую свертку по модулю . Обозначая , согласно равенствам (15) имеем:

(20)

В поле для элемента выполняется тождества:

; ;

(21)

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

Aлгоритм вычисления R(x)=r(x) для произвольного многочлена содержит 4 умножения и 12 сложений. А именно, воспользуемся равенством (12) и учтем, что в поле согласно второму из тождеств в (20) выполняется равенство , char=2. Имеем: