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