DSP-DFTセクショナルコンボリューション
長い持続時間の入力シーケンスx（n）が、2つのシーケンスを畳み込むことによって有限持続時間のインパルス応答を持つシステムで処理されると仮定します。DFTを介して実行される線形フィルタリングには固定サイズのデータブロックに対する操作が含まれるため、入力シーケンスは処理前に異なる固定サイズのデータブロックに分割されます。
次に、連続するブロックが一度に1つずつ処理され、結果が組み合わされて最終結果が生成されます。
畳み込みは、長い入力シーケンスを異なる固定サイズのセクションに分割することによって実行されるため、セクション畳み込みと呼ばれます。長い入力シーケンスは、FIRフィルター処理の前に、固定サイズのブロックにセグメント化されます。
離散たたみ込みを評価するために2つの方法が使用されます-
Overlap-save method
Overlap-add method
オーバーラップ保存方法
オーバーラップ保存は、非常に長い信号x（n）と有限インパルス応答（FIR）フィルターh（n）の間の離散たたみ込みを評価する効率的な方法の伝統的な名前です。オーバーラップ保存方法の手順は次のとおりです。
入力データブロックの長さ= N = L + M-1とします。したがって、DFTおよびIDFTの長さ= Nです。各データブロックは、前のブロックのM-1データポイントとそれに続くL個の新しいデータポイントを伝送して、長さN = L + M-1のデータシーケンスを形成します。
まず、データブロックごとにN点DFTが計算されます。
（L-1）ゼロを追加することにより、FIRフィルターのインパルス応答の長さが増加し、NポイントのDFTが計算されて保存されます。
2つのN点のDFT H（k）とXとの乗算M（K）：Y ' M（k）= H（K）・X M（k）は、ここで、K = 0,1,2、... N-1
その後、IDFT [Y ' M（（K）= Y'（（N）= [Y ' M（0）、Y' M（1）、Y ' M（2）、......、Y ' M（M-1）、Y' M（M）、...... Y ' M（N-1）]
（ここでは、N-1 = L + M-2）
最初のM-1ポイントはエイリアシングのために破損しているため、データレコードの長さがNであるため、それらは破棄されます。
最後のL点は畳み込みの結果とまったく同じなので、
Y ' M（N）= Y M（n）は、ここで、n = M、M + 1、...。N-1
エイリアシングを回避するために、各データレコードの最後のM-1要素が保存され、これらのポイントは後続のレコードに繰り越されて、最初のM-1要素になります。
エイリアシングを無効にするための最初のM-1ポイントが回避されるIDFTの結果と、残りのLポイントは、線形畳み込みの結果として望ましい結果を構成します。
オーバーラップ加算法
以下に、オーバーラップ法を使用して離散畳み込みを見つける手順を示します。
入力データのブロックサイズをLとします。したがって、DFTとIDFTのサイズは次のようになります。N= L + M-1
各データブロックには、最後にM-1個のゼロが追加されます。
N点DFTを計算します。
2つのN点DFTが乗算されます：Y m（k）= H（k）.X m（k）、ここでk = 0、、1,2、…。、N-1
IDFT [Y m（k）]は、DFTのサイズがN = L + M-1であるため、エイリアシングの影響を受けない長さNのブロックを生成し、それぞれにM-1個のゼロを追加することでシーケンスの長さをNポイントに増やします。ブロック。
各ブロックの最後のM-1ポイントをオーバーラップさせて、後続のブロックの最初のM-1ポイントに追加する必要があります。
（理由：各データブロックはM-1個のゼロで終了します）
したがって、この方法はオーバーラップ加算法として知られています。したがって、次のようになります。
y（n）= {y 1（0）、y 1（1）、y 1（2）、... ..、y 1（L-1）、y 1（L）+ y 2（0）、 y 1（L + 1）+ y 2（1）、... ... ..、y 1（N-1）+ y 2（M-1）、y 2（M）、....。 。.........}}