From a01d8b60ddcb7f44ce1944aafb127e47c5b8e9a7 Mon Sep 17 00:00:00 2001 From: "Steinar H. Gunderson" Date: Thu, 2 Mar 2006 13:00:46 +0000 Subject: [PATCH] Start working on the (32,26) Hamming code. --- hamming32.c | 209 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 209 insertions(+) create mode 100644 hamming32.c diff --git a/hamming32.c b/hamming32.c new file mode 100644 index 0000000..9547a28 --- /dev/null +++ b/hamming32.c @@ -0,0 +1,209 @@ +#include + +#define DATA_BITS 26 +#define PARITY_BITS 6 +#define EXTRA_BIT_POSITION (PARITY_BITS - 1) +#define CODE_BITS (DATA_BITS + PARITY_BITS) +#define NUM_DATA_WORDS (1 << DATA_BITS) + +unsigned char hamming_parity_lookup[256]; + +/* + * Needed since we store all the parity at the end of the word, not at the expected + * power-of-two bit positions. This is the inverse of the mapping + * (0..15) -> (0, 8, 4, 2, 1, the rest in ascending order) + */ +unsigned char permutation_table[CODE_BITS] = { + 0, 4, 3, 5, 2, 6, 7, 8, 1, 9, 10, 11, 12, 13, 14, 15 +}; + +/* FIXME: check if the lookup table actually helps us any here */ +unsigned find_parity_32(unsigned data) +{ + return + hamming_parity_lookup[ data & 0xff] ^ + hamming_parity_lookup[(data >> 8) & 0xff] ^ + hamming_parity_lookup[(data >> 16) & 0xff] ^ + hamming_parity_lookup[ data >> 24 ]; +} + +unsigned generate_parity(unsigned data) +{ + unsigned parity1 = find_parity_32(data & 0x036ad555); + unsigned parity2 = find_parity_32(data & 0x02d9b333); + unsigned parity3 = find_parity_32(data & 0x01c78f0f); + unsigned parity4 = find_parity_32(data & 0x003f80ff); + unsigned parity5 = find_parity_32(data & 0x00007fff); + unsigned parity6 = find_parity_32(data); + + return parity6 | (parity5 << 1) | (parity4 << 2) | (parity3 << 3) | (parity4 << 4) | (parity5 << 5); +} + +unsigned make_codeword(unsigned data) +{ + return (data << PARITY_BITS) | generate_parity(data); +} + +void generate_lookup() +{ + unsigned i; + + printf("Generating lookup table.\n"); + + for (i = 0; i < 256; ++i) { + unsigned parity = (i >> 4) ^ i; + parity = (parity >> 2) ^ parity; + parity = (parity >> 1) ^ parity; + hamming_parity_lookup[i] = parity & 1; + } +} + +/* can detect all single or double bit errors */ +int has_error(unsigned code) +{ + unsigned data = code >> PARITY_BITS; + unsigned parity = code & ((1 << PARITY_BITS) - 1); + + return (generate_parity(data) != parity); +} + +int has_double_error(unsigned code) +{ + unsigned i; + unsigned data = code >> PARITY_BITS; + unsigned parity = code & ((1 << PARITY_BITS) - 1); + unsigned gen_parity = generate_parity(data); + + unsigned hamming_parity = parity >> 1; + unsigned gen_hamming_parity = gen_parity >> 1; + unsigned extra_parity = find_parity_32(code); + + /* no errors at all (user should have used has_error() first; boo, hiss) */ + if (hamming_parity == gen_hamming_parity && extra_parity == 0) + return 0; + + /* both hamming and simple parity errors; this is a single-bit error */ + if (hamming_parity != gen_hamming_parity && extra_parity == 1) + return 0; + + /* hamming says OK, but simple parity indicates an error => simple parity error is wrong */ + if (hamming_parity == gen_hamming_parity && extra_parity == 1) + return 0; + + /* hamming says error, simple parity says OK => DOUBLE ERROR */ + return 1; +} + +#if 0 +/* 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[EXTRA_BIT_POSITION] = 0; + + for (i = 0; i < CODE_BITS; ++i) { + bits[i] = (code & (1 << i)) ? 1 : 0; + } + for (i = 1; i < CODE_BITS; ++i) { + parity[EXTRA_BIT_POSITION] ^= 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[EXTRA_BIT_POSITION] ^= 1; + } + + /* recompute the lower parity */ + return (code & ~1) | parity[EXTRA_BIT_POSITION]; +} +#endif + +void check_zero_bit_detection() +{ + unsigned i; + printf("Checking zero bit detection.\n"); + + for (i = 0; i < NUM_DATA_WORDS; ++i) { + unsigned code = make_codeword(i); + if (has_error(code)) { + printf("ERROR: Failed zero-bit test 1 for %x\n", i); + } + if (has_double_error(code)) { + printf("ERROR: Failed zero-bit test 2 for %x\n", i); + } + } +} + +void check_single_bit_detection() +{ + unsigned i, j; + printf("Checking single bit detection and correction.\n"); + + for (i = 0; i < NUM_DATA_WORDS; ++i) { + unsigned code = make_codeword(i); + for (j = 0; j < CODE_BITS; ++j) { + unsigned corrupted_code = code ^ (1 << j); + + if (!has_error(corrupted_code)) { + printf("ERROR: Failed single-bit test 1 for %x with bit %u flipped\n", i, j); + } + if (has_double_error(corrupted_code)) { + printf("ERROR: Failed single-bit test 2 for %x with bit %u flipped\n", i, j); + } +#if 0 + if (correct_single_bit_error(corrupted_code) != code) { + printf("ERROR: Failed single-bit correction test for %x with bit %u flipped\n", i, j); + } +#endif + } + } +} + +void check_double_bit_detection() +{ + unsigned i, j, k; + printf("Checking double bit detection.\n"); + + for (i = 0; i < NUM_DATA_WORDS; ++i) { + unsigned code = make_codeword(i); + for (j = 0; j < CODE_BITS; ++j) { + for (k = 0; k < CODE_BITS; ++k) { + unsigned corrupted_code = code ^ (1 << j) ^ (1 << k); + if (j == k) + continue; + + if (!has_error(corrupted_code)) { + printf("ERROR: Failed double-bit test 1 for %x with bit %u and %u flipped\n", i, j, k); + } + if (!has_double_error(corrupted_code)) { + printf("ERROR: Failed double-bit test 2 for %x with bit %u and %u flipped\n", i, j, k); + } + } + } + } +} + +int main() +{ + generate_lookup(); + check_zero_bit_detection(); + check_single_bit_detection(); + check_double_bit_detection(); + + return 0; +} -- 2.39.2