MINIMIZING EXCESS CODE LENGTH AND VLSI COMPLEXITY IN THE MULTIPLICATION FREE APPROXIMATION OF ARITHMETIC CODING

Two new algorithms for performing arithmetic coding without employing multiplication are presented. The first algorithm, suitable for an alp habet of arbitrary size, reduces the worst case normalized excess leng th to under 0.8% vs 1.911% for the previously known best method of Che vion et al. The second algorithm, suitable only for alphabets of less than 12 symbols, allows even greater reduction in the excess code leng th. For the important case of the binary alphabet, the worst case exce ss code length is reduced to less than 0.1% vs 1.1% for the method of Chevion et al. The implementation requirements of the proposed new alg orithms are discussed and shown to be similar to those of the algorith m proposed by Chevion et al.