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

データの冗長性を表現するにあたって、まず情報源のエントロピー率（レート）が記号ごとのエントロピーの平均であることに注目する。メモリをもたない情報源では、これは単に各記号のエントロピーだが、多くの確率過程では次のようになる。 r = lim n → ∞ 1 n H ( M 1 , M 2 , … M n ) , {\displaystyle r=\lim _{n\to \infty }{\frac {1}{n}}H(M_{1},M_{2},\dots M_{n}),}

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

言語または情報源の絶対レート（absolute rate）は単純に次のようになる。 R = log ⁡ 。 M 。 , {\displaystyle R=\log |M|,\,}

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

以上から、絶対冗長性（絶対冗長量）は次のように定義される。 D = R − r , {\displaystyle D=R-r,\,}

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

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

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

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

関連項目

データ圧縮

符号化方式

ネゲントロピー

表

話

編

歴
データ圧縮方式
可逆

エントロピー符号

一進法

算術

Asymmetric numeral systems（英語版）

ゴロム

ハフマン

適応型（英語版）

正準（英語版）

MH


レンジ

シャノン

シャノン・ファノ

シャノン・ファノ・イライアス（英語版）

タンストール（英語版）

ユニバーサル（英語版）

指数ゴロム（英語版）

フィボナッチ（英語版）

ガンマ

レーベンシュタイン（英語版）


辞書式（英語版）

BPE

Deflate

Lempel-Ziv

LZ77

LZ78

LZFSE

LZH

LZJB（英語版）

LZMA

LZO

LZRW（英語版）

LZS（英語版）

LZSS

LZW

LZWL（英語版）

LZX

LZ4

ROLZ（英語版）

統計型（英語版）

Brotli

Snappy

Zstandard


その他

BWT

CTW（英語版）

Delta

DMC（英語版）

MTF

PAQ

PPM

RLE


音声

理論

ビットレート

平均(ABR)

固定(CBR)

可変(VBR)


コンパンディング

畳み込み

ダイナミックレンジ

レイテンシ（英語版）

標本化定理

標本化

音質

音声符号化

サブバンド符号化

変換符号化

知覚符号化

コーデック

A-law

μ-law

ACELP

ADPCM

CELP

DPCM

フーリエ変換

LPC

LAR

LSP


MDCT

音響心理学

WLPC