... from
http://www.anujseth.com/crypto/ffield.html
Author: R. Beresford, EN160, VLSI Design, Spring 1997
A field is a set of numbers with an addition operation and a multiplication
operation. The result of adding any two numbers or multiplying any two numbers
of the field has to be in the set as well. There has to be a zero element, such
that adding zero to any element of the set gives you the element you started with.
And there has to be an identity element, such that multiplying any element by the
identity gives you the element itself. Some other familiar properties are also
required: there are additive and multiplicative inverses for every number (except
that zero has no multiplicative inverse); and the commutative, associative, and
distributive laws are obeyed in the ways you know from ordinary arithmetic.
Examples: the real numbers, the complex numbers, the rational numbersóall
of these with ordinary addition and multiplication satisfy the field properties.
However, all of these obvious examples have an infinite number of elements. A field
with a finite number of elements would have the interesting feature that arithmetic
could be done exactly by finite machines, such as computers. Would such a field of
numbers be useful for anything? Finite-field arithmetic has important applications
to error-correcting codes, which are essential technology.
There are lots of finite fields one can investigate. A key fact to absorb at the
beginning is this: the operations of addition and multiplication are not
going to be the familiar onesówe will be using ordinary-looking numbers and
doing things to them that we call ìadditionî and ì
multiplicationî, but which are definitely not the usual operations. If you
like, call them ìfield additionî and ìfield multiplication
î as a reminder. An example: suppose we do addition and multiplication
modulo p, where p is a prime number. (Modulo p means the
remainder after dividing by p). Then there is a finite field that can be
represented by the integers {0, 1, 2, .... p ñ1}. This field is
referred to as J/p:
J/p: the integers {0, 1, 2, .... p ñ1}
with p a prime number and arithmetic mod p.
Exercise 1.
For p = 7, find the additive and multiplicative inverses of all elements of
J / p .
Exercise 2.
Why does p have to be prime? Try doing the previous exercise with a set of
numbers where p is not prime.
Some one (Galois, perhaps) once got the idea of constructing a curious object that
can be said to combine the ordinary real numbers with elements from J /
p in a certain way, namely as a polynomial in the real variable x
whose coefficients are all taken from J / p. Adding two such
polynomials is to be done by field-adding the coefficients of like powers of
x, analogously to ordinary polynomial addition. Multiplying two such
polynomials is to be done by field-multiplying coefficientsóthe resulting
powers of x follow from the ordinary rules of arithmetic (exponents add).
Then like powers of x are to be collected using field addition. A
particular case will illustrate these ideas. When p = 2, the coefficients
are always going to be either 0 or 1. The arithmetic tables turn out to be the
logic functions XOR (for addition) and AND (for multiplication). An example of
such a polynomial would be P (x) = x
3 + x
2
+ 1 . At this point you could be wondering: when a field element ì
multipliesî a real number (a power of x), are we supposed to be doing
ordinary multiplication or field multiplication? The answer to this question never
actually is neededóbecause we donít try to evaluate P in any
ordinary sense. Its job will become clear shortly.
Exercise 3.
Show that (x
2 + x + 1)
2 = x
4
+ x
2 + 1 . Compare with the answer you would get in ordinary
arithmetic.
Exercise 4.
Can the polynomial x
3 + 1 be factored? If so, find its
factors.
For our purposes here, there are two important properties of polynomials like
P: their order, which is the highest power of x appearing; and
whether they are ìreducible,î meaning they can be factored, or
instead are irreducible . Take an irreducible polynomial of degree
m based on J / p. There is a unique field, called the Galois
field of order p
m, written as GF(p
m), that is
ìgeneratedî by this polynomial. For our example, using P
(x) = x
3 + x
2 + 1, which is irreducible,
we will be able to generate GF(2
3) = GF(8), a field of 8 elements. The
first step in generating the field is to decide that we can think about finding
ìrootsî of the polynomial (think about it, donít actually do
it!). If a is a root of P, then a
3 + a
2 + 1 = 0, or a
3 = a
2 + 1. (Make sure
you understand why these two equations are the same.) In general, of course, a
is a complex number. But who cares? All we want for now is that there is an
interesting progression of the powers of a that follows from the particular
form of the polynomial chosen:
a
0 = 1 a
4 = a * a
3 = a
(a
2 + 1) = a
3 + a = a
2
+ a + 1
a
1= a
a
5= a * a
4= a(a
2 +
a+1) = a
3+ a
2+a = a+1
a
2= a
2 a
6= a* a
5= a(a+1) = a
2+ a
a
3= a
2 + 1 a
7= a
* a
6= a(a
2+ a)
= a
3 + a
2= 1 = a
0
Clearly, all the higher powers of a will simply continue to reproduce this
cycle of 7 elements. To make this set the Galois field GF(8), we need to add the
eighth element, namely the 0 element. Do not make the mistake of thinking that we
need to calculate aóit is never done! All we need is this sequence
of powers of a, making up what is called the ìexponential
representationî of GF(8). Notice also how all powers of a can be
expressed in terms of 1, a, and a
2, as on the far-right-hand
sides of the previous equations. These first m =3 powers of a are
considered a ìbasisî for the ìpolynomial representationî
of GF(8). As it happens, there may be more than one irreducible polynomial of a
given degree. The Galois field that results will have a different order of the
elements, but the same essential structure in terms of addition and multiplication.
So it really doesnít matter which irreducible polynomial we start with.
Exercise 5.
Use the information just given to create the addition and multiplication tables
for GF(8).
Exercise 6.
Find a 4th-order irreducible polynomial over J /2 and generate GF(16) using
the method illustrated above.
As we have just seen, the field GF(2
m), with 2
m
elements, has two alternative representations, one in terms of powers of a
primitive root and the other in terms of a polynomial basis. To be specific, here
is an obvious way to represent the powers of a from our example of GF(8):
a
0: 000 a
4: 100
a
1: 001 a
5: 101
a
2: 010 a
6: 110
a
3: 011 0 : 111
In each case, we simply have the usual binary number that equals the exponent. The
only code left over for the zero element is then 111. If instead we choose to work
in the polynomial representation, one way to do so is to let the bits stand for 1,
a , and a
2, from least to most significant. With this
convention, the table would be:
a
0= 1 : 001 a
4= a
2+ a+
1 : 111
a
1= a: 010 a
5= a+1 : 011
a
2: 100 a
6= a
2+ a: 110
a
3= a
2 +1 : 101 0 : 000
Note that 0 has the more ìfamiliarî coding of 000.
Which representation should we work with? Refer back to Exercise 5 and you
will see that the multiplication table is simple to implement in the
exponential basisóall that is needed is addition of the exponents, with a
little care taken when the sum reaches (2
m ñ 1) or
greater. On the other hand, the good way to do addition is in the polynomial
basis, where it is nothing more than bitwise XOR.
Exercise 7.
Using the representations of GF(8) just given, verify that field addition is done
by bitwise XOR of the polynomial representation. Also, figure out how to implement
multiplication using the exponential representation.
Exercise 8.
Write down the exponential and polynomial representations for GF(16).
Exercise 9.
Find the sum of all the elements of the field for GF(16) and GF(8). (This result
is general.)
In error correction, we add extra bits to the data of interest in order to
impose some sort of structure. If the structure is corrupted, our knowledge of
what it should have been allows the errors to be corrected. In the simple case of
parity checks, the parity bits are made to depend on various subsets of the data
positions. If any one position goes bad, the parity bits that appear wrong can be
used to locate the position of the error. Reed-Solomon codes have the same spirit,
but a much richer mathematical structure, namely the structure of GF(2
m
). As a consequence of this rich structure, more errors can be corrected
for a given number of extra bits compared to simple parity checking.
Since it is extremely common to find byte-oriented computer hardware, choosing
8-bit data symbols is a natural move, although certainly not the only possible
one. With m =8, we get GF(2
8) = GF(256). The approach is to read
a certain number k of data symbols, less than (2
m ñ1),
and then put in extra symbols to get n =(2
m ñ1)
total. (The details of one way to do this encoding and decoding are embodied in
the program rsmain.c.) The resulting n-byte word will at various
times be treated as a polynomial in GF(2
m) in the sense that if
the symbols (bytes) of the word are D
0,D
1,
..., D
n ñ1, the word is considered to represent
the polynomial
D (x) = D
0+ D
1 x+
D
2 x
2+ .... + D
n ñ
1 x
n ñ1
Please do not be persuaded that this is like the polynomials introduced before,
with x a real number! No, now we are going to explicitly evaluate such
polynomials with x = a
k, some particular field element.
All of the arithmetic involved will be field arithmetic, and the result
of such an evaluation is of course just one field element or another. This is the
kind of calculation that allows every one of n input symbols to influence
each code symbol, and thereby impose an internal structure on the data.
There is a profusion of specific algorithms for implementing the Reed-Solomon
codes and here we will only consider one approach, hopefully a relatively simple
one. A particular Reed-Solomon code is defined by the parameters (n, k
) as introduced above. The coding theorists prove that such a code can correct up
to (n ñ k )/2 errors. Since n = (n ñ
k) is the number of extra symbols, this result basically says that for
every error you want to correct, you need two extra symbols. By the way, notice
that one error in this context means a bad byte, and so could be anywhere from 1
to 8 bits of bad data in a row. The encoding process is as follows:
1. Read k data symbols and form the input data word D consisting of
n zeros in positions D
0, D
1, ... ,
D
n ñ1 followed by the k data symbols in
positions D
n,D
n +1, ... D
n ñ1.
2. Form the code word symbols C
i by evaluating the data word
polynomial at the field elements a
ñi:
C
i = D (a
ñi ) = D
0 + D
1 a
ñi + D
2 a
ñ2i + .... + D
n
ñ1 a
ñ (nñ1) i
Exercise 10. Show that evaluating the resulting code-word polynomial C
(x) at the powers a
i gives back (decodes) the original
data word. (The result of Exercise 9 is useful here.)
The decoding process starts by evaluating the code-word polynomial at the first
n powers of a óbecause of how D was constructed, the
results should all be zero. These values are called the ìsyndromes.î
If they are not zero, there must have been errors occurring in the code word, and
adding these syndrome values back to the decoded word, position by position, will
restore zeros where they should be. But of course it is the other positions
of the decoded word that we really care about, the ones where the data should be.
We need to know the complete ìerror vectorî E (x) that
should be added into the decoded word to get the correct data. The first n
positions are given by the syndromes as just explained.
An error locator polynomial is defined as
L (x ) = 1 + L
1 x + L
2
x
2 + .... + L
n x
n
such that a
ñj is a root of L if and only if
j is the number of a position in the code word that is in error. Then
l
j = L (a
ñj ) is zero if and
only if e
j = E (a
ñj )
is not zero, because e
j is just the error that corrupted the
code word at position j . After transforming the received code word, the
error affects all of the decoded word positions. So it is basically by definition
true that l
je
j = 0 for all jand it then follows
as a matter of mathematics that there is a relation between L and E.
The relation is a convolution:
E
i = L
1 E
i
ñ1 + L
2 E
i ñ
2+ ... + L
n E
i ñ
n
This relation is used twice in decoding: first, with the known syndromes as
the first n positions of E in order to find the error locator and
second, with the known error locator to find the remaining components of the error
vector. The first task is the more involved one, and it is solved by a famous
algorithm due to Berlekamp and Massey. The second task is simpler because all of
the quantities on the right-hand side of the equation are then known.
Exercise 11.
Run the program rsmain.c and find out what happens to the decoded text
when the number of errors exceeds the capability of the code to correct them.
Chapters 1, 3 and 11 of the book by Hamming are a nice clear introduction to error
correction and algebraic coding (which is what we are doing here). The classic
book by Peterson and Weldon has lots of details, including Chapter 7 on switching
circuits that can implement the field arithmetic. The anthology edited by Wicker
and Bhargava is more up-to-date but possibly impenetrable. The article by Massey
shows a ircuit for his algorithm.
R.W. Hamming, Coding and Information Theory, (Prentice Hall: 1980).
J.L. Massey, IEEE Trans. Information Theory 15, 22 (1969).
W.W. Peterson and E.J. Weldon, Jr., Error-Correcting Codes, (MIT: 1972).
S.B. Wicker and V.K. Bhargava, ed.s, Reed-Solomon Codes and Their Applications, (IEEE: 1994).
Books RSS
