Galois Field

Content
History
Group
Finite Field (Galois Field)
Properties of Galois Field
Binary Field Arithmetic
Vector Spaces
Applications of finite fields
Parity Check code
The theory of finite fields as we know it today was constructed at

the end of the 18th century and during the 19th century.
The main researchers of the area are
Carl Friedrich Gauss (1777-1855)
Evariste Galois (1811-1832).
Gauss worked on problems in finite fields (possibly) around
1797-1798, at the time when he was working on his famous
Disquisitiones Arithmeticae (1801).
Galois paper Sur la theorie des nombres marks the beginning
of finite fields or Galois fields.
Eliakim H. Moore in 1893 proved that finite fields must have pm
elements, where p is a prime and m is any integer.
Group
Definition :- A set G on which a binary operation * is defined is
called a group if the following conditions are satisfied :
1. The binary operation * on G should be associative. That is for any a, b ,c

in G,
a*(b*c)=(a*b)*c
2. The binary operation * on G should be commutative. That is for any a and
b in G,
a*(b*c)=(a*b)*c
3.
4.
G contains an element e such that, for any a in G

a*e=e*a=a
this element e is called an identity element.
For any element a in G, There exists another element a in G such that,
a*a=e
Where a is the inverse of a.
Finite Field
Definition :- Let F be a set of elements on which two binary
operations, called addition + and multiplication . , are
defined. The Set F with the two binary operations + and . Is a
field if the following conditions are satisfied:
Finite Field is denoted by GF(q), Where q is a Prime.
Characteristic of a Finite Field
Properties of Finite Fields

1. The characteristic of a finite field is prime.
2. if a is a nonzero element of a finite field GF(q)
then aq-1 = 1.
3. Let a be a nonzero element in a finite field GF(q).
Let n be the order of a. Then n divides q-1.
4. In a finite field GF(q) a nonzero element a is said
to be primitive if the order of a is q-1.
Binary Field Arithmetic

In general we can construct codes with symbols from
Galois field GF(q), where q is a prime.
However codes with symbols from the binary field
GF(2) are most widely used in digital data
transmission and storage systems.
Information in these systems is universally coded in
binary form for practical reasons.
Therefore we will use binary arithmetic.
continue
In binary arithmetic we use modulo-2 addition and

multiplication, which are defined by the following tables.
This arithmetic is similar to ordinary arithmetic, except

that 1+1=0 instead of 2.
The reason is that in GF(2) there are only two elements
0 and 1 and if the result of any operation is different
from these values we take (i*j/2)=r. where I, j and r are
the element of GF(2).
Computations with polynomialas
Here we will consider polynomials whose

coefficients are from GF(2). A polynomial f(x) with one
variable x and with coefficients from GF(2) is given by
f(x)= f0+ f1x + f2x2 + f3x3 +..+ fnxn
Where fi is 0 or 1 for 0< i < n.
The degree of the polynomial is the largest power
of x.
Polynomials over GF(2) can be added, subtracted,
multiplied and divided in the usual way.
when f(x) is divided by g(x) we obtain a unique pair
of polynomials over GF(2),
f(x) = Q(x)g(x) + r(x)
where Q(x) = Quotient and r(x) = remainder.
continue
If r(x) = 0, then we say f(x) is divisible by g(x) and g(x) is a

factor of f(x).
For real numbers if a is a root of a polynomial Z(s), then
Z(a)=0, and Z(s) is divisible by s-a.
This statement is still true for polynomials over GF(2).
Irreducible polynomial
a polynomial p(x) over GF(2) of degree m is said to
be irreducible over GF(2) if p(x) is not divisiable by
any polynomial over GF(2) of degree less than m but
greater than zero.
Any irreducible polynomial over GF(2) of degree m
divides x2^(m-1)+1.
Primitive Polynomial
An Irreducible polynomial p(x) of degree m is said to
be primitive if the smallest positive n for which p(x)
divides xn +1 where n = 2m-1.
Vector Space
Linearly Independent vectors

A set of vectors v1 v2 v3 vk over a field F is said
to be linearly independent if and only if there exist k
scalars s1 s2 s3 sk (not all zero) from F, such that
s1v1 + s1v1 +s1v1 +..+s1v1 0.
For example vectors(1 0 1 1 0), (0 1 0 0 1) and

(1 1 0 1 1 ) are linearly independent.
Linearly independent vectors are used to form the
generator matrix in the linear block code.
Applications of finite fields
in cryptography
in coding theory
in engineering
in pure mathematics
Parity Check
Parity check is of two types one dimensional
and two dimensional.
In parity check a parity bit is added to every
data unit so that the no. of ones is either even
or odd.
In even/odd parity we make the no. of ones
even/odd.
Suppose the sender wants to send the word world. In

ASCII the five characters are coded as
1110111 1101111 1110010 1101100 1100100
The following shows the actual bits sent
11101110 11011110 11100100 11011000
11001001
Two-dimensional parity
In two-dimensional parity check, a block of bits is
divided into rows and a redundant row of bits is
added to the whole block.
The sender follows these steps:

The unit is divided into k sections, each of n bits.
All sections are added using ones complement to get
the sum.
The sum is complemented and becomes the checksum.
The checksum is sent with the data.
The receiver follows these steps:

The unit is divided into k sections, each of n bits.
All sections are added using ones complement to get
the sum.
The sum is complemented.
If the result is zero, the data are accepted: otherwise,
rejected.

Galois Field

Uploaded by

Copyright:

Available Formats

Galois Field

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Galois Field

Uploaded by

Copyright:

Available Formats

Content

The theory of finite fields as we know it today was constructed at

1. The binary operation * on G should be associative. That is for any a, b ,c

G contains an element e such that, for any a in G

Characteristic of a Finite Field

Properties of Finite Fields

Binary Field Arithmetic

In binary arithmetic we use modulo-2 addition and

This arithmetic is similar to ordinary arithmetic, except

Computations with polynomialas

Here we will consider polynomials whose

If r(x) = 0, then we say f(x) is divisible by g(x) and g(x) is a

Linearly Independent vectors

For example vectors(1 0 1 1 0), (0 1 0 0 1) and

Applications of finite fields

Suppose the sender wants to send the word world. In

The sender follows these steps:

The receiver follows these steps:

You might also like