FFTによる高速補間法

概要

論文の詳細を見る
FFTによる，帯域制限信号の補間は，CTの画像再構成やCGにおける形状補間などに応用される簡便で有効な補間法である．その高速アルゴリズムが仁木らやAdamsによって，異なるアプローチにより，考案されている．仁木らは，FFTの省略可能なバタフライ演算を詳細に調べることにより，乗算数でLN(1/2＋(logN)/2)の時間計算量をもつアルゴリズムを得ている．ここで，対数の底は2であり，Nは離散信号の標本数であり，Lは補間の倍率である．一方，Adamsは，L回のN点FFTにより補間が達成されることを示し，LN(1＋(logN)/2)の時間計算量をもつアルゴリズムを与えた．しかしながら，応用上は必ずしも全区間の補間を必要としないことも多い．仁木らは，更に，部分区間Wを高速に求める時間計算量LN(1/2＋(logW/L)/2)＋LN－W，作業記憶領域での領域計算量LNのアルゴリズムも与えている．本文では，離散フーリエ変換の一般的構造，性質に基づき，まず，彼らのアルゴリズムに見通しのよい説明を与え，更に，解析とインプリメントの容易な，部分区間の補間を求める時間計算量LN(1＋(logW/L)/2)＋LN－W，補間倍率に依存しない領域計算量Nをもつアルゴリズムを与えた．
電子情報通信学会の論文
1988-02-20