1 #include "hamming_16_11.h"
2
3 /*
4 generator matrix accodring to etsi B.3.4
5
6 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1
7 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0
8 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1
9 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0
10 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0
11 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1
12 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1
13 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0
14 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1
15 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1
16 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1
17
18 parity check matrix according to H = [-PT|In-k]
19
20 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 0
21 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
22 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0
23 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 0
24 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 1
25 */
26
27 // parity check matrix as code
28 uint16_t hamming_16_11_parity_check_matrix[] = {
29 0b1111010110010000,
30 0b0111101011001000,
31 0b0011110101100100,
32 0b1110101100100010,
33 0b1010011011100001
34 };
35
36 struct correction {
37 uint16_t syndrome;
38 uint16_t error_pattern;
39 };
40
41 // generated by applying possible combinations of errors
42 static struct correction corrections[] = {
43 { 1, 1 },
44 { 2, 2 },
45 { 4, 4 },
46 { 8, 8 },
47 { 16, 16 },
48 { 7, 32 },
49 { 13, 64 },
50 { 25, 128 },
51 { 22, 256 },
52 { 11, 512 },
53 { 21, 1024 },
54 { 14, 2048 },
55 { 28, 4096 },
56 { 31, 8192 },
57 { 26, 16384 },
58 { 19, 32768 }
59 };
60
hamming_16_11_parity(uint16_t * data)61 uint16_t hamming_16_11_parity(uint16_t* data) {
62 uint16_t parity = 0;
63
64 uint8_t k;
65 for (k = 0; k < 5; k++) {
66 uint8_t bit = 0, l;
67 for (l = 0; l < 16; l++) {
68 if ((hamming_16_11_parity_check_matrix[k] >> l) & 1) {
69 bit ^= ((*data >> l) & 1);
70 }
71 }
72
73 parity = (parity << 1) | (bit & 1);
74 }
75
76 return parity;
77 }
78
hamming_16_11(uint16_t * data)79 bool hamming_16_11(uint16_t* data) {
80 uint16_t parity = hamming_16_11_parity(data);
81
82 if (parity == 0) return true;
83
84 int num_corrections = sizeof(corrections)/sizeof(corrections[0]);
85 for (int i = 0; i < num_corrections; i++) {
86 if (corrections[i].syndrome == parity) {
87 *data = *data ^ corrections[i].error_pattern;
88 return true;
89 }
90 }
91
92 return false;
93 }
94