2S2122 Activity 4.1

From Microlab Classes
Jump to navigation Jump to search

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