Programming Assignment Checklist: Hamming Codes

Frequently Asked Questions

What are the goals of this assignment? To Learn about error-correcting codes and get more experience programming in machine language.

I can't launch the Java Web Start version of the Visual X-TOY simulator. Any ideas? Check the piazza thread on getting X-Toy to work. The have been a range of problems on both Mac OS and Windows this semester related to recent Java security bugs.

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

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.

How do I write/comment 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.

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.

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

• Comment each TOY program with your name, login, and pennkey. Your header should also describe the purpose of the program, including what it reads from standard input and what it writes to standard output.

• Include a register map at the top of your .toy file, as well as in your readme.

• Comment each TOY instruction with its "assembly language" equivalent.

• Comment each block of code that serves a high-level purpose, e.g., compute 3 parity bits.

Developing a TOY Program

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. To get started, download the sample TOY program multiply.toy.

Input, Output, and Testing

Input. Download data.zip and unzip it into the same folder as you encode.toy and decode.toy programs.

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

% more encode1.txt 
Terminal
---------------------------------------
0001 0001 0000 0001 
FFFF

% java TOY encode.toy < encode1.txt
...
Terminal
---------------------------------------
0001
0001
0000
0001
0001
0000
0000
...

% more decode1.toy
0001 0000 0000 0001 0001 0000 0000
FFFF

% java TOY decode.toy < decode1.txt
...
0001
0001
0000
0001
...

Testing.  The most complete way to test your TOY programs is to encode and decode all possible inputs. All the files referenced below are also in the data.zip archive.

• Use the input file encode16.txt< to debug encode.toy: it contains possible 4-bit inputs. The file encode16.txt.ans contains the answer: for brevity, it displays each bit as 0 or 1 (instead of 0000 or 0001) and groups the bits 7 per line (instead of 1 per line). encode16output.txt contains the output as it should be printed by encode.toy.

• Use the input file decode128.txt to debug decode.toy: it contains all possible 7-bit inputs, The file decode128.txt.ans contains the answer: again, for brevity, it displays each bit as a 0 or 1 and groups the bits 4 per line. decode128output.txt has the appropriate output from decode.toy.

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

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. Be very careful to update BOTH your comments and your actual code! It is very common to update only the pseduo-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 items is to fill in the question in the readme about registers before or during debugging.

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

• The program counter starts at 10 so make sure that you place your code starting at address 10.

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 surprised?

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