Coding theory MOC

Linear code

A 𝑞-ary linear code of length 𝑛 and dimension 𝑘 is a 𝑘-dimensional vector subspace C ≤𝕂𝑛𝑞, 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 ^minimumDistance 𝑑 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

  ⃗𝐱⋅⃗𝐲=⃗𝐱𝖳⃗𝐲=𝑛∑𝑖=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 𝑥 ∈C ⟺ 𝑥𝐻𝖳 =⃗𝟎.

• The value of syn⁡𝑥 =𝑥𝐻𝖳 is called the syndrome of 𝑥. Syndromes uniquely label cosets 𝐾syn⁡𝑥 ∈𝕂𝑛𝑞/C in the quotient.

• In a given coset 𝐾syn⁡𝑥 ∈𝕂𝑛𝑞/C a minimum weight string 𝑙syn⁡𝑥 ∈𝐾syn⁡𝑥 is called a coset leader, and the correction of a string 𝑥 is 𝑥 −𝑙syn⁡𝑥. Thus a perfect code has unique coset leaders.

• Linear equivalence of codes

Properties

• The ^rate of a [𝑛,𝑘]-code is 𝑛/𝑘.
• The ^minimumDistance of a linear code is its ^minimumWeight.

Special kinds of linear code

• Projective code

See also

• Extended code

---

tidy | en | SemBr

Footnotes

1. 1999. Introduction to coding theory, §3.2, pp. 35–36 ↩