Analysis and design of low-density parity-check convolutional codes

Abstract

Low-Density Parity-Check Faltungscodes (LDPC-CCs) koennen als konventionelle Faltungscodes mit hohem Gedaechtnis angesehen werden.<br />Durch ``Pipeline´´-Decodierung werden (LDPC-CCs) einer praktischen Verwendung zugaenglich, sowohl bei kontinuierlicher als auch bei blockweiser Uebertragung von Rahmen beliebiger Groesse, ohne dass die Komplexitaet gegenueber den entsprechenden LDPC Blockcodes steigt.<br />Zeitinvariante und zeitvariante LDPC-CCs koennen durch eine ``polynomial-domain´´ Syndromformermatrix definiert werden, die direkt aus quasi-zyklischen Blockcodes oder durch ``unwrapping´´ von LDPC Blockcodes hergeleitet werden kann.<br />LDPC-CCs koennen durch den ``pipelined Sum Product Algorithm´´ (SPA) decodiert werden, der aber Konvergenzprobleme haben kann, wegen der Zyklen im Tanner-Graphen des Codes. Unter Ausnutzung der Beziehungen zwischen der ``zeitbasierten´´ und der ``polynomial-domain´´ Syndromformermatrix wird eine Algorithmus vorgeschlagen, mit dem die Zyklenstruktur fuer zeitinvariante und zeitvariante LDPC-CCs ermittelt werden kann. Durch spezielle Struktureigenschaften der Gewichtsmatrix der ``polynomial-domain´´ Syndromformermatrix sind einige Zyklen unvermeidbar, unabhaengig davon, wie die monomialen Eintraege der Gewichtsmatrix gewaehlt werden. Es wird gezeigt, dass Eintraege mit hohem Gewicht einen nachteilig kleinen ``Girth´´ des Codegraphen verursachen, waehrend monomiale oder leere Eintraege einen grossen ``Girth´´ bewirken koennen.<br />Eine wichtige Eigenschaft jedes Kanalcodes ist sein Distanzspektrum, aber wegen des langen Gedaechtnisses der LDPC-CCs ist die Komplexitaet zu dessen Berechnung zu hoch, um praktisch durchfuehrbar zu sein.<br />Deshalb wird das Distanzspektrum geschaetzt, indem die ``polynomial-domain´´ Syndromformermatrix gesplittet wird, wobei die entstehenden Submatrizen ``Supercodes´´ beschreiben. Die lineare Abhaengigkeit zwischen Codeworten dieser Supercodes wird ausgenutzt zur Schaetzung einer Obergrenze der minimalen freien Distanz des urspruenglichen Codes.<br />Zur Anpassung an sich zeitlich aendernde Kanaleigenschaften wird eine Familie robuster ratenkompatibler (RC) punktierter LDPC-CCs hergeleitet, basierend auf einem zeitinvarianten LDPC-CC ``Muttercode´´, indem Codebits periodisch nicht uebertragen (punktiert) werden. Es wird gezeigt, dass die Laenge der Punktierungsperiode fuer hoch-ratige Codes ein wichtiger Designparameter ist, und dass die Vergroesserung der Punktierungsperiode die Leistungsfaehigkeit bei der Decodierung erhoehen kann; ausserdem kann der Bereich moeglicher kompatibler Coderaten vergroessert werden.<br />

Low-Density Parity-Check convolutional codes (LDPC-CCs) can be considered as conventional convolutional codes with large memory. Using pipeline decoding, it has been shown that they are suitable for practical implementation with continuous transmission as well as for block transmission in frames of arbitrary size without an increase in computational complexity compared to their block code counterparts.<br />Time-invariant or time-varying LDPC-CCs can be defined by polynomial-domain syndrome former matrices that can be derived from corresponding Quasi-Cyclic (QC) LDPC-BCs or ``unwrapping´´ LDPC-BCs.<br />LDPC-CCs can be efficiently decoded by a pipelined Sum Product Algorithm (SPA). It suffers, however, from convergence problems, due to cycles in the code's Tanner graph. According to the relationship of cycle structures between time- and polynomial-domain syndrome former matrices, we present a cycle counter algorithm for time-invariant and time-varying LDPC-CCs. Due specific structures in the weight matrix of a polynomial-domain syndrome former matrix, some cycles are unavoidable no matter what monomials are placed in the weight matrix. It is shown that large-weight entries lead to small girth, while monomial or empty entries may result in large girth.<br />An important characteristic of any code is its distance spectrum but for LDPC-CCs it is complicated to compute due to large code memory. An estimation of the distance spectrum of time-invariant LDPC-CCs is obtained by splitting the polynomial-domain syndrome former matrix into submatrices representing ``super codes´´ and then evaluating the linear dependence between codewords of the corresponding super codes. This estimation results in an upper bound on the minimum free distance of the original code.<br />To adapt to the changing conditions of time-varying channels, a family of robust rate-compatible (RC) punctured LDPC-CCs is derived from a time-invariant LDPC-CC mother code by periodically puncturing encoded bits. We show that the length of the puncturing period is an important parameter when designing high-rate punctured codes and, moreover, that extending the puncturing period can improve the decoding performance and extend the range of compatible rates.