😸

情報源符号化について

に公開
符号化
tech

符号化とは何か？無記憶・マルコフ情報源から最先端手法まで体系的に整理する

情報圧縮や通信において不可欠な技術である「符号化」。一口に符号化といっても、その対象や目的によって多種多様な手法が存在します。本記事では、情報源の種類と符号化の目的・手法に着目し、体系的に整理します。

🎯 符号化の目的による分類

区分 分類例 説明
情報圧縮（Source Coding） ハフマン符号、算術符号など 情報量を減らして効率よく表現する
誤り訂正（Channel Coding） ハミング符号、LDPCなど 通信路の誤りからデータを守る

🧠 情報源の種類

無記憶情報源（i.i.d.）

各記号が独立に、同じ分布に従って生成される。

  • 例：コイン投げ、独立な文字列

マルコフ情報源

直前の状態に依存して次の記号が生成される。

  • 例：自然言語、DNA配列

一般の確率過程

より高次な依存関係や非定常性を持つもの。

🧮 符号の性質と構造

符号（Code）の定義

情報源の各記号 x \in \mathcal{X} に対し、符号語 c(x) \in \{0,1\}^* を対応させる関数。

主な性質

  • 可逆性：元のデータに戻せる
  • 前綴符号（prefix-free）：ある符号語が他の接頭辞にならない
  • 一意復号可能：符号列から元の記号列が一意に定まる

📦 情報源符号化（可逆圧縮）

最適な平均符号長の下限：エントロピー

\mathbb{E}[l(X)] \geq H(X)

主な手法と特徴

手法 対象 特徴
ハフマン符号 無記憶情報源 最適な前綴符号、平均長が最小
シャノン符号 無記憶情報源 構成が簡単、エントロピーに近い
算術符号 任意の分布 平均長がエントロピーに任意に近づく
RLE 繰返しが多い列 連続する同じ記号を圧縮
LZW 一般 辞書ベース、実用的（PNGなど）
CTW マルコフ情報源 コンテキストに基づく圧縮

📡 通信路符号化（誤り訂正）

目的

ノイズのある通信路で、誤りを検出・訂正できるよう冗長性を追加する。

主な手法

手法 概要 特徴
パリティ符号 最も基本 誤り検出のみ可能
ハミング符号 1ビット誤り訂正 短距離通信に有効
リード・ソロモン符号 多重誤り訂正 CD, QRコードで活躍
畳み込み符号 状態依存 Viterbiアルゴリズムによる復号
LDPC/Turbo符号 近年の主力 5Gや衛星通信にも対応

📊 情報源ごとの比較

観点 無記憶情報源 マルコフ情報源
依存性 各記号は独立 状態遷移に依存
モデル P(x_1,\dots) = \prod P(x_i) ( P(x_1)\prod P(x_{i+1} x_i) )
適用符号 ハフマン、算術 CTW、Predictive Coding
難易度 比較的単純 状態推定が必要で複雑

✍️ まとめ

  • 符号化は「圧縮」と「誤り訂正」の2大目的に分類される
  • 情報源の統計的性質（無記憶、マルコフ）に応じた設計が重要
  • エントロピーは符号設計における理論的限界を与える
  • 実用的には、用途に応じてハフマン、LZW、算術符号、LDPCなどを使い分ける必要がある

🔍 次に読むなら

情報理論や圧縮アルゴリズムに関心がある方にとって、符号化は非常に奥が深く、理論と実装の橋渡しにもなる分野です。ご質問やコメントがあればぜひお知らせください！

GitHubで編集を提案

Discussion