git.sesse.net Git - hamming/blob - hamming.c

   1 #include <stdio.h>
   2
   3 #define DATA_BITS    11
   4 #define PARITY_BITS  5
   5 #define EXTRA_BIT_POSITION (PARITY_BITS - 1)
   6 #define CODE_BITS    (DATA_BITS + PARITY_BITS)
   7 #define NUM_DATA_WORDS (1 << DATA_BITS)
   8
   9 unsigned char hamming_lookup[NUM_DATA_WORDS];
  10
  11 /*
  12  * Needed since we store all the parity at the end of the word, not at the expected
  13  * power-of-two bit positions. This is the inverse of the mapping
  14  * (0..15) -> (0, 8, 4, 2, 1, the rest in ascending order)
  15  */
  16 unsigned char permutation_table[CODE_BITS] = {
  17         0, 4, 3, 5, 2, 6, 7, 8, 1, 9, 10, 11, 12, 13, 14, 15
  18 };
  19
  20 unsigned generate_parity(unsigned data)
  21 {
  22         unsigned bits[DATA_BITS];
  23         unsigned parity[PARITY_BITS];
  24         unsigned i;
  25
  26         parity[EXTRA_BIT_POSITION] = 0;
  27
  28         for (i = 0; i < DATA_BITS; ++i) {
  29                 bits[i] = (data & (1 << i)) ? 1 : 0;
  30                 parity[EXTRA_BIT_POSITION] ^= bits[i];
  31         }
  32
  33         parity[0] = bits[0] ^ bits[1] ^ bits[3] ^ bits[4] ^ bits[6] ^ bits[8] ^ bits[10];
  34         parity[1] = bits[0] ^ bits[2] ^ bits[3] ^ bits[5] ^ bits[6] ^ bits[9] ^ bits[10];
  35         parity[2] = bits[1] ^ bits[2] ^ bits[3] ^ bits[7] ^ bits[8] ^ bits[9] ^ bits[10];
  36         parity[3] = bits[4] ^ bits[5] ^ bits[6] ^ bits[7] ^ bits[8] ^ bits[9] ^ bits[10];
  37         parity[EXTRA_BIT_POSITION] ^= parity[0] ^ parity[1] ^ parity[2] ^ parity[3];
  38
  39         return parity[EXTRA_BIT_POSITION] | (parity[3] << 1) | (parity[2] << 2) | (parity[1] << 3) | (parity[0] << 4);
  40 }
  41
  42 unsigned make_codeword(unsigned data)
  43 {
  44         return (data << PARITY_BITS) | hamming_lookup[data];
  45 }
  46
  47 void generate_lookup()
  48 {
  49         unsigned i;
  50
  51         printf("Generating lookup table.\n");
  52
  53         for (i = 0; i < NUM_DATA_WORDS; ++i) {
  54                 hamming_lookup[i] = generate_parity(i);
  55         }
  56 }
  57
  58 /* can detect all single or double bit errors */
  59 int has_error(unsigned code)
  60 {
  61         unsigned data = code >> PARITY_BITS;
  62         unsigned parity = code & ((1 << PARITY_BITS) - 1);
  63
  64         return (hamming_lookup[data] != parity);
  65 }
  66
  67 int has_double_error(unsigned code)
  68 {
  69         unsigned i;
  70         unsigned data = code >> PARITY_BITS;
  71         unsigned parity = code & ((1 << PARITY_BITS) - 1);
  72         unsigned gen_parity = hamming_lookup[data];
  73
  74         unsigned hamming_parity = parity >> 1;
  75         unsigned gen_hamming_parity = gen_parity >> 1;
  76         unsigned extra_parity = 0;
  77
  78         /* check the lowest parity bit */
  79         for (i = 0; i < CODE_BITS; ++i) {
  80                 extra_parity ^= (code & 1);
  81                 code >>= 1;
  82         }
  83
  84         /* no errors at all (user should have used has_error() first; boo, hiss) */
  85         if (hamming_parity == gen_hamming_parity && extra_parity == 0)
  86                 return 0;
  87
  88         /* both hamming and simple parity errors; this is a single-bit error */
  89         if (hamming_parity != gen_hamming_parity && extra_parity == 1)
  90                 return 0;
  91
  92         /* hamming says OK, but simple parity indicates an error => simple parity error is wrong */
  93         if (hamming_parity == gen_hamming_parity && extra_parity == 1)
  94                 return 0;
  95
  96         /* hamming says error, simple parity says OK => DOUBLE ERROR */
  97         return 1;
  98 }
  99
 100 /* Correct any single-bit error -- assumes there are no double-bit errors */
 101 unsigned correct_single_bit_error(unsigned code)
 102 {
 103         unsigned bits[CODE_BITS];
 104         unsigned parity[PARITY_BITS];
 105         unsigned i, bp = 0;
 106
 107         parity[EXTRA_BIT_POSITION] = 0;
 108
 109         for (i = 0; i < CODE_BITS; ++i) {
 110                 bits[i] = (code & (1 << i)) ? 1 : 0;
 111         }
 112         for (i = 1; i < CODE_BITS; ++i) {
 113                 parity[EXTRA_BIT_POSITION] ^= bits[i];
 114         }
 115
 116         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];
 117         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];
 118         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];
 119         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];
 120
 121         for (i = 0; i < PARITY_BITS - 1; ++i) {
 122                 if (parity[i] != bits[PARITY_BITS - 1 - i]) {
 123                         bp |= (1 << i);
 124                 }
 125         }
 126
 127         if (bp != 0) {
 128                 /* flip the wrong bit */
 129                 code ^= (1 << permutation_table[bp]);
 130                 parity[EXTRA_BIT_POSITION] ^= 1;
 131         }
 132
 133         /* recompute the lower parity */
 134         return (code & ~1) | parity[EXTRA_BIT_POSITION];
 135 }
 136
 137 void check_zero_bit_detection()
 138 {
 139         unsigned i;
 140         printf("Checking zero bit detection.\n");
 141
 142         for (i = 0; i < NUM_DATA_WORDS; ++i) {
 143                 unsigned code = make_codeword(i);
 144                 if (has_error(code)) {
 145                         printf("ERROR: Failed zero-bit test 1 for %x\n", i);
 146                 }
 147                 if (has_double_error(code)) {
 148                         printf("ERROR: Failed zero-bit test 2 for %x\n", i);
 149                 }
 150         }
 151 }
 152
 153 void check_single_bit_detection()
 154 {
 155         unsigned i, j;
 156         printf("Checking single bit detection and correction.\n");
 157
 158         for (i = 0; i < NUM_DATA_WORDS; ++i) {
 159                 unsigned code = make_codeword(i);
 160                 for (j = 0; j < CODE_BITS; ++j) {
 161                         unsigned corrupted_code = code ^ (1 << j);
 162
 163                         if (!has_error(corrupted_code)) {
 164                                 printf("ERROR: Failed single-bit test 1 for %x with bit %u flipped\n", i, j);
 165                         }
 166                         if (has_double_error(corrupted_code)) {
 167                                 printf("ERROR: Failed single-bit test 2 for %x with bit %u flipped\n", i, j);
 168                         }
 169                         if (correct_single_bit_error(corrupted_code) != code) {
 170                                 printf("ERROR: Failed single-bit correction test for %x with bit %u flipped\n", i, j);
 171                         }
 172                 }
 173         }
 174 }
 175
 176 void check_double_bit_detection()
 177 {
 178         unsigned i, j, k;
 179         printf("Checking double bit detection.\n");
 180
 181         for (i = 0; i < NUM_DATA_WORDS; ++i) {
 182                 unsigned code = make_codeword(i);
 183                 for (j = 0; j < CODE_BITS; ++j) {
 184                         for (k = 0; k < CODE_BITS; ++k) {
 185                                 unsigned corrupted_code = code ^ (1 << j) ^ (1 << k);
 186                                 if (j == k)
 187                                         continue;
 188
 189                                 if (!has_error(corrupted_code)) {
 190                                         printf("ERROR: Failed double-bit test 1 for %x with bit %u and %u flipped\n", i, j, k);
 191                                 }
 192                                 if (!has_double_error(corrupted_code)) {
 193                                         printf("ERROR: Failed double-bit test 2 for %x with bit %u and %u flipped\n", i, j, k);
 194                                 }
 195                         }
 196                 }
 197         }
 198 }
 199
 200 int main()
 201 {
 202         generate_lookup();
 203         check_zero_bit_detection();
 204         check_single_bit_detection();
 205         check_double_bit_detection();
 206
 207         return 0;
 208 }