For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Efficient Universal Coding Algorithm for Noiseless Channel with Symbols of Unequal Cost
Ken-ichi IWATA Masakatu MORII Tomohiko UYEMATSU
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1997/11/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Source Coding
noiseless coding, additive cost of code symbol, universally optimal cost coding, Ziv-Lempel coding, Varn coding,
Full Text: PDF(506.2KB)>>
This paper describes an efficient and simple coding algorithm of universally optimal codes for stationary (ergodic) sources and noiseless channel with unequal symbol costs. The symbol cost indicates the required time (or space) for the transmission (or storage) of that symbol, and the cost of any code symbol depends only on that symbol. The proposed coding algorithm mainly consists of two parts. The first part is based on the well-known Ziv-Lempel coding algorighm proposed in 1978 (sometimes called LZ78), and the second part is based on the Varn coding algorithm. The coding algorithm asymptotically achieves an optimal average cost of codes for stationary sources, and also achieves an optimal cost of codes for stationary ergodic sources with probability one. Furthermore, the computational complexity of the proposed coding algorithm is linear with respect to the length of source sequence and coded sequence.