Program #2 - An example

Here's a detailed example applying Hamming's algorithm, ala Program #2:

1. Encoding

Assume the input data word is "BK"... 2 letters, 2 bytes. The ASCII encoding (a full table appears on page 109 of our text) for these letters is:

Letter B K
Hex 0x42 0x4B
Binary 0100 0010 0100 1011

Our code word includes these 16 data bits and 5 check bits. Here's what the code word for "BK" looks like (check bits = x, we'll figure out their value next):

Codeword xx0x 100x 0010 010x 0101 1
Bit pos 1234 5678 9012 3456 7890 1

1             2

The check bits are at position 1, 2, 4, 8, and 16 of the code word. Each check bit is set according to the parity of the bits it is responsible for checking. A check bit's value is '1' its bits have an odd parity (an odd number of 1's) and '0' with an even parity. The parity for each check bit is shown below (from page 64 of our text):

  • Bit #1: Check bits 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 = 3 1's
  • Bit #2: Check bits 2, 3, 6, 7, 10, 11, 14, 15, 18, 19 = 3 1's
  • Bit #4: Check bits 4, 5, 6, 7, 12, 13, 14, 15, 20, 21 = 4 1's
  • Bit #8: Check bits 8, 9, 10, 11, 12, 13, 14, 15 = 2 1's
  • Bit #16: Check bits 16, 17, 18, 19, 20, 21 = 3 1's

So, the code word with check bits calculated would be (check bits in bold):

Codeword 1100 1000 0010 0101 0101 1

Finally, we can pad this quantity with 3 0's in the front or back and write it out to complete our encoding. If we pad the end of the word with 000 then our final result  is:

Codeword 1100 1000 0010 0101 0101 1000
In hex    C    8    2    5    5    8

In my implementation, I actually found it easier to separate the check bits from the data bits. My code word consists of the 2 data bytes followed by 1 byte of 0-padded check bits. So, my program actually outputs:

Codeword 0100 0010 0100 1011 0001 1001
In hex    4    2    4    B    1    9

So, the input data word for letters "BK" is 0x424B. Using Hamming's algorithm, this was encoded into 0x424B19. As you can see, one advantage of this approach is that you can easily see the input data bytes and the value of your check bits.

2. Decoding

Not surprisingly, the decoding phase is the inverse of the encoding phase. We know the data bytes and the check bits, so all we need to do is verify that the parity of the data matches the parity predicted by the check bits.

Using the code word above, the value of check bit #1 is '1', implying odd parity. We know that the bits checked by bit #1 are the odd bits. There are three 1's in the code word at these locations, so the parity matches the prediction of check bit #1.

Each check bit must be verified, and if no discrepancies are found, then the data word is correct and can be written. Summarizing:

Input 

Code word

 424B19
Output

Data word

 424B 

Please note that the ASCII hex byte values 0x42 and 0x4B will appear as 'B' and 'K', respectively, when written using putchar().

Detecting and then correcting an error

Well, what happens if the parity check fails? Let's introduce an error into our code word and see what happens. You can use your ASCII table (page 110 in the text) add a one-bit error to one of our letters. For example, we can change 0x42, the letter 'B', to 0x43, the letter 'C'. Notice the change in one bit below:

Letter ASCII code
'B' 0x42

0100 0010
'C' 0x43

0100 0011

With this artificial error, our new codeword is: 0x434B19, or in binary:

Codeword 1100 1000 0011 0101 0101 1
Bit pos 1234 5678 9012 3456 7890 1

1             2

Let's check our parity bits:

  • Bit 1 - 3 1's, odd parity... OK
  • Bit 2 - 3 1's, odd parity... OK
  • Bit 4 - 5 1's, odd parity... Error!
  • Bit 8 - 3 1's, odd parity... Error!
  • Bit 16 - 3 1's, odd parity... OK

Parity errors are found in 2 check bits, check bit #4 and check bit #8. The sum of these two bit locations (4 + 8 = 12) leads us to the bit that must be changed to correct the error. Flipping bit 12 changes the codeword to:

Codeword 1100 1000 0010 0101 0101 1
Bit pos 1234 5678 9012 3456 7890 1

1             2

After this correction, the output data word is 0x424B.