A Caltech Library Service

Efficient Universal Noiseless Source Codes

Davisson, Lee D. and McEliece, Robert J. and Pursley, Michael B. and Wallace, Mark S. (1981) Efficient Universal Noiseless Source Codes. IEEE Transactions on Information Theory, 27 (3). pp. 269-279. ISSN 0018-9448.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Although the existence of universal noiseless variable-rate codes for the class of discrete stationary ergodic sources has previously been established, very few practical universal encoding methods are available. Efficient implementable universal source coding techniques are discussed in this paper. Results are presented on source codes for which a small value of the maximum redundancy is achieved with a relatively short block length. A constructive proof of the existence of universal noiseless codes for discrete stationary sources is first presented. The proof is shown to provide a method for obtaining efficient universal noiseless variable-rate codes for various classes of sources. For memoryless sources, upper and lower bounds are obtained for the minimax redundancy as a function of the block length of the code. Several techniques for constructing universal noiseless source codes for memoryless sources are presented and their redundancies are compared with the bounds. Consideration is given to possible applications to data compression for certain nonstationary sources.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 1981 IEEE. Manuscript received December 7, 1979; revised July 2, 1980. Date of Current Version: 06 January 2003. This work was supported by the National Science Foundation under Grants ENG75-20864 at the University of Illinois, Urbana, IL 61801, and ENG77-10503 at the University of Maryland, College Park, MD 20742,and by the Joint Services Electronics Program at the University of Illinois under Contract N00014-79-C-0424
Funding AgencyGrant Number
Joint Services Electronics ProgramN00014-79-C-0424
Record Number:CaltechAUTHORS:20120718-133007916
Persistent URL:
Official Citation:Davisson, L.; McEliece, R.; Pursley, M.; Wallace, M.; , "Efficient universal noiseless source codes," Information Theory, IEEE Transactions on , vol.27, no.3, pp. 269- 279, May 1981 doi: 10.1109/TIT.1981.1056355 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:32556
Deposited By: Ruth Sustaita
Deposited On:18 Jul 2012 20:44
Last Modified:26 Dec 2012 15:36

Repository Staff Only: item control page