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

标签：

• Binary-Linear-Codes

Author

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

Description

次の Tanner グラフに対応するパリティ検査行列が定める二元線形符号の符号長、情報ビット数、最小距離を求めよ。丸は変数ノード $v_1,\ldots,v_{10}$、四角は検査ノード $c_1,\ldots,c_5$ を表す。

辺の接続先は次の通りである。

$$\begin{aligned} c_1&:\ v_3,v_6,v_8,v_9,v_{10},\\ c_2&:\ v_1,v_3,v_5,v_7,v_9,\\ c_3&:\ v_4,v_6,v_7,v_9,v_{10},\\ c_4&:\ v_2,v_3,v_5,v_7,v_9,v_{10},\\ c_5&:\ v_5,v_6,v_9. \end{aligned}$$

题目描述

根据上图及列出的边，求 Tanner 图所定义二元线性码的码长、信息位数和最小距离。圆形是变量结点，方形是校验结点。

Kai

行を $c_1,\ldots,c_5$、列を $v_1,\ldots,v_{10}$ の順に並べると、検査行列は

$$H=\begin{pmatrix} 0&0&1&0&0&1&0&1&1&1\\ 1&0&1&0&1&0&1&0&1&0\\ 0&0&0&1&0&1&1&0&1&1\\ 0&1&1&0&1&0&1&0&1&1\\ 0&0&0&0&1&1&0&0&1&0 \end{pmatrix}.$$

変数ノードは10個なので符号長は $10$。第 $8,1,4,2$ 列は順に $e_1,e_2,e_3,e_4$ であり、第5列は第5成分が1なので、これら5列は一次独立である。従って $\operatorname{rank}_{\mathbb F_2}H=5$、情報ビット数は $10-5=5$。

各列は非零で互いに異なるため、重み1、2の非零符号語はない。また各列の成分和は $1$（$\mathbb F_2$ 上）なので、奇数本の列の和が零になることはなく、重み3もない。一方、第 $1,2,3,8$ 列の和は零なので、対応する重み4の符号語がある。よって

$$\boxed{\text{符号長 }10,\qquad\text{情報ビット数 }5,\qquad\text{最小距離 }4}.$$