From c9fad713cb2e032540dcee980cb7241b6123205d Mon Sep 17 00:00:00 2001 From: "Steinar H. Gunderson" Date: Wed, 1 Mar 2006 23:39:12 +0000 Subject: [PATCH] Implement single-bit correction. --- hamming.c | 50 +++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 49 insertions(+), 1 deletion(-) diff --git a/hamming.c b/hamming.c index 76c351b..0371458 100644 --- 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); + } } } } -- 2.39.2