diff options
| -rw-r--r-- | controller/fw/ldpc_decoder.c | 152 |
1 files changed, 152 insertions, 0 deletions
diff --git a/controller/fw/ldpc_decoder.c b/controller/fw/ldpc_decoder.c new file mode 100644 index 0000000..5200e8f --- /dev/null +++ b/controller/fw/ldpc_decoder.c @@ -0,0 +1,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) |