DSP-DFT巡回畳み込み
私たちは2つの有限持続配列は、Xみましょう1（n）およびX 2それらのDFTがXであるNと整数の長さを有する、（N）を1（K）およびX 2（K）は、それぞれ、下に示されています-
$$ X_1（K）= \ sum_ {n = 0} ^ {N-1} x_1（n）e ^ {\ frac {j2 \ Pi kn} {N}} \ quad k = 0,1,2。。 .N-1 $$ $$ X_2（K）= \ sum_ {n = 0} ^ {N-1} x_2（n）e ^ {\ frac {j2 \ Pi kn} {N}} \ quad k = 0 、1,2 ... N-1 $$ここで、X 3（K）として与えられる別のシーケンスx 3（n）のDFTを見つけようとします。
$ X_3（K）= X_1（K）\ times X_2（K）$
上記のIDFTを取ることにより、
$ x_3（n）= \ frac {1} {N} \ displaystyle \ sum \ limits_ {n = 0} ^ {N-1} X_3（K）e ^ {\ frac {j2 \ Pi kn} {N}} $
上記の方程式を解いた後、最終的に、次のようになります。
$ x_3（n）= \ displaystyle \ sum \ limits_ {m = 0} ^ {N-1} x_1（m）x_2 [（（nm））_ N] \ quad m = 0,1,2 ... N- 1 $
| 比較ポイント | 線形畳み込み | 巡回畳み込み |
|---|---|---|
| シフト | 線形シフト | 循環シフト |
| 畳み込み結果のサンプル | $ N_1 + N_2-1 $ | $ Max（N_1、N_2）$ |
| フィルタの応答を見つける | 可能 | ゼロパディングで可能 |
巡回畳み込みの方法
一般に、巡回畳み込みを実行するために採用される2つの方法があり、それらは次のとおりです。
- 同心円法、
- 行列乗算法。
同心円法
$ x_1（n）$と$ x_2（n）$を2つの指定されたシーケンスとします。$ x_1（n）$と$ x_2（n）$の巡回畳み込みの手順は次のとおりです。
2つの同心円を取ります。$ x_1（n）$のN個のサンプルを反時計回りの方向に外側の円の円周にプロットします（連続する点の距離を等しく維持します）。
$ x_2（n）$をプロットするには、$ x_2（n）$のN個のサンプルを時計回りに内側の円にプロットします。開始サンプルは$ x_1（n）$の0番目のサンプルと同じポイントに配置されます。
2つの円の対応するサンプルを乗算し、それらを追加して出力を取得します。
一度に1つのサンプルを使用して、内側の円を反時計回りに回転させます。
行列乗算法
行列法は、与えられた2つのシーケンス$ x_1（n）$と$ x_2（n）$を行列形式で表します。
与えられたシーケンスの1つは、一度に1つのサンプルの循環シフトを介して繰り返され、NXNマトリックスを形成します。
他のシーケンスは列行列として表されます。
2つの行列を乗算すると、巡回畳み込みの結果が得られます。