# Matrix column permutation under constraint

Apologize if you've read my question on Mathoverflow, I'm very curious about whether there's an answer to this.

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: $$H = \begin{bmatrix} \text{---} &X_1 &\text{---}\\ \text{---} &X_2 &\text{---}\\ &\vdots &\\ \text{---} &X_n &\text{---}\\ \end{bmatrix}$$ where submatrices $X_2,\ldots,X_n$ are just random column permutations of $X_1$. 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 $V_a$ and $V_b$, there exists an index $i$ s.t. $V_a[i] = V_b[i]$;

I tried to write a program to do that, but so far my effort is not good.

The question is: Is there any known algorithmic way to adjust the permutated submatrices $X_1,\ldots,X_n$ so that the overlapping constraint is satisfied?

-
Using Latex will be better. – Shiyu Jun 23 '11 at 3:04
I'm fairly sure that you forgot to include the condition that the two or more overlapping elements should be non-zero (i.e. equal to 1, if you're in binary case). That is equivalent to eliminating 4-cycles from the Tanner graph. – Jyrki Lahtonen Jun 23 '11 at 12:00
@percusse: The OP hasn't been heard from since June 24th. Wonder whether he is still interested? – Jyrki Lahtonen Aug 24 '11 at 20:35
@Jyrki: I have just put the Latex code in place, because it showed up on the frontpage. Took my 2 minutes but I certainly had no intention to revive this. :) – user13838 Aug 24 '11 at 20:44

I don't know an exact answer to your question, because it depends on several parameters, whether your goal is at all achievable. If there are too many 1s on your check matrix, this simply cannot be done. This is simply too long to be a comment, so I make it an answer instead.

I would have thought that eliminating 4-cycles from the Tanner graph would usually be easy. Eliminating 6-cycles and up is harder.

There are several approaches to constructing good LDPC parity check matrices based on, for example blocks, that are various powers of a matrix of the form $$\left(\begin{array}{ccccc} 0&1&0&\cdots&0\\ 0&0&1&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&0\\ 0&0&0&\cdots&1\\ 1&0&0&\cdots&0\end{array}\right),$$ where the ones are one position to the right from the diagonal and then at the bottom left.

Have you searched IEEE Xplore for this kind of constructions or others?

But anyway, I would have thought a that a simple procedure like generating random permutations, checking for the presence of 4-cycles, and then, if need be, breaking a 4-cycle by swapping two columns of the newly inserted block of rows, would work reasonably well.

Are you sure your parity check matrix has a low enough density? If your density is too high, then 4-cycle avoidance becomes much more difficult, indeed (and from some point on it becomes impossible!). To give you an idea: IIRC the check matrix of one of the LDPC codes specified in the standard for the next generation of digitial video broadcasting has 64800 columns and 21600 rows. The number of 1s per column on that matrix varies between 2 and 13 (3 being the most common value), so the density of 1s is much less than 1 in 1000. I'm bringing this up only in order to eliminate the possibility that you are testing your program with smaller input without realizing that your parameters may be out of range.

-