Redundancy (information theory)

In Information theory, redundancy measures the fractional difference between the entropy H(X) of an ensemble X, and its maximum possible value log ⁡ ( | A X | ) {displaystyle log(|{mathcal {A}}_{X}|)} . Informally, it is the amount of wasted 'space' used to transmit certain data. Data compression is a way to reduce or eliminate unwanted redundancy, while checksums are a way of adding desired redundancy for purposes of error detection when communicating over a noisy channel of limited capacity. In Information theory, redundancy measures the fractional difference between the entropy H(X) of an ensemble X, and its maximum possible value log ⁡ ( | A X | ) {displaystyle log(|{mathcal {A}}_{X}|)} . Informally, it is the amount of wasted 'space' used to transmit certain data. Data compression is a way to reduce or eliminate unwanted redundancy, while checksums are a way of adding desired redundancy for purposes of error detection when communicating over a noisy channel of limited capacity. In describing the redundancy of raw data, the rate of a source of information is the average entropy per symbol. For memoryless sources, this is merely the entropy of each symbol, while, in the most general case of a stochastic process, it is the limit, as n goes to infinity, of the joint entropy of the first n symbols divided by n. It is common in information theory to speak of the 'rate' or 'entropy' of a language. This is appropriate, for example, when the source of information is English prose. The rate of a memoryless source is simply H ( M ) {displaystyle H(M)} , since by definition there is no interdependence of the successive messages of a memoryless source. The absolute rate of a language or source is simply the logarithm of the cardinality of the message space, or alphabet. (This formula is sometimes called the Hartley function.) This is the maximum possible rate of information that can be transmitted with that alphabet. (The logarithm should be taken to a base appropriate for the unit of measurement in use.) The absolute rate is equal to the actual rate if the source is memoryless and has a uniform distribution. The absolute redundancy can then be defined as