線型符号
q 個の元からなる有限体 F = F q {\displaystyle F=\mathbb {F} _{q}} をとる。このとき n 次元線型空間 F の部分空間 C を線型符号という。また k = dimF C とするとき、線型符号 C のことを (n, k) 線型符号という。k 次元部分空間 C はその基底 g1, ..., gk ∈ F を指定すれば定まる。これらを並べた k×n 行列 G = (g1, ..., gk) を線型符号 C の生成行列という。定義から
C = { x G ∣ x ∈ F k } {\displaystyle C=\{\,xG\mid x\in F^{k}\,\}}
が成り立つ。また k 次元部分空間 C は連立一次方程式で指定しても定まる。そこで
C = { y ∈ F n ∣ y H t = 0 } {\displaystyle C=\{\,y\in F^{n}\mid yH^{t}=0\,\}}
となる(n − k)×n 行列 H を線型符号 C のパリティ検査行列という。定義から GH = 0 が成り立つ。これらの行列は適当に線型符号 C の基底を取りなおすことによって
G = ( I | P ) , H = ( − P t | I ) {\displaystyle G=(I|P),\quad H=(-P^{t}|I)}
の形にできる。このような G, H を組織符号形式という。このとき符号化前の k 個の記号からなる情報系列がそのまま符号語に現れているので、容易に復号ができる。符号語の残り n − k 個の記号はパリティ検査記号と呼ばれる。