5 #define CODE_BITS (DATA_BITS + PARITY_BITS)
6 #define NUM_DATA_WORDS (1 << DATA_BITS)
8 unsigned char hamming_lookup[NUM_DATA_WORDS];
10 unsigned generate_parity(unsigned data)
12 unsigned bits[DATA_BITS];
13 unsigned parity[PARITY_BITS];
18 for (i = 0; i < DATA_BITS; ++i) {
19 bits[i] = (data & (1 << i)) ? 1 : 0;
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];
29 return parity[4] | (parity[3] << 1) | (parity[2] << 2) | (parity[1] << 3) | (parity[0] << 4);
32 unsigned make_codeword(unsigned data)
34 return (data << PARITY_BITS) | hamming_lookup[data];
37 void generate_lookup()
41 printf("Generating lookup table.\n");
43 for (i = 0; i < NUM_DATA_WORDS; ++i) {
44 hamming_lookup[i] = generate_parity(i);
48 /* can detect all single or double bit errors */
49 int has_error(unsigned code)
51 unsigned data = code >> PARITY_BITS;
52 unsigned parity = code & ((1 << PARITY_BITS) - 1);
54 return (hamming_lookup[data] != parity);
57 int has_double_error(unsigned code)
60 unsigned data = code >> PARITY_BITS;
61 unsigned parity = code & ((1 << PARITY_BITS) - 1);
62 unsigned gen_parity = hamming_lookup[data];
64 unsigned hamming_parity = parity >> 1;
65 unsigned gen_hamming_parity = gen_parity >> 1;
66 unsigned extra_parity = 0;
68 /* check the lowest parity bit */
69 for (i = 0; i < CODE_BITS; ++i) {
70 extra_parity ^= (code & 1);
74 /* no errors at all (user should have used has_error() first; boo, hiss) */
75 if (hamming_parity == gen_hamming_parity && extra_parity == 0)
78 /* both hamming and simple parity errors; this is a single-bit error */
79 if (hamming_parity != gen_hamming_parity && extra_parity == 1)
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)
86 /* hamming says error, simple parity says OK => DOUBLE ERROR */
90 void check_zero_bit_detection()
93 printf("Checking zero bit detection.\n");
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);
100 if (has_double_error(code)) {
101 printf("ERROR: Failed zero-bit test 2 for %x\n", i);
106 void check_single_bit_detection()
109 printf("Checking single bit detection.\n");
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);
116 if (!has_error(corrupted_code)) {
117 printf("ERROR: Failed single-bit test 1 for %x with bit %u flipped\n", i, j);
119 if (has_double_error(corrupted_code)) {
120 printf("ERROR: Failed single-bit test 2 for %x with bit %u flipped\n", i, j);
126 void check_double_bit_detection()
129 printf("Checking double bit detection.\n");
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);
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);
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);
153 check_zero_bit_detection();
154 check_single_bit_detection();
155 check_double_bit_detection();