A Lower Bound on the Expected Length of One-to-One Codes

Alon Orlitsky; Noga Alon

doi:10.1109/18.333891

A Lower Bound on the Expected Length of One-to-One Codes

Alon Orlitsky
, Noga Alon

Research output: Contribution to journal › Article › peer-review

37 Scopus citations

Abstract

We show that the expected length of any one-to-one encod- ing of a discrete random variable X is at least H(X) — log (H(X) + 1) — log e and that this bound is asymptotically achievable.

Original language	English (US)
Pages (from-to)	1670-1672
Number of pages	3
Journal	IEEE Transactions on Information Theory
Volume	40
Issue number	5
DOIs	https://doi.org/10.1109/18.333891
State	Published - Sep 1994
Externally published	Yes

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Library and Information Sciences

Keywords

Source coding
nonprefix codes
one-to-one codes

Access to Document

10.1109/18.333891

Cite this

@article{97cca84e8fe243e691f0dc7e7b83b3f1,

title = "A Lower Bound on the Expected Length of One-to-One Codes",

abstract = "We show that the expected length of any one-to-one encod- ing of a discrete random variable X is at least H(X) — log (H(X) + 1) — log e and that this bound is asymptotically achievable.",

keywords = "Source coding, nonprefix codes, one-to-one codes",

author = "Alon Orlitsky and Noga Alon",

year = "1994",

month = sep,

doi = "10.1109/18.333891",

language = "English (US)",

volume = "40",

pages = "1670--1672",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

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

number = "5",

}

TY - JOUR

T1 - A Lower Bound on the Expected Length of One-to-One Codes

AU - Orlitsky, Alon

AU - Alon, Noga

PY - 1994/9

Y1 - 1994/9

N2 - We show that the expected length of any one-to-one encod- ing of a discrete random variable X is at least H(X) — log (H(X) + 1) — log e and that this bound is asymptotically achievable.

AB - We show that the expected length of any one-to-one encod- ing of a discrete random variable X is at least H(X) — log (H(X) + 1) — log e and that this bound is asymptotically achievable.

KW - Source coding

KW - nonprefix codes

KW - one-to-one codes

UR - https://www.scopus.com/pages/publications/0028514167

UR - https://www.scopus.com/pages/publications/0028514167#tab=citedBy

U2 - 10.1109/18.333891

DO - 10.1109/18.333891

M3 - Article

AN - SCOPUS:0028514167

SN - 0018-9448

VL - 40

SP - 1670

EP - 1672

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 5

ER -

A Lower Bound on the Expected Length of One-to-One Codes

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this