離散フーリエ変換 (一般)
n個組 ( v 0 , ... , v n − 1 ) {\displaystyle (v_{0},\ldots ,v_{n-1})} を n − 1 {\displaystyle n-1} 次の多項式
p v ( x ) = v 0 + v 1 x + v 2 x 2 + ⋯ + v n − 1 x n − 1 {\displaystyle p_{v}(x)=v_{0}+v_{1}x+v_{2}x^{2}+\cdots +v_{n-1}x^{n-1}}
と見做すと便利なことがある。離散フーリエ変換の定義式(2)の和を書き下すと、
f k = v 0 + v 1 α k + v 2 α 2 k + ⋯ + v n − 1 α ( n − 1 ) k {\displaystyle f_{k}=v_{0}+v_{1}\alpha ^{k}+v_{2}\alpha ^{2k}+\cdots +v_{n-1}\alpha ^{(n-1)k}}
となる。つまり、 f k {\displaystyle f_{k}} は多項式 p v ( x ) {\displaystyle p_{v}(x)} の x = α k {\displaystyle x=\alpha ^{k}} における値であり、
f k = p v ( α k ) {\displaystyle f_{k}=p_{v}(\alpha ^{k})}
と書ける。したがって、離散フーリエ変換は、多項式の係数を値に変換するもの考えることができる。係数は時間領域で、値は周波数領域にある。
もちろん、多項式の値は、単位元の n {\displaystyle n} 乗根( α {\displaystyle \alpha } とその2乗、3乗、4乗、...)において評価することが重要である。
同様に、逆離散フーリエ変換の式(3)を書き下すと
v j = 1 n ( f 0 + f 1 α − j + f 2 α − 2 j + ⋯ + f n − 1 α − ( n − 1 ) j ) ( 5 ) {\displaystyle v_{j}={\frac {1}{n}}(f_{0}+f_{1}\alpha ^{-j}+f_{2}\alpha ^{-2j}+\cdots +f_{n-1}\alpha ^{-(n-1)j})\qquad (5)}
である。多項式を
p f ( x ) = f 0 + f 1 x + f 2 x 2 + ⋯ + f n − 1 x n − 1 {\displaystyle p_{f}(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{n-1}x^{n-1}}
とすれば、
v j = 1 n p f ( α − j ) {\displaystyle v_{j}={\frac {1}{n}}p_{f}(\alpha ^{-j})}
が成り立つ。
以上をまとめると、以下のようになる。 もし、多項式 p ( x ) {\displaystyle p(x)} の値が多項式 q ( x ) {\displaystyle q(x)} の係数であるならば、(定数倍と順番の入れ替えを除けば) q ( x ) {\displaystyle q(x)} の値は p ( x ) {\displaystyle p(x)} の係数と等しい。