X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=hamming.c;h=33376f31993bd4b1ed25cd45355984b7ed1bcb4f;hb=069b121a26d0b1ca1ad43a747d441b5882cdb405;hp=76c351b2bae4acf597f3cc71cb6f0fdc75710d3a;hpb=0ca306f13d6b1548edf6106c504b1cd90c7c61ce;p=hamming

diff --git a/hamming.c b/hamming.c
index 76c351b..33376f3 100644
--- a/hamming.c
+++ b/hamming.c
@@ -2,31 +2,41 @@
 
 #define DATA_BITS    11
 #define PARITY_BITS  5
+#define EXTRA_BIT_POSITION (PARITY_BITS - 1)
 #define CODE_BITS    (DATA_BITS + PARITY_BITS)
 #define NUM_DATA_WORDS (1 << DATA_BITS)
 
 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. 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
+};
+
 unsigned generate_parity(unsigned data)
 {
 	unsigned bits[DATA_BITS];
 	unsigned parity[PARITY_BITS];
 	unsigned i;
 
-	parity[4] = 0;
+	parity[EXTRA_BIT_POSITION] = 0;
 	
 	for (i = 0; i < DATA_BITS; ++i) {
 		bits[i] = (data & (1 << i)) ? 1 : 0;
-		parity[4] ^= bits[i];
+		parity[EXTRA_BIT_POSITION] ^= bits[i];
 	}
 
 	parity[0] = bits[0] ^ bits[1] ^ bits[3] ^ bits[4] ^ bits[6] ^ bits[8] ^ bits[10];
 	parity[1] = bits[0] ^ bits[2] ^ bits[3] ^ bits[5] ^ bits[6] ^ bits[9] ^ bits[10];
 	parity[2] = bits[1] ^ bits[2] ^ bits[3] ^ bits[7] ^ bits[8] ^ bits[9] ^ bits[10];
 	parity[3] = bits[4] ^ bits[5] ^ bits[6] ^ bits[7] ^ bits[8] ^ bits[9] ^ bits[10];
-	parity[4] ^= parity[0] ^ parity[1] ^ parity[2] ^ parity[3];
+	parity[EXTRA_BIT_POSITION] ^= parity[0] ^ parity[1] ^ parity[2] ^ parity[3];
 
-	return parity[4] | (parity[3] << 1) | (parity[2] << 2) | (parity[1] << 3) | (parity[0] << 4);
+	return parity[EXTRA_BIT_POSITION] | (parity[3] << 1) | (parity[2] << 2) | (parity[1] << 3) | (parity[0] << 4);
 }
 
 unsigned make_codeword(unsigned data)
@@ -87,6 +97,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[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];
+}
+
 void check_zero_bit_detection()
 {
 	unsigned i;
@@ -106,7 +153,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 +166,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);
+			}
 		}
 	}
 }