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

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

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

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

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

線形符号と生成行列の技能を使います。 $u = (a, b)$ を $F_{3}^{2}$ 全体で動かして、符号語 $u G$ をすべて書き出しましょう。

ヒント 2

$u G = a (1, 0, 2, 1) + b (0, 1, 1, 0) = (a, b, 2 a + b, a)$ で、各成分は $3$ で割った余りにします。符号語は $3^{2} = 9$ 個です。

ヒント 3

$(0, 1)$ に対する符号語は $(0, 1, 1, 0)$ で重み $2$ 、 $(1, 0)$ に対する符号語は $(1, 0, 2, 1)$ で重み $3$ です。残りの符号語の重みも求め、 $0$ でないものの中で最小の重みとその個数を調べましょう。

答えと解説

答えを見る

(2, 2)

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

解説を読む

手順 1：符号語の一般形を求める。
$u = (a, b)$ とすると
$u G = a (1, 0, 2, 1) + b (0, 1, 1, 0) = (a, b, 2 a + b, a)$
である（各成分は $3$ を法として計算する）。 $G$ の 2 つの行は一次独立なので次元は $k = 2$ で、符号語は $3^{2} = 9$ 個ある。

手順 2：符号語をすべて書き出し、重みを数える。
$(a, b) (0, 0) (1, 0) (2, 0) (0, 1) (0, 2) (1, 1) (1, 2) (2, 1) (2, 2) u G (0, 0, 0, 0) (1, 0, 2, 1) (2, 0, 1, 2) (0, 1, 1, 0) (0, 2, 2, 0) (1, 1, 0, 1) (1, 2, 1, 1) (2, 1, 2, 2) (2, 2, 0, 2) 重み 033223443$
計算の例： $(a, b) = (2, 0)$ のとき第 3 成分は $2 \cdot 2 + 0 = 4 \equiv 1$ 、 $(1, 1)$ のとき $2 + 1 = 3 \equiv 0$ 、 $(1, 2)$ のとき $2 + 2 = 4 \equiv 1$ 、 $(2, 1)$ のとき $4 + 1 = 5 \equiv 2$ 、 $(2, 2)$ のとき $4 + 2 = 6 \equiv 0$ である。

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

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

別解

符号語は $(a, b, 2 a + b, a)$ (mod 3)。 $(a, b)$ の 9 通りすべてについて重みを求める。

$(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)$ : $2 a + b = 3 \equiv 0$ より $(1, 1, 0, 1)$ で重み 3
$(1, 2)$ : $2 + 2 = 4 \equiv 1$ より $(1, 2, 1, 1)$ で重み 4
$(2, 0)$ : $4 \equiv 1$ より $(2, 0, 1, 2)$ で重み 3
$(2, 1)$ : $5 \equiv 2$ より $(2, 1, 2, 2)$ で重み 4
$(2, 2)$ : $6 \equiv 0$ より $(2, 2, 0, 2)$ で重み 3

0 でない符号語の重みの最小値は 2 なので $d = 2$ 。重みが 2 の符号語は $(0, 1)$ と $(0, 2)$ の 2 個なので $A_{d} = 2$ 。

検算として、重み 1 の符号語がないことを確認する。 $a \neq = 0$ なら第 1 成分と第 4 成分がともに 0 でないので重みは 2 以上。 $a = 0$ なら $b \neq = 0$ で第 2 成分と第 3 成分が $b$ となり重みは 2。よって最小重みは 2 で、重み 2 の符号語は $a = 0$ の 2 個である。

答えは $(2, 2)$ 。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題