情報理論 - 通信路符号化

概要

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

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. 元の情報ビットを復元する。

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

• 最尤復号

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

• シンドローム復号

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

• 反復復号

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

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

二元対称通信路

二元対称通信路 (Binary Symmetric Channel, BSC) とは、情報理論における最も基本的な通信路モデルの1つである。
この通信路では、入力信号と出力信号はともに2値 (0と1) で表現される。

この対称性が二元対称通信路の特徴である。
これは、入力された0が1に反転する確率と1が0に反転する確率が等しい。

この確率をp ( $0\leq p\leq 0.5$ ) と表す。

したがって、入力信号が正しく伝送される確率は、$1-p$ となる。
pは、通信路の反転確率あるいはビット誤り率 (BER : Bit Error Rate) と呼ばれる。

二元対称通信路の重要なものとして、通信路容量の計算が簡単に行えることが挙げられる。
通信路容量Cは以下の式で表される。
$C=1-H(p)$

ここで、H(p)は2値エントロピー関数で、次式で定義される。
$H(p)=-p\log _{2}p-(1-p)\log _{2}(1-p)$

${\begin{array}{cc}\quad {\begin{array}{cc}0&\quad 1\end{array}}\\{\begin{array}{c}0\\1\end{array}}{\begin{pmatrix}1-p&p\\p&1-p\end{pmatrix}}\end{array}}$

二元対称通信路の通信路容量が最大となる値pを求める場合、${\dfrac {dH(p)}{dp}}=0$ となる値pを求めればよい。
したがって、
${\begin{aligned}{\dfrac {dH(p)}{dp}}&=0\\&=-\log _{2}p-1-{\dfrac {du}{dp}}\log _{2}u+1\quad \therefore u=1-p\\&=-\log _{2}p+\log _{2}u\\&=-\log _{2}p+\log _{2}(1-p)\\&=\log _{2}{\dfrac {1-p}{p}}=0\end{aligned}}$

より、
${\begin{array}{lcl}\log _{2}{\dfrac {1-p}{p}}&=0\\\iff {\dfrac {1-p}{p}}&=e^{0}\\\iff 1-p&=p\\\iff 2p&=1\\\iff p&={\dfrac {1}{2}}\end{array}}$

二元対称通信路において、H(p)はノイズによって引き起こされる不確実性の量を表す。
つまり、pが大きくなるほど (0.5まで)、不確実性が増加して、結果として通信路容量が減少することを意味する。

二元対称通信路モデルは、実際の通信システムでも頻繁に使用される。
例えば、デジタル通信における雑音の影響を模擬する場合や誤り訂正符号の性能評価を行う場合のベースラインモデルとして広く活用されている。

特に、誤り訂正符号の設計において、ハミング符号やBCH符号等の線形ブロック符号は、この通信路モデルを前提として設計されている。
これらの符号は、通信路で発生するビット反転を検出して、場合によっては訂正することができる。

また、シャノンの符号化定理との関連において、
通信路容量Cより小さい任意の伝送レートRに対して、任意に小さい誤り確率を実現できる符号化方式が存在することが証明されている。

衛星通信や光ファイバー通信等の多くのデジタル通信システムにおいて、二元対称通信路は基本的なモデルとして使用されている。
ただし、実際の通信路はより複雑な特性を持つことが多く、より精密なモデル化が必要となる場合もある。

例題:
ビット誤り率 $p=0.1\quad \cdots 10[\%]$ の二元対称通信路を考える。
入力メッセージとして、"1011"のビット列を送信する。

各ビットは、次のような確率で伝送される。
* 正しく伝送される確率 : $1-p=0.9\quad \cdots 90[\%]$
* 反転する確率 : $p=0.1\quad \cdots 10[\%]$

例えば、この"1011"の4ビットのメッセージの伝送において、3番目のビットだけが反転した場合、出力は"1001"となる。
この特定のエラーパターンが発生する確率は、次式のように計算できる。
$0.9\times 0.9\times 0.1\times 0.9=0.0729\quad \cdots 7.29[\%]$

これは
1番目のビット : 正しく伝送 (確率0.9)
2番目のビット : 正しく伝送 (確率0.9)
3番目のビット : 反転 (確率0.1)
4番目のビット : 正しく伝送 (確率0.9)

この通信路の通信路容量Cにおいて、$p=0.1$ の場合の2値エントロピー関数H(p)は、
${\begin{aligned}H(0.1)&=-0.1\times \log _{2}(0.1)-0.9\times \log _{2}(0.9)\\&\approx 0.469{\mbox{[bit]}}\end{aligned}}$

したがって、通信路容量は $C=1-H(0.1)\approx 1-0.469\approx 0.531\,{\mbox{[bit]/[channel]}}$ 使用する。
これは、理想的な符号化を行うことにより、1回のチャネル使用あたり最大で約0.531[ビット]の情報を、任意に小さい誤り確率で伝送できることを意味する。

上記の計算例は、実際の通信システムの設計において、必要な誤り訂正符号の強度を決定、あるいは、達成可能な通信速度を見積もる場合に重要となる。

二元対称消失通信路

二元対称消失通信路とは

二元対称消失通信路 (Binary Erasure Channel: BEC) は、ビットが完全に消失する可能性のある通信路をモデル化する。

二元対称消失通信路の特徴

• 誤りの検出が容易である。(消失位置が既知)
• 理論解析が簡単である。
• 符号の性能評価に有効である。

応用例

• パケット通信のモデル化
• インターネット通信の解析
• 消失訂正符号の設計

• 入力

  0, 1

• 出力

  0, 1, 消失記号 (ε)

• 消失確率

  $\varepsilon (0<\varepsilon <1)$

• 正しく伝送される確率

  $1-p-\varepsilon$

遷移確率

• $P(Y=0|X=0)=1-p-\varepsilon$
• $P(Y=\varepsilon |X=0)=\varepsilon$
• $P(Y=1|X=0)=p$

  
  

• $P(Y=0|X=1)=p$
• $P(Y=\varepsilon |X=1)=\varepsilon$
• $P(Y=1|X=1)=1-p-\varepsilon$

これらの遷移確率は、二元対称消失通信路の特性を表しており、各状態からの遷移確率の合計は1になる。
二元対称消失通信路は対称的な性質を持っており、入力が0の場合と1の場合で対称的な遷移確率を持つ。

• 入力 X = 0 の場合

  $(1-p-\varepsilon )+\varepsilon +p=1$

• 入力 X = 1 の場合

  $p+\varepsilon +(1-p-\varepsilon )=1$

二元対称消失通信路の通信路容量

二元対称消失通信路の通信路容量は、$C=1-H(\varepsilon )$ で表される。
ここで、H(ε)は2値エントロピー関数であり、$H(\varepsilon )=-\varepsilon \log _{2}(\varepsilon )-(1-\varepsilon )\log _{2}(1-\varepsilon )$ で表される。

この式は、消失確率εが増加すると容量が減少することを示している。
$\varepsilon =0$ の時の通信路容量は1、$\varepsilon =1$ の時の通信路容量は0となる。

導出過程:

通信路容量は、相互情報量I(X;Y)の最大値として定義される。
$C={\mbox{max}}I(X;Y)$

二元対称消失通信路の場合、入力分布が一様分布 $(P(X=0)=P(X=1)={\dfrac {1}{2}})$ の時に最大になる。

相互情報量は以下のように展開できる。
$I(X;Y)=H(Y)-H(Y|X)$

二元対称消失通信路では、$H(Y|X)=H(\varepsilon )$ となる。
これは、各入力に対して確率εで消失することを表している。

最適な入力分布 (一様分布) の時、$H(Y)=1$ となる。

したがって、通信路容量は次式となる。
$C=H(Y)-H(Y|X)=1-H(\varepsilon )$