On Unique Decodability

DOI10.1109/TIT.2008.929941zbMATH Open1319.94109arXiv0809.1043OpenAlexW2097916689MaRDI QIDQ3604879FDOQ3604879

Authors: Marco Dalai, Riccardo Leonardi 

Publication date: 24 February 2009

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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 E[l(X_1 X_2 ... X_n)]>= H(X_1,X_2,...,X_n), where X_1, X_2,...,X_n are the first n symbols of the source, E[l(X_1 X_2 ... X_n)] is the expected length of the code for those symbols and H(X_1,X_2,...,X_n) is their joint entropy. We show that, for certain sources with memory, the above inequality only holds when a limiting definition of "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.

Full work available at URL: https://arxiv.org/abs/0809.1043

Recommendations

• scientific article; zbMATH DE number 3883641
• On uniqueness of alphabetic decoding
• scientific article; zbMATH DE number 3264625
• A novel test for unique decipherability of codes
• Some algorithms concerning uniquely decipherable codes
• The decodability and correctability of codes
• Decipherability of codes
• On the characterization of linear uniquely decodable codes
• scientific article; zbMATH DE number 1498796

zbMATH Keywords

McMillan's theoremlossless source codingConstrained sourcesminimum expected code length

Mathematics Subject Classification ID

Source coding (94A29) Decoding (94B35)

Cited In (4)

• Applications of non-uniquely decodable codes to privacy-preserving high-entropy data representation
• Properties of unique information
• Two inequalities implied by unique decipherability
• Is Non-Unique Decoding Necessary?

This page was built for publication: On Unique Decodability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604879)