A rigorous performance analysis of Fano coding is presented, providing
an upper bound on the average codeword length of binary and ternary
Fano codes for an arbitrary discrete memoryless source. The
performance bound is slightly better than Shannon's well-known bound
for Shannon coding.

As a by-product a novel general lower bound on Shannon entropy is
derived that might be of interest also in a different context. This
bound is expressed with the help of variational distance and provides
a special case of a reverse Pinsker inequality.


Entropy lower bound, Fano coding, reverse Pinsker inequality, Shannon
entropy, variational distance.

-||-   _|_ _|_     /    __|__   Stefan M. Moser
[-]     --__|__   /__\    /__   Senior Researcher & Lecturer, ETH Zurich, Switzerland
_|_     -- --|-    _     /  /   Adj. Professor, National Chiao Tung University (NCTU), Taiwan
/ \     []  \|    |_|   / \/    Web: http://moser-isi.ethz.ch/

Last modified: Thu Apr 9 10:25:56 UTC+8 2015