
C.8.1 Codes and the decoding problem
Codes

Let be a field with elements. A linear code is a linear subspace of endowed with the
Hamming metric.

Hamming distance between x,y
.
Hamming weight of x
.

Minimum distance of the code
.

The code of dimension and minimum distance is denoted as .

A matrix whose rows are the base vectors of is the generator matrix.

A matrix with the property
is the check matrix.
Cyclic codes
The code is cyclic, if for every codeword
in its
cyclic shift
is again a codeword in .
When working with cyclic codes, vectors are usually presented as polynomials.
So is represented by the polynomial
with , more
precisely is an element of the factor ring
.
Cyclic codes over of length correspond onetoone to ideals in this factor ring.
We assume for cyclic codes that . Let be
the splitting field of over . Then has a primitive th root of unity which will be denoted by .
A cyclic code is uniquely given by a defining set which is a subset of such that
A cyclic code has several defining sets.
Decoding problem

Complete decoding: Given and a code
, so that is at distance from
the code, find
.

Bounded up to half the minimum distance: With the additional assumption
, a codeword with the above property
is unique.
Decoding via systems solving
One distinguishes between two concepts:

Generic decoding: Solve some system and obtain some "closed" formulas . Evaluating these formulas
at data specific to a received word should yield a solution to the decoding problem. For example for
. The roots of yield error positions, see the section on the
general errorlocator polynomial.

Online decoding: Solve some system . The solutions should solve the decoding problem.
Computational effort
 Generic decoding. Here, preprocessing is very hard, whereas decoding is relatively simple (if the formulas are sparse).
 Online decoding. In this case, decoding is the hard part.
