Open access peer-reviewed chapter

Irreducible Polynomials: Non-Binary Fields

Written By

Mani Shankar Prasad and Shivani Verma

Submitted: August 20th, 2021Reviewed: December 6th, 2021Published: April 5th, 2022

DOI: 10.5772/intechopen.101897

Chapter metrics overview

12 Chapter Downloads

View Full Metrics

Abstract

Irreducible polynomials play an important role in design of Forward Error Correction (FEC) codes for data transmission with integrity and automatic correction of data, as for example, Low-Density Parity Check codes. The usage of irreducible polynomials enables construction of non-prime-order finite fields. Most of the irreducible polynomials belong to binary Galois field. The important analytical concept is optimisation of irreducible polynomials for use in FECs in nonbinary Galois (NBG) field, leading to the development of an algorithm for LDPC that can work with nonbinary Galois fields. According to studies, the Tanner graph for ‘nonbinary Low Density Parity Check’ codes might get sparser as the field’s dimensions rise, ensuring that they do much better than their binary counterparts. A detailed discussion of representation of nonbinary irreducible polynomial and the computations involved have been illustrated. The concept has been tried for NB-LDPC codes. To prove the notion, computational complexity is found from different parameters such as performance of error correction capability, complexity cost and simulation time taken. Such detail study makes the NBG fields-based FEC very suitable for high-speed data transmission with self-error correction.

Keywords

  • irreducible polynomial
  • nonbinary Galois field
  • FEC
  • LDPC
  • Galois field

1. Introduction

Polynomials are algebraic expressions that consist of variables and coefficients. Indeterminates are another word for variables. Polynomial expressions can undergo a variety of mathematical operations, but they cannot be split by the variable.

The Greek phrases ‘poly’ and ‘nomial’, which imply ‘many’ and ‘period’, respectively, from the word Polynomial. A polynomial is a mathematical equation that is formed by multiplying the sum of terms in one or more variables by coefficients.

For example

5x3+74x223x+1E1

is a polynomial in single variable.

2x3y2+6x2y+5xy+3E2

is a polynomial in two variables.

For the polynomial, anxn+an1xn1+..a0, the degree is defined to be n if an0. The degree of the polynomial aijxiyjin two variables x, and y is given by maxi+jaij0.

Given two polynomials fxand gx, there exist unique quotient and remainder polynomialsqxand rx, such that

fx=qxgx+rx,where degree ofrx<gxE3

If gcdfxgx=d, then there exists two polynomials px,qxsuch as

d=pxfx+qxgxE4

1.1 Irreducible polynomials

Irreducible polynomials are considered as the basic constituents of all polynomials.

A polynomial of degree n ≥ 1 with coefficients in a field Fis defined as irreducible over Fin case it cannot be expressed as a product of two non-constant polynomials over Fof degree less than n.

Example 1:

Consider the x22polynomial. There are no zeroes in x22over Q. This is the same as asserting that √ 2 is not rational [1].

In casex22is reducible, we may write x22= g(x)h(x), where g(x) and h(x) are both fewer than two degrees. Because the LHS has a degree of two, the sole option is that both g(x) and h(x) have a degree of one. x22has a zero in Q in this example, which is a contradiction. As a result, x22is irreducible over Q. x22=x2x+2, and on the contrary, is reducible over R,x22=x2x+2.

Example 2: x4+x+1is an irreducible polynomial having degree 4 over GF2but x4+x3+x2+1is not irreducible because x4+x3+x2+1=x3+x+1x+1.

Every polynomial of degree one is irreducible. The polynomial x2+1is irreducible over R but reducible over C.

Gauss’s lemma.

A polynomialfZxQxof the form

fx=xn+an1x+n1++a1x+a0

is irreducible inQxiff it is irreducible inZx. More precisely, iffxZx,thenfxcan be factorised and represented as multiplication of two polynomials of lesser degrees r and s inQxiff it has such a factorisation with polynomials of similar degrees r and s inZx.

Eisenstein irreducibility criterion (1850).

Suppose that fxis the polynomial with coefficients in the ring Z of integers, given by fx=cnxn++c1x+c0and p is a prime which satisfies

  1. pdoes not divide cn;

  2. pdivides cn1,,p1,p0;

  3. p2does not divide c0;

Then, fxis irreducible over field Q of rational numbers. [2]

Dumas criterion (1906).

Let Fx=anxn+an1xn1+..a0be a polynomial with coefficients in Z [2]. Suppose there exists a prime p whose exact power pridividing ai(where ri=if ai=0), 0 ≤ i ≤ n, satisfy.

  • rn= 0,

  • (ri/ni) > r0/nfor1in1and

  • gcdr0nequals 1.

Then, F(x) is irreducible over Q.

