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

Dror Baron
, Andrew C. Singer

Office of the Dean of the College of Engineering and Applied Sciences

IEEE
University of Illinois at Urbana-Champaign

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

2 Scopus citations

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
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

Access to Document

10.1109/18.959291

Cite this

@article{9777cd7bb9f847d7bf4b5f23a457f003,

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",

volume = "47",

pages = "3088--3090",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

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 - https://www.scopus.com/pages/publications/0035504161

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

Access to Document

Other files and links

Fingerprint

Cite this