Importance

Loading Importance Indicators...

Abstract

A Galois field multiplier for GF(2.sup.n), with n=2m, multiplies two n-bit polynomials to produce a(x)*b(x)=a(x)b(x) mod g(x), where g(x) is a generator polynomial for the Galois field and '*' represents multiplication over the Galois field, by treating each polynomial as the sum of two m-bit polynomials: a(x)=a.sub.H (x)x.sup.m +a.sub.L (x) and b(x)=b.sub.H (x)x.sup.m +b.sub.L (x), with a.sub.H (x)x.sup.m =[a.sub.n-1 x.sup.(n-1)-m +a.sub.n-2 x.sup.(n-2)-m + . . . +a.sub.m+1 x.sup.(m+1)-m +a.sub.m ]x.sup.m a.sub.L (x)=a.sub.m-1 x.sup.m-1 +a.sub.m-2 x.sup.m-2 + . . . +a.sub.2 x.sup.2 +a.sub.1 x+a.sub.0 and b.sub.H and b.sub.L having corresponding terms. Multiplying the two polynomials then becomes: a(x)*b(x)=(a.sub.H (x)x.sup.m +a.sub.L (x))*(b.sub.H (x)x.sup.m +b.sub.L (x))=[(a.sub.H (x)b(x).sub.H)x.sup.m mod g(x) +(b.sub.H (x)a.sub.L (x)+a.sub.L (x)b.sub.L (x))]x.sup.m mod g(x)+a.sub.L (x)b.sub.L (x). The Galois field multiplier produces four degree-(n-2) polynomial products, namely, a.sub.H (x)b.sub.H (x)=V.sub.3 ; b.sub.H (x)a.sub.L (x)=V.sub.2 ; a.sub.H (x)b.sub.L (x)=V.sub.1 ; and a.sub.L (x)b.sub.L (x)=V.sub.0, in parallel in four m-bit polynomial multipliers. Next, a modulo subsystem multiplies V.sub.3 by x.sup.m and performs a modulo g(x) operation on the product V.sub.3 x.sup.m by treating V.sub.3 as V.sub.3H x.sup.m +V.sub.3L, with V.sub.3H including as a leading term 0x.sup.n-1. The modulo operation is performed by appropriately cyclically shifting (m-(k-2)) versions of an n-bit symbol that consists of the coefficients of V.sub.3H followed by m zeros, summing the results and adding the sum to an n-bit symbol that consists of the coefficients of V.sub.3L, V.sub.3H. The Galois field multiplier for GF(2.sup.n) with n=2m+1 operates in essentially the same manner, with a.sub.L and b.sub.L each including m+1 terms.

Loading the Abstract Image...

First Claim