Programming Assignment Checklist: Hamming Codes

Goals

Learn about error-correcting codes.
Learn to program in the TOY machine language.
Appreciate the programming and debugging advantages of a structured programming language like Java over machine language!

Frequently Asked Questions

What's up with input7.txt? One of the inputs is 1000. Sorry, it's a typo (which is now fixed). The 1000 should have been 0001. We regret any confusion this mistake caused.

I can't launch the Java Web Start version of the Visual X-TOY simulator. Any ideas? The program requires something called Web Start. When you installed Java initially, this was included. However, the last Windows security patch I applied broke this. If this happens to you, go to java.com and click the Get It Now button.

How do I format the TOY output? You can't. Just print one integer per line (0000 or 0001).

TOY.java doesn't read in some of my instructions. Any ideas? Be sure that you follow the required format XX: XXXX. Check for duplicated line numbers and using the letter O instead of the number 0.

My program prints out the right answer, but then I get java.lang.NumberFormatException: null. What could be wrong? You are probably trying to read from standard input, even though it is empty. Be sure that your TOY program terminates when it encounters FFFF.

TOY Simulator

To simulate the execution of your program on a TOY machine, use either the bare-bones TOY.java or the full-blown Visual X-TOY simulator.

The bare-bones TOY simulator is available in the ftp directory hamming. You need the three files TOY.java, StdIn.java, and In.java. To use the simulator, do the following:
- Compile it with javac TOY.java as usual.
- Test it by typing
```
java TOY multiply.toy
```
  First, you will see a core dump of every register and main memory location. Then, you will see the results of the computation. This TOY program expects you to enter two integers from standard input (in hex). After you do this, you will see their product (in hex) on standard output.
The Visual X-TOY simulator from lecture provides lots of useful development features. There are three modes (edit, debug, and machine). We used the machine mode in lecture, but you will probably want to develop with the edit mode.

Input, Output, and Testing

Input. Copy the hamming directory from the COS 126 ftp site to your computer.

Execution. To redirect standard input from a file, execute your programs with:

java TOY encode.toy < input4.txt
java TOY decode.toy < input7.txt

If you are using the Java X-TOY simulator, you can use Mode -> Load File to Stdin to redirect stdin from a file.

Testing. The most complete way to test your TOY programs is to encode and decode all possible inputs. Use the files all4.txt and all4.txt.ans to debug encode.toy: the first file contains all possible 4-bit inputs, the second contains the answer. We group the answer 7 integers per line even though the TOY machine outputs only 1 per line. Use the files all7.txt and all7.txt.ans to debug decode.toy: the first file contains all possible 7-bit inputs, the second contains the answer.

Reference solutions. As a special bonus, we provide Java source code HammingEncoder.java and HammingDecoder.java. for the two programs. You may wish to examine this and use it to develop your TOY programs.

Submission

readme.txt. Use the following readme file template and answer any questions.

Submission. Submit encode.toy and decode.toy.

Comments. You must comment your encode.toy and decode.toy programs to make it clear to the grader what you are doing and what each variable represents.

Debugging Tips

Here are some debugging hints that may help you out.

Remember that all values, "line numbers", and arithmetic are in hex. This is by far the most common error. For example, 1A comes after 19.
Comment your TOY code. Also, this may sound silly, but don't accidentally update your comments and forget to update the actual code!
All registers are global variables, so be careful.
Watch out for jump statements - if you insert a new line of code between existing lines, the location that you want to jump to may change.

Enrichment

Error correcting codes are used in CDs. You can drill a 2.5mm hole through it, and it will still play. Only 1/3 of data is music.
Geneticists observe a lot of "extra junk" and redundancy in human DNA. Are you surprized?
Error correcting codes are also widely used on noisy analog channels like radio links. This enables you to reduce the amount of power needed to transmit signals. Analogy: asking a bartender for a drink three times, rather than screaming over the noise just once.