線形符号と生成行列

$F_{2}$ や $F_{3}$ （ $p$ を法とする演算）上で、生成行列 $G$ から符号語 $u G$ をすべて書き出し、次元 $k$ 、ハミング重み、最小距離 $d$ （ $= 0$ でない符号語の重みの最小値）と重み $d$ の符号語の個数 $A_{d}$ を求められる

前提

ベクトル空間・一次独立・基底・次元（大学数学線形代数）
合同式（数学A 整数の性質）

この技能までの道筋（36 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
ベクトル空間・一次独立・基底・次元（大学数学線形代数）
因数分解（中学数学数と式）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）

説明

有限体 $F_{p}$ （ $p = 2, 3$ など）の成分をもつ生成行列 $G$ から、線形符号の符号語をすべて書き出します。そのうえで、符号の次元 $k$ 、各符号語のハミング重み、最小距離 $d$ 、重み $d$ の符号語の個数 $A_{d}$ を求めます。最小距離は、符号が何個までの誤りを検出・訂正できるかを決める量です。誤り訂正符号の性能評価や、重み分布を調べる場面で最初に行う作業になります。

なぜそうしてよいのか

$F_{p}$ （ $p$ は素数）は、集合 ${0, 1, \dots, p - 1}$ に $p$ を法とする和と積を入れたものです。たとえば $F_{2}$ では $1 + 1 = 0$ 、 $F_{3}$ では $2 + 2 = 1$ 、 $2 \cdot 2 = 1$ です。 $p$ が素数なので、 $0$ でない元には逆元があります。そのため実数のときと同じように、ベクトル空間・一次独立・掃き出し法・階数がそのまま使えます。長さ $n$ の線形符号とは、 $F_{p}^{n}$ の部分空間 $C$ のことです。 $C$ の基底を行として並べた $k \times n$ 行列 $G$ を生成行列といい、符号語は $u G$ （ $u \in F_{p}^{k}$ ）と表せます。 $u G = u_{1} g_{1} + \dots + u_{k} g_{k}$ （ $g_{i}$ は $G$ の第 $i$ 行）なので、 $C$ は $G$ の行ベクトルの一次結合全体、つまり行空間です。

$G$ の行が一次独立（階数 $k$ ）なら、異なる $u$ から異なる符号語ができます。 $u G = u^{'} G$ ならば $(u - u^{'}) G = 0$ となり、行の一次独立性から $u = u^{'}$ が従うからです。よって $C$ の次元は $k$ で、符号語はちょうど $p^{k}$ 個あります。この個数は、 $u_{1}, \dots, u_{k}$ をそれぞれ $p$ 通りに選ぶ積の法則からも分かります。

ベクトル $x$ のハミング重み $w (x)$ は、 $0$ でない成分の個数です。2 つのベクトルのハミング距離 $d (x, y)$ は、成分が異なる位置の個数で、 $d (x, y) = w (x - y)$ が成り立ちます。 $C$ は部分空間なので、 $x, y \in C$ ならば $x - y \in C$ です。逆に、 $0$ でない符号語 $c$ の重みは $d (c, 0)$ そのものです。したがって、異なる 2 符号語の距離の最小値（最小距離 $d$ ）は、 $0$ でない符号語の重みの最小値に等しくなります。この性質のおかげで、組を全部調べる必要はなく、 $p^{k} - 1$ 個の重みを見るだけで済みます。

手順

$G$ の階数を $p$ を法とする掃き出し法で確かめ、行が一次独立であることを確認する。このとき次元は $k$ （ $G$ の行数）、符号語の個数は $p^{k}$ になる。行が従属なら、次元は階数 $r$ で、独立な $r$ 行を選び直す。
$u = (u_{1}, \dots, u_{k}) \in F_{p}^{k}$ をすべて列挙し、各成分を $p$ で割った余りに直しながら $u G = u_{1} g_{1} + \dots + u_{k} g_{k}$ を計算する。
各符号語のハミング重み $w (c)$ （ $0$ でない成分の個数）を数える。 $F_{3}$ では $w (2 c) = w (c)$ なので、 $c$ と $2 c$ の組で数えれば手間が半分になる。
$0$ を除いた重みの最小値を最小距離 $d$ とし、重みがちょうど $d$ の符号語の個数 $A_{d}$ を数える。

例題

$F_{2}$ 上の生成行列 $G = 100010001110101011$ で定まる線形符号 $C$ について、次元 $k$ 、最小距離 $d$ 、重み $d$ の符号語の個数 $A_{d}$ を、組 $(k, d, A_{d})$ として求めよ。

例題の解答

手順 1： $G$ の左の $3 \times 3$ 部分は単位行列なので、階数は 3 で行は一次独立である。よって $k = 3$ で、符号語は $2^{3} = 8$ 個ある。

手順 2：各行を $g_{1} = 100110$ 、 $g_{2} = 010101$ 、 $g_{3} = 001011$ と書く。成分ごとに $mod 2$ で足すと（ $1 + 1 = 0$ ）、8 個の符号語は次のとおり。
- $u = 000$ ： $000000$
- $u = 100$ ： $100110$
- $u = 010$ ： $010101$
- $u = 001$ ： $001011$
- $u = 110$ ： $g_{1} + g_{2} = 110011$
- $u = 101$ ： $g_{1} + g_{3} = 101101$
- $u = 011$ ： $g_{2} + g_{3} = 011110$
- $u = 111$ ： $110011 + 001011 = 111000$

手順 3：重みは順に $0, 3, 3, 3, 4, 4, 4, 3$ である。

手順 4： $0$ を除いた重みの最小値は 3 なので $d = 3$ 。重み 3 の符号語は $100110, 010101, 001011, 111000$ の 4 個なので $A_{3} = 4$ 。

よって $(k, d, A_{d}) = (3, 3, 4)$ 。

答え: $(3, 3, 4)$

よくある誤り

法 $p$ で余りをとり忘れる誤り。 $F_{2}$ で $(1, 1, 0) + (0, 1, 1) = (1, 2, 1)$ としてしまう。正しくは $1 + 1 = 0$ なので $(1, 0, 1)$ で、重みは 2。
零ベクトルを含めて最小値をとり、 $d = 0$ としてしまう誤り。正しくは、最小距離は $0$ でない符号語の重みの最小値（異なる 2 符号語の距離の最小値）で、例題では $d = 3$ 。
$G$ の行だけを調べて $d$ や $A_{d}$ を決めてしまう誤り。例題で行の重み 3 だけを数えると $A_{3} = 3$ になる。正しくは一次結合 $g_{1} + g_{2} + g_{3} = 111000$ も重み 3 なので $A_{3} = 4$ 。行の重みより小さい重みの一次結合が現れることもあるので、 $p^{k}$ 個すべてを調べる。
$F_{3}$ で、重みを成分の値の和として数えてしまう誤り。 $w (2, 0, 1) = 3$ とするのは誤りで、重みは $0$ でない成分の個数なので $w (2, 0, 1) = 2$ 。また $- 1 \equiv 2$ なので、 $- (1, 2, 0) = (2, 1, 0)$ のように余りで書き直してから数える。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

検査行列と最小距離（大学数学情報理論・符号理論）
誤り訂正能力と復号の成功確率（大学数学情報理論・符号理論）
巡回符号と生成多項式（大学数学情報理論・符号理論）