FFTによる高速補間法

千葉 則茂  海野 啓明  三浦 守  

誌名
電子情報通信学会論文誌 A   Vol.J71-A   No.2   pp.207-212
発行日: 1988/02/25
Online ISSN: 
DOI: 
Print ISSN: 0373-6091
論文種別: 特集論文 (信号処理特集)
専門分野: 基礎理論
キーワード: 


本文: PDF(513.8KB)>>
論文を購入




あらまし: 
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)+LNW,作業記憶領域での領域計算量LNのアルゴリズムも与えている.本文では,離散フーリエ変換の一般的構造,性質に基づき,まず,彼らのアルゴリズムに見通しのよい説明を与え,更に,解析とインプリメントの容易な,部分区間の補間を求める時間計算量LN(1+(logW/L)/2)+LNW,補間倍率に依存しない領域計算量Nをもつアルゴリズムを与えた.