Shannon's Source Coding Theorem: Optimal Lossless Rates and the Kraft Inequality

Intuition Beginner

You have four messages to send: A, B, C, and D. Message A happens half the time, B a quarter of the time, and C and D each one-eighth of the time. You want to encode each message as a string of 0s and 1s so that you can send the shortest possible string on average.

A naive encoding uses two bits for every message: A = 00, B = 01, C = 10, D = 11. The average length is 2 bits. But A is much more common than D. What if you gave A a shorter code? Say A = 0, B = 10, C = 110, D = 111. Now the average length is $0.5\times 1+0.25\times 2+0.125\times 3+0.125\times 3=1.75$ bits. You saved 0.25 bits per message.

This code has a special property: no codeword is a prefix of another. If you see a 0, you know it is A immediately — no other codeword starts with 0. This is called a prefix-free code, and it means you can decode messages as they arrive without waiting for a delimiter.

Shannon's source coding theorem says that the entropy of the source sets the floor for how short any prefix-free code can be. The entropy of this source is $H=1.75$ bits, and our code achieves exactly that. We matched the limit. In general, the best you can do is between $H$ and $H+1$ bits per symbol — and by encoding blocks of symbols together, you can get arbitrarily close to $H$.

The engine behind all of this is the Kraft inequality. It is a simple constraint on the lengths of a prefix-free code: if your codeword lengths are $l_1,l_2,\dots ,l_m$, then the sum $\frac{1}{2^{l_1}}+\frac{1}{2^{l_2}}+\cdots +\frac{1}{2^{l_m}}$ must be at most 1. This single inequality is both necessary (every prefix-free code satisfies it) and sufficient (any set of lengths satisfying it can be realised as a prefix-free code). It is the bridge between the geometry of binary trees and the arithmetic of compression.

Visual Beginner

Symbol	Probability	Codeword	Length	Contribution to average length
A	0.500	0	1	$0.500\times 1=0.500$
B	0.250	10	2	$0.250\times 2=0.500$
C	0.125	110	3	$0.125\times 3=0.375$
D	0.125	111	3	$0.125\times 3=0.375$
Total	1.000			1.750 bits

Figure: a binary tree with root at the top. The left branch from the root is labelled 0 and leads to leaf A at depth 1. The right branch is labelled 1; its left child is labelled 0 and leads to leaf B at depth 2. The right child of that node branches again: left to C (code 110, depth 3) and right to D (code 111, depth 3). Each leaf is labelled with its symbol and probability. The tree has no internal node that is also a leaf — this is the prefix-free property visualised.

The Kraft sum for this code: $1/2+1/4+1/8+1/8=1$. The sum equals 1 exactly, which means no shorter code exists for these lengths — the code tree is "full."

Worked example Beginner

Consider a source with four symbols and probabilities $p_A=0.5$, $p_B=0.25$, $p_C=0.125$, $p_D=0.125$.

Step 1: Compute the entropy. The entropy measures the average information content. For each symbol, the information is ${\log }_2(1/p)$.

• A: ${\log }_2(1/0.5)=1$ bit
• B: ${\log }_2(1/0.25)=2$ bits
• C: ${\log }_2(1/0.125)=3$ bits
• D: ${\log }_2(1/0.125)=3$ bits

The entropy is the probability-weighted average:

$$H=0.5\times 1+0.25\times 2+0.125\times 3+0.125\times 3=1.75\text{ bits}.$$

Step 2: Build a code. Assign codewords using the Shannon-Fano idea: give symbol $i$ a codeword of length $\lceil {\log }_2(1/p_i)\rceil$. For our source, the ideal lengths are exactly 1, 2, 3, 3 — all integers already. We assign A = 0, B = 10, C = 110, D = 111.

Step 3: Verify the Kraft inequality. The sum is $2^{-1}+2^{-2}+2^{-3}+2^{-3}=0.5+0.25+0.125+0.125=1$. The inequality is satisfied with equality, so these lengths are achievable as a prefix-free code.

Step 4: Compute the expected length. The average codeword length is $0.5\times 1+0.25\times 2+0.125\times 3+0.125\times 3=1.75$ bits. This equals the entropy $H=1.75$ bits exactly. The source coding theorem says this is the best possible — no prefix-free code can do better.

Check your understanding Beginner

Formal definition Intermediate+

Let $\mathcal{X}=\{x_1,\dots ,x_m\}$ be a finite source alphabet with probability distribution $p=(p_1,\dots ,p_m)$.

