bit-flipping decoding

[divon]

Hello everyone,

I have a problem in trying to make a code for the algorithm of bit-flipping decoding, the algorithm is in the figure in the attachment. And this is the code that I wrote:

import numpy as np

#declaration of parity-check matrix
H = np.array([[1, 1, 0, 1, 0, 0], [0, 1, 1, 0, 1, 0],
            [1, 0, 0, 0, 1, 1], [0, 0, 1, 1, 0, 1]])

#setting the input and output of the LDPC
c = np.array([0, 0, 1, 0, 1, 1])
y = np.array([0, 1, 1, 0, 1, 1])

#initialization of bit flipping decoding
M = y[::].copy()
w_r = 2
w_c = 3
m = np.size(H,0)
N = np.size(H,1)
E = np.zeros((m, N))

#initializing value of B_j
B_j = np.where(H == 1)
B = B_j[1].reshape(m, w_c)

#setting value for i_prime
for k in range (w_c):
    i_prime = np.array_split (B[k], 3)
    split_i = np.array_split (i_prime, w_c)

#check message
    for j in range (m):
        for i in range (N):
            for i_prime in B:
                M_value = np.array_split(M[B], m)
                split_M = np.array_split(M_value, m)
                if split_i != i:
                    print (E)

I am stuck at line 11 of the algorithm, and I am looking forward to any helpers. Thanks...

[jefsummers]

My last math course was in 1979, so my understanding of the notation is a bit rusty. Can you explain line 11 in words? Or better, what steps you would take to perform that line?

[Larz60+]

if you don't have a copy, You can see the entire section of "Iterative Error Correction"
here: https://books.google.com/books?hl=en&lr=...zOnWrVD8ZQ

There are easier ways to do this in python (if not an assignment), see: https://stackoverflow.com/a/27958612

[divon]

My last math course was in 1979, so my understanding of the notation is a bit rusty. Can you explain line 11 in words? Or better, what steps you would take to perform that line?

Thank you very much for your reply, @jefsummers. The steps for performing line 11:

1. Get the value of B based on the matrix H. since matrix H is: , then B_0 which it should take from 1st row of H, the value is: B_0 = [0, 1, 3]. And the same pattern until B_3 that taken from 4th row with value: B_3 = [2, 3, 5]. In my code, it is in line 20.
   
   
2. Set the value for i_prime with the same value of B_j. For example, if j = 0, B_0 = [0, 1, 3], then i_prime = 0, 1, 3. And i_prime will be the constraints for XOR operation of value in matrix M, means that when j = 0, i = 0, B_0 = [0, 1, 3], i_prime = 0, 1, 3, when E_0, 0 for i_prime = 0 the XOR operation will be M_1 ^ M_3 (M_0 is not included since i = i_prime = 0)
   

I have attached the calculation that I have done manually, and I hope it will help.
   
   

[divon]

if you don't have a copy, You can see the entire section of "Iterative Error Correction"
here: https://books.google.com/books?hl=en&lr=...zOnWrVD8ZQ

There are easier ways to do this in python (if not an assignment), see: https://stackoverflow.com/a/27958612

Thank you very much for giving the link to "Iterative Error Correction" @Larz60+ . I have checked the "easier ways" link that you gave to me, unfortunately, my professor wanted me to make the program that must follow each step of the algorithm.

Right now I am confused about how to get the calculation in line 11 of the algorithm. Because I have obtained the value for i_prime, B_j, but I am stuck at separating M = [0, 1, 1, 0, 1, 1] into M[0] = 0, M[1] = 1, M[2] = 1, M[3] = 0, M[4] = 1, M[5] = 1 in order to calculate it in XOR manner at line 11.

[divon]

Hello everyone, especially to @jefsummers
I will try to explain the algorithm:

1. I have M = [0 1 1 0 1 1] and the value will be taken individually later.
   
2. The explanation of B_j is the same as in my previous reply.
   
