臺灣博碩士論文加值系統

使用有限體GF(2m)的算術運算能夠簡化電路複雜性與增快速度，所以依據其理論之架構已逐漸吸引相關學者進行研究，並廣泛應用於編碼、解碼與密碼通信上。然現有的有限體GF(2m)研究所使用的乘法、除法和反元運算仍需要不少的計算時間和龐雜的電路；因此，本研究即旨在GF(2m)上發展創新之細胞陣列快速乘法器架構，冀以有效簡化電路與增快計算速度。
本研究係在GF(2m)上利用全一多項式(All-One Polynomial, AOP)執行AB2乘法之有效率細胞陣列架構。首先，本研究使用AOP的特性，提出一個有效計算AB2的內積乘法定理與對應架構，接著再探討經由適當的排列對映將可使AB2乘法器亦能執行一般的AB乘法運算。其次，本研究依據在有限體GF(2m)之上不能分解的AOP提出兩個創新的位元-平行的細胞陣列乘法器架構，並與傳統之細胞陣列乘法器作完整之比較。最後，擴大細胞陣列為管線(Pipeline)架構以計算指數、反元和除法，此利於設計超大的有限體的平行乘法器。本研究所提出的乘法器具有高度規則性、模組化、和適於VLSI實作的特性，用於有限體的乘法和指數運算更有效率。相關的細胞陣列架構的比較顯示所提出的乘法器比傳統的乘法器具有更簡單的電路複雜性與更快的計算時間。

封面
Chapter 1 Introduction
Chapter 2 Related works
Chapter 3 Proposed Inner-product multiplication theorem
Chapter 4 Proposed bit-paralle cellular multiplier
Chapter 5 Pipeline architecture fo exponentiation in GF(2m)
Chapter 6 Pipeline architecture for multiplicatvie inversions/divisions
Chapter 7 Conclusions
Bibliography
Publications

