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.
Titolo: | On Unique Decodability |
Autori: | LEONARDI, Riccardo [Supervision] |
Data di pubblicazione: | 2008 |
Rivista: | |
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. |
Handle: | http://hdl.handle.net/11379/28559 |
Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
DL_TIT08.pdf | Full Text | NON PUBBLICO - Accesso privato/ristretto | Utenti riconosciuti Richiedi una copia | |
DL-TSIT-2008_post-print.pdf | DL-TSIT-2008_post-print | Documento in Post-print | ![]() | Open Access Visualizza/Apri |