Program #2

Design and implement an assembly program that uses Hamming's Algorithm to detect and correct errors in a byte stream.

1. Logistics

Program #2 is worth 100 points, or 10% of your final grade.

• Assigned: Mon Nov 10, 2003
• Due: Sat Nov 23, 2003

This program flexes your muscles in the following areas:

• Writing more P2 assembly code, of course, including the following:
  • bit-wise operations
  • parity checking
• Sharpening our hex/binary number skills
• Understanding Hamming's algorithm for error-correcting codes

2. Description

You should write two programs that use Hamming's algorithm:

• encode - reads a byte stream and encodes the data with error-correcting information
• decode - reads an encoded byte stream and decodes it, correcting any errors found in the stream

Hamming's algorithm

Hamming's algorithm is described in our text on pages 61-64.

In short, the Hamming algorithm is one method for creating an error-correcting code. Data is encoded with error-correcting information and then decoded. During the decoding process, any single-bit errors in the original data can be detected and corrected using the algorithm.

The steps for encoding are:

1. Read a data word
2. Create a number of parity check bits whose value is determined using the data word
3. Write the new code word which consists of the data word and the check bits
4. Go to step 1 until the byte stream is exhausted

The steps for decoding are:

1. Read a code word
2. Check the code word for errors using the check bits
3. If any errors were found, then correct them
4. Write the data word
5. Go to step 1 until the byte stream is exhausted

Some details

For Program #2, let's some parameters:

• Use a data word size of 2 bytes (16 bits)
• Use 5 check bits (this is the number required to encode 16 bits of data), making the total code word size 21 bits
• As a shortcut, let's pad the 5 check bits so that it's an even 8 bits. This means that the code word will be 3 bytes long (2 bytes data and 1 byte check bits)

If you're ambitious you can increase your data word size to 16 bytes (128 bits). This is the maximum data word size that can be handled with 8 check bits using the Hamming algorithm. It's some extra work though. Note that the overhead in this case (128 bits of data) is only 6% (8/128).

3. Implementation

In Program #1, we almost exclusively dealt with 4 byte integers. Now, you have to be very aware of byte size. Including:

• Instructions that deal with 1 byte must end in the letter 'b'. For example: 

        movb $0,%al

• Instructions that deal with 2 bytes at a time end with the letter 'w', for "word": 

        movw $1,%ax

• Register names change when dealing with different byte sizes:
  • %eax - a 4 byte register
  • %ax - the lower 2 bytes of eax
  • %al - the low byte of ax
  • %ah - the high byte of ax
  • This name convention applies for all registers: ebx-edx, edi, esi
• When dealing with 1 or 2 byte quantities on the stack, push and pop/add appropriately.

Reading & writing bytes of data

You can use two C functions to read and write data 1 byte at a time. They are:

• int getchar()

  Reads one byte and returns it. It returns -1 at the end of the stream.

   

• int putchar( int)

  Writes one byte. The return value is the character written or an EOF marker. You can probably ignore this for Program #2.

Notice that getchar() and putchar() deal with 4 byte quantities. The 1 byte read or written will be found in the lower byte of the 4 bytes. For more information and examples, try "help" on Microsoft Visual-whatever or google "getchar +visual".

Organizing the code word

In my implementation, I found it easier to separate the check bits and the data word when creating my code word. Instead of the organization shown in the example above, I used the following setup:

Please note this choice is not required. I just found it easier to design the program this way.

Lecture topics

I will lecture on the following topics:

• Bit flags
  • Defining hex constants
  • Binary masks
  • With andb
  • With orb
  • With XOR
• More EFLAGS - parity and carryout
• Parity checks
• Shifting bits
  • shlb
  • shrb

Is this section a reminder for you or me?

4. Grading

This is an individual project. If you need help, please see me. My standard office hours remain: MW 5:00-6:30pm & 8:30-10:00pm or email to setup an better time.

Please place your solution in a folder named "prog2" (or something similar) in your k: drive folder for our class. In this folder, you should include:

• Your assembly code (*.s)
• Your executables (*.exe)
• A README file (text, word, html, whatever) describing:
  • what each file in your folder does
  • how you tested your program and how I can reproduce these tests
  • document any problems you have/had

Always recompile and run your code here, on the k: drive, to exorcise any potential system-specific demons.

You will be graded on whether your solution works. You will also be graded on your ability to show you understand the code you turn in. You do this by:

• Commenting each block of code
• Commenting individual lines of non-trivial code
• Using meaningful label names
• Use an efficient, logical flow of statements, like unnecessary moves or labels

A program that works, without meeting these other criteria will lose (significant) points.

5. Hints, etc

I will provide a couple test cases of my own later this week.

A fairly detailed example of Hamming's algorithm at work: Program #2 example