冗長性 (情報理論)

冗長性：情報理論における無駄と効率

情報理論において、冗長性とは、メッセージの伝達に用いられるビット数と、そのメッセージの本質的な情報量との差を指します。言い換えれば、データ伝送における無駄な部分の量です。

例えば、同じ意味を伝えるのに、簡潔な表現と冗長な表現の両方がある場合、冗長な表現には無駄な情報が含まれています。この無駄な情報は、ノイズの多い通信路ではエラー検出や訂正に役立ちますが、そうでない場合は不要なデータ量を増やすだけです。

冗長性の定量的定義

冗長性を定量的に表現するには、情報源のエントロピーという概念が重要になります。エントロピーは、情報源から出力される記号の不確実性の尺度です。情報源のエントロピーレート（レート）は、記号ごとのエントロピーの平均値として定義されます。

メモリを持たない情報源の場合、レートは各記号のエントロピーに一致します。しかし、多くの確率過程では、長いメッセージ列全体の結合エントロピーを用いてレートを計算する必要があります。このレートは、メッセージ列の長さを無限大にしたときの、単位あたりのエントロピーの極限値として定義されます。

一方、絶対レートは、情報源が取りうる記号の種類数（アルファベットサイズ）の対数で表されます。これは、その情報源で伝達可能な情報の最大レートを示します。

絶対冗長性は、絶対レートと実際のレートの差として定義されます。そして、相対冗長性は、絶対冗長性を絶対レートで割った値であり、可能な最大データ圧縮率を示します。つまり、ファイルサイズをどれだけ削減できるかを表します。

冗長性とデータ圧縮

データ圧縮は、冗長性を排除・削減する技術です。冗長性の高いデータには、繰り返しパターンや予測可能な情報が多く含まれているため、それらを効率的に表現することで、データサイズを小さくすることができます。

例えば、テキストデータでは、特定の文字や単語が繰り返し出現することが多いため、それらの出現頻度に基づいて圧縮を行うことができます。画像データでは、隣接する画素の色が似ていることが多いので、差分符号化などの手法を用いて圧縮することができます。

冗長性と誤り訂正

ノイズの多い通信路では、データに意図的に冗長性を追加することで、誤りを検出したり訂正したりすることが可能です。チェックサムやハミング符号などは、冗長性を用いた誤り検出・訂正符号の例です。これらの符号は、データに冗長な情報を付加することで、受信側でエラーを検出し、場合によっては修正することができます。

冗長性と効率性

冗長性と対をなす概念として、効率性があります。効率性は、実際のレートを絶対レートで割った値で表され、情報伝達における効率の良さを示します。冗長性と効率性の和は常に1になります。

他の冗長性の表現

上記以外にも、相互情報量や合計相関など、冗長性を表現する様々な尺度が存在します。これらの尺度は、確率変数間の関係や、複数の確率変数をまとめて考えた場合の冗長性を測るために用いられます。

圧縮データの冗長性は、圧縮後のデータ長とエントロピーの差で表すことができます。メモリのない情報源では、この差は圧縮率に直接関係し、理想的な圧縮ではこの差はゼロに近づきます。

まとめ

冗長性は、情報伝達における無駄と効率の両面を持つ重要な概念です。データ圧縮や誤り訂正といった技術は、冗長性を適切に制御することで実現されています。情報理論における様々な問題を考える上で、冗長性の理解は不可欠です。

もう一度検索