文献

J-GLOBAL ID：201202247244508378   整理番号：12A0425308

任意の有限体上の円分高速Fourier変換のアルゴリズム及び複雑性に関して

On Algorithms and Complexities of Cyclotomic Fast Fourier Transforms Over Arbitrary Finite Fields

著者 (3件)： WU Xuebin (Lehigh Univ., PA, USA) ,  WANG Ying (New Jersey Res. Center of QUALCOMM Corporate Res. and Dev., NJ, USA) ,  YAN Zhiyuan (Lehigh Univ., PA, USA)
資料名： IEEE Transactions on Signal Processing  (IEEE Transactions on Signal Processing)
巻： 60  号： 3  ページ： 1149-1158  発行年： 2012年03月 
JST資料番号： C0228A  ISSN： 1053-587X  CODEN： ITPRED  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 有限体上の離散Fourier変換(DFTs)は暗号法及び誤り制御符号において幅広く使われており,最近提案された円分高速Fourier変換(CFFTs)はその低複雑性のために多くの関心を受けている。CFFTsの開かれた問題は現存するものが全て特性-2有限体用である事と計算複雑性の理論的試験がなされていない事である。本論文において,筆者らはこの2つの課題を論じ,その主要な貢献は以下である。1)Toeplitz行列ベクトル積(TMVPs)を計算するための効率的な双線形アルゴリズムを提案した。これは全ての有限体上で動作する。2)文献中の素数長を有した循環性畳み込みアルゴリズムを任意の有限体に対して拡張した。Toeplitz行列及びベクトルの積として循環性畳み込みを再定式化した。3)任意の有限体上のCFFTsの乗法及び加法複雑性に関する限界を導出した。

シソーラス用語： 高速Fourier変換 ,  *Toeplitz行列 ,  *ベクトル ,  *積算 ,  循環 ,  畳込み ,  アルゴリズム ,  限界
準シソーラス用語： *円分高速Fourier変換 ,  加法 ,  拡張 ,  *計算複雑性 ,  乗法 ,  *有限体【代数系】 ,  離散Fourier変換

分類 (4件)： 解析学  (AB05000M) ,  代数学  (AB02000R) ,  信号理論  (ND02020G) ,  符号理論  (ND02030R)

タイトルに関連する用語 (5件)： 有限体 ,  円 ,  高速Fourier変換 ,  アルゴリズム ,  複雑性