Read Solomon Project(Page 1)

ICMS

Page:

Related Projects :

ARITHMETIC OF FINITE FIELDS

Fields

A field is a set F with two binary operations (both associative and commutative), called 'addition' (+) and 'multiplication' (´) satisfying:

Identity	$ an element, denoted by 0: a + 0 = 0 + a = a	$ an element (not 0), denoted by 1: a ´ 1 = 1 ´ a = a
Inverse	For each aÎF, $ b: a + b = b + a = 0	For each aÎF and a¹0, $ b: a ´ b = b ´ a = 1
Distributive Law	a ´ (b + c) = (a ´ b) + (a ´ c)

Some well-known examples of fields are the sets of rational numbers, real numbers and complex numbers. A field with a finite number of elements is called a finite field.

Finite Fields

The simplest example of finite fields is F₂, which has only two elements (the ones guaranteed by the existence of identities). So F₂ = {0,1}. Here

0 + 0 = 1 + 1 = 0; 0 + 1 = 1 + 0 = 1

0 ´ 0 = 0 ´ 1 = 1 ´ 0 = 0; 1 ´ 1 = 1.

Similarly, for each prime p, the set F_p = {0,1,2,&,p-1}is a field where addition and multiplication are defined modulo p.

For example, for p = 7, 4 + 5 = 2 in F₇

The easiest way of 'constructing' larger (finite) fields from a given small field F is by 'attaching' a root (b) of an irreducible polynomial over F. [The set of complex numbers is obtained this way by 'attaching' a root (i) of the polynomial x² + 1 to the field of real numbers]. In fact all finite fields are constructed in this manner. It can be shown that the number of elements of a finite field is always some power of a prime power.

Construction of a field with eight elements

As an example we construct the field of order 8, GF(8), by attaching b, a root of the polynomial x³ + x + 1 over F₂.

Elements of GF(8) are polynomials over F₂ in b of degree at most two:

a₂b² + a₁b + a₀

(a₂, a₁, a₀) which is read as the integer whose binary representation is a₂a₁a₀

We add or multiply elements of GF(8) as polynomials and then use

b³ = - b - 1 (and hence b⁴ = - b² - b )

and arithmetic of F₂ to reduce the result to a polynomial of degree at most two.

For example, in GF(8) which is the set {0,1,2,&,7},

6 ´ 7 = (1,1,0) ´ (1,1,1)

= (b² + b) ´ (b² + b+ 1) = b⁴ + b = - b² = b² = (1,0,0) = 4.

Thus we have the following look-up tables:

+	0	1	2	3	4	5		6	7
0	0	1	2	3	4	5	6		7
1		0	3	2	5	4	7		6
2			0	1	6	7	4		5
3				0	7	6	5		4
4					0	1	2		3
5						0	3		2
6							0		1
7									0

×	1	2	3	4	5	6		7
1	1	2	3	4	5	6	7
2		4	6	3	1	7	5
3			5	7	4	1	2
4				6	2	5	1
5					7	3	6
6						2	4
7							3

The nonzero elements of a finite field always form a cyclic multiplicative group. Any generator is called a primitive element of the field. 2 is a primitive element for GF(8).

This field is used in the computer display of Reed - Solomon codes.