Home Online Manual
Top
Back: Decoding codes with Groebner bases
Forward: Cooper philosophy
FastBack: Non-commutative algebra
FastForward: References
Up: Decoding codes with Groebner bases
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

C.8.1 Codes and the decoding problem

Codes

  • Let $F_q$ be a field with $q$ elements. A linear code $C$ is a linear subspace of $F_q^n$ endowed with the Hamming metric.
  • Hamming distance between x,y $\in F_q^n: d(x,y)=\char93 \{i\vert x_i\ne y_i\}$. Hamming weight of x $\in F_q^n: wt(x)=\char93 \{i\vert x_i\ne 0\}$.
  • Minimum distance of the code $C: d(C):=\min_{{\bf x,y}\in C, {\bf x}\ne {\bf y}}(d({\bf x,y}))$.
  • The code $C$ of dimension $k$ and minimum distance $d$ is denoted as $[n,k,d]$.
  • A matrix $G$ whose rows are the base vectors of $C$ is the generator matrix.
  • A matrix $H$ with the property ${\bf c}\in C\iff H{\bf c}^T=0$ is the check matrix.

Cyclic codes

The code $C$ is cyclic, if for every codeword ${\bf c}=(c_0,\dots,c_{n-1})$ in $C$ its cyclic shift $(c_{n-1},c_0,\dots,c_{n-2})$ is again a codeword in $C$. When working with cyclic codes, vectors are usually presented as polynomials. So ${\bf c}$ is represented by the polynomial $c(x)=\sum_{i=0}^{n-1}c_ix^i$ with $x^n=1$, more precisely $c(x)$ is an element of the factor ring $F_q[X]/\langle X^n-1 \rangle$. Cyclic codes over $F_q$ of length $n$ correspond one-to-one to ideals in this factor ring. We assume for cyclic codes that $(q,n)=1$. Let $F=F_{q^m}$ be the splitting field of $X^n-1$ over $F_q$. Then $F$ has a primitive $n$-th root of unity which will be denoted by $a$. A cyclic code is uniquely given by a defining set $S_C$ which is a subset of $Z\!\!\! Z_n$ such that

\begin{displaymath} c(x) \in C \ \hbox{ if } \ c(a ^i )=0 \ \hbox{ for all } \ i \in S_C. \end{displaymath}

A cyclic code has several defining sets.

Decoding problem

  • Complete decoding: Given $y\in F_q^n$ and a code $C\subseteq F_q^n$, so that $y$ is at distance $d(y,C)$ from the code, find $c\in C: d(y,c)=d(y,C)$.
  • Bounded up to half the minimum distance: With the additional assumption $d({\bf y},C)\le(d(C)-1)/2$, a codeword with the above property is unique.

Decoding via systems solving

One distinguishes between two concepts:
  • Generic decoding: Solve some system $S(C)$ and obtain some "closed" formulas $CF$. Evaluating these formulas at data specific to a received word ${\bf r}$ should yield a solution to the decoding problem. For example for $f\in CF: f(syndrome({\bf r}),x)=poly(x)$. The roots of $poly(x)=0$ yield error positions, see the section on the general error-locator polynomial.
  • Online decoding: Solve some system $S(C,{\bf r})$. 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.