Creating a Parity Check Matrix

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.

Some LDPC software by David MacKay and others uses the alist format for parity check matrices. Two programs for converting between this format and the format for sparse parity check matrices used by this software are provided.

Methods for constructing LDPC codes

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:

1. Create a preliminary parity check matrix by one of the methods.
2. Add 1s to the parity check matrix in order to avoid rows that have no 1s in them, and hence are redundant, or which have only one 1 in them, in which case the corresponding codeword bits will always be zero. The places within such a row to add these 1s are selected randomly.
3. If the preliminary parity check matrix constructed in step (1) had an even number of 1s in each column, add further 1s to avoid the problem that this will cause the rows to add to zero, and hence at least one check will be redundant. Up to two 1s are added (since it is also undesirable for the sum of the rows to have only one 1 in it), at positions selected randomly from the entire matrix. However, the number of 1s to add in this step is reduced by the number already added in step (2). (Note that although redundant checks are not disastrous, they are better avoided; see the discussion of linear dependence in parity check matrices.)
4. If requested, try to eliminate situations where a pair of columns both have 1s in a particular pair of rows, which correspond to cycles of length four in the factor graph of the parity check matrix. When such a situation is detected, one of the 1s involved is moved randomly within its column. This continues until no such situations remain, or until 10 passes over all columns have failed to eliminate all such situations.

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. Note that despite the name, the columns do not have to have the same number of 1s - a distribution over several values for the number of 1s in a column can be specified instead. Such codes with different-weight columns are sometimes better than codes in which every column has the same weight.

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.

Converts a parity check matrix in alist format stored in the file named alist-file to the sparse matrix format used by this software, storing it in the file named pchk-file.

Converts a parity check matrix stored in the sparse matrix format used by this software, in the file named pchk-file, to the alist format, storing it in the file named alist-file.

Example: The parity check matrix for the Hamming code created by the example for make-pchk would print as follows:

print-pchk ham7.pchk

Parity check matrix in ham7.pchk (sparse format):

0: 0 3 4 5
1: 1 3 4 6
2: 2 4 5 6

print-pchk -d ham7.pchk

Parity check matrix in ham7.pchk (dense format):

 1 0 0 1 1 1 0
 0 1 0 1 1 0 1
 0 0 1 0 1 1 1

See the discussion above for more details on how these methods construct LDPC matrices.

Example 1: 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, using random seed 1. The matrix is then printed in sparse format using print-pchk.

make-ldpc ldpc.pchk 20 40 1 evenboth 3
print-pchk ldpc.pchk

Parity check matrix in ldpc.pchk (sparse format):

 0: 10 14 18 27 38 39
 1:  2  3  5 11 27 30
 2: 15 19 20 21 24 26
 3:  2  4 25 28 32 38
 4:  7  9 12 22 33 34
 5:  5  6 21 22 26 32
 6:  1  4 13 24 25 28
 7:  1 14 28 29 30 36
 8: 11 13 22 23 32 37
 9:  6  8 13 20 31 33
10:  0  3 24 29 31 38
11:  7 12 15 16 17 23
12:  3 16 29 34 35 39
13:  0  8 10 18 36 37
14:  6 11 18 20 35 39
15:  0  7 14 16 25 37
16:  2  4  9 19 30 31
17:  5  9 10 17 19 23
18:  8 15 17 21 26 27
19:  1 12 33 34 35 36

Example 2: The two make-ldpc commands below both create a 20 by 40 low density parity check matrix with 30% of columns with two 1s, 60% of columns with three 1s, and 10% of columns with seven 1s. The transpose of the parity check matrix is then printed in sparse format.

make-ldpc ldpc.pchk 20 40 1 evenboth 0.3x2/0.6x3/0.1x7 
make-ldpc ldpc.pchk 20 40 1 evenboth 3x2/6x3/1x7
print-pchk -t ldpc.pchk

Transpose of parity check matrix in ldpc.pchk (sparse format):

 0: 13 16
 1:  9 18
 2:  1 10
 3:  3 15
 4:  4 14
 5: 14 17
 6:  4  5
 7:  1  8
 8:  0  4
 9:  9 14
10:  5  8
11:  6 16
12:  2 12 19
13:  3 17 18
14:  2 16 17
15:  2 11 18
16: 12 13 19
17:  7 13 18
18:  2  5 11
19: 10 12 14
20:  1  8 16
21: 10 18 19
22:  3  6 17
23:  7 11 12
24:  1  2 19
25:  0  6  7
26:  5  8 15
27:  1  4  7
28:  6 13 19
29:  3  4 11
30:  3  8 17
31:  4  5  9
32:  0 10 15
33:  7 11 13
34:  8 12 19
35:  0  2 10
36:  0  5  9 11 15 17 18
37:  0  1  2  6  7 14 16
38:  0  1  3  9 12 13 15
39:  3  6  9 10 14 15 16