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

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

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

二元体 $F_{2} = {0, 1}$ 上で、生成多項式
$g (x) = x^{3} + x^{2} + 1$
で定まる符号長 $7$ 、次元 $4$ の巡回符号 $C$ を考える（ $g (x)$ は $x^{7} - 1$ を割り切る）。

語 $c = (c_{0}, c_{1}, \dots, c_{6}) \in F_{2}^{7}$ は多項式 $c (x) = c_{0} + c_{1} x + \dots + c_{6} x^{6}$ と同一視する。情報 $m = (m_{0}, m_{1}, m_{2}, m_{3})$ は $m (x) = m_{0} + m_{1} x + m_{2} x^{2} + m_{3} x^{3}$ と同一視し、次のように組織符号化する。

$x^{3} m (x)$ を $g (x)$ で割った余りを $r (x) = r_{0} + r_{1} x + r_{2} x^{2}$ とする。
符号語を $c (x) = x^{3} m (x) + r (x)$ とする。すなわち $c = (r_{0}, r_{1}, r_{2}, m_{0}, m_{1}, m_{2}, m_{3})$ である。

情報 $m = (1, 1, 0, 1)$ を符号化して得られる符号語 $c = (c_{0}, c_{1}, c_{2}, c_{3}, c_{4}, c_{5}, c_{6})$ を求めよ。

この問題で使うもの

巡回符号と生成多項式（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

巡回符号の組織符号化を使います。 $x^{n - k} m (x) = x^{3} m (x)$ を生成多項式 $g (x)$ で割った余りを求めましょう。

ヒント 2

$m (x) = 1 + x + x^{3}$ なので $x^{3} m (x) = x^{6} + x^{4} + x^{3}$ です。 $F_{2}$ 上の割り算では、 $g (x)$ の何倍かを「加える」ことで最高次の項を消していきます（ $1 + 1 = 0$ ）。

ヒント 3

まず $x^{3} g (x) = x^{6} + x^{5} + x^{3}$ を加えると $x^{5} + x^{4}$ が残ります。次に $x^{2} g (x)$ を加えて、次数が $3$ 未満になるまで続けましょう。

答えと解説

答えを見る

(0, 0, 1, 1, 1, 0, 1)

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

解説を読む

手順 1：情報多項式をつくる。
$m = (1, 1, 0, 1)$ より
$m (x) = 1 + x + x^{3}$
である。したがって
$x^{3} m (x) = x^{3} + x^{4} + x^{6} .$

手順 2： $x^{3} m (x)$ を $g (x) = x^{3} + x^{2} + 1$ で割る。 $F_{2}$ 上では引き算は足し算と同じ（ $1 + 1 = 0$ ）であることに注意する。

- 最高次の項 $x^{6}$ を消すために、 $x^{3} g (x) = x^{6} + x^{5} + x^{3}$ を加える：
$(x^{6} + x^{4} + x^{3}) + (x^{6} + x^{5} + x^{3}) = x^{5} + x^{4} .$
- 次に $x^{5}$ を消すために、 $x^{2} g (x) = x^{5} + x^{4} + x^{2}$ を加える：
$(x^{5} + x^{4}) + (x^{5} + x^{4} + x^{2}) = x^{2} .$

$x^{2}$ の次数 $2$ は $g (x)$ の次数 $3$ より小さいので、ここで止める。商は $x^{3} + x^{2}$ 、余りは
$r (x) = x^{2}$
である。

（検算： $g (x) (x^{3} + x^{2}) = x^{6} + x^{5} + x^{3} + x^{5} + x^{4} + x^{2} = x^{6} + x^{4} + x^{3} + x^{2}$ 。これに $r (x) = x^{2}$ を加えると $x^{6} + x^{4} + x^{3} = x^{3} m (x)$ となり、正しい。）

手順 3：符号語をつくる。
$c (x) = x^{3} m (x) + r (x) = x^{2} + x^{3} + x^{4} + x^{6} .$
よって $(r_{0}, r_{1}, r_{2}) = (0, 0, 1)$ であり、
$c = (0, 0, 1, 1, 1, 0, 1)$
となる。

確認： $c (x) = x^{2} (x^{4} + x^{2} + x + 1)$ であり、 $x^{4} + x^{2} + x + 1 = (x + 1) (x^{3} + x^{2} + 1)$ と因数分解できる。したがって $c (x) = x^{2} (x + 1) g (x)$ となり、 $c (x)$ は $g (x)$ で割り切れる。よって $c$ は確かに $C$ の符号語である。

答え： $(0, 0, 1, 1, 1, 0, 1)$

別解

$m (x) = 1 + x + x^{3}$ なので $x^{3} m (x) = x^{3} + x^{4} + x^{6}$ 。これを $g (x) = x^{3} + x^{2} + 1$ で $F_{2}$ 上割る。

1. $x^{6}$ を消すため $x^{3} g (x) = x^{6} + x^{5} + x^{3}$ を加える（ $F_{2}$ では加法と減法は同じ）。 $(x^{6} + x^{4} + x^{3}) + (x^{6} + x^{5} + x^{3}) = x^{5} + x^{4}$ 。
2. $x^{5}$ を消すため $x^{2} g (x) = x^{5} + x^{4} + x^{2}$ を加える。 $(x^{5} + x^{4}) + (x^{5} + x^{4} + x^{2}) = x^{2}$ 。

$x^{2}$ は次数が 3 未満なので余りは $r (x) = x^{2}$ 、すなわち $(r_{0}, r_{1}, r_{2}) = (0, 0, 1)$ 。商は $x^{3} + x^{2}$ 。

符号語は $c (x) = x^{2} + x^{3} + x^{4} + x^{6}$ 、すなわち $c = (0, 0, 1, 1, 1, 0, 1)$ 。

検算: $(x^{3} + x^{2}) g (x) = x^{6} + x^{5} + x^{3} + x^{5} + x^{4} + x^{2} = x^{6} + x^{4} + x^{3} + x^{2}$ となり、 $c (x)$ と一致する。よって $c (x)$ は $g (x)$ で割り切れる。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題