الانتقال إلى المحتوى
The Lumenary
المرحلة الجامعية المتقدمةApplied Mathematicsمُخطَّط له

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

أظهِر كل ما يلزم للوصول إلى هذا الموضوع

لم يُكتب درس هذا الموضوع بعد. المخطط أدناه جزء من خريطة المنهج ولم تجرِ مراجعته.

يعتمد على

Probability theory

عدد المتطلبات السابقة الإلزامية (حتى الأساس): 41

ستتعلّم

  • 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.

تعريف

  • 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.

مبرهنة

  • 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.

مفاهيم خاطئة شائعة

  • Equating information with meaning; Shannon information measures uncertainty.
  • Thinking a compression method can shrink every file.

اكتشافات اختيارية

مسارات التعلّم

قراءات إضافية

  • Thomas M. Cover and Joy A. Thomas, Elements of Information Theory (1991)
  • David J. C. MacKay, Information Theory, Inference, and Learning Algorithms (2003)