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:
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:
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 pm). The resulting Galois field is labeled GF(pm) and has pm elements.
Reference: Encyclopedia of Mathematics : Galois FieldSpecificially, let a=3 then successive powers of 3n describe all the non-zero field elements {1,3,2,6,4,5} for n= 0 to 5. For example, 33=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 = 3n then the operation log3(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(2m) in which the arithmetic operations differ from ordinary addition and multiplication. The simplest of these is GF(2).
NEXT: The Galois Field GF(2)
Thu Mar 28 17:06:49 ADT 2024
Last Updated: 05 JAN 2015 |
Richard Tervo [ tervo@unb.ca ] | Back to the course homepage... |