Linear code

A $𝑞$ -ary linear code of length $𝑛$ and dimension $𝑘$ is a $𝑘$ -dimensional vector subspace $C \leq 𝕂 𝑛 𝑞$ , #m/def/code where $𝕂 𝑞$ is the Galois field of order $𝑞$ . Thus it is a particular kind of code of length $𝑛$ in the alphabet $𝕂 𝑞$ . Following van Lint, a $𝑘$ -dimensional linear code of length $𝑛$ and minimum distance $𝑑$ is called an $[𝑛, 𝑘, 𝑑]$ code, where the $𝑑$ is optional.¹ Of particular interest are binary linear codes.

Further notions

A code is degenerate iff some digit is zero for all codewords.
$𝕂 𝑛 𝑞$ is equipped with a natural nondegenerate symmetric bilinear form
$⃗ 𝐱 \cdot ⃗ 𝐲 = ⃗ 𝐱 𝖳 ⃗ 𝐲 = 𝑛 \sum 𝑖 = 1 𝑥 𝑖 𝑦 𝑖$
which is used to define the Orthogonal code.
A generator matrix $𝐴$ has $C$ as its row space, and is said to be in standard form iff it is in reduced row echelon form $𝐴 = [𝟙 𝑘 ∣ 𝑃]$ . The first $𝑘$ digits are thence information digits and the latter are parity check digits. Every code is equivalent to one generated by such a standard form matrix.
The generator matrix $𝐻 = [- 𝑃 𝖳 ∣ 𝟙 𝑘]$ of the Orthogonal code is called the parity check matrix, since $𝑥 \in C ⟺ 𝑥 𝐻 𝖳 = ⃗ 𝟎$ .
The value of $s y n 𝑥 = 𝑥 𝐻 𝖳$ is called the syndrome of $𝑥$ . Syndromes uniquely label cosets $𝐾 s y n 𝑥 \in 𝕂 𝑛 𝑞 / C$ in the quotient.
In a given coset $𝐾 s y n 𝑥 \in 𝕂 𝑛 𝑞 / C$ a minimum weight string $𝑙 s y n 𝑥 \in 𝐾 s y n 𝑥$ is called a coset leader, and the correction of a string $𝑥$ is $𝑥 - 𝑙 s y n 𝑥$ . Thus a perfect code has unique coset leaders.
Linear equivalence of codes

Properties

The information rate of a $[𝑛, 𝑘]$ -code is $𝑛 / 𝑘$ .
The minimum distance of a linear code is its minimum weight.

Special kinds of linear code

Projective code

Linear code

Further notions

Properties

Special kinds of linear code

See also

Footnotes