阪大 基礎工学研究科 システム創成専攻 電子光科学I 2024年度 院試 過去問 解答例・解説（解説6項目）

(1)　$k$ 個の誤りが生じる確率と誤り個数の平均

行列 $W$ の対角成分 $1-\varepsilon$ が、ビットがそのまま伝わる確率である。各ビットは独立に確率 $\varepsilon$ で反転する。誤りの位置を指定した $k$ 個の集合に対して、その位置だけが反転し、残る $n-k$ 個が反転しない確率は $\varepsilon^k(1-\varepsilon)^{n-k}$ である。位置の選び方は $\dbinom nk$ 通りで、これらは互いに排反だから $$P(k)=\binom nk\varepsilon^k(1-\varepsilon)^{n-k}\qquad(k=0,1,\dots,n).$$ 平均は $k\dbinom nk=n\dbinom{n-1}{k-1}$ を使って $$\sum_{k=0}^{n}kP(k)=n\varepsilon\sum_{k=1}^{n}\binom{n-1}{k-1}\varepsilon^{k-1}(1-\varepsilon)^{n-k}=n\varepsilon\,(\varepsilon+1-\varepsilon)^{n-1}=n\varepsilon.$$

(2)　補元 $\bar{\bm v}$ も符号語になることの証明

$\bm v$ が符号語であることは、$H\bm v^{\mathsf T}=\bm 0\pmod 2$ と同じである。全成分が $1$ のベクトルを $\bm 1=(1,1,\dots,1)$ とおくと、$\bar v_i=1-v_i\equiv v_i+1\pmod2$ なので $\bar{\bm v}=\bm v+\bm 1$ である。

まず $H\bm 1^{\mathsf T}$ を求める。第 $j$ 成分は $H$ の第 $j$ 行にある $1$ の個数を $\bmod2$ で数えたものである。各行の $1$ の個数は、第1行 $4$、第2行 $4$、第3行 $4$、第4行 $8$ で、いずれも偶数だから $H\bm 1^{\mathsf T}=\bm 0\pmod2$ である。

したがって $$H\bar{\bm v}^{\mathsf T}=H\bm v^{\mathsf T}+H\bm 1^{\mathsf T}=\bm 0+\bm 0=\bm 0\pmod2$$ となり、$\bar{\bm v}$ も符号語である。$\blacksquare$

(3)　受信語 $(1,1,1,1,0,1,0,1)$ の復号

シンドローム $\bm s=H\bm r^{\mathsf T}\pmod2$ を求める。 $$\begin{aligned} \text{第1行（位置 }1,2,4,5\text{）}&:\ 1+1+1+0=3\equiv1,\\ \text{第2行（位置 }2,3,4,6\text{）}&:\ 1+1+1+1=4\equiv0,\\ \text{第3行（位置 }1,3,4,7\text{）}&:\ 1+1+1+0=3\equiv1,\\ \text{第4行（全位置）}&:\ 1+1+1+1+0+1+0+1=6\equiv0. \end{aligned}$$ よって $\bm s=(1,0,1,0)^{\mathsf T}\ne\bm 0$ で、誤りが含まれる。

$\bm r=\bm c+\bm e$ なら $H\bm r^{\mathsf T}=H\bm e^{\mathsf T}$ なので、$\bm s$ は誤りの位置に対応する列 $\bm h_i$ の和になる。$H$ のどの列も第4成分は $1$ だから、$\bm s$ の第4成分は誤りの個数の偶奇である。$\bm s$ の第4成分は $0$ なので、誤りの個数は偶数である。1個の誤りなら $\bm s$ が1本の列に等しく第4成分が $1$ になるので、誤りは1個ではない。

