File:Huffman coding example.svg
Summary
| Description | The picture is an example of Huffman coding. Colors make it clearer, but they are not necessary to understand it (according to Wikipedia's guidelines): probability is shown in red, binary code is shown in blue inside a yellow frame. For a more detailed description see below (I couldn't insert a table here). |
| Date | |
| Source |
self-made  This W3C-unspecified vector image was created with Inkscape .Category:Unspec New SVG created with Inkscape#{{padleft:{{%23expr:{{CURRENTYEAR}} -{{REVISIONYEAR}}}}%7C2%7C0}}{{padleft:{{%23expr:{{CURRENTMONTH2}}-{{REVISIONMONTH}}}}%7C2%7C0}}{{padleft:{{%23expr:{{CURRENTDAY2}} -{{REVISIONDAY2}}}}%7C2%7C0}} |
| Author | Alessio Damato |
Description: Assume you have a source generating 4 different symbols with probability . Generate a binary tree from left to right taking the two least probable symbols and putting them together to form another equivalent symbol having a probability that equals the sum of the two symbols. Keep on doing this until you have just one symbol. Then read the tree backwards, from right to left, assigning different bits to different branches. The final Huffman code is:
| Symbol | Code |
|---|---|
| a1 | 0 |
| a2 | 10 |
| a3 | 110 |
| a4 | 111 |
The standard way to represent a signal made of 4 symbols is by using 2 bits/symbol, but the entropy of the source is 1.73 bits/symbol. If this Huffman code is used to represent the signal, then the entropy is lowered to 1.83 bits/symbol; it is still far from the theoretical limit because the probabilities of the symbols are different from negative powers of two.
Licensing
 |
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled GNU Free Documentation License. |
   |
This file is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license. | |
| ||
| This licensing tag was added to this file as part of the GFDL licensing update. |
- You are free:
- to share – to copy, distribute and transmit the work
- to remix – to adapt the work
- Under the following conditions:
- attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.
