This software deals only with linear block codes for binary (ie, modulo-2, GF(2)) vectors. The set of valid codewords for a linear code can be specified by giving a parity check matrix, H, with M rows and N columns. The valid codewords are the vectors, x, of length N, for which Hx=0, where all arithmetic is done modulo-2. Each row of H represents a parity check on a subset of the bits in x; all these parity checks must be satisfied for x to be a codeword. Note that the parity check matrix for a given code (ie, for a given set of valid codewords) is not unique, even after eliminating rows of H that are redundant because they are linear combinations of other rows.
This software stores parity check matrices in files in a sparse format. These parity-check files are not human-readable (except by using the print-pchk program). However, they are readable on a machine with a different architecture than they were written on.
This software is primarily intended for experimentation with Low Density Parity Check (LDPC) codes. These codes can be constructed by various methods, which generally involve some random selection of where to put 1s in a parity check matrix. Any such method for constructing LDPC codes will have the property that it produces parity check matrices in which the number of 1s in a column is approximately the same (perhaps on average) for any size parity check matrix. For a given code rate, these matrices therefore become increasingly sparse as the length of a codeword, and hence the number of parity checks, increases.
Many methods for constructing LDPC matrices are described in the references. Two simple methods are currently implemented by this software, both of which operate according to the following scheme:
The evencol method is the simplest way of performing step (1) of the above procedure. For each column of the parity check matrix, independently, it places a specified number of 1s in positions selected uniformly at random, with the only constraint being that these 1s be in distinct rows.
The evenboth method also puts a specified number of 1s in each column, but it tries as well to keep the numbers of 1s in the rows approximately the same. Initially, it creates indicators for all the 1s that will be required, and assigns these 1s to rows as evenly as it can, favouring earlier rows if an exactly even split is not possible. It then assigns 1s to successive columns by selecting randomly, without replacement, from this initial supply of 1s, subject only to the constraint that the 1s assigned to a column must be in distinct rows. If at some point it is impossible to put the required number of 1s in a column by picking from the 1s remaining, a 1 is set in that column without reference to other columns, creating a possible unevenness.
Note that regardless of how evenly 1s are distributed in the preliminary parity check matrix created in step (1), steps (2) and (3) can make the numbers of 1s in the both rows and columns be uneven, and step (4), if done, can make the numbers of 1s in rows be uneven.
make-pchk pchk-file n-checks n-bits row:col ...
Creates a file named pchk-file in which it stores a parity check matrix with n-checks rows and n-bits columns. This parity check matrix consists of all 0s except for 1s at the row:col positions listed. Rows and columns are numbered starting at zero. This program is intended primarily for testing and demonstration purposes.
Example: The well-known Hamming code with codewords of length N=7 and with M=3 parity checks can be can be created as follows:
print-pchk [ -d ] pchk-file
Prints a human-readable representation of the parity check matrix stored in pchk-file. The -d option causes the matrix to be printed in a dense format, even though parity check matrices are always stored in the file in a sparse format.
The sparse display format consists of one line for every row of the matrix, consisting of the row number, a colon, and the column numbers at which 1s are located (possibly none). Row and columns numbers start at zero. No attempt is made to wrap long lines.
The dense display is the obvious array of 0s and 1s. Long lines are not wrapped.
Example: The parity check matrix for the Hamming code created by the example for make-pchk would print as follows:
make-ldpc pchk-file n-checks n-bits seed methodwhere method is one of the following:evencol checks-per-col [ no4cycle ] evenboth checks-per-col [ no4cycle ]
Creates a Low Density Parity Check matrix with n-checks rows and n-bits columns. The parity check matrix will be generated pseudo-randomly by the indicated method, using a pseudo-random number stream determined by seed. The actual random number seed used is 10 times seed plus 1, so as to avoid using the same stream as any of the other programs.
Two methods are currently available for creating the LDPC matrix, specified by evencol or evenboth. Both methods produce a matrix in which the number of 1s in each column is approximately checks-per-col. The evenboth method also tries to make the number of checks per row be approximately uniform; if this is not achieved, a message saying that how many bits were placed unevenly is displayed on standard error.
For both methods, the no4cycle option will cause cycles of length four in the factor graph representation of the code to be eliminated (if possible). A message is displayed on standard error if this is not achieved.
See the discussion above for more details on how these methods construct LDPC matrices.
Example: The make-ldpc command below creates a 20 by 40 low density parity check matrix with three 1s per column and six 1s per row. The matrix is then printed in sparse format using print-pchk.