Belief propagation (BP) decoding

To decode using belief propagation, first load an instance of the ldpc.BpDecoder class.

import numpy as np
import ldpc.codes
from ldpc import BpDecoder

H=ldpc.codes.rep_code(3) #parity check matrix for the length-3 repetition code
n=H.shape[1] #the codeword length

bpd = BpDecoder(
    H, #the parity check matrix
    error_rate=0.1, # the error rate on each bit
    max_iter=n, #the maximum iteration depth for BP
    bp_method="product_sum", #BP method. The other option is `minimum_sum'
)

Received vector decoding

Given a corrupted codeword, the bp_decoder.decode will provide an estimate of its unerrored form. For example, consider the case where we are encoding via a three-bit repetition code:

codeword=np.array([1,1,1])

If the above codeword is subject to an error on its first bit the received vector is given by

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

The above vector can be corrected using the bp_decoder.decode as follows:

decoded_codeword=bpd.decode(received_vector)

print(decoded_codeword)

[1 1 1]

Syndrome decoding

In syndrome decoding, the error syndrome is input to bp_decoder.decode function. This is useful in settings where the codeword cannot be directly measured. eg. in quantum error correction. The output of the syndrome recovery is an estimate of the error.

H=ldpc.codes.rep_code(3) #parity check matrix for the length-3 repetition code
n=H.shape[1] #the codeword length

bpd = BpDecoder(
    H, #the parity check matrix
    error_rate=0.1, # the error rate on each bit
    max_iter=n, #the maximum iteration depth for BP
    bp_method="product_sum", #BP method. The other option is `minimum_sum'
)

error = np.array([0,1,0])
syndrome = H@error %2 # the syndrome of the error

decoding=bpd.decode(syndrome)

print(f"Error: {error}")
print(f"Syndrome: {syndrome}")
print(f"Decoding: {decoding}")

Error: [0 1 0]
Syndrome: [1 1]
Decoding: [0 1 0]

Assymetric error channels

If the code bits are subject to different error rates, an error_channel vector can be provided instead of the error rate. The error channel specifies the probability of an error on each code bit. For example, consider the case below

bpd=BpDecoder(
    H,
    max_iter=n,
    bp_method="product_sum",
    error_channel=[0.1,0,0.1] #channel probability probabilities. Will overide error rate.
)

error=np.array([1,0,1])
syndrome=H@error%2
decoding=bpd.decode(syndrome)
print(f"Error: {error}")
print(f"Syndrome: {syndrome}")
print(f"Decoding: {decoding}")

Error: [1 0 1]
Syndrome: [1 1]
Decoding: [1 0 1]

Example: error correction over the binary symmetric channel

import numpy as np
from ldpc.codes import rep_code
from ldpc import BpDecoder

n=13
error_rate=0.3
runs=5
H=rep_code(n)

#BP decoder class. Make sure this is defined outside the loop
bpd=BpDecoder(H,error_rate=error_rate,max_iter=n,bp_method="product_sum")
error=np.zeros(n).astype(int) #error vector

for _ in range(runs):
    for i in range(n):
        if np.random.random()<error_rate:
            error[i]=1
        else: error[i]=0
    syndrome=H@error %2 #calculates the error syndrome
    print(f"Error: {error}")
    print(f"Syndrome: {syndrome}")
    decoding=bpd.decode(syndrome)
    print(f"Decoding: {decoding}\n")

Error: [1 0 1 0 0 0 1 1 1 1 0 1 0]
Syndrome: [1 1 1 0 0 1 0 0 0 1 1 1]
Decoding: [0 1 0 1 1 1 0 0 0 0 1 0 1]

Error: [0 0 0 0 0 0 0 0 1 0 0 0 0]
Syndrome: [0 0 0 0 0 0 0 1 1 0 0 0]
Decoding: [0 0 0 0 0 0 0 0 1 0 0 0 0]

Error: [0 0 0 0 1 0 1 1 1 1 1 0 1]
Syndrome: [0 0 0 1 1 1 0 0 0 0 1 1]
Decoding: [1 1 1 1 0 1 0 0 0 0 0 1 0]

Error: [0 0 1 0 0 0 0 0 1 1 1 0 1]
Syndrome: [0 1 1 0 0 0 0 1 0 0 1 1]
Decoding: [0 0 1 0 0 0 0 0 1 1 1 0 1]

Error: [0 0 1 0 0 0 1 1 0 0 0 0 1]
Syndrome: [0 1 1 0 0 1 0 1 0 0 0 1]
Decoding: [0 0 1 0 0 0 1 1 0 0 0 0 1]

Serial or Parallel Schedules

LDPCv2 has the option to switch between ‘parallel’ and ‘serial’ deocoding schedules. The default option is the parallel schedule. Serial scheduling can lead to better convergence in certain circumstances. Serial scheduling can be activated as follows:

H=ldpc.codes.rep_code(3) #parity check matrix for the length-3 repetition code
n=H.shape[1] #the codeword length

bpd = BpDecoder(
    H, #the parity check matrix
    error_rate=0.1, # the error rate on each bit
    max_iter=n, #the maximum iteration depth for BP
    bp_method="product_sum", #BP method. The other option is `minimum_sum',
    schedule = "serial" # the BP schedule
)

error = np.array([0,1,0])
syndrome = H@error %2 # the syndrome of the error

decoding=bpd.decode(syndrome)

print(f"Error: {error}")
print(f"Syndrome: {syndrome}")
print(f"Decoding: {decoding}")

Error: [0 1 0]
Syndrome: [1 1]
Decoding: [0 1 0]

Monte-Carlo Simulation Class

The ldpc.monte_carlo_simulation.MonteCarloBscSimulation provides a convenient way of testing the performance of binary linear codes over the binary symmetric channel.

import numpy as np
import ldpc.codes
from ldpc import BpDecoder
from ldpc.monte_carlo_simulation import MonteCarloBscSimulation
import ldpc.code_util

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 = ldpc.code_util.compute_code_parameters(H)

print(f"[n={n}, k={k}, d={d}]")

error_rate = 0.01
dec = BpDecoder(H, error_rate=error_rate, max_iter = 0, bp_method="minimum_sum")
mc_sim = MonteCarloBscSimulation(H, error_rate = error_rate, target_run_count=10000, Decoder = dec, tqdm_disable=True)
mc_sim.run()

[n=14, k=5, d=5]

{'logical_error_rate': 0.0019,
 'logical_error_rate_eb': 0.0004354756020720334,
 'error_rate': 0.01,
 'run_count': 10000,
 'fail_count': 19}