Chapter 2 - Introduction to Algebra


Group: a binary operation denoted as * on a set that meets these conditions:

Example of a group: XOR on binary numbers (Group = {0,1}, binary operation = XOR, identity elem = 0). Denoted as ⊕. Also called modulo-2 addition.


Have two elements: addition and multiplication, which meet the following:

Like with groups, Order is the size of the field and a finite field has a finite, known number of elements

Prime Fields

Binary Field Arithmetic

Most error coding algs use GF(2) or GF(2m)

Binary Field Polynomials

Regular polynomials where there is one variable and its coefficients are either 0 or 1

Binary Polynomial Arithmetic

Properties of Binary Field Polynomials

Galois Field GF(2m)

Field over GF(2) with 2m elements as opposed to just 0 and 1

Properties of GF(2m)

Finding the Minimal Polynomial of B

Example Computations Using GF(2m)

Vector Spaces

Vector space over GF(2)


A k by n matrix G over GF(2) has k rows and n columns, where each entry is in GF(2) (0 or 1)