2009年06月14日

情報理論 誤り訂正符号とは?!

今日は、インターネットや携帯電話に代表されるデジタル通信の要である「誤り訂正符号」(通信路符号化)について説明しよう。

さて、デジタル通信においては、テキストや音声や画像も全て「0」「1」に置き換えられたデータを通信している。例えば、テキストデータの場合、
「a」→「01100001」
「A」→「01000001」
というように、半角アルファベット文字は8個の「0」「1」によって、一意に符号(01データ)が割り当てられている。(この割り当て規則をASCIIコードといって、↓の通りになっている)

【ASCII文字コード】
http://e-words.jp/p/r-ascii.html



さて、今「a」の文字をインターネットで乙が甲に送信したとしよう。この時、実際の通信では「01100001」の符号が甲のPCへと伝送される。ところが、通信の途中でノイズが混じってしまい、甲に届いた符号が「01000001」だったとする。すると、↓の画像をのように、甲のPCでは「a」ではなくて「A」を受信したことになるわけだ。
noise_exsample.jpg
このように通信ノイズがあった時、送信した符号が相手に正しく伝わらないので、非常に困るわけだ。しかも、この手のノイズは(特に無線通信においては)結構あるわけで、ノイズを無視するわけにはいかない。となると、受信側はノイズのあることを前提として、受信符号から正しい符号に戻せるような仕組みが欲しい。
「そんな事できるのか?」と思う人がいるだろう。ところが、多少余計な「0」「1」を付加することにより、ノイズによって反転した「0」「1」を受信側で元に戻せるんですよ。


実際の例を示そう。ASCIIコードは、「0」「1」の数が8個と多いので、今は簡単のために
「a」→「0」
「A」→「1」
としよう。(以下、この規則は受信側もわかっているとする。)この時、「0」を送信して「1」を受信したとする。この時、受信側では正しい符号が「0」なのか「1」だったのかを判断できない。

ここで、送信側の方でもう1つ同じ「0」「1」を重ねるとして、
「a」→「00」
「A」→「11」
とする。ここで、「00」を送信して受信側で「01」だったとする。仮に、たかだか1個の「0」「1」しか反転しないとしても、この時受信側では「00」が「01」になったのか、「11」が「01」になったのか、まだわからない。ただし、ノイズによって反転した「0」「1」のある事だけは検出(誤り検出)できるが、正しい符号に戻すこと(誤り訂正)はできない。


さて、もう少し考えてみよう。
「a」→「000」
「A」→「111」
としよう。ここで「000」を送信して受信側で「010」だったとする。この時、仮に3つの「0」「1」のうち、一箇所しか反転しないとすれば、「010」は「000」だったと推測できる。この時は、誤り検出も誤り訂正もできるわけだ。この場合の概念図を以下に示す。
3bits_relation.jpg
↑の立方体は、「000」「001」「010」「011」「100」「101」「110」「111」の概念図を表している。この図では、立方体のそれぞれの頂点が各符号を表していて、辺でつながれたそれぞれ隣の頂点は一個の「0」「1」が反転している事をあらわしている。
ここで、「000」の隣接頂点「001」「010」「100」は、「000」から一個しか「0」「1」が反転していない。よって、たかだか1個の「0」「1」しか反転しないのであれば、この符号を受信した時に正しい符号が「000」であったことがわかる。
同じように、「111」の隣接頂点「011」「101」「110」を受信したのなら、正しい符号は「111」であった事がわかるだろう。
ただし、もし2つの「0」「1」が反転しているのであれば、受信符号の誤り検出はできるが、正しい符号への誤り訂正はできない。



この事を少し一般的に考えてみると、「誤り訂正」という概念は、以下のような集合図であらわせるわけだ。このように「000」と「111」で、1個の「0」「1」が反転した2つの集合に、共通部分がなければ誤り訂正が可能という事になる。
correction_code.jpg
問題は、今みたいに送るべき情報が「a」「A」の2つではなくて、数百万とか数千万みたいに非常に大きな数になった場合に、誤り訂正のために付加する符号をどう作るか?という事なんだよね。
実は、これは「巡回符号」「CRC符号」というようなアルゴリズムがすでに開発されているけど、話が非常に高度になるので興味のある方はそれぞれ調べてみてください。



いずれにしても、このような技術を使ってノイズで反転した「0」「1」を正しい符号に戻すことにより、多少電波や通信状態が悪かろうが、正しくメールやデジタルデータが相手に伝わるわけですよ。
いやぁ、誤り訂正符号の研究も数学を駆使することになるので、スゴイ面白そうなんだよねぇ。
posted by きらっち at 22:06| Comment(0) | TrackBack(0) | 科学
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

この記事へのトラックバックURL
http://blog.sakura.ne.jp/tb/29807541

この記事へのトラックバック