Binary Linear Codes

In LDPC, binary linear error correction codes are represented in terms of their parity check matrix stored in scipy.sparse format. As an example, the parity check matrix for the repetition code can be loaded from the ldpc.codes submodule as follows:

import numpy as np
import ldpc.codes
import ldpc.code_util
n=5 #specifies the lenght of the repetition code
H=ldpc.codes.rep_code(n) #returns the repetition code parity check matrix
print(H)

  (0, 0)        1
  (0, 1)        1
  (1, 1)        1
  (1, 2)        1
  (2, 2)        1
  (2, 3)        1
  (3, 3)        1
  (3, 4)        1

The above print statement displays a list of the coordinates for the nonzero elements of the parity check matrix. To print the matrix in a more readable form, the np.ndarray.toarray() method can be used.

print(H.toarray())

[[1 1 0 0 0]
 [0 1 1 0 0]
 [0 0 1 1 0]
 [0 0 0 1 1]]

Computing code properties

To compute the [n,k,d] code parameters we can use functions from the ldpc.mod2 and ldpc.code_util submodules. Below is an example showing how to calculate the code parameters of the Hamming code:

H = ldpc.codes.hamming_code(3)
print(H.toarray())

[[0 0 0 1 1 1 1]
 [0 1 1 0 0 1 1]
 [1 0 1 0 1 0 1]]

Number of physical bits

The number of physical bits \(n\) is simply the number of columns in the parity check matrix:

n = H.shape[1]
print(f"Number of physical bits, n = {n}")

Number of physical bits, n = 7

Code dimension (number of logical bits)

The number of logical bits \(k\) can be obtained using the ldpc.code_util.compute_code_dimension function.

k = ldpc.code_util.compute_code_dimension(H)
print(f"Number of logical bits, k = {k}")

Number of logical bits, k = 4

Code distance

An estimate of the code distance \(d\) can be obtained using the ldpc.code_util.estimate_code_distance function. This function first computes the kernel, then iterates over random linear combinations of the rows to find low weight codewords. By default, the function runs for \(0.025s\). This can be change by setting the timeout_seconds parameter.

d, number_code_words_sampled, lowest_weight_codewords = ldpc.code_util.estimate_code_distance(H, timeout_seconds = 0.1)
print(f"Code distance estimate, d <= {d} (no. codewords sampled: {number_code_words_sampled})")

Code distance estimate, d <= 3 (no. codewords sampled: 390178)

From the above, we see that the Hamming code has \(n=7\) physical bits, \(k=4\) logical bits, and \(d<=3\). The \([n,k,d]\) parameters can be calculated more directly for any parity check matrix using the ldpc.code_util.compute_code_parameters function. For example, we can compute the code parameters of the rank \(5\) Hamming code as follows:

H = ldpc.codes.hamming_code(5) # Rank 5 Hamming Code
n, k, d_estimate = ldpc.code_util.compute_code_parameters(H)

print(f"Code parameters: [n = {n}, k = {k}, d <= {d_estimate}]")

Code parameters: [n = 31, k = 26, d <= 3]

Code parameter calculation: LDPC code example

import ldpc.code_util
import numpy as np
H = np.array([[0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
       [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1],
       [1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0],
       [0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0],
       [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0],
       [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
       [0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0]])

n, k, d_estimate = ldpc.code_util.compute_code_parameters(H)
print(f"Code parameters: [n = {n}, k = {k}, d <= {d_estimate}]")

Code parameters: [n = 14, k = 5, d <= 5]

Encoding data with the generator matrix

The generator matrix \(G\) maps unencoded data to encoded codewords. The generator matrix can be obtained from a parity check matrix using the ldpc.code_util.construct_generator_matrix function. For example, the generator matrix for the Hamming code is computed as follows:

import numpy as np
import ldpc.codes
import ldpc.code_util

H = ldpc.codes.hamming_code(3)
G = ldpc.code_util.construct_generator_matrix(H)
G.toarray()

array([[1, 1, 1, 0, 0, 0, 0],
       [0, 1, 1, 1, 1, 0, 0],
       [0, 1, 0, 1, 0, 1, 0],
       [0, 0, 1, 1, 0, 0, 1]], dtype=uint8)

The generator matrix always satisfies the condition \(H\cdot G^T = 0\). i.e,

temp = H@G.T
temp.data = temp.data % 2
temp.toarray()

array([[0, 0, 0, 0],
       [0, 0, 0, 0],
       [0, 0, 0, 0]], dtype=uint8)

A \(k\)-bit message \(b\) can be encoded into a \(n\)-bit codeword \(c\) by multiplying by the generator matrix:

\[c = G^T\cdot b\]

For example, the \(4\)-bit message \(b=[1,0,1,1]\) can be encoded into a \(7\)-bit codeword \(c\) as follows:

b = np.array([1,0,1,1])

c = G.T@b % 2
c

array([1, 0, 0, 0, 0, 1, 1])

We can verify that \(c\) is a valid codeword by multiplying by the parity check matrix:

H@c % 2

array([0, 0, 0])