Redundancy of a binary prefix code ($R=\bar{\ell }-H(X)$)

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}$.