decoding.html

关于LDPC编/译码的方针平台。能随机产生信源和模拟高斯信道。

<P>By including likelihood ratios from all checks, a similar
calculation produces the current probability ratio for the bit to be 1
versus 0 based on all information that has propagated to the bit so
far.  This ratio can be thresholded at one to produce the current best
guess as to whether this bit is a 1 or a 0.

<P>The hope is that this algorithm will eventually converge to a state
where these bit probabilities give a near-optimal decoding.  This is
does not always occur, but the algorithm behaves well enough to
produce very good results at rates approaching (though not yet
reaching) the theoretical Shannon limit.


<P><A NAME="decode"><HR><B>decode</B>: Decode blocks of received data
into codewords.

<BLOCKQUOTE><PRE>
decode [ -t | -T ] <I>pchk-file received-file decoded-file</I> [ <I>bp-file</I> ] <I>channel method</I>
</PRE>
<BLOCKQUOTE>
where <TT><I>channel</I></TT> is one of:
<BLOCKQUOTE><PRE>
bsc <I>error-probability</I>

awgn <I>standard-deviation</I>

awln <I>width</I>
</PRE></BLOCKQUOTE>
and <TT><I>method</I></TT> is one of:
<BLOCKQUOTE><PRE>
enum-block <TT><I>gen-file</I></TT>

enum-bit <TT><I>gen-file</I></TT>

prprp <TT>[-]<I>max-iterations</I></TT>
</PRE></BLOCKQUOTE>
</BLOCKQUOTE>
</BLOCKQUOTE>

<P>Decodes the blocks in <TT><I>received-file</I></TT>, which are
assumed to be have been received through the specified channel.  The
results written to <TT><I>decoded-file</I></TT> are the specified
decoding method's guesses as to what bits were sent through the
channel, given what was received.  The probability of each bit being a
1, as judged by the decoding method being used, is written to
<TT><I>bp-file</I></TT>, if given.

<P>A newline is output at the end of each block written to
<TT><I>decoded-file</I></TT> and <TT><I>bp-file</I></TT>.  Newlines in
<TT><I>received-file</I></TT> are ignored.  A warning is displayed on
standard error if the number of bits in <TT><I>received-file</I></TT>
is not a multiple of the block length.

<P>A summary is displayed on standard error, giving the total number
of blocks decoded, the number of blocks that decoded to valid
codewords, the average number of iterations of the decoding algorithm
used, and the percent of bits that were changed from the values one
would guess for them based just on their individual likelihood ratios.

<P>If the <B>-t</B> option is given, a line of information regarding each block
decoded is written to standard output, preceded by a line of headers.
The information for each block is as follows:
<BLOCKQUOTE>
<TABLE>
<tr align="left" valign="top">
  <td> <B>block</B> </td> 
  <td>The number of the block, from zero</td></tr>
<tr align="left" valign="top">
  <td> <B>iterations</B> </td> 
  <td>The number of "iterations" used in decoding.  What exactly an iteration
      is depends on the decoding method used (see 
      <A HREF="decode-detail.html">here</A>).</td></tr>
<tr align="left" valign="top">
  <td> <B>valid</B> </td>
  <td>Has the value 1 if the decoding is a valid codeword, 0 if not.</td></tr>
<tr align="left" valign="top">
  <td> <B>changed</B> </td>
  <td>The number of bits in the decoding that differ from the bit that would
      be chosen based just on the likelihood ratio for that bit.  Bits whose
      likelihood ratios are exactly one contribute 0.5 to this count.</td></tr>
</TABLE>
</BLOCKQUOTE>
The file produced is is suitable for 
reading into the S-Plus or R statistics packages, with a command such as
<BLOCKQUOTE><PRE>
data <- read.table(<I>file</I>,header=T)
</PRE></BLOCKQUOTE>

<P>If instead the <B>-T</B> option is given, detailed information on
the process of decoding each block will be written to standard output.
For a description, see the <A HREF="decode-detail.html">documentation
on detailed decoding trace information</A>.

<P>The type of channel that is assumed is specified after the file
name arguments.  This may currently be either <TT>bsc</TT> (or
<TT>BSC</TT>) for the Binary Symmetric Channel, or <TT>awgn</TT> (or
<TT>AWGN</TT>) for the Additive White Gaussian Noise channel, or
<TT>awln</TT> (or <TT>AWLN</TT>) for the Additive White Logistic Noise
channel.  The channel type is followed by an argument specifying the
assumed characteristics of the channel, as follows:
<BLOCKQUOTE> 
<P>BSC: The probability that a bit will be flipped by noise - ie, the
        probability that the bit received is an error.

<P>AWGN: The standard deviation of the Gaussian noise added to the 
         encodings of the bits.

<P>AWLN: The width parameter of the logistic distribution for the noise 
         that is added to the encodings of the bits.
</BLOCKQUOTE>
See the description of <A HREF="channel.html">channel transmission</A>
for more about these channels.

<P>Following the channel specification is a specification of the
decoding method to use.  The <TT>enum-block</TT> and <TT>enum-bit</TT>
methods find the optimal decoding by exhaustive enumeration of
codewords derived from all possible source messages.  They differ in
that <TT>enum-block</TT> decodes to the most likely codeword, whereas
<TT>enum-bit</TT> decodes to the bits that are individually most
probable.  These methods require that a file containing a
representation of a generator matrix be given, to allow enumeration of
codewords.  If the parity check matrix has no redundant rows, any
valid generator matrix will give the same decoding (except perhaps if
there is a tie).  If redundant rows exist, the generator matrix should
specify the same set of message bits as the generator matrix that was
used for the actual encoding, since the redundancy will lead to some
codeword bits being fixed at zero (see <A HREF="dep-H.html">linear
dependence in parity check matrices</A>).

<P>The <TT>prprp</TT> decoding method decodes using <A
HREF="#prprp">probability propagation</A>.  The maximum number of
iterations of probability propagation to do is given following
<TT>prprp</TT>.  If a minus sign precedes this number, the maximum
number of iterations is always done.  If no minus sign is present, the
algorithm stops once the tentative decoding, based on bit-by-bit
probabilities, is a valid codeword.  Note that continuing to the
maximum number of iterations will usually result in
at least slightly different bit probabilities (written to
<TT><I>bp-file</I></TT> if specified), and could conceivably change 
the decoding compared to stopping at the first valid codeword, or
result in a failure to decode to a valid codeword even though one was 
found earlier.


<P><A NAME="extract"><HR><B>extract</B>: Extract the message bits from a block.

<BLOCKQUOTE><PRE>
extract <I>gen-file decoded-file extracted-file</I>
</PRE></BLOCKQUOTE>

<P>Given a file of codewords in <TT><I>decoded-file</I></TT> (usually,
decoded blocks output by <A HREF="#decode"><TT>decode</TT></A>), and a
generator matrix from <TT><I>gen-file</I></TT> (needed only to
determine where the message bits are located in a codeword), this
program writes the message bits extracted from these codewords to the
file <TT><I>extracted-file</I></TT>.

<P>A newline is output at the end of each block written to
<TT><I>extracted-file</I></TT>.  Newlines in
<TT><I>decoded-file</I></TT> are ignored.  A warning is displayed on
standard error if the number of bits in <TT><I>decoded-file</I></TT>
is not a multiple of the block length.

<HR>

<A HREF="index.html">Back to index for LDPC software</A>

</BODY></HTML>