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 unsigned generate_parity(unsigned data)
  11 {
  12         unsigned bits[DATA_BITS];
  13         unsigned parity[PARITY_BITS];
  14         unsigned i;
  15
  16         parity[4] = 0;
  17
  18         for (i = 0; i < DATA_BITS; ++i) {
  19                 bits[i] = (data & (1 << i)) ? 1 : 0;
  20                 parity[4] ^= bits[i];
  21         }
  22
  23         parity[0] = bits[0] ^ bits[1] ^ bits[3] ^ bits[4] ^ bits[6] ^ bits[8] ^ bits[10];
  24         parity[1] = bits[0] ^ bits[2] ^ bits[3] ^ bits[5] ^ bits[6] ^ bits[9] ^ bits[10];
  25         parity[2] = bits[1] ^ bits[2] ^ bits[3] ^ bits[7] ^ bits[8] ^ bits[9] ^ bits[10];
  26         parity[3] = bits[4] ^ bits[5] ^ bits[6] ^ bits[7] ^ bits[8] ^ bits[9] ^ bits[10];
  27         parity[4] ^= parity[0] ^ parity[1] ^ parity[2] ^ parity[3];
  28
  29         return parity[4] | (parity[3] << 1) | (parity[2] << 2) | (parity[1] << 3) | (parity[0] << 4);
  30 }
  31
  32 unsigned make_codeword(unsigned data)
  33 {
  34         return (data << PARITY_BITS) | hamming_lookup[data];
  35 }
  36
  37 void generate_lookup()
  38 {
  39         unsigned i;
  40
  41         printf("Generating lookup table.\n");
  42
  43         for (i = 0; i < NUM_DATA_WORDS; ++i) {
  44                 hamming_lookup[i] = generate_parity(i);
  45         }
  46 }
  47
  48 /* can detect all single or double bit errors */
  49 int has_error(unsigned code)
  50 {
  51         unsigned data = code >> PARITY_BITS;
  52         unsigned parity = code & ((1 << PARITY_BITS) - 1);
  53
  54         return (hamming_lookup[data] != parity);
  55 }
  56
  57 int has_double_error(unsigned code)
  58 {
  59         unsigned i;
  60         unsigned data = code >> PARITY_BITS;
  61         unsigned parity = code & ((1 << PARITY_BITS) - 1);
  62         unsigned gen_parity = hamming_lookup[data];
  63
  64         unsigned hamming_parity = parity >> 1;
  65         unsigned gen_hamming_parity = gen_parity >> 1;
  66         unsigned extra_parity = 0;
  67
  68         /* check the lowest parity bit */
  69         for (i = 0; i < CODE_BITS; ++i) {
  70                 extra_parity ^= (code & 1);
  71                 code >>= 1;
  72         }
  73
  74         /* no errors at all (user should have used has_error() first; boo, hiss) */
  75         if (hamming_parity == gen_hamming_parity && extra_parity == 0)
  76                 return 0;
  77
  78         /* both hamming and simple parity errors; this is a single-bit error */
  79         if (hamming_parity != gen_hamming_parity && extra_parity == 1)
  80                 return 0;
  81
  82         /* hamming says OK, but simple parity indicates an error => simple parity error is wrong */
  83         if (hamming_parity == gen_hamming_parity && extra_parity == 1)
  84                 return 0;
  85
  86         /* hamming says error, simple parity says OK => DOUBLE ERROR */
  87         return 1;
  88 }
  89
  90 void check_zero_bit_detection()
  91 {
  92         unsigned i;
  93         printf("Checking zero bit detection.\n");
  94
  95         for (i = 0; i < NUM_DATA_WORDS; ++i) {
  96                 unsigned code = make_codeword(i);
  97                 if (has_error(code)) {
  98                         printf("ERROR: Failed zero-bit test 1 for %x\n", i);
  99                 }
 100                 if (has_double_error(code)) {
 101                         printf("ERROR: Failed zero-bit test 2 for %x\n", i);
 102                 }
 103         }
 104 }
 105
 106 void check_single_bit_detection()
 107 {
 108         unsigned i, j;
 109         printf("Checking single bit detection.\n");
 110
 111         for (i = 0; i < NUM_DATA_WORDS; ++i) {
 112                 unsigned code = make_codeword(i);
 113                 for (j = 0; j < CODE_BITS; ++j) {
 114                         unsigned corrupted_code = code ^ (1 << j);
 115
 116                         if (!has_error(corrupted_code)) {
 117                                 printf("ERROR: Failed single-bit test 1 for %x with bit %u flipped\n", i, j);
 118                         }
 119                         if (has_double_error(corrupted_code)) {
 120                                 printf("ERROR: Failed single-bit test 2 for %x with bit %u flipped\n", i, j);
 121                         }
 122                 }
 123         }
 124 }
 125
 126 void check_double_bit_detection()
 127 {
 128         unsigned i, j, k;
 129         printf("Checking double bit detection.\n");
 130
 131         for (i = 0; i < NUM_DATA_WORDS; ++i) {
 132                 unsigned code = make_codeword(i);
 133                 for (j = 0; j < CODE_BITS; ++j) {
 134                         for (k = 0; k < CODE_BITS; ++k) {
 135                                 unsigned corrupted_code = code ^ (1 << j) ^ (1 << k);
 136                                 if (j == k)
 137                                         continue;
 138
 139                                 if (!has_error(corrupted_code)) {
 140                                         printf("ERROR: Failed double-bit test 1 for %x with bit %u and %u flipped\n", i, j, k);
 141                                 }
 142                                 if (!has_double_error(corrupted_code)) {
 143                                         printf("ERROR: Failed double-bit test 2 for %x with bit %u and %u flipped\n", i, j, k);
 144                                 }
 145                         }
 146                 }
 147         }
 148 }
 149
 150 int main()
 151 {
 152         generate_lookup();
 153         check_zero_bit_detection();
 154         check_single_bit_detection();
 155         check_double_bit_detection();
 156
 157         return 0;
 158 }