重畳加算法 重畳加算法の概要

ウィキペディア

重畳加算法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/01 00:50 UTC 版)

${\begin{aligned}y[n]=(\mathbf {h} *\mathbf {x} )[n]=\sum _{m=0}^{M-1}h[m]\cdot x[n-m]\end{aligned}}$

ここで 信号 $x[n]$は $n=1,\ldots ,N_{x}$、フィルタ $h[m]$は $m=0,\ldots ,M-1$ 以外で0、また$M<N_{x}$である。

重畳加算法の基本アイデアは、長い信号 $\mathbf {x}$ を区間長$L$で区切り、複数の短い断片 $\mathbf {x} _{k}$ と フィルタ $\mathbf {h}$ に関する複数の畳み込みに分割して、訳注: 適切なブロック長のFFTの積として効率的に計算することにある。

${\begin{aligned}x_{k}[n]\ &{\stackrel {\mathrm {def} }{=}}\ {\begin{cases}x[n+kL],&n=1,2,\ldots ,L\\0,&{\textrm {otherwise}}\end{cases}}\\x[n]&=\sum _{k}x_{k}[n-kL],\\\end{aligned}}$

離散畳み込み$(\mathbf {h} *\mathbf {x} )[n]$は、各区間の畳み込みの総和で表せる:

${\begin{aligned}y[n]=(\mathbf {h} *\mathbf {x} )[n]&=\sum _{m=0}^{M-1}\left(h[m]\cdot \sum _{k}x_{k}[n-m-kL]\right)\\&=\sum _{k}(\mathbf {h} *\mathbf {x} _{k})[n-kL]\\\end{aligned}}$

ここで各区間の畳み込み $y_{k}[n]\ {\stackrel {\mathrm {def} }{=}}\ (\mathbf {h} *\mathbf {x} _{k})[n]$は 領域 [1, L+M-1] 以外で 0 であり、任意の $N\geq (L+M-1)$ に関し、領域 [1, N] における $\mathbf {x} _{k}$ と $\mathbf {h}$ の $N$点巡回畳み込みと等価である。

重畳加算法のアドバンテージは、この巡回畳み込みが畳み込み定理により、次のような FFTの積の逆FFT として効率的に計算できる事にある:

$y_{k}[n]={\textrm {IFFT}}\left({\textrm {FFT}}\left(\mathbf {x} _{k}\right)\cdot {\textrm {FFT}}\left(\mathbf {h} \right)\right)[n]$

(式1)

ここで ${\textrm {FFT}}$と${\textrm {IFFT}}$は(ブロック長$N$の)高速フーリエ変換と逆高速フーリエ変換である。 FFTアルゴリズムによっては、(巡回畳み込み計算のために)FFTブロック長$N$を調整する事が理に適っている。例えばCooley-Tukey型FFTアルゴリズム (radix-2アルゴリズム) を使う場合、2の冪乗のブロック長を選ぶと有利である:

$N=L+M-1=2^{p},\quad p\in \mathbb {N}$