http://wol.ra.phy.cam.ac.uk/mackay/gallager/GH.html

GH.p

- grammar and perl program for making parity check matrices of Gallager codes and related codes

| Source code is in ~mackay/bin/GH.p. | "spec" files for GHG.p |

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.file
```
This 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 P
```
The 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/1
```
Produces 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/1
```
This 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>