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

3-точечное ДПФ с ядром β для вектора a=

, a-0., a-1., a-2

. задается формулой

A=(

, A

-0

.,

A

-1

.,A

-2

.)=

Так как ядро β удовлетворяет тождеству 1+, то легко проверить непосредственно, что числа могут быть вычислены по правилу:

s

-1

.=

, a

-1

.+

, a

-2

., m

-1

.=β∙

, s

-1

., A

-1

.=

, s

-2

.+

, a

-1

.,

,

которое содержит только одно умножение и 5 сложений (вместо 4 умножений и 6 сложений). Если , β

=

,

α

-3

.=

,

α

-85

.