SymmetricRVLC

Construction of Symmetrical Reversible Variable Length

Codes Using Backtracking

Hsien-Wen Tseng and Chin-Chen Chang

Department of Computer Science and Information Engineering National Chung Cheng University, Chiayi 621, Taiwan, R.O.C.

E-mail: {hwtseng,ccc}@http://wendang.chazidian.comu.edu.tw

Correspondence address:

Chin-Chen Chang

Professor

Department of Computer Science and Information Engineering National Chung Cheng University

Chiayi 621, Taiwan, R.O.C.

E-mail: ccc@http://wendang.chazidian.comu.edu.tw

TEL: 886-5-2720411 ext. 33100

FAX: 886-5-2720859

Construction of Symmetrical Reversible Variable Length

Codes Using Backtracking

Hsien-Wen Tseng and Chin-Chen Chang

Department of Computer Science and Information Engineering, National Chung Cheng University, Chaiyi, Taiwan 621, R.O.C.

E-mail: {hwtseng,ccc}@http://wendang.chazidian.comu.edu.tw

Abstract

Many coding standards, such as JPEG, H.261, H.263, MPEG-1, MPEG-2, use variable length codes (VLC) as their entropy coding strategy. However, VLC have a big drawback when transmitting over a noisy channel. This drawback is an error propagation problem. For this reason, reversible variable length codes (RVLC) have been used to enhance the error resilient capabilities of VLC. This paper presents a new algorithm using backtracking that can construct symmetrical RVLC. Depth first node generation is applied to this algorithm and 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.

Keywords: reversible variable length codes (RLVC), Huffman Code, H.263, MPEG-4,

JPEG-2000, error resilience

1

1. Introduction

Traditionally, variable length codes (VLC) have been used as entropy coding in many image coding standards (JPEG [1]) and video coding standards (H.261 [2], H.263 [3], MPEG-1 [4], MPEG-2 [5]). An example of VLC is the Huffman Code, which is well known to give the optimal code with minimum redundancy. But in recent years, more and more new standards such as JPEG-2000 [6], H.263+ [7], H.263++ [8], MPEG-4 [9] have adopted reversible variable length codes (RVLC), because VLC have the problem of error propagation. Even one single bit error will cause many following codewords to be misinterpreted. This is a big problem in an error-prone environment. In order to enhance the error resilient capabilities of VLC, Fraenkel and Klein [10] presented the bidirectional Huffman coding in 1990, Takishima et al. [11] proposed the RVLC for avoiding continuous errors in 1995. RVLC are not only a prefix code but also a suffix code. A code is called a prefix code namely if no codeword is a prefix of any other codewords. Conversely, a code is called a suffix code namely if no codeword is a suffix of any other codewords. Therefore, RVLC can be decoded both in the forward and backward directions so as to provide error resilient transmission over a noisy channel.

RVLC are very useful because they provide the capability of error resiliency and because they can be decoded in two directions. Except for the adoption in many 2

standards as we mentioned above, RVLC can also be applied to speed up searching of encoded data. For example, we can begin by searching the encoded data in the forward and backward directions at the same time. This can significantly reduce the search time and this kind of search is impossible when using VLC.

There are two types of RVLC, one is symmetrical and the other is asymmetrical. Symmetrical RVLC share the same code table when decoding both in the forward and backward directions, because the code is symmetrical. But two types of code tables are necessary for asymmetrical RVLC. For this reason, symmetrical RVLC is simpler than asymmetrical RVLC; meanwhile, the memory requirement of symmetrical RVLC is less than that of asymmetrical RVLC. However, asymmetrical RVLC always provides better efficiency than symmetrical RVLC because a more flexible code selection is allowed.

In this paper, we will concentrate on symmetrical RVLC and devise a new method of constructing symmetrical RVLC. The remainder of this paper is organized as follows. Section 2 introduces the related works. Section 3 explains the details of our proposed algorithm. Experimental results are presented in Section 4. The conclusions are drawn in Section 5.

3

2. Previous Works

In 1995, Takishima et al. [11] proposed a coding scheme to generate RVLC. It starts from a non-reversible VLC, such as Huffman Code, and converts the code by a top-down scheme into a symmetrical RVLC. Recently, Tsai and Wu [12, 13] proposed a more efficient symmetrical RVLC construction algorithm that is based on Takishima et al.’s algorithm. This algorithm also starts from a list of given Huffman Code, but uses a new codeword selection mechanism to select candidate codewords in each level. We first explain some terms in relation to their construction algorithms, and then briefly summarize their algorithms.

The number of symmetrical codewords on a full binary tree of level L is given as follows:

mo(L) = 2└(L+1)/2┘,

where └x┘ is the largest integer less than or equal to x. Let p(L) denote the total number of symmetrical codewords at level L unavailable due to the violation of the prefix condition. The calculation of p(L) can be found in [11]. Hence, the number of available symmetrical codewords, m(L), at level L is calculated as follows:

m(L) = mo(L) - p(L).

If we ignore the codeword selection mechanism in both Takishima et al.’s algorithm and Tsai and Wu’s algorithms, then their algorithms can be summarized as 4