= Redundancy of a binary prefix code
{title2=$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. Then
$$
\bar\ell=\sum_v s_v,\qquad H(X)=\sum_vs_vh(t_v),\qquad R=\sum_vs_v[1-h(t_v)],
$$
where $h$ is <binary entropy>. The first identity counts one digit for each visited interior node. The second follows by expanding $s_vh(t_v)=s_v\log_2s_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}$.
Back to article page
