Huffman Coding
Section Overview
Huffman coding offers a way to compress data. The average length
of a Huffman code depends on the statistical frequency with which
the source produces each symbol from its alphabet. A Huffman code
dictionary, which associates each data symbol with a codeword, has
the property that no codeword in the dictionary is a prefix of any
other codeword in the dictionary.
The huffmandict, huffmanenco,
and huffmandeco functions support Huffman coding
and decoding.
Note
For long sequences from sources having
skewed distributions and small alphabets, arithmetic coding compresses
better than Huffman coding. To learn how to use arithmetic coding,
see Arithmetic Coding. |
Back to Top
Creating a Huffman Code Dictionary
Huffman coding requires statistical information about the source
of the data being encoded. In particular, the p input
argument in the huffmandict function lists the
probability with which the source produces each symbol in its alphabet.
For example, consider a data source that produces 1s with probability
0.1, 2s with probability 0.1, and 3s with probability 0.8. The main
computational step in encoding data from this source using a Huffman
code is to create a dictionary that associates each data symbol with
a codeword. The commands below create such a dictionary and then show
the codeword vector associated with a particular value from the data
source.
symbols = [1 2 3]; % Data symbols
p = [0.1 0.1 0.8]; % Probability of each data symbol
dict = huffmandict(symbols,p) % Create the dictionary.
dict{1,:} % Show one row of the dictionary.The output below shows that the most probable data symbol, 3,
is associated with a one-digit codeword, while less probable data
symbols are associated with two-digit codewords. The output also shows,
for example, that a Huffman encoder receiving the data symbol 1 should
substitute the sequence 11.
dict =
[1] [1x2 double]
[2] [1x2 double]
[3] [ 0]
ans =
1
ans =
1 1
Back to Top
Example: Creating and Decoding a Huffman Code
The example below performs Huffman encoding and decoding, using
a source whose alphabet has three symbols. Notice that the huffmanenco and huffmandeco functions
use the dictionary that huffmandict created.
sig = repmat([3 3 1 3 3 3 3 3 2 3],1,50); % Data to encode
symbols = [1 2 3]; % Distinct data symbols appearing in sig
p = [0.1 0.1 0.8]; % Probability of each data symbol
dict = huffmandict(symbols,p); % Create the dictionary.
hcode = huffmanenco(sig,dict); % Encode the data.
dhsig = huffmandeco(hcode,dict); % Decode the code.
Back to Top
 | Companding a Signal | | Arithmetic Coding |  |
How much time do you spend on testing to ensure implementation meets system-level requirements?
Learn more
Store 
