1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
"""Decoding module."""
/* H: decoding matrix as shape (m, n) array
* m: number of equations represented by H
* n: number of code words
* y: received message in codeword space, length n
*
* out: output array of length n where the solutions in codeword space will be written
*
* maxiter: Maximum iteration number
*/
int decode(uint8_t H[], const int m, n, uint8_t y[], uint8_t out[], int maxiter) {
/* fixme: preprocess the following.
def bitsandnodes(H):
"""Return bits and nodes of a parity-check matrix H."""
bits_indices, bits = scipy.sparse.find(H)[:2]
nodes_indices, nodes = scipy.sparse.find(H.T)[:2]
bits_histogram = np.bincount(bits_indices)
nodes_histogram = np.bincount(nodes_indices)
return bits_histogram, bits, nodes_histogram, nodes
bits_hist, bits_values, nodes_hist, nodes_values = utils.bitsandnodes(H)
*/
float Lq[m*n];
float Lr[m*n];
float L_posteriori[n];
for (int n_iter=0; n_iter<maxiter; n_iter++) {
Lq, Lr, L_posteriori = inner_logbp(bits_hist, bits_values, nodes_hist,
nodes_values, y, Lq, Lr, n_iter, L_posteriori)
for (size_t i=0; i<n; i++)
out[i] = L_posteriori[i] <= 0.0f;
for (size_t i=0; i<m; i++) {
bool sum = 0;
for (size_t j=0; j<n; j++)
sum ^= H[i*n + j] * out[j];
if (sum)
continue;
}
return 1;
}
return -1;
}
/* Perform inner ext LogBP solver */
void inner_logbp(
size_t m, n,
int bits_hist[], bits_values[], nodes_hist[], nodes_values[],
uint8_t Lc[],
float Lq[], Lr[],
int n_iter,
float L_posteriori_out[]) {
/* step 1 : Horizontal */
int bits_counter = 0;
int nodes_counter = 0;
for (size_t i=0; i<m; i++) {
int ff = bits_hist[i];
bits_counter += ff;
for (size_t p=bits_counter; p<bits_counter+ff; p++) {
int j = bits_values[p];
float x = 1;
if (n_iter == 0) {
for (size_t q=bits_counter; q<bits_counter+ff; q++) {
if (bits_values[q] != j)
x *= tanhf(0.5f * Lc[bits_values[q]]);
}
} else {
for (size_t q=bits_counter; q<bits_counter+ff; q++) {
if (bits_values[q] != j)
x *= tanhf(0.5f * Lq[i, bits_values[q]]);
}
}
float num = 1 + x;
float denom = 1 - x;
if (num == 0)
Lr[i*n + j] = -1.0f;
else if (denom == 0)
Lr[i*n + j] = 1.0f;
else
Lr[i*n + j] = logf(num/denom);
}
}
/* step 2 : Vertical */
for (size_t j=0; j<n; j++) {
ff = nodes_hist[j];
for (size_t p=bits_counter; p<nodes_counter+ff; p++) {
int i = nodes_values[p];
Lq[i, j] = Lc[j]
for (size_t q=bits_counter; q<nodes_counter+ff; q++) {
if (nodes_values[q] != i)
Lq[i, j] += Lr[nodes_values[q], j];
}
}
nodes_counter += ff;
}
/* LLR a posteriori */
size_t nodes_counter = 0;
for (size_t j=0; j<n; j++) {
size_t ff = nodes_hist[j];
float sum = 0;
for (size_t k=bits_counter; k<nodes_counter+ff; k++)
sum += Lr[nodes_values[k]*n + j];
nodes_counter += ff;
L_posteriori_out[j] = Lc[j] + sum;
}
}
def get_message(tG, x):
"""Compute the original `n_bits` message from a `n_code` codeword `x`.
Parameters
----------
tG: array (n_code, n_bits) coding matrix tG.
x: array (n_code,) decoded codeword of length `n_code`.
Returns
-------
message: array (n_bits,). Original binary message.
"""
n, k = tG.shape
rtG, rx = utils.gausselimination(tG, x)
message = np.zeros(k).astype(int)
message[k - 1] = rx[k - 1]
for i in reversed(range(k - 1)):
message[i] = rx[i]
message[i] -= utils.binaryproduct(rtG[i, list(range(i+1, k))],
message[list(range(i+1, k))])
return abs(message)
|
