ものであり，多倍長乗算を用いたアプリケーションやシステムの実現において有益 な指標となる．また，多倍長演算に関する実装技術の研究や開発，およびアプリケー ションシステムの利用促進に大きく寄与すると考えられる．
謝辞
本研究を進めるにあたり，お世話になった多くの方々に感謝いたします．
長年にわたり多くの御指導をいただいた電気通信大学情報工学科の阿部公輝助教 授に感謝いたします．また，主任指導教員として御尽力いただいた電気通信大学情報 工学科の尾内理紀夫教授に感謝いたします．FFT 乗算アルゴリズムに関して，重要 な議論をしていただいた電気通信大学情報工学科の野下浩平教授に感謝いたします．
また，FFT 乗算器に関する研究において，応用面で有益なアドバイスをいただいた 電気通信大学情報工学科の加古孝教授に感謝いたします．FFT 乗算における誤差の 見積もりに関して，多忙な時間をさいて有意義な議論をしていただいた電気通信大 学情報工学科の山本野人教授に感謝いたします．本論文の査読を通して，論文の質 を高めるために御尽力いただいた電気通信大学情報工学科の小林聡助教授に感謝い たします．日々の研究生活や本論文の作成にあたり多くのアドバイスをいただいた 電気通信大学情報工学科の楯岡孝道博士に感謝いたします．FFT の設計に関して多 くのアドバイスをいただいた NEC システムデバイス研究所の鈴木紀章博士に感謝 いたします．卒業後も筆者の研究生活をさまざまな面で支えていただいた東京工科 大学コンピュータサイエンス学部の松永俊雄教授に感謝いたします．本研究を始め るきっかけを与えていただき，その後も多倍長演算に関して様々な議論をしていた だいた東京工科大学コンピュータサイエンス学部の月江伸弘博士に感謝いたします．
最後に研究生活を支えていただいた家族と電気通信大学阿部公輝研究室の皆様に感 謝いたします．
参考文献
[1] H. Fujiwara, “High-Accurate Numerical Method for Integral Equations of the First Kind under Multiple-Precision Arithmetic,” Theoretical and Ap-plied Mechanics Japan, Vol.52, pp.193-203, 2003.
[2] M. Agrawal, N. Kayal, and N. Saxena, PRIMES Is in P, http://www.cse.iitk.ac.in/, 2002.
[3] 夛田光輝, 上島直樹, 茶谷芳裕, 鎌田弘之, “カオスシステムにおける有限桁演算 の影響度の評価について,” 第17回 回路とシステム軽井沢ワークショップ論文 集, pp.13-18, 2004.
[4] 月江伸弘, 小澤智, “カオス方程式の数値解における有効桁数の減少,” 情報処理 学会論文誌, Vol.44, No.11, pp.2778-2786, 2003.
[5] J. C. Sprott, “Chaos and time-series analysis,” Oxford University Press, 2003.
[6] Z. Dyka and P. Langendoerfer, “Area efficient hardware implementation of elliptic curve cryptography by iteratively applying Karatsuba’s method,”
Proc. of the Design, Automation and Test in Europe Conference and Exhi-bition, Vol.3, pp.70-75, May 2005.
[7] B. W.-K. Ling, C. Y.-F. Ho and P. K.-S. Tam, “Chaotic filter bank for computer cryptography,” Chaos, Solitons & Fractals, In Press, Available online 5 Jun. 2006.
[8] T.-I Chien and T.-L. Liao, “Design of secure digital communication sys-tems using chaotic modulation, cryptography and chaotic synchronization,”
Chaos, Solitons and Fractals, Vol.24, pp.241-255, 2005.
[9] D. E. Knuth, The Art of Computer Programming, Volume 2, 2nd Edition : Seminumerical Algorithms, Addison-Wesley, MA, 1981.
[10] A. Karatsuba and Y. Ofman, “Multiplication of multidigit numbers on au-tomata,” Sov. Phys. Dokl., Vol.7, pp.595-596, 1963.
[11] A. L. Toom, “The complexity of a scheme of functional elements realizing the multiplication of integers,”Sov. Math., Vol.3, pp.714-716, 1963.
[12] S. A. Cook, “On the minimum computation time of functions,” Ph.D thesis of Harvard University, Chap.III, May 1966, pp.51-77.
[13] A. Sch¨onhage, V. Strassen, Computing 1, pp.182-196, 1966.
[14] A. Sch¨onhage, V. Strassen, “Schnelle multiplikation grosser zahlen,” Com-puting 7, pp.282-289, 1971.
[15] Dan Zuras, “More on Squaring and Multiplying Large Integer,”IEEE Trans.
Computers, Vol.43, No 8, pp.899-908, Aug. 1994.
[16] exflib - Extended Precision Float-Point Arithmetic Library,
http://www-an.acs.i.kyoto-u.ac.jp/ fujiwara/exflib/exflib-index.html [17] GMP, http://www.swox.com/gmp/
[18] FFTW, http://www.fftw.org/
[19] C. S. Wallace, “A Suggestion for a Fast Multiplier,”IEEE Trans. Electronic Computers, Vol.EC-13, No.2, pp.14-17, Feb, 1964.
[20] C. Grabbe, M. Bednara, J. Teich, J. von zur Gathen, and J. Shokrollahi,
“FPGA designs of parallel high performance GF(2233) multiplier,” Proc. of the IEEE International Symposium on Circuits and Systems, pp.362-369, May 2003.
[21] L. S. Cheng, A. Miri, and T. H. Yeap, “Improved FPGA Implementations of Parallel Karatsuba Multiplication overGF(2n),” Proc. of the 22nd Biennial Symposium on Communications, Kingston, Canada, Jun. 2004.
[22] A. Weimerskirch and C. Paar, “Generalizations of the Karatsuba Algorithm for Efficient Implementaions,” Cryptology ePrint Archive, http://eprint.iarc.org/, Report 2006/224, 2006.
[23] 柴岡雅之,高木直史,高木一義, “Karatsubaアルゴリズムに基づく小面積並列乗 算,” 電子情報通信学会2005年総合大会講演論文集, Vol.A-3, Mar. p.66, 2005.
[24] Verilog DOT COM, http://www.verilog.com [25] Synopsys, http://www.synopsys.com
[26] VLSI Design and Education Center Homepage, http://www.vdec.u-tokyo.ac.jp
[27] Cadence, http://www.cadence.com
[28] 後保範, “多数桁分割乗算の高速計算法,” 情報処理学会論文誌, Vol.46, No.5, pp.1266-1273, May 2005.
[29] J. W. Cooley and J. W. Tukey, “An Algorithm for Machine Computation of
the Complex Fourier Series,” Mathematics of Computation, Vol.19, pp.297-301, Apr. 1965.
[30] 安居院 猛, 中嶋 正之, “FFTの使い方”, 秋葉出版, 1986.
[31] C. M. Fiduccia, “Fast Matrix Multiplication,” Proceedings of Third Annual ACM Symposium on Theory of Computing, pp.45-49, 1971.
[32] M. Frigo, “A Fast Fourier Transform Compiler,” ACM SIGPLAN Notices, Vol. 39, Issue 4, pp.642-655, Apr. 2004.
[33] J. van der Hoeven, “The Truncated Fourier Transform and Applications,”
Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, pp.290-296, 2004.
[34] B. M. Baas, “A Low-Power, High-Performance 1024-Point FFT Processor,”
IEEE Journal of Solid-State Circuits, Vol.34, No.3, pp.380-387, Mar. 1999.
[35] N. Miyamoto, L. Karnan, K Maruo, K. Kotani, and T. Ohmi, “A Small-Area High-Performance 512-Point 2-Dimensional FFT Single-Chip Proces-sor,” Proceedings of the 2004 Conference on Asia South Pacific Design Au-tomation : Electronic Design and Solution Fair 2004, pp.537-538, Jan. 2004.
[36] ALTERA, http://www.altera.com.
[37] “ALTERA White Paper : Floation-Point FFT Processor (IEEE754 Single Precision) Radix 2 Core,”
http://www.altera.co.jp/literature/wp/wp fft radix2.pdf.
[38] C. J. Weinstein, “Roundoff Noise in Floating Point Fast Fourier Transform computation ,” IEEE Transactions on Audio and Electroacoustics, Vol.AU-17, No.3, Sep. 1969.
[39] Tran-Thong and D. Liu, “Accumulation of Roundoff Errors in Floating Point FFT,”IEEE Transactions on Circuits and Systems, Vol.CAS-24, No.3, Mar.
1877.
[40] I. Pitas and M. G. Strintzis, “Floating Point Error Analysis of Two-Dimensional Fast Fourier Transform Algorithms,” IEEE Transactions on Circuits and Systems, Vol.35, No.1, Jan. 1988.
[41] D. C. Munson and B. Liu, “Floating Point Roundoff Error in the Prime Fac-tor FFT,” IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol.ASSP-29, No.4, Aug. 1981.
[42] Y. Ma, “An Accurate Error Analysis Model for Fast Fourier Transform,”
IEEE Transactions on Signal Processing, Vol.45, No.6, Jun. 1997.
[43] P. Henrici, Applied and Computational Complex Analysis, Vol.3, Chap.13,
John Wiley & Sons, NY, 1986.
[44] 平山 弘, “FFTによる高精度数の乗算,” 情報処理学会 研究報告 High Perfor-mance Computing, Vol.65, No.65-6, pp.27-32, 1997.
[45] J. L. Hennessy and D. A. Patterson, Computer Architecture: A Quantitative Approach, 3rd Edition, Morgan Kaufmann, CA, 2003.
[46] Intel Co., http://www.intel.com
[47] benchFFT, http://www.fftw.org/benchfft/
[48] Intel(R) Pentium(R) 4 processor specifications,
http://www.intel.co.jp/products/processor/pentium4/specs.htm
付録 A
加算回路
本章では基本的な算術演算回路である加算回路について述べる．ハードウェアで 扱う加算回路は大きく桁上げ伝搬加算器と桁上げ保存加算器に分けられる．以降，そ れぞれについて述べる．