符号理論

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

符号理論(ふごうりろん、: Coding theory)は、情報を符号化して通信を行う際の効率と信頼性についての理論である。数学情報理論と深く関わっている。また、符号の特性についても研究し、特定の用途に適した符号体系を作るのに使われる。

符号は以下の2種類に分けられる。

  1. 情報源符号(データ圧縮: コンパクト符号など)
  2. 伝送路符号(誤り検出訂正: ブロック符号畳み込み符号前方誤り訂正(FEC)、など)

情報源符号化は、情報源で転送前のデータをより効率的に圧縮することを目指す。この成果はインターネット上でのデータ圧縮形式としてよく見かける。伝送路符号化は、余分なデータビット(冗長ビット)を付与することで、通信路上に存在する雑音などの障害への耐性を強化する。この技術はあまり目立たないが、例えば音楽CDではリード・ソロモン符号を使って傷や埃による誤りを訂正している。この場合の通信路はCD自体である。携帯電話も高周波転送におけるノイズや減衰による誤りを検出訂正する技術を使っている。一般にデジタル信号による通信には、必ず何らかの誤り検出訂正技術が使われている。

情報源符号化[編集]

情報源符号化の目的は、情報源におけるデータをより小さくすることである。詳細は符号化方式およびデータ圧縮を参照されたい。

情報源のエントロピーは情報量の尺度である。基本的に情報源符号化では情報源に存在する冗長性をなるべく排除しようとし、より少ないビット数でより多くの情報を格納しようとする。データ圧縮の手法として、特定の確率モデルに従ってメッセージのエントロピーを最小化する手法をエントロピー符号と呼ぶ。情報源符号化として情報源のエントロピーの限界を達成しようとする各種技法がある。ただし、理論上限界とされる以上の効率は達成できない。

例えば、ファクシミリの転送では、単純な連長圧縮符号が使われている。

伝送路符号化[編集]

伝送路符号化の目的は、なるべく高速に転送でき、なるべく多くの符号語を含み、誤り検出訂正可能な符号を見出すことである。これらの目的は互いに相反するため、用途によって適切な符号体系は異なる。符号に求められる特性は、転送中に発生するエラーの確率に依存する。例えば、CD では埃や傷による誤りを訂正することを主に考慮している。従って符号はインターリーブされた形式となり、データはディスク面のあちこちに分散される。よい符号とは言えないが、単純な繰り返し符号を例として考える。例えば、何らかの(音声のような)データのブロックを3回送信するとする。受信側は3回受信したデータブロックをビット毎に比較し、多数決で正しいデータを決定する。これを少しひねって、ビットの送信順を変えてインターリーブさせる。データを4つの小さいブロックに分割し、1つめのブロックの1ビット目の次に2つめのブロックの1ビット目という順に送信するのである。これをディスク面全体に分散するよう3回繰り返す。このような単純な繰り返し符号ではあまり効率的ではないが、実際にはもっと効率的な符号を使って情報をインターリーブし、ディスク面の一部に傷があっても誤り訂正できるようにしている。

別の用途にはもっと適した符号が別に存在する。宇宙空間での通信は受信機の熱雑音の影響が大きく、これはCDの傷などとは異なり、連続的なノイズである。電話回線を使ったモデムではノイズがあるために転送速度が制限されるが、それと同様である。携帯電話は減衰が問題となる。高周波では受信機がほんの数センチ動いただけでも減衰により信号が捕らえられなくなる。このような減衰に対処する伝送路符号化の技法も存在する。

代数的符号理論(Algebraic coding theory)とは、符号の特性を代数学的に表現し研究する分野である。

代数的符号理論は基本的に以下の2つの符号に分類される。

  1. 線型ブロック符号
  2. 畳み込み符号

主に符号の以下の特性を分析する。

  • 符号語の長さ
  • 正しい符号語の総数
  • 2つの正しい符号語間の最小ハミング距離

線型ブロック符号[編集]

線型ブロック符号線型性を有している。すなわち、任意の2つの符号語の総和も符号語であり、情報源のビット列のブロックにもそれが適用される(そのため線型ブロック符号と呼ぶ)。線型でないブロック符号も存在するが、それでよいかどうかを証明することは困難である。

線型ブロック符号は (n,m,dmin) で表され、それぞれ以下のような意味を持つ。

  1. n は符号語の長さ(シンボル数)
  2. m は一度に符号化されるシンボル数
  3. dmin は符号間の最小ハミング距離

線型ブロック符号に属する符号として以下のようなものがある。

  1. 巡回符号ハミング符号は巡回符号のサブセット)
  2. 反復符号
  3. パリティ符号
  4. リード・ソロモン符号
  5. BCH符号
  6. 代数幾何符号
  7. リード・マラー符号
  8. 完全符号

