Construction of Symmetrical Reversible Variable Length Codes Using Backtracking

Abstract

Many coding standards, such as JPEG, H.261, H.263, MPEG-1, MPEG-2, use variable length code (VLC) as their entropy coding strategy. However, VLCs have a big drawback when transmitting over a noisy channel. This drawback is an error propagation problem. For this reason, reversible variable length codes (RVLCs) have been used to enhance the error resilient capabilities of VLC. This paper presents a new algorithm using backtracking that can construct symmetrical RVLCs. Depth first node generation is applied to this algorithm and a bounding function is used to replace nodes with their symmetrical children. The experimental results show that our algorithm can generate better codes than those of previous methods. In addition, our proposed algorithm provides a shorter maximum code length. The shorter maximum code length can usually achieve more efficient decoding.