2
$\begingroup$

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 open-source code on Github (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
64B71F486AD57125660C4512247B229F0017BA649C6C11148FB00B70808286F1A9790748D296A593FA4FD2C6D7AAF7750F0C71B31AEE5B400C7F5D73AAF00710
681A8E51420BD8294ECE13E491D618083FFBBA830DB5FAF330209877D801F92B5E07117C57E75F6F0D873B3E520F21EAFD78C1612C6228111A369D5790F5929A
04DF1DD77F1C20C1FB570D7DD7A1219EAECEA4B2877282651B0FFE713DF338A63263BC0E324A87E2DC1AD64C9F10AAA585ED6905946EE167A73CF04AD2AF9218
35951FEE6F20C902296C9488003345E6C5526C5519230454C556B8A04FC0DC642D682D94B4594B5197037DF15B5817B26F16D0A3302C09383412822F6D2B234E
7681CF7F278380E28F1262B22F40BF3405BFB92311A8A34D084C086464777431DBFDDD2E82A2E6742BAD6533B51B2BDEE0377E9F6E63DCA0B0F1DF97E73D5CD8
188157AE41830744BAE0ADA6295E08B79A44081E111F69BBE7831D07BEEBF76232E065F752D4F218D39B6C5BF20AE5B8FF172A7F1F680E6BF5AAC3C4343736C2
5D80A6007C175B5C0DD88A442440E2C29C6A136BBCE0D95A58A83B48CA0E7474E9476C92E33D164BFF943A61CE1031DFF441B0B175209B498394F4794644392E
60CD1F1C282A1612657E8C7C1420332CA245C0756F78744C807966C3E1326438878BD2CCC83388415A612705AB192B3512EEF0D95248F7B73E5B0F412BF76DB4
434B697B98C9F3E48502C8DBD891D0A0386996146DEBEF11D4B833033E05EDC28F808F25E8F314135E6675B7608B66F7FF3392308242930025DDC4BB65CD7B6E
766855125CFDC804DAF8DBE3660E8686420230ED4E049DF11D82E357C54FE256EA01F5681D95544C7A1E32B7C30A8E6CF5D0869E754FFDE6AEFA6D7BE8F1B148
222975D325A487FE560A6D146311578D9C5501D28BC0A1FB48C9BDA173E869133A3AA9506C42AE9F466E85611FC5F8F74E439638D66D2F00C682987A96D8887C
14B5F98E8D55FC8E9B4EE453C6963E052147A857AC1E08675D99A308E7269FAC5600D7B155DE8CB1BAC786F45B46B523073692DE745FDF10724DDA38FD093B1C
1B71AFFB8117BCF8B5D002A99FEEA49503C0359B056963FE5271140E626F6F8FCE9F29B37047F9CA89EBCE760405C6277F329065DF21AB3B779AB3E8C8955400
0008B4E899E5F7E692BDCE69CE3FAD997183CFAEB2785D0C3D9CAE510316D4BD65A2A06CBA7F4E4C4A80839ACA81012343648EEA8DBBA2464A68E115AB3F4034
5B7FE6808A10EA42FEF0ED9B41920F82023085C106FBBC1F56B567A14257021BC5FDA60CBA05B08FAD6DC3B0410295884C7CCDE0E56347D649DE6DDCEEB0C95E
5E9B2B33EF82D0E64AA2226D6A0ADCD179D5932EE1CF401B336449D0FF775754CA56650716E61A43F963D59865C7F017F53830514306649822CAA72C152F6EB2
2CD8140C8A37DE0D0261259F63AA2A420A8F81FECB661DBA5C62DF6C817B4A61D2BC1F068A50DFD0EA8FE1BD387601062E2276A4987A19A70B460C54F215E184
06F1FF249192F2EAF063488E267EEE994E7760995C4FA6FFA0E4241825A7F5B65C74FB16AC4C891BC008D33AD4FF97523EE5BD14126916E0502FF2F8E4A07FC2
65287840D00243278F41CE1156D1868F24E02F91D3A1886ACE906CE741662B40B4EFDFB90F76C1ADD884D920AFA8B3427EEB84A759FA02E00635743F50B942F0
4109DA2A24E41B1F375645229981D4B7E88C36A12DAB64E91C764CC43CCEC188EC8C5855C8FF488BB91003602BEF43DBEC4A621048906A2CDC5DBD4103431DB8
2185E3BC7076BA51AAD6B199C8C60BCD70E8245B874927136E6D8DD527DF0693DC10A1C8E51B5BE93FF7538FA138B335738F4315361ABF8C73BF40593AE22BE4
228845775A262505B47288E065B23B4A6D78AFBDDB2356B392C692EF56A35AB4AA27767DE72F058C6484457C95A8CCDD0EF225ABA56B7657B7F0E947DC17F972
2630C6F79878E50CF5ABD353A6ED80BEACC7169179EA57435E44411BC7D566136DFA983019F3443DE8E4C60940BC4E31DCEAD514D755AF95A622585D69572692
7273E8342918E097B1C1F5FEF32A150AEF5E11184782B5BD5A1D8071E94578B0AC722D7BF49E8C78D391294371FFBA7B88FABF8CC03A62B940CE60D669DFB7B6
087EA12042793307045B283D7305E93D8F74725034E77D25D3FF043ADC5F8B5B186DB70A968A816835EFB575952EAE7EA4E76DF0D5F097590E1A2A978025573E
$\endgroup$
2
  • $\begingroup$ Hi! To rule out minor programming bugs: You don't happen to have a few lines of matlab where you just construct H and G and then multiply them? So that we can run the same? $\endgroup$ – Marcus Müller Dec 26 '20 at 8:58
  • $\begingroup$ Hi Marcus, thank you for your comment! I have added my code to the original post. I was also wondering if my result is due to any programming bugs, but I compared by matrices to the Github repo I mentioned and got the same result. I also manually inspected at least a small portion of each matrix against the values given by the blue book. The only other thing I can think of, aside from programming bugs or conceptual errors, is that I am getting rank(H)=1021 but the blue book says the rank should be 1020. $\endgroup$ – Austin Dec 26 '20 at 9:58
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.