Jump to content

File:Huffman coding example.svg

Page contents not supported in other languages.
This is a file from the Wikimedia Commons
From Wikipedia, the free encyclopedia

Original file (SVG file, nominally 277 × 133 pixels, file size: 13 KB)

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 .
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

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 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.
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 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.
You may select the license of your choice.

Captions

Add a one-line explanation of what this file represents

Items portrayed in this file

depicts

18 May 2007

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)Alejo2083fixed 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 page uses this file:

Global file usage

The following other wikis use this file: