# Verifying LDPC matrices in CCSDS blue book

My understanding is that LDPC is a linear block code such that its generator matrix $$\mathbf{G}$$ and parity check matrix $$\mathbf{H}$$ satisfy $$\mathbf{GH}^T=0$$.

I am using the CCSDS blue book here as reference, specifically Figures 7-1 and 7-2.

Figure 7-1 and Table 7-1 give rise to a parity check matrix, constructed using circulants, with column weight 4 and row weight 32. Aside from giving regular weights, the circulants seem somewhat arbitrary;

• Is there a reason/method behind the circulants?

Also, I have implemented both matrices in MATLAB but do not get a matrix of zeros when multiplying the generator matrix with the transpose of the parity check matrix, a result that I am also getting with GitHub - nicopi - LDPC Codes for Deep-Space Communications (specifically with the $$\mathbf{G}$$ and $$\mathbf{H}$$ matrices in data.mat).

• Is there anything I am missing conceptually that would explain this parity check result?

I have written the following code to create the matrices:

Helper function to create a matrix given the first row of all circulants:

function [matrix,matrixHex] = auxiliary_expandCirculants(circulantSize,matrixSize,circulantFirstRow,circulantFirstRowType)
% Inputs:
%   circulantSize: size of the circulant
%   matrixSize: dimensions of the matrix in terms of circulants
%   circulantFirstRow: either 1) a matrix where each row corresponds to the
%       locations of 1s in the first row of each circulant, or 2) a cell
%       containing character arrays of the hex value of the first row of
%       each circulant; circulants are enumerated from left to right and
%       top to bottom
%   circulantFirstRowType: 'binary' if circulantFirstRow is a matrix or
%   'hex' if circulantFirstRow is a cell
% Outputs:
%   matrix: the matrix corresponding to the specified input circulants
%   matrixHex: a single character array containing the hex values of all
%       circulant first rows

% check for errors
if prod(matrixSize)~=length(circulantFirstRow)
error('The number of circulants in the matrix and the number of entries in the input data file should be equal.');
end

if strcmp(circulantFirstRowType,'binary')
matrixHex = '';
elseif strcmp(circulantFirstRowType,'hex')
matrixHex = strjoin(circulantFirstRow);
matrixHex = matrixHex(~isspace(matrixHex));
end

% fill matrix
matrix = zeros(circulantSize*matrixSize);
for ii=1:matrixSize(1)
for jj=1:matrixSize(2)

% used to index the input 'circulantFirstRow'
idxMatrix = (ii-1)*matrixSize(2)+jj;

% represent the first row of the circulant as a binary vector
if strcmp(circulantFirstRowType,'binary')
row = zeros(1,circulantSize);
row(circulantFirstRow(idxMatrix,:)+1) = 1; % one-based indexing
elseif strcmp(circulantFirstRowType,'hex')
currentHex = circulantFirstRow{idxMatrix};
row = [];
for kk=1:ceil(circulantSize/4)
row = [de2bi(hex2dec(currentHex(end-kk+1)),'left-msb',min(4,circulantSize-length(row))) row]; % generate from right to left
end
end

circulant = toeplitz([row(1) fliplr(row(2:end))],row);
idxMatrixRows = (ii-1)*circulantSize+1:ii*circulantSize;
idxMatrixCols = (jj-1)*circulantSize+1:jj*circulantSize;
matrix(idxMatrixRows,idxMatrixCols) = circulant;

% generate hexadecimal value for circulant first rows
if strcmp(circulantFirstRowType,'binary')
circulantFirstRowHex = '';
for kk=1:ceil(circulantSize/4)
idxLeft = max(1,circulantSize-kk*4+1);
idxRight = circulantSize-(kk-1)*4;
circulantFirstRowHex = [dec2hex(bi2de(row(idxLeft:idxRight),'left-msb'),1) circulantFirstRowHex]; % generate each hex value from right to left
end
matrixHex = [matrixHex circulantFirstRowHex]; % concatenate all hex values from left to right
end
end
end

end


Main file:

circulantSize = 511;
baseMatrixSize = [2 16];
circulantFirstRow = readmatrix('data_8176-7156.csv'); % corresponds to Table 7-1 of the blue book
fileID = fopen('data_generatorParityColumns.txt','r'); % corresponds to Table C-1 of the blue book
formatSpec = '%s';
generatorParitySize = [baseMatrixSize(2)-baseMatrixSize(1) baseMatrixSize(1)];
generatorParityColumnsHex = textscan(fileID,formatSpec);
generatorParityColumnsHex = generatorParityColumnsHex{1};

