IRIS Institutional Research Information System - OPENBS Open Archive UniBS
il nuovo catalogo dedicato alla raccolta e alla disseminazione della produzione scientifica dell'Università degli Studi di
Brescia, denominato OPENBS. E' possibile cercare pubblicazioni in OPENBS:
- per parola chiave, utilizzando la barra di ricerca situata in alto
- per filtro di ricerca (Autore, Titolo, Riviste), utilizzando il pulsante Sfoglia
- specificando criteri di ricerca con possibilità di aggiungere gradualmente più filtri (Autore, Data, Tipologia,..) che
perfezionino i risultati, utilizzando la finestra Ricerca - per elemento di filtro di ricerca (e.g. per un elemento di Tipologia: contributo su rivista) nella sezione Scopri
EnglishIn 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 |
http://hdl.handle.net/11379/28559
Copyright © 2021