Implement single-bit correction.

diff --git a/hamming.c b/hamming.c
index 76c351b2bae4acf597f3cc71cb6f0fdc75710d3a..03714582b4ac5018e95551d86798f4d8dbf6fc50 100644 (file)
--- a/hamming.c
+++ b/hamming.c
@@ -7,6 +7,14 @@
 
 unsigned char hamming_lookup[NUM_DATA_WORDS];
 
+/* 
+ * Needed since we store all the parity at the end of the word, not at the expected
+ * power-of-two bit positions.
+ */
+unsigned char permutation_table[CODE_BITS] = {
+       0, 4, 3, 5, 2, 6, 7, 8, 1, 9, 10, 11, 12, 13, 14, 15
+};
+
 unsigned generate_parity(unsigned data)
 {
        unsigned bits[DATA_BITS];
@@ -87,6 +95,43 @@ int has_double_error(unsigned code)
        return 1;
 }
 
+/* Correct any single-bit error -- assumes there are no double-bit errors */
+unsigned correct_single_bit_error(unsigned code)
+{
+       unsigned bits[CODE_BITS];
+       unsigned parity[PARITY_BITS];
+       unsigned i, bp = 0;
+
+       parity[4] = 0;
+
+       for (i = 0; i < CODE_BITS; ++i) {
+               bits[i] = (code & (1 << i)) ? 1 : 0;
+       }
+       for (i = 1; i < CODE_BITS; ++i) {
+               parity[4] ^= bits[i];
+       }
+
+       parity[0] = bits[PARITY_BITS+0] ^ bits[PARITY_BITS+1] ^ bits[PARITY_BITS+3] ^ bits[PARITY_BITS+4] ^ bits[PARITY_BITS+6] ^ bits[PARITY_BITS+8] ^ bits[PARITY_BITS+10];
+       parity[1] = bits[PARITY_BITS+0] ^ bits[PARITY_BITS+2] ^ bits[PARITY_BITS+3] ^ bits[PARITY_BITS+5] ^ bits[PARITY_BITS+6] ^ bits[PARITY_BITS+9] ^ bits[PARITY_BITS+10];
+       parity[2] = bits[PARITY_BITS+1] ^ bits[PARITY_BITS+2] ^ bits[PARITY_BITS+3] ^ bits[PARITY_BITS+7] ^ bits[PARITY_BITS+8] ^ bits[PARITY_BITS+9] ^ bits[PARITY_BITS+10];
+       parity[3] = bits[PARITY_BITS+4] ^ bits[PARITY_BITS+5] ^ bits[PARITY_BITS+6] ^ bits[PARITY_BITS+7] ^ bits[PARITY_BITS+8] ^ bits[PARITY_BITS+9] ^ bits[PARITY_BITS+10];
+       
+       for (i = 0; i < PARITY_BITS - 1; ++i) {
+               if (parity[i] != bits[PARITY_BITS - 1 - i]) {
+                       bp |= (1 << i);
+               }
+       }
+       
+       if (bp != 0) {
+               /* flip the wrong bit */
+               code ^= (1 << permutation_table[bp]);
+               parity[4] ^= 1;
+       }
+
+       /* recompute the lower parity */
+       return (code & ~1) | parity[4];
+}
+
 void check_zero_bit_detection()
 {
        unsigned i;
@@ -106,7 +151,7 @@ void check_zero_bit_detection()
 void check_single_bit_detection()
 {
        unsigned i, j;
-       printf("Checking single bit detection.\n");
+       printf("Checking single bit detection and correction.\n");
 
        for (i = 0; i < NUM_DATA_WORDS; ++i) {
                unsigned code = make_codeword(i);
@@ -119,6 +164,9 @@ void check_single_bit_detection()
                        if (has_double_error(corrupted_code)) {
                                printf("ERROR: Failed single-bit test 2 for %x with bit %u flipped\n", i, j);
                        }
+                       if (correct_single_bit_error(corrupted_code) != code) {
+                               printf("ERROR: Failed single-bit correction test for %x with bit %u flipped\n", i, j);
+                       }
                }
        }
 }