Databases Reference
In-Depth Information
of its offspring. The next symbol is again
a
. As we have an external node corresponding to
symbol
a
, we simply traverse the tree from the root node to the external node corresponding
to
a
in order to find the codeword. This traversal consists of a single right branch. Therefore,
the Huffman code for the symbol
a
is 1.
After the code for
a
has been transmitted, the weight of the external node corresponding
to
a
is incremented, as is the weight of its parent. The third symbol to be transmitted is
r
.As
this is the first appearance of this symbol, we send the code for the NYT node followed by the
previously arranged binary representation for
r
. If we traverse the tree from the root to the
NYT node, we get a code of 0 for the NYT node. The letter
r
is the 18th letter of the alphabet;
therefore, the binary representation of
r
is 10001. The code for the symbol
r
becomes 010001.
The tree is again updated as shown in the figure, and the coding process continues with symbol
d
. Using the same procedure for
d
, the code for the NYT node, which is now 00, is sent,
followed by the index for
d
, resulting in the codeword 0000011. The next symbol
is the
22nd symbol in the alphabet. As this is greater than 20, we send the code for the NYT node
followed by the 4-bit binary representation of 22
v
11. The code for the NYT node
at this stage is 000, and the 4-bit binary representation of 11 is 1011; therefore,
−
10
−
1
=
is encoded
as 0001011. The next symbol is
a
, for which the code is 0, and the encoding proceeds.
v
3.4.3 Decoding Procedure
The flowchart for the decoding procedure is shown in Figure
3.15
. As we read in the received
binary string, we traverse the tree in a manner identical to that used in the encoding procedure.
Once a leaf is encountered, the symbol corresponding to that leaf is decoded. If the leaf is the
NYT node, then we check the next
e
bits to see if the resulting number is less than
r
.If t
is less than
r
, we read in another bit to complete the code for the symbol. The index for the
symbol is obtained by adding one to the decimal number corresponding to the
e
-or
e
1-bit
binary string. Once the symbol has been decoded, the tree is updated and the next received bit
is used to start another traversal down the tree. To see how this procedure works, let us decode
the binary string generated in the previous example.
+
Examp l e 3 . 4 . 3 : Decoding Procedure
The binary string generated by the encoding procedure is
000001010001000001100010110
Initially, the decoder tree consists only of the NYT node. Therefore, the first symbol to be
decoded must be obtained from the NYT list. We read in the first 4 bits, 0000, as the value of
e
is four. The 4 bits 0000 correspond to the decimal value of 0. As this is less than the value
of
r
, which is 10, we read in one more bit for the entire code of 00000. Adding one to the
decimal value corresponding to this binary string, we get the index of the received symbol as
1. This is the index for
a
; therefore, the first letter is decoded as
a
. The tree is now updated
as shown in Figure
3.13
. The next bit in the string is 1. This traces a path from the root node
to the external node corresponding to
a
. We decode the symbol
a
and update the tree. In this
case, the update consists only of incrementing the weight of the external node corresponding
