📄 pchk.html
字号:
<HTML><HEAD><TITLE> Creating a Parity Check Matrix </TITLE></HEAD><BODY><H1> Creating a Parity Check Matrix </H1><P>This software deals only with linear block codes for binary (ie,modulo-2, GF(2)) vectors. The set of valid codewords for a linearcode can be specified by giving a <I>parity check matrix</I>,<B>H</B>, with <I>M</I> rows and <I>N</I> columns. The validcodewords are the vectors, <B>x</B>, of length <I>N</I>, for which<B>Hx</B>=<B>0</B>, where all arithmetic is done modulo-2. Each rowof <B>H</B> represents a parity check on a subset of the bits in<B>x</B>; all these parity checks must be satisfied for <B>x</B> to bea codeword. Note that the parity check matrix for a given code (ie,for a given set of valid codewords) is not unique, even aftereliminating rows of <B>H</B> that are redundant because they arelinear combinations of other rows.<P>This software stores parity check matrices in files in a sparseformat. These parity-check files are <I>not</I> human-readable(except by using the <A HREF="#print-pchk"><TT>print-pchk</TT></A>program). However, they <I>are</I> readable on a machine with adifferent architecture than they were written on.<P>Some LDPC software by David MacKay and others uses the <A HREF="http://www.inference.phy.cam.ac.uk/mackay/codes/alist.html">alistformat</A> for parity check matrices. Two programs for convertingbetween this format and the format for sparse parity check matricesused by this software are provided.<A NAME="ldpc"><H2>Methods for constructing LDPC codes</H2></A><P>This software is primarily intended for experimentation with LowDensity Parity Check (LDPC) codes. These codes can be constructed byvarious methods, which generally involve some random selection ofwhere to put 1s in a parity check matrix. Any such method forconstructing LDPC codes will have the property that it produces paritycheck matrices in which the number of 1s in a column is approximatelythe same (perhaps on average) for any size parity check matrix. For agiven code rate, these matrices therefore become increasingly sparseas the length of a codeword, and hence the number of parity checks,increases.<P>Many methods for constructing LDPC matrices are described in the<A HREF="refs.html">references</A>. Two simple methods are currentlyimplemented by this software, both of which operate according to thefollowing scheme:<OL><LI> Create a preliminary parity check matrix by one of the methods.<LI> 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.<LI> 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 <A HREF="dep-H.html">linear dependence in parity check matrices</A>.)<LI> 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.</OL><P>The <I>evencol</I> method is the simplest way of performing step(1) of the above procedure. For each column of the parity checkmatrix, independently, it places a specified number of 1s in positionsselected uniformly at random, with the only constraint being thatthese 1s be in distinct rows. Note that despite the name, the columnsdo not have to have the same number of 1s - a distribution overseveral values for the number of 1s in a column can be specifiedinstead. Such codes with different-weight columns are sometimesbetter than codes in which every column has the same weight.<P>The <I>evenboth</I> method also puts a specified number of 1s ineach column, but it tries as well to keep the numbers of 1s in therows approximately the same. Initially, it creates indicators for allthe 1s that will be required, and assigns these 1s to rows as evenlyas it can, favouring earlier rows if an exactly even split is notpossible. It then assigns 1s to successive columns by selectingrandomly, without replacement, from this initial supply of 1s, subjectonly to the constraint that the 1s assigned to a column must be indistinct rows. If at some point it is impossible to put the requirednumber of 1s in a column by picking from the 1s remaining, a 1 is setin that column without reference to other columns, creating a possibleunevenness. <P>Note that regardless of how evenly 1s are distributed in thepreliminary 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, andstep (4), if done, can make the numbers of 1s in rows be uneven.<P><A NAME="make-pchk"><HR><B>make-pchk</B>: Make a parity check matrix by explicit specification.<BLOCKQUOTE><PRE>make-pchk <I>pchk-file n-checks n-bits row</I>:<I>col ...</I></PRE></BLOCKQUOTE><P>Creates a file named <TT><I>pchk-file</I></TT> inwhich it stores a parity check matrix with <TT><I>n-checks</I></TT>rows and <TT><I>n-bits</I></TT> columns. This parity check matrixconsists of all 0s except for 1s at the <I>row</I>:<I>col</I>positions listed. Rows and columns are numbered starting at zero.This program is intended primarily for testing and demonstration purposes. <P><B>Example:</B> The well-known Hamming code with codewords oflength <I>N</I>=7 and with <I>M</I>=3 parity checks can be can becreated as follows:<UL><PRE><LI>make-pchk ham7.pchk 3 7 0:0 0:3 0:4 0:5 1:1 1:3 1:4 1:6 2:2 2:4 2:5 2:6</PRE></UL><P><A NAME="alist-to-pchk"><HR><B>alist-to-pchk</B>: Convert a paritycheck matrix from alist format to the sparse matrix format used bythis software.<BLOCKQUOTE><PRE>alist-to-pchk <I>alist-file pchk-file</I></PRE></BLOCKQUOTE><P>Converts a parity check matrix in <A HREF="http://www.inference.phy.cam.ac.uk/mackay/codes/alist.html">alistformat</A> stored in the file named <TT><I>alist-file</I></TT> to the sparse matrix format used by this software, storing it in thefile named <TT><I>pchk-file</I></TT>.<P><A NAME="pchk-to-alist"><HR><B>pchk-to-alist</B>: Convert a paritycheck matrix to alist format.<BLOCKQUOTE><PRE>pchk-to-alist <I>pchk-file alist-file</I></PRE></BLOCKQUOTE><P>Converts a parity check matrix stored in the sparse matrix formatused by this software, in the file named <TT><I>pchk-file</I></TT>, tothe <AHREF="http://www.inference.phy.cam.ac.uk/mackay/codes/alist.html">alistformat</A>, storing it in the file named <TT><I>alist-file</I></TT>.<P><A NAME="print-pchk"><HR><B>print-pchk</B>: Print a parity check matrix.<BLOCKQUOTE><PRE>print-pchk [ -d ] [ -t ] <I>pchk-file</I></PRE></BLOCKQUOTE><P>Prints a human-readable representation of the parity check matrix storedin <TT><I>pchk-file</I></TT>.The <B>-d</B> option causes the matrix to be printed in a denseformat, even though parity check matrices are always stored in thefile in a sparse format. If the <B>-t</B> option is present, what isprinted is the transpose of the parity check matrix.<P>The sparse display format consists of one line for every row of thematrix, consisting of the row number, a colon, and the column numbersat which 1s are located (possibly none). Row and columns numbersstart at zero. No attempt is made to wrap long lines.<P>The dense display is the obvious array of 0s and 1s. Long linesare not wrapped.<P><B>Example</B>: The parity check matrix for the Hamming code created by the example for <A HREF="#make-pchk"><TT>make-pchk</TT></A> would print as follows:<UL><PRE><LI>print-pchk ham7.pchkParity check matrix in ham7.pchk (sparse format):0: 0 3 4 51: 1 3 4 62: 2 4 5 6<LI>print-pchk -d ham7.pchkParity 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</PRE></UL><P><A NAME="make-ldpc"><HR><B>make-ldpc</B>: Make a low density paritycheck matrix, by random generation.<BLOCKQUOTE><PRE>make-ldpc <I>pchk-file n-checks n-bits seed method</I></PRE><BLOCKQUOTE>where <TT><I>method</I></TT> is one of the following:<BLOCKQUOTE><PRE>evencol <I>checks-per-col</I> [ no4cycle ]evencol <I>checks-distribution</I> [ no4cycle ]evenboth <I>checks-per-col</I> [ no4cycle ]evenboth <I>checks-distribution</I> [ no4cycle ]</PRE></BLOCKQUOTE></BLOCKQUOTE></BLOCKQUOTE><P>Creates a Low Density Parity Check matrix with<TT><I>n-checks</I></TT> rows and <TT><I>n-bits</I></TT> columns. Theparity check matrix will be generated pseudo-randomly by the indicatedmethod, using a pseudo-random number stream determined by <TT><I>seed</I></TT>.The actual random number seed used is 10 times <TT><I>seed</I></TT> plus 1,so as to avoid using the same stream as any of the other programs.<P>Two methods are currently available for creating the LDPC matrix,specified by <TT>evencol</TT> or <TT>evenboth</TT>. Both methodsproduce a matrix in which the number of 1s in each column isapproximately <TT><I>checks-per-col</I></TT>, or varies from columnto column according the the <TT><I>checks-distribution</I></TT>. The <TT>evenboth</TT> method also tries to make the number of checks per row beapproximately uniform; if this is not achieved, a message saying thathow many bits were placed unevenly is displayed on standard error.<P>For both methods, the <TT>no4cycle</TT> option will cause cycles oflength four in the factor graph representation of the code to beeliminated (if possible). A message is displayed on standard error ifthis is not achieved.<P>A <TT><I>checks-distribution</I></TT> has the form<BLOCKQUOTE><PRE><I>prop</I>x<I>count</I>/<I>prop</I>x<I>count</I>/...</PRE></BLOCKQUOTE>Here, <TT><I>prop</I></TT> is a proportion of columns that have the associated <TT><I>count</I></TT>. The proportions need not sum to one,since they will be automatically normalized. For example, <TT>0.3x4/0.2x5</TT>specifies that 60% of the columns will contain four 1s and 40% will contain five 1s.<P>See the <A HREF="#ldpc">discussion above</A> for more detailson how these methods construct LDPC matrices.<P><B>Example 1:</B> The <TT>make-ldpc</TT> 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 formatusing <A HREF="#print-pchk">print-pchk</A>.<UL><PRE><LI>make-ldpc ldpc.pchk 20 40 1 evenboth 3<LI>print-pchk ldpc.pchkParity 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 3310: 0 3 24 29 31 3811: 7 12 15 16 17 2312: 3 16 29 34 35 3913: 0 8 10 18 36 3714: 6 11 18 20 35 3915: 0 7 14 16 25 3716: 2 4 9 19 30 3117: 5 9 10 17 19 2318: 8 15 17 21 26 2719: 1 12 33 34 35 36</PRE></UL><P><B>Example 2:</B> The two <TT>make-ldpc</TT> commandsbelow 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% ofcolumns with seven 1s. The transpose of the parity check matrixis then printed in sparse format.<UL><PRE><LI>make-ldpc ldpc.pchk 20 40 1 evenboth 0.3x2/0.6x3/0.1x7 <LI>make-ldpc ldpc.pchk 20 40 1 evenboth 3x2/6x3/1x7<LI>print-pchk -t ldpc.pchkTranspose 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 1410: 5 811: 6 1612: 2 12 1913: 3 17 1814: 2 16 1715: 2 11 1816: 12 13 1917: 7 13 1818: 2 5 1119: 10 12 1420: 1 8 1621: 10 18 1922: 3 6 1723: 7 11 1224: 1 2 1925: 0 6 726: 5 8 1527: 1 4 728: 6 13 1929: 3 4 1130: 3 8 1731: 4 5 932: 0 10 1533: 7 11 1334: 8 12 1935: 0 2 1036: 0 5 9 11 15 17 1837: 0 1 2 6 7 14 1638: 0 1 3 9 12 13 1539: 3 6 9 10 14 15 16</PRE></UL><HR><A HREF="index.html">Back to index for LDPC software</A></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -