Write a TOY program to encode data using Hamming codes. Then write a TOY program to correct encoded data that has been corrupted.

Perspective.  Error correcting codes enable data to be sent through a noisy communication channel without corruption. To accomplish this, the sender appends redundant information to the message, so that even if some of the original data is corrupted during transmission, the receiver can still recover the original message intact. Transmission errors are common and can arise from scratches on a CD, static on a cell phone, or atmospheric interference. In a noisy environment, error correcting codes can increase the throughput of a communication link since there is no need to retransmit the message if it becomes partially corrupted during transmission. For this reason, error correcting codes are used in many common systems including: storage devices (CD, DVD, DRAM), mobile communication (cellular telephones, wireless, microwave links), digital television, and high-speed modems (ADSL, xDSL).

Hamming Codes.   A Hamming code is a specific type of error correcting code that allows the detection and correction of single bit transmission errors. Hamming codes are used in many applications where such errors are common, including DRAM memory chips and satellite communication hardware. Hamming codes work by repeatedly reading four message bits, which we denote by m1, m2, m3, m4, and then inserting three parity bits, which we denote by p1, p2, and p3. If any one of these seven bits is corrupted during transmission, the receiver can detect the error and recover the original four message bits intact. This is called single bit error correction because at most one bit can be corrected per unit of data sent. The overhead for using this method is a 1.75 times increase in the amount of bandwidth since we use three extra parity bits for every four message bits. This compares favorably with naive approaches, e.g., sending three copies of each bit and using the one that appears most frequently.

Before we describe the algebra of Hamming codes, we first visualize the calculation of these parity bits using Venn diagrams. As an example, suppose we wish to send the message 1101. We associate each of the four message bits with a specific intersection region of three pair wise overlapping circles, as illustrated below:

Now imagine this picture is transmitted via modem over a noisy communication channel, and that one bit is corrupted so that the following picture arrives at the receiving station (corresponding to 1001100:

Of course, in practice, only the 7 bits are transmitted, rather than the circle diagrams.

Part 1. Write a TOY program encode.toy to encode a binary message using the scheme described above. Your program should repeatedly read four bits m1, m2, m3, and m4 from TOY standard input, and output the seven bits m1, m2, m3, m4, p1, p2, p3 to TOY standard output, where

Part 2. Write a TOY program decode.toy to correct a Hamming encoded message. Your program should repeatedly read seven bits m1, m2, m3, m4, p1, p2, p3 from TOY standard input, and output four bits to TOY standard output. Recall, to determine which one, if any, of the message bits is corrupted, perform the following three parity checks:

1. p1 = m1 ^ m2 ^ m4
2. p2 = m1 ^ m3 ^ m4
3. p3 = m2 ^ m3 ^ m4

Input format. For convenience, we'll transmit each bit individually (as 0000 or 0001), instead of packing 16 per TOY word as would be done in a real application. Your program should repeat until FFFF appears on TOY standard input. You may also assume that the number of transmitted bits (not including the terminating value) is a multiple of four when encoding, and a multiple of seven when correcting. Here are example input files for encode.toy and decode.toy.

Help. For your convenience, take look to hamming.zip. Ther is given an implementation in Java and the input files input[47].txt and all[47].txt.

Submission to Goya. Submit the files: encode.toy, decode.toy, and readme.txt as an tar archiv hamming.tar.

In order to create the tar-archiv use the following UNIX command: tar -cvf hamming.tar encode.toy, decode.toy readme.txt

Extra credit. Write a TOY program for part 2 that uses the fewest number of words of TOY main memory. You should count each (nonzero) line of your program.