Beta Phase: Square45 is currently in beta testing. Expect some features or content to be incomplete or missing.
45

Shannon's Source Coding Theorem

Sets a fundamental limit on the average number of bits required to represent information from a source, impacting data compression and encryption efficiency.
📜

The statement of the theorem

Let XX be a discrete random variable representing the source output alphabet X\mathcal{X} with probability mass function P(x)P(x). The entropy of XX is defined as H(X)=−∑x∈XP(x)log⁡2P(x)H(X) = -\sum_{x \in \mathcal{X}} P(x) \log_2 P(x). For any uniquely decodable code C={cx}x∈X\mathcal{C} = \{c_x \}_{x \in \mathcal{X}} with average code length L=E[∣cX∣]L = E[|c_X|], the following inequality holds:\n1N∑i=1N∣cXi∣≥H(X)−12log⁡2(eN)\frac{1}{N} \sum_{i=1}^{N} |c_{X_i}| \ge H(X) - \frac{1}{2} \log_2 (e N) \nAs N→∞N \to \infty, the minimum average code length LminL_{min} approaches the entropy: Lmin≥H(X)L_{min} \ge H(X). Furthermore, there exists a code such that Lmin≤H(X)+ϵL_{min} \le H(X) + \epsilon for any ϵ>0\epsilon > 0.
Source: Wikipedia