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

CNRS U.M.R. 7599
| ||

``Probabilités et Modèles Aléatoires''
| ||

**Auteur(s): **

**Code(s) de Classification MSC:**

- 94A15 Information theory, general, See also {62B10}
- 94A24 Coding theorems (Shannon theory)
- 60F15 Strong theorems

**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