25-08-2017, 09:32 PM
Multimedia Communications
Multimedia Communications.pdf (Size: 624.73 KB / Downloads: 156)
Optimal codes
The necessary conditions for an optimal variable-length
binary code are:
1. Given any two letters aj and ak if then
2. The two least probable letters have codewords with the same
maximum length
3. In the tree corresponding to the optimum code, there must be
two branches stemming from each intermediate node
4. Suppose we change an intermediate node into a leaf node by
combining all the leaves descending from it into a composite
word of a reduced alphabet. Then, if the original tree was
optimal for the original alphabet, the reduced tree is optimal
for the reduced alphabet.
Condition #1 and #2
• Condition #1 is obvious
• Suppose an optimum code C exists in which the two code
words corresponding to the least probable symbols do not
have the same length. Suppose the longer code word is k bits
longer than the shorter one.
• As C is optimal, the codes corresponding to the least probable
symbols are also the longest.
• As C is a prefix code, none of the code words is a prefix of
the longer code.
Huffman Codes
Since the Huffman code which gives the optimal codes meets
the Conditions #1, #2, #3 and #4, these conditions are also
sufficient conditions.
• It can be shown that not only does Huffman’s algorithm
always give a “right answer”, but also, every “right answer”.
– For the proof see section 4.3.1 in “Information theory and data
compression” by D. Hankerson.
Nonbinary Huffman Codes
Instead of combining three letters at the beginning we could have
combined two letters, into an alphabet of size 5,
– If we combine three letters from this alphabet we end up in alphabet
with a size of 3.
– We could combine three in the first step and two in the second step.
Which one is better?
– Observation:
• all combine letters will have codewords of the same length
• Symbols with the lowest probability will have the longest codeword
– If at some stage we are allowed to combine less than m symbols the
logical place is the very first stage
• In the general case of a code alphabet with m symbols (mary)
and a source with N symbols, the number of letters
combined in the first phase is: N modulo (m-1)
Primary version
The leaf nodes (source letters) are sorted non-increasingly
• We merge from below in the case of a tie
• When two nodes are merged they are called siblings
• When two nodes are merged, the parent node will be ranked
on the higher of the two sibling nodes.
• In the labeling of the edges (branches) of the tree, the edge
going from parent to highest sibling is labeled zero
• At start all letters have a count of one
• Update after count increment: the assignment of leaf nodes to
source letters is redone so that the weights are in nonincreasing
order
Performance
Adaptive Huffman codes: respond to locality
• Encoder is "learning" the characteristics of the source. The decoder must
learn along with the encoder by continually updating the Huffman tree so
as to stay in synchronization with the encoder.
• Another advantage: they require only one pass over the data.
• Of course, one-pass methods are not very interesting if the number of bits
they transmit is significantly greater than that of the two-pass scheme.
Interestingly, the performance of these methods, in terms of number of bits
transmitted, can be better or worse than that of static Huffman coding.
• This does not contradict the optimality of the static method as the static
method is optimal only over all methods which assume a time-invariant
mapping.
Adaptive Huffman Codes
• Update a node:
– If the node is the root, increase its weight and exit
– If the node has the highest node number in its block, increment its
weight, update its parent.
– If the node does not have the highest node number, swap it with the
node with highest number in the block (as long as the node with the
higher number is not the parent of the node being updated), increment
its weight, update its parents.