diff options
| author | jaseg <git-bigdata-wsl-arch@jaseg.de> | 2020-02-28 18:29:41 +0100 |
|---|---|---|
| committer | jaseg <git-bigdata-wsl-arch@jaseg.de> | 2020-02-28 18:29:41 +0100 |
| commit | 89b32316aa46f22a4f967ca7953089a3df0c16e7 (patch) | |
| tree | fddb3fd4538d3a52ab7a23a9275497f824d482bc | |
| parent | 9cf1fee2e9f625ca6787e3b14c759be43ea663e6 (diff) | |
| download | master-thesis-89b32316aa46f22a4f967ca7953089a3df0c16e7.tar.gz master-thesis-89b32316aa46f22a4f967ca7953089a3df0c16e7.tar.bz2 master-thesis-89b32316aa46f22a4f967ca7953089a3df0c16e7.zip | |
embedded ldpc decoder 50% working
| -rw-r--r-- | controller/fw/Makefile | 5 | ||||
| -rw-r--r-- | controller/fw/ldpc_decoder.c | 197 | ||||
| -rw-r--r-- | controller/fw/ldpc_decoder_test.py | 53 | ||||
| -rw-r--r-- | controller/fw/test_decoder.py | 167 | ||||
| -rw-r--r-- | controller/fw/test_pyldpc_utils.py | 182 | ||||
| -rw-r--r-- | lab-windows/fec_experiments.ipynb | 416 |
6 files changed, 925 insertions, 95 deletions
diff --git a/controller/fw/Makefile b/controller/fw/Makefile index e2f0f4c..291f840 100644 --- a/controller/fw/Makefile +++ b/controller/fw/Makefile @@ -50,7 +50,7 @@ CFLAGS += -nostdlib -ffreestanding CFLAGS += -mthumb -mcpu=cortex-m4 -mfloat-abi=hard -mfpu=fpv4-sp-d16 CFLAGS += -fno-common -ffunction-sections -fdata-sections -INT_CFLAGS += -Wall -Wextra -Wshadow -Wimplicit-function-declaration -Wundef +INT_CFLAGS += -Wall -Wextra -Wpedantic -Wshadow -Wimplicit-function-declaration -Wundef INT_CFLAGS += -Wredundant-decls -Wmissing-prototypes -Wstrict-prototypes CXXFLAGS += -Os -g @@ -97,6 +97,9 @@ $(BUILDDIR)/tinyaes/aes.o: mkdir -p $(@D) make -C $(@D) -f $(TINYAES_DIR_ABS)/Makefile VPATH=$(TINYAES_DIR_ABS) CFLAGS="$(CFLAGS) -c" CC=$(CC) LD=$(LD) AR=$(AR) aes.o +ldpc_decoder_test.so: ldpc_decoder.c + gcc -fPIC -shared -Wall -Wextra -Wpedantic -std=gnu11 -O0 -g -o $@ $^ + clean: -rm -r $(BUILDDIR)/src -rm $(BUILDDIR)/$(BINARY) diff --git a/controller/fw/ldpc_decoder.c b/controller/fw/ldpc_decoder.c index 5200e8f..10b5a08 100644 --- a/controller/fw/ldpc_decoder.c +++ b/controller/fw/ldpc_decoder.c @@ -1,86 +1,160 @@ -"""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) - */ +#include <stdint.h> +#include <unistd.h> +#include <stdbool.h> +#include <math.h> +#include <stdio.h> + +void inner_logbp( + size_t m, size_t n, + size_t bits_count, size_t nodes_count, const uint32_t bits_values[], const uint32_t nodes_values[], + int8_t Lc[], + float Lq[], float Lr[], + unsigned int n_iter, + float L_posteriori_out[]); + +//decode(384, 6, 8, ...) +int decode(size_t n, size_t nodes_count, size_t bits_count, uint32_t bits[], int8_t y[], int8_t out[], unsigned int maxiter) { + const size_t m = n * nodes_count / bits_count; 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) + /* Calculate column bit positions from row bit positions */ + int32_t bits_transposed[nodes_count * n]; + for (size_t i=0; i<nodes_count * n; i++) + bits_transposed[i] = -1; + + for (size_t i=0; i<m; i++) { + for (size_t j=0; j<bits_count; j++) { + int32_t *base = bits_transposed + bits[i*bits_count + j] * nodes_count; + for (; *base != -1; base++) + ; + *base = i; + } + } + + /* + printf("Row positions: ["); + for (size_t i=0; i<m*bits_count; i++) { + if (i) + printf(", "); + if (i%32 == 0) + printf("\n "); + printf("%4d", bits[i]); + } + printf("\n]\n"); + + printf("Column positions: ["); + for (size_t i=0; i<n*nodes_count; i++) { + if (i) + printf(", "); + if (i%32 == 0) + printf("\n "); + printf("%4d", bits_transposed[i]); + } + printf("\n]\n"); + */ + + /* Run iterative optimization algorithm */ + for (unsigned int n_iter=0; n_iter<maxiter; n_iter++) { + inner_logbp(m, n, bits_count, nodes_count, bits, (uint32_t*)bits_transposed, y, Lq, Lr, n_iter, L_posteriori); + + float *arrs[3] = {Lq, Lr, L_posteriori}; + const char *names[3] = {"Lq", "Lr", "L_posteriori"}; + size_t lens[3] = {m*n, m*n, n}; + const size_t head_tail = 10; + for (int j=0; j<3; j++) { + printf("%s=[", names[j]); + bool ellipsis = false; + const int w = 16; + for (size_t i=0; i<lens[j]; i++) { + if (lens[j] > 1000 && i/w > head_tail && i/w < m*n/w-head_tail) { + if (!ellipsis) { + ellipsis = true; + printf("\n ..."); + } + continue; + } + if (i) + printf(", "); + if (i%w == 0) + printf("\n "); + float outf = arrs[j][i]; + char *s = outf < 0 ? "\033[91m" : (outf > 0 ? "\033[92m" : "\033[94m"); + printf("%s% 012.6g\033[38;5;240m", s, outf); + } + printf("\n]\n"); + } + 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]; - + for (size_t j=0; j<bits_count; j++) + sum ^= out[bits[i*bits_count + j]]; if (sum) continue; } - return 1; + fflush(stdout); + return n_iter; } - + + fflush(stdout); 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, + size_t m, size_t n, + size_t bits_count, size_t nodes_count, uint32_t const bits_values[], const uint32_t nodes_values[], + int8_t Lc[], + float Lq[], float Lr[], + unsigned int n_iter, float L_posteriori_out[]) { + /* + printf("Input data: ["); + for (size_t i=0; i<n; i++) { + if (i) + printf(", "); + if (i%32 == 0) + printf("\n "); + printf("%4d", Lc[i]); + } + printf("\n]\n"); + */ + /* step 1 : Horizontal */ - int bits_counter = 0; - int nodes_counter = 0; + unsigned int bits_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]; + printf("=== i=%zu\n", i); + for (size_t p=bits_counter; p<bits_counter+bits_count; p++) { + size_t j = bits_values[p]; + printf("\033[38;5;240mj=%04zd ", j); float x = 1; if (n_iter == 0) { - for (size_t q=bits_counter; q<bits_counter+ff; q++) { - if (bits_values[q] != j) + for (size_t q=bits_counter; q<bits_counter+bits_count; q++) { + if (bits_values[q] != j) { + int lcv = Lc[bits_values[q]]; + char *s = lcv < 0 ? "\033[91m" : (lcv > 0 ? "\033[92m" : "\033[94m"); + printf("nij=%04u Lc=%s%3d\033[38;5;240m ", bits_values[q], s, lcv); x *= tanhf(0.5f * Lc[bits_values[q]]); + } } } else { - for (size_t q=bits_counter; q<bits_counter+ff; q++) { + for (size_t q=bits_counter; q<bits_counter+bits_count; q++) { if (bits_values[q] != j) - x *= tanhf(0.5f * Lq[i, bits_values[q]]); + x *= tanhf(0.5f * Lq[i*n + bits_values[q]]); } } + printf("\n==== i=%03zd p=%01zd x=%08f\n", i, p-bits_counter, x); + float num = 1 + x; float denom = 1 - x; if (num == 0) @@ -90,40 +164,40 @@ void inner_logbp( else Lr[i*n + j] = logf(num/denom); } + + bits_counter += bits_count; } /* step 2 : Vertical */ + unsigned int nodes_counter = 0; 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]; + for (size_t p=bits_counter; p<nodes_counter+nodes_count; p++) { + size_t i = nodes_values[p]; - Lq[i, j] = Lc[j] + Lq[i*n + j] = Lc[j]; - for (size_t q=bits_counter; q<nodes_counter+ff; q++) { + for (size_t q=bits_counter; q<nodes_counter+nodes_count; q++) { if (nodes_values[q] != i) - Lq[i, j] += Lr[nodes_values[q], j]; + Lq[i*n + j] += Lr[nodes_values[q]*n + j]; } } - nodes_counter += ff; + nodes_counter += nodes_count; } /* LLR a posteriori */ - size_t nodes_counter = 0; + 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++) + for (size_t k=bits_counter; k<nodes_counter+nodes_count; k++) sum += Lr[nodes_values[k]*n + j]; - nodes_counter += ff; + nodes_counter += nodes_count; L_posteriori_out[j] = Lc[j] + sum; } } - +/* TODO def get_message(tG, x): """Compute the original `n_bits` message from a `n_code` codeword `x`. @@ -150,3 +224,4 @@ def get_message(tG, x): message[list(range(i+1, k))]) return abs(message) +*/ diff --git a/controller/fw/ldpc_decoder_test.py b/controller/fw/ldpc_decoder_test.py new file mode 100644 index 0000000..d5cbb24 --- /dev/null +++ b/controller/fw/ldpc_decoder_test.py @@ -0,0 +1,53 @@ + +import pyldpc +import scipy.sparse +import numpy as np +import test_decoder +import os, sys +import ctypes as C +import argparse + +if __name__ != '__main__': + raise RuntimeError("Please don't import this module, this is a command-line program.") + +parser = argparse.ArgumentParser() +parser.add_argument('-r', '--reference', action='store_true', default=False, help='Run reference decoder instead of C implemention') +args = parser.parse_args() + +lib = C.CDLL('./ldpc_decoder_test.so') + +n = 384 +nodes, bits = 6, 8 +H, G = pyldpc.make_ldpc(n, nodes, bits, systematic=False, seed=0) +_1, bits_pos, _2 = scipy.sparse.find(H) +_, k = G.shape + +st = np.random.RandomState(seed=0) +test_data = st.randint(0, 2, k) +d = np.dot(G, test_data) % 2 +x = (-1) ** d + +bits_pos = bits_pos.astype(np.uint32) +x = x.astype(np.int8) + +lib.decode.argtypes = [C.c_size_t, C.c_size_t, C.c_size_t, C.POINTER(C.c_size_t), C.POINTER(C.c_int8), C.POINTER(C.c_int8), C.c_uint] + +if args.reference: + ref_out = test_decoder.decode(H, x, 3) + print('decoder output:', ref_out, flush=True) + print('msg reconstruction:', pyldpc.get_message(G, ref_out)) + print('reference decoder: ', np.all(np.equal(pyldpc.get_message(G, ref_out), test_data)), flush=True) + print(ref_out.dtype) + +else: + out = np.zeros(n, dtype=np.uint8) + # print('python data:', x, flush=True) + print('decoder iterations:', lib.decode(n, nodes, bits, + bits_pos.ctypes.data_as(C.POINTER(C.c_ulong)), + x.ctypes.data_as(C.POINTER(C.c_int8)), + out.ctypes.data_as(C.POINTER(C.c_int8)), + 25), flush=True) + print('decoder output:', out) + print('msg reconstruction:', pyldpc.get_message(G, out)) + print('decoder under test:', np.all(np.equal(pyldpc.get_message(G, out.astype(np.int64)), test_data))) + print(out.dtype) diff --git a/controller/fw/test_decoder.py b/controller/fw/test_decoder.py new file mode 100644 index 0000000..806125b --- /dev/null +++ b/controller/fw/test_decoder.py @@ -0,0 +1,167 @@ +"""Decoding module.""" +import numpy as np +import warnings +import test_pyldpc_utils as utils + +from numba import njit, int64, types, float64 + +np.set_printoptions(linewidth=180, threshold=1000, edgeitems=20) + +def decode(H, y, snr, maxiter=100): + """Decode a Gaussian noise corrupted n bits message using BP algorithm. + + Decoding is performed in parallel if multiple codewords are passed in y. + + Parameters + ---------- + H: array (n_equations, n_code). Decoding matrix H. + y: array (n_code, n_messages) or (n_code,). Received message(s) in the + codeword space. + maxiter: int. Maximum number of iterations of the BP algorithm. + + Returns + ------- + x: array (n_code,) or (n_code, n_messages) the solutions in the + codeword space. + + """ + m, n = H.shape + + bits_hist, bits_values, nodes_hist, nodes_values = utils.bitsandnodes(H) + + var = 10 ** (-snr / 10) + + if y.ndim == 1: + y = y[:, None] + # step 0: initialization + + Lc = 2 * y / var + _, n_messages = y.shape + + Lq = np.zeros(shape=(m, n, n_messages)) + + Lr = np.zeros(shape=(m, n, n_messages)) + + for n_iter in range(maxiter): + print(f'============================ iteration {n_iter} ============================') + Lq, Lr, L_posteriori = _logbp_numba(bits_hist, bits_values, nodes_hist, + nodes_values, Lc, Lq, Lr, n_iter) + print("Lq=", Lq.flatten()) + print("Lr=", Lr.flatten()) + #print("L_posteriori=", L_posteriori.flatten()) + print('L_posteriori=[') + for row in L_posteriori.reshape([-1, 16]): + for val in row: + cc = '\033[91m' if val < 0 else ('\033[92m' if val > 0 else '\033[94m') + print(f"{cc}{val: 012.6g}\033[38;5;240m", end=', ') + print() + x = np.array(L_posteriori <= 0).astype(int) + + product = utils.incode(H, x) + + if product: + break + + if n_iter == maxiter - 1: + warnings.warn("""Decoding stopped before convergence. You may want + to increase maxiter""") + return x.squeeze() + + +output_type_log2 = types.Tuple((float64[:, :, :], float64[:, :, :], + float64[:, :])) + + +#@njit(output_type_log2(int64[:], int64[:], int64[:], int64[:], float64[:, :], +# float64[:, :, :], float64[:, :, :], int64), cache=True) +def _logbp_numba(bits_hist, bits_values, nodes_hist, nodes_values, Lc, Lq, Lr, + n_iter): + """Perform inner ext LogBP solver.""" + m, n, n_messages = Lr.shape + # step 1 : Horizontal + + bits_counter = 0 + nodes_counter = 0 + for i in range(m): + print(f'=== i={i}') + ff = bits_hist[i] + ni = bits_values[bits_counter: bits_counter + ff] + bits_counter += ff + for j_iter, j in enumerate(ni): + nij = ni[:] + print(f'\033[38;5;240mj={j:04d}', end=' ') + + X = np.ones(n_messages) + if n_iter == 0: + for kk in range(len(nij)): + if nij[kk] != j: + lcv = Lc[nij[kk],0] + lcc = '\033[91m' if lcv < 0 else ('\033[92m' if lcv > 0 else '\033[94m') + print(f'nij={nij[kk]:04d} Lc={lcc}{lcv:> 8f}\033[38;5;240m', end=' ') + X *= np.tanh(0.5 * Lc[nij[kk]]) + else: + for kk in range(len(nij)): + if nij[kk] != j: + X *= np.tanh(0.5 * Lq[i, nij[kk]]) + print(f'\n==== {i:03d} {j_iter:01d} {X[0]:> 8f}') + num = 1 + X + denom = 1 - X + for ll in range(n_messages): + if num[ll] == 0: + Lr[i, j, ll] = -1 + elif denom[ll] == 0: + Lr[i, j, ll] = 1 + else: + Lr[i, j, ll] = np.log(num[ll] / denom[ll]) + # step 2 : Vertical + + for j in range(n): + ff = nodes_hist[j] + mj = nodes_values[bits_counter: nodes_counter + ff] + nodes_counter += ff + for i in mj: + mji = mj[:] + Lq[i, j] = Lc[j] + + for kk in range(len(mji)): + if mji[kk] != i: + Lq[i, j] += Lr[mji[kk], j] + + # LLR a posteriori: + L_posteriori = np.zeros((n, n_messages)) + nodes_counter = 0 + for j in range(n): + ff = nodes_hist[j] + mj = nodes_values[bits_counter: nodes_counter + ff] + nodes_counter += ff + L_posteriori[j] = Lc[j] + Lr[mj, j].sum(axis=0) + + return Lq, Lr, L_posteriori + + +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) diff --git a/controller/fw/test_pyldpc_utils.py b/controller/fw/test_pyldpc_utils.py new file mode 100644 index 0000000..6b14532 --- /dev/null +++ b/controller/fw/test_pyldpc_utils.py @@ -0,0 +1,182 @@ +"""Conversion tools.""" +import math +import numbers +import numpy as np +import scipy +from scipy.stats import norm +pi = math.pi + + +def int2bitarray(n, k): + """Change an array's base from int (base 10) to binary (base 2).""" + binary_string = bin(n) + length = len(binary_string) + bitarray = np.zeros(k, 'int') + for i in range(length - 2): + bitarray[k - i - 1] = int(binary_string[length - i - 1]) + + return bitarray + + +def bitarray2int(bitarray): + """Change array's base from binary (base 2) to int (base 10).""" + bitstring = "".join([str(i) for i in bitarray]) + + return int(bitstring, 2) + + +def binaryproduct(X, Y): + """Compute a matrix-matrix / vector product in Z/2Z.""" + A = X.dot(Y) + try: + A = A.toarray() + except AttributeError: + pass + return A % 2 + + +def gaussjordan(X, change=0): + """Compute the binary row reduced echelon form of X. + + Parameters + ---------- + X: array (m, n) + change : boolean (default, False). If True returns the inverse transform + + Returns + ------- + if `change` == 'True': + A: array (m, n). row reduced form of X. + P: tranformations applied to the identity + else: + A: array (m, n). row reduced form of X. + + """ + A = np.copy(X) + m, n = A.shape + + if change: + P = np.identity(m).astype(int) + + pivot_old = -1 + for j in range(n): + filtre_down = A[pivot_old+1:m, j] + pivot = np.argmax(filtre_down)+pivot_old+1 + + if A[pivot, j]: + pivot_old += 1 + if pivot_old != pivot: + aux = np.copy(A[pivot, :]) + A[pivot, :] = A[pivot_old, :] + A[pivot_old, :] = aux + if change: + aux = np.copy(P[pivot, :]) + P[pivot, :] = P[pivot_old, :] + P[pivot_old, :] = aux + + for i in range(m): + if i != pivot_old and A[i, j]: + if change: + P[i, :] = abs(P[i, :]-P[pivot_old, :]) + A[i, :] = abs(A[i, :]-A[pivot_old, :]) + + if pivot_old == m-1: + break + + if change: + return A, P + return A + + +def binaryrank(X): + """Compute rank of a binary Matrix using Gauss-Jordan algorithm.""" + A = np.copy(X) + m, n = A.shape + + A = gaussjordan(A) + + return sum([a.any() for a in A]) + + +def f1(y, sigma): + """Compute normal density N(1,sigma).""" + f = norm.pdf(y, loc=1, scale=sigma) + return f + + +def fm1(y, sigma): + """Compute normal density N(-1,sigma).""" + + f = norm.pdf(y, loc=-1, scale=sigma) + return f + + +def bitsandnodes(H): + """Return bits and nodes of a parity-check matrix H.""" + if type(H) != scipy.sparse.csr_matrix: + bits_indices, bits = np.where(H) + nodes_indices, nodes = np.where(H.T) + else: + 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 + + +def incode(H, x): + """Compute Binary Product of H and x.""" + return (binaryproduct(H, x) == 0).all() + + +def gausselimination(A, b): + """Solve linear system in Z/2Z via Gauss Gauss elimination.""" + if type(A) == scipy.sparse.csr_matrix: + A = A.toarray().copy() + else: + A = A.copy() + b = b.copy() + n, k = A.shape + + for j in range(min(k, n)): + listedepivots = [i for i in range(j, n) if A[i, j]] + if len(listedepivots): + pivot = np.min(listedepivots) + else: + continue + if pivot != j: + aux = (A[j, :]).copy() + A[j, :] = A[pivot, :] + A[pivot, :] = aux + + aux = b[j].copy() + b[j] = b[pivot] + b[pivot] = aux + + for i in range(j+1, n): + if A[i, j]: + A[i, :] = abs(A[i, :]-A[j, :]) + b[i] = abs(b[i]-b[j]) + + return A, b + + +def check_random_state(seed): + """Turn seed into a np.random.RandomState instance + Parameters + ---------- + seed : None | int | instance of RandomState + If seed is None, return the RandomState singleton used by np.random. + If seed is an int, return a new RandomState instance seeded with seed. + If seed is already a RandomState instance, return it. + Otherwise raise ValueError. + """ + if seed is None or seed is np.random: + return np.random.mtrand._rand + if isinstance(seed, numbers.Integral): + return np.random.RandomState(seed) + if isinstance(seed, np.random.RandomState): + return seed + raise ValueError('%r cannot be used to seed a numpy.random.RandomState' + ' instance' % seed) diff --git a/lab-windows/fec_experiments.ipynb b/lab-windows/fec_experiments.ipynb index e17e560..348119b 100644 --- a/lab-windows/fec_experiments.ipynb +++ b/lab-windows/fec_experiments.ipynb @@ -2,19 +2,20 @@ "cells": [ { "cell_type": "code", - "execution_count": 30, + "execution_count": 92, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import matplotlib\n", "from matplotlib import pyplot as plt\n", - "import pyldpc" + "import pyldpc\n", + "import scipy.sparse" ] }, { "cell_type": "code", - "execution_count": 31, + "execution_count": 93, "metadata": {}, "outputs": [], "source": [ @@ -23,25 +24,25 @@ }, { "cell_type": "code", - "execution_count": 92, + "execution_count": 115, "metadata": {}, "outputs": [], "source": [ - "H, G = pyldpc.make_ldpc(1024, 6, 8, systematic=False)" + "H, G = pyldpc.make_ldpc(384, 6, 8, systematic=False, seed=0)" ] }, { "cell_type": "code", - "execution_count": 95, + "execution_count": 116, "metadata": {}, "outputs": [ { "data": { "text/plain": [ - "(1024, 261)" + "(384, 101)" ] }, - "execution_count": 95, + "execution_count": 116, "metadata": {}, "output_type": "execute_result" } @@ -53,21 +54,13 @@ }, { "cell_type": "code", - "execution_count": 94, + "execution_count": 117, "metadata": {}, "outputs": [ { - "name": "stderr", - "output_type": "stream", - "text": [ - "<ipython-input-94-bc8d2a92108c>:1: RuntimeWarning: More than 20 figures have been opened. Figures created through the pyplot interface (`matplotlib.pyplot.figure`) are retained until explicitly closed and may consume too much memory. (To control this warning, see the rcParam `figure.max_open_warning`).\n", - " fig, ax = plt.subplots(figsize=(15, 6))\n" - ] - }, - { "data": { "application/vnd.jupyter.widget-view+json": { - "model_id": "96882c0b2fb3492a8fbcd68d4c1db371", + "model_id": "af5e3d32d4e7491ea2dfdceceef0b346", "version_major": 2, "version_minor": 0 }, @@ -80,7 +73,7 @@ } ], "source": [ - "fig, ax = plt.subplots(figsize=(15, 6))\n", + "fig, ax = plt.subplots(figsize=(9, 6))\n", "fig.tight_layout()\n", "ax.matshow(H)\n", "None" @@ -88,21 +81,358 @@ }, { "cell_type": "code", - "execution_count": 96, + "execution_count": 118, + "metadata": {}, + "outputs": [], + "source": [ + "import ctypes\n", + "lib = ctypes.CDLL('../controller/fw/ldpc_decoder_test.so')" + ] + }, + { + "cell_type": "code", + "execution_count": 119, + "metadata": {}, + "outputs": [], + "source": [ + "np.set_printoptions(linewidth=180, threshold=1000, edgeitems=20)\n", + "#bits_indices, bits, _ = scipy.sparse.find(H)\n", + "#np.all(bits_indices == np.repeat(range(288), 8))\n", + "bits_indices, bits, _ = scipy.sparse.find(H.T)\n", + "#p.bincount(bits_indices)" + ] + }, + { + "cell_type": "code", + "execution_count": 120, "metadata": {}, "outputs": [ { - "name": "stderr", - "output_type": "stream", - "text": [ - "<ipython-input-96-9621d966b0c0>:6: RuntimeWarning: More than 20 figures have been opened. Figures created through the pyplot interface (`matplotlib.pyplot.figure`) are retained until explicitly closed and may consume too much memory. (To control this warning, see the rcParam `figure.max_open_warning`).\n", - " fig, ax = plt.subplots(figsize=(15, 3))\n" - ] - }, + "data": { + "text/plain": [ + "True" + ] + }, + "execution_count": 120, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "bits_indices, bits, _ = scipy.sparse.find(H)\n", + "l = [ 0, 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\n", + " , 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\n", + " , 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\n", + " , 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\n", + " , 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, 153, 154, 155, 156, 157, 158, 159\n", + " , 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191\n", + " , 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223\n", + " , 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255\n", + " , 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287\n", + " , 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319\n", + " , 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351\n", + " , 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383\n", + " , 33, 34, 52, 55, 232, 251, 252, 287, 42, 49, 78, 115, 234, 247, 265, 375, 61, 93, 106, 121, 198, 223, 243, 285, 43, 168, 173, 254, 255, 333, 339, 359\n", + " , 32, 146, 148, 184, 269, 328, 340, 365, 36, 159, 189, 245, 272, 286, 324, 382, 3, 50, 70, 97, 170, 274, 299, 329, 39, 46, 77, 85, 235, 271, 281, 320\n", + " , 14, 24, 69, 113, 203, 237, 298, 369, 53, 54, 66, 163, 200, 225, 256, 357, 88, 151, 211, 263, 267, 311, 316, 370, 10, 91, 100, 192, 293, 295, 315, 368\n", + " , 73, 90, 116, 129, 150, 233, 290, 350, 63, 158, 193, 209, 219, 226, 248, 325, 124, 127, 133, 214, 246, 318, 355, 381, 1, 101, 135, 141, 253, 279, 312, 341\n", + " , 83, 95, 111, 145, 191, 283, 306, 331, 15, 38, 105, 139, 164, 179, 230, 304, 48, 60, 123, 132, 220, 303, 336, 346, 23, 41, 45, 94, 176, 221, 222, 240\n", + " , 62, 96, 130, 194, 208, 210, 335, 360, 21, 79, 112, 125, 153, 297, 363, 383, 7, 47, 154, 261, 291, 305, 334, 349, 2, 138, 167, 212, 216, 257, 284, 342\n", + " , 76, 122, 162, 239, 353, 366, 377, 380, 13, 72, 103, 228, 288, 300, 310, 338, 0, 110, 149, 190, 207, 217, 275, 374, 27, 67, 81, 84, 114, 131, 177, 280\n", + " , 51, 107, 128, 156, 181, 202, 249, 302, 25, 31, 59, 64, 136, 152, 186, 236, 18, 74, 137, 197, 204, 337, 354, 372, 4, 56, 108, 126, 174, 187, 188, 378\n", + " , 57, 118, 140, 196, 264, 292, 309, 322, 65, 87, 144, 183, 268, 273, 317, 356, 8, 17, 169, 180, 199, 301, 326, 373, 44, 68, 80, 82, 143, 201, 266, 347\n", + " , 9, 242, 250, 258, 319, 332, 344, 371, 12, 20, 92, 104, 117, 142, 276, 277, 6, 28, 86, 102, 119, 160, 182, 238, 30, 109, 134, 171, 227, 229, 278, 367\n", + " , 37, 40, 175, 224, 241, 289, 321, 379, 5, 99, 260, 282, 313, 330, 352, 358, 157, 172, 195, 262, 307, 323, 351, 361, 19, 26, 35, 58, 75, 166, 314, 345\n", + " , 22, 89, 244, 294, 296, 343, 348, 376, 29, 71, 147, 165, 178, 259, 270, 327, 11, 16, 98, 155, 206, 215, 362, 364, 120, 161, 185, 205, 213, 218, 231, 308\n", + " , 48, 50, 100, 261, 297, 325, 363, 378, 13, 25, 36, 42, 96, 101, 234, 258, 19, 52, 67, 83, 162, 187, 270, 352, 7, 16, 188, 207, 321, 330, 367, 374\n", + " , 60, 91, 93, 128, 190, 218, 287, 295, 5, 58, 75, 108, 170, 172, 298, 346, 51, 88, 121, 130, 139, 255, 267, 373, 18, 21, 157, 168, 174, 265, 345, 383\n", + " , 76, 97, 120, 137, 158, 210, 248, 353, 3, 43, 136, 194, 245, 273, 293, 313, 64, 79, 113, 142, 191, 232, 253, 306, 55, 219, 246, 268, 281, 294, 314, 343\n", + " , 0, 34, 89, 154, 201, 290, 307, 377, 112, 138, 198, 264, 302, 308, 342, 362, 61, 86, 127, 148, 247, 286, 349, 365, 39, 118, 141, 181, 223, 291, 315, 355\n", + " , 125, 180, 282, 303, 316, 326, 332, 335, 1, 32, 104, 105, 178, 189, 348, 361, 45, 78, 92, 155, 185, 300, 357, 380, 29, 40, 46, 147, 160, 225, 241, 372\n", + " , 2, 14, 99, 156, 214, 235, 256, 278, 9, 28, 74, 238, 257, 284, 299, 323, 70, 98, 114, 119, 151, 285, 296, 360, 41, 129, 150, 215, 224, 277, 329, 368\n", + " , 57, 95, 126, 134, 221, 280, 310, 317, 11, 30, 102, 230, 269, 275, 288, 318, 15, 65, 82, 182, 212, 266, 309, 358, 107, 111, 115, 240, 243, 251, 272, 305\n", + " , 87, 90, 204, 244, 320, 334, 336, 337, 23, 33, 59, 85, 109, 149, 283, 381, 131, 165, 192, 196, 211, 236, 259, 312, 31, 117, 153, 164, 199, 213, 222, 319\n", + " , 54, 69, 94, 161, 186, 249, 304, 356, 6, 8, 106, 122, 177, 205, 217, 344, 17, 62, 66, 123, 197, 226, 339, 371, 44, 145, 206, 237, 239, 289, 322, 379\n", + " , 71, 143, 163, 167, 176, 200, 331, 351, 72, 132, 140, 171, 179, 193, 254, 354, 12, 77, 103, 159, 202, 252, 366, 376, 37, 173, 203, 220, 229, 231, 311, 333\n", + " , 68, 208, 216, 233, 260, 271, 327, 350, 49, 84, 166, 169, 262, 274, 338, 340, 81, 135, 144, 263, 324, 359, 364, 375, 10, 22, 63, 80, 227, 228, 292, 328\n", + " , 110, 124, 146, 152, 175, 341, 369, 370, 4, 20, 26, 35, 116, 183, 195, 301, 24, 56, 73, 133, 184, 209, 279, 382, 27, 38, 47, 53, 242, 250, 276, 347\n", + " , 16, 82, 142, 210, 217, 268, 344, 370, 10, 12, 124, 126, 201, 325, 336, 353, 47, 73, 92, 95, 107, 212, 240, 312, 33, 102, 132, 164, 221, 254, 296, 314\n", + " , 30, 49, 56, 58, 61, 67, 140, 260, 41, 60, 76, 89, 218, 279, 302, 338, 20, 62, 79, 113, 186, 213, 331, 355, 25, 28, 29, 108, 153, 169, 297, 364\n", + " , 18, 75, 117, 120, 133, 287, 326, 329, 86, 137, 149, 162, 200, 249, 309, 351, 26, 163, 178, 245, 284, 361, 371, 380, 65, 72, 216, 219, 258, 294, 304, 333\n", + " , 8, 193, 197, 225, 241, 270, 319, 324, 81, 83, 100, 111, 122, 155, 228, 278, 182, 189, 196, 263, 275, 327, 337, 360, 6, 15, 35, 53, 203, 237, 308, 379\n", + " , 36, 166, 204, 252, 256, 282, 365, 373, 19, 66, 106, 114, 139, 161, 188, 247, 97, 165, 211, 224, 310, 354, 362, 382, 63, 78, 94, 99, 317, 339, 342, 376\n", + " , 23, 51, 105, 143, 261, 289, 292, 330, 45, 148, 152, 171, 208, 238, 242, 303, 17, 91, 110, 231, 255, 271, 299, 372, 27, 87, 90, 129, 134, 236, 301, 352\n", + " , 40, 160, 180, 192, 229, 243, 273, 320, 9, 42, 115, 127, 157, 285, 349, 368, 68, 84, 170, 177, 232, 307, 321, 369, 3, 11, 57, 125, 147, 172, 283, 291\n", + " , 7, 190, 222, 227, 295, 348, 350, 359, 43, 69, 98, 101, 128, 207, 277, 293, 31, 55, 104, 119, 130, 158, 341, 375, 13, 85, 135, 226, 305, 318, 358, 366\n", + " , 22, 34, 183, 187, 199, 215, 311, 378, 32, 70, 112, 154, 205, 230, 266, 322, 54, 202, 248, 272, 290, 323, 343, 345, 0, 88, 150, 173, 233, 234, 269, 334\n", + " , 141, 146, 206, 220, 253, 281, 332, 381, 21, 138, 144, 174, 179, 194, 262, 298, 38, 71, 93, 156, 168, 181, 214, 239, 48, 50, 77, 264, 288, 328, 356, 357\n", + " , 96, 167, 184, 267, 280, 300, 347, 363, 14, 44, 80, 103, 145, 209, 335, 367, 2, 5, 74, 109, 121, 136, 151, 276, 131, 191, 195, 223, 286, 316, 377, 383\n", + " , 4, 39, 159, 235, 274, 306, 313, 346, 1, 24, 46, 52, 64, 123, 250, 259, 37, 59, 175, 185, 198, 251, 257, 340, 116, 118, 176, 244, 246, 265, 315, 374\n", + " , 26, 74, 124, 155, 189, 219, 374, 381, 4, 38, 103, 139, 199, 293, 319, 350, 75, 77, 158, 161, 181, 208, 261, 284, 39, 109, 122, 175, 234, 265, 271, 340\n", + " , 2, 130, 275, 277, 312, 333, 342, 362, 13, 31, 95, 209, 249, 289, 298, 375, 47, 125, 131, 164, 226, 252, 353, 356, 21, 159, 166, 324, 330, 339, 368, 383\n", + " , 10, 37, 89, 197, 220, 223, 300, 366, 0, 12, 78, 111, 112, 154, 311, 377, 86, 129, 140, 141, 191, 204, 254, 297, 3, 42, 61, 126, 185, 257, 269, 371\n", + " , 35, 43, 157, 210, 215, 251, 347, 367, 17, 177, 180, 193, 213, 263, 363, 372, 57, 104, 203, 227, 236, 253, 262, 344, 64, 72, 82, 135, 136, 239, 320, 348\n", + " , 1, 116, 218, 240, 288, 334, 357, 364, 20, 49, 97, 121, 182, 256, 294, 309, 79, 102, 113, 118, 137, 152, 195, 343, 23, 30, 48, 128, 216, 291, 313, 335\n", + " , 58, 63, 127, 169, 228, 264, 328, 369, 62, 70, 106, 144, 153, 198, 201, 255, 56, 107, 148, 162, 179, 212, 290, 351, 54, 59, 88, 92, 143, 282, 303, 365\n", + " , 99, 123, 165, 200, 222, 296, 302, 349, 15, 36, 50, 94, 160, 167, 230, 370, 73, 120, 138, 194, 231, 246, 259, 379, 9, 25, 146, 224, 260, 301, 359, 376\n", + " , 100, 183, 186, 238, 248, 258, 331, 352, 114, 117, 184, 188, 221, 268, 327, 378, 115, 192, 205, 214, 242, 325, 332, 382, 71, 84, 98, 174, 206, 235, 314, 317\n", + " , 19, 65, 101, 172, 196, 270, 316, 318, 28, 67, 119, 173, 202, 306, 341, 354, 7, 27, 247, 280, 285, 292, 321, 329, 60, 80, 93, 304, 310, 323, 336, 345\n", + " , 14, 52, 90, 132, 156, 276, 358, 380, 40, 91, 110, 171, 217, 233, 278, 281, 11, 66, 108, 149, 176, 241, 244, 283, 18, 32, 45, 87, 207, 245, 267, 307\n", + " , 22, 55, 142, 170, 187, 229, 308, 337, 6, 46, 134, 150, 178, 211, 250, 279, 16, 133, 266, 286, 315, 326, 338, 361, 24, 68, 76, 81, 225, 243, 295, 322\n", + " , 8, 41, 53, 69, 83, 96, 190, 237, 44, 51, 232, 272, 273, 287, 346, 355, 5, 29, 33, 147, 163, 274, 299, 360, 34, 85, 105, 145, 151, 168, 305, 373\n", + " , 126, 143, 197, 211, 267, 318, 326, 362, 26, 124, 200, 232, 265, 270, 298, 319, 5, 45, 48, 169, 203, 286, 351, 381, 24, 44, 123, 137, 156, 273, 283, 307\n", + " , 18, 108, 199, 234, 262, 275, 314, 375, 4, 37, 68, 75, 164, 264, 291, 295, 94, 183, 207, 221, 271, 289, 293, 354, 121, 131, 161, 166, 188, 259, 284, 327\n", + " , 10, 90, 127, 147, 244, 316, 328, 358, 11, 23, 122, 220, 288, 304, 325, 366, 63, 70, 101, 106, 146, 168, 195, 370, 52, 182, 218, 249, 330, 332, 333, 368\n", + " , 74, 97, 102, 239, 290, 308, 340, 373, 20, 110, 145, 163, 229, 246, 251, 331, 84, 136, 149, 213, 258, 301, 360, 365, 51, 114, 174, 238, 276, 348, 352, 383\n", + " , 13, 27, 30, 92, 187, 302, 338, 341, 62, 79, 80, 186, 230, 278, 294, 324, 9, 67, 180, 269, 285, 312, 343, 372, 7, 14, 83, 89, 160, 178, 287, 364\n", + " , 47, 56, 78, 107, 128, 177, 228, 250, 46, 100, 243, 252, 255, 282, 299, 345, 25, 28, 72, 162, 245, 257, 317, 382, 32, 36, 69, 115, 237, 342, 347, 355\n", + " , 105, 154, 179, 184, 268, 277, 346, 350, 6, 15, 55, 111, 113, 225, 297, 320, 21, 85, 86, 109, 261, 305, 344, 349, 22, 112, 125, 181, 216, 233, 281, 311\n", + " , 35, 38, 43, 82, 219, 263, 322, 380, 53, 57, 81, 117, 185, 247, 323, 367, 65, 66, 150, 165, 170, 235, 300, 357, 3, 29, 116, 144, 176, 196, 274, 306\n", + " , 2, 95, 98, 120, 141, 158, 193, 315, 64, 91, 99, 142, 248, 256, 279, 361, 60, 130, 167, 210, 236, 253, 254, 339, 59, 77, 129, 191, 202, 223, 296, 310\n", + " , 1, 16, 40, 140, 173, 209, 280, 353, 58, 73, 87, 96, 134, 208, 212, 313, 12, 42, 93, 119, 135, 272, 303, 329, 34, 118, 148, 189, 214, 222, 321, 337\n", + " , 54, 71, 88, 241, 356, 374, 376, 378, 39, 76, 157, 192, 205, 231, 266, 335, 8, 153, 155, 194, 204, 206, 359, 377, 17, 49, 61, 103, 133, 151, 336, 379\n", + " , 19, 172, 175, 190, 198, 201, 217, 227, 0, 31, 41, 104, 152, 159, 171, 309, 33, 132, 240, 242, 260, 292, 334, 369, 50, 138, 139, 215, 224, 226, 363, 371\n", + "\n", + "]\n", + "np.all(bits == l)" + ] + }, + { + "cell_type": "code", + "execution_count": 121, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "True" + ] + }, + "execution_count": 121, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "bits_indices, bits, _ = scipy.sparse.find(H.T)\n", + "l = [\n", + " 0, 74, 108, 179, 201, 285, 0, 63, 113, 189, 208, 276, 0, 71, 116, 186, 196, 272, 0, 54, 105, 171, 203, 271, 0, 79, 141, 188, 193, 245, 0, 89\n", + " , 101, 186, 238, 242, 0, 86, 129, 159, 233, 265, 0, 70, 99, 172, 226, 259, 1, 82, 129, 156, 236, 282, 1, 84, 117, 169, 219, 258, 1, 59, 139, 145\n", + " , 200, 248, 1, 94, 121, 171, 230, 249, 1, 85, 134, 145, 201, 278, 1, 73, 97, 175, 197, 256, 1, 56, 116, 185, 228, 259, 1, 65, 122, 159, 217, 265\n", + " , 2, 94, 99, 144, 234, 276, 2, 82, 130, 166, 205, 283, 2, 78, 103, 152, 231, 244, 2, 91, 98, 161, 224, 284, 2, 85, 141, 150, 209, 253, 2, 69\n", + " , 103, 181, 199, 266, 2, 92, 139, 176, 232, 267, 2, 67, 125, 164, 211, 249, 3, 56, 142, 189, 235, 243, 3, 77, 97, 151, 219, 262, 3, 91, 141, 154\n", + " , 192, 241, 3, 75, 143, 167, 226, 256, 3, 86, 117, 151, 225, 262, 3, 93, 115, 151, 238, 271, 3, 87, 121, 148, 211, 256, 3, 77, 127, 174, 197, 285\n", + " , 4, 52, 113, 177, 231, 263, 4, 48, 125, 147, 238, 286, 4, 48, 108, 176, 239, 279, 4, 91, 141, 159, 204, 268, 4, 53, 97, 160, 217, 263, 4, 88\n", + " , 135, 190, 200, 245, 4, 65, 143, 182, 193, 268, 4, 55, 111, 188, 195, 281, 5, 88, 115, 168, 229, 276, 5, 67, 119, 149, 236, 285, 5, 49, 97, 169\n", + " , 203, 278, 5, 51, 105, 173, 204, 268, 5, 83, 131, 185, 237, 243, 5, 67, 114, 165, 231, 242, 5, 55, 115, 189, 233, 261, 5, 70, 143, 146, 198, 260\n", + " , 6, 66, 96, 183, 211, 242, 6, 49, 137, 148, 209, 283, 6, 54, 96, 183, 217, 287, 6, 76, 102, 164, 237, 255, 6, 48, 98, 189, 228, 251, 6, 57\n", + " , 143, 159, 236, 269, 6, 57, 128, 178, 215, 280, 6, 48, 107, 174, 232, 265, 7, 79, 142, 148, 214, 260, 7, 80, 120, 171, 206, 269, 7, 91, 101, 148\n", + " , 212, 277, 7, 77, 125, 190, 215, 275, 7, 66, 100, 149, 227, 274, 7, 50, 110, 148, 203, 283, 7, 68, 130, 150, 213, 257, 7, 61, 139, 163, 212, 250\n", + " , 8, 77, 106, 189, 207, 273, 8, 81, 122, 155, 224, 270, 8, 57, 130, 161, 230, 270, 8, 75, 98, 148, 225, 258, 8, 83, 136, 170, 235, 245, 8, 56\n", + " , 128, 173, 236, 263, 8, 54, 118, 177, 213, 250, 8, 93, 132, 182, 223, 280, 9, 73, 133, 155, 207, 262, 9, 60, 142, 146, 218, 277, 9, 78, 117, 186\n", + " , 192, 252, 9, 91, 101, 152, 194, 245, 9, 72, 104, 149, 235, 281, 9, 55, 134, 183, 194, 275, 9, 49, 114, 163, 201, 260, 9, 69, 106, 150, 210, 257\n", + " , 10, 83, 139, 185, 227, 257, 10, 75, 138, 157, 235, 269, 10, 83, 122, 144, 207, 268, 10, 64, 98, 157, 236, 259, 10, 75, 137, 170, 223, 254, 10, 55\n", + " , 125, 175, 239, 266, 10, 86, 110, 153, 202, 266, 10, 81, 124, 167, 231, 277, 11, 58, 102, 179, 215, 280, 11, 92, 108, 149, 200, 259, 11, 60, 124, 167\n", + " , 228, 248, 11, 59, 100, 166, 229, 273, 11, 85, 114, 146, 215, 256, 11, 50, 100, 182, 227, 278, 11, 67, 128, 163, 217, 246, 11, 64, 120, 146, 197, 272\n", + " , 12, 68, 97, 184, 236, 277, 12, 54, 104, 162, 209, 252, 12, 94, 118, 173, 223, 272, 12, 89, 116, 163, 216, 273, 12, 59, 96, 157, 220, 261, 12, 63\n", + " , 97, 173, 224, 250, 12, 86, 121, 147, 210, 252, 12, 73, 134, 185, 193, 283, 13, 85, 113, 174, 206, 285, 13, 65, 113, 164, 239, 264, 13, 50, 129, 161\n", + " , 213, 250, 13, 76, 123, 146, 214, 260, 13, 79, 101, 151, 230, 244, 13, 87, 125, 186, 195, 266, 13, 74, 140, 166, 229, 253, 13, 64, 123, 157, 201, 265\n", + " , 14, 69, 109, 177, 201, 267, 14, 56, 106, 150, 210, 265, 14, 75, 118, 161, 221, 255, 14, 49, 123, 169, 222, 263, 14, 60, 141, 191, 208, 271, 14, 85\n", + " , 127, 152, 221, 269, 14, 80, 111, 191, 210, 279, 14, 86, 118, 174, 225, 278, 15, 95, 104, 152, 218, 272, 15, 50, 102, 186, 209, 247, 15, 72, 129, 157\n", + " , 195, 249, 15, 66, 130, 189, 216, 243, 15, 62, 140, 145, 192, 241, 15, 69, 112, 171, 198, 267, 15, 79, 120, 145, 203, 240, 15, 62, 110, 169, 212, 248\n", + " , 16, 76, 100, 173, 211, 260, 16, 60, 119, 167, 202, 275, 16, 68, 102, 174, 196, 274, 16, 75, 126, 187, 198, 247, 16, 66, 133, 147, 228, 286, 16, 62\n", + " , 142, 152, 234, 283, 16, 87, 120, 167, 233, 277, 16, 63, 138, 175, 207, 278, 17, 77, 105, 186, 207, 254, 17, 78, 104, 153, 210, 243, 17, 71, 109, 181\n", + " , 218, 287, 17, 65, 102, 161, 193, 287, 17, 80, 133, 148, 202, 276, 17, 63, 111, 180, 202, 272, 17, 85, 106, 144, 232, 273, 17, 83, 132, 164, 215, 240\n", + " , 18, 81, 138, 181, 213, 271, 18, 64, 131, 185, 239, 253, 18, 52, 140, 180, 219, 250, 18, 93, 115, 171, 238, 248, 18, 52, 110, 165, 214, 279, 18, 74\n", + " , 125, 153, 230, 254, 18, 60, 119, 179, 233, 270, 18, 58, 118, 186, 239, 283, 19, 77, 140, 165, 210, 285, 19, 69, 127, 151, 213, 282, 19, 70, 108, 177\n", + " , 201, 264, 19, 94, 114, 157, 192, 282, 19, 76, 116, 182, 228, 243, 19, 90, 103, 169, 204, 281, 19, 61, 104, 174, 194, 272, 19, 53, 134, 188, 199, 285\n", + " , 20, 86, 115, 168, 217, 259, 20, 95, 128, 161, 194, 247, 20, 72, 98, 153, 214, 262, 20, 57, 132, 154, 238, 253, 20, 65, 127, 147, 198, 245, 20, 93\n", + " , 126, 162, 216, 270, 20, 91, 137, 160, 199, 247, 20, 71, 132, 184, 217, 274, 21, 51, 103, 182, 239, 250, 21, 82, 137, 151, 212, 242, 21, 54, 101, 170\n", + " , 232, 270, 21, 87, 133, 165, 229, 285, 21, 90, 101, 171, 224, 284, 21, 51, 135, 179, 225, 276, 21, 79, 103, 181, 223, 255, 21, 88, 140, 190, 195, 284\n", + " , 22, 67, 132, 191, 230, 271, 22, 75, 129, 170, 205, 260, 22, 93, 113, 154, 233, 259, 22, 65, 133, 181, 214, 264, 22, 82, 112, 168, 205, 258, 22, 76\n", + " , 111, 182, 194, 267, 22, 86, 122, 158, 209, 251, 22, 81, 141, 176, 220, 246, 23, 52, 142, 184, 221, 264, 23, 95, 114, 190, 203, 269, 23, 77, 128, 150\n", + " , 220, 257, 23, 79, 98, 176, 232, 256, 23, 79, 99, 161, 221, 247, 23, 53, 113, 158, 192, 279, 23, 74, 100, 172, 236, 284, 23, 64, 106, 187, 202, 275\n", + " , 24, 59, 126, 168, 222, 281, 24, 61, 133, 156, 205, 272, 24, 68, 105, 181, 218, 282, 24, 90, 141, 187, 210, 250, 24, 80, 126, 158, 224, 271, 24, 78\n", + " , 130, 156, 200, 240, 24, 50, 109, 190, 213, 284, 24, 82, 127, 176, 193, 244, 25, 57, 132, 153, 216, 241, 25, 83, 108, 145, 213, 284, 25, 76, 134, 178\n", + " , 225, 275, 25, 56, 135, 159, 206, 242, 25, 78, 124, 160, 202, 282, 25, 95, 129, 177, 222, 281, 25, 94, 131, 180, 223, 282, 25, 74, 99, 173, 231, 246\n", + " , 26, 68, 136, 165, 194, 277, 26, 61, 142, 185, 197, 276, 26, 68, 104, 144, 204, 274, 26, 58, 126, 162, 233, 240, 26, 71, 122, 146, 214, 277, 26, 95\n", + " , 127, 150, 205, 254, 26, 62, 116, 182, 222, 279, 26, 94, 119, 176, 204, 287, 27, 71, 136, 155, 211, 267, 27, 74, 129, 144, 229, 284, 27, 95, 100, 149\n", + " , 208, 251, 27, 61, 107, 155, 192, 268, 27, 66, 135, 180, 200, 249, 27, 67, 120, 147, 221, 246, 27, 67, 127, 172, 216, 279, 27, 50, 111, 187, 200, 275\n", + " , 28, 88, 119, 162, 219, 287, 28, 57, 115, 156, 235, 265, 28, 61, 130, 175, 198, 287, 28, 87, 139, 172, 206, 284, 28, 73, 139, 157, 212, 260, 28, 87\n", + " , 135, 168, 232, 253, 28, 65, 121, 177, 217, 257, 28, 95, 135, 166, 218, 281, 29, 48, 106, 170, 237, 241, 29, 60, 136, 179, 229, 267, 29, 49, 97, 179\n", + " , 195, 244, 29, 55, 116, 188, 223, 270, 29, 77, 126, 167, 206, 274, 29, 56, 131, 159, 236, 263, 29, 86, 117, 165, 220, 255, 29, 72, 131, 182, 207, 252\n", + " , 30, 67, 123, 146, 208, 286, 30, 88, 115, 156, 230, 280, 30, 84, 143, 165, 222, 286, 30, 50, 123, 168, 235, 261, 30, 92, 124, 191, 230, 248, 30, 53\n", + " , 105, 154, 231, 262, 30, 62, 107, 191, 218, 253, 30, 49, 110, 161, 226, 269, 31, 61, 104, 178, 220, 273, 31, 76, 128, 153, 197, 251, 31, 84, 143, 189\n", + " , 233, 260, 31, 48, 123, 190, 204, 253, 31, 48, 134, 160, 198, 261, 31, 63, 106, 180, 206, 274, 31, 51, 133, 147, 202, 274, 31, 51, 102, 166, 213, 261\n", + " , 32, 57, 116, 160, 209, 273, 32, 71, 117, 190, 203, 262, 32, 84, 97, 155, 220, 254, 32, 93, 126, 189, 218, 247, 32, 89, 136, 148, 219, 286, 32, 70\n", + " , 96, 164, 194, 266, 32, 90, 137, 181, 206, 244, 32, 58, 138, 158, 205, 268, 33, 80, 109, 183, 212, 245, 33, 49, 103, 191, 195, 241, 33, 83, 122, 177\n", + " , 234, 281, 33, 58, 102, 184, 231, 240, 33, 81, 107, 144, 221, 264, 33, 52, 121, 179, 203, 258, 33, 93, 98, 156, 224, 241, 33, 55, 136, 166, 195, 246\n", + " , 34, 53, 123, 178, 237, 278, 34, 81, 105, 168, 237, 243, 34, 54, 137, 188, 238, 271, 34, 74, 121, 158, 196, 244, 34, 85, 143, 186, 228, 255, 34, 85\n", + " , 119, 173, 196, 264, 34, 87, 116, 157, 229, 257, 34, 63, 142, 149, 233, 273, 35, 75, 120, 184, 226, 276, 35, 55, 107, 180, 229, 267, 35, 89, 112, 160\n", + " , 215, 261, 35, 64, 125, 171, 230, 243, 35, 71, 117, 154, 194, 247, 35, 50, 118, 169, 226, 258, 35, 53, 110, 187, 234, 242, 35, 48, 100, 152, 237, 259\n", + " , 36, 73, 121, 183, 208, 249, 36, 88, 131, 164, 197, 246, 36, 60, 108, 178, 214, 252, 36, 70, 111, 171, 211, 245, 36, 80, 139, 164, 226, 286, 36, 59\n", + " , 105, 173, 193, 246, 36, 92, 107, 155, 209, 257, 36, 59, 100, 172, 235, 245, 37, 92, 118, 147, 216, 275, 37, 69, 96, 151, 202, 265, 37, 56, 101, 181\n", + " , 197, 241, 37, 54, 117, 166, 238, 261, 37, 73, 114, 184, 200, 270, 37, 82, 141, 167, 219, 254, 37, 76, 109, 149, 216, 256, 37, 66, 112, 165, 215, 278\n", + " , 38, 65, 128, 155, 227, 249, 38, 70, 123, 175, 239, 266, 38, 64, 106, 188, 225, 271, 38, 90, 108, 170, 231, 243, 38, 95, 109, 159, 232, 252, 38, 80\n", + " , 122, 153, 209, 285, 38, 73, 120, 162, 227, 275, 38, 58, 135, 176, 201, 267, 39, 63, 126, 146, 196, 258, 39, 89, 105, 188, 211, 277, 39, 91, 107, 147\n", + " , 223, 244, 39, 59, 111, 191, 234, 272, 39, 58, 112, 187, 224, 248, 39, 81, 120, 163, 223, 262, 39, 62, 121, 175, 224, 240, 39, 84, 127, 156, 193, 241\n", + " , 40, 55, 124, 168, 207, 265, 40, 88, 99, 170, 226, 279, 40, 80, 131, 177, 235, 268, 40, 90, 117, 178, 227, 269, 40, 53, 138, 156, 199, 257, 40, 61\n", + " , 96, 145, 222, 249, 40, 82, 112, 152, 234, 240, 40, 93, 136, 158, 221, 247, 41, 52, 139, 183, 212, 248, 41, 54, 119, 152, 226, 278, 41, 89, 99, 164\n", + " , 199, 251, 41, 64, 132, 150, 220, 253, 41, 84, 112, 180, 222, 251, 41, 51, 135, 155, 196, 251, 41, 70, 124, 179, 208, 286, 41, 68, 112, 185, 211, 281\n", + " , 42, 66, 124, 145, 227, 283, 42, 78, 124, 158, 232, 279, 42, 73, 137, 149, 234, 256, 42, 51, 130, 163, 199, 274, 42, 52, 137, 190, 195, 252, 42, 63\n", + " , 140, 174, 225, 256, 42, 71, 109, 163, 196, 263, 42, 92, 107, 178, 210, 258, 43, 84, 129, 144, 206, 266, 43, 91, 103, 178, 227, 261, 43, 66, 101, 188\n", + " , 237, 264, 43, 83, 143, 184, 204, 263, 43, 92, 113, 172, 207, 255, 43, 70, 110, 169, 216, 266, 43, 60, 136, 172, 193, 264, 43, 90, 132, 153, 214, 242\n", + " , 44, 89, 98, 167, 220, 255, 44, 72, 104, 145, 198, 276, 44, 78, 133, 162, 225, 246, 44, 62, 111, 150, 237, 263, 44, 81, 128, 183, 198, 280, 44, 57\n", + " , 114, 183, 208, 270, 44, 89, 122, 175, 228, 248, 44, 51, 138, 172, 219, 282, 45, 68, 118, 158, 238, 254, 45, 90, 113, 154, 234, 273, 45, 94, 109, 162\n", + " , 196, 240, 45, 69, 96, 184, 205, 287, 45, 94, 138, 151, 208, 259, 45, 52, 110, 160, 215, 254, 45, 72, 134, 175, 200, 249, 45, 87, 99, 185, 204, 269\n", + " , 46, 59, 119, 169, 199, 251, 46, 56, 140, 170, 212, 286, 46, 58, 140, 144, 217, 250, 46, 84, 130, 154, 203, 287, 46, 78, 115, 166, 205, 258, 46, 82\n", + " , 102, 160, 239, 252, 46, 74, 99, 191, 192, 280, 46, 49, 138, 174, 197, 244, 47, 92, 134, 163, 219, 280, 47, 72, 108, 187, 201, 282, 47, 79, 96, 176\n", + " , 221, 280, 47, 88, 131, 159, 218, 283, 47, 72, 114, 154, 228, 268, 47, 62, 125, 180, 192, 242, 47, 53, 142, 162, 222, 262, 47, 69, 103, 187, 199, 255\n", + "\n", + "]\n", + "np.all(bits == l)" + ] + }, + { + "cell_type": "code", + "execution_count": 122, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "(288, 384)" + ] + }, + "execution_count": 122, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "H.shape" + ] + }, + { + "cell_type": "code", + "execution_count": 123, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "2304" + ] + }, + "execution_count": 123, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "np.sum(H)" + ] + }, + { + "cell_type": "code", + "execution_count": 124, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "110592" + ] + }, + "execution_count": 124, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "len(H.flatten())" + ] + }, + { + "cell_type": "code", + "execution_count": 125, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "True" + ] + }, + "execution_count": 125, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "6 * 384 == 8*288" + ] + }, + { + "cell_type": "code", + "execution_count": 126, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "array([6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,\n", + " 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,\n", + " 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,\n", + " 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,\n", + " 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,\n", + " 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,\n", + " 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6])" + ] + }, + "execution_count": 126, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "np.sum(H, axis=0)" + ] + }, + { + "cell_type": "code", + "execution_count": 127, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "array([8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,\n", + " 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,\n", + " 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,\n", + " 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,\n", + " 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,\n", + " 8, 8, 8])" + ] + }, + "execution_count": 127, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "np.sum(H, axis=1)" + ] + }, + { + "cell_type": "code", + "execution_count": 128, + "metadata": {}, + "outputs": [ { "data": { "application/vnd.jupyter.widget-view+json": { - "model_id": "961f48f481054e9da3c60ff5414e4ab8", + "model_id": "7612cc62e7f34f70a0a93ed84b88fe79", "version_major": 2, "version_minor": 0 }, @@ -116,10 +446,10 @@ { "data": { "text/plain": [ - "<matplotlib.image.AxesImage at 0x7f4bcd779e50>" + "<matplotlib.image.AxesImage at 0x7fc70960cac0>" ] }, - "execution_count": 96, + "execution_count": 128, "metadata": {}, "output_type": "execute_result" } @@ -130,13 +460,33 @@ "d = np.dot(G, test_data) % 2\n", "x = (-1) ** d\n", "\n", - "fig, ax = plt.subplots(figsize=(15, 3))\n", + "fig, ax = plt.subplots(figsize=(9, 3))\n", "ax.matshow(x.reshape((-1, 64)))" ] }, { "cell_type": "code", - "execution_count": 97, + "execution_count": 129, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "((384,), (101,))" + ] + }, + "execution_count": 129, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "x.shape, test_data.shape" + ] + }, + { + "cell_type": "code", + "execution_count": 130, "metadata": {}, "outputs": [ { @@ -145,7 +495,7 @@ "True" ] }, - "execution_count": 97, + "execution_count": 130, "metadata": {}, "output_type": "execute_result" } |