TELECOMMUNICATIONS AND RADIO ENGINEERING - 2009 Vol. 68,
No 20 		 

 

 

 

Recursive Coding: A New Fast and Simple Alternative of Arithmetical Coding

N.N. Ponomarenko and V.V. Lukin
National Aerospace University (Kharkiv Aviation Institute), 17, Chkalov St., Kharkiv, 61070, Ukraine

K.O. Egiazarian, and J. Astola
Institute of Signal Processing, Tampere University of Technology, P.O.Box 553, FIN-33101, Tampere, Finland

Abstract
A novel fast recursive coding technique is proposed. It operates with only integer values not longer 8 bits and is multiplication free. Recursion the algorithm is based on indirectly provides rather effective coding of symbols for very large alphabets. The code length for the proposed technique can be up to 20-30% less than for arithmetic coding and, in the worst case it is only by 1-3% larger.

References

  1. Rissänen, J., (1976), Generalized craft inequality and arithmetic coding, IBM J. Res. Develop., 20:198-203.
  2. Huffman, D.A., (1952), A method for the construction of minimum-redundancy codes, Proc. Inst. Radio Eng., 40(9):1098-1101.
  3. Bell, T., Witten, I.H., and Cleary, J.G., (1989), Modeling for text compression. ACM Computing Surveys, 21(4):557-591.
  4. Rissänen, J., and Mohiuddin, K.M., (1989), A multiplication-free multialphabet arithmetic code, IEEE Transactions on Communications, 37(2):93-98.
  5. Chevion, D., Karnin, E.D., and Walach, E., (1991), High efficiency, multiplication free approximation of arithmetic coding, Data Compression Conference, pp. 43-52.
  6. Jones, D.W., (1988), Application of splay trees to data compression, Communications of the ACM, 31(8):996-1007.
  7. Ryabko, B.Ya., (1989), A fast sequential code, Soviet Math. Dokl., 39(3):533-537 (in Russian).
  8. Graf, U., (1997), Dense coding - a fast alternative to arithmetic coding, Proceedings of Compression and Complexity of Sequences, pp. 295-304.
  9. Liddell, M., and Moffat, A., (2003), Hybrid Prefix Code for Practical Use, Proceedings of Data Compression Conference, pp. 392-401.
  10. Ryabko, B., and Rissänen, J., (2003), Fast adaptive arithmetic code for large alphabet sources with asymmetrical distributions, IEEE Communications Letters, 7(1):33-35.
  11. Ryabko, B., Astola, J., and Egiazarian, K., (2003), Fast codes for large alphabets, Communications in information and systems, 3(2):65-78.
  12. Ryabko, B., Marchokov, G., Egiazarian, K., and Astola, J., (2003), The fast algorithm for the block codes and its application to image compression, Proceedings of ICIP, 2:205-207.


pages 1857-1863

Back