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

手順 1：符号語と最小距離を求める。
$\mathbf{u}\in \{0,1\}$ に対して $\mathbf{u}G$ を計算すると、符号語は
$$00000,11111$$
の 2 つである。$0$ でない符号語は $11111$ だけで、その重みは $5$ である。よって最小距離は $d=5$ である。

手順 2：訂正できる誤りの個数を求める。
$$t=\lfloor \frac{d-1}{2}\rfloor =\lfloor \frac{4}{2}\rfloor =2$$
である。したがって、誤りが $2$ 個以下なら受信語は送った符号語に最も近く、最小距離復号で必ず正しく復号される。

誤りが $3$ 個以上なら、受信語はもう一方の符号語との距離が $2$ 個以下になり、そちらに復号されて失敗する。たとえば $00000$ を送って $3$ ビット誤ると、受信語と $00000$ の距離は $3$、$11111$ との距離は $2$ になる。よって、復号に成功するのは誤りが $0,1,2$ 個のときに限る。

手順 3：反復試行の確率で成功確率を計算する。
$5$ ビットのうち誤りがちょうど $i$ 個になる確率は ${}_5{\mathrm{C}}_i{p}^i(1-p{)}^{5-i}$ である。これを $i=0,1,2$ について足すと
$$P=\sum _{i=0}^2{}_5{\mathrm{C}}_i{\left(\frac{1}{10}\right)}^i{\left(\frac{9}{10}\right)}^{5-i}$$
となる。各項は次のとおりである。
- $i=0$：${\left(\frac{9}{10}\right)}^5=\frac{59049}{100000}$
- $i=1$：$5\cdot \frac{1}{10}\cdot {\left(\frac{9}{10}\right)}^4=\frac{5\cdot 6561}{100000}=\frac{32805}{100000}$
- $i=2$：$10\cdot \frac{1}{100}\cdot {\left(\frac{9}{10}\right)}^3=\frac{10\cdot 729}{100000}=\frac{7290}{100000}$

よって
$$P=\frac{59049+32805+7290}{100000}=\frac{99144}{100000}=\frac{12393}{12500}$$
である。

答え：$\frac{12393}{12500}$

符号 $C=\{00000,11111\}$ は長さ 5 の繰り返し符号で、最小距離は 5 である。受信語と 2 つの符号語とのハミング距離の和は 5 なので、一方が 2 以下なら他方は 3 以上となり、同点（タイ）は起こらない。したがって、誤りビット数が 2 以下のときに正しく復号される。

誤りビット数を $k$ とすると、$k$ は二項分布 $B(5,\frac{1}{10})$ に従う。

$P={\sum }_{k=0}^2\left(\genfrac{}{}{0ex}{}{5}{k}\right){\left(\frac{1}{10}\right)}^k{\left(\frac{9}{10}\right)}^{5-k}$

各項は次のとおり。
- $k=0$: $9^5/10^5=59049/100000$
- $k=1$: $5\cdot 9^4/10^5=5\cdot 6561/100000=32805/100000$
- $k=2$: $10\cdot 9^3/10^5=10\cdot 729/100000=7290/100000$

合計は $(59049+32805+7290)/100000=99144/100000$ である。

約分する。$99144=8\cdot 12393$、$100000=8\cdot 12500$ より $12393/12500$。$12393$ は 2 でも 5 でも割り切れないので、これ以上約分できない。

検算：誤って復号される確率は $k\ge 3$ のときで、次のとおり。
- $k=3$: $10\cdot 81/10^5=810/10^5$
- $k=4$: $5\cdot 9/10^5=45/10^5$
- $k=5$: $1/10^5$

合計は $856/10^5$ となる。$1-856/10^5=99144/10^5$ で一致する。