Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/6755
標題: 低複雜度並列正規基底有限場乘法器之探討
Study of Low Complexity Bit Parallel Finite Field Multipliers with Normal Basis
作者: 王俊傑
Wang, Chun-Chien
關鍵字: Finite Field Multiplier
正規基底
Normal Basis
有限場乘法器
出版社: 電機工程學系
摘要: 近年來,有限場的應用範圍很廣,像是錯誤更正碼、密碼學、計算機科學方向等 。其中 ,在有限場乘法器的基本數學運算中,乘法運算是複雜度最高,且運算量最耗時間的一種。所以選擇一個硬體結構簡單且效能高的乘法器是必要的。而有限場乘法器的複雜度非常依賴有限場基底的選擇,不同的基底即會產生不同的結構與不同的複雜度,本文將提出在正規基底上所建構出的Massey-Omura乘法器,此有限場乘法器依不同的硬體結構可分為位元串列式乘法器與位元並列式乘法器兩種,兩者之間的關係最主要在於空間與時間複雜度的不同,位元串列式乘法器比位元並列式乘法器具較低的空間複雜度,但時間複雜度卻相對增加,而位元並列式乘法器雖需要比位元串列式乘法器更多的硬體空間,但其運算時間可因此降低,兩者之間是成反比關係,在本文中我們會探討到乘法器結構上冗餘的問題 ,以及四種並列式正規基底乘法器的冗餘結構,因此可借由位元並列式乘法器的冗餘來減少乘法函數矩陣的空間複雜度,而達到空間複雜度與時間複雜度之間的妥協 。
Recently, the applications of finite field is widely applied in many areas, such as error correcting codes, cryptography, and computer science. Multiplication has large complexity and enormous time consuming among the basic arithmetic operations in finite field multiplier. Therefore, to choose a finite field multiplier with simple architecture and high efficiency is necessary. The complexity of finite field multiplier is closely related to the choice of a basis in finite field. The selection of finite field bases results in different construction and complexity for the multiplier. We will study the Massey-Omura multiplier over normal bases and propose some variations of it. The finite field multipliers can be roughly classified into two categories: bit series multiplier and bit parallel multiplier. The main difference between bit series and bit parallel multipliers is their area and time complexity. Though the area complexity of bit series multiplier is lower than bit parallel multiplier, the time complexity of bit series multiplier is increased. On the other hand, bit parallel multiplier has higher area complexity with high speed. The redundancy problem and redundancy construction of bit parallel multiplier over normal basis will be addressed in the paper. We will discuss two previous constructions and proposed two new normal basis multipliers. The area complexity of two new bit parallel multipliers can be reduced by the redundancy of key function and we can trade off the area complexity and time complexity.
URI: http://hdl.handle.net/11455/6755
Appears in Collections:電機工程學系所

文件中的檔案:

取得全文請前往華藝線上圖書館



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