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 0とx 2とx 4及びX 6が一つのカテゴリーに分類されていると同様に、点は、X 1、X、3、xは5及び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]は奇数部分を表します。ダイアグラムで実現したい場合は、以下のように表示できます。

上の図から、

$ W_8 ^ 4 = -1 $

$ W_8 ^ 5 = -W_8 ^ 1 $

$ W_8 ^ 6 = -W_8 ^ 2 $

$ W_8 ^ 7 = -W_8 ^ 3 $

同様に、最終的な値は次のように書くことができます-

$ G [0] -H [0] = x [4] $

$ G [1] -W_8 ^ 1H [1] = x [5] $

$ G [2] -W_8 ^ 2H [2] = x [6] $

$ G [1] -W_8 ^ 3H [3] = x [7] $

上記は周期系列です。このシステムの欠点は、Kが4ポイントを超えて破ることができないことです。ここで、上記をさらに詳しく見ていきましょう。このような構造になります

シーケンスx [n] = {1,1、-1、-3,0,1,2,1}について考えてみます。FFTを計算します。

Solution −指定されたシーケンスはx [n] = {2,1、-1、-3,0,1,2,1}です。

以下に示すように用語を配置します。