Please use this identifier to cite or link to this item:
標題: 低階正規元素之改良式並列乘法器
A Modified Parallel Multiplier for Low Order Normal Elements
作者: 江家興
Jiang, Jia-Xing
關鍵字: finite field
normal basis
normal basis multiplier
出版社: 電機工程學系所
引用: [1] S. Lin and D.J. Costello, Error Control Coding: Fundamentals and Applications. Prentice Hall, 1983. [2] F.J. MacWilliams and N.J.A. Sloane, The Theory of Error Correcting Codes. New York: North-Holland, 1977. [3] I.S. Reed and X. Chen, Error-Control Coding for Data Networks. Kluwer Academic Publishers, 1999. [4] W. Stallings, Cryptography and Network Security: Principles and Practices. Prentice Hall, 2003. [5] C.C. Wang, T.K. Truong, H.M. Shao, L.J. Deutsch, J.K. Omura, and I.S. Reed, "VLSI Architectures for Computing Multiplications and Inverses in ," IEEE Trans. Computers, vol. 34, no. 8, pp. 709- 716, Aug. 1985. [6] A. Reyhani-Masoleh and M.A. Hasan,"A New Construction of Massey-Omura Parallel Multiplier over ," IEEE Trans. Computers, vol. 51, no. 5, pp. 511-520, May 2002. [7] R.C. Mullin, I.M. Onyszchuk, S.A. Vanstone, and R.M. Wilson,"Optimal Normal Bases in ," Discrete Applied Math., vol. 22, pp. 149-161, 1988/1989. [8] M.A. Hasan, M.Z. Wang, and V.K. Bhargava, "A Modified Massey-Omura Parallel Multiplier for a Class of Finite Fields," IEEE Trans. Computers, vol. 42, no. 10, pp. 1278-1280, Oct. 1993. [9] I.S. Hsu, T.K. Truong, L.J. Deutsch, and I.S. Reed, "A Comparison of VLSI Architectures of Finite Field Multipliers Using Dual, Normal or Standard Bases, " IEEE Trans. Computers, vol. 37, no. 6, pp. 735-739, June 1988. [10] E.D. Mastrovito, "VLSI Architectures for Computation in Galois Fields, " PhD thesis, Linkoping Univ., Linkoping, Sweden, 1991. [11] A. Halbutogullari and C.K. Koc, "Mastrovito Multiplier for General Irreducible Polynomials," IEEE Trans.Computers, vol. 49, no. 5, pp. 503-518, May 2000. [12] S.T.J. Fenn, M. Benaissa, and D. Taylor, " Multiplication and Division Over the Dual Basis," IEEE Trans. Computers, vol. 45, no. 3, pp. 319-327, Mar.1996 [13] H. Wu, M.A. Hasan, and I.F. Blake, "New Low-Complexity Bit-Parallel Finite Field Multipliers Using Weakly Dual Bases," IEEE Trans. Computers, vol. 47, no. 11, pp. 1223-1234, Nov. 1998. [14] B. Sunar and C.K. Koc, "Mastrovito Multiplier for All Trinomials," IEEE Trans. Computers, vol. 48, no. 5, pp. 522-527, May 1999. [15] M. Elia, M. Leone, and C. Visentin, "Low Complexity Bit-Parallel Multipliers for with Generator Polynomial ," Electronics Letters, vol. 35, no. 7, pp. 551-552, Apr. 1999. [16] M.A. Hasan, M.Z. Wang, and V.K. Bhargava, "Modular Construction of Low Complexity Parallel Multipliers for a Class of Finite Fields ," IEEE Trans. Computers, vol. 41, no. 8, pp. 962-971, Aug. 1992. [17] C.K. Koc and B. Sunar, "Low-Complexity Bit-Parallel Canonical and Normal Basis Multipliers for a Class of Finite Fields," IEEE Trans. Computers, vol. 47, no. 3, pp. 353-356, Mar. 1998. [18] H. Wu and M.A. Hasan, "Low Complexity Bit-Parallel Multipliers for a Class of Finite Fields," IEEE Trans. Computers, vol. 47, no. 8, pp. 883-887, Aug. 1998. [19] C. Paar, "A New Architecture for a Parallel Finite Field Multiplier with Low Complexity Based on Composite Fields," IEEE Trans. Computers, vol. 45, no. 7, pp. 856-861, July 1996. [20] C. Paar, P. Fleishmann, and P. Roelse, "Efficient Multiplier Architectures for Galois Fields ," IEEE Trans. Computers, vol. 47, no. 2, pp. 162-170, Feb. 1998. [21] J.L. Massey and J.K. Omura, "Computational Method and Apparatus for Finite Field Arithmetic," US Patent Number 4,587,627, May 1986. [22] B. Sunar and C.K. Koc, "An Efficient Optimal Normal Basis Type II Multiplier," IEEE Trans. Computers, vol. 50, no. 1, pp. 83-88, Jan. 2001 [23] M. Elia and M. Leone, "On the Inherent Space Complexity of Fast Parallel Multipliers for ," IEEE Trans. Computers, vol. 51, no. 3, pp. 346-351, Mar. 2002.
摘要: 近年來由於通訊及網路的快速發展,使得正規基底乘法器的硬體實現已普遍被使用到各領域中。有限場元素使用正規基底表示的原因,是由於其算術運算很容易被硬體實現。Massey-Omura乘法器是以正規基底所表示的並列乘法器,至於乘法運算只需要將二個輸入同時做循環移動,即可利用m個相同邏輯電路來得到乘法積所有的位元。過去的文獻都是以全一多項式來定義有限場,Massey-Omura並行乘法器的有一些多餘或重複的運算,在其它文獻都已提出低電路複雜度之改良式硬體架構。在本論文裡,已證明不只這類型有多餘或重複的運算,任何不可分解多項式所定義的有限場,都有此類問題。在此利用低階正規元素的觀念來建構並列正規基底乘法器之硬體架構,此架構可適用於任何有限場,且和其它文獻所提的硬體架構做比較,都有明顯的改善。而且所提的硬體架構具有模組性與規則性,因此,非常適合VLSI的實現。
Recently, implementations of normal basis multiplication over the extended binary field GF(2^m) have received considerable attention. For efficient hardware implementation of finite field arithmetic units, the use of a normal basis is advantageous. The Massey-Omura multiplier of GF(2^m) uses a normal basis and its bit parallel version is usually implemented using m identical combinational logic blocks whose inputs are cyclically shifted from one another. In the past, it was shown that, for a class of finite fields defined by irreducible all-one polynomials, the parallel Massey-Omura multiplier had redundancy and a modified architecture of lower circuit complexity was proposed. In this article, it is shown that, not only does this type of multipliers contain redundancy in that special class of finite fields, but it also has redundancy in fields GF(2^m) defined by any irreducible polynomial. By removing the redundancy, we propose a new architecture for the normal basis parallel multiplier, which is applicable to any arbitrary finite field and has significantly lower circuit complexity compared to the original Massey-Omura normal basis parallel multiplier. The proposed multiplier structure is also modular and, hence, suitable for VLSI realization.
其他識別: U0005-2607200610441500
Appears in Collections:電機工程學系所



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.