Galois Fields: GF(2) and GF(2m) and Primitive Polynomial

Galois Fields: GF(2) and GF(2^m)

---

1. What is a Galois Field (GF)?

A Galois Field (GF) is a finite set of elements in which the four basic arithmetic operations—addition, subtraction, multiplication, and division (except by zero)— are all well defined and closed.

GF(q) ⇒ a field with exactly q elements

---

2. The Simplest Field: GF(2)

GF(2) is the smallest possible finite field and forms the foundation of all digital systems.

GF(2) = {0, 1}

Addition in GF(2)

Addition is performed modulo 2 (XOR operation):

+	0	1
0	0	1
1	1	0

Multiplication in GF(2)

×	0	1
0	0	0
1	0	1

GF(2) is used in binary logic, XOR operations, and simple error-control codes.

---

3. Meaning of GF(2^m)

GF(2^m) is a finite field containing exactly 2^m elements. Each element represents an m-bit symbol.

Field	Number of Elements
GF(2)	2
GF(2²)	4
GF(2³)	8
GF(2⁸)	256

Important: GF(2^m) is not integer arithmetic modulo 2^m. It is polynomial-based arithmetic.

---

4. Example: GF(2²)

Primitive Polynomial

p(x) = x² + x + 1

Field Elements

Element	Polynomial	Binary
0	0	00
1	1	01
α	x	10
α + 1	x + 1	11

Addition Example

(α + 1) + α = 1

Multiplication Example

α · (α + 1) = α² + α

α² = α + 1 ⇒ result = 1

---

5. Example: GF(2³)

Primitive Polynomial

p(x) = x³ + x + 1

α³ = α + 1

Field Elements

Power	Polynomial	Binary
α⁰	1	001
α¹	α	010
α²	α²	100
α³	α + 1	011
α⁴	α² + α	110
α⁵	α² + α + 1	111
α⁶	α² + 1	101

---

6. Mathematical Definition of GF(2^m)

GF(2^m) = GF(2)[x] / <p(x)>

This means:

• Elements are polynomials of degree < m
• Coefficients are binary (0 or 1)
• Addition is XOR
• Multiplication is polynomial multiplication followed by reduction modulo p(x)

---

7. Summary

• GF(2) is the binary field
• GF(2^m) extends GF(2) using polynomials
• RS coding operates on GF(2^m) symbols
• Arithmetic is polynomial-based, not integer-based

A Galois Field GF(2^m) is a finite field containing 2^m elements, constructed using binary polynomials of degree less than m, with arithmetic performed modulo an irreducible primitive polynomial.

Further Reading

1. Use of Galois Field in Red-Solomon Coding