5 #define CODE_BITS (DATA_BITS + PARITY_BITS)
6 #define NUM_DATA_WORDS (1 << DATA_BITS)
8 unsigned char hamming_lookup[NUM_DATA_WORDS];
11 * Needed since we store all the parity at the end of the word, not at the expected
12 * power-of-two bit positions.
14 unsigned char permutation_table[CODE_BITS] = {
15 0, 4, 3, 5, 2, 6, 7, 8, 1, 9, 10, 11, 12, 13, 14, 15
18 unsigned generate_parity(unsigned data)
20 unsigned bits[DATA_BITS];
21 unsigned parity[PARITY_BITS];
26 for (i = 0; i < DATA_BITS; ++i) {
27 bits[i] = (data & (1 << i)) ? 1 : 0;
31 parity[0] = bits[0] ^ bits[1] ^ bits[3] ^ bits[4] ^ bits[6] ^ bits[8] ^ bits[10];
32 parity[1] = bits[0] ^ bits[2] ^ bits[3] ^ bits[5] ^ bits[6] ^ bits[9] ^ bits[10];
33 parity[2] = bits[1] ^ bits[2] ^ bits[3] ^ bits[7] ^ bits[8] ^ bits[9] ^ bits[10];
34 parity[3] = bits[4] ^ bits[5] ^ bits[6] ^ bits[7] ^ bits[8] ^ bits[9] ^ bits[10];
35 parity[4] ^= parity[0] ^ parity[1] ^ parity[2] ^ parity[3];
37 return parity[4] | (parity[3] << 1) | (parity[2] << 2) | (parity[1] << 3) | (parity[0] << 4);
40 unsigned make_codeword(unsigned data)
42 return (data << PARITY_BITS) | hamming_lookup[data];
45 void generate_lookup()
49 printf("Generating lookup table.\n");
51 for (i = 0; i < NUM_DATA_WORDS; ++i) {
52 hamming_lookup[i] = generate_parity(i);
56 /* can detect all single or double bit errors */
57 int has_error(unsigned code)
59 unsigned data = code >> PARITY_BITS;
60 unsigned parity = code & ((1 << PARITY_BITS) - 1);
62 return (hamming_lookup[data] != parity);
65 int has_double_error(unsigned code)
68 unsigned data = code >> PARITY_BITS;
69 unsigned parity = code & ((1 << PARITY_BITS) - 1);
70 unsigned gen_parity = hamming_lookup[data];
72 unsigned hamming_parity = parity >> 1;
73 unsigned gen_hamming_parity = gen_parity >> 1;
74 unsigned extra_parity = 0;
76 /* check the lowest parity bit */
77 for (i = 0; i < CODE_BITS; ++i) {
78 extra_parity ^= (code & 1);
82 /* no errors at all (user should have used has_error() first; boo, hiss) */
83 if (hamming_parity == gen_hamming_parity && extra_parity == 0)
86 /* both hamming and simple parity errors; this is a single-bit error */
87 if (hamming_parity != gen_hamming_parity && extra_parity == 1)
90 /* hamming says OK, but simple parity indicates an error => simple parity error is wrong */
91 if (hamming_parity == gen_hamming_parity && extra_parity == 1)
94 /* hamming says error, simple parity says OK => DOUBLE ERROR */
98 /* Correct any single-bit error -- assumes there are no double-bit errors */
99 unsigned correct_single_bit_error(unsigned code)
101 unsigned bits[CODE_BITS];
102 unsigned parity[PARITY_BITS];
107 for (i = 0; i < CODE_BITS; ++i) {
108 bits[i] = (code & (1 << i)) ? 1 : 0;
110 for (i = 1; i < CODE_BITS; ++i) {
111 parity[4] ^= bits[i];
114 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];
115 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];
116 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];
117 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 for (i = 0; i < PARITY_BITS - 1; ++i) {
120 if (parity[i] != bits[PARITY_BITS - 1 - i]) {
126 /* flip the wrong bit */
127 code ^= (1 << permutation_table[bp]);
131 /* recompute the lower parity */
132 return (code & ~1) | parity[4];
135 void check_zero_bit_detection()
138 printf("Checking zero bit detection.\n");
140 for (i = 0; i < NUM_DATA_WORDS; ++i) {
141 unsigned code = make_codeword(i);
142 if (has_error(code)) {
143 printf("ERROR: Failed zero-bit test 1 for %x\n", i);
145 if (has_double_error(code)) {
146 printf("ERROR: Failed zero-bit test 2 for %x\n", i);
151 void check_single_bit_detection()
154 printf("Checking single bit detection and correction.\n");
156 for (i = 0; i < NUM_DATA_WORDS; ++i) {
157 unsigned code = make_codeword(i);
158 for (j = 0; j < CODE_BITS; ++j) {
159 unsigned corrupted_code = code ^ (1 << j);
161 if (!has_error(corrupted_code)) {
162 printf("ERROR: Failed single-bit test 1 for %x with bit %u flipped\n", i, j);
164 if (has_double_error(corrupted_code)) {
165 printf("ERROR: Failed single-bit test 2 for %x with bit %u flipped\n", i, j);
167 if (correct_single_bit_error(corrupted_code) != code) {
168 printf("ERROR: Failed single-bit correction test for %x with bit %u flipped\n", i, j);
174 void check_double_bit_detection()
177 printf("Checking double bit detection.\n");
179 for (i = 0; i < NUM_DATA_WORDS; ++i) {
180 unsigned code = make_codeword(i);
181 for (j = 0; j < CODE_BITS; ++j) {
182 for (k = 0; k < CODE_BITS; ++k) {
183 unsigned corrupted_code = code ^ (1 << j) ^ (1 << k);
187 if (!has_error(corrupted_code)) {
188 printf("ERROR: Failed double-bit test 1 for %x with bit %u and %u flipped\n", i, j, k);
190 if (!has_double_error(corrupted_code)) {
191 printf("ERROR: Failed double-bit test 2 for %x with bit %u and %u flipped\n", i, j, k);
201 check_zero_bit_detection();
202 check_single_bit_detection();
203 check_double_bit_detection();