On optimal reversible-variable-length codes Conference Paper uri icon


  • n honor of the sixtieth anniversary of the Kraft inequality, we present variations motivated by the study of reversible-variable-length codes. Reversible-variable-length codes or fix-free codes are prefix condition codes that are instantaneous when decoded in either the forward and backward direction. They have been investigated for joint source-channel coding and have been applied within the video standards H.263+ and MPEG-4. They are also interesting for problems in information retrieval such as searching for patterns directly in compressed text. We provide a low-complexity heuristic to produce fix-free codes. The design of optimal or minimum-redundancy reversible-variable-length codes has been a longstanding open problem. We offer the first solution both to this problem and to a variation in which all codewords are also required to be palindromes.

name of conference

  • 2009 Information Theory and Applications Workshop (ITA)

published proceedings

  • 2009 Information Theory and Applications Workshop

author list (cited authors)

  • Savari, S. A.

citation count

  • 9

complete list of authors

  • Savari, SA

publication date

  • February 2009