フェルマ数変換を用いた高速フーリエ変換

森川　良孝  山根　延元  浜田　博  

誌名
電子情報通信学会論文誌 D   Vol.J65-D   No.7   pp.826-833
発行日: 1982/07/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


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



あらまし: 
離散フーリエ変換（DFT）は，デジタル信号処理における最も重要な処理手段である．本論文では，フェルマ数変換（FNT）を用いた高速フーリエ変換（FFT）を提案し，このアルゴリズムに基くFFT専用プロセッサの経済的有効性について述べている．本FFTアルゴリズムは次の3つの事実に基いている．素数変換長DFTは，フーリエ変換核系列と信号系列の循環たたみ込み（DCC）に帰着する．DCCは数論変換（NTT）を通じて計算できる．変換系列長が互いに素な因数に分解できる場合には，DFTの直積分解が存在する．NTTのうちでモジュール化が容易で高速アルゴリズムが存在するのはFNTである．しかし，FNTを用いた，との方法だけでは，DFTの変換長は極めて制限される．そこでの事実に注目してDFTの変換長の多様化を計っている．本アルゴリズムはモジュール化が容易なため，そのハードウェア化はたやすい．そこで本アルゴリズムに含まれているFNTバタフライ及び乗算の実行回数を算出することによってプロセッサの製作コストを割り出し，同一能力を有する，基数2のFFTに基くプロセッサと比較してコストパフォーマンスが約2倍優れていることを示している．