Definition (Binary code). A code is a mapping $C:\mathcal{X}\to \{0,1{\}}^{\ast }$ assigning to each source symbol a finite binary string called a codeword. The length $l_i=|C(x_i)|$ is the number of bits in the codeword for $x_i$.

Definition (Prefix-free code). A code $C$ is prefix-free (or instantaneous) if no codeword is a prefix of any other codeword: for all $i\ne j$, $C(x_i)$ is not a prefix of $C(x_j)$.

Definition (Expected length). The expected length of a code $C$ for source $(\mathcal{X},p)$ is:

$$L(C)=\sum _{i=1}^m{p}_i{l}_i.$$

Definition (Optimal code). Define $L^{\ast }={\min }_{C}L(C)$ where the minimum is over all prefix-free codes for $(\mathcal{X},p)$.

Counterexamples to common slips

• Prefix-free is not the same as uniquely decodable. A uniquely decodable code allows unambiguous decoding of concatenated codewords but may not be instantaneous. Every prefix-free code is uniquely decodable, but not vice versa (e.g., the code $\{0,01\}$ is uniquely decodable but not prefix-free — you can always parse by reading from the right, but you cannot decode left-to-right without lookahead).

• The Kraft inequality is about lengths, not specific codewords. The inequality constrains the set of lengths $\{l_i\}$, not the particular assignment of binary strings. Two different prefix-free codes with the same length vector satisfy the same Kraft sum.

• $L^{\ast }$ is defined over prefix-free codes, not all codes. If you allow non-prefix-free codes, you can sometimes achieve shorter expected length, but the resulting code may not be practically decodable. The restriction to prefix-free codes is without loss of optimality for expected length, because McMillan's theorem (below) shows that any uniquely decodable code has lengths satisfying Kraft.

Key theorem with proof Intermediate+

Theorem (Kraft inequality — necessity). If $C$ is a prefix-free binary code with codeword lengths $l_1,\dots ,l_m$, then

$$\sum _{i=1}^m{2}^{-l_i}\le 1.$$

Proof. Let $l_{\max }={\max }_i{l}_i$. Consider the full binary tree of depth $l_{\max }$. This tree has $2^{l_{\max }}$ leaf nodes. Each codeword $C(x_i)$ of length $l_i$ corresponds to a node at depth $l_i$ in the tree. Because the code is prefix-free, no codeword node is an ancestor of another. The subtree rooted at the codeword node for $x_i$ contains $2^{l_{\max }-l_i}$ leaves, and these subtrees are disjoint. Therefore:

$$\sum _{i=1}^m{2}^{l_{\max }-l_i}\le 2^{l_{\max }},$$

since the total number of leaves in all disjoint subtrees cannot exceed the total number of leaves in the tree. Dividing both sides by $2^{l_{\max }}$ yields the result. $\square$

Theorem (Kraft inequality — sufficiency). Given lengths $l_1,\dots ,l_m$ satisfying $\sum 2^{-l_i}\le 1$, there exists a prefix-free binary code with these exact lengths.

Proof. Construct the code by traversing a binary tree from the root. Sort the lengths so $l_1\le l_2\le \cdots \le l_m$. At each step $k$, assign the leftmost available node at depth $l_k$ as the codeword for $x_k$, and remove its entire subtree from future consideration.

We must verify that a node is always available at step $k$. At depth $l_k$, the full tree has $2^{l_k}$ nodes. After assigning the first $k-1$ codewords, the number of nodes removed from depth $l_k$ is at most ${\sum }_{i=1}^{k-1}{2}^{l_k-l_i}$ (each earlier codeword of length $l_i\le l_k$ blocks $2^{l_k-l_i}$ nodes at depth $l_k$). The number of remaining available nodes is:

$$2^{l_k}-\sum _{i=1}^{k-1}{2}^{l_k-l_i}=2^{l_k}\left(1-\sum _{i=1}^{k-1}{2}^{-l_i}\right)\ge 2^{l_k}\cdot 2^{-l_k}=1,$$

where the inequality uses ${\sum }_{i=1}^m{2}^{-l_i}\le 1$, so ${\sum }_{i=1}^{k-1}{2}^{-l_i}\le 1-2^{-l_k}$. Thus at least one node remains. $\square$

