# Singular

### 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.