ECE4253 Digital Communications | |

Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada | |

0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0Significantly, this is equivalent to the exclusive-OR operation. The set satisfies the definition of an additive group: the properties of closure, identity, inverse, and associative can be confirmed for addition in this set. The operation is also commutative. For this field the multiplication operation is defined as:

0 × 0 = 0 0 × 1 = 0 1 × 0 = 0 1 × 1 = 1While this is like normal multiplication, it is also equivalent to a logical AND operation. The set satisfies the definition of a multiplicative group: the properties of closure, identity, inverse, and associative can be confirmed for multiplication in this set (excluding the zero which has no inverse). The operation is also commutative.

In summary the set {0,1} is both an additive group and multiplicative group and the operation of multiplication is distributive over addition (e.g. a × [b+c] = a×b + b×c ) both operations are commutative and the set defines a field named **GF(2)**. This field forms the basis for larger fields of the form GF(2^{m}).

These mathematical definitions constitute the theoretical underpinnings for all the manipulations to follow. The rules of everyday math work on real numbers because the real numbers form a field. The same familiar operations work with the Galois field GF(2) with the major difference being that modulo 2 addition is used.

2. Multi-bit binary values can be represented as polynomials with coefficents from **GF(2)** or the set {0,1}.

For example, the 6-bit binary sequence **110011** can be written as

and simplified as:

or as polynomial terms in brackets as:

or the same bits in decimal format as:

The *degree* of a polynomial is the power of the highest non-zero
coefficient. The above example shows a polynomial of "degree 5"; note that a degree 5 polynomial spans 6 bits.

A *monic polynomial* is defined as having 1 as the highest order coefficient as in this example.

3. Polynomials can be manipulated using the usual arithmetic rules, in particular, the polynomial powers add under multiplication, as expected.

Example 1: The product (110011) x (10) = (1100110) can be written as:

4. Polynomials always use modulo 2 addition as described above.

Example 2: The product (11) x (11) can be computed as:

11 x 11 ---- 11 + 110 ---- 101 Note modulo 2 additionand as a polynomial:

Note that this result is not "3 x 3 = 9" as this is **not** ordinary binary arithmetic!

5. The rules for **subtraction** follow from addition (because 1+1=0,
then 0-1=1) and are also equivalent to the exclusive-OR operation, as:

0 - 0 = 0 0 - 1 = 1 1 - 0 = 1 1 - 1 = 0

Therefore, subtraction is the same as addition in GF(2).

6. With these rules in mind, a **division** such as (x^{2} + 1) / (x + 1) or (101) / (11) can be accomplished:

1 1 quotient = x + 1 ________ 1 1 ) 1 0 1 1 1 ---- 1 1 Note modulo 2 subtraction 1 1 ---- 0 remainder = 0

Therefore: x^{2} + 1 = (x + 1)(x + 1).

The polynomial (x + 1) is a *factor* of x^{2} + 1.

An polynomial that has no factors other than 1 and itself is called an *irreducible
polynomial* or equivalently a *prime polynomial* with the analogy being a prime integer.

Note again that (101) is *not* the integer 5 and the polynomial (101) is not prime (irreducible)!

The *prime integers* {2,3,5,7,11,13,17,19,23,29,31,37...} have no factors other than 1 and themselves.

To determine if a number such as 37 is prime, it could be tested against all possible factors from 2 to 36. In practice, only odd potential factors need to be tried once 2 is tested. In any case, testing can stop when the square root of the number is reached. Some observations can help when checking by hand:

- Multiples of 2 are checked by inspection since those integers are even (the least significant bit is 0).
- Multiples of 3 are checked by inspection since the digits in those integers add to give a multiple of 3.
- Multiples of 5 are checked by inspection since those integers must end in 0 or 5.

For example, to check if 37 is prime, test only {2,3,5} (by inspection) and stop after the square root of 37.

Similarly, to check if 137 is prime, test only {2,3,5,7,9,11} .
*(Although 9 could be skipped after eliminating 3 as a factor.)*

In summary, it is only necessary to test with prime numbers up to the square root.

It should be noted that factoring very large integers represents a formidable computational challenge for which no dramatic shortcuts exist to simplify the task.

- Multiples of (10) = x are checked by inspection since the smallest polynomial term is not 1.
- Multiples of (11) = x+1 are checked by inspection since those polynomials have an even number of terms.

Example 3:

Determine if the polynomial P(x) is irreducible, where
P(x) = x^{6} + x^{5} + x^{2} + x = (1100110)

1. By inspection, since the smallest term is 0, then (10)=x is a factor.

2. Since there is an even (4) number of terms, then (11)=x+1 is also a factor.

By either of these tests, the polynomial P(x) is not irreducible. There is no need for further calculations.

Check: The polynomial P(x) = (1100110) has factors P(x) = (10)(11)(11)(11)(11)(11)

Example 4:

