Transcription
Huffman Shift CodeThe most popular technique for removing coding redundancy is Huffman coding. Whencoding symbols of an information source individually, Huffman coding yields the smallestpossible number of code symbols per source symbol. Huffman coding has the higher codingefficiency.When a large number of symbols are to be coded, the construction of optimal binary Huffmancode is a nontrivial task. For general case of J source symbols, J-2 source reductions and J-2code assignments are required. So complexity increases. So sacrificing coding efficiency forsimplicity in code construction becomes necessary.In the Huffman shift code, the symbols are divided into blocks of equal size. Usually, theblock size is 2k-1 symbols, where k is a positive integer. If k 1 (the size of each block is 1),then the Huffman shift coding is equivalent to the standard Huffman coding.The individual source symbols within first block are coded identically with standard Huffmancode. While coding the symbols of first block, hypothetical symbol with probability equal tosum of probabilities of all symbols belonging to other blocks is coded with them, thusaffecting codeword assignment. The code words for the remaining symbols can beconstructed by means of one or more prefix code followed by the reference block as in thecase of binary shift code.The truncated Huffman coding makes J-K-1 Huffman code assignments and J-K-1 sourcereductions, thus taking less time, by cost of greater average code length and less efficiency.Huffman Shift Algorithm:The Huffman shift code is generated by the following procedure:1. The source symbols are arranged so that their probabilities are monotonicallydecreasing.2. The total number of source symbols is divided into symbol blocks of equal size.3. The individual source symbols within first block are coded identically with standardHuffman code. While coding the symbols of first block, hypothetical symbol withprobability equal to sum of probabilities of all symbols belonging to other blocks iscoded with them, thus affecting codeword assignment.4. Let's designate the Huffman code of that hypothetical symbol as C.5. The code of i-th symbol of block k is Ck-1 concatenated with Huffman code of i-thsymbol of the first block.
Example 1:The source of information A generates the symbols shown below. Encoding the sourcesymbols with the binary encoder and the truncated Huffman encoder gives:Source 60.050.040.02H 2.778Binary Code0000000100100011010001010110011110004The Entropy of the source isSince we have 9 symbols (9 16 24), we need 4 bits at least to represent each symbol inbinary (fixed-length code). Hence the average length of the binary code isThus the efficiency of the binary code isLet’s divide the source symbols into blocks of 3 (22-1) symbols, to construct a Huffman shiftcode,. Let’s introduce a hypothetical symbol Ax which probability is 0.35 (equals the sum ofthe probabilities of the last six symbols from A3 to A8). The new set of symbols is shown inthe table below.Source SymbolAxA0A1A2Pi0.350.30.20.15Truncated Huffman101000001
Then, the resultant code isSource SymbolTruncated 050.040.0211 0111 00011 001LavgH 2.7783.01010000011 011 0001 001The 6 less probable source symbols are assigned the Huffman code of that hypotheticalsymbol Ax (1) concatenated with natural binary code of length 3.The average length of the truncated Huffman code isThus the efficiency of the Shannon-Fano code isThis example demonstrates that the efficiency of the Huffman shift encoder is much higherthan that of the binary encoder.Applying the Huffman code of the same source, we get the following codewordsSource 60.050.040.02H 2.778Truncated Huffman000110011010101011111011110111112.81
The average length of the Huffman code isThus the efficiency of the Shannon-Fano code isThis example demonstrates that the efficiency of the truncated Huffman encoder is a bitlower than that of the standard Huffman encoder. However, the time is reduced as it needsonly 2 (4-2) stages of reduction while the Huffman needs 7 (9-2) stages of reduction.Exercise 1:The source of information A generates the symbols shown below. Encode the source symbolswith the binary encoder, the Huffman encoder and the Huffman shift encoder.Source 0.01Compare the efficiency of the three codes and comment on the results.Exercise 2:The source of information A generates the symbols shown below. Encode the source symbolswith the binary encoder, the Huffman encoder and the Huffman shift encoder.Source SymbolA1A2A3A4A5Pi0.20.10.10.060.05
0.020.01Compare the efficiency of the three codes and comment on the results. (Hint: let 2k -1 7)
Then, the resultant code is Source Symbol P i Truncated Huffman A0 0.3 01 A1 0.2 000 A2 0.15 001 A3 0.1 1 01 A4 0.08 1 000 A5 0.06 1 001 A6 0.05 11 01 A7 0.04 11 000 A8 0.02 11 001 L avg H 2.778 3.01 The 6 less probable source symbols are assigned the Huffman code of that hypothetical symbol Ax (1) concatenated with natural binary code of length 3.
