📄 ldpc.htm
字号:
color: #24355D;
}
h3 {
color: #24355D;
}
/* Header style
----------------------------------------------- */
#header {
background: url(/-/includes/style/solitude/navy/bg_mast.gif) center center repeat-x;
}
/* Sidebar style
----------------------------------------------- */
#sidebar h3, #sidebar-alternate h3 {
color: #24355D;
}
/* Tweaks for Three-column layout
----------------------------------------------- */
#sidebar-alternate .alternate-content {
background: url(/-/includes/style/solitude/navy/bg_pattern.gif);
}
/** END CUSTOM SKIN **/
</style>
<!-- Hack to avoid flash of unstyled content in IE -->
<script> </script>
</head><body id="onecolumn">
<div id="container">
<div class="wrapper">
<div id="header">
<div class="wrapper">
<h1 id="page-title"><div id="g_title">LDPC Code</div></h1>
<div style="clear: both;"></div>
<p class="description"></p><div id="g_description"><p><font size="4" face="georgia">Using MATLAB</font></p></div>
<div style="clear: both;"></div>
</div>
</div>
<!-- /editable --><!-- /wrapper --><!-- /header -->
<div id="main-content">
<div class="wrapper">
<div class="content-item"><div id="g_body"><p></p>
<p><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000" face="verdana"><font size="2">This
LDPC software is intended as an introduction to LDPC codes computer
based simulation. The pseudo-random irregular low density
parity check matrix is based on Radford M. Neal鈥檚 programs collection,
which can be found in [1]. <font face="verdana">While Neal鈥檚
collection is well documented, in my opinion, C source
codes are still overwhelming, especially if you are not knowledgeable
in C language. My software is written for MATLAB, which is more
readable than C. You may also want to refer to another MATLAB based
LDPC source codes in [2], which has different flavor of code-writing
style (in fact Arun has error in his log-likelihood decoder). </font></font></font></span></p>
<p><font size="2" face="georgia"><strong></strong></font> </p>
<p><font size="2" face="georgia"><strong>Creating LDPC matrix</strong></font></p>
<p><font size="2" face="verdana">Steps for creating LDPC matrix (from Neal's website):</font></p>
<ul>
<li><font size="2" face="verdana">Select one of the method for creating sparse parity check matrix: (1) Evencol, or (2) Evenboth.</font>
</li><li><font size="2" face="verdana">Add 1s to rows that have no 1s or only have one 1 in them.</font>
</li><li><font size="2">If desired, try to avoid having cycle of lenght-four, where pair of column, both have 1s in particular rows</font></li></ul>
<p><font size="2">Evencol randomly distribute the same amount of 1s
between columns, evenboth is similar to evencol, but also try to make
rows having the same number of 1s.</font></p>
<p><font size="2">Function <font face="courier new,monospace"><strong>makeLdpc.m</strong></font> accepts 5 parameters:</font></p>
<ul>
<li><font size="2">M: Number of row </font>
</li><li><font size="2">N: Number of column</font>
</li><li><font size="2">method: Method for distributing 1s, 0 = Evencol, 1 = Evenboth</font>
</li><li><font size="2">noCyle: Eliminate length-four cycle</font>
</li><li><font size="2">onePerCol: Number of 1s per column.</font></li></ul>
<p><font size="2">The output is M x N matrix parity check matrix <strong>H</strong>. This function can only create R = 1/2 LDPC matrix.</font></p>
<p><font size="2" face="georgia"><strong></strong></font> </p>
<p><font size="2" face="georgia"><strong>Generating parity check bits</strong></font></p>
<p><font size="2" face="verdana">Parity check bits is computed using sparse LU decomposition, utilizing sparse matrix properties of <strong>H</strong>. Let <strong>H</strong> = [<strong>A</strong>|<strong>B</strong>]. We need to decompose <strong>A</strong> become <strong>LU</strong>, where <strong>L</strong> is lower triangular and <strong>U</strong> is upper triangular. In order the reduction to work, <strong>A</strong> must be non-singular, hence <strong>A</strong> must be reordered to give 1s on the diagonal. Steps for reordering <strong>A</strong> are (simplification from Neal's website):</font></p>
<ul>
<li><font size="2">Set <strong>L</strong> and <strong>U</strong> to all zeros.</font>
</li><li><font size="2">Set <strong>F</strong> to <strong>H</strong></font></li></ul>
<p><font size="2"> for i = 1 to M:</font></p>
<ul>
<li><font size="2">Find non-zero element of <strong>F</strong> that is in row i and column i, or in the latter column</font>
</li><li><font size="2">Rearrange columns of <strong>F</strong> and <strong>H</strong> from i onward to put this element in row i column i</font>
</li><li><font size="2">Copy column i of <strong>F</strong> up to row i to column i of <strong>U</strong></font>
</li><li><font size="2">Copy column i of <strong>F</strong> from row i to colunm i of <strong>L</strong></font>
</li><li><font size="2">Add row i of <strong>F</strong> to later rows that have value 1 in column i.</font></li></ul>
<p><font size="2"> end</font></p>
<ul>
<li><font size="2">Set <strong>B</strong> to the N - M column of the rearranged <strong>H</strong>.</font></li></ul>
<p><font size="2">There are 3 strategies to choose the next non-zero element for the diagonal:</font></p>
<ul>
<li><font size="2">First: choose the first found non-zero element from column i onward from column search.</font>
</li><li><font size="2">Mincol (minimal column): choose non-zero element from column i onward that has minimum number of non-zeros in its column.</font>
</li><li><font size="2">Minprod (minimal product): choose non-zero
element from column i onward that minimized the product of: (1) the
number of non-zeros in its row minus 1, and (2) the number of non-zeros
in its column minus 1.</font></li></ul>
<p><font size="2">Let <strong>z</strong> = <strong>Bs</strong>, where <strong>s</strong> is binary input vector. Solve <strong>L</strong>(<strong>Uc</strong>) = <strong>z</strong> for <strong>c</strong>, where <strong>c</strong> is parity check vector. Provided <strong>c</strong> is correct, let <strong>u</strong> = [<strong>c</strong>|<strong>s</strong>]. We should have <strong>Hu'</strong> = <strong>0</strong>, where <strong>H</strong> is rearranged original <strong>H</strong>.</font></p>
<p><font size="2">Function <font face="courier new,monospace"><strong>makeParityChk.m</strong></font> accepts 3 parameters:</font></p>
<ul>
<li><font size="2">dSource: Binary source</font>
</li><li><font size="2">H: Parity check matrix (from makeLdpc.m)</font>
</li><li><font size="2">strategy: Strategy for LU decomposition, 0 = First, 1 = Mincol, and 2 = Minprod,</font></li></ul>
<p><font size="2">and the output will be: </font></p>
<ul>
<li><font size="2">c: Parity check bits vector</font>
</li><li><font size="2">newH: Rearrange H, which should be used for encoding-decoding instead of original H.</font></li></ul>
<p><font size="2" face="georgia"><strong></strong></font> </p>
<p><font size="2" face="georgia"><strong>Decoding</strong></font></p>
<p><font size="2" face="verdana">LDPC code decoding is done using
iterative belief propagation or sum-product algorithm (SPA). Four
versions of SPA decoder (BPSK modulated under AWGN channel) are
presented:</font></p>
<ul>
<li><font size="2">Hard-decision (bit-flip) decoder (<font face="courier new,monospace"><strong>decodeBitFlip.m</strong></font>)</font></li></ul>
<p><font size="2">Decode 0/1 message, choose '1' if
the majority is 1, else '0'. The decoder could be used for
tutorial or introduction to message passing algorithms since it does
not employ complicated probability or log-likelihood
function. Expect worse performance compared to BPSK for
very low E<font size="1">b</font>/N<font size="1">0</font>.</font></p>
<ul>
<li><font size="2">Probability-domain SPA decoder (<font face="courier new,monospace"><strong>decodeProbDomain.m</strong></font>)</font></li></ul>
<p><font size="2">Based on Gallager's works [3]. </font></p>
<ul>
<li><font size="2">Log-domain SPA decoder (<font face="courier new,monospace"><strong>decodeLogDomain.m</strong></font>)</font></li></ul>
<p><font size="2">Similar to probability-domain SPA, but using
log-likelihood instead of probability function. The
advantage is operations can be done using additions
instead of multiplications, which computationaly less expensive.</font></p>
<ul>
<li><font size="2">Simplified log-domain SPA decoder (<font face="courier new,monospace"><strong>decodeLogDomainSimple.m</strong></font>)</font></li></ul>
<p><font size="2">A modified version of log-domain SPA, replaces Pi(x)
with minimum(x). For further simplification, log-likelihood
function can be replaced with incoming signal waveform directly
[5], hence simplified log-domain decoder does not need noise
variance information.</font></p>
<p><font size="2"></font> </p>
<p><font size="2">Both probability-domain and log-domain decoder need noise variance (N<font size="1">0</font>/2)
information for their input. Other decoder's paramaters include
received noisy signal, H matrix and number of iteration. </font></p>
<p> </p>
<p><font size="2" face="georgia"><strong>Putting it all together</strong></font></p>
<p><font size="2" face="verdana">Download all the files below and run <font face="courier new,monospace"><strong>ldpcBer.m</strong></font>, you'll be good! You might want to modify <font face="courier new,monospace">ldpcBer.m</font> first, running smaller size of LDPC matrix (i.e. smaller data frame) or chose your prefered decoder. </font></p><font face="georgia">
</font><p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font face="georgia"><font size="2" color="#000000"> </font></font></span></p>
<p>
</p><table class="MsoTableGrid" style="border: medium none ; border-collapse: collapse;" border="1" cellpadding="0" cellspacing="0">
<tbody>
<tr style="">
<td style="border: 1pt solid windowtext; padding: 0in 5.4pt; width: 239.4pt; background-color: transparent;" valign="top" width="319">
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font color="#000000"><font face="courier new,monospace"><font size="2"><a href="http://bsnugroho.googlepages.com/ldpcBER.m">ldpcBer.m</a></font></font></font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font size="2" color="#000000" face="courier new,monospace"> </font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font color="#000000"><font size="2" face="courier new,monospace"><a href="http://bsnugroho.googlepages.com/makeLdpc.m">makeLdpc.m</a></font></font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><font size="2"><span style="font-family: Verdana;"><font color="#000000" face="courier new,monospace"> </font></span><span style="font-family: Verdana;"><font color="#000000" face="courier new,monospace"> </font></span></font></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font color="#000000"><font face="courier new,monospace"><font size="2"><a href="http://bsnugroho.googlepages.com/makeParityChk.m">makeParityChk.m</a></font></font></font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><font size="2"><span style="font-family: Verdana;"><font color="#000000" face="courier new,monospace"> </font></span><span style="font-family: Verdana;"><font color="#000000" face="courier new,monospace"> </font></span></font></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font color="#000000"><font size="2" face="courier new,monospace"><a href="http://bsnugroho.googlepages.com/decodeBitFlip.m">decodeBitFlip.m</a></font></font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font size="2" color="#000000" face="courier new,monospace"> </font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font color="#000000"><font size="2" face="courier new,monospace"><a href="http://bsnugroho.googlepages.com/decodeProbDomain.m">decodeProbDomain.m</a></font></font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><span style="font-family: Verdana;"><font color="#000000"><font size="2" face="courier new,monospace"></font></font></span></span> </p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><span style="font-family: Verdana;"><font color="#000000"><font size="2" face="courier new,monospace"><a href="http://bsnugroho.googlepages.com/decodeLogDomain.m">decodeLogDomain.m</a></font></font></span></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><span style="font-family: Verdana;"><span style="font-family: Verdana;"><font color="#000000"><font size="2" face="courier new,monospace"></font></font></span></span></span> </p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><font size="2"><span style="font-family: Verdana;"><span style="font-family: Verdana;"><span style="font-family: Verdana;"><font color="#000000"><font face="courier new,monospace"><a href="http://bsnugroho.googlepages.com/decodeLogDomainSimple.m">decodeLogDomainSimple.m</a></font></font></span></span></span><span style="font-family: Verdana;"><font color="#000000"> </font></span></font></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font size="2" color="#000000"></font></span> </p></td>
<td style="border-color: windowtext windowtext windowtext rgb(236, 233, 216); border-top: 1pt solid windowtext; border-right: 1pt solid windowtext; border-bottom: 1pt solid windowtext; padding: 0in 5.4pt; width: 239.4pt; background-color: transparent;" valign="top" width="319">
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font color="#000000"><font face="verdana"><font size="2">Run LDPC codes BER simulation.</font></font></font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font size="2" color="#000000"> </font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font color="#000000"><font face="verdana"><font size="2">Create a R = 1/2 LDPC matrix.</font></font></font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font size="2" color="#000000" face="verdana"> </font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font color="#000000"><font face="verdana"><font size="2">Create parity check bits.</font></font></font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font size="2" color="#000000" face="verdana"> </font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font color="#000000"><font face="verdana"><font size="2">Hard-decision SPA decoder</font></font></font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font size="2" color="#000000" face="verdana"> </font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font color="#000000"><font face="verdana"><font size="2">Probability-domain SPA decoder.</font></font></font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font size="2" color="#000000"> </font></span></p><span style="font-family: Verdana;">
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font color="#000000"><font size="2" face="verdana">Log-domain SPA decoder.</font></font></span></p>
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font color="#000000"><font size="2" face="verdana"></font></font></span> </p><span style="font-family: Verdana;"><font color="#000000"><font face="verdana">
<p class="MsoNormal" style="margin: 0in 0in 0pt;"><span style="font-family: Verdana;"><font color="#000000"><font face="verdana"><font size="2">Simplified log-domain SPA decoder.</font></font></font></span></p></font></font></span></span></td></tr></tbody></table><font face="georgia"></font>
<p><font size="2" face="georgia"><strong></strong></font> </p>
<p><strong><font size="2" face="Georgia">Upcoming</font></strong></p>
<ul>
<li><font size="2" face="verdana">C-MEX version of the decoders.</font></li></ul>
<p><font size="2"></font> </p>
<p><font size="2" face="georgia"><strong>Upadate</strong></font></p>
<ul>
<li><font size="2" color="#ff0000">18 February 2008: Eb/N0 value correction</font> </li></ul>
<p> </p>
<p><font size="2" face="georgia"><strong>Reference </strong><font face="verdana">(Drop <a href="http://bsnugroho.googlepages.com/about">me</a> an email if you need any of these materials)</font></font></p>
<p><font face="verdana"><font size="2"><font face="verdana">[1] Radford M. Neal, <a href="http://www.cs.toronto.edu/%7Eradford/ftp/LDPC-2006-02-08/"><font color="#800080" face="verdana">http://www.cs.toronto.edu/~radford/ftp/LDPC-2006-02-08/</font></a></font></font></font></p>
<p><span style="font-size: 12pt; font-family: 'Times New Roman';"><font size="1"><font face="verdana"><font size="2" face="verdana">[2]</font> <font size="2" face="verdana">Arun Avudainayagam,</font> <span style="font-size: 12pt; font-family: 'Times New Roman';"><font size="2" color="#000000" face="verdana"><a href="http://arun-10.tripod.com/ldpc/ldpc.htm">http://arun-10.tripod.com/ldpc/ldpc.htm</a></font></span></font></font></span></p>
<p><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000" face="verdana"><span style="font-size: 12pt; font-family: 'Times New Roman';"><font size="2"><font face="verdana">[3]</font> <font face="Verdana">R. G. Gallager, Low-Density Parity-Check Codes. Cambridge, MA: M. I. T. Press, 1963. </font></font></span></font></span></p>
<p><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000" face="verdana"><span style="font-size: 12pt; font-family: 'Times New Roman';"></span></font></span><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000" face="verdana"><span style="font-size: 12pt; font-family: 'Times New Roman';"><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000" face="verdana"><span style="font-size: 12pt; font-family: 'Times New Roman';"><font size="2"><font face="verdana">[4]</font> <font face="Verdana">D.
MacKay, "Good error correcting codes based on very sparse
matrices," IEEE Trans. Information Theory, pp. 399-431, March 1999.</font></font></span></font></span></span></font></span></p>
<p><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000" face="verdana"><span style="font-size: 12pt; font-family: 'Times New Roman';"><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000" face="verdana"><span style="font-size: 12pt; font-family: 'Times New Roman';"></span></font></span><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000" face="verdana"><span style="font-size: 12pt; font-family: 'Times New Roman';"><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000" face="verdana"><span style="font-size: 12pt; font-family: 'Times New Roman';"><font size="2"><font face="verdana">[5]</font> <font face="verdana">W. E. Ryan, "An introduction to LDPC codes," August 2003.</font></font></span></font></span></span></font></span></span></font></span></p>
<p><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000" face="verdana"><span style="font-size: 12pt; font-family: 'Times New Roman';"><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000" face="verdana"><span style="font-size: 12pt; font-family: 'Times New Roman';"><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000" face="verdana"><span style="font-size: 12pt; font-family: 'Times New Roman';"></span></font></span></span></font></span></span></font></span><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000"><span style="font-size: 12pt; font-family: 'Times New Roman';"><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000"><span style="font-size: 12pt; font-family: 'Times New Roman';"><span style="font-size: 12pt; font-family: 'Times New Roman';"><font size="2" color="#000000" face="verdana"><span style="font-size: 12pt; font-family: 'Times New Roman';"><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000" face="verdana"><span style="font-size: 12pt; font-family: 'Times New Roman';"><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000" face="verdana"><span style="font-size: 12pt; font-family: 'Times New Roman';"><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000" face="verdana"><span style="font-size: 12pt; font-family: 'Times New Roman';"><font size="2"><font face="verdana">[6]</font> <font face="verdana">Bernhard M. J. Leiner, "LDPC codes - a Brief Tutorial," April 2005.</font></font></span></font></span></span></font></span></span></font></span></span></font></span></span></font></span></span></font></span></p><font color="#000000"><font color="#000000"><font size="2" color="#000000" face="verdana"></font></font></font><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000"><span style="font-size: 12pt; font-family: 'Times New Roman';"><span style="font-size: 12pt; font-family: 'Times New Roman';"><font color="#000000"><span style="font-size: 12pt; font-family: 'Times New Roman';"></span></font></span></span></font></span></div></div>
<div style="clear: both;"></div>
</div>
</div>
<!-- /wrapper --><!-- /main-content -->
<div id="footer"><div class="wrapper">
<hr>
<p></p><div id="g_footer"><p style="text-align: center;"><font size="2"> </font><a href="http://bsnugroho.googlepages.com/home"><font size="2" color="#0000ff">Home</font></a><font size="2"> | </font><a href="http://bsnugroho.googlepages.com/about"><font size="2" color="#0000ff">About</font></a></p></div>
<div style="clear: both;"></div>
</div></div>
<!-- /wrapper --><!-- /footer -->
</div>
</div>
<!-- /wrapper --><!-- /container -->
<div id="extraDiv1"><span></span></div><div id="extraDiv2"><span></span></div>
<div id="extraDiv3"><span></span></div><div id="extraDiv4"><span></span></div>
<div id="extraDiv5"><span></span></div><div id="extraDiv6"><span></span></div>
</body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -