<P>By including likelihood ratios from all checks, a similarcalculation produces the current probability ratio for the bit to be 1versus 0 based on all information that has propagated to the bit sofar.  This ratio can be thresholded at one to produce the current bestguess as to whether this bit is a 1 or a 0.<P>The hope is that this algorithm will eventually converge to a statewhere these bit probabilities give a near-optimal decoding.  This isdoes not always occur, but the algorithm behaves well enough toproduce very good results at rates approaching (though not yetreaching) the theoretical Shannon limit.<P><A NAME="decode"><HR><B>decode</B>: Decode blocks of received datainto 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 areassumed to be have been received through the specified channel.  Theresults written to <TT><I>decoded-file</I></TT> are the specifieddecoding method's guesses as to what bits were sent through thechannel, given what was received.  The probability of each bit being a1, 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 onstandard 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 numberof blocks decoded, the number of blocks that decoded to validcodewords, the average number of iterations of the decoding algorithmused, and the percent of bits that were changed from the values onewould 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 blockdecoded 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 onthe process of decoding each block will be written to standard output.For a description, see the <A HREF="decode-detail.html">documentationon detailed decoding trace information</A>.<P>The type of channel that is assumed is specified after the filename 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 Noisechannel.  The channel type is followed by an argument specifying theassumed 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 thedecoding method to use.  The <TT>enum-block</TT> and <TT>enum-bit</TT>methods find the optimal decoding by exhaustive enumeration ofcodewords derived from all possible source messages.  They differ inthat <TT>enum-block</TT> decodes to the most likely codeword, whereas<TT>enum-bit</TT> decodes to the bits that are individually mostprobable.  These methods require that a file containing arepresentation of a generator matrix be given, to allow enumeration ofcodewords.  If the parity check matrix has no redundant rows, anyvalid generator matrix will give the same decoding (except perhaps ifthere is a tie).  If redundant rows exist, the generator matrix shouldspecify the same set of message bits as the generator matrix that wasused for the actual encoding, since the redundancy will lead to somecodeword bits being fixed at zero (see <A HREF="dep-H.html">lineardependence in parity check matrices</A>).<P>The <TT>prprp</TT> decoding method decodes using <AHREF="#prprp">probability propagation</A>.  The maximum number ofiterations of probability propagation to do is given following<TT>prprp</TT>.  If a minus sign precedes this number, the maximumnumber of iterations is always done.  If no minus sign is present, thealgorithm stops once the tentative decoding, based on bit-by-bitprobabilities, is a valid codeword.  Note that continuing to themaximum number of iterations will usually result inat 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, orresult 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 agenerator matrix from <TT><I>gen-file</I></TT> (needed only todetermine where the message bits are located in a codeword), thisprogram writes the message bits extracted from these codewords to thefile <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 onstandard 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>