Completely factor the polynomial P(x) = x^{5} + x^{4} + x^{3} + x^{2} + x + 1 =
(111111).

1. By inspection, since the smallest term is 1, then (10)=x is not a factor.

2. By inspection, since there is an even (6) number of terms, then (11)=x+1 is a factor.

Check with a test division. As expected, division by (x+1) yields a zero remainder, and a factor is found. This polynomial is not irreducible.

10101 quotient = xTherefore: x^{4}+ x^{2}+ 1 -------- 11 ) 111111 11 -- 011 11 -- 011 11 -- 00 remainder = 0

It is now necessary to check for further factors of the quotient q(x) = x^{4}+x^{2}+1 = (10101).

1. By inspection, since the smallest term is 1, then (10)=x is not a factor.

2. By inspection, since there is an odd (3) number of terms, then (11)=x+1 is not factor.

3. The highest term is x^{4}, terms up to x^{2} must be tested (corresponding to the square root).

Consequently, it is necessary to test, at most, the following 'odd' polynomials:

a. (11) : x + 1 = (done by inspection) b. (101) : x^{2}+ 1 = (x+1)(x+1) c. (111) : x^{2}+ x + 1

And the only remaining test is with x^{2} + x + 1 = (111):

111 quotient = x^{2}+ x + 1 ------- 111 ) 10101 111 --- 100 111 --- 111 111 --- 000 remainder = 0

The division (1011111) / (111) = (111) with remainder 0

Therefore, the polynomial P(x) = (111111) has factors P(x) = (11) (111) (111).

Example 5:

Completely factor the polynomial P(x) = x^{6} + x^{5} + 1 = (1100001).

1. By inspection, since the smallest term is 1, then (10)=x is not a factor.

2. By inspection, since there is an odd (3) number of terms, then (11)=x+1 is not a factor.

3. The highest term is x^{6}, terms up to x^{3} must
be tested (corresponding to the square root).

It is necessary to test, at most, the following 'odd' polynomials:

a. (11) : x + 1 = (done by inspection) b. (101) : x^{2}+ 1 = (x+1)(x+1) c. (111) : x^{2}+ x + 1 d. (1001) : x^{3}+ 1 = (x+1)(x^{2}+x+1) e. (1011) : x^{3}+ x + 1 f. (1101) : x^{3}+ x^{2}+ 1 g. (1111) : x^{3}+ x^{2}+ x + 1 = (x+1)(x^{2}+1)

Where some test divisions could be avoided if the obvious factorable terms are skipped, as shown above.

Test division by (111):
10110 --------- 111 ) 1100001 111 --- 0100 111 --- 110 111 --- 011 = remainder |
Test division by (1011):
1110 --------- 1011 ) 1100001 1011 ---- 1110 1011 ---- 101 1011 ---- 0011 = remainder |
Test division by (1101):
1001 --------- 1101 ) 1100001 1101 ---- 001001 1101 ---- 0100 = remainder |

Because all possible factors of P(x) have been tested up to the square root of P(x), then P(x) is irreducible.

Note that only three long divisions were actually required to check this polynomial of degree 6.

Table of Irreducible Polynomials

**Definition:** An irreducible polynomial P(x) of degree N is primitive if P(x) is a factor of x^{M}+1 for M=2^{N}-1 *and no smaller M*.

In GF(2), the expression x^{M}+1 is equivalent to x^{M}-1 and this definition may be written using either form.

Example 6: **A Primitive Polynomial** - The polynomial P(x)=x^{3}+x+1=(1011) of degree 3 is irreducible. Let M=2^{3}-1=7. Because P(x) is a factor of x^{7}+1=(10000001) but is not a factor of any smaller x^{M}+1, then P(x) is primitive.

Example 7: **A Prime but not Primitive Polynomial** - The polynomial P(x)=x^{4}+x^{3}+x^{2}+x+1=(11111) of degree 4 is irreducible. Let M=2^{4}-1=15. Although P(x) is a factor of x^{15}+1=(1000000000000001) it is also factor of the smaller x^{5}+1=(100001) and P(x) is not primitive.

Observe the value 11 (highlighted) as the division proceeds below. This value is
essentially being *shifted* across P(x). It has already been
noted that subtraction is equivalent to XOR. Consequently, the
division reduces to shifting 11 across P(x) and performing the XOR
operation if the msb of both values equals 1.

1 0 1 1 1 1 1 = x^{6}+ x^{ 4}+ x^{3}+ x^{2}+ x + 1 ----------------- 1 1 ) 1 1 1 0 0 0 0 1 1 1 XOR --- 0 1 1 1 no! --- 0 1 0 1 1 XOR ----- 1 0 1 1 XOR --- 1 0 1 1 XOR --- 1 0 1 1 XOR --- 1 1 1 1 XOR --- 0 remainder = 0

Fri May 17 21:49:46 ADT 2024
Last Updated: 15 JAN 2012 |
Richard Tervo [ tervo@unb.ca ] | Back to the course homepage... |