- 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" 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:


 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
 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 <>
Last modified: Thu Sep 21 18:33:43 2000