K. Iwata et al., AN EFFICIENT UNIVERSAL CODING ALGORITHM FOR NOISELESS CHANNEL WITH SYMBOLS OF UNEQUAL COST, IEICE transactions on fundamentals of electronics, communications and computer science, E80A(11), 1997, pp. 2232-2237
This paper describes an effcient and simple coding algorithm of univer
sally optimal codes for stationary (ergodic) sources and noiseless cha
nnel 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 base
d on the well-known Ziv-Lempel coding algorithm proposed in 1978 (some
times called LZ78), and the second part is based on the Varn coding al
gorithm. The coding algorithm asymptotically achieves an optimal avera
ge cost of codes for stationary sources, and also achieves an optimal
cost of codes for stationary ergodic sources with probability one. Fur
thermore, the computational complexity of the proposed coding algorith
m is linear with respect to the length of source sequence and coded se
quence.