Irreducible Polynomials: Non-Binary Fields

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.

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

$$5x^3+\frac{7}{4}{x}^2-\frac{2}{3}x+1$$E1

is a polynomial in single variable.

$$\surd 2x^3{y}^2+6x^{2}y+5\mathit{xy}+\surd 3$$E2

is a polynomial in two variables.

For the polynomial, $a_n{x}^n+a_{n-1}{x}^{n-1}+\dots \dots ..a_0$, the degree is defined to be n if $a_n\ne$ 0. The degree of the polynomial $\sum a_{\mathit{ij}}{x}^i{y}^j$ in two variables x, and y is given by $max\left\{i+j|a_{\mathit{ij}}\ne 0\right\}.$

Given two polynomials $f\left(x\right)$ and $g\left(x\right)$, there exist unique quotient and remainder polynomials$q\left(x\right)$ and $r\left(x\right)$, such that

$$f\left(x\right)=q\left(x\right)g\left(x\right)+r\left(x\right),\mathit{\text{where degree of}}r\left(x\right)<g\left(x\right)$$E3

If $\mathit{gcd}\left[f\left(x\right),g\left(x\right)\right]=d$, then there exists two polynomials $p\left(x\right),q\left(x\right)$ such as

$$d=p\left(x\right)f\left(x\right)+q\left(x\right)g\left(x\right)$$E4

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 F is defined as irreducible over F in case it cannot be expressed as a product of two non-constant polynomials over F of degree less than n.

Example 1:

Consider the $x^2–2$ polynomial. There are no zeroes in $x^2-2$over Q. This is the same as asserting that √ 2 is not rational [1].

In case$x^2-2$ is reducible, we may write $x^2–2$ = 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. $x^2–2$has a zero in Q in this example, which is a contradiction. As a result, $x^2–2$is irreducible over Q. $x^2–2=\left(\mathrm{x}-2\right)\left(\mathrm{x}+2\right)$, and on the contrary, is reducible over $\mathrm{R},x^2-2=\left(x-\surd 2\right)\left(x+\surd 2\right).$

Example 2: $x^4+x+1$ is an irreducible polynomial having degree 4 over $\mathit{GF}\left(2\right)$ but $x^4+x^3+x^2+1$ is not irreducible because $x^4+x^3+x^2+1=\left(x^3+x+1\right)\left(x+1\right)$.

Every polynomial of degree one is irreducible. The polynomial $x^2+1$ is irreducible over R but reducible over C.

Gauss’s lemma.

A polynomial$f\in Z\left[x\right]\subseteq Q\left[x\right]$ of the form

$$f\left(x\right)=x^n+a_{n-1}x+n-1+\dots +a_{1}x+a_0$$

is irreducible in$\mathrm{Q}\left[\mathrm{x}\right]$iff it is irreducible in$\mathrm{Z}\left[\mathrm{x}\right]$. More precisely, if$\mathrm{f}\left(\mathrm{x}\right)\in \mathrm{Z}\left[\mathrm{x}\right],$ then$\mathrm{f}\left(\mathrm{x}\right)$can be factorised and represented as multiplication of two polynomials of lesser degrees r and s in$\mathrm{Q}\left[\mathrm{x}\right]$iff it has such a factorisation with polynomials of similar degrees r and s in$\mathrm{Z}\left[\mathrm{x}\right].$

Eisenstein irreducibility criterion (1850).

Suppose that $f\left(x\right)$is the polynomial with coefficients in the ring Z of integers, given by $f\left(x\right)=c_n{x}^n+\cdots +c_{1}x+c_0$and p is a prime which satisfies

1. $p$ does not divide $c_n$;

2. $p$ divides $c_{n-1},\dots ,p_1,p_0$;

3. $p^2$ does not divide $c_0$;

Then, $f\left(x\right)$ is irreducible over field Q of rational numbers. [2]

Dumas criterion (1906).

Let $\mathrm{F}\left(\mathrm{x}\right)=a_n{x}^n+a_{n-1}{x}^{n-1}+\dots \dots ..a_0$ be a polynomial with coefficients in Z [2]. Suppose there exists a prime p whose exact power $p^{r_i}$ dividing $a_i$ (where $r_i=\infty$ if $a_i=0$), 0 ≤ i ≤ n, satisfy.

• $r_n$ = 0,

• ($r_i$/$n-i$) > $\left(r_0/n\right)\mathit{\text{for}}1\le i\le n-1$ and

• $\mathit{gcd}\left(r_0,n\right)$ equals 1.

Then, F(x) is irreducible over Q.

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

1.2 Monic polynomials

A polynomial$x^n+a_{n-1}{x}^{n-1}+\dots \dots .+a_{1}x+a_0$in which the coefficient of the highest-order term is 1 is called a monic polynomial. For example, $x^2+3$ is monic but, $7x^2+3$ is not monic (the highest power of $x^2$has a coefficient of 7, not 1).

Let $F_q$ stand for the finite field of q elements, where q is the prime number. Gauss’ formula, in general, gives the number of monic irreducible polynomials $M_n\left(p\right)$ of degree n over the finite field $F_q$. [3]

$$M_n\left(p\right)=\frac{1}{n}\sum _{d/n}\mu \left(d/n\right)q^d$$E5

where $\mu \left(r\right)$ denotes the Mobius function and $d$ includes all positive divisors of n. d also includes 1 and n. Also, $\mu \left(1\right)=1$. The value of $\mu \left(d\right)$ calculated 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 $\mu \left(d\right)=0,$ that is,

$$\mu \left(d\right)=\left\{\begin{array}{l}1,d\text{is squarefree positive integer with an even number of prime factors}\\ -1,d\text{is square freepositive integer with an}\mathrm{odd}\text{number of prime factors}\\ 0,d\mathrm{has}\mathrm{a}\text{squared prime factor}\end{array}\right.$$

In particular,$\mu \left(d\right)=-1$ for all primes$p$.

Example: $\mathit{GF}\left(256\right)=\mathit{GF}\left(2^8\right).\text{That is},p=2\mathit{\text{and}}n=8.$

$$Mn\left(p\right)=\frac{1}{8}\sum _{d/8}\mu \left(8/n\right)2^d=\frac{1}{8}\sum _{d\mathrm{\varepsilon }\left(1,2,4,8\right)}\mu \left(\frac{8}{n}\right)2^d$$

1.3 Primitive polynomials

A ‘primitive polynomial’ has its roots as primitive elements in the field $\mathit{GF}\left(p^n\right)$. It is an irreducible polynomial of degree d. It can be proved that there are $\varnothing \left(\raisebox{1ex}{$p^d-1$}\!\left/ \!\raisebox{-1ex}{$d$}\right.\right)$ number of primitive polynomials, where $\varnothing$ is Euler phi-function. For example, if p = 2, d = 4, $\varnothing \left(\raisebox{1ex}{$2^4-1$}\!\left/ \!\raisebox{-1ex}{$4$}\right.\right)$ is 2, so there exist exactly two primitive polynomials of degree 4 over $\mathit{GF}\left(2\right).$ The MATLAB function pol = gfprimfd(m,opt,p) searches for one or more primitive polynomials for $\mathit{GF}\left(p^n\right),$where p represents a number that is prime and n is greater than 0. The MATLAB code below seeks primitive polynomials for $\mathit{GF}\left(81\right)$ having 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 =

 2 1 0 0 1

pol2 =

 2 1 0 0 1

 2 2 0 0 1

 2 0 0 1 1

 2 0 0 2 1

pol3 = [ ]

Because no primitive polynomial for $\mathit{GF}\left(81\right)$ has 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 $\mathit{GF}\left(81\right)$.

Further, Primpoly(m) gives the primitive polynomial for $\mathit{GF}\left(2^m\right)$, where m is an integer between 2 and 16. The output is an integer, whose binary representation represents the polynomial coefficients.

For $\mathit{GF}\left(2^m\right)$, 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].

opt	Meaning of pr
‘min’	One primitive polynomial for GF(2^∧m) having the smallest possible number of nonzero terms
‘max’	One primitive polynomial for GF(2^∧m) having the greatest possible number of nonzero terms
‘all’	All primitive polynomials for GF(2^∧m)
Positive integer k	All primitive polynomials for GF(2^∧m) 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 a represents a primitive polynomial for the Galois field $\mathit{GF}\left(2^m\right),$ and 0 otherwise [4].

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, N_b = 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 $n^p=q$ is represented as $\mathit{GF}\left(n^p\right)$. 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, for$p\le 32$, it is normal to represent an entire polynomial in GF$\left(2^p\right)$as 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 a₀ coefficient. For example, the polynomial form of the Galois field with 16 elements (known as GF (16), so that p = 4), is:

