Saltar al contenido ForoHackers

Information theory: start here

Teoría de la información
#903 · Ophuscado · · Denunciar

Information theory measures how much information a source produces and how reliably it can cross a noisy channel. It sets hard limits: the least a message can be compressed to, and the most a channel can carry without error. Compression, error-correcting codes, communications and parts of machine learning all rest on it.

Key concepts

  • Entropy: the average surprise of a source in bits; it is the lower bound on lossless compression.
  • Source coding: Huffman and arithmetic coding approach the entropy limit.
  • Channel capacity: the highest rate at which a noisy channel can carry data with arbitrarily small error.
  • Error-correcting codes: added redundancy lets the receiver detect and repair errors; parity, Hamming and Reed-Solomon codes are classics.
  • Mutual information: how much knowing one variable tells you about another.

Vocabulary

  • Bit: the unit of information, one yes-or-no choice between equally likely options.
  • Redundancy: the part of a message that is not needed to convey its content.
  • Lossy and lossless: whether the original can be recovered exactly.
  • Kolmogorov complexity: the length of the shortest program that outputs a given string.

What to study, in order

  1. Probability basics: distributions, expectation and independence.
  2. Compute the entropy of a text by letter frequencies and compare it with what a general-purpose compressor achieves.
  3. Implement Huffman coding and measure its gap from the entropy.
  4. Build a Hamming code that corrects a single flipped bit.
  5. Study channel capacity for a binary symmetric channel, then cross-entropy as a loss in learning.

Related tags

#probability #cryptography #signal-processing #machine-learning

Inicia sesión o únete para responder.