ブロック符号は、硬貨を敷き詰める問題と関係している。これは2次元で考えると分かりやすい。硬貨を何枚もテーブルの上に並べ、なるべく稠密に敷き詰める。すると、ちょうど蜂の巣のように正六角形状に敷き詰められる。しかし、ブロック符号はもっと高次元であり、容易に視覚化できない。宇宙空間での通信に使われた強力なゴレイ符号では24次元を使っている。一般的な2進数の符号では次元は符号語の長さとなる。

符号理論では、N次元球モデルを使う。例えば、テーブル上の円に何枚の硬貨を敷き詰められるか、あるいは3次元では球体の中にどれだけビー玉を詰められるかという問題と同じである。別の考慮として、符号の選択がある。例えば、正六角形を四角形の枠に敷き詰めようとしても、角に隙間ができてしまう。次元を大きくすると、隙間となる空間の割合は小さくなる。しかし、ある次元で符号が隙間無く敷き詰められるようになり、それを完全符号と呼ぶ。そのような符号の例は非常にまれである(ハミング [n,k,3]、ゴレイ [24,12,8],[23,12,7],[12,6,6])。

もうひとつ、よく見逃される点として、1つの符号語が持つ近傍の数がある。再び硬貨を例にすると、最初に硬貨を方形の格子に詰める。この場合、各硬貨には4つの近傍がある。正六角形では、各硬貨は6つの近傍を持つ。次元を大きくすると、近傍の数は急速に増加する。結果として、ノイズによってある符合語を近傍の別の符号語と間違う可能性も大きくなる。これはブロック符号の基本的制限であり、実際すべての符号に言えることである。ある近傍に間違う可能性は低くても、近傍が増えれば全体としての誤り率は問題となる。

畳み込み符号[編集]

畳み込み符号は電話回線用モデム(V.32、V.17、V.34)や GSM 携帯電話、さらには衛星通信や軍事通信機器にも使われている。

ここでのアイデアは、入力となるメッセージ群のシンボル列の重み付き総和として各符号語のシンボルを作成するということである。これは線形時不変系において入力とインパルス応答が判っているときに出力を求める畳み込みに似ている。

従って、畳み込みエンコーダの出力は一般に、畳み込みエンコーダとレジスタの状態に対する入力ビットの畳み込みである。

基本的に畳み込み符号は同等なブロック符号以上のノイズ耐性を保証しないが、多くの場合、同程度のブロック符号よりも実装が大幅に単純化される。エンコーダは大抵の場合、状態メモリとフィードバック論理(通常 XORゲート)を持つ単純な回路である。デコーダはファームウェアやソフトウェアで実装される。

畳み込み符号のデコードに最適なアルゴリズムとしてビタービ・アルゴリズムがある。その計算負荷を減らす単純化手法もあり、最も可能性の高い経路だけを探索する。これは最適ではないが、低ノイズの環境ではよい結果となることがわかっている。最近のマイクロプロセッサでは、この縮小された探索アルゴリズムで平均毎秒4,000符号語以上のデコードが可能である。

符号理論の応用[編集]

符号理論におけるもう1つの課題は、同期を可能とする符号の設計である。例えば、位相変移(phase shift)を容易に検出・訂正できるよう符号を設計すれば、複数の信号を同じ通信路で同時に送ることができる。例えば、携帯電話で使われている符号分割多元接続(CDMA)符号がある。その詳細は本項目の範囲外だが、大まかに言えば、各携帯電話に特別な符号語が割り当てられる。転送時、その符号語を使って音声を表すビット列をスクランブル(暗号化)する。受信機では、その逆を行って暗号解読する。このような符号語の特性により、同時に複数の携帯電話がそれぞれ個別の符号語を割り当てられ、通話可能となる。1つの受信機から見れば、他の通話の信号は低レベルなノイズとしか認識されない。

もう1つの一般的な符号のクラスとして、自動再送制御(ARQ)符号がある。この場合、送信機は長いメッセージにパリティビットを付与する。受信機はメッセージとパリティビットが一致するかを調べ、一致しない場合に送信機にメッセージの再送を要求する。ごく単純なものを除いて、Wide Area Networkで使用されるプロトコルには必ず ARQ が使われている。例えば、SDLC (IBM)、TCPX.25 などである。この分野では、拒絶されたパケットと新たなパケットの一致問題という部分でも研究が進んでいる。つまり、新たに受信したパケットが再送されたものか、それとも別の新しいパケットなのかを識別する問題である。一般にパケットに番号を振ることで対処するが、プロトコルスタックがある場合、再送を制御する階層が異なる場合がある。TCP/IPは両方の技法を採用している好例である。コネクションのある場合、TCP/IPはARQ符号による再送を行う。しかし、コネクションがない場合、ARQ は使われず、アプリケーション層で(必要に応じて)再送を制御しなければならない。

関連項目[編集]

参考文献[編集]

  • Vera Pless, Introduction to the Theory of Error-Correcting Codes, John Wiley & Sons, Inc. (1982) ISBN 0-471-08684-3