$$a_3{x}^3+a_2{x}^2+a_1{x}^1+a_0{x}^0$$

with $a_3{a}_2{a}_1{a}_0$ corresponding to the binary numbers 0000 to 1111.

For any finite field $\mathit{GF}\left(2^p\right),$ there exists a primitive polynomial of degree $p$ over $\mathit{GF}\left(q\right)$ [11].

Table 2 lists the primitive polynomials.

Number of primitive polynomials of degree N
N	No
1	1
2	1
4	2
8	16
16	2048
32	67,108,864

Table of primitive polynomials up to degree 31
N	Primitive polyn omials
1, 2, 3, 4, 6, 7, 15, 22	1 + X + X^n
5, 11, 21, 29	1 + X^2 + X^n
10, 17, 20, 25, 28, 31	1 + X^3 + X^n
9	1 + X^4 + X^n
23	1 + X^5 + X^n
18	1 + X^7 + X^n
8	1 + X^2 + X^3 + X^4 + X^n
12	1 + X + X^3 + X^4 + X^n
13	1 + X + X^4 + X^6 + X^n
14, 16	1 + X + X^3 + X^4 + X^n

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($p^m$), given by gfprimdf(m,p), is shown in polynomial format by the gfpretty function

For binary field, $p=1$, while for $p\ge 2$, 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=3$ while considering the primitive polynomial$1+x+x^2.$

Binary	Polynomial
0 0 0	0x^2 + 0x + 0	0
0 0 1	0x^2 + 0x + 1	1
0 1 0	0x^2 + 1x + 0	x
0 1 1	0x^2 + 1x + 1	x + 1
1 0 0	1x^2 + 0x + 0	x^2
1 0 1	1x^2 + 0x + 1	x^2 + 1
1 1 0	1x^2 + 1x + 0	x^2 + x
1 1 1	1x^2 + 1x + 1	x^2 + x + 1

Table 3.

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

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.

Nonbinary LDPC parity 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 $\left(M\times N\right)$ NB-LDPC code written in a Galois field $\mathit{GF}\left(q\right)$, where $q=2^p$ is the field’s order. $\left(d_v,d_c\right)$ are 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 $\mathit{GF}\left(2^p=q\right)$.

We define a primitive polynomial of degree $p$ for the field:

$$p\left(x\right)=a_0+a_{1}x+a_2{x}^2\dots +x^p$$

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

$$A=\left[\begin{array}{cccccc}0& 1& 0& 0& \dots & 0\\ 0& 0& 1& 0& \dots & 0\\ 0& 0& 0& 1& \dots & 0\\ .& .& .& .& \dots & .\\ 0& .& .& .& \dots & 1\\ a_0& a_1& a_2& a_3& \dots & a_{p-1}\end{array}\right]$$

where [$a_0,a_1\dots ,a_{p-1}$] 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 $h_{\mathit{ij}}$ of the parity check matrix can be written in the form of a $\left(p\times p\right)$ binary matrices $H_{\mathit{ij}}$, where $H_{\mathit{ij}}$ is the result of the tranpose of a power of the primitive matrix of the Galois field. Subsequently, the $\left(M\times N\right)$ nonbinary parity check matrix can be written in the form of a $M_{b}X{N}_b$ binary parity check matrix, where $M_b=\mathit{pM}$ and $N_b=\mathit{pN}$ as shown in Figure 4. The zero elements of the parity check matrix are represented with all-zero matrices of size $\left(p\times p\right).$

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:

$$\sum _{j:H_{\mathit{ij}}\ne 0}{H}_{\mathit{ij}}{X}_j^T=0^T$$E6

where $H_{\mathit{ij}}$ is the matrix representation of the Galois field element $h_{\mathit{ij}}$, $X_j$ is the p-bits binary mapping of the symbol $c_j$, and 0 is 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.

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.