> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/compression.md).

# compression

## Basic idea

Encoding data with fewer bits by exploiting statistical structure. Lossless compression is bounded below by Shannon entropy; lossy compression trades fidelity for size.

## Key formulas

* Shannon source-coding bound: $\bar L \ge H(X)$
* Kraft inequality: $\sum\_i 2^{-l\_i} \le 1$
* Shannon entropy: $H(X) = -\sum\_i p\_i \log\_2 p\_i$
* Source coding: rates above entropy are asymptotically achievable; rates below entropy are not.
* Channel coding: rates below $C=\max\_{p(x)}I(X;Y)$ admit asymptotically reliable codes.
* A code of distance $d$ corrects $\lfloor(d-1)/2\rfloor$ errors; Reed–Solomon codes meet the Singleton bound.