この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

情報理論・符号理論の問題

難易度 1教科書の例題レベル大学数学情報理論・符号理論

3 元体 $F_{3} = {0, 1, 2}$ （演算は $3$ を法とする）上の符号長 $4$ の線形符号 $C$ を、生成行列
$G = (10011120)$
によって $C = {u G ∣ u = (u_{1}, u_{2}) \in F_{3}^{2}}$ と定める。符号語のハミング重みを $0$ でない成分の個数とし、 $C$ の最小距離 $d$ を $0$ でない符号語の重みの最小値とする。 $C$ の最小距離 $d$ と、重みがちょうど $d$ である符号語の個数 $A_{d}$ を、組 $(d, A_{d})$ の形でこの順に求めよ。

この問題で使うもの

線形符号と生成行列（説明と入口の問題）

この問題を解けるようになるまで（37 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

「線形符号と生成行列」の技能を使います。 $u = (u_{1}, u_{2})$ を $F_{3}^{2}$ の 9 通りすべて動かして、符号語 $u G$ を書き出しましょう。

ヒント 2

$u G = (u_{1}, u_{2}, u_{1} + u_{2}, 2 u_{1})$ を $3$ を法として計算し、各符号語の $0$ でない成分の個数（重み）を数えます。

ヒント 3

たとえば $(u_{1}, u_{2}) = (1, 2)$ のとき $u G = (1, 2, 0, 2)$ で重み $3$ 、 $(0, 1)$ のとき $(0, 1, 1, 0)$ で重み $2$ です。残りも同様に求め、 $0$ でない符号語の重みの最小値とその個数を数えましょう。

答えと解説

答えを見る

(2, 2)

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

手順 1：符号語の形を書く。
$G$ の 1 行目を $g_{1} = (1, 0, 1, 2)$ 、2 行目を $g_{2} = (0, 1, 1, 0)$ とすると、
$u G = u_{1} g_{1} + u_{2} g_{2} = (u_{1}, u_{2}, u_{1} + u_{2}, 2 u_{1}) (mod 3)$
である。 $g_{1}, g_{2}$ は一次独立（第 1・第 2 成分を見ればよい）なので次元は $k = 2$ であり、符号語は $3^{2} = 9$ 個ある。

手順 2：符号語をすべて書き出し、重みを求める。（成分は $3$ を法として計算する）
- $(u_{1}, u_{2}) = (0, 0)$ ： $(0, 0, 0, 0)$ 、重み $0$
- $(1, 0)$ ： $(1, 0, 1, 2)$ 、重み $3$
- $(2, 0)$ ： $(2, 0, 2, 4) = (2, 0, 2, 1)$ 、重み $3$
- $(0, 1)$ ： $(0, 1, 1, 0)$ 、重み $2$
- $(0, 2)$ ： $(0, 2, 2, 0)$ 、重み $2$
- $(1, 1)$ ： $(1, 1, 2, 2)$ 、重み $4$
- $(1, 2)$ ： $(1, 2, 3, 2) = (1, 2, 0, 2)$ 、重み $3$
- $(2, 1)$ ： $(2, 1, 3, 4) = (2, 1, 0, 1)$ 、重み $3$
- $(2, 2)$ ： $(2, 2, 4, 4) = (2, 2, 1, 1)$ 、重み $4$

手順 3：最小距離と個数を読み取る。
$0$ でない符号語の重みは $2, 3, 4$ のいずれかで、最小値は $2$ なので $d = 2$ 。重み $2$ の符号語は $(0, 1, 1, 0)$ と $(0, 2, 2, 0)$ の $2$ 個なので $A_{2} = 2$ 。

よって $(d, A_{d}) = (2, 2)$ 。

別解

符号語は $u G = (u_{1}, u_{2}, u_{1} + u_{2}, 2 u_{1})$ と書ける。0 でない $(u_{1}, u_{2})$ の 8 通りについて、符号語とハミング重みを調べる。

$(1, 0) \to (1, 0, 1, 2)$ ：重み 3
$(2, 0) \to (2, 0, 2, 1)$ ：重み 3
$(0, 1) \to (0, 1, 1, 0)$ ：重み 2
$(0, 2) \to (0, 2, 2, 0)$ ：重み 2
$(1, 1) \to (1, 1, 2, 2)$ ：重み 4
$(1, 2) \to (1, 2, 0, 2)$ ：重み 3
$(2, 1) \to (2, 1, 0, 1)$ ：重み 3
$(2, 2) \to (2, 2, 1, 1)$ ：重み 4

最小の重みは 2 で、重み 2 の符号語は $(0, 1, 1, 0)$ と $(0, 2, 2, 0)$ の 2 個である。

よって $d = 2, A_{d} = 2$ 。

検算： $G$ は $k = 2$ なので符号語は $3^{2} = 9$ 個（零語を含む）。重みの内訳は 0 が 1 個、2 が 2 個、3 が 4 個、4 が 2 個で、合計 9 個となり一致する。

情報理論・符号理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題