大阪大学 基礎工学研究科 電子光科学 (システム創成専攻) 2024年度 電子光科学 [I-3]

标签：

• Osaka-University
• Binary-Linear-Codes
• Minimum-Distance-Error-Correction

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

通信路と線形符号について、以下の問に答えよ。

(1) 通信路行列が次式で表される通信路を用いて、長さ $n$ の符号語を送信したとき、受信語に $k$ 個の誤りが生じる確率と受信語に生じる誤りの個数の平均を求めよ。ただし、$k=0,1,2,\ldots,n$ とする。

$$W=\begin{pmatrix}1-\varepsilon&\varepsilon\\\varepsilon&1-\varepsilon\end{pmatrix},\qquad0<\varepsilon\ll\frac12.$$

(2) パリティ検査行列が次式で表される線形符号で、$v=(v_1,v_2,\ldots,v_8)$ が符号語であれば、$\bar v=(\bar v_1,\bar v_2,\ldots,\bar v_8)$ も符号語となることを示せ。ただし、$\bar v_i=1-v_i$、$v_i\in\{0,1\}$ $(i=1,2,\ldots,8)$ とする。

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

以下の問では、問 (1) の通信路で問 (2) の線形符号を用いて通信を行った場合を考える。

(3) 受信語が $(1,1,1,1,0,1,0,1)$ のとき、送信された符号語を推定せよ。符号語が推定できない場合は、その理由を簡潔に述べ、受信語に含まれる可能性のある誤りの個数を全て挙げよ。

(4) 受信語が $(1,0,1,1,1,1,0,0)$ のとき、送信された符号語を推定せよ。符号語が推定できない場合は、その理由を簡潔に述べ、受信語に含まれる可能性のある誤りの個数を全て挙げよ。

(5) 一般の受信語について、復号結果に含まれる誤りの個数の平均を、$\varepsilon$ の次数が低い方から 2 項まで求めよ。ただし、符号語が推定できない場合は、受信語をそのまま復号結果とせよ。

Kai

以下、符号の演算は $\mathbb F_2$ 上で行い、最小距離復号を用いる。

(1)

誤り数 $K$ は二項分布に従うので

$$\boxed{P(K=k)=\binom nk\varepsilon^k(1-\varepsilon)^{n-k},\qquad E[K]=n\varepsilon}.$$

(2)

$\boldsymbol1=(1,\ldots,1)$ とおく。$H$ の各行の1の個数が偶数なので $H\boldsymbol1^T=0$。 したがって $Hv^T=0$ なら

$$H\bar v^T=H(v+\boldsymbol1)^T=Hv^T+H\boldsymbol1^T=0.$$

よって $\bar v$ も符号語である。

(3)

$r=(1,1,1,1,0,1,0,1)$ のシンドロームは $Hr^T=(1,0,1,0)^T$。 距離2にある符号語は

$$\begin{gathered} (0,1,1,1,0,1,0,0),\quad(1,0,0,1,0,1,0,1),\\ (1,1,1,0,0,0,0,1),\quad(1,1,1,1,1,1,1,1) \end{gathered}$$

の4つで、尤度が同じ。したがって一意には推定できない。符号語の重みは偶数、シンドロームは非零なので、誤り数は $0,8$ を除く偶数であり、

$$\boxed{2,4,6\text{ 個}}$$

がすべて可能である。

(4)

$Hr^T=(1,1,1,1)^T$ は $H$ の第4列。よって第4ビットの1ビット誤りと推定し、

$$\boxed{\hat v=(1,0,1,0,1,1,0,0)}.$$

(5)

この符号の非零符号語の重みは4または8なので、最小距離は4。0、1ビット誤りは完全に訂正できる。 2ビット誤りでは最小距離の候補が複数あるため受信語を保持し、誤りが2個残る。 3ビット誤りではそのシンドロームは $H$ の一意の列に一致する。反転されるビットは元の誤りの3か所に含まれないので、誤りが4個となる。

したがって残留誤り数 $R$ の平均は

$$\begin{aligned} E[R]&=2\binom82\varepsilon^2(1-\varepsilon)^6 +4\binom83\varepsilon^3(1-\varepsilon)^5+O(\varepsilon^4)\\ &=\boxed{56\varepsilon^2-112\varepsilon^3+O(\varepsilon^4)}. \end{aligned}$$