Lower Bounds on the Redundancy of Huffman Codes with Known and Unknown Probabilities
Blanes, Ian (Universitat Autònoma de Barcelona)
Hernández-Cabronero, Miguel (Universitat Autònoma de Barcelona)
Serra-Sagristà, Joan (Universitat Autònoma de Barcelona)
Marcellin, Michael W. (University of Arizona. Department of Electrical and Computer Engineering)

Fecha:	2019
Resumen:	In this paper, we provide a method to obtain tight lower bounds on the minimum redundancy achievable by a Huffman code when the probability distribution underlying an alphabet is only partially known. In particular, we address the case where the occurrence probabilities are unknown for some of the symbols in an alphabet. Bounds can be obtained for alphabets of a given size, for alphabets of up to a given size, and alphabets of arbitrary size. The method operates on a computer algebra system, yielding closed-form numbers for all results. Finally, we show the potential of the proposed method to shed some light on the structure of the minimum redundancy achievable by the Huffman code.
Ayudas:	Ministerio de Economía y Competitividad TIN2015-71126-R Agencia Estatal de Investigación RTI2018-095287-B-I00 Generalitat de Catalunya 2014/SGR-691 Generalitat de Catalunya 2017/SGR-463
Derechos:	Aquest document està subjecte a una llicència d'ús Creative Commons. Es permet la reproducció total o parcial, la distribució, la comunicació pública de l'obra i la creació d'obres derivades, fins i tot amb finalitats comercials, sempre i quan es reconegui l'autoria de l'obra original.
Lengua:	Anglès
Documento:	Article ; recerca ; Versió publicada
Materia:	Huffman code ; Redundancy ; Lower bounds
Publicado en:	IEEE Access, Vol. 7 (July 2019) , p. 115857-115870, ISSN 2169-3536

DOI: 10.1109/ACCESS.2019.2932206

14 p, 9.0 MB

El registro aparece en las colecciones:
Documentos de investigación > Documentos de los grupos de investigación de la UAB > Centros y grupos de investigación (producción científica) > Ingeniería > Group on Interactive Coding of Images (GICI)
Artículos > Artículos de investigación
Artículos > Artículos publicados