過去サンプルのDFTの再帰的計算

arg maxarg min\providecommandrecterf\providecommand\providecommand\providecommandPr

はじめに

信号処理に於いて、時刻 n 毎に直近 N 個のサンプルの(時間的に逆向きの)DFTを計算したい状況がある。例えばDCTによる近似的な直交変換 LMS (Least Mean Square) アルゴリズムがそうである。その際に毎度 N 点FFTを実行すると毎時刻 O(NlogN) の計算量となる。しかし実は漸化式を用いてこれを回避し、毎度 O(N) の計算量とする方法がある([1] p65)。本記事ではこれについて述べ、Mathematicaによる数値例を載せる。

“過去サンプルのDFTの再帰的計算” の続きを読む