Add preliminary source files.

diff --git a/hamming.c b/hamming.c
new file mode 100644 (file)
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 (file)
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...