Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
1999-11-16
2001-05-08
Williams, Howard L. (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
Reexamination Certificate
active
06229460
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to a method of generating a symmetrical reversible variable length code.
2. Description of the Prior Art
Variable length codes (hereinafter called VLCs) can achieve higher compression efficiency by assigning codewords with variable code lengths to digital data with non-uniform probability distributions. There are many modern image and video coding standards, such as the JPEG still image coding standard, the ITU series of H.261 and H.263 video coding standards and the ISO series of MPEG-1 and MPEG-2 standards, adopting VLCs as the entropy coding stage. Due to the variable code length nature of VLCs, such schemes are very sensitive to errors in noisy environments. Even one single bit mismatch will cause a serious synchronous problem due to the propagation of errors. Moreover, there are more and more image and video applications being applied and developed in unreliable wireless environments at present time, and the trend will become more important and popular in the future. Therefore, suitable retransmission protocols for less time-constrained applications and adequate VLC code designs for critical time-constrained applications are the main issues for the applications operated in error-prone environments.
A new reversible variable length code (hereinafter called RVLC) has been proposed for the applications operated in the error-prone environments. RVLCs can be decoded both in the forward and backward directions. For example, when an error occurs in the normal forward decoding of a bit stream, the RVLC decoder then proceeds to the end of the bit stream and decodes it in the backward direction. In other words, bit synchronization will not be affected by the propagation of a single bit error. A lot of research topics, such as H.263+and MPEG-4, pay extensive attention on RVLC. Y. Takishima, M. Wada and H. Murakami have proposed a symmetrical RVLC algorithm in the paper, “Reversible Variable Length Code” IEEE Trans. Comm., Vol.43, No.2/3/4, pp.158-163, 1995. The symmetrical RVLC algorithm proposed by Takishima et al. is described in detail as follows.
In this algorithm, the symmetrical RVLC is derived from a Huffman code. The Huffman code, in which digital data are assigned to codewords with optimal bit-lengths according to the known probability distribution of various symbols, is a non-reversible VLC. A RVLC must satisfy both the prefix condition and the suffix condition for instantaneous forward and backward decoding, respectively. If the RVLC satisfies the prefix (or suffix) condition, it means that each codeword does not coincide with the prefixes (or suffixes) of longer codewords. For example, the codeword “1001”, which is the prefix of the codeword “100111 (4 bits), does not satisfy the prefix condition. Before discussing this algorithm, some mathematical functions and the codeword properties are described first.
FIG. 1
(Prior Art) is a diagram of a binary tree for illustrating symmetrical codes and non-symmetrical codes. The binary tree begins at root R. Nodes of the next level in the binary tree are obtained by appending a bit of “0” or “1,” where appending “0” and “1” can generate a new code on the left side and on the right side, respectively. In
FIG. 1
, there are five levels, denoted by L1~L5, in this binary tree. The nodes on these levels correspond to codes with the code lengths from 1 to 5, respectively. For a symmetrical code, such as 11011 (node 5g), the bit sequences read from left to right and from right to left are the same. On the contrary, the non-symmetrical codeword, such as 10011, does not possess such bit sequence property. In
FIG. 1
, the nodes corresponding to symmetrical codes are represented by full circles and the nodes corresponding to non-symmetrical codes are represented by empty circles. If all codewords of a VLC are symmetrical, the VLC is reversible. Reversibility means that digital data can be decoded in the forward direction or in the backward direction. The number of the codes that have length L and can be instantaneously decoded, denoted by m(L), is determined as follows.
On a full binary tree as illustrated in
FIG. 1
, the number of symmetrical codes with length L, denoted by m
0
(L), is calculated as follows:
m
0
(L)=2
└(L+1)/2┘
(1)
where └x┘ denotes the ceiling function, which is the smallest integer or equal to x. The relation between L and m
0
(L) determined by equation (1) is illustrated in Table 1.
L
1
2
3
4
5
6
7
8
m
0
(L)
2
2
4
4
8
8
16
16
Not all of the symmetrical codes decided by equation (1) satisfy the instantaneous decoding condition. The symmetrical codes that satisfy the prefix condition and the suffix condition belong to those defined in m(L). Refer to the binary tree shown in FIG.
1
and consider a path from the root R to a leaf node at level L, such as the path 1a -2a -3a -4a -5a. In such a path, the codes corresponding to the nodes in the head are the prefix of the codes corresponding to the nodes in the tail. In other words, only one node can be selected as a candidate in a path. Selecting two or more nodes in a path can result in the violation of the prefix condition. Therefore, m(L) can be derived from m
0
(L) by deleting the nodes that could violate the prefix condition. Let u(i,L) denotes the number of symmetrical codes with length L that violate the prefix condition when a node at the i-th level is selected as a candidate. There are three different cases.
(a) u(i,L)=m
0
(L−2i), when i≦L/2;
(b) u(i,L)=1 or 0, when L/2<i<L;
(c) u(i,L)=0, in all other cases.
According to conditions (a), (b) and (c), the number of symmetrical codes with length L that can be assigned to an instantaneously decodable VLC, denoted by m(L), is given as follows:
m
(
L
)
=
m
0
(
L
)
-
∑
i
=
1
⌊
L
/
2
⌋
u
(
i
,
L
)
·
n
(
i
)
-
∑
i
=
⌊
L
/
2
⌋
+
1
L
-
1
x
(
i
,
L
(
2
)
where n(i) denotes the number of codewords with length i in the original VLC and x(i,L) denotes the number of codewords with length i whose (2i−L) suffixes are symmetrical. In equation (2), the second term and the third terms are used to calculate the total number of symmetrical codes due to the violation of the prefix condition in case (a) and case (b), respectively. Therefore, the symmetrical codes with length L which satisfy the instantaneous decoding condition, denoted by m(L), can be acquired by deleting the codewords that violate the prefix condition from the symmetrical codewords with length L, denoted by m
0
(L).
The symmetrical RVLC algorithm proposed by Takishima et al. derives a RVLC from an original VLC, such as the Huffman code, by using the function m(L).
Step 1:
The bit length vector n
rev
(i) of the target RVLC is initialized to be the bit length vector n(i) of the original VLC (such as the Huffman code). The component of a bit length vector indicates the number of the codewords with length i. Accordingly, n
rev
(i)=n(i).
Step 2:
For every i, the condition n
rev
(i)≦m(i) is examined, where n
rev
(i) denotes the number of the codewords with length i and m(i) denotes the number of the symmetrical codes with length i which satisfy the instantaneous decoding condition. Accordingly, when n
rev
(i)≦m(i), it means that the number of the symmetrical codes is enough to be assigned to the codewords with length i in the target RVLC. When the condition is not satisfied, it means that the assignment requires the codes with length i+1. At this time, the bit length vector n
rev
(i) of the target RVLC must be adjusted:
n
rev
(
i+
1)=
n
rev
(
i+
1)+
n
rev
(i)−
m
(i (3)
n
rev
(
i
)=
m
(
i
(4)
In equation (4), n
rev
(i) is set to be the maximal possible number, m(i). The other unassigned codewords with length i (that is, n
rev
(i)−m(i)) are assigned by the codes with length i+1. It is noted tha
Liu Shu-Wei
Tsai Chien-Wu
Wu Ja-Ling
Cyberlink Corporation
Fish & Richardson P.C.
Williams Howard L.
LandOfFree
Method of generating a symmetrical reversible variable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of generating a symmetrical reversible variable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of generating a symmetrical reversible variable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2440440