Note that Eisenstein’s criterion is a special case of Dumas criterion with r0=1.

1.2 Monic polynomials

A polynomialxn+an1xn1+.+a1x+a0in which the coefficient of the highest-order term is 1 is called a monic polynomial. For example, x2+3is monic but, 7x2+3is not monic (the highest power of x2has a coefficient of 7, not 1).

Let Fqstand for the finite field of q elements, where q is the prime number. Gauss’ formula, in general, gives the number of monic irreducible polynomials Mnpof degree nover the finite field Fq. [3]

Mnp=1nd/nμd/nqdE5

where μrdenotes the Mobius function and dincludes all positive divisors of n. dalso includes 1 and n.Also, μ1=1. The value of μdcalculated at a product of distinct primes is 1 if number of factors is even and it is equal to −1 if the number of factors is odd. For all other natural numbers μd=0,that is,

μd=1,dis squarefree positive integer with an even number of prime factors1,dis square freepositive integer with anoddnumber of prime factors0,dhasasquared prime factor

In particular,μd=1for all primesp.

Example: GF256=GF28.That is,p=2andn=8.

Mn(p)=18d/8μ8/n2d=18dɛ1248μ8n2d

1.3 Primitive polynomials

A ‘primitive polynomial’ has its roots as primitive elements in the field GFpn. It is an irreducible polynomial of degree d. It can be proved that there are pd1dnumber of primitive polynomials, where is Euler phi-function. For example, if p = 2, d = 4, 2414is 2, so there exist exactly two primitive polynomials of degree 4 over GF2.The MATLAB function pol = gfprimfd(m,opt,p) searches for one or more primitive polynomials for GFpn,where p represents a number that is prime and n is greater than 0. The MATLAB code below seeks primitive polynomials for GF81having various other properties.

p = 3; n = 4;

pol1 = gfprimfd(m,'min',p)

pol2 = gfprimfd(m,3,p)

pol3 = gfprimfd(m,4,p)

The output is as shown below:

pol1 =

21001

pol2 =

21001

22001

20011

20021

pol3 = [ ]

Because no primitive polynomial for GF81has exactly four nonzero terms, pol3 is empty. Also, pol1 represents a single three-term polynomial, whereas pol2 represents all of the three-term primitive polynomials for GF81.

Further, Primpoly(m)gives the primitive polynomial for GF2m, where m is an integer between 2 and 16. The output is an integer, whose binary representation represents the polynomial coefficients.

For GF2m, primpoly(m,opt)returns one or more primitive polynomials. As seen in Table 1, the output depends on the argument opt. The output argument (an integer represented in binary format) represents the coefficients of the relevant polynomial. There is no element in the output if no primitive polynomial satisfies the conditions [4].

optMeaning of pr
‘min’One primitive polynomial for GF(2m) having the smallest possible number of nonzero terms
‘max’One primitive polynomial for GF(2m) having the greatest possible number of nonzero terms
‘all’All primitive polynomials for GF(2m)
Positive integer kAll primitive polynomials for GF(2m) that have k nonzero terms

Table 1.

Different options for argument ‘opt’ in primpoly (m,opt).

m = 4;

defaultprimpoly = primpoly(m)

allprimpolys = primpoly(m,'all')

i1 = isprimitive(25)

i2 = isprimitive(21)

The output is as shown below:

Primitive polynomial(s) =

D^4+D^1+1

defaultprimpoly =

19

Primitive polynomial(s) =

D^4+D^1+1

D^4+D^3+1

allprimpolys =

19

25

i1 = logical

=1

i2 = logical

=0

The MATLAB function isprimitive(a)gives the output as 1 if arepresents a primitive polynomial for the Galois field GF2m,and 0 otherwise [4].

Advertisement

2. Role of primitive polynomials in nonbinary LDPC codes [12]

Error control codes find applications in the transmission and storage of vast amounts of error-prone data. Mostly, binary and nonbinary channels use ECC codes such as BCH codes, Reed Solomon codes [5], and Low-Density Parity Check codes. Berlekamp and Massey, after Peterson, created powerful algorithms that proved possible with the use of latest digital techniques. In addition to this, the usage of primitive polynomials and the Galois field offered these routines a structured and systematic approach.

LDPC codes got an initial explanation from Gallager in 1963. A parity check matrix (PCM) having sparse characteristics with a minimal number of nonzero components feature LDPC codes. These codes were overlooked until the mid-1990s despite their superior performance due to their decoding complexity, which exceeded the capacity of then electronic systems. When Mackay et al. reviewed the LDPC codes in 1996 [6], they discovered that when decoded using probabilistic soft choice decoding methods, they obtain performance close to the Shannon limit. Gallager later proposed nonbinary LDPC (NB-LDPC) codes by extending the concept of LDPC codes to nonbinary alphabets.

