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

Tasks

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

1. (3 pts)  Do Section 2.8, Projects and Problems 3
2. (1 pt)  Find the first-order entropy of a source with 6 symbols having probabilities .10, .12, .43, .05, .20, and .10  (solve completely).
3. (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.)
4. (2 pts)  Do Section 2.8, Projects and Problems 7 (Defend your answers)
5. (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.

	a	b	c	d	e	f
code 1	01	011	10	1000	0011	0111
code 2	1010	001	101	0001	1101	1011
code 3	1000	100000	100	1	10000	10

7. (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)?
8. (1 pt)  What is the information content of a message of 32 symbols from a source with three symbols if:
• each symbol is equally likely
• the symbol probabilities are .5, .3, and .2
9. (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.
10. (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.
11. (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

1. Students are expected to work in groups of 2.   Only one submission should be turned in from each group.
2. Clearly label your answers, and please submit them in the order assigned.
3. (repeated from course syllabus)   Academic Honesty: Students in one group are not permitted to access or compare homework, program, or project answers with those of any other student (past or present, alive or dead) or any Internet web site prior to submitting the assignment.  Comparing answers before submitting one's work, or getting answers off of the Internet 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. Students who compare answers prior to submission 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 who gets answers and the student who gives answers.
4. (repeated from course syllabus)  Lateness Policy: Unexcused late assignments will be penalized up to 5% per day not including weekends up to a 10-day maximum penalty of 50%. Without prior discussion with the professor, assignments will not be accepted more than two weeks late.