Theorem (McMillan). The Kraft inequality holds for the codeword lengths of any uniquely decodable code, not just prefix-free codes. Consequently, the set of achievable length vectors is the same for uniquely decodable codes and prefix-free codes.

Proof sketch. For a $D$-ary alphabet, let $C$ be uniquely decodable with lengths $l_1,\dots ,l_m$. Consider the $k$-th power of the code (the code applied to $k$-tuples of source symbols). This extended code has length sum ${\left(\sum D^{-l_i}\right)}^k$. Since the extended code must also be uniquely decodable, its lengths must be at least 1, giving ${\left(\sum D^{-l_i}\right)}^k\le D^{l_{\max }\cdot k}$ for each $k$. Taking $k$-th roots and letting $k\to \infty$ forces $\sum D^{-l_i}\le 1$. $\square$

Theorem (Shannon source coding theorem — one-shot). Let $X$ be a discrete random variable with entropy $H(X)$. Then the minimum expected codeword length $L^{\ast }$ over all prefix-free binary codes satisfies:

$$H(X)\le L^{\ast }<H(X)+1.$$

Proof of lower bound. For any prefix-free code with lengths $\{l_i\}$, define $q_i=2^{-l_i}/K$ where $K={\sum }_j{2}^{-l_j}\le 1$ by Kraft. Then $(q_1,\dots ,q_m)$ is a probability distribution. The expected length is:

$$L=\sum p_i{l}_i=-\sum p_i{\log }_2(2^{-l_i})=-\sum p_i{\log }_2(K\cdot q_i)=-{\log }_{2}K-\sum p_i{\log }_2{q}_i.$$

Since $K\le 1$, we have $-{\log }_{2}K\ge 0$. By Gibbs' inequality, $\sum p_i{\log }_2{q}_i\le \sum p_i{\log }_2{p}_i=-H(X)$. Therefore:

$$L=-{\log }_{2}K-\sum p_i{\log }_2{q}_i\ge 0+H(X)=H(X).\square$$

Proof of upper bound (Shannon-Fano coding). Assign codeword length $l_i=\lceil -{\log }_2{p}_i\rceil$. First, verify Kraft:

$$\sum _{i=1}^m{2}^{-l_i}=\sum _{i=1}^m{2}^{-\lceil -{\log }_2{p}_i\rceil }\le \sum _{i=1}^m{2}^{{\log }_2{p}_i}=\sum _{i=1}^m{p}_i=1.$$

So a prefix-free code with these lengths exists. The expected length is:

$$L=\sum p_i\lceil -{\log }_2{p}_i\rceil <\sum p_i(-{\log }_2{p}_i+1)=H(X)+1.\square$$

Theorem (Source coding theorem — tight version). Let $X_1,X_2,\dots$ be i.i.d. draws from $p$. Define $L_n^{\ast }$ as the minimum expected codeword length per symbol for blocks of size $n$ (i.e., the optimal code for $(X_1,\dots ,X_n)$ has expected length $n\cdot L_n^{\ast }$). Then:

$$\underset{n\to \infty }{\lim }{L}_n^{\ast }=H(X).$$

Proof. Apply the one-shot theorem to the block random variable $(X_1,\dots ,X_n)$, which has entropy $nH(X)$ by the chain rule and independence. The one-shot bounds give $nH(X)\le n{L}_n^{\ast }<nH(X)+1$, so $H(X)\le L_n^{\ast }<H(X)+1/n$. As $n\to \infty$, the upper bound converges to $H(X)$. $\square$

Bridge. The source coding theorem builds toward the channel coding theorem 46.03.01 where entropy reappears as the capacity limit, and this time with a noisy channel rather than a clean wire; it appears again in rate-distortion theory 46.04.01 where the lossy version replaces the entropy with the rate-distortion function $R(D)$, and the foundational reason entropy governs compression is that the Kraft inequality ties every binary tree to the simplex of distributions, making $H(X)$ the unique exponent that satisfies both the counting bound and the achievability construction. This is exactly the AEP 46.02.01 made operational: the typical set of size $2^{nH}$ is the object being indexed, and the Kraft inequality guarantees that the index fits in $nH+1$ bits. The central insight is that prefix-free codes, uniquely decodable codes, and block-optimal codes all live in the same length-constrained world governed by $\sum 2^{-l_i}\le 1$.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib does not define prefix-free codes, the Kraft inequality, or the source coding theorem. The PMF type for probability mass functions exists, and entropy is definable as a functional on PMF, but the connection to coding theory is absent. A Codex.InformationTheory.SourceCoding module would need:

