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

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

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

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

情報語 $m = (m_{0}, m_{1}, m_{2}, m_{3}) = (1, 0, 0, 1)$ を、情報多項式 $m (x) = m_{0} + m_{1} x + m_{2} x^{2} + m_{3} x^{3} = 1 + x^{3}$ で表す。組織符号化では、 $x^{3} m (x)$ を $g (x)$ で割った余りを $r (x)$ （次数 $2$ 以下）として、符号多項式を $c (x) = r (x) + x^{3} m (x)$ と定める。

このときの余り $r (x)$ を求めよ。ただし、係数の計算はすべて $2$ を法として行う。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

巡回符号の組織符号化の技能を使います。 $n - k = 7 - 4 = 3$ なので、 $x^{3} m (x)$ を $g (x)$ で割った余りを求めればよいです。

ヒント 2

$x^{3} m (x) = x^{6} + x^{3}$ を $x^{3} + x^{2} + 1$ で割ります。 $F_{2}$ では引き算と足し算が同じなので、 $x^{k} g (x)$ を足して最高次の項を消していきます。

ヒント 3

商に $x^{3}$ を立てると残りは $x^{5}$ 、続けて $x^{2}$ を立てると残りは $x^{4} + x^{2}$ になります。あと $2$ 回、同じ操作をしてください。

答えと解説

答えを見る

x + 1

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

解説を読む

方針：組織符号化では、 $x^{n - k} m (x)$ を生成多項式 $g (x)$ で割った余りを求めます。ここでは $n = 7, k = 4$ なので $n - k = 3$ です。

手順 1： $x^{3} m (x)$ を計算する
$x^{3} m (x) = x^{3} (1 + x^{3}) = x^{6} + x^{3} .$

手順 2： $g (x) = x^{3} + x^{2} + 1$ で割る（係数は $2$ を法とするので、引き算は足し算と同じ）

- 最高次 $x^{6}$ を消すため、商に $x^{3}$ を立てる： $x^{3} g (x) = x^{6} + x^{5} + x^{3}$ 。これを足すと
$(x^{6} + x^{3}) + (x^{6} + x^{5} + x^{3}) = x^{5} .$
- 商に $x^{2}$ を立てる： $x^{2} g (x) = x^{5} + x^{4} + x^{2}$ 。足すと $x^{4} + x^{2}$ 。
- 商に $x$ を立てる： $xg (x) = x^{4} + x^{3} + x$ 。足すと $x^{3} + x^{2} + x$ 。
- 商に $1$ を立てる： $g (x) = x^{3} + x^{2} + 1$ 。足すと $x + 1$ 。

残りは次数 $1 < 3$ なので割り算はここで終わりです。商は $q (x) = x^{3} + x^{2} + x + 1$ 、余りは $r (x) = x + 1$ で、
$x^{6} + x^{3} = (x^{3} + x^{2} + x + 1) (x^{3} + x^{2} + 1) + (x + 1) .$

手順 3：確かめ
符号多項式は $c (x) = r (x) + x^{3} m (x) = 1 + x + x^{3} + x^{6}$ です。 $2$ を法とすると $- r (x) = r (x)$ なので $c (x) = x^{3} m (x) - r (x) = q (x) g (x)$ となり、 $c (x)$ は $g (x)$ で割り切れます。実際、 $(x^{3} + x^{2} + x + 1) (x^{3} + x^{2} + 1)$ を展開して $2$ を法として整理すると $x^{6} + x^{3} + x + 1$ になり、 $c (x)$ と一致します。よって $c (x)$ は確かに $C$ の符号語で、係数列は $(1, 1, 0, 1, 0, 0, 1)$ です（後ろ $4$ 個が情報語 $(1, 0, 0, 1)$ そのもの）。

したがって $r (x) = x + 1$ 。

別解

$x^{3} m (x) = x^{3} + x^{6}$ を $g (x) = x^{3} + x^{2} + 1$ で割る（係数は $F_{2}$ ）。

筆算：
- $x^{6} + x^{3} - x^{3} \cdot g = x^{6} + x^{3} - (x^{6} + x^{5} + x^{3}) = x^{5}$
- $x^{5} - x^{2} \cdot g = x^{5} - (x^{5} + x^{4} + x^{2}) = x^{4} + x^{2}$
- $x^{4} + x^{2} - x \cdot g = x^{4} + x^{2} - (x^{4} + x^{3} + x) = x^{3} + x^{2} + x$
- $x^{3} + x^{2} + x - 1 \cdot g = x^{3} + x^{2} + x - (x^{3} + x^{2} + 1) = x + 1$

よって商は $x^{3} + x^{2} + x + 1$ 、余りは $r (x) = x + 1$ 。

検算： $x^{3} \equiv x^{2} + 1$ より $x^{4} \equiv x^{2} + x + 1$ 、 $x^{5} \equiv x + 1$ 、 $x^{6} \equiv x^{2} + x$ 。したがって $x^{6} + x^{3} \equiv (x^{2} + x) + (x^{2} + 1) = x + 1$ となり一致する。

（このとき $c (x) = 1 + x + x^{3} + x^{6}$ 。）

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題