In this paper we propose a revisitation of the topic of unique decodability and of some fundamental theorems of lossless coding. It is widely believed that, for any discrete source $X$, every ``uniquely decodable'' block code satisfies \begin{equation*} E[l(X_1 X_2 \cdots X_n)]\geq H(X_1,X_2,\ldots,X_n),\nonumber \end{equation*} where $X_1, X_2,\ldots,X_n$ are the first $n$ symbols of the source, $E[l(X_1 X_2 \cdots X_n)]$ is the expected length of the code for those symbols and $H(X_1,X_2,\ldots,X_n)$ is their joint entropy. We show that, for certain sources with memory, the above inequality only holds when a limiting definition of {``\em uniquely decodable code''} is considered. In particular, the above inequality is usually assumed to hold for any ``practical code'' due to a debatable application of McMillan's theorem to sources with memory. We thus propose a clarification of the topic, also providing an extended version of McMillan's theorem to be used for Markovian sources.
On Unique Decodability
DALAI, MarcoMethodology
;LEONARDI, RiccardoSupervision
2008-01-01
Abstract
In this paper we propose a revisitation of the topic of unique decodability and of some fundamental theorems of lossless coding. It is widely believed that, for any discrete source $X$, every ``uniquely decodable'' block code satisfies \begin{equation*} E[l(X_1 X_2 \cdots X_n)]\geq H(X_1,X_2,\ldots,X_n),\nonumber \end{equation*} where $X_1, X_2,\ldots,X_n$ are the first $n$ symbols of the source, $E[l(X_1 X_2 \cdots X_n)]$ is the expected length of the code for those symbols and $H(X_1,X_2,\ldots,X_n)$ is their joint entropy. We show that, for certain sources with memory, the above inequality only holds when a limiting definition of {``\em uniquely decodable code''} is considered. In particular, the above inequality is usually assumed to hold for any ``practical code'' due to a debatable application of McMillan's theorem to sources with memory. We thus propose a clarification of the topic, also providing an extended version of McMillan's theorem to be used for Markovian sources.File | Dimensione | Formato | |
---|---|---|---|
DL_TIT08.pdf
solo utenti autorizzati
Tipologia:
Full Text
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
146.02 kB
Formato
Adobe PDF
|
146.02 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
DL-TSIT-2008_post-print.pdf
accesso aperto
Descrizione: DL-TSIT-2008_post-print
Tipologia:
Documento in Post-print
Licenza:
Creative commons
Dimensione
133.14 kB
Formato
Adobe PDF
|
133.14 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.