Databases Reference
In-Depth Information
T A B L E 13 . 10
Sample table for obtaining the Huffman code for a given
label value and run length. The values of
Z
are
represented in hexadecimal.
Z
/
C
Codeword
Z
/
C
Codeword
···
Z
/
C
Codeword
0/0 (EOB)
1010
···
F/0 (ZRL)
11111111001
0/1
00
1/1
1100
···
F/1
1111111111110101
0/2
01
1/2
11011
···
F/2
1111111111110110
0/3
100
1/3
1111001
···
F/3
1111111111110111
0/4
1011
1/4
111110110
···
F/4
1111111111111000
0/5
11010
1/5
11111110110
···
F/5
1111111111111001
.
.
.
.
.
The categories and the corresponding difference values are shown in Table
13.9
.For
example, if the difference between two labels was 6, we would send the Huffman code for
Category 3. As Category 3 contains the eight values
, the Huffman
code for Category 3 would be followed by 3 bits that would specify which of the eight values
in Category 3 was being transmitted.
The binary code for the AC coefficients is generated in a slightly different manner. The
category
C
that a nonzero label falls in and the number of zero-valued labels
Z
since the last
nonzero label form a pointer to a specific Huffman code, as shown in Table
13.10
. Thus, if the
label being encoded falls in Category 3, and there have been 15 zero-valued labels prior to this
nonzero label in the zigzag scan, then we form the pointer
F
{−
7
,
−
6
,
−
5
,
−
4
,
4
,
5
,
6
,
7
}
/
3, which points to the codeword
1111111111110111. Because the label falls in Category 3, we follow this codeword with
3 bits that indicate which of the eight possible values in Category 3 the label takes on.
There are two special codes shown in Table
13.10
. The first is for the end-of-block (EOB).
This is used in the same way as in the Chen and Pratt [
196
] algorithm; that is, if a particular
label value is the last nonzero value along the zigzag scan, the code for it is immediately
followed by the EOB code. The other code is the ZRL code, which is used when the number
of consecutive zero values along the zigzag scan exceeds 15.
To see how all of this fits together, let's encode the labels in Table
13.8
. The label cor-
responding to the DC coefficient is coded by first taking the difference between the value of
the quantized label in this block and the quantized label in the previous block. If we assume
that the corresponding label in the previous block was
1, then the difference would be 3.
From Table
13.9
, we can see that this value falls in Category 2. Therefore, we would send the
Huffman code for Category 2 followed by the 2-bit sequence 11 to indicate that the value in
Category 2 being encoded was 3, and not
−
2, or 2. To encode the AC coefficients, we
first order them using the zigzag scan. We obtain the sequence
−
3,
−
1
−
93000
···
0
The first value, 1, belongs to Category 1. Because there are no zeros preceding it, we transmit
the Huffman code corresponding to 0/1, which from Table
13.10
is 00. We then follow this
by a single bit 1 to indicate that the value being transmitted is 1 and not
−
1. Similarly,
−
9
