Question: Generate submatrices using random column permutation with constraints

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 used the Maple function randperm to do column permutation. But I'm wondering is there any known algorithmic way to adjust the permutated submatrices X1..Xn so that the overlapping constraint is satisfied?

Thanks in advance,

Kelvin

 

Please Wait...