Multiplier-adder in the Galois fields, and its use in a digital

Details Multiplier-adder in the Galois fields, and its use in a digital Multiplier-adder in the Galois fields, and its use in a digital

1989-11-03

1991-09-03

Harkcom, Gary V.

Boots, shoes, and leggings

G06F 700

Patent

active

050460374

DESCRIPTION:

BRIEF SUMMARY
The invention relates to the field of digital telecommunications, and more particularly to the digital signal processing necessary in this type of application.
Digital telecommunications are subject to interference which necessitates an efficient protection of the information by encoding using error detecting and correcting codes.
Codes which are particularly advantageous for this type of error detection and correction are the Reed Solomon (RS) or BCH type codes which provide a reasonable balance between complexity of implementation and efficiency. These codes make use of processing of polynomials with values in the Galois fields.
The French Patent Application No. 86 14677 in the name of the Applicant describes a polynomial operator in the Galois fields and a digital signal processing processor using such an operator. The central component of such an operator is a multiplier-adder circuit performing the operations of multiplication and addition of polynomials in the Galois fields. The multiplier-adder described in this application was not optimized, either with regard to the number of logic levels necessary for the computation or to the area of the operator, this resulting in too great a duration of computation and too great a size.
Furthermore there is known, from an article by B. A. LAWS Jr et al. entitled "A cellular-array multiplier for GF(2 m)", pages 1575-1578, Vol. C20, No. 12, Dec. 1971 of the IEEE Transactions on computers, a multiplier-adder of the matrix type using a breakdown of the polynomial operation P=A*B+C which performs an iterative computation by means of a square matrix structure.
The subject of the invention is a multiplier-adder which is simple and to which parameters can be applied, is programmable in the Galois fields and has a faster processing speed, this operator being able to process all of the Galois fields up to CG(2.sup.N), N being determined at the outset by the designer.
According to the invention, a multiplier-adder in one of the fields up to CG(2.sup.N) where N is a predetermined integer, having three multiple inputs intended to receive the coefficients of polynomial operands A, B and C of degree m-1 less than N for the polynomial operation P in the Galois field of degree m, CG(2.sup.m): P=(A*B)+C, where * and + are respectively multiplication and addition, performed Modulo G, in the Galois field CG(2.sup.m) of generator polynomial G, and a data input to which parameters can be applied, for this generator polynomial, comprising:
a decoder constituted from a line of N elementary identical cells CD.sub.j, arranged in order from j=0 to N-1, receiving the coefficients of the generator polynomial G(N:0) and transmitting the coefficients of this polynomial without the one having the highest degree G(N-1:0) and a polynomial with a significant coefficient derived by the logical combination of the generator polynomial marking the degree m of the chosen Galois field, DG(N-1:0);
a computing matrix constituted from p lines of identical elementary computing cells for performing the polynomial computation in p steps, the cells of the last line supplying the terms of degrees 0 to m-1 of the resulting polynomial P,
is characterized in that, for a computation in p=2N-1 steps, the computing matrix comprises 2n-1 lines from i=0 to 2(N-1) and N columns of j=0 to N-1 of cells CM.sub.i,j connected in a tree structure, the non-connected inputs receiving logic "0" levels, each elementary computing cell MC.sub.i,j comprising:
five vertical inputs connected to the vertical outputs of the preceding cell of the same column, receiving the terms of degree j, G(j) DG(j) and B(j) of the generator polynomial, of the degree polynomial, and of the polynomial B, the term of degree i-j of the polynomial A, and the term of degree j of an intermediate result z.sup.i-1 (j), two lateral inputs receiving from the cell of the column of inferior rank of the same line the term of degree j-1 of the intermediate result z.sup.i-1 (j-1) and the term of degree (i+1-j) A(i+1-j) of the polynomial A,
two lateral outputs to

REFERENCES:
patent: 3805037 (1974-04-01), Ellison
patent: 4866654 (1989-09-01), Yamada
patent: 4918638 (1990-04-01), Matsumoto et al.
IEEE Transactions on Computers, vol. C-20, No. Dec. 12, 1971, IEEE(US), Laws, Jr. et al.: "A Cellular-Array Multiplier for GF(2.sup.m)", pp. 1573-1578.
IEEE Transactions on Computers, vol. C-33, No. 4, Apr. 1984, IEEE(US), Yeh et al.: "Systolic Multipliers for Finite Fields GF(2.sup.m)", pp. 357-360.

Affiliated with

Also associated with

Rating

Multiplier-adder in the Galois fields, and its use in a digital does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multiplier-adder in the Galois fields, and its use in a digital , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiplier-adder in the Galois fields, and its use in a digital will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1014286