next up previous contents
Next: よい符号とは何か? Up: 符号理論の数学的基礎付け Previous: 符号理論の数学的基礎付け

ブロック符号の数学的モデル

情報をkビット毎のブロックに区切り, ブロック毎に符号化して送信するブロック符号が数学的にどう記述されるか, そしてどのような性質を持つかを考えてみよう.

Bを0と1の二つの元からなる集合$\{0,1\}$とすると, 0と1からなるkビットの信号全体はBk個の直積Bkと同一視できる.

\begin{displaymath}B^k=\{(x_1,x_2,\dots,x_k)\vert x_i\in B=\{0,1\}, i=1,2,\dots,...
...longleftrightarrow x_1x_2\cdots x_k
\text{ : $k$ビットの信号}\end{displaymath}

例 4.1  

\begin{displaymath}\begin{array}{ccc}
\text{$B^3$の元}&&\text{3ビットの信号} \\ ...
...& & 101 \\
(1,1,0) & & 110 \\
(1,1,1) & & 111 \\
\end{array}\end{displaymath}

数字を一個ずつばらして括弧に入れただけと思うかも知れないが, その通りである. ただ, こうすることで, 次のような「数学」的表記が可能になるのである.

kビットの信号にlビットの余分な情報を付加して送るブロック符号を考えることにすると, この符号化は次のようにモデル化される.

\begin{displaymath}B^k \overset{\varphi}{\to} B^n \text{ : 単射 (ただし, $n=k+l>k$)}\end{displaymath}

${\mathbf x}\in B^k$に対し, $\varphi({\mathbf x})\in B^n$ xの符号化されたものというわけである(単射という条件が必要なのは, 違うデータが符号化して同じものになっては, 復号ができなくなるからである). このようにモデル化されるブロック符号について, k情報長(information length), n符号長(code length), n-k冗長性(redundancy), k/n符号化率(infomation rate, または code rate)といい, 符号長n, 情報長kの符号を(n,k)-符号という. また, 単射$\varphi$によるBkの像 $\operatorname{Im}\varphi$符号(code)といい, $\operatorname{Im}\varphi$の元を符号語という. 以下, $\operatorname{Im}\varphi$Cと書くことにする.

用語のまとめ
符号長 = 符号のビット数
情報長 = 情報ビットの長さ
冗長性 = 符号長-情報長
符号化率 = 情報長/符号長

問題 4.2   例[*], 例[*]の符号について, 符号長, 情報長, 冗長性, 符号化率を求めてみよう.

以上の記号の下で, ブロック符号の誤り訂正について考えてみよう.そのために, まずハミング距離という概念を導入する.

定義 4.3   ${\mathbf x},{\mathbf y}\in B^n$に対し, $\sharp\{i \vert x_i\not= y_i\}$(すなわち異なる成分の個数) を x yハミング距離といい, d(x,y)で表す. これは距離の公理を満たす [*].

例 4.4   例えば, n=4の場合, d((0,0,0,0), (0,0,0,1))=1, d((0,1,0,1), (1,1,0,0))=2などととなる.

さて, 符号語 ${\mathbf x}\in C$を送信して, 受け手が受信した受信語が x'だったとするとき,

\begin{displaymath}\underline{
\text{符号語${\mathbf x}\in C$について送信中にエラーが起きる}
\Longleftrightarrow
{\mathbf x}\not= {\mathbf x}'}
\end{displaymath}

であるから, このハミング距離を使うと,

\begin{displaymath}\underline{
\text{符号語${\mathbf x}\in C$について送信中にエ...
...起きる}
\Longleftrightarrow
d({\mathbf x},{\mathbf x}')\not=0}
\end{displaymath}

と表現されることが分かる.

ある通信を行って, 受信側が ${\mathbf x}'\in B^n$という受信語を受け取ったとする. 受信側は当然送信語が何であったか知るよしもないから, 受信語から送信語を当てる(復元する)ことが必要となる. これにはどうすればよいだろうか?

いま, 各ビットに対して, 誤りが生じる確率がどれも等しく独立にpであるとしよう(2元対称通信路). pは通信路のハード的な特性から定まる非常に小さい数であるが(というか十分小さくなければ信用のおける通信路とならない), ここでは便宜上p=10-a, (a>1)とでもしておこう. すると, xが通信中のエラーで yになる確率 $P({\mathbf x}\to{\mathbf y})$は,

\begin{displaymath}P({\mathbf x}\to{\mathbf y})\sim 10^{-ad({\mathbf x},{\mathbf y})}
\end{displaymath}

となるから, ${\mathbf x}_1,{\mathbf x}_2\in C$に対して,

\begin{displaymath}d({\mathbf x}',{\mathbf x}_1)<d({\mathbf x}',{\mathbf x}_2)
...
...to{\mathbf x}')>\hspace{-2pt}>P({\mathbf x}_2\to{\mathbf x}')
\end{displaymath}

であり, x'にハミング距離で近い位置にあるものほど x'の送信語である確率が高い(僅差ではなく圧倒的に高い)ことが分かる. したがって, 最も原始的な誤り訂正の方法として, x'とのハミング距離が一番小さいCの元を送信語だと「思う」(当然ハズレていることもある)という復号法が考えられるであろう. これを最尤復号(最も尤もらしいものを択るという意味)という.

これですべてが上手くいけばよいのだが, 残念ながら最尤復号には次のような弱点がある.

1.
Cの元を総当たりで調べるので, 何といっても時間がかかる.
2.
一番近いところにあるものが一つだけとは限らない.
こういった弱点を改善した復号が, 今から述べる最小距離復号である. これを説明するために, 次の量が大事になる.

定義 4.5   符号 $C\subset B^n$に対し, $ \min \{ d({\mathbf x},{\mathbf y}) \vert {\mathbf x},{\mathbf y}\in C, {\mathbf x}\not={\mathbf y}\}$C最小距離といい, d(C)または, 単にdと書く. また, 最小距離がdの(n,k)-符号を(n,k,d)-符号という.

受信語 ${\mathbf x}'\in B^n$に対して,

\begin{displaymath}C_{{\mathbf x}'}:=\left\{{\mathbf y}\in C \left\vert d({\mathbf x}',{\mathbf y})< \frac{d}{2}\right.\right\} \end{displaymath}

という集合を考える. すると, dCの最小距離であることから, 任意の ${\mathbf x}'\in B^n$に対して, $C_{{\mathbf x}'}=\phi$かまたは Cx'は唯一つの元からなる. このとき, 受信語 ${\mathbf x}'\in B^n$に対して,

\begin{displaymath}\begin{cases}
\text{$C_{{\mathbf x}'}=\{{\mathbf y}\}\not=\p...
...{$C_{{\mathbf x}'}=\phi$ならば, } & \text{諦める}
\end{cases}\end{displaymath}

によって受信語からの誤り訂正を行う復号法を最小距離復号という(下図参照).


\begin{picture}(40,120)
\put(205,82){\circle{30}}
\put(201,78){・}
\put(196,78){...
...put(130,40){・}
\put(160,60){・}
\put(200,45){・}
\put(240,50){・}
\end{picture}

最小距離復号を用いた誤り訂正においては, 復号を諦める場合を除いて, 唯一つのCの元へと復号される. 復号の候補をハミング距離がd/2未満の 位置にあるものに絞ることで, 復号時間が節約され, また同時に, 復号できる 場合には唯一つに定まることが保証されることになる. 復号できない場合は 諦めるなんていい加減なことでどないすんねん, と憤りを感じられる方も いるだろうが, 復号できない場合は, 再送を要求するなり何なり別の方法を 採ればよいだけのことである. 以後, 本稿では, 最小距離復号のみを考えることにする [*].

注意 4.6   最尤復号, 最小距離復号ともに, 誤り訂正能力に関しては, Bn内のCの点の散らばり方(互いに離れていればいるほどよい)のみに依存し, 全単射 $\varphi : B^k \to C$の定め方には無関係であることに注意しておこう. もちろん, $\varphi$も符号化と復号のプロセスを担う大事な写像ではあるが, 今後, 符号を議論するとき, しばしば$\varphi$のことは忘れてCのみを考えることになる.


next up previous contents
Next: よい符号とは何か? Up: 符号理論の数学的基礎付け Previous: 符号理論の数学的基礎付け
Mitsuru Kawazoe
2001-11-14