Programming Assignment Checklist: Hamming Codes

Frequently Asked Questions

What are the goals of this assignment? To learn about error-correcting codes; to learn to program in a machine language; and to appreciate the programming and debugging advantages of a structured programming language like Java over machine language!

What is the format of a .toy file? To initialize a location in memory to have a value, write (on its own line) the index of the memory location (two hex digits), followed by a colon, followed by a space, followed by the value (four hex digits). Anything else on the line is ignored by the TOY simulator and treated as a comment. As well, lines not of this format are ignored. Read the sample TOY program multiply.toy.

TOY.java isn't following the TOY program that I gave it! What is going on? It's indeed doing what you asked, but you might not have asked for what you meant to.

Be sure that each line follows the required format XX: XXXX.
Check for duplicated line numbers or out-of-order line numbers.
Check for using a letter like O or l instead of the number 0 or 1.
Remember that all values, "line numbers", and arithmetic are in hex. For example, 1A comes after 19.
Unlike BASIC, you cannot skip a line number. This leaves an instruction command 0000 which halts the program when executed.
Watch out for jump statements — if you insert a new line of code between existing lines, you have to renumber the lines, and the location that you want to jump to may change.
The program counter starts at 10 so make sure that you place your code starting at address 10.
Be very careful to update BOTH your comments and your actual code at the same time! It is very common to update only the pseudo-code and not the machine instruction.
All registers are global variables, so be careful. One way to be sure that a register is not used for two different purposes is to fill in the question in the readme about registers before or during debugging.

How much do I need to comment my TOY code? At a minimum, you should:

Comment each TOY program with your name, login, and precept. Your header should also describe the purpose of the program, including what it reads from standard input and what it writes to standard output.
Comment each TOY instruction with its pseudocode equivalent.
Comment each block of code that serves a high-level purpose, e.g., compute 3 parity bits.

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

When I run my TOY code in the simulator I get the error java.lang.NumberFormatException: null. What does this mean? This is the error that TOY.java produces when you try to read from standard input when there is no input left. Be sure that your TOY program terminates when it encounters FFFF.

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.

Running TOY Programs

To simulate the execution of your program on a TOY machine, use either the text-based TOY.java or the Visual X-TOY simulator — both are available on the assignment page.

Command-line TOY simulator. The command-line TOY simulator lets you simulate the code, using Java's standard input/output to simulate TOY's standard input/output. TOY.java takes one command-line argument, which is the name of a TOY program file.

Compile it with
```
% javac TOY.java
```
Test it on the sample TOY program by typing the values in boldface.
```
% java-introcs TOY multiply.toy
...
Terminal
---------------------------------------
0002
0005
000A
...
```
First, you will see a core dump (the contents of the pc, the registers, and main memory) before the computation begins. When TOY asks for input, type it in (the 0002 and 0005 above). When TOY produces output, it will appear on the screen (the 000A above). Finally you will see a core dump after the computations ends.
To edit your own TOY programs, use any text editor.

Visual X-TOY simulator. The Visual X-TOY simulator from lecture provides lots of useful development features. There are three modes (edit, debug, and machine).

To load a TOY program, select File -> Open, then browse to find the program, e.g., multiply.toy.
To execute your program, select Mode -> Debug Mode. Then click the Run button at the bottom. You can enter data on standard input by typing the value in the Stdin tab and clicking the Add button. You will have to click the Run button to resume execution. You can see the results on standard output in the Stdout tab.
To edit your own program, select Mode -> Edit Mode. You can type your program directly in the edit window. You might wish to use multiply.toy as a reference for formatting and commenting.
To redirect standard input from a file, select Mode -> Load File to Stdin.

Testing

Input, Output and Testing. Once you have written your first version of encode.toy, run

% java-introcs TOY encode.toy

to type your inputs interactively, or

% java-introcs TOY encode.toy < encode1.txt

to read your inputs from a file instead. The file encode1.txt consists of a single test case for your encode.toy

0000 0001 0000 0001
FFFF

and if your program is working correctly, testing on this input should give the following, surrounded by initial and final core dumps.

This correct answer also appears in the file encode1-answer.txt. We provide several input test files of different sizes for both encode.toy and decode.toy, as well as the answers for each. Note that for convenience, the answer files list each input line and just a shortened version of the corresponding outputs.

The most complete way to test your TOY programs is to encode and decode all possible inputs. Use the sample inputs encode16.txt and decode128.txt to do this.

Reference solutions. As a special bonus, we provide HammingEncoder.java and HammingDecoder.java, which are two programs that encode or decode numbers in the same format as the assignment. You are welcome to examine or execute this code to help you in any way you see fit.

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.
Error correcting codes are also widely used on noisy analog channels such as 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.