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

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

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

二元体 $F_{2} = {0, 1}$ 上で、次の $4 \times 10$ 行列 $H$ を考える。
$H = 1000010000100001110010101001011001010011$
$H$ の列は、 $F_{2}^{4}$ のベクトルのうちハミング重み（ $1$ である成分の個数）が $1$ または $2$ であるもの全部（ $10$ 個）を $1$ 回ずつ並べたものである。 $H$ を検査行列とする符号長 $10$ の二元線形符号
$C = {x \in F_{2}^{10} : H x^{T} = 0}$
について、 $C$ の最小距離を $d$ とし、 $C$ に含まれるハミング重み $k$ の符号語の個数を $A_{k}$ とする。 $d, A_{d}, A_{d + 1}$ をこの順に組で求めよ。

この問題で使うもの

検査行列と最小距離（説明と入口の問題）
線形符号と生成行列（説明と入口の問題）
組合せ（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

最小距離は「検査行列の列のうち和が $0$ になる列の最小本数」で決まる。重みの分布は、 $16$ 個しか符号語のない双対符号 $C^{⊥}$ （ $H$ の行空間）を調べてから MacWilliams の恒等式で移すと楽になる。

ヒント 2

$u \in F_{2}^{4}$ の重みを $w$ とすると、 $u H$ の重みは $w + w (4 - w) = w (5 - w)$ になる。これから $W_{C^{⊥}} (x, y)$ を求め、 $W_{C} (x, y) = \frac{1}{16} W_{C^{⊥}} (x + y, x - y)$ を計算する。

ヒント 3

$W_{C^{⊥}} (x, y) = x^{10} + 5 x^{6} y^{4} + 10 x^{4} y^{6}$ である。 $5 (x + y)^{6} (x - y)^{4} + 10 (x + y)^{4} (x - y)^{6} = (x^{2} - y^{2})^{4} (15 x^{2} - 10 x y + 15 y^{2})$ と因数分解できる。

答えと解説

答えを見る

(3, 10, 15)

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

解説を読む

最小距離 $d$ 。 線形符号の最小距離は、検査行列の列のうち和が $0$ になる（一次従属な）列の最小個数に等しい。 $H$ の列はすべて $0$ でなく互いに異なるので、 $1$ 列や $2$ 列で和が $0$ にはならず $d \geq 3$ 。一方、たとえば第 $1, 2, 5$ 列について $e_{1} + e_{2} + (e_{1} + e_{2}) = 0$ なので、第 $1, 2, 5$ 成分だけが $1$ の重み $3$ の符号語がある。よって $d = 3$ 。

双対符号の重み分布。 $C^{⊥}$ は $H$ の行空間で、 $u \in F_{2}^{4}$ に対して符号語 $(u \cdot h_{1}, \dots, u \cdot h_{10})$ （ $h_{j}$ は $H$ の第 $j$ 列）からなる。 $H$ の左 $4$ 列が単位行列なので $rank H = 4$ 、 $∣ C^{⊥} ∣ = 16$ 、 $dim C = 6$ である。 $u$ の重みを $w$ とすると、
- 重み $1$ の列 $e_{i}$ では $u \cdot e_{i} = u_{i}$ なので、 $1$ になるのは $w$ 個、
- 重み $2$ の列 $e_{i} + e_{j}$ では $u_{i} + u_{j} = 1$ となるのは $i, j$ の一方だけが $u$ の台に入るときで、 $w (4 - w)$ 個。

よって符号語の重みは $w + w (4 - w) = w (5 - w)$ 。 $w = 0, 1, 2, 3, 4$ のときそれぞれ $0, 4, 6, 6, 4$ で、該当する $u$ の個数は $1, 4, 6, 4, 1$ 。したがって $C^{⊥}$ の重み数え上げ多項式は
$W_{C^{⊥}} (x, y) = x^{10} + 5 x^{6} y^{4} + 10 x^{4} y^{6} .$

