千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2024年8月実施 専門 B9

标签：

• Connectivity
• Kernel-and-Image

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

二元体上で

$$H=\begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\end{pmatrix}, \qquad C=\ker(H:\mathbb F_2^7\to\mathbb F_2^3)$$

とする。$\operatorname{wt}(v)$ は Hamming 重みを表す。

(1) 非零の $a\in C$ は $\operatorname{wt}(a)\ge3$ を満たすことを示せ。(2) 重み $3$ の符号語の個数を答えよ。理由は不要。(3) 頂点集合を $C$、隣接条件を $\operatorname{wt}(x-y)=3$ とするグラフが連結な無向グラフであることを示せ。

题目描述

对给定二元校验矩阵的核 $C$：(1) 证明非零码字的 Hamming 重量至少为三。(2) 给出重量为三的码字个数。(3) 将 Hamming 距离为三的码字相连，证明所得图无向且连通。

Kai

(1)

$H$ の七つの列は、$\mathbb F_2^3$ のすべての非零ベクトルを一度ずつ並べたものである。したがって一列の和も、相異なる二列の和も $0$ にならない。よって重み $1,2$ の符号語は存在しない。

(2)

$\boxed7$ 個。

(3)

標準基底を $e_i$ とする。次の四つの重み $3$ の符号語を考える。

$$c_3=e_1+e_2+e_3,\quad c_5=e_1+e_4+e_5,\quad c_6=e_2+e_4+e_6,\quad c_7=e_3+e_4+e_7.$$

第 $7,6,5,3$ 座標を順に見れば、これらは一次独立である。$H$ の列 $1,2,4$ は基底をなすので $\operatorname{rank}H=3$、$\dim C=4$。従って上の四つは $C$ の基底である。

任意の符号語はこれらの和で表され、一つずつ加える操作はグラフの辺に沿う移動になる。よって任意の頂点は $0$ と道で結ばれ、グラフは連結である。重みは $x-y$ と $y-x$ で等しいため隣接関係は対称、従って無向である。