Lab 2: Entropy Coding

ECE3141 Lab 2

Information and Networks, ECE3141
Lab 2: Entropy Coding

1. Introduction
We have seen in lectures that “Information” is something that can be quantitatively
measured, and it is determined by the “surprise” or “uncertainty” of an event1
. So, a very
likely event (e.g. warm temperatures experienced in summer) conveys little information
when it occurs, whereas a less likely event (snow falling in summer) gives us much more
information.
We further saw that the average information rate, or “Entropy”, of a sequence of events tells
us the absolute minimum number of transmitted or stored bits needed to communicate that
sequence of events (on average).
A third key concept introduced in lectures was the difference between “binary digits” (the 1s
and 0s used to communicate information) and information “bits” (the actual information
carried). If we have an inefficient communication system, we might send a lot of binary
digits without conveying that much information. However, the entropy measure is important
because it tells us the lower limit on the number of binary digits needed to communicate the
sequence of events. We cannot go below this without losing information.
The mathematical calculation of entropy (mean information content of a set of discrete,
independent data) tells us the minimum average number of bits needed to communicate that
data without information loss. (See box below.) The entropy is calculated from the
probabilities of the individual possible event outcomes, which collectively make up the
probability mass function (pmf) p(X):
𝐻𝐻 = �𝑝𝑝(𝑥𝑥𝑖𝑖)𝐼𝐼(𝑥𝑥𝑖𝑖)
𝑖𝑖
= −�𝑝𝑝(𝑥𝑥𝑖𝑖)𝑙𝑙𝑙𝑙𝑙𝑙2(𝑝𝑝(𝑥𝑥𝑖𝑖))
𝑖𝑖
where 𝐼𝐼(𝑥𝑥𝑖𝑖) = −log2(𝑝𝑝(𝑥𝑥𝑖𝑖)) is the information associated with the event 𝑥𝑥 = 𝑥𝑥𝑖𝑖. Entropy is
maximised when all the outcomes are equally likely; that is, we get the same amount of
information when we learn each outcome. So, for example, if we have 8 possible outcomes
and they are all equally likely (𝑝𝑝(𝑥𝑥𝑖𝑖) = 1
8 𝑓𝑓𝑓𝑓𝑓𝑓 𝑎𝑎𝑎𝑎𝑎𝑎 𝑖𝑖), substitution in the above expressions
will show that 𝐼𝐼(𝑥𝑥𝑖𝑖) = 3 𝑓𝑓𝑓𝑓𝑓𝑓 𝑎𝑎𝑎𝑎𝑎𝑎 𝑖𝑖, and H=3 bits. In this case, we would allocate one of the
eight possible 3-bit words to identify each of the 8 possible outcomes and knowing that H=3
tells us that no other code word representation can do any better; we require at least 3 bits per
code word.
1 An “event” could be many things but in telecommunications it is commonly a symbol or message to be transmitted or stored.
ECE3141 Lab 2
2
However, if the outcomes are not equally likely (for instance, Figure 1 shows the pmf for
pixel intensities in an example image), then we learn more from a low-probability event
(because it is less expected) and we learn less (that is, we gain less information) from a more
probable event. In this case, we can represent our data more efficiently by using fewer bits
(binary digits) to identify the more likely outcome, and more bits to identify the less likely
outcome2
.
Figure 1. An example of a common data source
(pixel intensities in a “typical” image),
demonstrating different frequencies of occurrence
(i.e. different probabilities) for different intensities.
“Information loss”?
It is important to understand that the “information loss” referred to above has nothing to do
with bit errors or problems with transmission. It is concerned only with representing the
original data. If the entropy calculation says there is an average H bits/event of information,
then that’s how many bits we need to send (on average) to describe a series of such events;
any less and we cannot recover the original data.
For example, suppose we are measuring temperature 5 times per second. Maybe each
measurement comes from the digital thermometer as 1 byte (8 bits). We can (obviously)
communicate the temperature data if we send 5 x 8 = 40 bits per second, but perhaps we
don’t need that much. After accumulating lots of temperature measurements, we can estimate
the pmf and that allows us to calculate the entropy; let’s say it is 2.3 bits per temperature data
point. (It’s an average, so it doesn’t have to be an integer). Without knowing how we could
represent the data (this will be explored later in this lab), we now know that we MUST
transmit AT LEAST 5 x 2.3 = 11.5 bits per second (on average) if we’re to be able to recover
the original temperatures at a receiver somewhere. If we only have 10 bits per second
available, it is impossible (no matter how we represent the data) to recover the original
temperatures. There will be information loss even if those 10 bits per second are
communicated with absolute accuracy (no errors).
Note, however, that the entropy calculation assumes that each xi is independent. In our
temperature example (and in many other cases), they may not be. If we know the temperature
at one time instant, we might be able to make a good guess about what the next one will be.
In this case, we might decide to transmit temperature differences (that is, the change in
temperature from 200 ms ago). In this case, we might expect that the pmf of this differential
data is less uniform than that of the independent temperatures, will lead to a still lower
entropy, and therefore the data could be represented with fewer average bits.
2 Don’t worry if it is not intuitively obvious that this is necessarily true. The first exercise below should convince you of it.
ECE3141 Lab 2
3
The important point to understand is that, however we model the data, the uncertainty about
each new value means that there is an absolute lower limit to the number of bits needed to
remove that uncertainty at the receiver.
Again as we discussed in lectures, a common example of a variable length code is Morse code
from the early days of telegraphy (see Figure 2). Note that the more commonly occurring
letters (e.g. e, t) have been assigned shorter code words than less commonly occurring letters
(like q or j).
Figure 2. Table of Morse Code (from
http://www.bbc.co.uk/schools/gcsebitesize/science/ocr_gateway/home_energy/light_and_lasersrev1.shtml ).
If we have a variable length code (like Morse code), an important parameter is the average
number of bits/symbol. Suppose we have a set S of i symbols, each symbol si is represented
by a binary code word of length Li bits (i.e. Li is not the actual code word, but the number of
bits in the code word that represents si) and occurs with probability pi. Write down an
expression for the average number of bits/symbol in the box below.
Average number of bits/symbol:
�𝑝𝑝𝑖𝑖𝐿𝐿𝑖𝑖
𝑖𝑖
𝑖𝑖=1
The expression you’ve just written gives us the actual average number of bits/symbol, but it
may or may not be equal to the entropy. It cannot be less than the entropy but it could be
more, depending on how efficient the code is.
While the entropy formula tells us the minimum average number of bits needed, it doesn’t
tell us how to construct a set of code words that will achieve it. However, several suitable
codes were developed in the second half of the 20th century, the most important of which
are3
:
• Huffman Coding. Given a set of (assumed independent) symbols of known
probability to be represented, this technique will generate variable bit length codes
(one code per symbol) that most closely match the average word length given by the
Entropy, within the limitation that we use an integer number of bits for each code
word.
3 These are not the only variable length coding methods, and there are also several variations to each of them.
ECE3141 Lab 2
4
• LZW (Lempel-Ziv-Welch) codes. By building up a library of sequences of symbols
at both encoder and decoder, the LZW coder allocates a fixed length code word to a
variable number of symbols.
• Arithmetic Coding. By interpreting a group of symbols as defining a segment on a
number line, and then identifying that segment with an appropriate number of bits,
arithmetic coding allocates a variable number of bits to a variable number of symbols.
The advantage of arithmetic coding is that it can take us arbitrarily close to the
entropy limit if the probabilities of the symbols are known and the symbol sequence
is stationary (i.e. the statistics do not change with time).
These are examples of code word assignment schemes collectively known as “Entropy
Coders” (to finally explain the title of this laboratory exercise!), or “Variable Length Codes”
(VLCs). They are by no means the only methods available to us to reduce the bit rate we use
to transmit or store digital data. Rather, they are tools that we can use to exploit the statistics
of a set of “outcomes” generated by some other process, where those outcomes could
represent anything from spreadsheet entries to text characters to speech sample magnitudes to
colour descriptions of video. There are numerous other compression techniques that exploit,
for instance, known characteristics of the source of the data (e.g. knowing that it is a speech
signal) or how it will be used (e.g. knowing what components of an image our eyes are most
sensitive to). All of these other compression methods, even if they give us much greater
savings in bit rate4 than entropy coding alone, will generate sets of symbols for transmission
or storage, and they can all take advantage of entropy coding. In short, entropy coding is a
component of very many communication and storage systems, even if it might not always be
the main source of bit rate savings.
In this laboratory class, you will carry out the following as you investigate the representation
of data using variable length codes:
• Calculate entropy for simple probability distributions
• Demonstrate that variable length codes can provide data rate advantages for nonuniform probability distributions
• Use the Huffman coding tools in Matlab to generate code words, and both encode and
decode some simple data.
• Use the same tools to encode ASCII text data
• Investigate issues of code book generation at encoder and decoder, and whether the
code book itself needs to be communicated
2. Pre-lab
Prior to the laboratory class, you must read through this entire laboratory description and
complete the pre-lab online quiz. You may also be able to complete answers to some of the
questions which are based on theory (i.e. that don’t depend on experimental results).
You should also consider each exercise given, and think about the Matlab processing you
need to do (that is, how will the algorithm work? What instructions will you need? Do you
know how to use them?). In particular, you should familiarise yourself with the Huffman
Coding functions and the use of cell arrays, as discussed in Section 4(b) below.
4 These “much greater savings” are only really achievable if we can tolerate some loss, or distortion, of our data (i.e. the coder is
“lossy”). Entropy coding is always lossless, and can achieve much less compression by itself, though it may be used in conjunction
with lossy coding tools. Lossy coding applies when we are dealing with digitised versions of analogue (e.g. image or sound) data in
which some limited signal distortion may not be noticeable or can be tolerated. You can learn much more about these different
compression methods (such as JPEG, MPEG. MP3, etc.) in ECE4146 Multimedia Technologies.
ECE3141 Lab 2
5
3. Entropy and variable length coding
The following table lists a set of 16 symbols that could be used in a message we want to
transmit (we’re labelling them “a” to “p” but this, of course, is arbitrary), along with three
different probability distributions and three different sets of code words we might use to
represent the 16 quantities. For now, assume that any transmitted bits are received reliably by
a decoder, so we do not have to worry about the effect of transmission bit errors5
.
Symbol
s
PA(s) PB(s) PC(s) Code set
1
Code set
2
Code set
3
Huffman code
based on PB
a 0.0625 0.2 0.02 0000 001 101 11
b 0.0625 0.08 0.08 0001 0000 0000 0100
c 0.0625 0.08 0.08 0010 0001 0001 0001
d 0.0625 0.08 0.08 0011 0100 0100 0000
e 0.0625 0.08 0.08 0100 0101 0101 0011
f 0.0625 0.08 0.08 0101 0110 0110 0010
g 0.0625 0.06 0.06 0110 0111 0111 1010
h 0.0625 0.06 0.06 0111 1000 1000 0111
i 0.0625 0.06 0.06 1000 1001 1001 0110
j 0.0625 0.06 0.06 1001 1010 1010 1001
k 0.0625 0.06 0.06 1010 1011 1011 1000
l 0.0625 0.06 0.06 1011 1100 1100 0101
m 0.0625 0.01 0.05 1100 1101 1101 101101
n 0.0625 0.01 0.05 1101 1110 1110 101100
o 0.0625 0.01 0.06 1110 11110 11110 101111
p 0.0625 0.01 0.06 1111 11111 11111 101110
Table 1. Table of alternative symbol probabilities and code words. You will fill in the last column when you
complete Part 4a below.
Complete the following table of calculations and conclusions based upon the probabilities
and code words above. (Hint: It’s a little tedious but, if you like, you could do this by hand
using a calculator, without using Matlab. However, you will need the probability vector in
Matlab for the next step anyway, so it might be just as easy to use Matlab from the start.)
5 This may seem an unrealistic assumption, but in any practical system a source coding process (i.e. coding according to the
properties of the data source) such as entropy coding will be followed by a channel coding process (i.e. coding according to the
properties of the channel). The latter will add error protection (e.g. error correction bits, or an acknowledgement/retransmission
protocol) to ensure that the probability of errors getting through to the source decoder will be very small. Management of such
transmission errors is, of course, very important, but it’s out of scope for this lab. We will explore it in the next one.
ECE3141 Lab 2
6
What is the entropy of the source if the probabilities are those described
by PA?
4 bits/symbol
What is the average number of bits/symbol if the probabilities are
described by PA and we represent the symbols with Code Set 1?
4 bits/symbol
What do you conclude from your answers to the above two questions?
Average word length = Entropy, therefore the absolute minimum number of transmitted or
stored bits needed to communicate that sequence of events has been achieved. We cannot
go lower than this without losing information.
What is the entropy of the source if the probabilities are those described
by PB?
3.6489
bits/symbol
What is the average number of bits/symbol if the probabilities are
described by PB and we represent the symbols with Code Set 1?
4 bits/symbol
What do you conclude from your answers to the above two questions?
Average word length > Entropy.
What is the average number of bits/symbol if the probabilities are
described by PB and we represent the symbols with Code Set 2?
3.82 bits/symbol
What do you conclude from your answer to the above question?
Average word length > Entropy, but it is more efficient than PB & Code Set 1.
What is the average number of bits/symbol if the probabilities are
described by PC and we represent the symbols with Code Set 2?
4.1 bits/symbol
What do you conclude from your answer to the above question?
Entropy of source if probabilities are those described by PC: 3.9509 bits/symbol
Average word length > Entropy.
Code set 3 has the same code word lengths as Code set 2. The only difference is the first
code word. What problem do you foresee in using Code set 3, that we would not have with
Code set 2? Could Code set 3 be used in a practical system?
Code set 3, starting with 101 instead of 001, would take a longer time to process due to the
prefix code 1, which could be any of the following – 1000, 1001, 1010, 1011, 1100, 1101,
1110, 11110, 11111.
ECE3141 Lab 2
7
4. Huffman coding
Your calculations have shown that, by appropriate allocation of variable length codes to
represent symbols, we can obtain an advantage compared with use of fixed length code
words. However, we don’t know if the code word sets we have in the table are the best that
we can do. Perhaps there’s another set of variable length codes that can get us even closer to
the limit defined by the entropy. Within the constraint of allocating an integer number of bits
to represent any input symbol, and on the assumption that the symbols are independent,
Huffman Coding will generate optimum code words; that is, there are no other variable
length code words (that can be allocated one word per input symbol) which will get us closer
to the entropy limit.
You have seen in lectures how to generate Huffman Codes, but there is a Matlab function
that will generate them for you.
a) Read the Matlab documentation on the functions huffmandict, Huffmanenco and
huffmandeco. Create one vector containing the symbols a..p, and another with the
probabilities PB from the earlier table. (Hint: When using character symbols, the
symbol vector has to be a cell array.) Then use huffmandict to create the dictionary of
code words. Write the code words in the last column of the earlier table. Here is some
example code that may help, but you should not just copy and use it blindly; you need
to understand what it is doing!
PB=[0.2 .08 .08 .08 .08 .08 .06 .06 .06 .06 .06 .06 .01 .01 .01 .01]
symbols=['a';'b';'c';'d';'e';'f';'g';'h';'i';'j';'k';'l';'m';'n';'o';'p'];
c_symbols=cellstr(symbols);
dict=huffmandict(c_symbols,PB);
dict{:,:} % Display contents of dict array
Using the Huffman code words that you have now written in the earlier table, what is the
mean number of bits/symbol if the symbols follow the PB probabilities and we encode them
using the Huffman code words?
3.68 bits/symbol
What does the Huffman coder do if all the symbols have the same probability (i.e. as with
PA)?
Mean number of bits/symbol becomes 4 bits/symbol.
You might be thinking that the last question has been a bit contrived because we use 16
symbols, conveniently matched to a 4 bit code word. What happens if we don’t have such a
match? Suppose we had, say, 20 symbols that occur with equal probability (0.05). Before
running the Huffman coder, ask yourself how you would allocate code words to represent
such a set of symbols; would you just use 5 bits to identify each symbol, even though we
don’t have 32 symbols? What does the Huffman coder do when you present it with this
problem?
I would exhaust all possible 4 bit code words before using 5 bit code words.
ECE3141 Lab 2
8
Now that we have an understanding of how Huffman coding works, let’s move on from the
artificial examples above and use it to compress some real data, in this case ASCII text. You
will appreciate by now that we must have the probabilities of occurrence of each character if
we are to generate a Huffman code. We will discuss more in the next section about what
statistics we should use to generate the code table, but one way to obtain the probabilities is
to analyse a lot of text (in the appropriate language) and count the frequencies with which
each character occurs6
, then hope that the statistics are similar to the particular text we want
to transmit. One such source was used to obtain the figures in Table 2. As an aside, compare
some of the highest and lowest letter probabilities with the Morse code length in Figure 2, to
confirm that they make sense. We need these characters and their probabilities7 in
appropriate arrays to allow us to generate Huffman codes in Matlab. To save you time
importing and getting formats right, this data is available for you in the correct array formats,
in the file “HuffmanText.mat”. You will need to import this file into your Matlab data space,
using a command such as importdata() or matfile(). You can use your own approach
and initiative to do this but, if you get stuck, the following example code may help:
>> HuffmanObject = importdata('HuffmanText.mat');
>> symbols = HuffmanObject.AsciiChar
>> symbols_probs = HuffmanObject.AsciiProb
>> [dict2,Av_lenA] = huffmandict(symbols,symbols_probs) ;
Char Prob Char Prob Char Prob Char Prob
7 1.04E-03 O 1.85E-03 g 1.57E-02
(SPACE) 1.73E-01 8 1.06E-03 P 2.63E-03 h 2.76E-02
! 7.20E-05 9 1.03E-03 Q 3.18E-04 i 4.93E-02
" 2.46E-03 : 4.38E-03 R 2.54E-03 j 8.73E-04
# 1.80E-04 ; 1.22E-03 S 4.03E-03 k 6.80E-03
$ 5.65E-04 < 1.23E-03 T 3.34E-03 l 3.20E-02
% 1.61E-04 = 2.29E-04 U 8.19E-04 m 1.65E-02
& 2.27E-04 > 1.25E-03 V 8.97E-04 n 5.00E-02
' 2.46E-03 ? 1.48E-03 W 2.54E-03 o 5.81E-02
( 2.19E-03 @ 7.33E-05 X 3.45E-04 p 1.56E-02
) 2.25E-03 A 3.15E-03 Y 3.06E-04 q 7.51E-04
* 6.32E-04 B 2.18E-03 Z 7.62E-05 r 4.29E-02
+ 2.16E-04 C 3.93E-03 [ 8.68E-05 s 4.40E-02
, 7.43E-03 D 3.17E-03 \ 1.57E-05 t 6.41E-02
- 1.38E-02 E 2.69E-03 ] 8.89E-05 u 2.11E-02
. 1.52E-02 F 1.43E-03 ^ 3.39E-06 v 8.52E-03
6 It’s not even straightforward what this means! Some people have done character counts on dictionary words, but not all words in
the dictionary are equally likely to be used. Others have performed such counts on, for example, the collected works of Shakespeare,
but is this representative of the text you might be encoding? The probability data we are using here comes from someone who has
analysed a year’s worth of PDA memos (“PDA”?! Yes, it’s old; from 2002.). This may also not be representative, but at least this data
includes punctuation marks and capital letters, which are often omitted in these types of analyses. If you find a source of such
statistics that you think is better, let us know! 7 Note that the TAB character is missing from this data set. If you try below to process some text with a TAB in it, it will cause an
error.
ECE3141 Lab 2
9
/ 1.56E-03 G 1.89E-03 _ 1.17E-03 w 1.31E-02
0 5.55E-03 H 2.34E-03 ` 8.89E-06 x 1.96E-03
1 4.62E-03 I 3.23E-03 a 5.22E-02 y 1.14E-02
2 3.34E-03 J 1.74E-03 b 1.03E-02 z 6.00E-04
3 1.86E-03 K 6.92E-04 c 2.13E-02 { 2.63E-05
4 1.36E-03 L 1.90E-03 d 2.52E-02 | 6.78E-06
5 1.67E-03 M 3.55E-03 e 8.63E-02 } 2.58E-05
6 1.16E-03 N 2.10E-03 f 1.38E-02 ~ 3.39E-06
Table 2. An example set of measured probabilities of occurrence for letters and symbols in English.
b) Use the huffmandict function with the provided arrays to generate code words to
represent each of the characters in the table according to the associated probabilities.
What is the longest code word generated? What is the shortest? Are these assigned to the
expected characters?
Longest: 18 bits (^, ~) (p = 3.39E-06)
Shortest: 3 bits (space) (p = 1.73E-01)
Yes they are assigned to the expected characters.
c) So, now that we have a dictionary of variable length code words that should represent
English text efficiently, let’s try it out. Copy (or write) any random example of
English text (e.g. from an email or some part of this document) into a text array in
Matlab. Then encode it using huffmanenco and decode using huffmandeco. The
Matlab documentation gives guidance to calculate and compare the number of bits
needed before and after Huffman encoding. Try a few examples.
Note that, since Matlab uses the single apostrophe character to delimit text strings, a
piece of text that contains an apostrophe will cause it to terminate the string, and then
the subsequent text will cause an error. You need to “escape” the apostrophe by
inserting an extra apostrophe before each apostrophe in the string (so that, wherever
the original text contained a ‘, it now appears as ‘‘) then terminate the string with a
single apostrophe in the normal way.
By what percentage is the number of bits to represent a “typical” text string reduced using
Huffman coding?
Reduction = (Original-Encoded)/Original
Reduction = (371-261)/371
Reduction = 0.2965
ECE3141 Lab 2
10
5. Code word dictionaries
Hopefully you have realised an important requirement for a Huffman encoder and decoder to
work together is that the code word dictionary, or “lookup table”, must be available to both
encoder and decoder. Of course, the two must also be identical. There are two obvious
approaches to this problem.
One approach would be to rely on globally agreed statistics (effectively what we have
done in the previous exercise) and use the same code word dictionary for many
communication sessions, either by communicating the code word dictionary once or have
the encoder and decoder derive it based on the same probability data8
. What would be the
advantages and disadvantages of this approach?
Advantages: High security factor
Disadvantages: If miscommunicated/lost, cannot be recovered
The second approach is to analyse the message (or file, or image, or whatever) we want to
send, obtain the probability statistics for our symbol set, generate the optimum code word
set for this data set, and send the dictionary along with the message. What would be the
advantages and disadvantages of this approach?
Advantages: Ease of encoding/decoding
Disadvantages: Low security factor
There is no single answer as to which of the above approaches is best. It really depends on
the circumstances. Some video coding standards actually define, inside the standards
document, the bit patterns of variable length codes to be used to represent certain data (based
on statistics obtained during experiments carried out as the standard was developed). JPEG
uses the alternative approach when coding certain image data9
; the Huffman coding
dictionary is embedded in every JPEG image file and can be chosen to best suit each one.
Clearly one important consideration in our choice between the above two approaches is
whether we have the time and processing cycles available to analyse data statistics before
defining variable length code words. In the case of video calling, we probably don’t, since we
need to send video description data as soon as possible to minimise end-to-end delay.
Another is the size of the data file, as shown in figure 3 and the following example.
8 This latter approach could be a risky one, because the two dictionary generators would have to run exactly the same algorithm.
Huffman codes are not unique (that is, there can be multiple Huffman code word sets that give the same average bits/symbol), so we
need to be confident that encoder and decoder generate the same one! If you’re unclear why Huffman codes are not unique, discuss
with a demonstrator.
9 Not pixel intensities directly, but other image descriptors. JPEG is based on use of a 2-dimensional transform called the Discrete
Cosine Transform (similar to the Fourier transform), and it is the quantised transform coefficients that are Huffman encoded.
ECE3141 Lab 2
11
Figure 3. We compress our data with an Entropy Coder (such as Huffman Coder) but,
if we have to add a code word look up table to decode it, have we saved anything?
(The size of the blocks is supposed to indicate the amount of data required.)
Try to estimate how many bits it would take to represent the Huffman code word dictionary
that was generated from the ASCII character statistics. Note: there is no single, correct
answer to this question. Just think about what information a decoder would have to have to
be able to receive the variable length codes and turn them back into the correct ASCII text,
then come up with a method (it doesn’t have to be super-efficient) to represent that
information. Then calculate how many bits would be required.
(7+8+12) bits * 95 characters = 2565 bits
2^7bits = 128 bits
2^6bits = 64 bits
Suppose your code word dictionary requires X bits to send. Obviously, the Huffman coding
must save us at least X bits when compressing the actual data, or else (when we add the
bits necessary to represent the compressed data AND the code word dictionary) we would
get no advantage overall (see figure 3). At the end of Section 4 above, you calculated the
percentage by which your text data was compressed using the Huffman code without
taking account of the code word dictionary. How big would the original text file have to be
before it was worth Huffman coding, if we wanted to send the code word dictionary along
with the compressed data?
1,274 bytes = 10192 bits
1/0.2965=3.37
>3.37*10192=34347 bits
ECE3141 Lab 2
12
6. Sensitivity to errors
Although we said earlier that this lab has nothing to do with transmission errors, before we
finish let’s just spend a moment considering the consequences if there were bit errors in
transmission.
Consider first the case where we don’t use a VLC like Huffman coding. Instead we
represent text as fixed length ASCII codes or, in the case of our small set of data in Section
3 above, we use fixed-length 4-bit code words. What is the consequence of a single bit
error in the binary sequence that is generated?
Wrong information would be received
Now consider the case of a single bit error in a sequence of Huffman-generated VLCs.
What do you think is the consequence now? Is the communication more, or less, sensitive
to errors? Why? (Hint: there are several possible approaches to answer this question: you
could just consider the problem theoretically and describe what you think will happen, you
could take a sequence of Huffman codes making up a message from the set you generated
in Section 3 above and by hand see what happens when one bit is flipped, or you could try
to introduce a bit error in the encoded sequence in Matlab to see what is decoded.)
More sensitive to errors because redundancies are removed.
7. Conclusion
Having completed this laboratory, you have gained an understanding of code word length
and symbol probabilities, the applicability of variable length code words, and that, depending
on the symbol probabilities, these VLCs could result in data compression or expansion.
Proper design of a VLC scheme uses the known or assumed probabilities to minimise the
number of bits required to send a series of symbols.
You now also have experience with one of the best-known VLC methods: Huffman Coding.
And you can appreciate the trade-offs in using Huffman coding, in terms of assumed or
measured probabilities, and the transmission overhead that might be necessary if we need to
communicate the code word dictionary.
Before finishing, could each student please click on the “Feedback” icon for this laboratory
on Moodle, to record the average compression you achieved using the Huffman coding on
your example text. This will allow us to look at the overall average result and you’ll be able
to see if you have a similar result to others. Clicking on “feedback” also gives an opportunity
to provide some brief feedback on this laboratory exercise. (All inputs via the “feedback”
icon are anonymous.)
Finally, please submit this completed report via Moodle by the stated deadline. In so doing,
please be aware of the following:
• Even if you have had a mark assigned to you during the lab session, this mark will
not be registered unless you have also submitted the report.
• Your mark may also not be accepted or may be modified if your report is incomplete
or is identical to that of another student. (But it’s OK if you jointly wrote a report
with your partner and then both kept a copy.)
• By uploading the report, you are agreeing with the following student statement on
collusion and plagiarism, and must be aware of the possible consequences.
ECE3141 Lab 2
13
Student statement:
I have read the University’s statement on cheating and plagiarism, as described in the Student
Resource Guide. This work is original and has not previously been submitted as part of
another unit/subject/course. I have taken proper care safeguarding this work and made all
reasonable effort to make sure it could not be copied. I understand the consequences for
engaging in plagiarism as described in Statue 4.1 Part III – Academic Misconduct. I certify
that I have not plagiarised the work of others or engaged in collusion when preparing
this submission.
– END –