DSP-高速フーリエ変換

以前のDFT法では、計算部分が長すぎることがわかりました。それを減らしたい。これは、FFTまたは高速フーリエ変換を介して実行できます。したがって、FFTは、計算部分が削減されるアルゴリズム形式の離散フーリエ変換の計算に他なりません。

FFTを使用する主な利点は、FFTを使用してFIRフィルターを設計できることです。数学的には、FFTは次のように書くことができます。

$$ x [K] = \ displaystyle \ sum \ limits_ {n = 0} ^ {N-1} x [n] W_N ^ {nk} $$

それをよりよく理解するために例を見てみましょう。$ x_0 \ quadから\ quad x_7 $までの8つのポイントを検討しました。一方のグループでは偶数の用語を選択し、もう一方のグループでは奇数の用語を選択します。上記の概略図を以下に示します-

ここで、ポイントは、x ₀とx ₂とx ₄及びX _6が一つのカテゴリーに分類されていると同様に、点は、X ₁、X、₃、xは₅及びX _7は、別のカテゴリに置かれています。これで、さらに2つのグループにまとめて、計算を進めることができます。ここで、これらをさらに2つに分割することが、計算にどのように役立つかを見てみましょう。

$ x [k] = \ displaystyle \ sum \ limits_ {r = 0} ^ {\ frac {N} {2} -1} x [2r] W_N ^ {2rk} + \ displaystyle \ sum \ limits_ {r = 0 } ^ {\ frac {N} {2} -1} x [2r + 1] W_N ^ {（2r + 1）k} $

$ = \ sum_ {r = 0} ^ {\ frac {N} {2} -1} x [2r] W_ {N / 2} ^ {rk} + \ sum_ {r = 0} ^ {\ frac {N } {2} -1} x [2r + 1] W_ {N / 2} ^ {rk} \ times W_N ^ k $

$ = G [k] + H [k] \ times W_N ^ k $

最初は8ポイントのシーケンスを使用しましたが、後でそれをG [k]とH [k]の2つの部分に分割しました。G [k]は偶数部分を表し、H [k]は奇数部分を表します。ダイアグラムで実現したい場合は、以下のように表示できます。