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, Marco
Methodology
;
LEONARDI, Riccardo
Supervision
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 in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11379/28559
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact