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!
 A: 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.