% create base matrix as given by Figure 7-1 of the blue book
[baseMatrix,baseMatrixHex] = auxiliary_expandCirculants(circulantSize,baseMatrixSize,circulantFirstRow,'binary');

% create generator matrix as given by Figure 7-2 of the blue book
[generatorParityColumns,~] = auxiliary_expandCirculants(circulantSize,generatorParitySize,generatorParityColumnsHex,'hex');
generatorMatrix = [eye(size(generatorParityColumns,1)) generatorParityColumns];

generatorMatrix*baseMatrix.'


data_8176-7156.csv: a two-column csv file corresponding to the middle column of Table 7-1 of the blue book

0   176
12  239
0   352
24  431
0   392
151 409
0   351
9   359
0   307
53  329
0   207
18  281
0   399
202 457
0   247
36  261
99  471
130 473
198 435
260 478
215 420
282 481
48  396
193 445
273 430
302 451
96  379
191 386
244 467
364 470
51  382
192 414


'data_generatorParityColumns.txt': a text file corresponding to Table C-1 of the blue book

55BF56CC55283DFEEFEA8C8CFF04E1EBD9067710988E25048D67525426939E2068D2DC6FCD2F822BEB6BD96C8A76F4932AAE9BC53AD20A2A9C86BB461E43759C
6855AE08698A50AA3051768793DC238544AF3FE987391021AAF6383A6503409C3CE971A80B3ECE12363EE809A01D91204F1811123EAB867D3E40E8C652585D28
62B21CF0AEE0649FA67B7D0EA6551C1CD194CA77501E0FCF8C85867B9CF679C18BCF7939E10F8550661848A4E0A9E9EDB7DAB9EDABA18C168C8E28AACDDEAB1E
681A8E51420BD8294ECE13E491D618083FFBBA830DB5FAF330209877D801F92B5E07117C57E75F6F0D873B3E520F21EAFD78C1612C6228111A369D5790F5929A
35951FEE6F20C902296C9488003345E6C5526C5519230454C556B8A04FC0DC642D682D94B4594B5197037DF15B5817B26F16D0A3302C09383412822F6D2B234E
5D80A6007C175B5C0DD88A442440E2C29C6A136BBCE0D95A58A83B48CA0E7474E9476C92E33D164BFF943A61CE1031DFF441B0B175209B498394F4794644392E
60CD1F1C282A1612657E8C7C1420332CA245C0756F78744C807966C3E1326438878BD2CCC83388415A612705AB192B3512EEF0D95248F7B73E5B0F412BF76DB4
434B697B98C9F3E48502C8DBD891D0A0386996146DEBEF11D4B833033E05EDC28F808F25E8F314135E6675B7608B66F7FF3392308242930025DDC4BB65CD7B6E
766855125CFDC804DAF8DBE3660E8686420230ED4E049DF11D82E357C54FE256EA01F5681D95544C7A1E32B7C30A8E6CF5D0869E754FFDE6AEFA6D7BE8F1B148
222975D325A487FE560A6D146311578D9C5501D28BC0A1FB48C9BDA173E869133A3AA9506C42AE9F466E85611FC5F8F74E439638D66D2F00C682987A96D8887C
14B5F98E8D55FC8E9B4EE453C6963E052147A857AC1E08675D99A308E7269FAC5600D7B155DE8CB1BAC786F45B46B523073692DE745FDF10724DDA38FD093B1C
1B71AFFB8117BCF8B5D002A99FEEA49503C0359B056963FE5271140E626F6F8FCE9F29B37047F9CA89EBCE760405C6277F329065DF21AB3B779AB3E8C8955400
2CD8140C8A37DE0D0261259F63AA2A420A8F81FECB661DBA5C62DF6C817B4A61D2BC1F068A50DFD0EA8FE1BD387601062E2276A4987A19A70B460C54F215E184

Found out where the issue was. The above code gives a matrix of 0s, 2s, and 4s, but I forgot to take the matrix multiplication $$\mathbf G\mathbf H^T$$ modulo 2, which would give the expected matrix of all zeros.