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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publication1990 IEEE International Symposium on Information Theory (ISIT 1990)
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
Number of pages1
Publication statusPublished - 1 Dec 1990
Event1990 IEEE International Symposium on Information Theory (ISIT 1990) - San Diego, United States
Duration: 14 Jan 199019 Jan 1990

Conference

Conference1990 IEEE International Symposium on Information Theory (ISIT 1990)
Abbreviated titleISIT 1990
CountryUnited States
CitySan Diego
Period14/01/9019/01/90

Fingerprint

Redundancy
Entropy

Cite this

Tjalkens, T. J., & Willems, F. M. J. (1990). Asymptotic optimality of a universal variable-to-fixed length binary source coding algorithm. In 1990 IEEE International Symposium on Information Theory (ISIT 1990) Piscataway: Institute of Electrical and Electronics Engineers.
Tjalkens, Tjalling J. ; Willems, Frans M.J. / Asymptotic optimality of a universal variable-to-fixed length binary source coding algorithm. 1990 IEEE International Symposium on Information Theory (ISIT 1990). Piscataway : Institute of Electrical and Electronics Engineers, 1990.
@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 = "12",
day = "1",
language = "English",
booktitle = "1990 IEEE International Symposium on Information Theory (ISIT 1990)",
publisher = "Institute of Electrical and Electronics Engineers",
address = "United States",

}

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, 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 proceedingConference contributionAcademicpeer-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

AN - SCOPUS:0025590835

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

PB - Institute of Electrical and Electronics Engineers

CY - Piscataway

ER -

Tjalkens TJ, Willems FMJ. Asymptotic optimality of a universal variable-to-fixed length binary source coding algorithm. In 1990 IEEE International Symposium on Information Theory (ISIT 1990). Piscataway: Institute of Electrical and Electronics Engineers. 1990