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

5-точечное ДПФ с ядромзадается равенством

,

непосредственное вычисление по которому требует 16 умножений и 20 сложений. Использование только тождества на ядре (которое в данном случае имеет вид 1+++) дает 9 умножений и 21 сложение. Это достигается, например, следующим образом:

,

Аналогично,

,

,

и, наконец,

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

Утверждение 4.5.1.

Два двучлена и , , , , , можно перемножить, выполняя не более трех умножений чисел в поле F.

Действительно, ()()?

, где , и

Если умножение происходит в поле F, то , где ,

Следствие 4.5.1.

Два многочлена степени m над полем F можно перемножить, выполняя не более умножений чисел в поле F.

Например, для m=3 (с учетом, что char GF()=2) имеем:

?

?

=

?

где t?

(так что при вычислении по модулю многочлена надо делать редукцию по модулю ); согласно утверждению 4.5.1:

?

?

?

Для вычисления , , опять воспользуемся утверждением 4.5.1. Имеем

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