(35.175.212.130) 您好!臺灣時間:2021/05/17 21:20
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:李秋瑩
研究生(外文):chiou-yng lee
論文名稱:有限場GF(2^m)乘法與指數運算之低複雜位元並列式心臟收縮電路架構
論文名稱(外文):Low-Complexity Bit-Parallel Systolic Architecture for Computing Multiplication and Exponentiation over Finite Field GF(2^m)
指導教授:盧而輝
指導教授(外文):erl-huei lu
學位類別:博士
校院名稱:長庚大學
系所名稱:電機工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:英文
論文頁數:124
中文關鍵詞:有限場乘法心臟收縮陣列全一多項式等距多項式三項多項式
外文關鍵詞:finite fieldmultiplicationsystolic arrayAOPESPtrinomial
相關次數:
  • 被引用被引用:0
  • 點閱點閱:342
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在目前,有限場 GF(2m) 是研究錯誤控制編碼、密碼技術及數位信號處理的有效工具。在有限場的各種運算中,以乘法及求反元素運算最為複雜;然而GF(2m)的運算卻較一般GF(p)或GF(pm)簡單且應用較多。舉凡二進位BCH碼 (Binary BCH Code) 之解碼、RS碼 (Reed-Solomon Code) 之編碼與解碼及在安全通信上數位信息的加密與解密,若在GF(2m)中執行運算將可達到快速與簡化系統電路的目的,是以GF(2m) 的使用較多也較為重要。
儘管如此,GF(2m)的乘法及求指數的運算仍然相當複雜。針對GF(2m)中的乘法運算陸續有學者提出快速演算法及快速電路來實現。其中,亦有部份論文和本論文的背景相同,都是針對全一多項式(all-one polynomial, AOP)、等距多項式(equally-spaced polynomial, ESP)的特性來發展快速低複雜性乘法演算法。由於目前所提出的AOP及ESP乘法器並非心臟收縮陣列電路,故電路動作時必須等到前一筆資料運算完成後才能輸入下一筆資料。因此電路的輸出速度 (throughput) 不高。
本文分五個章節探討有現場GF(2m)上設計乘法及指數的運算之心臟收縮電路,這些電路是依據不可分解的AOP、ESP及三項多項式(Trinomials, xm+xn+1)。在第三章探討利用兩個運算,內積乘法及元素循環,來設計乘法及指數的運算之心臟收縮電路。藉由第三章內積運算原理,於第四章提出AB2+C乘法心臟收縮電路。為了提昇乘法器執行速度及適用於較大有現場之計算,第五章提出模組化之乘法心臟收縮電路。第六章利用以上章節所探討的心臟收縮乘法器來設計心臟收縮指數運算器。第七章提出位元置換原理來設計心臟收縮乘法器,其有現場GF(2m)是由不可分解的三項多項式xm+xn+1產生的。以上所述探討心臟收縮電路,對於電路複雜度及計算速度均優於傳統心臟收縮電路,因此本文所提出的乘法器及指數運算是很適合實現於VLSI電路上。
Finite field arithmetic has been extensively applied in error control coding [7] and cryptography, [8]. Important operations in finite fields are addition, multiplication, exponentiation, division and computing multiplicative inverse. Addition is very simple and can be implemented with an extremely simple circuit if field elements are represented in a polynomial form. The other operations are much more complex. This study focuses on the hardware implementation of fast and low-complexity multipliers over GF(2m) since computing exponentiation, division and computing multiplicative inverse can be performed by computing multiplication iteratively.
In 1984, Yeh, Reed and Truong [5] developed a parallel-in parallel-out systolic architecture to perform the operation AB+C in a general field GF(2m). Since then, many bit-parallel systolic multipliers have been proposed (see, for example,[3-5]). However, these multipliers are inefficient for cryptographic applications due to the system’s complexity. In 1989, Itoh and Tsujii [17] designed two low-complexity multipliers for the class of GF(2m), based on the irreducible all one polynomial (AOP) of degree m and the irreducible equally spaced polynomial (ESP) of degree m, to reduce the system’s complexity. Later, Hasan, Wang and Bhargava [21] developed an ESP-based multiplier using small-scale AOP-based multipliers as the processing units. Recently, Koc and Sunar [18] presented low-complexity bit-parallel canonical and normal basis multipliers based on an AOP. Wu et al. [20] also proposed low-complexity bit-parallel multipliers using weakly dual basis. Drolet [22] introduced a representation based on an isomorphism from GF(2m) into the residue polynomial ring modulo xn+1. With this representation, he presented a serial multiplier and claimed that it is comprised of the least number of gates of all serial multipliers. Although the above low-complexity multipliers adequate for secure cryptosystem applications, none of them is designed with a systolic technique. Accordingly, the computation delay for multiplications over GF(2m) is very long if m is large.
The bit-parallel systolic architectures for computing multiplication and exponentiation over a class of fields GF(2m) were presented in this thesis. In Chapter 3, two operations, called the cyclic shifting and the inner product, are defined by the properties of irreducible all one polynomials. An effective algorithm is proposed for computing multiplications over a class of fields GF(2m) using the two operations. Then, two low-complexity bit-parallel systolic multipliers are presented based on the algorithm. An algorithm for computing AB2+C over a finite field GF(2m) in Chapter 4 is presented using the properties of the irreducible all one polynomial of degree m. In Chapter 5, it has shown that if, for a certain degree, an irreducible ESP of a large degree can be obtained from a corresponding irreducible AOP of a extremely small degree. A small AOP-based multiplier of small size can also be applied to construct a large ESP-based multiplier, in which the root of an irreducible equally spaced polynomial of degree nr represents the elements. Then regarding complexity, the structure of an ESP-based multiplier can be applied to construct modular architecture. In Chapter 6, the designed multiplication tree, based on the characteristic of a binary tree, uses the ideal bit-parallel systolic multipliers to compute exponentiation in GF(2^m). Finally, Chapter 7 presents a bit-parallel systolic multiplier in the finite field GF(2^m) over the polynomial basis, where irreducible trinomials xm+xn+1 generate the fields GF(2^m).
As compared to the conventional systolic multipliers, the proposed multipliers were designed using systolic technology that involves a very low latency and a very high throughput, and significantly reduce the time and space complexity. Moreover, they are well suited for use in VLSI techniques.
封面
中文摘要
英文摘要
誌謝
Chpater 1 Introduction
1.1 Background
1.2 Synopsis of dissertation
Chpater 2 Finite Field GF(2'''''')
2.1 Representation of field elements
2.2 Constructing finite fields
2.3 Multiplication in standard basis
Chapter 3 Bit-Parallel Systolic Multipliers for GF(2'''''') Fields Defined by All One and Equally-Spaced Polynomials
3.1 Preliminaries
3.2 Algorithm
3.3 AOP-Based Multipliers
3.3.1 Multiplier 1
3.3.2 Multiplier 2
3.4 ESP-Based Multipliers
3.5 Comparisons and Discussion
Chpater 4 Systolic Architectrues for Low-Complexity Bit-Parallel Multipliers for Computing AB2+C Multiplication''s in a GF (2m) Class Field
4.1 Introduction
4.2 Matematic background
4.3 Algorithm
4.4 Hardware Implementation
4.5 Comparisons and Conclusions
Chapter 5 Bit-Parallel Systolic Modular Multipliers for a Class fo GF(2m)
5.1 Proposed multiplication algorithm via an irreducible AOP
5.2 Structure and complexity
5.3 ESP-Based Multipliers
5.3.1 Multiplication
5.3.2 Final reduction polynomial (denoted FRP)
5.3.3 Structure and complexity
5.4 Summary
Chapter 6 Bit-Parallel Systolic Architecture for Computing Exponentiation
6.1 Parallel squaring algorithm based on the AOP
6.2 Hardware implementation for computing AOP-based exponentiation
6.2.1 Input modulus unit
6.2.2 Full parallel binary multiplier tree unit
6.2.3 Modular unit
6.3 Performance analysis
6.4 Conclusions
Chapter 7 Efficient design of bit-parallel systolic multiplier for irreducible trinomials
7.1 Introduction
7.2 Mathematical background
7.3 New multiplication algorithm
7.3.1 Realized multiplication algorithm
7.3.2 Reduction procedure
7.4 Hardware implementation
7.5 Conclusions
Chapter 8 Conclusions and future research work
8.1 Summary and main contribution
8.2 Suggestion for future research
Bibliography
[1]H. Kung, “Why Systolic Architectures?,” Computer, Vol. 15, PP. 37-46, 1982.
[2]H. Kung, “Let’s Design Algorithms for VLSI,” Proceeding Caltech Conference on VLSI: Architecture, Design, Fabrication, PP.65-90, 1979.
[3]S. W. Wei, "A Systolic Power-Sum Circuit for GF(2m)," IEEE Trans. on Computers, Vol. 43, No. 2, PP. 226-229, Feb. 1994.
[4]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.
[5]C. S. Yeh, S. Reed, and T.K. Truong, "Systolic Multipliers for Finite Fields GF(2m)," IEEE Trans. on Computers, Vol. C-33, PP. 357-360, Apr. 1984.
[6]C. L. Wang, “Bit-Level Systolic Array for Fast Exponentiation in GF(2m),” IEEE Trans. on Computers, Vol. 43, No. 7, PP. 838-841, Jul. 1994.
[7]E. R. Berlekamp, Algebraic Coding Theory, New York: McGraw-Hill,1968.
[8]D. E. R. Denning, Cryptography and Data Security. Reading, MA: Addison-Wesley, 1983.
[9]A. M. Odlyzko, "Discrete Logarithms in Finite Fields and Their Cryptographic Significance, "Proc. Eurocrypt ’84, PP. 224-314, Apr. 1984.
[10]W. Diffe and M. Hellman, "New directions in cryptography," IEEE Trans. Inform. Theory, Vol. IT-22, PP. 644-654, 1976.
[11]C. Paar and P. S. Rodriguez, “A New Class of Fast Finite Architectures for Public-Key Algorithms,” Advances on Crytpography, Eurocrypt ’97, pp. 363-378, Springer-Verlag, 1997.
[12]C.L. Wang and J.H. Guo, "New Systolic Arrays for AB2+C, Inversion, and Division in GF(2m), " IEEE Trans. Computers, Vol. 49, No. 10, PP. 1120-1125, Oct. 2000.
[13]J. Omura and J. Massey, “Computational Method and Apparatus for Finite Fields,” U.S. Patent Number 4,587,627, May 1986.
[14]J. J. Wonziak, "Systolic Dual Basis Serial Multiplier," IEE Proc.-Comput. Digit. Tech., Vol. 145, No. 3, PP. 237-241, May 1998.
[15]A. Pincin, "A New Algorithm for Multiplication in Finite Field," IEEE Trans. on Computers, No. 7, PP. 1045-1049, Jul. 1989.
[16] A.J. Menezes, Application of Finite Fields, Norwell: Massachusetts 02061 USA.
[17]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.
[18]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, Mar. 1998.
[19]H. Wu, and M. A. Hasan, "Low-Complexity Bit-Parallel Multipliers for a Class of Finite Fields," IEEE Trans. on Computers, Vol. 47, No. 8, PP. 883-887, Nov. 1998.
[20]H. Wu, M. A. Hasan, and L. 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, Nov. 1998.
[21]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. 41, No. 8, PP. 962-971, Aug. 1992.
[22]G. Drolet, "A New Representation of Elements of Finite Fields GF(2m) yielding small complexity arithmetic," IEEE Trans. on Computers, Vol. 47, No. 9, PP. 938-946, Sep. 1998.
[23]G. Seroussi, “Table of Low-Weight Binary Irreducible Polynomials,” http://www.hpl.hp.com/techreports/98/HPL-98-135.html.
[24]M.A. Hasan, M. Wang, and V.K. Bhargava, " A Modified Massey-Omura Multiplier for a Class of Finite Fields", IEEE Trans. on Computers, Vol. C-41 , No.8, PP.962-972, Aug. 1992.
[25]B. Sinar and C.K. Koc, "Mastrovito Multiplier for All Trinomials," IEEE Trans. on Computers, Vol. 48, No. 5, PP. 522-527, May. 1999.
[26]A. Halbutogullari and C.K. Koc, "Mastrovito Multiplier for General Irreducible Polynomials," IEEE Trans. on Computers, Vol. 49, No. 5, PP. 503-518, May. 2000.
[27]Y. R. Shayan, Tho Le-Ngoc, and V.K. Bhargava, "Binary-Decision Approach to Fast Chien Search for Software Decoding of BCH codes", IEE Proc., Vol. I34, Pt. F, No.6, PP. 629-632, 1987.
[28]T.C. Batee and D.I. Schneider, “Computation with Finite Field,” information and computers, Volume 6, PP. 79-98, Mar. 1963.
[29]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. C-42 , PP.1010-1015, 1993.
[30]P.A. Scott, S.E. Tavares, and L.E. Peppard, "A Fast VLSI Multiplier for GF(2m)," IEEE Trans. on Selected Area in Commun. SAC-4, PP. 62-66, 1986.
[31]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, pp. 578-586, Apr. 1988.
[32]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.
[33]G. L. Feng, "A VLSI Architecture for Fast Inversion in GF(2m)," IEEE Trans. on Computers, Vol. 38, No. 10, PP. 1383-1386, Oct. 1989.
[34]M.A Hasan and V.K. Bhargava, "Bit-Serial Systolic Divider and Multiplier for Finite Fields GF(2m)," IEEE Trans. on Computers, No. 8, PP. 972-980, Aug. 1992.
[35]D. E. R. Denning, Cryptography and Data Security, Reading, MA: Addison-Wesley, 1983.
[36]M. Y. Rhee, Cryptography and Secure Communications, McGraw-Hill, Singapore, 1994.
[37]C.L Wang and J.H. Guo, "New Systolic Arrays for C+AB2, Inversion, and Division in GF(2m)," IEEE Trans. Computers, Vol. C-49 , No.10, PP.1120-1125, Oct. 2000.
[38]J. H. Guo and C. L Wang, "A new systolic squarer and its application to compute exponentiations in GF(2m)," IEEE intern. Symp. on CS, pp. 2044-2047, Jun. 1997.
[39]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, Mar. 1998.
[40]A. Ghafoor and A. Singh, "Systolic architecture for finite field exponentiation," IEE proc. Vol. 136, Pt. E, no. 6, pp. 465-470, Nov. 1989.
[41]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. computers vol. C-39, pp. 258-262, Feb. 1990.
[42]S.K. Jain, L. Song, and K.K. Parhi, "Efficient semi-systolic architectures for finite field arithmetic," IEEE Trans. Computers, No. 6, pp. 101-113, Mar. 1998.
[43]B.B Zhou, "A new bit-serial systolic multiplier over GF(2m)," IEEE Trans. Computers, No. 6, pp. 749-751, June. 1988.
[44]C.W. and M.K. Chang, "Bit-level systolic arrays for finite field multiplications," Journal of VLSI Signal Processing, pp.85-92, June 1995.
[45]Chiou-Yng Lee, Erl-Huei Lu, and Jau-Yien Lee "Bit-Parallel Systolic Multipliers for GF(2m) Fileds Defined by All-One and Equally-Spaced Polynomials," IEEE Transaction on Computers, pp. 385-393, May 2001.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top