Efficient galois field multiplier structures for error-correction encoding and decoding

[0002] This invention relates to communication systems employing polynomial-generated error-correction encoding, and more particularly relates to encoding and decoding techniques for reducing the number of logic gates used in such systems.

[0003] Polynomial-generated error-correction coding, such as Reed-Solomon coding, requires encoders and decoders with many gates. Most of the gates are allocated to Galois field multiplier structures. By using certain field polynomials for the Galois field multiplier structures, the number of gates can be reduced. However, the field polynomial which enables gate reduction is frequently incompatible with other parts of the encoder or decoder system which are made with commercially available parts. As a result, there is a need for a system of converting a code compatible with one field polynomial to a code compatible with another field of polynomial which enables a reduction in the number of gates used in the encoders or decoders. This invention addresses the problem and provides a solution.

[0004] The preferred embodiment is useful on a communication system employing polynomial-generated error-correction coding using encoders and decoders which comprise logic gates. In such an environment, according to a first embodiment of the invention, code words of a first form compatible with a first field polynomial selected to reduce the number of the logic gates are generated, preferably by an encoder. Code words of a second form compatible with a second field polynomial are decoded, preferably by a decoder. The code words of the first form are converted to code words of the second form before the code words of the second form are decoded.

[0005] According to a second embodiment of the invention, code words of a first form compatible with a first field polynomial are generated, preferably by an encoder. Code words of a second form compatible with a second field polynomial selected to reduce the number of logic gates are decoded, preferably by a decoder. The codes words of the first form are converted to code words of the second form before the code words of the second form are decoded by the decoder.

[0006] Using the foregoing techniques, systems employing field polynomials selected to reduce the number of logic gates can be made compatible with systems also employing encoders or decoders that use other field polynomials. As result, polynomial-generated error-correction coding systems can be customized to increase efficiency and reduce overall costs.

[0007] FIG. 1 is a schematic block diagram of a preferred form of a communication system made in accordance with the invention.

[0008] FIG. 2 is a schematic block diagram of a preferred form of logic gates used in the encoder or decoder shown in FIG. 1.

[0009] Referring to FIG. 1, a preferred embodiment of the invention comprises a data source 10 which transmits conventional communication data to a Reed-Solomon encoder 12 employing polynomial-generated error-correction coding and also comprising logic gates that are operable to generate code words of a first form compatible with a first field polynomial selected to reduce the number of the logic gates. The first field polynomial may be selected as described in “Efficient Multiplier Architectures for Galois Fields Gf(2⁴ⁿ)” by Christof Paar et al., IEEE Transactions on Computers, Vol. 47, No. 2, February 1998.

[0010] The Reed-Solomon code words generated by encoder 12 are transmitted to a conventional modulator 14. The modulated signals are then transmitted over a conventional communication medium 16, such as wires, optic fibers, or an atmospheric communication channel. The transmitted signals are received by a conventional demodulator 18 and, after demodulation, are transmitted to a converter 20. In a manner explained later, converter 20 converts the code words from the first form compatible with the field polynomial used by encoder 12 to a second form compatible with a second field polynomial used by a Reed-Solomon decoder 22 which may employ commercially available off-the-shelf components, including decoding gates, which are compatible with the second field polynomial. The converted code words are then sent to decoder 22 which uses the second field polynomial to generate data useful to a data user 24, which may comprise communication equipment or computer equipment that employs the data originally received from source 10.

[0011] As an alternative embodiment, decoder 22 may include logic gates operable to decode code words of a form compatible with a field polynomial selected to reduce the number of logic gates in decoder 22. In such an environment, encoder 12 uses a first field polynomial in order to encode data from source 10 according to a Reed-Solomon code. According to the alternative embodiment, encoder 12 may use commercially-available off-the-shelf components, including encoding gates, which are compatible with the first field polynomial. Converter 20 then converts the code generated by encoder 12, which is compatible with the first field polynomial, to a code which is compatible with a second field polynomial used by decoder 22 in order to reduce the number of logic gates in decoder 22.

[0012] The first and second field polynomials used by encoder 12 and decoder 22, as well as the construction and operation of converter 20, are explained in terms of Galois field arithmetic in the following section of this specification.

[0013] A Galois field is like any other field in that all of the elements within the field are closed under “addition” and “multiplication.” The operations of addition and multiplication, however, are defined over a polynomial, typically known as the field polynomial. Typically, the field polynomial will be monic and irreducible over GF(2) and will be of order-m, so that it can be extended to GF(2^m). Using α, GF(2^m) can be constructed by defining all of the elements in the field in terms of a basis of elements, [α⁰, α¹, α², . . . , α^m−1]. For example, the typical field polynomial used to define GF(2⁸) is given as:

[0014] p(X)=X⁸+X⁴+X³+X²+1  (26)

[0015] Now, if a is defined to be a zero of p(X), then we have

[0016] p(α)=α⁸+α⁴+α³+α²+1=0→α⁸=α⁴+α³+α²+1  (27)

