64回の積和演算をしなくはいけません。これを減らすことができるのでしょうか?
そして今は、 なのでこの回転は図のように8分割されて回転していることになるのです。
奇数 偶数とも上半分だけで計算することができるようになりました。
だから なんかは、まず45度ずれてさらに90度ずれる波を求めていることになります。
演算の流れをもう一度よく見てシグナルフローグラフを作ってみましょう。
と実際は計算されます。ここで 以降の第2項に-が付いているのは
つまり半周期(180度)回転したものはjxj=-1を掛けたものに等しいという条件です。
これを見ると4回の掛け算+8回の加算で計算することができます。
これをプログラミングすることで周波数領域を求めることができます。
そして得られた番号に格納されたデータと最初のデータを交換すればよい