MacWilliams の恒等式。
$W_{C} (x, y) = \frac{1}{16} W_{C^{⊥}} (x + y, x - y)$
を使う。 $(x + y)^{4} (x - y)^{4} = (x^{2} - y^{2})^{4}$ に注意すると
$5 (x + y)^{6} (x - y)^{4} + 10 (x + y)^{4} (x - y)^{6} = (x^{2} - y^{2})^{4} (15 x^{2} - 10 x y + 15 y^{2}) .$
$(x^{2} - y^{2})^{4} = x^{8} - 4 x^{6} y^{2} + 6 x^{4} y^{4} - 4 x^{2} y^{6} + y^{8}$ を掛けて、 $x^{10 - k} y^{k}$ の係数を $k = 0, 1, \dots, 10$ の順に並べると
$15, - 10, - 45, 40, 30, - 60, 30, 40, - 45, - 10, 15.$
$(x + y)^{10}$ の係数 $1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1$ を加えると
$16, 0, 0, 160, 240, 192, 240, 160, 0, 0, 16.$
これを $16$ で割って
$A_{0} = 1, A_{3} = 10, A_{4} = 15, A_{5} = 12, A_{6} = 15, A_{7} = 10, A_{10} = 1$
（他は $0$ ）。合計は $64 = 2^{6}$ で $dim C = 6$ と一致する。 $A_{1} = A_{2} = 0, A_{3} \neq = 0$ からも $d = 3$ が確かめられる。

直接の検算。 和が $0$ になる列の $3$ 元集合は ${e_{i}, e_{j}, e_{i} + e_{j}}$ が $6$ 個、 ${e_{i} + e_{j}, e_{j} + e_{k}, e_{i} + e_{k}}$ が $4$ 個で、計 $10$ 個。 $4$ 元集合は、 ${e_{i}, e_{j}, e_{i} + e_{k}, e_{j} + e_{k}}$ （ ${i, j}$ が $6$ 通り、 $k$ が $2$ 通り）で $12$ 個、重み $2$ の列 $4$ 本（完全グラフ $K_{4}$ の $4$ -サイクル）で $3$ 個、計 $15$ 個。重み $1$ の列が奇数本のときは和の重みの偶奇が合わず、重み $1$ の列が $4$ 本のときは和が $1111 \neq = 0$ なので、これ以外の組合せはない。

以上より $(d, A_{d}, A_{d + 1}) = (3, 10, 15)$ 。

別解

H の列は互いに異なる非零ベクトルなので、重み 1, 2 の符号語は存在せず d≥3 である。列 e_1, e_2, e_{12}（e_{ij}=e_i+e_j）は和が 0 なので、重み 3 の符号語があり、d=3 となる。

重み k の符号語の個数は、和が 0 になる列の k 個の部分集合の個数に等しい。列は "単独" e_i（4 個）と "対" e_{ij}（6 個）に分けられる。K4 の頂点を 1〜4 とみなすと、対は辺に対応する。

A_3 を数える。
- 単独 2 個と対 1 個の場合、{e_i, e_j, e_{ij}} が条件を満たし、6 個ある。
- 対 3 個の場合、{e_{ij}, e_{jk}, e_{ik}} が条件を満たし、K4 の三角形に対応して 4 個ある。
- 単独 1 個と対 2 個の場合、2 つの対の和は重み 0, 2, 4 のいずれかで重み 1 にならないので、0 個。
- 単独 3 個の場合、和の重みは 3 なので、0 個。

よって A_3 = 10。

A_4 を数える。
- 単独 4 個の場合、和は (1,1,1,1) で 0 にならない。
- 単独 3 個と対 1 個の場合、単独の和は重み 3、対は重み 2 なので 0 にならない。
- 単独 2 個と対 2 個の場合、辺を共有する 2 辺 e_{ab}, e_{bc} の和は e_a+e_c になるので、単独 e_a, e_c が一意に決まる。辺を共有する 2 辺の組は、共有頂点 4 通り × 他の 2 頂点の選び方 3 通り = 12 個。
- 単独 1 個と対 3 個の場合、辺の和は常に偶数重みなので重み 1 にならず、0 個。
- 対 4 個の場合、各頂点の次数が偶数の 4 辺の集合は 4 サイクルで、3 個。

よって A_4 = 12 + 3 = 15。

答え: (d, A_d, A_{d+1}) = (3, 10, 15)。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題