Saltar al contenido ForoHackers

Information theory: start here

Teoría de la información
#3409 · · Citar · 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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder