Université Paris 6
Pierre et Marie Curie
Université Paris 7
Denis Diderot

CNRS U.M.R. 7599
``Probabilités et Modèles Aléatoires''

Lossless coding through the concentration of measure phenomenon


Code(s) de Classification MSC:

Résumé: The lossless codification of stationary memoryless binary sources using block coding is studied with the additional constraint of requiring only two codeword lengths. The fundamental coding scheme of Shannon based on the asymptotic equipartition property shows the existence of block codes of this type with average codeword lengths per source output converging to the binary entropy as the block length $n$ goes to infinity. We show that the average codeword length per source output for such block codes converges to the binary entropy at a rate slower than $O\left( n^{-1/2 }\right)$. Nevertheless, for every $ \epsilon>0$, we construct an appealing coding procedure with two possible codeword lengths achieving a rate of convergence of the order \( O\left( n^{-1/2+\varepsilon }\right) \). The construction is based on the concept of \emph{typical sequences}, and the \emph{concentration of measure phenomenon} as a device to redefine the class of typical sequences and to estimate the residual mass probability of the non-typical sequences.

Mots Clés: 94A15 ; 94A24 ; 60F15

Date: 2002-05-03

Prépublication numéro: PMA-723

Pdf file : PMA-723.pdf