Coding Theory & Compression

← Back to Domain-Specific Families

Abstractions about communication channels, error-correcting codes, decoding bounds and algorithms, quantization, bitrate control, and compact data representation.

15 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Binary erasure channel — A memoryless channel model that delivers each input bit correctly or replaces it with an explicit erasure symbol at a fixed probability.
• Communication source — The sender or stochastic process that generates and encodes message symbols for transmission through a communication channel to one or more receivers.
• Elias Bassalygo bound — An asymptotic upper bound on error-correcting-code rate derived by restricting codewords to a dense Hamming sphere and applying a Plotkin-type distance bound.
• Line spectral pairs — A representation of linear-prediction filter coefficients by the interlacing unit-circle roots of two symmetric auxiliary polynomials.
• Linear programming decoding — Error-correcting-code decoding by relaxing maximum-likelihood integer constraints to a tractable linear program over a codeword polytope approximation.
• Log area ratio — A logarithmic transform of a speech-filter reflection coefficient used as a quantized transmission parameter in legacy linear-predictive codecs.
• Parvaresh–Vardy code — An algebraic error-correcting code that encodes correlated polynomial evaluations so received words can be efficiently list-decoded beyond the Reed–Solomon radius.
• Polar code (coding theory) — A linear error-correcting code that recursively transforms channels into nearly perfect and nearly useless bit-channels, placing information only on the reliable ones.
• Sequential decoding — A variable-effort tree-search method for approximately maximum-likelihood decoding long convolutional or tree codes using far less memory than exhaustive trellis decoding.
• Shannon–Fano–Elias coding — A prefix-coding construction that chooses codewords from binary expansions of cumulative-probability midpoints.
• Small-bias sample space — A compact distribution on binary strings whose parity over every nonempty coordinate subset differs from uniform by at most ε, providing pseudorandomness against linear tests.
• Smart Bitrate Control — A historical DivX and Nandub multipass encoding technique that allocates bitrate and keyframes from first-pass video complexity analysis.
• Trellis quantization — Choose a block's quantized transform-coefficient sequence by searching a trellis whose states capture coding context and whose path cost combines distortion with estimated coded rate, rather than rounding coefficients independently.
• VCDIFF — A standardized delta-encoding format expressing a target byte sequence through ADD, COPY and RUN instructions relative to source data.
• Wozencraft ensemble — An explicit finite ensemble of rate-one-half linear codes over a finite field in which almost every member asymptotically meets the Gilbert–Varshamov distance bound.