通用式GF(2m)乘法器
Unified Parallel Systolic Multiplier Over GF(2^m)
-
摘要: 近些年来,有限场数值运算被广泛应用在编码理论、计算机密码、数字讯号处理, 逻辑设计, 和随机数产生器等领域上,受到相当大注意。在有限场的各种运算之中,以加法运算最为简单,而以乘法、指数、及找乘法反元素等运算较为复杂。然而有限场GF(2m)的运算,由于无进位问题必须处理,因此较有限场GF(P)或GF(Pm)中的运算简单而且应用较广。在这些有限场数值运算中最重要的运算动作为乘法运算,因为加法和减法运算只是简单的互斥运算,而更复杂的运算如除法、指数运算、和反元素运算都可以利用乘法的反复运算来解决,因此乘法运算可说是有限场数学最核心之运算动作,乃成重要的研究主题。由于有限场元素的表示法会直接影响到执行的效率,所以有许多专家学者专注在不同的元素表示法,这其中有三种最常被用到的表示法为(1)多项式基底(Polynomial Basis (PB))表示法,(2)正规基底(Normal Basis (NB))表示法,和(3)双重基底(dual basis (DB))表示法。有许多的学者相继设计了多种的位并列心脏收缩乘法器,值得注意,依据不同的元素表示法,GF(2m)乘法具有不同的算法与电路架构,因此对于使用者来说是不是很实用的。因此设计的乘法电路能够适用于不同的基底表示法,此电路称为通用式乘法电路,是值得研究的主题。Hankel矩阵是广泛地应用于数字信号处理之数据处理运算单元,如乘法与除法。为了克服GF(2m)的各种基底乘法之缺点,即传统的GF(2m)乘法器是依据单一基底表示法来设计有效率的电路架构,本文依据Hankel矩阵架构与特性,提出Hankel矩阵乘法也设计成位并列心脏收缩架构,我们也证明GF(2m)的各种基底乘法均能表示成Hankel矩阵乘法,与传统乘法相比,提出的通用式乘法具有最低复杂度电路架构。Abstract: In general, there are three popular basisrepresentations, standard (canonical, polynomial) basis, normal basis,and dual basis, for representing elements in \it GF(2^m). Variousbasis representations have their distinct advantages and have theirdifferent associated multiplication architectures. In this paper, wewill present a unified systolic multiplication architecture, byemploying Hankel matrix-vector multiplication, for various basisrepresentations. For various element representation in \it GF(2^m),we will show that various basis multiplications can be performed byHankel matrix-vector multiplications. A comparison with existing andsimilar structures has shown that the proposed architectures performwell both in space and time complexities.