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

難易度 4大学院入試の標準レベル証明問題大学数学情報理論・符号理論

$m \geq 3$ を整数とし、 $n = 2^{m} - 1$ とおく。 $p (x) \in F_{2} [x]$ を次数 $m$ の原始多項式とする。すなわち $p (x)$ は $F_{2}$ 上既約であり、有限体 $F_{2^{m}}$ における $p (x)$ の根 $α$ の乗法的位数はちょうど $n$ である。

$g (x) = (x + 1) p (x)$ とし、
$C = {c (x) \in F_{2} [x] ∣ c (x) = 0 または de g c (x) < n, かつ g (x) ∣ c (x)}$
とおく。 $c (x) = c_{0} + c_{1} x + \dots + c_{n - 1} x^{n - 1}$ を語 $(c_{0}, c_{1}, \dots, c_{n - 1}) \in F_{2}^{n}$ と同一視し、語の重みを $0$ でない成分の個数、 $C$ の最小距離 $d$ を $C$ の $0$ でない語の重みの最小値と定める（ $C$ は線形符号である）。

このとき、 $C$ の最小距離が $d = 4$ であることを証明せよ。

なお、有限体 $F_{2^{m}}$ の基本的な性質（ $α$ を根にもつ $F_{2} [x]$ の多項式はすべて $p (x)$ で割り切れること、 $F_{2^{m}}$ の $0$ でない元はすべて $α^{k}$ $(0 \leq k \leq n - 1)$ の形に書けること、 $1, α, \dots, α^{m - 1}$ が $F_{2}$ 上 1 次独立であること）は用いてよい。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$C$ の語を「 $x = 1$ と $x = α$ を代入すると $0$ になる多項式」と言い換え、重み $1, 2, 3$ の語がないことと、重み $4$ の語があることを別々に示しましょう。

ヒント 2

$c (1)$ は重みの偶奇を表します。重み $2$ の語 $x^{i} + x^{j}$ については $α^{j - i} = 1$ が導かれることに注目し、 $α$ の位数を使います。重み $4$ の語は $1 + α + α^{2}$ を $α$ のべきで表すことで作れます。

ヒント 3

$g (x) ∣ c (x)$ は「 $(x + 1) ∣ c (x)$ かつ $p (x) ∣ c (x)$ 」と同値であり（ $x + 1$ と $p (x)$ は互いに素）、それは $c (1) = 0$ かつ $c (α) = 0$ と同値です。 $c (1) = 0$ から重みは偶数とわかるので、残るのは重み $2$ の場合の否定と、重み $4$ の語の構成です。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$c (x) \in C$ を「 $c (1) = 0$ かつ $c (α) = 0$ 」と同値に言い換え、逆向きでは $x + 1$ と $p (x)$ が互いに素（ $p (1) \neq = 0$ ）であることを根拠にしている（2 点）
$c (1)$ が重みの偶奇に等しいことから、重みが奇数の語（特に重み 1, 3）がないことを示している（2 点）
重み 2 の語 $x^{i} + x^{j}$ を仮定すると $α^{j - i} = 1$ （ $0 < j - i < n$ ）となり、 $α$ の位数が $n$ であることに矛盾することを示している（2 点）
$1 + α + α^{2} = α^{k}$ となる $k$ をとり、1 次独立性から $1 + α + α^{2} \neq = 0$ かつ $k \in / {0, 1, 2}$ を確認している（2 点）
$1 + x + x^{2} + x^{k}$ が $c (1) = 0, c (α) = 0$ を満たし重み 4 の語であることを確かめ、 $d \geq 4$ と合わせて $d = 4$ と結論している（2 点）

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

模範解答を読む

方針. まず $C$ の語を「 $c (1) = 0$ かつ $c (α) = 0$ 」で特徴づける。これを使って重み $1, 2, 3$ の語がないこと（ $d \geq 4$ ）を示し、次に重み $4$ の語を具体的に構成して $d = 4$ を示す。

ステップ 1（ $C$ の特徴づけ）. 次数 $n$ 未満（または $0$ ）の $c (x) \in F_{2} [x]$ について
$c (x) \in C ⟺ c (1) = 0 かつ c (α) = 0$
を示す。

