Scribd
Upload
50 views17 pages

Huffman Coding Analysis and Efficiency

The document discusses encoding techniques for discrete memoryless sources, focusing on Huffman coding and the calculation of average code-word lengths, efficiencies, and compression ratios. It provides examples with specific symbols and their probabilities, detailing how to derive Huffman codes and evaluate their performance. Additionally, it covers entropy calculations and the implications for message transmission rates in a communication system.

Uploaded by

seashellsss
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
50 views17 pages

Huffman Coding Analysis and Efficiency

The document discusses encoding techniques for discrete memoryless sources, focusing on Huffman coding and the calculation of average code-word lengths, efficiencies, and compression ratios. It provides examples with specific symbols and their probabilities, detailing how to derive Huffman codes and evaluate their performance. Additionally, it covers entropy calculations and the implications for message transmission rates in a communication system.

Uploaded by

seashellsss
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

 The code-words produced by the encoder are

in BINARY form.

 The source code is UNIQUELY DECODABLE.


Given a discrete memoryless source of entropy H(x),
the average code-word length L for any source
encoding is bounded as
 Is a source code whose average word length approaches
the fundamental limit set by the entropy of a discrete
memory less source, namely H(x).

 Produces the most efficient prefix code for a given set of


independent messages.
The source symbols are listed in order of
decreasing probability. The two source symbols
of lowest probability are assigned a 0 or a 1.
These 2 source symbols as regarded as being
combined into a new source symbols with
probability equal to the sum of the 2 original
probabilities.
These 2 source symbols as regarded as being
combined into a new source symbols with
probability equal to the sum of the 2 original
probabilities.
The five source symbols of the alphabet of a discrete memoryless source
and their probabilities are shown in the left-most columns. Find the
average information and the code word for the five symbols.
SYMBOL PROBABILIT
Y
S0 0.4
S1 0.2
S2 0.2
S3 0.1
S4 0.1
The following 6 letters, having the probabilities shown, must be
digitally transmitted. Determine the following:
a) the minimum number of bits per character H(x)
b) Huffman code
c) Compression Ratio(n/L)
d) Efficiency(Hx/L)

Xi P(Xi)
A, B 0.3
C 0.13
D, E, F 0.09
A discrete memoryless source has an alphabet of five symbols with the
probabilities for its output, as given here: Compute two different Huffman codes
for this source. Hence, for each of the two codes, find
a) The average code-word length
b) The variance of the average code-word length over the
ensemble of source symbols.
SYMBOL PROBABILITY
S0 0.55
S1 0.15
S2 0.15
S3 0.10
S4 0.05
Consider a group of eight possible messages (each message may be a single
character of text, a sentence, or the description of a possible outcome). Let’s
represent the messages using the characters A through H. The messages are
independent and have the probabilities of occurrence as listed below. Develop
a Huffman code to efficiently represent the set of messages.
SYMBOL PROBABILITY OF
OCCURRENCE
A 0.4
B 0.2
C 0.15
D 0.13
E 0.05
F 0.04
G 0.02
H 0.01
A source has three possible messages. The messages are
independent and have the following probabilities of
occurrence. Develop a Huffman code to represent the set of
messages and evaluate the efficiency of the code.

MESSAGE PROBABILITY OF
A 0.75
B 0.1875
C 0.0625
Consider the following set of messages:

Assume that the probability of occurrence of each message is independent and that each
message is transmitted independently.

a. Calculate the entropy of the message set.


b. How many binary digits (1 and 0) are required to transmit each message if a straight binary
assignment is use?
c. Suppose the communication system has the capability to transmit 6000 bits/sec error free
across the channel. How many messages per second can be transmitted if a straight binary
assignment is used?

You might also like