６．通信路符号化・線形符号

公開状態にしてますが、編集中です。
間違いや表記ゆれがあります。

ハミング距離

ハミング距離は、二つの系列の違いを数値で表す手段。
これを代数的に捉える。

長さ$${n}$$の二つの系列
$${a=\{a_1,a_2 \cdot \cdot  \cdot ,a_n\}}$$
$${b=\{b_1,b_2 \cdot \cdot  \cdot ,b_n\}}$$
について考える。

$$a,b$$に互いに対応する位置にあるシンボルで異なるものがハミング距離である。

$${d_H(a,b)=\displaystyle \sum_{i=1}^n \delta(a_i,b_i)}$$

クロネッカーのデルタを用いて、その距離を考える。

$${\delta(x,y) = \begin{cases} 0 & (x =y) \\ 1 & (x \ne y) \end{cases}}$$

2元系列系では、
01と$${x,y}$$関係から排他的論理和(XOR)を利用すれば良いので、
$${d_H(a,b)=\displaystyle \sum_{i=1}^n(a_i \oplus b_i)}$$

一方の系列（ここでは、$${a}$$とする）とすべてのシンボルが0である系列0との距離を$${a}$$の重みといい、この距離にハミング距離を用いたものをハミング重みという。

$${w_H(a)=d_H(a,0)=\displaystyle \sum_{i=1}^n \delta(a_i,0)}$$

以上から、二元系列系の両者の関係は、
$${d_H(a,b)=w_H(a \oplus b)}$$

例題

$${a=(0,0,0),b=(1,0,0)}$$の時、
ハミング距離と$${a}$$のハミング重みを求める。

$${d_H(a,b)=0\oplus1+0\oplus0+0\oplus0}$$
$${=1+0+0=1}$$

$${w(a)=0+1+1=2}$$

誤り検出

符号$${C}$$に含まれる異なる二つの符号語$${a_i,a_j}$$のハミング距離$${d_H(a_i,a_j)}$$の最小値

$${d_{\min}=\displaystyle\min_{i \ne j}d_H(a_i,a_j)}$$
これを符号$${C}$$の最小距離という。

図のように半径$${t}$$が、
$${d_{\min} \ge 2t+1}$$
を満足すれば、他の球と共通の系列を持たない。

さらに、

$${t'=d_{\min} - (2t+1)}$$は、他の球と共通の系列を持たない。
$${t+1}$$個以上$${t+t'}$$以下の誤りは、
訂正できないが、検出はできる。

訂正は、検出されることが基となるから、
訂正＞検出の関係性。

以上のことから、
$${t}$$個以下の誤り訂正、
$${t+t'}$$個以下の誤り検出が可能にするには、

$${d_{\min} \ge 2t+t'+1}$$

例題

$${a=(0,0,0),b=(1,1,1)}$$
の時、何個の誤りを訂正できるか？

ハミング距離は３。
$${3 \ge 2t+1}$$
$${t \le 1}$$

したがって、一個以下の誤り訂正が可能。

総括問題

(7,4)ハミング符号を使用して、通信路の送信側で情報ビットを符号化し、受信側で誤り訂正で行い復号する。
４つの情報ビットがすべて正しく得られる確率を求めよ。

(7,4)ハミング符号は、最小距離は３。
それ以下の組み合わせは存在しない。

画像で、後述する生成行列を示しているが、
３つの検査ビットの取り方$${2^3}$$通りの中でも、最小距離は３になる。

誤り訂正は、
$${3 \ge 2t+1}$$
$${t \le 1}$$

誤り検出は、
$${3 \ge (2t+1) +1}$$
$${t \le 2}$$

４つの情報ビットを全て正しく得るには、
１つ誤りの場合でも、訂正できるからOK。
２つ誤りがあると検出はできるが、訂正はできない。

何かしらの誤り源を想定して計算をする。
ここでは、加算的２元通信路を考える。
送信シンボル$${\{0,1\}}$$の定常確率が、
$${q_0=\displaystyle\frac{1}{3}}$$、$${q_1=\displaystyle\frac{2}{3}}$$
とする。

加算的２元通信路では、1が誤りになるから、
$${(q_0)^7+_7C_1(q_0)^7(q_1)\displaystyle\frac{64}{243}}$$

線形符号

伝送する系列情報ビット$${i}$$と
誤り検出・訂正のために付加する検査ビット$${p}$$を考える。

$${k}$$個のシンボルで構成される情報ビットと$${n-k}$$このシンボルで構成される検査ビットを付加した、
長さ$${n}$$の系列符号語とする符号を$${(n,k)}$$符号という。

そして、符号語$${a}$$の情報ビット$${i}$$、検査ビット$${p}$$は、
それぞれ行ベクトルで表される。

$${a=\{ \bold i,\bold p\}}$$
$${=\{i_1,i_2 \cdot \cdot \cdot i_k,p_1,p_2 \cdot \cdot \cdot p_{n-k}\}}$$

また、

$${\begin{pmatrix} p_1 \\ p_2 \\\cdot\\\cdot\\\cdot\\p_{n-k}\end{pmatrix}＝\bold P\begin{pmatrix} i_1 \\ i_2 \\\cdot\\\cdot\\\cdot\\i_{k}\end{pmatrix}}$$

$${p^{ \mathrm{ T }}=Pi^{ \mathrm{ T }}}$$
$${p=iP^{ \mathrm{ T }}}$$

2を法とした計算

要するに、合同式（$${\mod 2}$$）

modは、あまりの数に注目する。
$${2\times3 \equiv1 \mod 5}$$
$${2 \times 3}$$を5で割ると、1になる。
このとき、5を法とした計算という。

情報理論の世界は、$${0,1}$$なので、

乗算の場合は、
$${0\times 0=0,0\times 1=0 ,1\times 0=0,1\times 1=1}$$

加算の場合（重要）は、
$${0＋0=0,0+ 1=1 ,1+ 0=1,\bold {1+ 1=0}}$$

1+1=0は違和感がありますが、
２を法の場合は正しいです。

生成行列

生成行列は、符号語$${a}$$から定義する。

$${a=\{ \bold i,\bold p\}}$$
$${=\{ \bold i,\bold {ip^T}\}}$$
$${=\{ \bold {iI_k},\bold {ip^T}\}}$$（※$${I_k}$$は、$${k}$$次正方行列。）
$${=\bold i\{\bold {I_k},\bold {p^T}\}}$$

このとき、$${a=\{ \bold i,\bold G\}}$$とした、
$${\bold G=\{\bold {I_k},\bold {p^T}\}}$$を生成行列という。

情報ビット$${i}$$から、符号語$${a}$$を生成する行列という意味を成している。

（生成行列の画像）

検査行列

$${Pi^{ \mathrm{ T }}-p^{ \mathrm{ T }}=0^T}$$

2を法とする加算と減算は同じなので、
$${Pi^{ \mathrm{ T }}＋p^{ \mathrm{ T }}=0^T}$$
$${\begin{pmatrix} P , I_{n-k}\end{pmatrix}\begin{pmatrix} i^T \\ p^T\end{pmatrix}=0^T}$$
$${\begin{pmatrix} P , I_{n-k}\end{pmatrix}a^T=0^T}$$

検査行列$${H}$$は、
$${H=\begin{pmatrix} P , I_{n-k}\end{pmatrix}}$$
で示されて、

$${Ha^T=0^T}$$
$${aH^T=0}$$

この式から、受信側で誤り検査をすることができることを示している。

（検査行列の画像）

検査行列から生成行列を求める