生成行列

生成行列（英: Generator matrix）とは、符号理論における線型符号の基底であり、全ての符号語を生成する。線型符号 C の生成行列を G とすると、

w=cG

となり、w は線型符号 C の1つの符号語、c はある行ベクトルである。このとき、w と c の間に全単射が存在する。(n, M = q^k, d)_q-符号の生成行列の次元は k * n となる。ここで n は符号語の長さ、k は情報ビット数、d は符号における最小ハミング距離、q はアルファベットにおけるシンボル数（例えば q = 2 なら、バイナリ符号）である。冗長ビット数は r = n − k で表される。

生成行列の標準形式は次の通りである。

[math]G = \begin{bmatrix} I_k | P \end{bmatrix}[/math]

ここで [math]I_k[/math] は [math]k*k[/math] の単位行列であり、P の次元は [math]k*r[/math] である。

生成行列は、その符号のパリティ検査行列の構築に用いることができる（逆も可能）。

符号の等価性

符号 C₁ と C₂ が等価（C₁ ~ C₂ と記述）であるとは、以下の2つの変換を使って、一方の符号からもう一方の符号を生成できることを意味する。

1. 要素の入れ替え
2. 要素の拡大縮小

等価な符号はハミング距離が同じである。

等価な符号の生成行列は以下のような変換で相互変換可能である。

1. 行の入れ替え
2. 行の拡大縮小
3. 行の追加
4. 列の入れ替え
5. 列の拡大縮小

外部リンク

• MathWorld entry