Project 2: Huffman Code and Hamming Code
Project 2: Huffman Code and Hamming Code
In this project, students are required to write a program to implement Huffman and Hamming codes to encode/decode their first name. The details of this project are as follows.
Step 1: Huffman Encoding. In this step, please encode your first name (in lower case) using Huffman code. The codebook of the 26 letters from ‘a’ to ‘z’ is stored in the given Huffman Dictionary file named ‘dict.mat’ for Matlab and ‘dict.csv’ for Pathon. In this codebook, the first column consists of the letters from ‘a’ to ‘z’, and the second column consists of the corresponding Huffman codewords for different letters. If you use Matlab, please use the command ‘load(‘dict.mat’)’ to read the file and store the codebook in the cell named “dict’ in Matlab. In the future, you can find the codeword of each letter in ‘dict’. For example, if you want to find the codeword of letter ‘c’, which is the third letter, you can input the command ‘hamming_c=cell2mat(dict(3,2))’. Here, 3 is the index of letter ‘c’ in the first column of ‘dict’, and 2 means the second column of ‘dict’, which is the codeword. Then, the codeword of letter ‘c’ is stored in the vector named ‘hamming_c” in Matlab. On the other hand, if you use Pathon, please use ‘csv.reader(open('dict.csv','r'))’ to open the file and save each row. After saving it, you could use the index to find the codeword of each letter. Note that the Python index differs from Matlab index since it starts from 0, not 1. As a result, the index of ‘a’ is 0, the index of ‘b’ is 1, and so on. You may refer to the following code for reading the file and find the codeword for letter ‘a’.
In this project, you need to encode your first name in your Student ID Card using the given codebook. If the number of letters in your first name is no smaller than 5 and no larger than 8, just keep your first name. If the number of letters in your first name is less than 5, please add ‘a’, ‘b’, ‘c’, …, after the last letter of your first name until the number of letters reaches 5. For example, if your first name is ‘edg’, you should expand it to ‘edgab’. If the number of letters of your first name is larger than 8, you can just keep the first 8 letters and remove the others. For example, if your first name is ‘abcdefghijklmn’, you can just keep ‘abcdefgh’.
For the above modified first name (if the number of letters of your first name is no smaller than 5 and no larger than 8, your modified first name is just your first name), please use the given codebook to encode each letter. In your report, please show your modified first name and the corresponding codewords for the letters in your modified first name.
Step 2: Before Hamming Encoding. For (7,4) Hamming code, every 4 bits are encoded to a 7-bit codeword. As a result, the number of input bits to (7,4) Hamming code should be a multiple of 4. However, in Step 1, the number of bits to encode your modified first name may be not a multiple of 4. If so, please add a minimum number of 0 at the end of the Huffman codeword obtained in Step 1 to ensure that the number of bits is a multiple of 4. For example, if the Huffman codeword of your modified first name is ‘1001 101’ in Step 1, you should expand it to ‘1001 1010’. The last bit 0 is added to make the number of bits equal to 8, a multiple of 4.
In your report, please show the expanded Huffman codeword of your modified first name.
Step 3: (7,4) Hamming Encoding. In this step, please use (7,4) Hamming code to introduce parity bits to your Huffman codeword obtained in Step 2 for error correcting. You can first apply the (7,4) Hamming code to the first 4 bits in the Huffman codeword, and then the second 4 bits, and so on. Please use the following generator in slides to generate the Hamming codeword.
For example, if the Huffman codeword obtained in Step 2 is ‘1001 1010’, the corresponding Hamming codeword is ‘1001011 1010001’.
Please show the Hamming codeword corresponding to the expanded Huffman codeword of your first name obtained in Step 2.
Step 4: Transmission over noisy wireless channel. Suppose that the Hamming codeword obtained in Step 4 is transmitted over a noisy wireless channel. Let us assumed that in every 7 bits in the codeword, there exists only one error at some position. For example, suppose that Hamming codeword is ‘1001011 1010001’ in Step 3. For the first 7 bits, the error pattern is ‘0100000’, while for the second 7 bits, the error pattern is ‘0000010’. In this case, the received codeword is ‘1101011 1010011’. When you write the program, for every 7 bits in Huffman codeword, you can first randomly generate an integer in the range of [1,7], which is denoted by n, and then generate a 7-bit error pattern where only the n-th bit is 1, and the other 6 bits are all zero. In your report, please show the error patterns that you randomly generate and the corresponding received codeword with errors.
Step 5: Hamming Decoding. Given the received codeword with errors, please perform Error Syndrome based Hamming Decoding Algorithm to correct the errors in the codeword. Please show in the report the decoded Huffman codeword after Hamming decoding. Please check whether it is the same as the Huffman codeword obtained in Step 2. (In Step 4, you generate some error patterns. You cannot just use these error patterns to correct errors in your program, because in practice, error patterns are unknown. You need to use Error Syndrome based Hamming Decoding Algorithm to correct the errors. The TA will check your program on this algorithm). Step 6: Huffman Decoding. After you get the Huffman codeword, you can refer to the given Huffman codebook to recover your modified first name. Note that in Step 2, maybe you have added some 0 bits at the end to make sure the number of bits in the expanded Huffman codeword is a multiple of 4. Here, you should delete them. Huffman code is an instantaneously decodable code. As a result, you can design the decoding algorithm based on this property. For example, for the first bit, your program should check whether this bit is a codeword of some letter in the codebook. If so, the first letter is decoded and you can look at the second bit to decode the second letter. Otherwise, you check whether the first two bits are the codeword of some letter in the codebook. You can keep doing this to decode all the letters. Please write a code to decode the Huffman code based on the given codeword, and show the decoded letters in your report. Check whether these letters are the same as your modified first name.
Submission Checklist:
First, please submit your Matlab or Pathon code. Second, please submit a report covering the following information:
- Your name and student ID
- Your modified first name (if the number of letters is no smaller than 5 and no larger than 8, just keep your original first name) and the Huffman codeword for your modified first name (please use the given codebook). You need to design the program to encode each letter, rather than you look at the codebook and then input the codeword of your first name. Whenever you show the codeword in report, please put a space after each 4 bits such that it is easier to read the codeword. For example, ‘1010 0011 1100 1010’.
- The expanded Huffman codeword if the number of bits in the original Huffman codeword is not a multiple of 4
- The Hamming codeword after implementing (7,4) Hamming code to the expanded Huffman codeword (please use the given generator matrix). Please use red color to mark all the parity bits in the Hamming codeword.
- The random error patterns that you generate and the received Hamming codewords with errors
- The Huffman codeword obtained after performing Error Syndrome based Hamming Decoding Algorithm.
- The decoded letters based on the Huffman codeword and codebook. Please use the program to decode the codeword.