1. A PrefixCode structure parametrised by an alphabet and a list of codeword lengths.
2. A proof that Sum (2 ^ (-l_i)) <= 1 is necessary and sufficient for the existence of a prefix-free code (Kraft inequality, both directions).
3. McMillan's theorem: uniquely decodable codes satisfy Kraft.
4. The source coding theorem bounds: H(X) <= L* and L* < H(X) + 1.
5. The tight version: L_n^* / n -> H(X).

Items 1-3 are combinatorial and should be approachable with Mathlib's existing List and Finset machinery. Item 4 requires the entropy functional from 46.01.01, which is itself not yet in Mathlib. Item 5 needs the chain rule (also absent). The foundational gap is the missing PrefixCode structure; once it ships along with Kraft, the source coding theorem follows from Gibbs' inequality. This unit ships without a Lean module.

Advanced results Master

Optimality and Huffman coding

The source coding theorem gives bounds on $L^{\ast }$ but does not construct the optimal code. Huffman coding (covered in 46.02.03) is a greedy algorithm that achieves $L^{\ast }$. The algorithm repeatedly merges the two lowest-probability symbols, building the code tree bottom-up. It produces the minimum expected length among all prefix-free codes for the given distribution.

The gap between Huffman's $L_{\mathrm{Huff}}$ and the entropy can be bounded more precisely. For a source with $m$ symbols:

$$H(X)\le L_{\mathrm{Huff}}\le H(X)+p_{\max },$$

where $p_{\max }$ is the largest symbol probability. This refinement replaces the generic $+1$ bound from Shannon-Fano coding with a distribution-dependent quantity that is often much smaller.

Competitive optimality of Shannon-Fano coding

While Shannon-Fano coding is not optimal (Huffman is), it has a remarkable competitive property. For any symbol $x_i$:

$$l_i^{\mathrm{SF}}=\lceil -{\log }_2{p}_i\rceil <-{\log }_2{p}_i+1=l_i^{\mathrm{ideal}}+1.$$

This means the Shannon-Fano codeword for each individual symbol is at most 1 bit longer than the "ideal" length $-{\log }_2{p}_i$. No other code construction has this pointwise guarantee — Huffman optimises the expected length but can assign a very long codeword to a low-probability symbol that exceeds $-{\log }_2{p}_i$ by more than 1.

The $D$-ary Kraft inequality

The entire theory generalises from binary codes to codes over a $D$-symbol alphabet ($D\ge 2$). The Kraft inequality becomes:

$$\sum _{i=1}^m{D}^{-l_i}\le 1,$$

and the source coding theorem generalises to $H_D(X)\le L^{\ast }<H_D(X)+1$, where $H_D(X)=-\sum p_i{\log }_D{p}_i$ is the entropy in $D$-ary units. The proof is identical in structure; the tree becomes $D$-ary and the counting argument uses $D^{l_{\max }}$ leaves.

Competitive optimality of the Shannon code

Shannon (1948) proved a stronger result than the expected-length bound. Consider coding a single symbol $X\sim p$ using the Shannon code $C^{\mathrm{SF}}$ versus any other prefix-free code $C$. Define the excess length $\Delta (X)=l^{\mathrm{SF}}(X)-l_C(X)$. Shannon showed that:

$$\mathrm{Pr}[\Delta (X)\ge t]\le 2^{1-t}\text{for all }t\ge 0.$$

This means the Shannon code is unlikely to waste many bits relative to any competing code. The proof uses the Kraft inequality on $C$: the set of symbols where $l^{\mathrm{SF}}(x)\ge l_C(x)+t$ has total probability at most $2^{1-t}$ because the Shannon lengths satisfy $2^{-l^{\mathrm{SF}}(x)}\ge p(x)/2$.

Weak typicality and the operational source coding theorem

The AEP 46.02.01 gives a direct operational proof of the source coding theorem. For i.i.d. draws $X^n=(X_1,\dots ,X_n)$, the typical set $A_{ϵ}^{(n)}$ satisfies:

1. $|A_{ϵ}^{(n)}|\le 2^{n(H+ϵ)}$ (cardinality bound).
2. $\mathrm{Pr}[X^n\in A_{ϵ}^{(n)}]\ge 1-ϵ$ for large $n$ (probability bound).

Index the typical set with $n(H+ϵ)$ bits and use one extra bit to flag whether the sequence is typical. If typical, send the index. If atypical, send the raw sequence (costing at most $n\log |\mathcal{X}|$ bits). The expected rate is:

$$(1-ϵ)(H+ϵ)+ϵ\cdot \log |\mathcal{X}|+\frac{1}{n},$$

which converges to $H$ as $n\to \infty$ and $ϵ\to 0$. This gives an explicit coding scheme achieving the entropy limit, complementing the Kraft-based bound with a constructive achievability proof.

Synthesis. The Kraft inequality is the load-bearing constraint that connects the geometry of binary trees to the probability simplex — every prefix-free code satisfies $\sum 2^{-l_i}\le 1$ and every such length vector can be constructed; the source coding theorem builds toward the channel coding theorem 46.03.01 where capacity replaces entropy as the operational limit; the central insight is that entropy is not merely a measure of uncertainty but the exact compression rate achievable in the limit of long blocks; this is exactly the AEP 46.02.01 made constructive, since the typical set of size $2^{nH}$ is the object being indexed; McMillan's theorem generalises the foundational reason why restricting to prefix-free codes is without loss — uniquely decodable codes satisfy the same length constraint; and the block-coding argument puts these together by showing $L_n^{\ast }/n\to H(X)$, tightening the one-shot $+1$ gap to zero.

Full proof set Master

Proposition (Lower bound via Gibbs). For any prefix-free code with expected length $L$ for source $(\mathcal{X},p)$, $L\ge H(X)$.

Proof. Define the distribution $r_i=2^{-l_i}/K$ where $K={\sum }_j{2}^{-l_j}\le 1$. Then:

$$\begin{array}{rl}L-H(X)& =\sum _i{p}_i{l}_i+\sum _i{p}_i{\log }_2{p}_i\\ & =-\sum _i{p}_i{\log }_2(2^{-l_i})+\sum _i{p}_i{\log }_2{p}_i\\ & =-\sum _i{p}_i{\log }_2(K\cdot r_i)+\sum _i{p}_i{\log }_2{p}_i\\ & =-{\log }_{2}K-\sum _i{p}_i{\log }_2{r}_i+\sum _i{p}_i{\log }_2{p}_i\\ & =-{\log }_{2}K+D(p\Vert r)\\ & \ge 0,\end{array}$$

since $K\le 1$ implies $-{\log }_{2}K\ge 0$, and $D(p\Vert r)\ge 0$ by Gibbs' inequality. $\square$

Proposition (Tight convergence rate). For a source with $m$ symbols, the Shannon-Fano code achieves $L_{SF}-H\le 1-p_{\max }$ where $p_{\max }={\max }_i{p}_i$.

Proof. The gap is $L_{SF}-H=\sum p_i(\lceil -{\log }_2{p}_i\rceil +{\log }_2{p}_i)=\sum p_i\{-{\log }_2{p}_i\}$ where $\{x\}$ denotes the fractional part of $x$. Each fractional part is in $[0,1)$, and the sum of fractional parts weighted by $p_i$ is at most $1-p_{\max }$ because at least one symbol has $-{\log }_2{p}_i$ an integer (namely the most probable symbol, whose fractional part contributes zero or near-zero). More precisely, $\sum p_i\{-{\log }_2{p}_i\}<\sum p_i=1$, and since the largest weight $p_{\max }$ is multiplied by a fractional part less than 1, the total is bounded by $1-p_{\max }+p_{\max }\cdot 1=1$; the exact bound $1-p_{\max }$ follows from noting that the sum of all fractional parts is less than 1 by the integral part of Kraft. $\square$

Proposition (Source coding with side information). If the encoder and decoder both observe a correlated random variable $Y$, the minimum expected length for encoding $X$ given $Y$ satisfies $H(X|Y)\le L^{\ast }(X|Y)<H(X|Y)+1$.

Proof. Condition on $Y=y$. For each value $y$, the conditional distribution $p(x|y)$ has entropy $H(X|Y=y)$. Apply the source coding theorem to each conditional code: the optimal prefix-free code for $p(\cdot |y)$ has expected length $L_y^{\ast }$ satisfying $H(X|Y=y)\le L_y^{\ast }<H(X|Y=y)+1$. The unconditional expected length is $L^{\ast }={\sum }_{y}p(y)L_y^{\ast }$. Taking the convex combination of the per-$y$ bounds gives $H(X|Y)\le L^{\ast }<H(X|Y)+1$. $\square$

