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

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

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

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

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

技能「線形符号と生成行列」を使います。 $u = (a, b)$ として符号語 $u G$ をすべて書き出し、それぞれのハミング重みを調べましょう。

ヒント 2

$u G = a (1, 0, 2, 1) + b (0, 1, 1, 0) = (a, b, 2 a + b, a)$ です。第 3 成分は $3$ を法として計算します。

ヒント 3

$(a, b) = (0, 1)$ のとき $(0, 1, 1, 0)$ で重み $2$ 、 $(1, 0)$ のとき $(1, 0, 2, 1)$ で重み $3$ です。残りの $(a, b)$ についても同様に計算し、 $0$ でない符号語の重みの最小値と、その重みをもつ符号語の個数を数えましょう。

答えと解説

答えを見る

(2, 2)

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

解説を読む

手順 1：符号語の一般形を求める。
$u = (a, b)$ （ $a, b \in F_{3}$ ）とすると、
$u G = a (1, 0, 2, 1) + b (0, 1, 1, 0) = (a, b, 2 a + b, a)$
である。ただし第 3 成分は $3$ を法として計算する。

手順 2：符号語をすべて書き出す。 $a, b$ はそれぞれ $0, 1, 2$ の $3$ 通りなので、積の法則より $u$ は $3 \times 3 = 9$ 通りある。 $G$ の 2 つの行は一次独立なので $C$ の次元は $k = 2$ で、符号語は $9$ 個すべて異なる。

$(a, b)$	符号語	重み
$(0, 0)$	$(0, 0, 0, 0)$	$0$
$(0, 1)$	$(0, 1, 1, 0)$	$2$
$(0, 2)$	$(0, 2, 2, 0)$	$2$
$(1, 0)$	$(1, 0, 2, 1)$	$3$
$(1, 1)$	$(1, 1, 0, 1)$	$3$
$(1, 2)$	$(1, 2, 1, 1)$	$4$
$(2, 0)$	$(2, 0, 1, 2)$	$3$
$(2, 1)$	$(2, 1, 2, 2)$	$4$
$(2, 2)$	$(2, 2, 0, 2)$	$3$

第 3 成分の計算例： $(a, b) = (1, 1)$ では $2 \cdot 1 + 1 = 3 \equiv 0$ 、 $(a, b) = (1, 2)$ では $2 + 2 = 4 \equiv 1$ 、 $(a, b) = (2, 2)$ では $4 + 2 = 6 \equiv 0 (mod 3)$ である。

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

答え： $(d, A_{d}) = (2, 2)$

別解

符号語は $u = (a, b)$ に対して $(a, b, 2 a + b, a)$ となる（成分は $F_{3}$ で計算）。0 でない $u$ は 8 個あり、すべて列挙する。
- $(0, 1) \to (0, 1, 1, 0)$ ：重み 2
- $(0, 2) \to (0, 2, 2, 0)$ ：重み 2
- $(1, 0) \to (1, 0, 2, 1)$ ：重み 3
- $(1, 1) \to (1, 1, 0, 1)$ ：重み 3
- $(1, 2) \to (1, 2, 1, 1)$ ：重み 4
- $(2, 0) \to (2, 0, 1, 2)$ ：重み 3
- $(2, 1) \to (2, 1, 2, 2)$ ：重み 4
- $(2, 2) \to (2, 2, 0, 2)$ ：重み 3

重みの最小値は 2 なので $d = 2$ 。重みが 2 の符号語は $(0, 1, 1, 0)$ と $(0, 2, 2, 0)$ の 2 個なので $A_{d} = 2$ 。
検算： $a \neq = 0$ のとき第 1 成分と第 4 成分がともに 0 でないので重みは 2 以上。重み 2 になるのは第 2 成分と第 3 成分がともに 0 でないときだけだが、 $a \neq = 0$ では $(a, b, 2 a + b, a)$ の第 1・4 成分に加えて第 2 または第 3 成分のどちらかが 0 でないため重みは 3 以上になる。よって重み 2 は $a = 0$ の場合のみで、上の結果と一致する。
答え： $(d, A_{d}) = (2, 2)$ 。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題