summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorjaseg <git-bigdata-wsl-arch@jaseg.de>2020-02-28 12:59:25 +0100
committerjaseg <git-bigdata-wsl-arch@jaseg.de>2020-02-28 12:59:25 +0100
commit9cf1fee2e9f625ca6787e3b14c759be43ea663e6 (patch)
tree01050612fd6c015e5e6c511b6a70526e75ac20a4
parentf6061fe574166b7d23b208f047e8789081877c57 (diff)
downloadmaster-thesis-9cf1fee2e9f625ca6787e3b14c759be43ea663e6.tar.gz
master-thesis-9cf1fee2e9f625ca6787e3b14c759be43ea663e6.tar.bz2
master-thesis-9cf1fee2e9f625ca6787e3b14c759be43ea663e6.zip
ldpc decoder: wip
-rw-r--r--controller/fw/ldpc_decoder.c152
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)