[0017] Any element in GF(2⁸) then can be defined by the field polynomial as a linear combination of [α⁰, α¹, . . . , α⁷. The field element, α⁸, is derived from (27) and all other field elements also are derived in a similar manner from the field polynomial. All of the field elements (except 0) from GF(256) can be represented as ac where i is an integer between 0 and 254. This is useful for multiplication between field elements:

[0018] α¹α=α^i+j  (28)

[0019] The integer representation of the field elements is simply given by the expansion of the basis elements (i.e., α⁰=1, α⁸=29). Thus, multiplication of the integer representations of the field elements does not correspond to multiplication over the field GF(256).

[0020] The addition of any two field elements from GF(256) can be done as an addition over GF(2) of each of the bits in the bit-representation of the field elements. This amounts to a simple XOR of each of the 8 bits of the field elements to be added.

[0021] To understand how the multiplication of two elements from GF(256), α=α and b=α^jworks, each element is represented as a polynomial over GF(2) (i.e., α(x) and α(x) respectively):

[0022] α(x)=α₀x⁰+α₁x¹+ . . . +α₇x⁷  (29)

[0023] b(x)=b₀x⁰+α₁x¹+ . . . b₇x⁷  (30)

[0024] The coefficients of the polynomial are simply the coefficients of the basis expansion for the element. The multiplication of the two elements then is the multiplication of the two polynomials modulo the field polynomial:

[0025] c(x)=α(x)b(x) mod p(x)=α^i+j  (31)

[0026] where the last equality in (31) follows from (28). An architecture for implementing the multiplication follows from the solution to each of the 8 coefficients of c(x) in terms of the α′_is and b′_is. For example, the solution to the first coefficient of c(x) is:

[0027] c₀=α₀b₀+α₇b₇₊α₆b₇+α₇b₆+α₅b₇₊α₆b₆+α₇b₅+α₁b₇+α₂b₆+α₃b₅+α₄b₄+α₅b₃+α₆b₂+α₇b₁  (32)

[0028] where α_ib_jis implemented as an AND gate between the two bits, α_i, b_jand α_i+b_jis implemented as XOR gate between the two bits. The above architecture using the field polynomial that is defined in (26) is not optimal in terms of minimizing the number of gates used. A more efficient architecture comes from the realization that GF(256) can be generated from many different field polynomials with each of the resulting fields being isomorphic. C. Paar, et al. in “Efficient Multiplier Architectures for Galois Fields GF(2⁴ⁿ),” IEEE Trans. on Computers, voL 47, pp. 162-170, February 1998, describe field polynomials that produce a minimum number of gates for a multiplication over GF(256). The resulting field polynomial is given as a composite field. The composite field consists of taking an order-4 field polynomial with coefficients from GF(4) and constructing GF((2²)⁴)=GF(256), whereas, before, an order-8 polynomial was used with coefficients from GF(2), to construct GF(2⁸)=GF(256). The new field polynomial is given as:

[0029] p_c(x)=x⁴+x³+w²x²+w  (33)

[0030] where w is the primitive element of the field polynomial, q(x), that defines GF(4):

[0031] q(x)=x²+x+1  (34)

[0032] q(w)=w²+w+1=0→w²=w+1  (35)

[0033] The code words generated by encoder 12 which are compatible with a first field polynomial can be converted to a form compatible with a second field polynomial used by decoder 22 according to expressions (36)-(40).

[0034] To show that the field generated by p(x) is isomorphic to the field generated by p_c(x), the following mapping is defined:

[0035] Ψ:GF(2⁸)→GF((2²)⁴)  (36)

[0036] The zero element must map to the zero element by the definition of an isomorphic map:

[0037] Ψ(0)=0  (37)

[0038] From (37) it follows that:

[0039] Ψ(α^κ)=β^κκ=0,1, . . . , 254  (38)

[0040] where α is the primitive element of p(x). Solving the above equations, w=α^85κ and β=α^31κ. Therefore, the isomorphic map is completely defined by:

[0041] Ψ(α^κ)=α^31κ  (39)

[0042] The resulting architecture can be found by defining multiplication with respect to p_c(x):

[0043] c(x)=α(x)b(x) mod p_c(x)  (40)

[0044] where α(x) and b(x) are now order-3 polynomials with coefficients from GF(4). As a result, after solving for c₀, c₁, c₂, c₃in terms of the α′_is, b′_is, product terms α_ib_jare evaluated using a GF(4) multiply, while additions are evaluated as usual.

[0045] FIG. 2 illustrates logic gates suitable for use in encoder 12 or decoder 22. More specifically, FIG. 2 shows and gates 31-33 and exclusive OR gates 41-44. The gate arrangement of FIG. 2 may be used to implement a GF(4) multiple with field polynomial q(x)=x²+x+1.

[0046] The embodiments described in connection with FIG. 1 illustrate preferred forms of the invention which may be altered and modified without departing from the true spirit and scope of the invention as defined in the accompanying claims.