File:Huffman coding example.svg
Original file (SVG file, nominally 277 × 133 pixels, file size: 13 KB)
Captions
Captions
Summary
[edit]DescriptionHuffman coding example.svg | 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 . |
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
[edit]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.http://www.gnu.org/copyleft/fdl.htmlGFDLGNU Free Documentation Licensetruetrue |
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.http://creativecommons.org/licenses/by-sa/3.0/CC BY-SA 3.0Creative Commons Attribution-Share Alike 3.0truetrue |
- 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.
File history
Click on a date/time to view the file as it appeared at that time.
Date/Time | Thumbnail | Dimensions | User | Comment | |
---|---|---|---|---|---|
current | 13:45, 4 December 2007 | 277 × 133 (13 KB) | Alejo2083 (talk | contribs) | fixed minor mistake | |
14:59, 18 May 2007 | 277 × 133 (13 KB) | Alejo2083 (talk | contribs) | {{Information |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 fr |
You cannot overwrite this file.
File usage on Commons
The following page uses this file:
File usage on other wikis
The following other wikis use this file:
- Usage on en.wikipedia.org
- Usage on en.wikibooks.org