Chapter 5
Finite Field
Spring 2009
Ammar Abu-Hudrouss Islamic
University Gaza ١
Properties of Finite fields
Finite Field or Galois Field has q different possible values and has
the following properties
There are two defined operations, namely addition and
multiplication.
The result of adding or multiplying two elements from the field
is always an element in the field.
One element of the field is the element zero, such that a + 0 = a
for any element a in the field.
One element of the field is unity, such that a • 1 = a for any
element a in the field.
Channel Coding Theory
Slide ٢
١
Properties of Finite fields
Finite Field or Galois Field has q different possible values and has
the following properties
For every element a in the field, there is an additive inverse
element -a, such that a + ( - a) = 0.
For every non-zero element b in the field there is b
multiplicative inverse elementb -l , such that bb -1 = 1.
The associative a + (b + c) = (a + b) + c, a • (b • c) = (a • b) • c,
commutative a + b = b + a, a • b = b • a, and distributive a • (b +
c) = a • b + a • c laws apply.
Channel Coding Theory
Slide ٣
Prime Finite fields
These properties can be satisfied if the field size is any prime
number or any integer power of a prime.
The rules for a finite field with a prime number (p ) of elements
{0 ,1 ,2 ,…,p - 1 } can be satisfied by carrying out the arithmetic
modulo-p.
Example : Finite Field GF(3)
+ 0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
Channel Coding Theory
Slide ٤
٢
Prime Finite fields
Example : finite field GF(3)
X 0 1 2
0 0 0 0
1 0 1 2
2 0 2 1
The additive inverse of 0 is 0 and of 1 is 2.
The multiplicative inverse of 1 is 1 and the multiplicative inverse
of 2 is 2.
Channel Coding Theory
Slide ٥
Prime Finite fields
In any prime size field, it can be proved that there is always at
least one element whose powers constitute all the nonzero
elements of the field. This element is said to be primitive.
For example, in the field GF(7), the number 3 is primitive as
30 = 1
31 = 3
32 = 2
33 = 6
34 = 4
35 = 5
Higher powers of 3 just repeat the pattern as 36 = 1
Channel Coding Theory
Slide ٦
٣
Prime Finite fields
multiplication can be done by adding powers of the primitive
In GF(7)
6 x 2 = 33 x 32 = 35 = 5.
Hence we can find the multiplicative inverse of any element as 3i
as 3-i = 36-i.
the multiplicative inverse of 6 (33) is 6 (33),
the multiplicative inverse of 4 (34) is 2 (32)
and the multiplicative inverse of 5 (35) is 3 (31).
Channel Coding Theory
Slide ٧
Extension of Prime Field
We will consider extension of binary field ( p = 2)
The extended fields will inherit the module-2 addition (i.e the
addition and subtraction are the same)
For any field where q = 2m, there is a primitive where
m
2 1
1
or
m
2 1
1 0
One of the factor of this polynomial should equal zero and it
should not be in the form of n + 1 (n < 2m -1)
Channel Coding Theory
Slide ٨
٤
Extension of Prime Field
Take as an example the field GF(23). The factors of 7 + 1 are
7 1 1 3 1 3 2 1
Both the polynomials of degree 3 are primitive and so we choose,
arbitrarily,
3 1 0
This yields that the nonzero element of field is
2 2
0 1 1
3 1 4 3 2
4 4 3 2 2 1
6 5 3 2 2 1
Channel Coding Theory
Slide ٩
Extension of Prime Field
The nonzero powers of a can be multiplied by adding the powers
of a modulo-7.
To add two elements together, we must first express each
element as a binary polynomial in powers of a of degree 2 or
less.
Addition is then by modulo-2 addition of the terms of the
polynomial, for example:
3 4 1 2 2 1
Each element is its additive inverse (inherited from binary)
Channel Coding Theory
Slide ١٠
٥
Extension of Prime Field
The field elements can be assigned to any numeric value.
Addition and multiplication can be done as shown in the graph
Map to
Value 1
power of
Map to
Arithmetic
Result numeric
operation
value
Map to
Value 2
power of
Channel Coding Theory
Slide ١١
Polynomial representation of FF elements
To simplify the addition we can use the following representation
for the finite field elements in GF(8)
Element Coefficients value
2 1 0
0 0 0 0 0
0 0 0 1 1
1 0 1 0 2
2 1 0 0 4
3 0 1 1 3
4 1 1 0 6
5 1 1 1 7
6 1 0 1 5
Channel Coding Theory
Slide ١٢
٦
Polynomial representation of FF elements
The addition of two numbers can be done by the modulo-2
addition of bits.
If wish to add 3 to 6, the binary values 011 and 110 would be
added using exclusive OR to produce 101 (i,.e. 5). This confines
with
3 6 5
The multiplication is done by the previous methods adding the
power of alpha modulus 7.
4 3 2 3 5 7
6 3 4 3 7 0 1
2 7 1 5 6 5
Channel Coding Theory
Slide ١٣
Roots of Polynomial
Polynomial with real coefficients can be always factorized if we
using complex numbers
X 2 6 X 10 X 3 j X 3 j
The same analogy can be used for finite field irreducible
polynomial can be factorized in some extended field.
For example X3 + X + 1 is irreducible in the binary field
But in GF(8)
X 3 X 1 X X 2 X 4
Channel Coding Theory
Slide ١٤
٧
Roots of Polynomial
It can be easily verified for any binary polynomial f(X)
f X 2 f X 2
Which mean if is a root of the polynomial then 2, 4, 8 ,… are
also roots for the same polynomial.
The same applies to factorization over larger finite fields. If
f(x) is irreducible q-arry polynomial then it will have roots in
some extention GF(qm). The relation become
f X q f X q
Which mean if is a root of the polynomial then q, q2, q3 ,…
are also roots for the same polynomial.
Channel Coding Theory
Slide ١٥
Minimum polynomial
If an irreducible polynomial (X) has as a root, it is called the
minimum polynomial of (or of any of its other conjugate roots).
If is primitive element then (X) is primitive polynomial.
Consider GF(8) which is generated by primitive polynomial
X3+X+1
The roots of this primitive polynomial is ,2, and 4
Then X3 + X + 1 is minimal polynomial of ,2, and 4
Then X3 + X2 + 1 is minimal polynomial of 3,6, and 12
Channel Coding Theory
Slide ١٦
٨
Order of an Element
If m is the smallest integer value for which m= 1, then
the element is said to be of order m and it must be a root of
Xm + 1.
If it is also a root of some irreducible polynomial f(X), then f(X)
is a factor of Xm + 1.
Example: if we take = 3 ,in GF(8) example, the lowest value of
m for m = 1 is 7.
This means that 3 is of order 7 and it is a root of X7 + 1.
As 3 is a root of X3 + X2 + 1, then X3 + X2 + 1 is a factor of X7+
1.
Channel Coding Theory
Slide ١٧
Finite Field Elements as Roots of Polynomial
The roots ofXq + 1 where q = 2m-1, are the nonzero element of
GF(2m)
Example: in GF(8)
X 7 1 X 1 X 3 X 1 X 3 X 2 1
is a root of X3 + X + 1, hence 2 and 4 are also roots
3 is a root of X3 + X2 + 1 , hence 6 and 5 are also roots
The root of X + 1 is 1.
Then all the elements of the fields are roots of X7 + 1.
Channel Coding Theory
Slide ١٨
٩
Finite Field Elements as Roots of Polynomial
The roots ofXq+ 1 where q = 2m-1, are the nonzero element of
GF(2m)
X 7 1 X 1 X 3 X 1 X 3 X 2 1
Channel Coding Theory
Slide ١٩
Roots of an Irreducible polynomial
If we consider irreducible polynomial of degree c, it will have c
c-1 .
roots , 2, 4, ….,2
But 2c= hence 2c-1 =1.
Thus is a root of X2c-1 + 1.
As the roots of X2c-1 + 1 are the nonzero elements of GF(2c), any
irreducible polynomial of degree c always has roots in GF(2c)
Conversely, the factors of X2c-1 + 1 include all the irreducible
polynomials of degree c.
Channel Coding Theory
Slide ٢٠
١٠
Roots of an Irreducible polynomial
Example X3 + X + 1 and X3 + X2 + 1 are the only irreducible
polynomial of degree 3 as they are factors of X7 + 1
Channel Coding Theory
Slide ٢١
Factorization of Polynomial
To find the field in which polynomial has its factors, we find the
factors to begin with. The LCM c’ of the orders; the factor of
the polynomial can be found in GF(2c’).
Proof
2ab 1 2a 1
b
2ab a
2
1 2 1 a b 1
| 2a
b 2
2a
b 3
So 2a-1 is a factor of 2ab -1, and so 2c’ is a multiple of 2c – 1 if c’
is multiple of c.
Channel Coding Theory
Slide ٢٢
١١
Factorization of Polynomial
If c’ is multiple of the orders if akk the binary factors then all
the roots can be represented in GF(2c’).
An example , the polynomial X 5 + X 4 + 1 factories into
(X3 + X + 1) and (X2 + X + 1) . It therefore has factors in GF(26).
Channel Coding Theory
Slide ٢٣
Discrete Fourier Transform
The definition of the DFT of an w-point sequence in the field of
complex numbers is usually expressed in terms of the relation
between the frequency domain samples Vk and the time domain
samples vi:
n 1
Vk vi e j 2ik / n
i 0
In the finite field GF(2m) there will be a transform of v(X) into
V(z), equivalent to the Fourier transform, only if there is an nth
root of 1 within the field, i.e. a term
such that n= 1. This will be satisfied if
2m 1
c
n
Channel Coding Theory
Slide ٢٤
١٢
Discrete Fourier Transform over FF
There will be two particular cases of interest to us. One will be
the case where a binary vector of length 2m - 1 is transformed
over GF(2m); c = 1 and
n 1
Vk vi ik
i 0
The easiest way to visualize the Fourier transform from the
definition above is as follows. Regard the sequence to be
transformed as a polynomial f(X).
Now to calculate the transform coefficient in position k,
substitute X = k.
Channel Coding Theory
Slide ٢٥
Discrete Fourier Transform
Example
The sequence 0101100 is equivalent to X5 + X3 + X2. The Fourier
transform over GF(8) is
V0 1 1 1 1
V1 5 3 2 0
V2 3 6 4 0
V3 1 2 6 3
V4 6 5 1 0
V5 4 1 3 5
V6 2 4 5 6
Channel Coding Theory
Slide ٢٦
١٣
Discrete Fourier Transform
The inverse is given by
n 1
vi Vk ik
k 0
The inverse Fourier transform can be presented in a similar way.
Regard the sequence as a polynomial V(z) and substitute z = i to
obtain the value of the inverse transform in position i.
Channel Coding Theory
Slide ٢٧
Discrete Fourier Transform
Example
The sequence 0101100 is equivalent to z5 + z3 + z2. The inverse
Fourier transform over GF(8) is
V0 1 1 1 1
V6 2 4 5 6
V5 4 1 3 5
V4 6 5 1 0
V3 1 2 6 3
V2 3 6 4 0
V1 5 3 2 0
Channel Coding Theory
Slide ٢٨
١٤
Discrete Fourier Transform
Example
The sequence 12 20 60 is equivalent to.
X 6 2 X 5 X 4 2 X 3 6 X
The Fourier transform over GF(8) is
V0 1 2 2 6 4
V1 6 0 5 5 1 6
V2 5 5 2 2
V3 4 3 6 4 2 1
V4 3 1 3 0 3 0
V5 2 6 0 3 4 0
V6 1 4 4 6 5 6
Channel Coding Theory
Slide ٢٩
Discrete Fourier Transform
Then the Fourier transform of the sequence is 060264
The inverse Fourier can be found by the same method and it has
the sequence 6 20604
Note the relationship to the forward transform. The value of
both transforms in position 0 is the same
However, for the other positions, the inverse transform in
position i makes the same substitution as for the forward
transform in position n - k.
Therefore the only difference between the forward and inverse
transforms is a reversing of the order of the samples, other
than the one in position zero.
Channel Coding Theory
Slide ٣٠
١٥
Roots and Spectral Components
A consequence of the definition of the Fourier transform is that
roots of a polynomial in the time domain are related to zero
components in the transform over GF(2m).
A polynomial v(X) has a root k if and only if the component Vk
of the transform is zero.
Conversely, the polynomial v(X) has a zero component vi if and
only if a' is a root of the transform polynomial V(z).
Channel Coding Theory
Slide ٣١
Roots and Spectral Components
As an example, the binary sequence 0001011 is equivalent to X3
+ X + 1.
As this is the primitive polynomial used to generate the finite
field GF(8), it is the minimum polynomial of a and therefore has
roots a, a2 and a4.
Thus we would expect the frequency components V1, V2 and ¥4
to be zero, and this is found to be the case.
Channel Coding Theory
Slide ٣٢
١٦