2個の誤りを調べる。列の上3成分は $000$ から $111$ の8通りを1回ずつ取るので、$\bm h_i+\bm h_j=\bm s$ となる位置の組は、上3成分の和が $(1,0,1)$ になる組である。 $$\{i,j\}=\{1,8\},\ \{2,3\},\ \{4,6\},\ \{5,7\}$$ の4組がある。受信語との距離が $2$ の符号語は $$(0,1,1,1,0,1,0,0),\ (1,0,0,1,0,1,0,1),\ (1,1,1,0,0,0,0,1),\ (1,1,1,1,1,1,1,1)$$ の4つで、どれも同じ確率 $\varepsilon^2(1-\varepsilon)^6$ をもつ。最も確からしい候補が1つに決まらないので、送信符号語は推定できない。

可能性のある誤りの個数は偶数で、距離が $2,4,6$ の符号語がそれぞれ $4,8,4$ 個ある。$8$ 個の誤りは送信符号語が $\bar{\bm r}=(0,0,0,0,1,0,1,0)$ の場合だが、(2)の結果から $H\bar{\bm r}^{\mathsf T}=\bm s+H\bm 1^{\mathsf T}=\bm s\ne\bm0$ で符号語でないので、起こりえない。

(4)　受信語 $(1,0,1,1,1,1,0,0)$ の復号

$$\begin{aligned} \text{第1行（位置 }1,2,4,5\text{）}&:\ 1+0+1+1=3\equiv1,\\ \text{第2行（位置 }2,3,4,6\text{）}&:\ 0+1+1+1=3\equiv1,\\ \text{第3行（位置 }1,3,4,7\text{）}&:\ 1+1+1+0=3\equiv1,\\ \text{第4行（全位置）}&:\ 1+0+1+1+1+1+0+0=5\equiv1. \end{aligned}$$ $\bm s=(1,1,1,1)^{\mathsf T}$ で、これは $H$ の第4列 $\bm h_4$ に一致する。第4成分が $1$ なので誤りは奇数個で、$\varepsilon\ll\tfrac12$ では最も確からしいのは1個である。1個なら誤りは第4ビットなので、第4ビットを反転して $$\hat{\bm c}=(1,0,1,0,1,1,0,0)$$ とする。確かめでは $H\hat{\bm c}^{\mathsf T}$ の4行が、$1+0+0+1=2$、$0+1+0+1=2$、$1+1+0+0=2$、$4$ で、すべて偶数となり $\bm 0$ である。

(5)　復号後の誤り個数の平均

復号規則は次のとおりである。$\bm s=\bm 0$ なら $\bm r$ を出力する。$\bm s\ne\bm0$ で第4成分が $1$ なら、$\bm s$ に等しい列 $\bm h_j$ の位置 $j$ を反転する。$\bm s\ne\bm0$ で第4成分が $0$ なら、$\bm r$ をそのまま出力する。線形性より、復号後の誤り個数は送信符号語によらないので、$\bm c=\bm 0$ として誤りパターン $\bm e$ の重み $w$ で場合分けする。

$w=0$：誤りなし。$w=1$：$\bm s=\bm h_j$ で位置 $j$ を反転し、誤りは $0$ 個になる。

$w=2$：$\bm s=\bm h_i+\bm h_j$ は $\bm 0$ でなく（列が異なる）、第4成分は $0$ なので、$\bm r$ がそのまま出力される。誤りは2個。パターンは $\dbinom82=28$ 通り。

$w=3$：$\bm s=\bm h_i+\bm h_j+\bm h_k$ の第4成分は $1$ で、8本の列のうちの1つ $\bm h_l$ に等しい。$l\in\{i,j,k\}$ なら残りの2列の和が $\bm 0$ になり、列が異なることに反するので、$l$ は $i,j,k$ と異なる。位置 $l$ を反転するので誤りは $4$ 個になる。パターンは $\dbinom83=56$ 通り。

$w\ge4$ の項は $\varepsilon^4$ 以上である。平均は $$E=28\cdot2\,\varepsilon^2(1-\varepsilon)^6+56\cdot4\,\varepsilon^3(1-\varepsilon)^5+O(\varepsilon^4).$$ $(1-\varepsilon)^6=1-6\varepsilon+\cdots$ を入れると、$\varepsilon^3$ の係数は $56\cdot(-6)+224=-112$ である。よって $$E=56\varepsilon^2-112\varepsilon^3+O(\varepsilon^4).$$