( $\Rightarrow$ ) $c (x) = g (x) h (x) = (x + 1) p (x) h (x)$ と書けるので、 $x = 1$ を代入すると $c (1) = 0$ 、 $x = α$ を代入すると $p (α) = 0$ より $c (α) = 0$ 。

( $\Leftarrow$ ) $c (1) = 0$ なので因数定理より $(x + 1) ∣ c (x)$ 。また $c (α) = 0$ なので、仮定から用いてよい事実により $p (x) ∣ c (x)$ 。ここで $p (x)$ は次数 $m \geq 3$ の既約多項式なので $1$ 次因数 $x + 1$ をもたず、 $p (1) \neq = 0$ である。よって $p (x)$ と $x + 1$ はどちらも既約で互いに異なる（同伴でない）ので互いに素であり、 $F_{2} [x]$ は一意分解整域だから $(x + 1) p (x) = g (x) ∣ c (x)$ 。したがって $c (x) \in C$ 。

ステップ 2（奇数の重みの語はない）. $c (x) \in C$ の重みを $w$ とすると、 $c (1) = c_{0} + c_{1} + \dots + c_{n - 1}$ は $F_{2}$ で $w mod 2$ に等しい。ステップ 1 より $c (1) = 0$ なので $w$ は偶数である。特に重み $1$ と $3$ の語は $C$ に存在しない。

ステップ 3（重み 2 の語はない）. 重み $2$ の語 $c (x) = x^{i} + x^{j}$ （ $0 \leq i < j \leq n - 1$ ）が $C$ に属すると仮定して矛盾を導く。ステップ 1 より $c (α) = 0$ なので
$α^{i} + α^{j} = α^{i} (1 + α^{j - i}) = 0.$
$α \neq = 0$ （位数をもつ乗法群の元）なので $α^{i} \neq = 0$ であり、体では零因子がないから $1 + α^{j - i} = 0$ 、すなわち標数 $2$ より $α^{j - i} = 1$ 。ところが $0 < j - i < n$ であり、 $α$ の位数は $n$ だから $α^{j - i} \neq = 1$ 。これは矛盾である。よって重み $2$ の語は存在しない。

ステップ 2, 3 より、 $C$ の $0$ でない語の重みは $4$ 以上であり、 $d \geq 4$ 。

ステップ 4（重み 4 の語の構成）. $β = 1 + α + α^{2} \in F_{2^{m}}$ とおく。 $m \geq 3$ より $1, α, α^{2}$ は $F_{2}$ 上 1 次独立なので $β \neq = 0$ 。よって $β = α^{k}$ となる整数 $k$ （ $0 \leq k \leq n - 1$ ）がある。

この $k$ は $0, 1, 2$ のどれとも異なる。実際、
- $k = 0$ なら $1 + α + α^{2} = 1$ 、すなわち $α + α^{2} = 0$ となり、
- $k = 1$ なら $1 + α^{2} = 0$ 、
- $k = 2$ なら $1 + α = 0$

となるが、いずれも $1, α, α^{2}$ の自明でない 1 次結合が $0$ になることを意味し、1 次独立性に反する。

そこで $c (x) = 1 + x + x^{2} + x^{k}$ とおく。指数 $0, 1, 2, k$ は相異なり、すべて $n - 1$ 以下なので、 $c (x)$ は次数 $n$ 未満で重みはちょうど $4$ である。さらに
$c (1) = 1 + 1 + 1 + 1 = 0, c (α) = 1 + α + α^{2} + α^{k} = β + β = 0$
（標数 $2$ ）なので、ステップ 1 より $c (x) \in C$ 。したがって $C$ には重み $4$ の語が存在し、 $d \leq 4$ 。

結論. ステップ 2, 3 より $d \geq 4$ 、ステップ 4 より $d \leq 4$ なので、 $C$ の最小距離は $d = 4$ である。（したがって $C$ は 1 個の誤りを訂正し、同時に 2 個の誤りを検出できる。） $■$

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる