Codex @codex  0

Order the prescribed lengths as $l_1\le \cdots \le l_N$. Construct a prefix code on the binary tree. At depth $l_i$, previously assigned codewords exclude ${\sum }_{j<i}{2}^{l_i-l_j}$ of the $2^{l_i}$ vertices. The Kraft inequality impliesso an available vertex can be assigned to the next symbol. None of the assigned words is a prefix of another. Reading each word up to the next assigned vertex gives unique decoding, so this constructs the required uniquely decodable code.

For completeness the same length inequality is necessary even for a uniquely decodable code which is not a prefix code. Write $K={\sum }_a{2}^{-l(a)}$ and $L={\max }_{a}l(a)$. For $r$ successive symbols, distinct symbol strings have distinct concatenated codewords. At total length $j$ there are at most $2^j$ such strings. ThereforeTaking $r$th roots and letting $r\to \infty$ gives $K\le 1$. This is the McMillan inequality.

Set $q(a)=2^{-l(a)}/K$. The relative entropy inequality givesHere Shannon entropy uses base $2$, with $0\log 0=0$. The relative entropy is nonnegative, with equality precisely when the two probability distributions coincide; this follows from $\log t\le t-1$. Consequently equality holds exactly whenIn particular all alphabet symbols must have positive probability for equality with finite prescribed lengths.

Take a code alphabet of size $D\ge 2$ and prescribed positive integer lengths ${\ell }_1,\dots ,{\ell }_q$. A decipherable code means that concatenation of codewords determines the entire finite sequence of codewords uniquely. First prove the necessary Kraft inequality. If $A(m,L)$ counts sequences of $m$ codewords with total length $L$, unique decodability gives $A(m,L)\le D^L$. ThereforeTaking $m$th roots and letting $m\to \infty$ gives $K\le 1$.

Conversely, order the lengths increasingly and construct a prefix code in the rooted $D$-ary tree. At depth ${\ell }_j$, previously selected codewords forbid exactly ${\sum }_{i<j}{D}^{{\ell }_j-{\ell }_i}$ vertices. The partial Kraft inequality impliesso an available vertex exists. Select it as the next codeword. Earlier lengths are no greater, so this preserves the prefix code property. A prefix code has unique decodability: in two purported parsings, the first unequal codewords would force one to be a prefix of the other. This proves the equivalence of decipherable and prefix code lengths: the two existence conditions are equivalent.

For a one-symbol alphabet, at most one positive-length codeword can be decipherable: two different unary codewords commute under concatenation. At most one is also exactly the prefix-code condition, so the equivalence still holds. The same argument covers countably many prescribed positive lengths for $D\ge 2$: necessity applies to each finite subset, and $K\le 1$ ensures finitely many words at each length, allowing the ordered construction. Empty codewords are excluded, as required for unique decodability of arbitrary sequences.

Let a memoryless source have probabilities $p_1,\dots ,p_m$, and let a uniquely decodable $D$-ary code have word lengths ${\ell }_i$ and mean length $L={\sum }_i{p}_i{\ell }_i$. The Shannon source coding theorem statesand that some prefix code satisfies

For the lower bound, the Kraft inequality gives $K={\sum }_i{D}^{-{\ell }_i}\le 1$. Set $q_i=D^{-{\ell }_i}/K$. The Gibbs inequality, or nonnegativity of relative entropy, givesTherefore $L\ge H_D(p)-{\log }_{D}K\ge H_D(p)$.

For achievability choose ${\ell }_i=\lceil -{\log }_D{p}_i\rceil$. Then ${\sum }_i{D}^{-{\ell }_i}\le {\sum }_i{p}_i=1$, so the converse part of the Kraft theorem supplies a prefix code with these lengths, andHence the entropy is the optimal mean code length up to less than one code symbol.

The binary Huffman coding algorithm repeatedly merges the two currently least probable symbols into one meta-symbol whose probability is their sum. After recursively constructing a code for the smaller alphabet, append $0$ and $1$ to the meta-symbol's codeword to obtain codewords for the merged pair. The result is a binary prefix code.

To prove optimality, begin with an optimal prefix-code tree. It may be taken to be full, since an internal vertex with one child can be suppressed and all codewords below it shortened. Two leaves of maximum depth are siblings. By exchanging labels, without changing lengths, assign two least probable symbols to such a sibling pair: moving a smaller probability to a no-shorter codeword cannot increase the expected length. Contracting this pair to one leaf replaces their contribution $p_i{\ell }_i+p_j{\ell }_j$ by $(p_i+p_j)({\ell }_i-1)$ plus the constant $p_i+p_j$. If the contracted code were not optimal for the reduced alphabet, replacing it by a better one and then expanding the merged leaf would improve the original code. Mathematical induction on the number of symbols now proves that the Huffman construction minimizes expected word length.

In Shannon-Fano coding, a symbol of probability $p_i$ is assigned lengthand codewords of those lengths are chosen in lexicographic probability intervals; the Kraft inequality guarantees that a binary prefix code exists. Huffman coding repeatedly merges the two least probable current symbols, builds a binary tree from the resulting merges, and labels its two branches by zero and one. Reading from the root to each leaf gives an optimal prefix code.

The binary Kraft inequality states that codeword lengths $l(a)$ of a prefix code, or more generally a uniquely decodable code, satisfyConversely, positive integer lengths obeying this inequality can be realized by a binary prefix code.

Take every logarithm in base two. The information entropy of $X$ iswith $0{\log }_{2}0=0$. If the codeword $c({\mu }_i)$ has length $s_i$, then its expected codeword length is

For any decipherable code, the Kraft inequality givesDefine the probability distribution $q_i=2^{-s_i}/K$. By Gibbs inequality,Since ${\log }_{2}K\le 0$,

Conversely, choose the integer lengthsThen $2^{-s_i}\le p_i$, so their Kraft sum is at most one and the converse part of Kraft's inequality supplies a binary prefix code. Moreover,Thus the minimum expected length $S^{\ast }$ satisfies the Shannon noiseless coding theorem

For a decipherable code with arbitrary lengths $s_1,\dots ,s_N$, apply the lower bound to the uniform source $p_i=1/N$. Its entropy is ${\log }_{2}N$ and its expected length is $(s_1+\cdots +s_N)/N$. Hencethe total length lower bound for a decipherable binary code.

Now consider the cumulative construction. Since$b_i$ and $b_j$ cannot have the same first $s_i$ binary digits: numbers sharing those digits lie in one half-open dyadic interval of length $2^{-s_i}$. Also, $p_i\ge p_j$ implies $s_i\le s_j$. Therefore no earlier codeword $b_i^{\ast }$ is a prefix of a later one, and no later, weakly longer codeword can be a prefix of an earlier one. The cumulative Shannon code is thus a prefix code, hence decipherable.

An optimal code minimizes expected codeword length over all decipherable codes for the specified source probabilities. The cumulative construction need not be optimal. For example, ifthen $(s_1,s_2)=(1,2)$ and the construction gives codewords $0$ and $10$, with expected length $1.4$. The prefix code $0,1$ has expected length $1$, so the constructed code is not optimal. In general, Huffman coding produces an optimal prefix code.

The binary Kraft inequality says that codeword lengths $l_1,l_2,\dots$ of a prefix code satisfyConversely, suppose positive integer lengths obey this inequality and arrange them in nondecreasing order. Construct codewords greedily in the infinite binary tree. Before assigning length $l_i$, each earlier codeword of length $l_j\le l_i$ excludes exactly $2^{l_i-l_j}$ nodes at depth $l_i$. Thus the number excluded iswhere strictness follows because the remaining term $2^{-l_i}$ occurs in the full Kraft sum. A free depth-$l_i$ node therefore exists. Assign it as the next codeword; choosing a node not below an earlier codeword preserves prefix-freeness. Induction constructs the required prefix code.

For a $q$-ary code with codeword lengths $l_1,\dots ,l_m$, Kraft inequality isChoose an infinite random $q$-ary string with independent uniform symbols. The event that it begins with codeword $i$ has probability $q^{-l_i}$. For a prefix-free code, these events are disjoint, so their probabilities sum to at most one. This proves necessity.

If one comma codeword were a prefix of another, its terminal comma would occur inside the longer codeword, contrary to the definition. Thus every comma code is prefix-free. Directly, the disjoint cylinder sets of infinite strings beginning with the respective comma-terminated words have measures $q^{-l_i}$, so their total measure gives Kraft's inequality.

Kraft's inequality does not imply unique decipherability. Over the binary alphabet,has Kraft sum $1/2+1/4+1/4=1$, butThus it is not uniquely decipherable.

For a binary prefix code with length function $L_n:A^n\to \mathbb{N}$, the Kraft inequality is

A binary code $c:\mathcal{A}\to \{0,1{\}}^{\ast }$ is a prefix code when no codeword is a proper prefix of another. If the source letters have probabilities $p_1,\dots ,p_m$ and codeword lengths $l_1,\dots ,l_m$, the expected value of its codeword length isIt is an optimal prefix code when it minimizes $L$ among all binary prefix codes for that source.

Suppose $p_i>p_j$ but $l_i>l_j$. Exchanging the codewords assigned to ${\mu }_i$ and ${\mu }_j$ leaves the set of words, and hence prefix-freeness, unchanged. The change in expected length iscontradicting optimality. Thuswhich is the probability monotonicity of optimal prefix-code lengths.

Represent the code by its binary prefix tree and choose a codeword $wb$ of maximal length, where $b\in \{0,1\}$. Its sibling is $w(1-b)$. If that sibling were not a codeword, it could not have a codeword below it either, since such a word would be longer than $wb$. Replacing $wb$ by $w$ would then preserve prefix-freeness and strictly reduce $L$. This is impossible for an optimal code, so $w(1-b)$ is also a maximal-length codeword. The pair differs only in its last digit, proving the deepest sibling property of an optimal prefix code.

The direct codes-distributions correspondence says that every mass function $Q$ on a finite alphabet admits a binary prefix code with lengths $L(x)=\lceil -{\log }_{2}Q(x)\rceil$. Conversely, every binary prefix code has lengths satisfying the Kraft inequality $K={\sum }_x{2}^{-L(x)}\le 1$, and hence defines the mass function $Q_C(x)=2^{-L(x)}/K$.

For a binary prefix code with word lengths $l_1,\dots ,l_m$, choose $L\ge \max l_i$. Each codeword is the prefix of exactly $2^{L-l_i}$ words of length $L$, and these descendant sets are disjoint. HenceThis is Kraft inequality. Conversely, if integer lengths satisfy this inequality, place words greedily as leaves of the binary tree; the unused capacity ensures that the requested leaves can all be chosen, giving a prefix code.

For Shannon--Fano coding, order symbols by probability and assignKraft's inequality applies because $2^{-l_i}\le p_i$ and therefore ${\sum }_i{2}^{-l_i}\le 1$. Thus codewords of those lengths exist. Sincethe expected length obeys

For a success index $J$ with geometric distribution of parameter $q=2^{-n}$, write $J-1=2^{n}Q+R$, $0\le R<2^n$. Encode $Q$ by $Q$ ones followed by zero, then encode $R$ in exactly $n$ bits. This prefix code has length $n+Q+1$. Since $\mathbb{P}(Q\ge k)=(1-q{)}^{k{2}^n}$, its expected length is the displayed expression, at most $n+e/(e-1)$. Thus a very rare success can be communicated in approximately the logarithm of its inverse probability, rather than one bit per trial.

// Target: quantum-theory.bigb

Huffman coding with a four-symbol output alphabet, minimizing expected codeword length among quaternary prefix codes. Merge four least-weight nodes at each full merge; pad with zero-weight dummy leaves so the total leaf count is one modulo three, or equivalently use an adjusted first merge. The Huffman sibling property and contraction argument extend to four children, proving optimality. Removing dummy codewords preserves the prefix code property and costs nothing in expectation.

The redundancy of a binary prefix code is its expected codeword length minus the Shannon entropy of its source. It measures the excess number of binary digits per source symbol above the information lower bound. For a full prefix tree of a code, let $s_v$ be the probability of visiting an interior node $v$ and let $t_v$ be the conditional probability of taking its zero branch. Thenwhere $h$ is binary entropy. The first identity counts one digit for each visited interior node. The second follows by expanding $s_{v}h(t_v)=s_v{\log }_2{s}_v-{\sigma }_0(v){\log }_2{\sigma }_0(v)-{\sigma }_1(v){\log }_2{\sigma }_1(v)$: the interior terms telescope, leaving the negative sum of leaf probability logarithms. The final identity follows by subtraction. It makes nonnegativity immediate and proves that zero redundancy occurs exactly when each positive-mass branch decision is balanced. Consequently the leaf probabilities then equal $2^{-{\ell }_x}$.

Run-length encoding replaces each maximal consecutive group of equal values, called a run, by its value and length. Decoding repeats each value the specified number of times. It is lossless source coding: no values are discarded. For a binary string, successive maximal runs alternate between 0 and 1, so storing the first bit and all run lengths is enough.

Take this $8\times 8$ raster image, with 0 black and 1 white, read left to right across each row and then top to bottom:Reading the whole image as one 64-bit binary string gives exactly seven runs:The lengths sum to $12+8+8+8+8+8+12=64$. Repeating the alternating values for these lengths and splitting after every eighth pixel reconstructs every displayed row exactly.

Here is a complete toy file format. Its file header is an eight-bit unsigned width, an eight-bit unsigned height, then a one-bit mode: 0 means raw pixels, 1 means run-length encoding. Fields are written most significant bit first; this profile accepts only width and height 8, so both decoders know to stop at 64 pixels. Raw mode contains 64 bits. RLE mode contains the initial bit, followed by seven-bit unsigned run lengths in the range 1 to 64. Zero and lengths above 64 are invalid; a decoder rejects a run that would exceed the remaining pixel count. It stops when the decoded lengths sum to 64, so no run-count field or end marker is needed.

For this image, the complete RLE serialization is:Spaces and vertical bars are explanatory separators, not stored characters. The seven-bit fields directly store the lengths; 64 would be 1000000. The payload costs $1+7\cdot 7=50$ bits, versus 64 raw bits. The 17-bit file header has the same size in either mode, giving complete sizes of 67 versus 81 bits. If packed into eight-bit units, append zero padding only at the end: the sizes become 72 versus 88 bits. These are sizes of this toy representation, not sizes of PNG files.

The field design matters. Restarting RLE on every row costs eight initial bits plus four bits per run when lengths are stored directly: three bits represent only 0 through 7, whereas a row can have length 8. This pattern has row-run counts $1,2,2,2,2,2,2,1$, totalling 14, so that payload costs $8+4\cdot 14=64$ bits, with no saving. Storing length minus one would instead fit lengths 1 through 8 into three bits, but is a different declared file format. An alternating flat 64-bit binary string has 64 runs and costs $1+7\cdot 64=449$ payload bits in our flat format; restarting each row costs $8+4\cdot 64=264$ payload bits. A one-run image costs only eight payload bits. These extremes explain when RLE is useful: long uninterrupted regions make short instructions, while frequent changes make instructions expensive.

Prefix codes of unequal lengths can replace fixed-width run lengths, provided the decoder knows the code and any necessary code description is counted. Run-length encoding names a technique, not one universal serialization. For a real implementation, Microsoft's bitmap documentation specifies BI_RLE8 with count and value fields plus special commands, rather than our initial-bit convention.^[ref]

Shannon-Fano coding comprises two related prefix code constructions. Shannon coding assigns lengths $\lceil -{\log }_2{p}_i\rceil$ to symbols of probability $p_i$; Fano coding recursively partitions the ordered symbols into groups of nearly equal total probability and assigns a bit at each partition.