冗長性 (情報理論)のソースを表示

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

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

:<math>r = \lim_{n \to \infty} \frac{1}{n} H(M_1, M_2, \dots M_n),</math>

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

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

:<math>R = \log |M| ,\,</math>

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

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

:<math> D = R - r ,\,</math>

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

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

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

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

== 関連項目 ==
* [[データ圧縮]]
* [[符号化方式]]
* [[ネゲントロピー]]

{{データ圧縮}}
{{デフォルトソート:しようちようせい}}
[[Category:情報理論]]