Programming Assignment Checklist: Hamming Codes

Frequently Asked Questions (TOY programming)

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 preparation do I need before beginning this assignment? Read Chapter 6 of the textbook and watch the accompanying lecture videos.

How do I edit and execute a TOY program? Use either the command-line TOY simulator TOY.java or the Visual X-TOY simulator. Both are available on the assignment page. See the section below for some frequently asked questions.

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 single 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.

The TOY simulator isn't following the TOY program that I gave it! What is going on? We recommend checking for the following errors:

The program counter starts at 10 so make sure that you place your code starting at memory address 10.
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, memory address 1A follows 19. If you don't specify the value for a memory address, that memory address will have the default value of 0000, which is a halt instruction.
Watch out for jump statements—if you insert a new line of code between existing lines, you will have to renumber the lines. Also, be sure to update any jump statements that have hardwired line numbers.
Be very careful to update both your comments and your actual code at the same time! It is very common to update only the pseudocode 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.txt 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.

Can I assume that the input files are in the prescribed format? Yes, as usual, you can make this assumption. For example, the input files will contain only a sequence of 0000's and 0001's, followed by FFFF. Input files for encode.toy will have a multiple of four 0000's and 0001's; input files for decode.toy will have a multiple of seven 0000's and 0001's.

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

Frequently Asked Questions (TOY.java simulator)

What is the command-line TOY simulator? It is a Java program (from lecture) that lets you simulate the behavior of a real TOY machine using a .toy file.

How do I use the command-line TOY simulator? Download TOY.java and compile it with the following command:

% javac-introcs TOY.java

Execute it by specifying the name of the .toy file as the command-line argument.

% java-introcs TOY multiply.toy
0002
0005
000A

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).

How do I see a core dump (the contents of the PC, the registers, and main memory)? Use --verbose command-line option.

% java-introcs TOY --verbose multiply.toy

How do I edit a TOY program? Use any text editor. If you use DrJava, we recommend (temporarily) turning off the auto-indentation.

When I run my TOY code in the simulator I get the error java.lang.ClassNotFoundException: TOY. What does this mean? Did you download TOY.java and compile it? Is it in the same directory as encode.toy and decode.toy?

When I run my TOY code in the simulator I get the error java.util.NoSuchElementException. 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.

Frequently Asked Questions (Visual X-TOY simulator)

Why use the Visual X-TOY simulator instead of TOY.java? The Visual X-TOY simulator provides lots of useful development features. There are three modes (edit, debug, and simulator).

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 load a TOY program? Select File -> Open, then browse to find the program, e.g., multiply.toy.

How do I edit a TOY 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.

How do I execute a TOY 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.

How do I redirect standard input from a file? In Edit Mode, select Mode -> Load File to Stdin.

I get the warning "There are undefined lines. Note that this may not be a fatal error, it may be the space between functions between lines 19 and 20, and 29 and 30." What did I do wrong? Which memory address follows 19?

I get the error "Fatal error at 10: This will be interpreted by the C Parser as 10: 81FF. The simplest way to avoid this is to eliminate all colon usage outside intended instructions." What does this mean? The X-TOY parser is confused. Did you put exactly one space between the colon and the TOY instruction?

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 produce the following output:

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.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps. If you get stumped or frustrated on some portion of the assignment, you should not hesitate to consult a preceptor.

Download/unzip hamming.zip into your assignment 4 folder.
Download / install X-TOY.
Open X-TOY and experiment with some of the example programs (File -> Open Example Program).
- Add, Echo and Sum are simple Toy programs.
- Open and experiment with multiply.toy, which is included in the hamming.zip.
- Try executing some of the precept exercises.
Read, compile and run the reference solutions: HammingEncoder.java and HammingDecoder.java. Use these reference solutions as a "design" for TOY programs.
As you write your TOY programs, remember:
- The first section contains the TOY instruction - in HEX
- The second section contains the TOY pseudo-code
- The third section is used for your comments
In X-TOY, create a new file (File -> New).
- Change the header to the standard header (you can copy-and-paste over the default header).
- Save the file (File -> Save) as encode.toy in your assignment 4 folder.
- Incrementally implement and test encode.toy , using HammingEncoder.java as a guide. Note: as you revise your program, you will need to edit your TOY statement numbers accordingly.
  1. Write TOY code that inputs a number from standard input. If the number is negative, the program shall halt. Otherwise, it prints the number and inputs the next number.
  2. Edit your TOY program from step (a) so that it now reads in sequences of four numbers, halting if the first number is negative. Otherwise, it writes the four numbers and inputs the next sequence of numbers.
  3. Edit your TOY program from step (b) so that it now computes the parity bits, and writes the parity bits.
Incrementally implement and test decode.toy, using HammingDecoder.java as a guide.

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.