CS4450-001 Coding and Information Theory Fall 2019
Programming Project
In this project, you are going to write a computer program to solve certain computing problems studied in this course. You are free to select your favorite programming language. You can make use of any reference materials, but you cannot copy entire program code from others. You are required to demonstrate your program with meaningful examples to your professor and to submit a project report with one to two pages to document (1) Algorithms you have applied and assumptions you have made, (2) Program specifications and designs, (3) How to compile and run your program with an example, and (4) References, if any. You will get a bonus if you search for a research paper that is relevant to your project topic and give a simple discussion to prepare your work with the work presented in your selected paper in your project report.
The problems are listed as below. You are required to select only one problem to solve. If you want to do something different, you need to discuss it with your professor before starting your project. A team of two or three students are also encouraged. In this case, a team should select two problems.
1. Uniquely Decodable Code
Given a 𝑟-ary code 𝐶, determine if 𝐶 is uniquely decodable by computing 𝐶, 𝐶, … and 𝐶 and checking if 𝐶 and 𝐶 are distinct. If 𝐶 is not uniquely decodable, provide an example. (You can assume 𝑟 = 2 or 3.)
2. Instantaneous Code
Given a sequence of word lengths, determine if there is an instantaneous 𝑟-ary code with such word lengths. If yes, construct such an instantaneous code. (You can assume 𝑟 = 2 or 3.)
3. Huffman Code
Generate a r-ary Huffman code and calculate its average word-length for a given source with probabilities 𝑝. (You can assume 𝑟 = 2 or 3.)
4. Hamming Code
Given a k-bit binary number (data), generate a binary Hamming code word which contains the data. The generated code word should have a minimum length n for correcting a single bit error. (Note: you need to compute the minimum length n first.)
What to Submit:
1. Project report
2. Your program source code
Due Date: 12/03/2019