Universidad avanzadaApplied MathematicsPlanificado
Information theory
Entropy and information, Shannon's source coding theorem, prefix codes and Huffman coding, mutual information, channel capacity and the noisy-channel coding theorem.
math.applied.information-theory
La lección de este tema todavía no se ha escrito. El esquema siguiente forma parte del mapa del plan de estudios y no ha sido revisado.
Se basa en
Requisitos previos obligatorios, hasta el fondo: 41
Aprenderás a
- Compute entropy, joint and conditional entropy, and mutual information.
- Construct Huffman codes and prove Kraft's inequality.
- State the source coding and noisy-channel coding theorems and compute the capacity of the binary symmetric channel.
Definición
- The entropy of a discrete random variable X is H(X) = −Σ p(x) log₂ p(x).
- The mutual information of X and Y is I(X; Y) = H(X) − H(X | Y).
- The capacity of a channel is the maximum of I(X; Y) over all input distributions.
Teorema
- The expected length of an optimal binary prefix code for X lies between H(X) and H(X) + 1 bits.
- Kraft: a binary prefix code with codeword lengths ℓᵢ exists if and only if Σ 2^(−ℓᵢ) ≤ 1.
- The binary symmetric channel with crossover probability p has capacity 1 − H(p).
- Noisy-channel coding theorem: reliable communication is possible at every rate below capacity and impossible at rates above it.
Errores frecuentes
- Equating information with meaning; Shannon information measures uncertainty.
- Thinking a compression method can shrink every file.
Descubrimientos opcionales
Itinerarios de aprendizaje
Lecturas complementarias
- Thomas M. Cover and Joy A. Thomas, Elements of Information Theory (1991)
- David J. C. MacKay, Information Theory, Inference, and Learning Algorithms (2003)