3. In the loop of j in range 4 and i in range 6, I will do the equation E[j, i] = XOR of all M[i'].
   For example: when j = 0, i = 0, B_0 = 0, 1, 3, i' = 0, 1, 3, E[0, 0] = M[1] ^ M[3] (M[0] is not included because i' = i).
   Same thing also happened in i = 1 at E[0, 1] = M[0] ^ M[3] (M[1] is not included because i' = i)
   But when j = 0, i = 2, E[0, 2] = M[0] ^ M[1] ^ M[3]. How to implement this condition in python?
   

Here is the update of my code:

import numpy as np

#declaration of parity-check matrix
H = np.array([[1, 1, 0, 1, 0, 0], [0, 1, 1, 0, 1, 0],
            [1, 0, 0, 0, 1, 1], [0, 0, 1, 1, 0, 1]])

#setting the input and output of the LDPC
c = np.array([0, 0, 1, 0, 1, 1])
y = np.array([0, 1, 1, 0, 1, 1])

#initialization of bit flipping decoding
w_r = 2
w_c = 3
m = np.size(H,0)
N = np.size(H,1)
E = np.zeros((m, N))
#Code for obtain each value of matrix M
M = np.hsplit(y[::].copy(), N)

#initializing value of B
B_j = np.where(H == 1)
B = B_j[1].reshape(m, w_c)

for j in range (m):
    for i in range (N):
        for i_prime in B[j]:
            print (i_prime)
            #this part is supposed to be for line 11 of the algorithm and I am stuck at it
            if i_prime != i:
                E[j, i] = M[i_prime != i] ^ M[i_prime != i]

[divon]

Hello everyone,
I would like to post today's update, in this program I can obtain the value of M[i_prime] when i != i_prime, but I am still stuck for representing line 11 of the algorithm into python

import numpy as np

#declaration of parity-check matrix
H = np.array([[1, 1, 0, 1, 0, 0], [0, 1, 1, 0, 1, 0],
            [1, 0, 0, 0, 1, 1], [0, 0, 1, 1, 0, 1]])

#setting the input and output of the LDPC
c = np.array([0, 0, 1, 0, 1, 1])
y = np.array([0, 1, 1, 0, 1, 1])

#initialization of bit flipping decoding
w_r = 2
w_c = 3
m = np.size(H,0)
N = np.size(H,1)
M = np.hsplit(y[::].copy(), N)
E = 0

#initializing value of B
B_j = np.where(H == 1)
B = B_j[1].reshape(m, w_c)

for j in range (m):
    for i in range (N):
        for i_prime in B[j]:
            if i != i_prime:
                print (M[i_prime], i, i_prime)
                E = M[i_prime] ^ M[i_prime + 1] #this part is for equation in line 11 of the algorithm
                print (E)

[divon]

Hello everyone
I would like to post an update on my quest to translate line 11 of the algorithm to python, and finally, I made it. The code is like this:

import numpy as np

#declaration of the parity-check matrix
H = np.array([[1, 1, 0, 1, 0, 0], [0, 1, 1, 0, 1, 0],
            [1, 0, 0, 0, 1, 1], [0, 0, 1, 1, 0, 1]])

#setting the input and output of the LDPC
c = np.array([0, 0, 1, 0, 1, 1])
y = np.array([0, 1, 1, 0, 1, 1])

#initialization of bit flipping decoding
w_r = 2
w_c = 3
m = np.size(H,0)
N = np.size(H,1)
M = y[::].copy()
E = np.zeros((m, N), dtype=int)
l_max = 150

#initializing value of B
B_j,B_i = np.where(H == 1)
B = [[],[],[],[]]
for temp_index in range(B_j.size):
    B[B_j[temp_index]].append(B_i[temp_index])

"""B_j = np.where(H == 1)
B = B_j[1].reshape(m, w_c)"""

#Iteration count
l = 0
if l <= l_max:

#Step 1: Check messages
    for j in range (m):
        for i in range (N):
            for i_prime in B[j]:
                if i != i_prime:
                    #E[j][i] = np.bitwise_xor(E[j][i], M[i_prime])
                    E[j][i] ^= M[i_prime]

#Step 2: Bit messages
    """for i in range (N):
        if M[i] == 0 and E[1][i] > E[0][i]:
            M[i] = 1
        elif M[i] == 1 and E[0][i] > E[1][i]:
            M[i] = 0"""

I thought my program is complete, but there are 19 more lines to go. And for the next problem is to obtain how many times numbers one and zero show for each column of the matrix E. For example, if matrix E:


Then, in the first column, the number of one is shown 2 times and the same with zero. How to obtain this value? When I tried the code

#Step 2: Bit messages
    """for i in range (N):
        if M[i] == 0 and E[1][i] > E[0][i]:
            M[i] = 1
        elif M[i] == 1 and E[0][i] > E[1][i]:
            M[i] = 0"""

The result is not correct and I have tried DataFrame from pandas, but it is not working. The code for DataFrame:

#change the code below Step 2 into this
    for i in range (N):
        M_i = pd.DataFrame(E)
        M_i.mode(axis=0)
print (M_i)

Please give me suggestions for this.

[divon]

Hello everyone
Finally I have solved the bit-flipping algorithm, the code will be like this

import numpy as np

#declaration of parity-check matrix
H = np.array([[1, 1, 0, 1, 0, 0], [0, 1, 1, 0, 1, 0],
            [1, 0, 0, 0, 1, 1], [0, 0, 1, 1, 0, 1]])

#setting the input and output of the LDPC
c = np.array([0, 0, 1, 0, 1, 1])
y = np.array([0, 1, 1, 0, 1, 1])

#initialization of bit flipping decoding
w_r = 2
w_c = 3
m = np.size(H,0)
N = np.size(H,1)
M = y[::].copy()
M_i = np.zeros((6), dtype=int)
s = np.zeros((4), dtype=int)
E = np.zeros((m, N), dtype=int)
l_max = 150

#initializing value of B
B_j,B_i = np.where(H == 1)
B = [[],[],[],[]]
for temp_index in range(B_j.size):
    B[B_j[temp_index]].append(B_i[temp_index])

"""B_j = np.where(H == 1)
B = B_j[1].reshape(m, w_c)"""

#Iteration count
l = 0
while l <= l_max:

#Step 1: Check messages
    for j in range (m):
        for i in range (N):
            for i_prime in B[j]:
                if i != i_prime:
                    #E[j][i] = np.bitwise_xor(E[j][i], M[i_prime])
                    E[j][i] ^= M[i_prime]

#Step 2: Bit messages
    for i in range (N):
        M_i[i] = (E[:, i] == 1). sum()
        if M[i] == 0 and M_i[i] < 2:
            M[i] = 1
        elif M[i] == 1 and M_i[i] < 2:
            M[i] = 0

#Stopping criteria
    for j in range (m):
        for i_prime in B[j]:
            s[j] ^= M[i_prime]

    count = np.sum(s)

    if count == 0:
        print ("The codeword is: ", M)
        break
    elif l == l_max:
        print ("The codeword is failed to obtain, since Maximum iteration has achieved.")
        break
    elif count != 0:
        l = l + 1
        continue

[Larz60+]

Thanks for sharing solution