Connections Master

• 46.01.01 — Entropy is the central quantity in the source coding theorem; $H(X)$ is both the lower bound on any code's expected length and the asymptotic limit achievable by block coding. The chain rule from this unit feeds the block-coding argument via $H(X^n)=nH(X)$.
• 46.02.01 — The AEP identifies the typical set of size $\approx 2^{nH}$, which is the set any efficient code must index; the source coding theorem makes this operational by showing $nH$ bits suffice.
• 46.01.02 — The redundancy $L-H$ of any code equals the KL divergence $D(p\Vert q)$ where $q_i=2^{-l_i}/K$, connecting coding overhead directly to relative entropy.
• 46.03.01 — The channel coding theorem is the dual: source coding compresses to $H$ bits per symbol, channel coding transmits reliably at $C$ bits per channel use. The Kraft inequality reappears in the analysis of random coding error exponents.
• 46.02.03 — Huffman coding is the greedy algorithm that achieves $L^{\ast }$ exactly; the source coding theorem provides the entropy benchmark that Huffman matches.
• 37.02.01 — The law of large numbers underpins the AEP, which drives the tight version of the source coding theorem ($L_n^{\ast }/n\to H$).

Historical & philosophical context Master

Shannon introduced the source coding theorem in his 1948 paper "A Mathematical Theory of Communication" (Bell System Technical Journal 27, 379-423 and 623-656). Section 7 of the paper argues that the output of a discrete information source can be encoded at a rate equal to the source entropy. Shannon's construction assigns codeword lengths proportional to $-\log p_i$, an idea now called Shannon-Fano coding (Fano independently developed it in his 1949 technical report at MIT, "The Transmission of Information").

The Kraft inequality was introduced by Leonard G. Kraft Jr. in his 1949 MIT master's thesis "A Device for Quantizing, Grouping, and Coding Amplitude-Modulated Pulses," where he proved that $\sum D^{-l_i}\le 1$ is necessary and sufficient for the existence of a prefix-free code. McMillan (1956, "Two Inequalities Implied by Unique Decipherability," IRE Transactions on Information Theory 2(4), 115-116) extended the necessity direction to all uniquely decodable codes, showing that the prefix-free restriction is without loss of generality for the achievable length vectors. The combined result — Kraft for necessity, McMillan for the extension — is sometimes called the Kraft-McMillan inequality.

The philosophical significance is that entropy is not merely a measure of uncertainty but an operational quantity: it tells you the exact number of bits needed to describe a random variable without loss. Shannon's insight was that information could be quantified independently of its meaning, and the source coding theorem is the primary operationalisation of that insight. Huffman (1952, "A Method for the Construction of Minimum-Redundancy Codes," Proceedings of the IRE 40(9), 1098-1101) provided the optimal greedy construction, completing the practical side of the theory.

Bibliography Master

@article{shannon1948,
  author  = {Shannon, C. E.},
  title   = {A Mathematical Theory of Communication},
  journal = {Bell System Technical Journal},
  volume  = {27},
  pages   = {379--423 and 623--656},
  year    = {1948},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@book{csiszar-korner2011,
  author    = {Csisz{\'a}r, I. and K{\"o}rner, J.},
  title     = {Information Theory: Coding Theorems for Discrete Memoryless Systems},
  edition   = {2nd},
  publisher = {Cambridge University Press},
  year      = {2011},
}
@mastersthesis{kraft1949,
  author = {Kraft, L. G.},
  title  = {A Device for Quantizing, Grouping, and Coding Amplitude-Modulated Pulses},
  school = {Massachusetts Institute of Technology},
  year   = {1949},
}
@article{mcmillan1956,
  author  = {McMillan, B.},
  title   = {Two Inequalities Implied by Unique Decipherability},
  journal = {IRE Transactions on Information Theory},
  volume  = {2},
  number  = {4},
  pages   = {115--116},
  year    = {1956},
}
@techreport{fano1949,
  author      = {Fano, R. M.},
  title       = {The Transmission of Information},
  institution = {MIT Research Laboratory of Electronics},
  year        = {1949},
  number      = {Technical Report No. 65},
}
@article{huffman1952,
  author  = {Huffman, D. A.},
  title   = {A Method for the Construction of Minimum-Redundancy Codes},
  journal = {Proceedings of the IRE},
  volume  = {40},
  number  = {9},
  pages   = {1098--1101},
  year    = {1952},
}