Asymptotic optimality of a universal variable-to-fixed length binary source coding algorithm

Tjalling J. Tjalkens; Frans M.J. Willems

Asymptotic optimality of a universal variable-to-fixed length binary source coding algorithm

Tjalling J. Tjalkens, Frans M.J. Willems

Signal Processing Systems

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

Summary form only given. The asymptotic performance of the modified Lawrence algorithm, a universal binary variable-to-fixed-length source coding algorithm has been investigated. For M (the segment set cardinality) large enough, it has been shown that the rate R(p) as a function of the source parameter p satisfies R(p) ≤ h(p)(1 + (log log M)/(2 log M)) for 0 < p < 1, where h(p) is the binary entropy function. It has also been proved that there exist no codes that have a better asymptotic performance, thereby establishing the asymptotic optimality of the modified Lawrence code. The asymptotic bounds show that universal variable-to-fixed-length codes can have a significantly lower redundancy than universal fixed-to-variable-length codes with the same number of code words.

Original language	English
Title of host publication	1990 IEEE International Symposium on Information Theory (ISIT 1990)
Place of Publication	Piscataway
Publisher	Institute of Electrical and Electronics Engineers
Number of pages	1
Publication status	Published - 1 Dec 1990
Event	1990 IEEE International Symposium on Information Theory, ISIT 1990 - San Diego, United States Duration: 14 Jan 1990 → 19 Jan 1990

Conference

Conference	1990 IEEE International Symposium on Information Theory, ISIT 1990
Abbreviated title	ISIT 1990
Country/Territory	United States
City	San Diego
Period	14/01/90 → 19/01/90

Cite this

@inproceedings{da7b7197bf704899a89ad92339c0e6e7,

title = "Asymptotic optimality of a universal variable-to-fixed length binary source coding algorithm",

abstract = "Summary form only given. The asymptotic performance of the modified Lawrence algorithm, a universal binary variable-to-fixed-length source coding algorithm has been investigated. For M (the segment set cardinality) large enough, it has been shown that the rate R(p) as a function of the source parameter p satisfies R(p) ≤ h(p)(1 + (log log M)/(2 log M)) for 0 < p < 1, where h(p) is the binary entropy function. It has also been proved that there exist no codes that have a better asymptotic performance, thereby establishing the asymptotic optimality of the modified Lawrence code. The asymptotic bounds show that universal variable-to-fixed-length codes can have a significantly lower redundancy than universal fixed-to-variable-length codes with the same number of code words.",

author = "Tjalkens, {Tjalling J.} and Willems, {Frans M.J.}",

year = "1990",

month = dec,

day = "1",

language = "English",

booktitle = "1990 IEEE International Symposium on Information Theory (ISIT 1990)",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

note = "1990 IEEE International Symposium on Information Theory, ISIT 1990, ISIT 1990 ; Conference date: 14-01-1990 Through 19-01-1990",

}

Tjalkens, TJ & Willems, FMJ 1990, Asymptotic optimality of a universal variable-to-fixed length binary source coding algorithm. in 1990 IEEE International Symposium on Information Theory (ISIT 1990). Institute of Electrical and Electronics Engineers, Piscataway, 1990 IEEE International Symposium on Information Theory, ISIT 1990, San Diego, California, United States, 14/01/90.

Asymptotic optimality of a universal variable-to-fixed length binary source coding algorithm. / Tjalkens, Tjalling J.; Willems, Frans M.J.
1990 IEEE International Symposium on Information Theory (ISIT 1990). Piscataway: Institute of Electrical and Electronics Engineers, 1990.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Asymptotic optimality of a universal variable-to-fixed length binary source coding algorithm

AU - Tjalkens, Tjalling J.

AU - Willems, Frans M.J.

PY - 1990/12/1

Y1 - 1990/12/1

N2 - Summary form only given. The asymptotic performance of the modified Lawrence algorithm, a universal binary variable-to-fixed-length source coding algorithm has been investigated. For M (the segment set cardinality) large enough, it has been shown that the rate R(p) as a function of the source parameter p satisfies R(p) ≤ h(p)(1 + (log log M)/(2 log M)) for 0 < p < 1, where h(p) is the binary entropy function. It has also been proved that there exist no codes that have a better asymptotic performance, thereby establishing the asymptotic optimality of the modified Lawrence code. The asymptotic bounds show that universal variable-to-fixed-length codes can have a significantly lower redundancy than universal fixed-to-variable-length codes with the same number of code words.

AB - Summary form only given. The asymptotic performance of the modified Lawrence algorithm, a universal binary variable-to-fixed-length source coding algorithm has been investigated. For M (the segment set cardinality) large enough, it has been shown that the rate R(p) as a function of the source parameter p satisfies R(p) ≤ h(p)(1 + (log log M)/(2 log M)) for 0 < p < 1, where h(p) is the binary entropy function. It has also been proved that there exist no codes that have a better asymptotic performance, thereby establishing the asymptotic optimality of the modified Lawrence code. The asymptotic bounds show that universal variable-to-fixed-length codes can have a significantly lower redundancy than universal fixed-to-variable-length codes with the same number of code words.

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

M3 - Conference contribution

BT - 1990 IEEE International Symposium on Information Theory (ISIT 1990)

PB - Institute of Electrical and Electronics Engineers

CY - Piscataway

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

Y2 - 14 January 1990 through 19 January 1990

ER -

Asymptotic optimality of a universal variable-to-fixed length binary source coding algorithm

Abstract

Conference

Other files and links

Fingerprint

Cite this