> 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/error_correcting_codes.md).

# Error-correcting codes

## Basic idea

Error-correcting codes add structured redundancy so a receiver can reconstruct data corrupted in transit or storage. Code distance determines the number of detectable and correctable symbol errors.

## Key formulas

* A block code maps $k$ information symbols to $n$ code symbols; its rate is $R=k/n$.
* Minimum distance $d$ detects up to $d-1$ errors and corrects up to $\lfloor(d-1)/2\rfloor$ errors.
* Binary Hamming codes have parameters $\[2^r-1,2^r-r-1,3]$ and correct one bit error using a syndrome that identifies its position.
* Adding an overall parity bit gives SECDED: single-error correction and double-error detection.
* Reed–Solomon encodes a degree-$\<k$ polynomial by evaluating it at $n$ distinct field points.
* An $\[n,k]$ Reed–Solomon code has distance $d=n-k+1$, meeting the Singleton bound and making it maximum-distance separable.
* Erasures reveal their locations: a code of distance $d$ corrects any $s$ erasures and $e$ errors when $s+2e\<d$.
* Practical decoding uses polynomial interpolation, syndromes, the error-locator polynomial, and finite-field arithmetic.

## Resources

* [Reed–Solomon error correction](https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction)
* [Hamming code](https://en.wikipedia.org/wiki/Hamming_code)