How to determine LDPC generator matrix form parity check matrix (802.16e)

Question

I have parity check table H for 802.16e standard with 1/2 rate and expansion factor 96:

Hb = 
-1 94 73 -1 -1 -1 -1 -1 55 83 -1 -1 7 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 27 -1 -1 -1 22 79 9 -1 -1 -1 12 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 24 22 81 -1 33 -1 -1 -1 0 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1
61 -1 47 -1 -1 -1 -1 -1 65 25 -1 -1 -1 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1
-1 -1 39 -1 -1 -1 84 -1 -1 41 72 -1 -1 -1 -1 -1 0 0 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 46 40 -1 82 -1 -1 -1 79 0 -1 -1 -1 -1 0 0 -1 -1 -1 -1 -1
-1 -1 95 53 -1 -1 -1 -1 -1 14 18 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 -1 -1
-1 11 73 -1 -1 -1 2 -1 -1 47 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 -1
12 -1 -1 -1 83 24 -1 43 -1 -1 -1 51 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1
-1 -1 -1 -1 -1 94 -1 59 -1 -1 70 72 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1
-1 -1 7 65 -1 -1 -1 -1 39 49 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0
43 -1 -1 -1 -1 66 -1 41 -1 -1 -1 26 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0

Then I get H in binary form with sizes 1152x2304: spy(H) img

I want to get a matrix generator G from H, how can I do it? I need to encode words by multiplying words by a generator matrix (cw = m*G, where m - input word, cw - code word).

I try different ways, but at the end i cant reach nnz(mod(G*H', 2)) equal 0.

Renaud Pacalet Renaud Pacalet · Accepted Answer · 2017-07-27T08:46:17

An old question but as I had the same and designed a solution...

This LDPC code is systematic, that is, the code words contain the information bits, and the information bits are the leading bits of the code word. All computations are made in GF2 (Galois field of size 2).

Let us denote:

n the code word length (and number of columns of H and G),
m the number of parity bits (and the number of rows of H),
k=n-m the number of information bits (and the number of rows of G),
[A,B] the matrix formed by concatenating left to right the two sub-matrices A and B (when A and B have the same number of rows),
A^ the transposed matrix of matrix A,
Ip the identity matrix of size p,
0p the zero vector of size p,
inv(A) the inverse of square matrix A.

If u is a k-bits word to encode (information bits) and x the corresponding n-bits code word, as the code is systematic with leading information bits, we have:

x = u * G
  = u * [Ik,F] = [u,u * F] = [u,c]
c = u * F

where F is a k-rows, m-columns matrix. We can also represent the parity check matrix H as H = [A,B] where A is a m-rows, k-columns matrix and B is a m-rows, m-columns (square) matrix. As a matter of fact, B is not singular (it has an inverse). So:

H * x^ = [A,B] * x^ = [A,B] * [u,c]^ = A * u^ + B * c^ = 0n^
(H * x^)^ = u * A^ + c * B^ = 0n
(H * x^)^ * inv(B^) = u * A^ * inv(B^) + c = 0n

From which it comes (we are in GF2):

c = u * (A^ * inv(B^))

And thus:

F = A^ * inv(B^)
G = [Ik,A^ * inv(B^)]

An octave code that computes G from H (where H is already in GF2) and checks that G * H^ = 0 (the Matlab code should be very similar):

pkg load communications

function F = make_gen_min(H)
    m = size(H, 1);
    n = size(H, 2);
    k = n - m;
    A = H(1:m, 1:k);
    B = H(1:m, k+1:n);
    F = transpose(A) * inv(transpose(B)); 
endfunction

function G = make_gen(H)
    m = size(H, 1);
    n = size(H, 2);
    k = n - m;
    F = make_gen_min(H);
    G = [gf(eye(k), 2), F];
endfunction

H = [...];

G = make_gen(H);
if(any(G * transpose(H)))
    disp ("Error: G * transpose(H) != 0");
else
    disp ("Note: G * transpose(H) == 0");
endif

How to determine LDPC generator matrix form parity check matrix (802.16e)

1 Answers