On the cost of worst case coding length constraints

Dror Baron; Andrew C. Singer

doi:10.1109/18.959291

On the cost of worst case coding length constraints

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

Abstract

We investigate the redundancy that arises from adding a worst case length constraint to uniquely decodable fixed-to-variable codes over achievable Huffman codes. This is in contrast to the traditional metric of the redundancy over the entropy. We show that the cost for adding constraints on the worst case coding length is small, and that the resulting bound is related to the Fibonacci numbers.

Original language	English (US)
Pages (from-to)	3088-3090
Number of pages	3
Journal	IEEE Transactions on Information Theory
Volume	47
Issue number	7
DOIs	https://doi.org/10.1109/18.959291
State	Published - Nov 2001

Keywords

Data compression
Fibonacci numbers
Huffman coding
Redundancy
Source coding
Uniquely decodable

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Library and Information Sciences

Online availability

10.1109/18.959291

Library availability

Discover UIUC Full Text

Cite this

@article{62d2678562e448acbeff336b7d448fc4,

title = "On the cost of worst case coding length constraints",

abstract = "We investigate the redundancy that arises from adding a worst case length constraint to uniquely decodable fixed-to-variable codes over achievable Huffman codes. This is in contrast to the traditional metric of the redundancy over the entropy. We show that the cost for adding constraints on the worst case coding length is small, and that the resulting bound is related to the Fibonacci numbers.",

keywords = "Data compression, Fibonacci numbers, Huffman coding, Redundancy, Source coding, Uniquely decodable",

author = "Dror Baron and Singer, {Andrew C.}",

year = "2001",

month = nov,

doi = "10.1109/18.959291",

language = "English (US)",

volume = "47",

pages = "3088--3090",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

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

number = "7",

}

TY - JOUR

T1 - On the cost of worst case coding length constraints

AU - Baron, Dror

AU - Singer, Andrew C.

PY - 2001/11

Y1 - 2001/11

N2 - We investigate the redundancy that arises from adding a worst case length constraint to uniquely decodable fixed-to-variable codes over achievable Huffman codes. This is in contrast to the traditional metric of the redundancy over the entropy. We show that the cost for adding constraints on the worst case coding length is small, and that the resulting bound is related to the Fibonacci numbers.

AB - We investigate the redundancy that arises from adding a worst case length constraint to uniquely decodable fixed-to-variable codes over achievable Huffman codes. This is in contrast to the traditional metric of the redundancy over the entropy. We show that the cost for adding constraints on the worst case coding length is small, and that the resulting bound is related to the Fibonacci numbers.

KW - Data compression

KW - Fibonacci numbers

KW - Huffman coding

KW - Redundancy

KW - Source coding

KW - Uniquely decodable

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

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

U2 - 10.1109/18.959291

DO - 10.1109/18.959291

M3 - Article

AN - SCOPUS:0035504161

SN - 0018-9448

VL - 47

SP - 3088

EP - 3090

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 7

ER -

On the cost of worst case coding length constraints

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this