冗長性 (情報理論)

冗長性（じょうちょうせい、英: Redundancy）とは、情報理論において、あるメッセージを転送するのに使われているビット数からそのメッセージの実際の情報に必須なビット数を引いた値である。冗長度、冗長量とも。大まかに言えば、あるデータを転送する際に無駄に使われている部分の量に相当する。好ましくない冗長性を排除・削減する方法として、データ圧縮がある。逆にノイズのある通信路容量が有限な通信路で誤り検出訂正を行う目的で冗長性を付与するのが、チェックサムやハミング符号などである。

定量的定義

データの冗長性を表現するにあたって、まず情報源のエントロピー率（レート）が記号ごとのエントロピーの平均であることに注目する。メモリをもたない情報源では、これは単に各記号のエントロピーだが、多くの確率過程では次のようになる。

r=\lim _{n\to \infty }{\frac {1}{n}}H(M_{1},M_{2},\dots M_{n}),

これは n 個の記号の結合エントロピーを n で割ったものの n が無限大になったときの極限である。情報理論では、言語の「レート」や「エントロピー」を扱うことが多い。これは例えば、情報源が英語などの言語の文である場合には適切である。メモリのない情報源では、その逐次的メッセージ列に相互依存が全くないため、レートは定義から $H(M)$ となる。

言語または情報源の絶対レート（absolute rate）は単純に次のようになる。

R=\log |M|,\,

これは、メッセージ空間あるいはアルファベットの濃度（cardinality）の対数である。この式を「ハートレー関数 (Hartley function)」と呼ぶこともある。これがそのアルファベットで転送可能な情報の最大のレートとなる。対数の底は測定単位を考慮して決定される。情報源にメモリがなく、一様分布であるとき、絶対レートは実際のレートと等しい。

以上から、絶対冗長性（絶対冗長量）は次のように定義される。

D=R-r,\,

これはつまり、絶対レートと実際のレートの差である。

${\frac {D}{R}}$ を相対冗長性（相対冗長量）と呼び、可能な最大データ圧縮比を表している。すなわち、ファイルサイズがどれだけ削減できるかということと等価である。冗長性と対をなす概念として効率（efficiency）があり、 ${\frac {r}{R}}$ で表される。したがって、 ${\frac {r}{R}}+{\frac {D}{R}}=1$ である。メモリのない一様分布の情報源は、冗長性がゼロで効率が100%であり、圧縮できない。

他の冗長性の表現

2つの確率変数の「冗長性」の尺度として、相互情報量あるいはその正規化形がある。多数の確率変数の冗長性の尺度としては、合計相関（total correlation）がある。

圧縮済みデータの冗長性は、 $n$ 個のメッセージを圧縮したときの期待される長さ $L(M^{n})$ とそのエントロピー $nr$ の差で表される。ここで、データはエルゴード的で定常的であると仮定している。つまり、メモリのない情報源である。レートの差 $L(M^{n})/n-r$ は $n$ が増大するに従って小さくなるが、実際の差 $L(M^{n})-nr$ はそうならない。しかし、エントロピーが有限なメモリのない情報源では、理論上の上限が 1 となる。

参考文献

Fazlollah M. Reza. An Introduction to Information Theory. New York: McGraw-Hill, 1961. New York: Dover, 1994. ISBN 0-486-68210-2
B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C. New York: John Wiley & Sons, Inc., 1996. ISBN 0-471-12845-7

定量的定義

他の冗長性の表現

参考文献

関連項目