Algebraic and Stochastic Coding Theory

10

Cyclic Codes

10.1  Definition

Cyclic codes were first studied by Prange [1957]. They are a special class of linear codes defined as follows: A subset S of $F_q^n$ is cyclic (or of cyclic order, or a cyclic shift of one position) if

$\{a_0,a_1,\dots ,a_{n-1}\}\in S\to \{a_{n-1},a_0,a_1,\dots ,a_{n-2}\}\in S.$

This can be regarded as the conversion of a combinatorial structure S into an algebraic structure, also in S. The cyclic shift of r positions is defined as

$\{a_0,a_1,\dots ,a_{n-1}\}\in S\to \{a_{n-r},\dots ,a_{n-1},a_0,a_1,\dots ,a_{n-r-1}\}\in S.$

See §C.1 for cyclic permutations. A linear code C is called a cyclic code if C is a cyclic set. The elements of S can be the codewords $c_n\in F_q^n$. Then the cyclic shift of r positions of codewords in $F_q^n$ is

$\{c_0,c_1,\dots ,c_{n-1}\}\in F_q^n\to \{c_{n-r},\dots ,c_{n-1},c_0,c_1,\dots ,c_{n-r-1}\}\in F_q^n.$

Cyclic codes were the ...