From: Steinar H. Gunderson <sgunderson@bigfoot.com>
Date: Wed, 1 Mar 2006 01:30:11 +0000 (+0000)
Subject: Add preliminary source files.
X-Git-Url: https://git.sesse.net/?p=hamming;a=commitdiff_plain;h=0ca306f13d6b1548edf6106c504b1cd90c7c61ce

Add preliminary source files.
---

diff --git a/hamming.c b/hamming.c
new file mode 100644
index 0000000..76c351b
--- /dev/null
+++ b/hamming.c
@@ -0,0 +1,158 @@
+#include <stdio.h>
+
+#define DATA_BITS    11
+#define PARITY_BITS  5
+#define CODE_BITS    (DATA_BITS + PARITY_BITS)
+#define NUM_DATA_WORDS (1 << DATA_BITS)
+
+unsigned char hamming_lookup[NUM_DATA_WORDS];
+
+unsigned generate_parity(unsigned data)
+{
+	unsigned bits[DATA_BITS];
+	unsigned parity[PARITY_BITS];
+	unsigned i;
+
+	parity[4] = 0;
+	
+	for (i = 0; i < DATA_BITS; ++i) {
+		bits[i] = (data & (1 << i)) ? 1 : 0;
+		parity[4] ^= 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];
+
+	return parity[4] | (parity[3] << 1) | (parity[2] << 2) | (parity[1] << 3) | (parity[0] << 4);
+}
+
+unsigned make_codeword(unsigned data)
+{
+	return (data << PARITY_BITS) | hamming_lookup[data];
+}
+
+void generate_lookup()
+{
+	unsigned i;
+
+	printf("Generating lookup table.\n");
+	
+	for (i = 0; i < NUM_DATA_WORDS; ++i) {
+		hamming_lookup[i] = generate_parity(i);
+	}
+}
+
+/* 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 (hamming_lookup[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 = hamming_lookup[data];
+
+	unsigned hamming_parity = parity >> 1;
+	unsigned gen_hamming_parity = gen_parity >> 1;
+	unsigned extra_parity = 0;
+
+	/* check the lowest parity bit */
+	for (i = 0; i < CODE_BITS; ++i) {
+		extra_parity ^= (code & 1);
+		code >>= 1;
+	}
+
+	/* 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;
+}
+
+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.\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);
+			}
+		}
+	}
+}
+
+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;
+}
diff --git a/hamming.txt b/hamming.txt
new file mode 100644
index 0000000..aa9e947
--- /dev/null
+++ b/hamming.txt
@@ -0,0 +1,28 @@
+(15,11) Hamming code:
+
+
+ 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
+p1 p2 D1 p1 D2 D3 D4 p4 D5 D6 D7 D8 D9 DA DB
+--    xx    xx    xx    xx    xx    xx    xx
+   -- xx       xx xx       xx xx       xx xx
+         -- xx xx xx             xx xx xx xx
+                     -- xx xx xx xx xx xx xx
+                     
+p1 = D1 ^ D2 ^ D4 ^ D5 ^ D7 ^ D9 ^ D11
+p2 = D1 ^ D3 ^ D4 ^ D6 ^ D7 ^ D10 ^ D11
+p3 = D2 ^ D3 ^ D4 ^ D8 ^ D9 ^ D10 ^ D11
+p4 = D5 ^ D6 ^ D7 ^ D8 ^ D9 ^ D10 ^ D11
+
+   D1 D2 D3 D4 D5 D6 D7 D8 D9 DA DB
+p1 xx xx    xx xx    xx    xx    xx
+p2 xx    xx xx    xx xx       xx xx
+p3    xx xx xx          xx xx xx xx
+p4             xx xx xx xx xx xx xx
+
+Add an extra parity bit p5 for detecting double-bit errors; this is simply
+the XOR of all the bits, _including_ the other parity bits (see Wikipedia).
+
+Strategy: lookup tables. Table of 2048 values -> 5 parity bits should be very
+	  cheap (consume 2kB of RAM for unsigned char, fits nicely into L1
+          cache and all). Do we want to encode extra information here? Probably
+          not worth it at all...