readme

根据LDPC码中码子的构造方法中的PEG算法

From: "Xiao-Yu Hu" <[e-mail]>
 Source C++ codes for approximating the MinDist problem of LDPC codes

I feel very happy that I am now able to send you the source C++ codes
for approximating the MinDist problem of LDPC codes.

The source files have been tested through the C++ compiler xlC on IBM
RS/6000 running AIX operating system. On other compilers and platforms,
minor changes may be needed on Makefile and/or source C++ files.

Here are some examples for the commands:
1) Main -code Reg252x504.dat -outFileCW Reg252x504.CW -thresh 25
   Remarks: The program computes the minum distance (an upper bound) of
the code Reg252x504.dat using single- and two-position Bit-Reversing,
and stores valid codewords found of weight less than 25 to the file
Reg252x504.CW.
2) Main -code Reg252x504.dat -outFileCW Reg252x504.CW -thresh 25
-switch 0
   Remarks: Berrou's error impulse + single-position bit-reversing +
two-position bit reversing

The following is the usage reminder issued by the program if one gives
wrong input argument.
--------------------------------------------------------------------
                           Usage Reminder:
                              Main -code codeName  -outFileCW outNameCW
-thresh estLowWeight                Option: -switch opt  -speedup inum
                                       opt==0 --- Berrou's impulse
error followed by                                       single-position
bit-reversing followed by                                two-position
bit reversing
      opt==1 --- single- and two-position bit reversing (DEFAULT)
      inum==1 --- normal speed at each iteration (DEFAULT)
                          2 --- faster, but low-weight codewords may be
missed                     3 --- fastest, but low-weight codewords may
be missed

This free software is to compute approximately the minimum distance and
the corresponding multiplicity of iteratively decodeable linear codes,
for instance LDPC codes. Recall that the general MinDist problem of
linear codes is NP-hard, the software thus produces an estimate and an
upper bound of the minimum distance based on true (low-weight)
codewords  found by a fine-tuned local search. The algorithm proved to
be powerful in the sense that it found 2 codewords of weight 20 for
MacKay (3,6)-regular (504, 252) code, 1 codeword of weight 34 for
MacKay (3, 6)-regular (1008, 504) code, 66 codewords of weight 40 for
the Margulis (p=11) code, 2184 codewords of weight 14 for the
Ramanujan-Margulis (13, 5) code, and 204 codewords of weight 24 for the
Ramanujan-Margulis (17, 5) code.

 The main progamm Main reads in an LDPC code from 'codeName'. The
format  is as follows: The first line contains the number block length,
N. The second line defines the number of parity-checks, M. The third
line defines the number of columns of the compressed parity-check. The
following M lines are then the compressed parity-check matrix. Each of
the M rows contains the indices (1 ... N) of 1's in the compressed row
of parity-check matrix. If not all column entries are used, the column
is filled up with 0's.

One needs to supply the programm with an estimate of the minimum
distance of the code by specifying -thresh estLowWeight. The specific
value of estLowWeight does not affect the ability of the algorithm to
capture low-weight codewords, but it prescribes the largest weight of
which codewords (found) are writen into outNameCW --- for a codewith a
minimum distance of 20, no one is interested in the codeword of weight
over 50. Therefore, estLowWeight shall be slightly larger the true
minimum distance. If estLowWeight is smaller than the lowest weight
 found by the programm, no codewords are written into the output
codeword file, but the program will tell you the lowest weight ever
found. Note that the output codeword file 'outNameCW' is updated from
time to time, one can terminate the program at any time when he think
the lowest weight is satisfactory.

 A log file called 'outNameCW.spect' records the lower-part spectrum of
the code based on the codewords found so far. The posotion denotes the 
distance, and the number the multiplicity.
---------------------------------------------------------------------

Concerning the LDPC codes I have sent to you, the program finds 2
codewords of weight 20 for Reg252x504.dat, 1 codeword of weight 48 for 
Reg504x1008.dat, 1 codeword of weight 13 for irReg252x504.dat, 1
codeword of weight 13 for irReg504x1008.dat, 1 codeword of weight 15
for irUppTriang518x1024.dat, and 2 codewords of weight 17 for
irUppTriang1030x2048.dat