|
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 one-to-one 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 error-locator 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.
|