A source can be compressed only when it has redundancy which is the amount of “useless information” that can be eliminated via fixed length compression codes. >[!def] Redundancy >For a stationary ergodic source, its total redundancy ρT is defined as: ρT=log2∣X∣−H(X)where log2∣X∣ is the compression rate of UD code and H(X) is the rate for asymptotically lossless code.
Proposition (2 types of redundancies)
ρT=ρD+ρM
where: >[!def] Intra-symbol source redundancy >ρD is the redundancy due to source’s non-uniform marginal pmf ρD=log2∣X∣−H(X1)this looks at the redundancy for each RV isolated from others (i.e. some letters in the alphabet are just more common than others independent of their ordering in words or sentences)
Definition (Inter-symbol source redundancy)
ρM is the redundancy due to source memory: ρM=H(X1)−H(X)this looks at redundancy when comparing between RVs in sequence (i.e. the letter ‘q’ is often followed by ‘u’ in the English language so this introduces some redundancy).
Proposition ((Redundancies for different stationary ergodic sources))
\mboxSource\mboxiiduniform\mboxiidnon−uniform\mboxMCsymmetric(i.e.uniformMC)\mboxMCnon−symmetric(i.e.non−uniformMC)ρD0log∣X∣−H(X1)0log∣X∣−H(X1)ρM00H(X1)−H(X2∣X1)H(X1)−H(X2∣X1)ρT=ρD+ρM0ρDρMρD+ρM