File:Huffman coding example.svg

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Huffman_coding_example.svg‎ (SVG file, nominally 277 × 133 pixels, file size: 13 KB)

[edit] 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

18 May 2007(2007-05-18)
Source self-made
Inkscape Logo.svg
 This vector image was created with Inkscape.
Author

Alessio Damato
Permission
(Reusing this file)

See below.

Description: Assume you have a source generating 4 different symbols {a1,a2,a3,a4} with probability {0.4;0.35;0.2;0.05}. 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.

[edit] Licensing

I, the copyright holder of this work, hereby publish it under the following licenses:
GNU head 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.

w:en:Creative Commons
attribution share alike		 This file is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.
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 attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work).
  • share alike – If you alter, transform, or build upon this work, you may distribute the resulting work only under the same or similar license to this one.
This licensing tag was added to this file as part of the GFDL licensing update.

w:en:Creative Commons
attribution share alike		 This file is licensed under the Creative Commons Attribution-Share Alike 2.5 Generic, 2.0 Generic and 1.0 Generic license.
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 attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work).
  • share alike – If you alter, transform, or build upon this work, you may distribute the resulting work only under the same or similar license to this one.
You may select the license of your choice.

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeThumbnailDimensionsUserComment
current13:45, 4 December 2007Thumbnail for version as of 13:45, 4 December 2007277 × 133 (13 KB)Alejo2083 (fixed minor mistake)
14:59, 18 May 2007Thumbnail for version as of 14:59, 18 May 2007277 × 133 (13 KB)Alejo2083 ({{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)
The following pages on the English Wikipedia link to this file (pages on other projects are not listed):

Global file usage

The following other wikis use this file:

Metadata

This file contains additional information, probably added from the digital camera or scanner used to create or digitize it. If the file has been modified from its original state, some details may not fully reflect the modified file.
Width 277
Height 133
Retrieved from "http://en.wikipedia.org/wiki/File:Huffman_coding_example.svg"
Personal tools
Namespaces
Variants
Views
Actions
Navigation
Interaction
Toolbox