Optimal Prefix Codes for Pairs of Geometrically Distributed Random Variables

DOI10.1109/TIT.2012.2236915zbMATH Open1364.94743arXiv1102.2413MaRDI QIDQ2989324FDOQ2989324

Authors: Frédérique Bassino, Julien Clément, Gadiel Seroussi, Alfredo Viola 

Publication date: 8 June 2017

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

Abstract: Optimal prefix codes are studied for pairs of independent, integer-valued symbols emitted by a source with a geometric probability distribution of parameter $q$, $0<q<1$. By encoding pairs of symbols, it is possible to reduce the redundancy penalty of symbol-by-symbol encoding, while preserving the simplicity of the encoding and decoding procedures typical of Golomb codes and their variants. It is shown that optimal codes for these so-called two-dimensional geometric distributions are emph{singular}, in the sense that a prefix code that is optimal for one value of the parameter $q$ cannot be optimal for any other value of $q$. This is in sharp contrast to the one-dimensional case, where codes are optimal for positive-length intervals of the parameter $q$. Thus, in the two-dimensional case, it is infeasible to give a compact characterization of optimal codes for all values of the parameter $q$, as was done in the one-dimensional case. Instead, optimal codes are characterized for a discrete sequence of values of $q$ that provide good coverage of the unit interval. Specifically, optimal prefix codes are described for $q=2^{-1/k}$ ($kge1$), covering the range $qge1/2$, and $q=2^{-k}$ ($k>1$), covering the range $q<1/2$. The described codes produce the expected reduction in redundancy with respect to the one-dimensional case, while maintaining low complexity coding operations.

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

Recommendations

• Optimal prefix codes for sources with two-sided geometric distributions
• On the ratio of prefix codes to all uniquely decodable codes with a given length distribution
• Algorithms and Data Structures
• Optimal random coding
• Optimal Prefix Codes And Huffman Codes
• Optimal Prefix Codes for Infinite Alphabets With Nonlinear Costs
• On the geometric constructions of optimal linear codes
• On the redundancy of optimal binary prefix-condition codes for finite and infinite sources (Corresp.)
• scientific article; zbMATH DE number 3910298
• Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes

Mathematics Subject Classification ID

Other types of codes (94B60)

Cited In (1)

• Efficient prefix coding of uncertainty spaces

This page was built for publication: Optimal Prefix Codes for Pairs of Geometrically Distributed Random Variables

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