This software makes sparse matrices built from permutation matrices
and identity matrices. The normal constraint that columns should
not overlap by more than 1 is satisfied if all the submatrices have the same
size and there are only two matrices per column. Beyond that, there
is a risk of overlaps exceeding 1. By using huge matrices you can reduce
this probability. (The expected number of 2-overlaps is of order 1
independent of N.)
** Note GH.p is superceded by GHG.p, whose usage is very similar, but it
combines GH.p and GHmaker.p**

The usage of GH.p is

GH.p (N=10000) (file=GHmaker.p) specfile () = (optional arguments)The program GH.p suggests a value for M and writes another program GHmaker.p whose usage is

GHmaker.p (seed=1548) (M=1459) > alist.fileThis program creates a parity check matrix H, written in "alist" format. The matrix is written in accordance with the design specified in specfile. The design allows 1s to be added to the matrix H in blocks. The syntax is as follows:

# comment lines start with # # leading blanks are ignored and comments can be put # at ends of lines too # # the first line must specify the value of lambda, the ratio N/M, in the # form n/m # example, for a rate 1/2 code: lambda 2/1 # whereas for a rate 1/4 code, lambda 4/3 # # All measurements are made in units of M. All cartesian coordinates # are (horizontal,vertical) # # subsequent lines are either block commands or control commands. # # block commands come in three flavours: # Identity blocks: 1x3 I 1/3 at 0/1,0/1 5x1 I 1/3 at 1/3,0/1 # and Permutation blocks: 5x2 P 1/3 at 1/3,1/3 # S ("staircase") produces a weight 2 square like an identity matrix shifted 1x1 S 1/1 at 0/1,0/1 # for future purposes the following types are also intended: # convolutional code. K and L produce two different addidas stripes 1x1 K 1/1 at 0/1,0/1 1x1 L 1/1 at 1/1,0/1 # commands useful for making figures: # interleaver operation, i.e. reorder columns. This is drawn as a circle # with an arrow 1x1 C 1/1 at 0/1,0/1 # this makes an oval 1x1 O 1/3x1/1 at 0/1,0/1 # puncturing 1 p 1/1 at 0/1 # Note a superposed C and I are identical to a P # # control commands: # registerI 1/3 # registerI records the permutation matrix I of size M/3 as having been # included in the matrix, so subsequent permutations will be forbidden # from matching # refresh # "refresh" purges the memory of permutation matrices that have been # written. Until a "refresh", the GHmaker program will take care # *not* to produce two P's that clash with each other. # you must do a refresh whenever there is a change of size of # block of type I or P, if there are any more P's to come. # recommended order is to do all the Is of one size first then all # the Ps of that size.The above commands produce:

(a)

1x3 I 1/3 at 0/1,0/1--- a vertical (1x3) column of identity matrices with top left corner at "0,0" (actually 1,1); all these matrices have size M/3 * M/3.

I 0 0 0 0 0 I 0 0 0 0 0 I 0 0 0 0 0(b)

5x1 I 1/3 at 1/3,0/1--- a horizontal row of 5 identity matrices, size M/3 * M/3.

0 I I I I I 0 0 0 0 0 0 0 0 0 0 0 0

5x2 P 1/3 at 1/3,1/3--- a block of random permutation matrices, size M/3 * M/3.

0 0 0 0 0 0 0 P P P P P 0 P P P P PThe end result is a standard construction 1A Gallager code with t=3 and t_r=6.

The spec file

lambda 3/2 1x2 I 1/2 at 0/1,0/1 3x3 P 1/3 at 1/2,0/1Produces a superb rate 1/3 code of construction 2A.

The same syntax can be used to make other irregular codes, by using unequal size matrices I and P, or by superposition.

When I say construction 1A and construction 2A, this is not quite accurate. In MacKay/Neal papers, the constructions used random weight 2 or 3 columns, rather than permutation matrices.

A possible addition to the syntax above would be to have an object of type T which is a block of uniform weight columns made at random. The syntax would be

1x1 T t=3 2/1x1/1 at 0/1,0/1This would make a single block with weight 3 per column with size 2/1x1/1. This makes a genuine "1A" Gallager matrix. This syntax is *not* available at the moment! If it were available, then the precise construction 2A of MacKay/Neal would be

lambda 3/2 1x2 I 1/2 at 0/1,0/1 1x1 T t=3 1/1x1/1 at 1/2,0/1

History: I made a load of specific C programs called code4 and code5 and some others that modified alists and made new alists from them. I then wrote specific perl programs permalist*.p which made some of the constructions here implemented by GH.p. I used those with the simulator called GH. The best of those was permarand.p (which stops using prime numbers as generators, which was a bad idea!)

David MacKay <mackay@mrao.cam.ac.uk> Last modified: Thu Sep 21 18:33:43 2000