Performance analysis of Fano coding

Abstract

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.