# Doing column permutation under row overlap constraint

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!

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. ). 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.