ECE4253 Digital Communications | |

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

The *Galois field* is especially important in digital communications.
The definition of a Galois field emerges from the essential mathematical characteristics of groups, rings and fields.

A **group** is a set **S** along with an operation (e.g. "+") that acts on two elements {A,B} of the set and obeys the properties of:

- Closure: the result of A + B is always an element of
**S**. - Associative: A + (B + C) = (A + B) + C
- Identity: There is an identity element I such that A + I = A for all A
- Inverse: There is always some element B such that A + B = I for any A

The **order** of a group is the number of elements in the set **S**.

An **Abelian group** or **commutative group** is a group whose properties also include:

- Commutative: (A+B) = (B+A)

An **additive group** is an Abelian group under "+" which may not be addition in the usual sense.

A **multiplicative group** is an Abelian group under "×" which may not be multiplication in the usual sense.

A **ring** is a additive group with a second operation (e.g. "×") that obeys the properties of associative and is
distributive over addition.

A **commutative ring** is a ring whose multiplication properties also include commutative.

A **field** is a commutative ring whose properties also include a multiplicative inverse (for non-zero elements).

A **Galois field** is a finite field under specific "+" and "×" operations.

• The set of non-negative integers S={0,1,2,3,...} is not a group under ordinary addition as there is no inverse *B* to give A+*B*=0 without negative integers. (inverse)

• The set of all integer multiples of *n* is an additive group. For example, with *n*=3, the set
S={...,-9,-6,-3,0,+3,+6,+9,...} is an additive group.

• The set of all integer multiples of *n* is not a multiplicative group. For example, with *n*=3, the set
S={...,-9,-6,-3,0,+3,+6,+9,...} has no identity element under multiplication.

• The set of all integers is an commutative ring under ordinary addition and multiplication. This set is not a field as it does not include a multiplicative inverse.

• The set of real numbers is a field under ordinary addition and multiplication. This suggests that the manipulation of Galois fields will follow many of the familiar rules of arithmetic.

By specifying a finite set and operations based on *modulus arithmetic* the same set S may be a field, depending on the specific modulus.

• Let the set be S={0,1,2,3,...,*n-1*} where *n*=7 in the above example.

• Let the "+" operation be defined as "addition modulo *n*" for integer *n*. The finite set S={0,1,2,3,...,*n*-1} is an additive group. Closure is ensured since (A+B) modulo *n* will always
be an element of S. For example, with *n*=7 giving the set S={0,1,2,3,4,5,6}, the addition (3+6) modulo 7 = 2 which is
an element of S. The identity element I=0 for addition. The additive inverse requires that for each element A, there is an B such that (A+B) modulo 7 = 0. With A=3, for example, then (3+4) modulo 7 = 0 and the same result can be found for all elements of S.

• Let the "×" operation be defined as "multiplication modulo *n*" for integer *n*. The finite set S={0,1,2,3,...,*n*-1} is a multiplicative group *only if n is a prime integer*. As with addition, closure is ensured for any *n* since (A×B) modulo *n* will always be an element of S.
The identity element I=1 for multiplication. The multiplicative inverse requires that for each non-zero element A, there is an B such that (A×B) modulo 7 = 1. With A=3, for example, then (3×5) modulo 7 = 1 and the same result can be found for all elements of S as shown in the table
below. This outcome emerges only when the modulus *n* is a prime. As a counterexample with modulus *n*=6, the calculation (3×B) modulo 6 can only equal 0 or 3 whatever the value of B and will never equal I.

Using MATLAB, the modulo 7 multiplication table below shows that for each non-zero element A there is an inverse element B such that A×B=1.

>> AxB = mod((1:6)'*(1:6),7) AxB = 1 2 3 4 5 6 2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 5 3 1 6 4 2 6 5 4 3 2 1

• In summary, the ring of integers modulo *n* is a finite field
only if *n* is a prime p (or the power p^{m}). The
resulting Galois field is labeled GF(p^{m}) and has p^{m} elements.

Specificially, let a=3 then successive powers of 3^{n} describe all the non-zero field elements {1,3,2,6,4,5} for n= 0 to 5. For example, 3^{3}=6 in this sytem.

Using MATLAB, these terms are found as:

>> mod(3.^(0:5), 7) ans = 1 3 2 6 4 5

The terms repeat periodically for larger *n*. This result is not obtained for a=2; however, a=5 also generates these elements (in a different order). The only primitive roots of this field are {3,5}.

It follows that if A = 3^{n} then the operation log_{3}(A) = n exists as the *discrete logarithm* of A for this
particular field. In general, the direct computation of such logarithms is not straightforward and the use of a lookup table is one possible approach.

The above finite field is written as GF(7) and is defined on modulo 7 addition ('+') and multiplication
('×') operations. The fields of specific interest in digital communications are those finite fields of the form GF(2^{m}) in which the arithmetic operations differ from ordinary addition and multiplication. The simplest of these is GF(2).

NEXT: The Galois Field GF(2)

Fri May 17 21:04:41 ADT 2024
Last Updated: 05 JAN 2015 |
Richard Tervo [ tervo@unb.ca ] | Back to the course homepage... |