DSP-インプレース計算
このメモリの効率的な使用は、FFTを計算するための高速ハードウェアを設計するために重要です。インプレース計算という用語は、このメモリ使用量を説明するために使用されます。
時系列でのデシメーション
この構造では、すべてのポイントをバイナリ形式、つまり0と1で表します。次に、これらの構造を逆にします。その後に取得するシーケンスは、ビット反転シーケンスと呼ばれます。これは、時系列でのデシメーションとも呼ばれます。8点DFTのインプレース計算は、以下に示すように表形式で示されています。
| ポイント | バイナリ形式 | リバーサル | 同等のポイント |
|---|---|---|---|
| 0 | 000 | 000 | 0 |
| 1 | 001 | 100 | 4 |
| 2 | 010 | 010 | 2 |
| 3 | 011 | 110 | 6 |
| 4 | 100 | 001 | 1 |
| 5 | 101 | 101 | 5 |
| 6 | 110 | 011 | 3 |
| 7 | 111 | 111 | 7 |
周波数シーケンスでのデシメーション
時系列とは別に、N点シーケンスも頻度で表すことができます。それをよりよく理解するために、4ポイントのシーケンスを取りましょう。
シーケンスを$ x [0]、x [1]、x [2]、x [3]、x [4]、x [5]、x [6]、x [7] $とします。最初に、2つのポイントを1つのグループにグループ化します。数学的には、このシーケンスは次のように書くことができます。
$$ x [k] = \ sum_ {n = 0} ^ {N-1} x [n] W_N ^ {nk} $$ここで、シーケンス番号0〜3の1つのグループと、シーケンス4〜7の別のグループを作成します。これで、数学的にこれを次のように表すことができます。
$$ \ displaystyle \ sum \ Limits_ {n = 0} ^ {\ frac {N} {2} -1} x [n] W_N ^ {nk} + \ displaystyle \ sum \ limits_ {n = N / 2} ^ {N-1} x [n] W_N ^ {nk} $$nをrに置き換えましょう。ここで、r = 0、1、2…。（N / 2-1）です。数学的には、
$$ \ displaystyle \ sum \ limits_ {n = 0} ^ {\ frac {N} {2} -1} x [r] W_ {N / 2} ^ {nr} $$最初に最初の4つの点（x [0]、x [1]、x [2]、x [3]）を取り、次のように数学的に表現しようとします。
$ \ sum_ {n = 0} ^ 3x [n] W_8 ^ {nk} + \ sum_ {n = 0} ^ 3x [n + 4] W_8 ^ {（n + 4）k} $
$ = \ lbrace \ sum_ {n = 0} ^ 3x [n] + \ sum_ {n = 0} ^ 3x [n + 4] W_8 ^ {（4）k} \ rbrace \ times W_8 ^ {nk} $
今$ X [0] = \ sum_ {n = 0} ^ 3（X [n] + X [n + 4]）$
$ X [1] = \ sum_ {n = 0} ^ 3（X [n] + X [n + 4]）W_8 ^ {nk} $
$ = [X [0] -X [4] +（X [1] -X [5]）W_8 ^ 1 +（X [2] -X [6]）W_8 ^ 2 +（X [3] -X [7]）W_8 ^ 3 $
さらに2つの部分に分割できます。つまり、4ポイントのシーケンスとして分割する代わりに、2ポイントのシーケンスに分割できます。