Skip to the content ForoHackers
Log inJoin

Information theory: start here

Information theory
#3409 · · Quote · Report

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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply