Optymalne kodowanie

Optimum encoding (Huffman Code) For any given source with elements (messages), the optimum binary code exists, in which the two least likely code words and have the same length and differ in only the last bit, ending in a 0 and ending in a 1.
Shorter codewords encode more likely source elements, i.e. if , then .
Among code words of the same length , two words differ in only the last bit.
Step 0. Set i =0; . Assign empty code word to each source element.
Step 1. Reorder source elements such that .
Step 2. Create the reduced source , by joining the least likely elements and . Set ; .
Step 3. If M =2, then GO TO Step 4, otherwise GO TO Step 1.
-----------------------------------------------------------------------------------------------------------------
Step 4. Add 0 at the right side of a code word that encodes and add 1 at the right side of a code word that encodes .
Step 5. Set ; . If , then GO TO Step 4, otherwise END the Algorithm.
When performing Steps 1-3 in a loop, times, source is reduced to the binary one.
When performing Steps 4-5 in a loop, times, the reduced sources are encoded by adding 0 and 1 at the end of the least likely codewords.
... zobacz całą notatkę