[1] T. Itoh and S. Tsujii, “Structure of parallel multipliers for a class of fields GF(2m),” Information and Computation, vol. 83, pp. 21-40, 1989.
[2] C.K. Koc and B. Sunar, “Low complexity bit-parallel canonical and normal basis multipliers for a class of finite fields,” IEEE trans. on computers, vol. 47, no. 3, pp. 353-356, 1998.
[3] H. Wu, M. A. Hasan, and Lan F. Blake, “New low-complexity bit-parallel finite field multipliers using weakly dual bases,” IEEE trans. on computers, vol. 47, no. 11, pp. 1223-1234, 1998.
[4] B.A. Laws, Jr, and C.K. Rushforth, “A cellular-array multiplier for GF(2m),” IEEE trans. on computers, vol. C-20 , pp. 1573-1578,1971.
[5] C. C. Wang and D. Pei, “A VLSI design for computing exponentiations in GF(2m) and its application to generate pseudorandom number sequences,” IEEE trans. on computers, vol. C-39, pp. 258-262, Feb. 1990.
[6] Shyue-Win Wei, “A systolic power-sum circuit for GF(2m),” IEEE trans. on computers, vol. 43, no. 2, pp. 226~229, 1994.
[7] Shyue-Win Wei, “VLSI architectures for computing exponentiations, multiplicative inverses, and divisions in GF(2m),” IEEE trans. on circuits and systems-II, vol. 44, no. 10, pp.847-855, Oct. 1997.
[8] Jiri Adamek, “Foundations of Coding: theory and application of error-correcting codes, with an introduction to cryptography and information theory,” John Wiley & Sons, 1991.
[9] C. C. Wang, T. K. Truong, H. M. Shao, L. J. Dentsh, J. K. Omura, and I. S. Reed, “VLSI architectures for computing multiplications and inverses in GF(2m),” IEEE trans. on computers, vol. C-34, pp.709-716, 1985.
[10] C. L. Wang and J. L. Lin, “A systolic architectures for computing inverses and divisions in finite fields GF(2m),” IEEE trans. on computers, vol. 42, pp.1010-1015, 1993.
[11] P. A. Scott, S. J. Simmons, S. E. Tavares, and L. E. Peppard. “Architectures for exponentiation in GF(2m),” IEEE J. Select. Areas commun., vol.6, no.3, pp. 578-586, 1988.
[12] Shyue-Win Wei, “VLSI Architectures for Computing Exponentiations, Multiplicative Inverses, and Divisions in GF(2m),” IEEE Trans. Circuits and Systems II: Analog and Digital Processing, vol. 44, pp. 845-855, Oct. 1997.
[13] S. R. Whitaker, J. A. Canaris, and K. B. Cameron, “Reed Solomon VLSI Cosdec for advanced television,” IEEE Trans. Circuit Syst. Video Technol., vol. 1, pp. 230-236, June 1991.
[14] S. W. Wei and C. H. Wei, “A high-speed real-time binary BCH decoder,” IEEE Trans. Circuit Syst. Video Technol. vol. 3, pp. 138-147, June 1993.
[15] S. Y. Kung, VLSI Array Processors. Englewood Cliffs, NJ: Prentice-Hall, 1988.
[16] L. A. Glasser and D. W. Dobberuhl, The Design and Analysis of VLSI Circuits. Reading, MA: Addison-Wesley, 1985.
[17] T. R. N. Rao and E. Fujiwara, Error-Control Coding for Computer Systems. Eaglewood Cliffs, NJ: Prentice-Hall, 1989.
[18] A. M. Michelson and A. H. Levesqu, Error-Control Techniques for Digital Communicaion. New York: Wiley, 1985.
[19] R. E. Blahut, Theory and Practice of Error Control Codes. Reading, MA: Addison-Wesley, 1983.
[20] W. W. Peterson and E. J. Weldon, Jr., Error-Correcting Codes, Jr., Cambridge, MA: The MIT Press, 1972.
[21] S. Lin and D. J. Costellor, Jr., Error Control Coding. Englewood Cliffes, NJ: Prentice-Hall, 1983.
[22] E. R. Berlekamp, Algebraic Coding Theory, revised ed. Laguna Hills, CA: Aegean Park, 1984.
[23] Jyh-Huei Guo and Chin-Liang Wang, “A Low Time-Complexity, Hardware-efficient bit-parallel power-sum circuit for finite fields GF(2m),” IEEE International Symposium on Circuit and Systems 1999 (ISCAS’99), vol. 1, pp.521-524.
[24] D. R. Stinson, Cryptography: Theory and Practice. CRC Press, 1995.
[25] B. Schneier, Applied Cryptography, New-York: Wiley, 1996.
[26] C.-S. Yeh, I.S.Reed, and T.K.Truong, “Systolic multipliers for finite field GF(2m),” IEEE Trans. Comput., vol. C-33, pp. 357-360, 1984.
[27] C.-L. Wang and J.-H. Guo, “New systolic arrays for C+AB2, inversion, and division in GF(2m),” in Proc. 1995 European Conference Circuit Theory Design (ECCTD’95), Istanbul, Turkey, Aug. 1995, pp. 431-434.
[28] Jyh-Huei Guo and Chin-Liang Wang, “A new systolic architecture for fast exponentiation in GF(2m),” in Proc. 1995 Int. Sym. Communications (ISCOM), Taipei, Taiwan, Dec. 1995, pp.521-524.
[29] R. Furness, M. Benaissa, S.T.J. Fenn, “Circuit architectures for semi-bit-serial and programmable arithmetic in finite fields,” 1998 IEEE International Conference on Electronics, Circuits and Systems, vol. 3, 1998, pp. 415-418.
[30] J. L. Massey and J. K. Omra, “Computational method and application for finite field arithmetic,”U.S. Patent Application, submitted 1981.
[31] E. R. Belekamp, “Bit-serial Reed-Solomon encoders,” IEEE Trans. Inform. Theory, vol. IT-28, pp. 869-874, 1982.
[32] M. A. Hasan and V. K. Bhagava, “Division and bit-serial multiplication over GF(qm),” IEE Proceedings-E, vol. 139, no. 3, pp. 230-236, May 1992.
[33] C. Paar, “A new architecture for a parallel finite field multiplier with low complexity based on composite fields,” IEEE Trans. Computers, vol. 45, o.7, pp. 856-861, July 1996.
[34] Michael Orchard, “Fast bit-reversal algorithms based on index representations in GF(2b),” IEEE International Symposium on Circuits and Systems, vol.3, 1989, pp. 1903-1906)
[35] R. Lidl and H. Niederreiter, Finite Fields. Reading, Mass.: Addison-Wesley, 1983.
[36] I. S. Hsu, T. K. Truong, L. J. Deutsch, and J. S. Reed “A Comparison of VLSI Architecture of Finite Fields Multipliers Using Dual, Normal, or Standard Bases,” IEEE Trans. Computers, vol. 37, no. 6, pp. 735-739, June 1988.
[37] R.Barua, S.Sengupta, “Architectures for arithmetic over GF(2m),” VLSI Design, 1997. Proceedings., Tenth International Conference on , 1997, pp. 465-468.
[38] M.A. Hasan, M. Z. Wang, and V.K. Bhargava, “Modular construction of low complexity parallel multipliers for a class of finite fields GF(2m),” IEEE trans. on computers, vol. C-41, pp. 962-971, Aug. 1992.
[39] M.A. Hasan, M. Z. Wang, and V.K. Bhargava, “A modified Massey-Omura multiplier for a class of finite fields,” IEEE trans. on computers, vol. 42, no. 10, pp. 1278-1280, Oct. 1993.
[40] P. K. S. Wah and M. Z. Wang, “Realization and application of the Massey-omura lock,” presented at the Int. Zurich Semp., 1984.
[41] W. Drescher and G. Fettweis, “VLSI Architectures for Multiplication in GF(2m) for Application Tailored Digital Signal Processors,” IEEE VLSI Signal Processing, IX, 1996, pp.55-64.
[42] H. M. Shao and I. S. Reed, “On the VLSI design of a pipeline Reed-Solomon decoder using systolic arrays,” IEEE Trans. Comput., vol. C-37, pp. 1273-1280, 1988.
[43] S. K. Jain, L. Song, and K. K. Parhi, “Efficient Semi-Systolic Architectures for Finite Field Arithmetic, ” IEEE Trans. On VLSI Systems, vol. 6, no. 1, pp. 101-113, March 1998.
[44] M.Pontas, “Algorithm for squaring in GF(2m) in standard basis,” Electronics Letters, 31st August 1989 vol. 25, no. 18, pp. 1262-1263
[45] A. J. Menezes, ed, Applications of Finite Fields. Boston: Kluwer Academic, 1993.
[46] H.Y.H Chuang, and G. He, “Design of problem-size independent systolic arrays systems,” Proc. IEEE Int. Conf. ICCD’84, Port Chester, New York, USA, 152-156, 1984.
[47] Shyue-Win Wei, “Power-sum circuit for finite fields GF(2m),” United States Patent, Patent Number: 5,931,894, Aug. 3, 1999.
[48] A. M. Odlyzko, “Discrete logarithms in finite fields and their cryptographic significance,” in Adv. Cryptol., Proc. Eurocrypt '84, Paris, France, April 1984, pp.224-314.
[49] D.E. Knuth, “The Art of Computer Programming,” vol. 2, Seminumerical Algorithms, Reading, MA: Addison-Wesley, 1969.
[50] Chin-Liang Wang, “A Systolic Exponentiator for finite fields GF(2m),” Proceedings of the 34th Midwest Symposium on Circuits and Systems, 1992, pp. 279-282 vol.1
[51] H. T. Kung and M. Lam, “Fault tolerance and two level pipelining in VLSI systolic arrays,” in Proc. MIT Conf. Advanced Res. VLSI, Cambridge, MA, Jan. 1984, pp.74-83.
[52] P. A. Scott, S. E. Tavares, and L. E. Peppard. “A fast VLSI multiplier for GF(2m),” IEEE J. Select. Areas commun., vol. SAC-4, pp. 62-66, Jan. 1986.
[55] -, “Division and bit-serial multiplication over GF(2m),” IEE Proc. -E, vol. 139, pp. 230-236, May 1992.
[53] G. K. Maki, K. B. Gameron, and P. A. Owsley, “High-speed real-time Ree-Solomon decoder,” U.S. Patent 487 368 3, Oct. 1989.
[54] K. Araki, I. Fujita, and M. Morisue, “Fast inverter over finite field based on Euclid’s algorithm,” Tans. IEICE, vol. E-72, pp. 1230-1234, Nov. 1989.
[56] D. E. R. Denning, Cryptography and Data Security, Reading, MA: Addison-Wesley, 1983.
[57] Yuh-Tsuen Horng and Shyue-Win Wei, “Fast Inverters and Dividers for Finite Field GF(2m)”, 1994 IEEE Asia-Pacific Conference on Circuits and Systems (APCCAS), 1994, pp. 206-211.
[58] H. Brunner, A. Curiger, and M. Hofstetter, “On computing multiplicative inverses in GF(2m), ” IEEE Trans. Comput., vol. 42, no. 8, pp. 1010-1015, Aug. 1993.
[59] G. I. Davida., “Inverse of elements of a Galois field, ” Electron. Lett., vol. 8, pp. 518-520, Oct. 1972.