Coding theory MOC

Code

A 𝑞-ary code C of length 𝑛 is a inhabited subset C ⊆𝑆𝑛𝑞, where 𝑆𝑞 is a set (called an alphabet) containing 𝑞 letters.¹ #m/def/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 minimum distance 𝑑 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

• 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

#state/tidy | #lang/en | #SemBr