Doing column permutation under row overlap constraint

Question

In coding theory, there are parity-check codes whose parity-check matrices $H$ are generated via column permutations. For instance, the binary LDPC codes constructed in Gallager's 1962 IRE Trans paper uses the following $H$ matrix:

$$H = \left[\begin{array}{c} X_1\\ X_2\\ \vdots\\ X_n \end{array}\right]$$

where submatrices $X_i$, $2 \leq i \leq n$ are obtained by randomly permuting columns of $X_1$ of certain kind. However, to make the codes suitable to iterative decoding, typically we impose one restriction which requires that any two row vectors in $H$ mustn't have 2 or more overlapping nonzero elements. In other words, we would like $H$ to be free of $2 \times 2$ all-one matrix.

I tried to write a program to do that, but so far my effort is not good. I'm wondering if there is any known algorithmic way to adjust the permutated submatrices $X_1, \dots, X_n$ so that the overlapping constraint is satisfied?

Thanks for your help!

Answer 1

I doubt there is a particular algorithm worth mentioning for avoiding $2 \times 2$ all-one submatrices (or better known as $4$-cycles in the context of LDPC codes) in parity-check matrices which is specially tailored for Gallager's original method you described.

If you follow the method given in the 1962 paper in the most straightforward way, your $a\times b$ binary matrix $X_1$ should be of the form

$$X_1 = \left[\begin{array}{cccc} \boldsymbol{1}&\boldsymbol{0}&\dots&\boldsymbol{0}\\ \boldsymbol{0}&\boldsymbol{1}&\dots&\boldsymbol{0}\\ \vdots&\vdots&\ddots&\vdots\\ \boldsymbol{0}&\boldsymbol{0}&\dots&\boldsymbol{1} \end{array}\right],$$

where $\boldsymbol{0}$ and $\boldsymbol{1}$ are the $i$-dimensional all-zero and all-one row vectors for some fixed divisor $i$ of $b$ respectively. So, your parity-check matrix $H$ is obtained by stacking $n$ copies of $X_1$ for some small integer $n$ and then (pseudo)-randomly permuting the columns of each of the $n-1$ layers. Because the whole point of Gallager codes is to randomly pick parity-check matrixes from an ensemble in the first place, any sensible pseudo-random method for avoiding $4$-cycles as you permute columns should be fine as long as it works. If anything, you're not supposed to make your permutations too specific. If you can't seem to get $4$-cycle-free $H$ that works fine in simulations, most likely you're using the wrong kind of $X_1$ (or maybe not picking permutations randomly enough).

If you would like another textbook example of pseudo-random algorithms for avoiding $4$-cycles in LDPC codes, you can find one by MacKay and Neal in Section 1.3.1 of this article by S. J. Johnson, where the author gives a brief verbal explanation and pseudo-code (see pages 14–15. Also, MacKay and Neal's paper is Ref. [21]). While their construction is not exactly the same as Gallager's original method, you can see that it doesn't need esoteric hacking knowledge to avoid $4$-cycles.

If you're ok with a bipartite graph approach for constructing LDPC codes rather than the matrix view taken by Gallager, and would like a more recent and well-known algorithm for avoiding short cycles, the progressive edge-growth (PEG) algorithm is among the most effective ones and is known to work great in the finite length regime like in your case:

X.-Y. Hu, E. Eleftheriou, and D. M. Arnold, Regular and irregular progressive edge-growth Tanner graphs, IEEE Trans. Inform. Theory, 51 (2005) 386–398.