情報理論 - 通信路符号化

概要

通信路符号化は、情報を効率的かつ信頼性高く伝送するための重要な技術である。

1948年にクロード・シャノンにより提唱された。
これは、ノイズのある通信路でも、通信路容量以下の情報であれば、任意に小さい誤り率で伝送できることを理論的に証明した。

通信路符号化は、送信するデータに冗長性を持たせることにある。
例えば、単純な反復符号では同じビットを複数回送信することにより、ノイズの影響を軽減する。
しかし、実際の通信システムではより洗練された符号化方式が用いられる。

代表的な符号化方式として、ハミング符号がある。
これは、データビットにパリティビットを追加することにより、1ビットの誤りを検出し訂正できる符号である。

より高度な符号としてBCH符号やリード・ソロモン符号があり、これらは複数ビットの誤りに対応できる。

現在では、畳み込み符号とターボ符号が広く使用されている。
畳み込み符号は、入力データを過去の入力と組み合わせて符号化することにより、連続的な誤り訂正能力を持つ。
ターボ符号は、複数の符号器と反復復号を組み合わせることで、シャノン限界に近い性能を実現することが可能である。

近年では、LDPC (Low-Density Parity-Check) 符号が注目を集めている。
これは疎なパリティ検査行列を使用して、高い符号化効率と優れた誤り訂正能力を両立する。
5G等の最新の通信規格でも採用されている。

符号化の性能評価には、主に符号化率と最小距離が用いられる。
符号化率は元のデータ量に対する符号化後のデータ量の比で効率性を表す。

最小距離は、符号語間のハミング距離の最小値で、誤り訂正能力を決定付ける。

通信路符号化は、理論と実践の両面で発展を続けており、量子通信やDNAストレージ等、新しい応用分野も広がっている。

通信路モデル

通信路モデルは、情報がどのように伝送され、その過程でどのような影響を受けるかを数学的に表現したものである。

離散無記憶通信路 (DMC: Discrete Memoryless Channel) は、最も基本的な通信路モデルである。
この通信路では、入力シンボルが出力シンボルに変換される過程が、確率的に表現される。

「離散」とは入出力が離散的な値を取ることを意味し、「無記憶」とは現在の出力が過去の入出力に依存しないことをす。

例えば、二元対称通信路 (BSC: Binary Symmetric Channel) では、入力ビット (0または1) が確率pで反転し、確率 (1-p) で正しく伝送される。
この確率pは、通信路の誤り率を表す。

通信路容量Cは、通信路を通じて伝送可能な最大の情報量を表す。

シャノンの通信路容量定理によれば、$C={\mbox{max[I(X;Y)]}}$ と定義される。
ここで、I(X;Y)は入力Xと出力Yの相互情報量である。

BSCの場合、通信路容量は次式で与えられる。
ここでH(p)は二元エントロピー関数である。
$C=1-H(p)$

ノイズは通信路上で発生する外乱であり、熱雑音、干渉、フェージング等が原因である。
これらのノイズにより、送信信号は歪められて、受信側で誤りが生じる。

誤りパターンは通信路の特性によって異なり、ランダム誤り、バースト誤り (連続的な誤り) 等がある。

符号化の基礎

符号化率Rは、情報ビット数kと符号語長nの比として次式で定義される。
$R={\dfrac {k}{n}}$

例えば、4ビットの情報に対して7ビットの符号語を使用する場合、符号化率は ${\dfrac {4}{7}}$ となる。

符号化率が高いほど伝送効率は良くなるが、誤り訂正能力は低下する。

ハミング距離は、2つの符号語間で異なるビット位置の数を表す。

例: ハミング距離が2の場合 (2番目と3番目のビットが異なる)

符号語1: 1010
符号語2: 1100

最小距離d_minは、符号に含まれる任意の2つの符号語間のハミング距離の最小値のことである。
これにより、符号の誤り検出・訂正能力が決まる。

t個までの誤りを検出する場合:
$d_{min}\geq t+1$

t個までの誤りを訂正する場合
$d_{min}\geq 2t+1$

エンコーダの基本構造

1. 情報ビット列を受信する。
2. 符号化規則に従って冗長ビットを付加する。
3. 符号語を生成する。

デコーダの基本構造

1. 受信した符号語を解析する。
2. 誤り検出を行う。
3. 可能な場合は誤り訂正を実施する。
4. 元の情報ビットを復元する。

デコーディング方式には、以下に示すものがある。

• 最尤復号

  受信語に最も近い符号語を選択する。

• シンドローム復号

  誤りパターンを効率的に特定する。

• 反復復号

  段階的に信頼度を向上させる。

実際の系では、上記の概念を組み合わせて、要求される性能と複雑さのバランスを取った設計が行われる。