= Solution
The <redundancy of a binary prefix code>[redundancy] is $R=\bar\ell-H(X)$, measured in bits per source symbol. Write $s_v=\sigma_0(v)+\sigma_1(v)$ for the total mass passing through interior node $v$. Counting each <codeword>[codeword]'s length as one for each interior node its route visits gives
$$
\bar\ell=\sum_xp_x\sum_{v\text{ on its route}}1=\sum_{v\in N}s_v.
$$
The <Shannon entropy>[entropy] can be split into the conditional binary decisions along that route. Algebraically each node contributes
$$
s_v h(\sigma_0(v)/s_v)=s_v\log_2s_v-\sigma_0(v)\log_2\sigma_0(v)-\sigma_1(v)\log_2\sigma_1(v).
$$
Summing telescopes: each non-root interior mass appears once positively as a parent and once negatively as a child. The root term is $1\log_21=0$ and the remaining leaf terms sum to $-\sum_xp_x\log_2p_x=H(X)$. Hence
$$
H(X)=\sum_{v\in N}s_vh(\sigma_0(v)/s_v).
$$
Subtracting this identity from the expected-length identity proves
$$
\boxed{R=\sum_{v\in N}(\sigma_0(v)+\sigma_1(v))\left[1-h\!\left(\frac{\sigma_0(v)}{\sigma_0(v)+\sigma_1(v)}\right)\right]}.
$$
Thus <redundancy of a binary prefix code>[redundancy] is the sum of the probability-weighted imbalances of the binary branch decisions. Nodes with no mass contribute zero by <continuity>. The formula holds for every full prefix tree, even without optimality.
Back to article page
