Coding theory MOC

Code

A 𝑞-ary code C of length 𝑛 is a inhabited subset C ⊆𝑆𝑛𝑞, where 𝑆𝑞 is a set (called an alphabet) containing 𝑞 letters.¹ code

• An element 𝑥 ∈C is thence called a codeword.
• The Hamming distance 𝑑(𝑥,𝑦) between codewords 𝑥,𝑦 ∈𝐶 is the number of positions in which they differ, and makes 𝑆𝑞 a metric space.
• The weight of a code is the distance from the zero-codeword wt⁡𝑥 =𝑑(⃗𝟎,𝑥), where ⃗𝟎 consists of some distinguished letter 0 ∈𝑆.

Following van Lint, a code if length 𝑛 with 𝑀 codewords and ^minimumDistance 𝑑 is called an (𝑛,𝑀,𝑑)-code. An important special case is a linear code, where we take 𝑆𝑞 =𝕂𝑞, the Galois field of order 𝑞, and require C ≤𝕂𝑛𝑞 to be a vector subspace.

Further notions

• The minimum distance of a non-unary code C is

min{𝑑(𝑥,𝑦):𝑥,𝑦∈C;𝑥≠𝑦}

• The minimum weight of a non-unary code is

  min{wt⁡𝑥:𝑥∈C;𝑥≠⃗𝟎}

• The information rate of a 𝑞-ary code C of length 𝑛 is

  𝑅=𝑛−1log𝑞⁡|C|

• The covering radius of a a code C ⊆𝑆𝑛𝑞 is the minimum radius required for Hamming balls around codewords to cover the whole space, i.e.

  cov⁡(C)=max{min{𝑑(𝑐,𝑥):𝑐∈C}:𝑥∈𝑆𝑛𝑞}

• Equivalence of codes

Special kinds of code

• Linear code

• Perfect code

• Systematic code

---

tidy | en | SemBr

Footnotes

1. 1999. Introduction to coding theory, §3.1, pp. 33–34 ↩