循環畳み込み

巡回畳み込みは、巡回畳み込みとも呼ばれ、周期畳み込みの特殊なケースであり、同じ周期を持つ 2 つの周期関数の畳み込みです。周期畳み込みは、たとえば、離散時間フーリエ変換(DTFT) のコンテキストで発生します。特に、2 つの離散シーケンスの積の DTFT は、個々のシーケンスの DTFT の周期畳み込みです。また、各 DTFT は、連続フーリエ変換関数の周期的な合計です (離散時間フーリエ変換 § フーリエ変換との関係を参照)。DTFT は通常、周波数の連続関数ですが、周期畳み込みと巡回畳み込みの概念は、データの離散シーケンスにも直接適用できます。そのコンテキストでは、巡回畳み込みは、特定の種類の一般的なフィルタリング操作の効率を最大化する上で重要な役割を果たします。

2つのT周期関数の周期畳み込みは次のように定義されます。${\displaystyle h_{_{T}}(t)}$${\displaystyle x_{_{T}}(t)}$

${\displaystyle \int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau ,}$   ^{[1] [2]}

ここで、 は任意のパラメータです。通常の線形畳み込みまたは非周期畳み込みの表記法による別の定義は、とを非周期成分との周期的な和として表すことから得られます。つまり、 です。${\displaystyle t_{o}}$${\displaystyle h_{_{T}}(t)}$${\displaystyle x_{_{T}}(t)}$${\displaystyle h}$${\displaystyle x}$

${\displaystyle h_{_{T}}(t)\ \triangleq \ \sum _{k=-\infty }^{\infty }h(t-kT)=\sum _{k=-\infty }^{\infty }h(t+kT).}$

それから：

どちらの形式も周期畳み込みと呼ぶことができる。^[a]円畳み込み^{[2] [3]}という用語は、との両方がゼロでない部分を区間に制限するという重要な特殊なケースから生じたものである。 すると周期的な和は周期的な拡張^{[b]となり、これは}円関数としても表すことができる。${\displaystyle h}$${\displaystyle x}$${\displaystyle [0,T].}$

${\displaystyle x_{_{T}}(t)=x(t_{\mathrm {mod} \ T}),\quad t\in \mathbb {R} \,}$（任意の実数）^[c]

そして積分の限界は関数の長さに減少します。${\displaystyle h}$

${\displaystyle (h*x_{_{T}})(t)=\int _{0}^{T}h(\tau )\cdot x((t-\tau )_{\mathrm {mod} \ T})\ d\tau .}$^{[d] [e]}

同様に、離散シーケンスとパラメータNに対して、非周期関数と の循環畳み込みを 次のように記述できます。${\displaystyle h}$${\displaystyle x}$

${\displaystyle (h*x_{_{N}})[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\cdot \underbrace {x_{_{N}}[n-m]} _{\sum _{k=-\infty }^{\infty }x[n-m-kN]}}$

この関数はN周期です。最大でN 個の一意の値を持ちます。 xとh の両方の非ゼロ範囲がN 以下である特殊なケースでは、積分変換の核が巡回行列である行列乗算に還元できます。

非常に実用的に興味深いケースを図に示します。xシーケンスの持続時間はN (またはそれ以下) で、hシーケンスの持続時間はそれより大幅に短くなります。この場合、循環畳み込みの値の多くはx∗hの値と同じになります。これは、 hシーケンスが有限インパルス応答(FIR) フィルターである場合に実際に望ましい結果です。さらに、循環畳み込みは、高速フーリエ変換(FFT) アルゴリズムと循環畳み込み定理を使用して計算すると非常に効率的です。

Nの実際的な値よりも長いxシーケンスを処理する方法もあります。シーケンスはセグメント (ブロック) に分割され、部分的に処理されます。次に、フィルターされたセグメントを慎重につなぎ合わせます。エッジ効果は、入力ブロックまたは出力ブロックのいずれかを重ね合わせることで除去されます。これらの方法を説明して比較しやすくするために、長さ 201 のhシーケンスとN = 1024の FFT サイズを 例として両方の方法を説明します 。

この方法では、FFT サイズ (1024) に等しいブロック サイズを使用します。まず、通常の畳み込みまたは線形畳み込みの観点から説明します。通常の畳み込みが各ブロックで実行されると、フィルターの遅延(200 サンプル)により、ブロックの端で開始および減衰の過渡現象が発生します。畳み込み出力のうち、エッジ効果の影響を受けないのは 824 個だけです。その他は破棄されるか、単に計算されません。入力ブロックが連続している場合、出力にギャップが生じます。ギャップは、入力ブロックを 200 サンプル重ね合わせることで回避されます。ある意味では、各入力ブロックの 200 要素が「保存」され、次のブロックに持ち越されます。この方法はオーバーラップ保存と呼ばれますが、^[4]次に説明する方法では、出力サンプルで同様の「保存」が必要です。

FFT を使用して 824 個の影響を受けない DFT サンプルを計算する場合、影響を受けるサンプルを計算しないという選択肢はありませんが、循環畳み込みのため、先頭と末尾のエッジ効果が重複して追加されます。その結果、1024 ポイントの逆 FFT (IFFT) 出力には、エッジ効果のサンプル 200 個 (破棄) と影響を受けないサンプル 824 個 (保持) のみが含まれます。これを説明するために、右側の図の 4 番目のフレームは、周期的に (または「循環的に」) 拡張されたブロックを示し、5 番目のフレームは、シーケンス全体に対して実行された線形畳み込みの個々のコンポーネントを示します。エッジ効果は、拡張されたブロックからの寄与が元のブロックからの寄与と重複する部分です。最後のフレームは複合出力で、緑色のセクションは影響を受けない部分を表します。

この方法はオーバーラップ加算として知られています。^[4] この例では、サイズ 824 の連続した入力ブロックを使用し、各ブロックに 200 個のゼロ値のサンプルを埋め込みます。次に、1024 要素の出力ブロックを重ね合わせて追加します。何も破棄されませんが、各出力ブロックの 200 個の値は、次のブロックとの追加のために「保存」する必要があります。どちらの方法も、1024 ポイントの IFFT ごとに 824 個のサンプルのみを進めますが、オーバーラップ保存では、最初のゼロ埋め込みと最後の追加が回避されます。

• 畳み込み定理
• 循環行列
• 離散ヒルベルト変換