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

[ X1 ]

[ X2 ]

[ .... ]

[ Xn ]

where submatrices X2 .. Xn are just random column permutations of X1. However, to make the codes efficient in decoding, there is one restriction which requires that any two row vectors in H mustn't have 2 or more overlapping elements. By overlapping, I mean for two different row vectors of H, say Va and Vb, there exists an index i s.t. Va[i] = Vb[i];

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

Thanks for your help!

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!