Course: CIS451/651 Data Compression in Multimedia
Professor: Paul D. Amer
Semester: Spring 2013
Title: Homework 1: Chapters 1 & 2

Tasks

Read chapters 1 and 2, and appendices A and B in the Sayood textbook. Submit answers to the following questions.

(3 pts) Do Section 2.8, Projects and Problems 3
(1 pt) Find the first-order entropy of a source with 6 symbols having probabilities .10, .12, .43, .05, .20, and .10 (solve completely).
(2 pts)(Difficult) Do Section 2.8, Projects and Problems 4 (Hint: first make up a simple example with actual p and q values that satisfy the given constraints.)
(2 pts) Do Section 2.8, Projects and Problems 7 (Defend your answers)
(3 pts) Consider the following three codings with source alphabet {a,b,c,d,e,f} and code alphabet {0,1}. For each code,

is the code uniquely decodable? If yes, argue why. If not, give two source messages that encode to the same coded message.
if the code is uniquely decodable, is it a prefix-free (i.e., instantaneous) code?
If the code is uniquely decodable and not prefix-free, give an equivalent uniquely decodable, prefix-free code with the same lengths of code words.

(1 pt) An information source generates words from an alphabet of 256 equally probable symbols. How long is a word from this source containing 128 bits of information (and no redundancy)?
(1 pt) What is the information content of a message of 32 symbols from a source with three symbols if:

(3 pts) Unary Code performance - In class, we looked at using a unary code for encoding the integers 0,1,2, ..., N,... which respectively occur with probabilities of 1/2, 1/4, 1/8,...,1/2^N+1, ... I claimed in class that the entropy of the system was 2 bits/code and that the unary code required 2 bits/code (hence making the unary code optimal). Prove the infinite summation resulting from the entropy formula equals 2.
(6 pts) Represent the base10 integer values 14₁₀ and -19₁₀ in:
- 8-bit unsigned
- 6-bit signed magnitude
- 10-bit excess+10
- 9-bit excess-20
- 14-bit 1s-complement
- 16-bit 2s-complement
Give each of your six answers above in 3 formats: binary, octal, hexadecimal.
(6 pts) What integer value does binary pattern 1011011 represent assuming each of the following semantics:
- unsigned
- signed magnitude
- excess+10
- excess-20
- 1s-complement
- 2s-complement
Give each of your six answers above in 3 number systems: base10, base8, base16.

Notes

Graduate students must do all assignments individually. Undergraduate students may collaborate in groups of 2 for assignments. Only one submission with both names should be turned in from a group.
Clearly label your answers, and please submit them in the order assigned.
(repeated from course syllabus) Academic Honesty: Unless explicitly stated otherwise, students are not permitted to access or compare any homework, or program-project answers with those of any other student or group past or present, alive or dead, or any Internet web site prior to submitting the assignment. Comparing answers, or getting answers off the Internet before submitting one's work is considered cheating. If you do not have time to complete an assignment, it is better to submit partial solutions than to get answers from someone else. While it is obviously difficult to enforce this policy, students who do not follow this policy should be keenly aware that in this class, they are cheating, and if caught, will be prosecuted according to University guidelines. This applies both to the student (or group) who gets answers and the student (or group) who gives answers.
(repeated from course syllabus) Lateness Policy: Assignments are due at the beginning of class. Unexcused late assignments will be penalized up to 10% per school day (weekends do not count) up to a 2-day maximum penalty of 20%. Without prior discussion with the professor, assignments will not be accepted more than two school days late.