2S2122 Activity 4.1

Instructions

• Answer the following problems individually and truthfully.
• Be sure to show your solutions and please box your final answers.
• Please write your complete name, student number, and section on the upper left corner of your answer sheet. No name, student number, and section, no grade.
• Save your answers in pdf file type with the filename format "section_lastname_firstname_studentnumber.pdf" all in small caps. For example: "abc_wayne_bruce_201101474.pdf".
• Submit your files in the respective submission bin in UVLE. Be sure to submit in the correct class!
• Have fun doing these exercises :) these are not boring!

Grading Rubrics

• If you have a good solution and a correct answer, you get full points.
• If you have a good solution but the answer is not boxed (or highlighted), you get a 5% deduction of the total points for that problem.
• If you have a good solution but the answer is wrong, you get a 20% deduction of the total points for that problem.
• If your solution is somewhat OK but incomplete. You only get 40% of the total problem.
• If you have a bad solution but with a correct answer. That sounds suspicious. You get 0% for that problem. A bad solution may be:
  • You just wrote the given.
  • You just dumped equations but no explanation to where they are used.
  • You attempted to put a messy flow to distract us. That's definitely bad.
• No attempt at all means no points at all.
• Some problems here may be too long to write. You are allowed to write the general equation instead but be sure to indicate what it means.
• Make sure that you use bits as our units of information.

Problem 1 (2 pts.)

Suppose you have a source with a source distribution shown in:

Symbol	Probability
a	0.05
b	0.25
c	0.37
d	0.22
e	0.11

1. Without using Huffman encoding, create your own binary tree with arbitrary instantaneous codewords that tries to achieve the the ideal entropy $H(S)=2.078$ bits. (1 pt.)
2. Prove using Kraft's inequality that your codes are indeed instantaneous. (1 pt.)

Problem 2 (2 pts.)

1. Create a trinary tree (i.e., $D=3$) with instantaneous codewords for 10 symbols. Assume that the symbols have varying (arbitrary) probabilities. We just need a trinary tree with instantaneous codewords. (1 pt.)
2. Prove using Kraft's inequality that your codes are indeed instantaneous. (1 pt.)

Problem 3 (2 pts.)

In your own words, how cool is information theory in terms of coding theory?

Problem 4 (2 pts.)

Differentiate repetition codes, block codes, and Hamming codes. Make sure to indicate the tradeoffs for each encoding scheme.

Problem 5 (2 pts.)

Using (15,11) Hamming codes do the following for each number:

• Identify if the code has no error, single error, or double error.
• If it has a single error, identify which bit is faulty.
• Make sure to show your solution how you arrive at your answer. No solution no points. All or nothing.

1. 101111010111000 (1 pt.)
2. 111100011100001 (1 pt.)