Non-Asymptotic Bounds for Optimal Fixed-to-Variable Lossless Compression without Prefix Constraints

Igal Sason; Sergio Verdu

doi:10.1109/ISIT.2018.8437771

Non-Asymptotic Bounds for Optimal Fixed-to-Variable Lossless Compression without Prefix Constraints

Igal Sason, Sergio Verdu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are presented as well. Lower bounds on the cumulant generating function of the codeword lengths are given, by means of the smooth Rényi entropy, for source codes that allow decoding errors.

Original language	English (US)
Title of host publication	2018 IEEE International Symposium on Information Theory, ISIT 2018
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2211-2215
Number of pages	5
ISBN (Print)	9781538647806
DOIs	https://doi.org/10.1109/ISIT.2018.8437771
State	Published - Aug 15 2018
Event	2018 IEEE International Symposium on Information Theory, ISIT 2018 - Vail, United States Duration: Jun 17 2018 → Jun 22 2018

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2018-June
ISSN (Print)	2157-8095

Other

Other	2018 IEEE International Symposium on Information Theory, ISIT 2018
Country/Territory	United States
City	Vail
Period	6/17/18 → 6/22/18

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Keywords

Cumulant generating function
Lossless source coding
Rényi information measures

Access to Document

10.1109/ISIT.2018.8437771

Cite this

Sason, I., & Verdu, S. (2018). Non-Asymptotic Bounds for Optimal Fixed-to-Variable Lossless Compression without Prefix Constraints. In 2018 IEEE International Symposium on Information Theory, ISIT 2018 (pp. 2211-2215). [8437771] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2018-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2018.8437771

@inproceedings{d9419196af604d06ada6fe2169305714,

title = "Non-Asymptotic Bounds for Optimal Fixed-to-Variable Lossless Compression without Prefix Constraints",

abstract = "Bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are presented as well. Lower bounds on the cumulant generating function of the codeword lengths are given, by means of the smooth R{\'e}nyi entropy, for source codes that allow decoding errors.",

keywords = "Cumulant generating function, Lossless source coding, R{\'e}nyi information measures",

author = "Igal Sason and Sergio Verdu",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 2018 IEEE International Symposium on Information Theory, ISIT 2018 ; Conference date: 17-06-2018 Through 22-06-2018",

year = "2018",

month = aug,

day = "15",

doi = "10.1109/ISIT.2018.8437771",

language = "English (US)",

isbn = "9781538647806",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2211--2215",

booktitle = "2018 IEEE International Symposium on Information Theory, ISIT 2018",

address = "United States",

}

Sason, I & Verdu, S 2018, Non-Asymptotic Bounds for Optimal Fixed-to-Variable Lossless Compression without Prefix Constraints. in 2018 IEEE International Symposium on Information Theory, ISIT 2018., 8437771, IEEE International Symposium on Information Theory - Proceedings, vol. 2018-June, Institute of Electrical and Electronics Engineers Inc., pp. 2211-2215, 2018 IEEE International Symposium on Information Theory, ISIT 2018, Vail, United States, 6/17/18. https://doi.org/10.1109/ISIT.2018.8437771

Non-Asymptotic Bounds for Optimal Fixed-to-Variable Lossless Compression without Prefix Constraints. / Sason, Igal; Verdu, Sergio.

2018 IEEE International Symposium on Information Theory, ISIT 2018. Institute of Electrical and Electronics Engineers Inc., 2018. p. 2211-2215 8437771 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2018-June).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Non-Asymptotic Bounds for Optimal Fixed-to-Variable Lossless Compression without Prefix Constraints

AU - Sason, Igal

AU - Verdu, Sergio

PY - 2018/8/15

Y1 - 2018/8/15

N2 - Bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are presented as well. Lower bounds on the cumulant generating function of the codeword lengths are given, by means of the smooth Rényi entropy, for source codes that allow decoding errors.

AB - Bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are presented as well. Lower bounds on the cumulant generating function of the codeword lengths are given, by means of the smooth Rényi entropy, for source codes that allow decoding errors.

KW - Cumulant generating function

KW - Lossless source coding

KW - Rényi information measures

UR - http://www.scopus.com/inward/record.url?scp=85052452889&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052452889&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2018.8437771

DO - 10.1109/ISIT.2018.8437771

M3 - Conference contribution

AN - SCOPUS:85052452889

SN - 9781538647806

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2211

EP - 2215

BT - 2018 IEEE International Symposium on Information Theory, ISIT 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2018 IEEE International Symposium on Information Theory, ISIT 2018

Y2 - 17 June 2018 through 22 June 2018

ER -

Sason I, Verdu S. Non-Asymptotic Bounds for Optimal Fixed-to-Variable Lossless Compression without Prefix Constraints. In 2018 IEEE International Symposium on Information Theory, ISIT 2018. Institute of Electrical and Electronics Engineers Inc. 2018. p. 2211-2215. 8437771. (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2018.8437771

Non-Asymptotic Bounds for Optimal Fixed-to-Variable Lossless Compression without Prefix Constraints

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this