The NB-LDPC codes are defined for Galois fields of order, strictly higher than 2. They are considered as a good alternative to LDPC codes (Refer Figure 1) because:

  • The graph for an NBLDPC code is frequently less dense than the graph for a binary-LDPC code for the same code rate and binary length [7]. As a result, the topological features of the NB-LDPC code plot have improved, with a larger girth and fewer halting and trapping sets.

  • For a binary Low-Density Parity Check code sent with a high-order modulation, the Maximum a-posteriori (MAP) de-mapper produces probability at the binary level for the decoder. This means that decoder input messages are associated even when the cycles are absent. If the LDPC code is defined in the same or higher order of Galois field as the order of modulation, the NB-LDPC decoder is initialised with non-correlated messages. NB-LDPC codes outperform other high-order modulation codes as a consequence.

  • Better AWGN channel performance: Decoding techniques in [8] push NB-LDPC codes close to capacity limits, especially at high rates for the AWGN channel. Li et al.[9] looked at the result of implementing NB-LDPC codes over AWGN channel. The decoding capabilities of NB-LDPC codes demonstrated that the Shannon capacity of the binary AWGN channel may be achieved with suitably long code words by simply increasing the field order q of the NB-LDPC code (Figure 1).

Figure 1.

Binary vs. nonbinary LDPC, Nb = 3008 bits and R = 1/2 [12].

2.1 Galois fields

A Galois field is a finite field with a finite order, which is either a prime number or the power of a prime number. A field of order np=qis represented as GFnp. A specific type called as characteristic-2 fields are the fields when n=2.All the elements of a characteristic-2 field can be shown in a polynomial format [10].

In coding applications, forp32, it is normal to represent an entire polynomial in GF2pas a single integer value in which individual bits of the integer represent the coefficients of the polynomial. The least significant bit of the integer represents the a0 coefficient. For example, the polynomial form of the Galois field with 16 elements (known as GF (16), so that p = 4), is:

a3x3+a2x2+a1x1+a0x0

with a3a2a1a0corresponding to the binary numbers 0000to 1111.

For any finite field GF2p,there exists a primitive polynomial of degree pover GFq[11].

Table 2 lists the primitive polynomials.

Number of primitive polynomials of degree N
NNo
11
21
42
816
162048
3267,108,864
Table of primitive polynomials up to degree 31
NPrimitive polyn omials
1, 2, 3, 4, 6, 7, 15, 221 + X+ Xn
5, 11, 21, 291 + X2 + Xn
10, 17, 20, 25, 28, 311 + X3 + Xn
91 + X4 + Xn
231 + X5 + Xn
181 + X7 + Xn
81 + X2 + X3 + X4 + Xn
121 + X+ X3 + X4 + Xn
131 + X+ X4 + X6 + Xn
14, 161 + X+ X3 + X4 + Xn

Table 2.

Primitive polynomials.

The following MATLAB functions provide default primitive polynomials for Galois field:

The row vector that supplies the coefficients of the default primitive polynomial for GF(pm), given by gfprimdf(m,p), is shown in polynomial format by the gfpretty function

For binary field, p=1, while for p2, it represents a nonbinary field. Hence, nonbinary LDPC codes can be visualised as a direct generalisation of binary LDPC codes. Table 3 shows the example for p=3while considering the primitive polynomial1+x+x2.

BinaryPolynomial
0 0 00x2 + 0x + 00
0 0 10x2 + 0x + 11
0 1 00x2 + 1x + 0x
0 1 10x2 + 1x + 1x + 1
1 0 01x2 + 0x + 0x2
1 0 11x2 + 0x + 1x2 + 1
1 1 01x2 + 1x + 0x2 + x
1 1 11x2 + 1x + 1x2 + x + 1

Table 3.

For p= 3 while considering the primitive polynomial 1 + x+ x2.

The binary coefficients of the polynomial representation can be used to represent the Parity Check Matrix of a NB-LDPC code in a binary matrix form (Refer Figures 2 and 3).

Figure 2.

NonbinaryLDPCparity check matrix [12].

Figure 3.

Tanner graph for a nonbinary parity check matrix [12].

The field’s nonbinary elements can be represented as a polynomial [11] when the field order of an NB-LDPC code is a power of 2, giving the field elements a binary representation.

Consider a normal M×NNB-LDPC code written in a Galois field GFq, where q=2pis the field’s order. dvdcare the degrees of connection of the variable and check nodes, respectively. The nonzero elements of the NB parity check matrix H associated with the code correspond to the Galois field GF2p=q.

We define a primitive polynomial of degree pfor the field:

px=a0+a1x+a2x2+xp

A matrix A of size p × p is also associated to the primitive polynomial [10].

A=010000010000010.....0...1a0a1a2a3ap1

where [a0,a1,ap1] are primitive polynomial p(x)‘s coefficients.

Because p(x) represents the field’s primitive polynomial, A can be called as its primitive element in matrix representation. As a result, the binary matrix representations of all the other elements of the field are generated by the powers of the matrix A. Thus, the nonzero elements hijof the parity check matrix can be written in the form of a p×pbinary matrices Hij, where Hijis the result of the tranpose of a power of the primitive matrix of the Galois field. Subsequently, the M×Nnonbinary parity check matrix can be written in the form of a MbXNbbinary parity check matrix, where Mb=pMand Nb=pNas shown in Figure 4. The zero elements of the parity check matrix are represented with all-zero matrices of size p×p.

Figure 4.

Nonbinary parity check matrix [12].

Modulo-2 addition and multiplication of polynomial representations are used to do arithmetic on the GF(q) elements. Modulo-2 arithmetic over the matrix representations can also be used to do arithmetic on the matrix representations. As a result, in the vectorial domain, the parity check equation may be represented as:

j:Hij0HijXjT=0TE6

where Hijis the matrix representation of the Galois field element hij, Xjis the p-bits binary mapping of the symbol cj, and 0is the all zero-component vector.

The methods for decoding binary LDPC codes may be generalised to nonbinary LDPC codes defined over finite fields by performing modifications in correspondence to finite fields. MacKay et al. [13] expanded the belief propagation technique to nonbinary LDPC codes constructed over finite fields. The main obstacle in the development of the hardware realisation of the BP decoding algorithm is its computational complexity, the major factor being the check nodes processing, which is composed of a high number of additions and multiplications. A combination of iterative and list decoding algorithms [12] can be used to design low complexity nonbinary LDPC decoders.

Advertisement

3. Conclusion

In both binary (Galois field) and nonbinary fields, this chapter introduces monic, irreducible, primal polynomials. With examples, the MATLAB functions related to primitive polynomials were also discussed. The relevance of polynomials and the Galois field in creating the nonbinary LDPC code’s parity check matrix for error detection and correction has also been described.

References

  1. 1.http://www.math.ucsd.edu/∼jmckerna/Teaching/15-16/Spring/103B/l_17.pdf
  2. 2.http://maths.du.ac.in/Events/IWM/talks/S.K.Khanduja.pdf
  3. 3.Chebolu SK, Miná J. Counting irreducible polynomials over finite fields using the inclusion-exclusion principle. Mathematics Magazine. 2011;84:369-371. DOI: 10.4169/math.mag.84.5.369 c Mathematical Association of America
  4. 4.https://in.mathworks.com/help/
  5. 5.Hanzlík P. Steganography in Reed-Solomon Codes. Sweden: Luleå University of Technology; 2011
  6. 6.MacKay DJC, Neal RM. Near shannon limit performance of low-density parity check codes. Electronics Letters. 1997;33(6):457-458. DOI: 10.1049/el:19970362
  7. 7.MacKay DJC, Davey MC. Evaluation of gallager codes for short block length and high-rate applications. In: Marcus B, Rosenthal J, editors. Codes, Systems, and Graphical Models. The IMA Volumes in Mathematics and its Applications, Vol. 123. New York, NY: Springer; 2001. DOI: 10.1007/978-1-4613-0165-3_6
  8. 8.Ma L, Wang L, Zhang J. Performance Advantage of Non-binary LDPC Codes At High Code Rate under AWGN Channel. 2006 International Conference on Communication Technology. 2006. pp. 1-4. DOI: 10.1109/ICCT.2006.341827
  9. 9.Li G, Fair IJ, Krzymien W. Density evolution for nonbinary LDPC codes under Gaussian approximation. IEEE Transactions on Information Theory. 2009;55(3):997-1015
  10. 10.Poulliat C, Fossorier M, Declercq D. Design of non binary ldpc codes using their binary image: algebraic properties. Seattle, USA: In Proceedings of IEEE ISIT; 2006
  11. 11.Poulliat C, Fossorier M, Declercq D. Opitmization of non-binary ldpc codes using their binary images. Munich, Germnay: In Proceedings of IEEE Int. Symp. on Turbo codes; 2006
  12. 12.Shams B. Next generation non-binary LDPC codes. Information Theory [cs.IT]. French: University of Cergy Pontoise; 2010
  13. 13.Davey M, Mackay DJC. Low Density Parity Check Codes Over gf(q). IEEE Communication Letter. 1998;2:165-167

Written By

Mani Shankar Prasad and Shivani Verma

Submitted: August 20th, 2021Reviewed: December 6th, 2021Published: April 5th, 2022