The Low-Density Parity-Check (LDPC) codes, which were invented by Gallager back in 1960s, have attracted considerable attentions recently. Compared with other error correction codes, LDPC codes are well suited for wireless, optical, and magnetic recording systems due to their near- Shannon-limit error-correcting capacity, high intrinsic parallelism and high-throughput potentials. With these remarkable characteristics, LDPC codes have been adopted in several recent communication standards such as 802.11n (Wi-Fi), 802.16e (WiMax), 802.15.3c (WPAN), DVB-S2 and CMMB. This dissertation is devoted to exploring efficient VLSI architectures for high-performance LDPC decoders and LDPC-like detectors in sparse inter-symbol interference (ISI) channels. The performance of an LDPC decoder is mainly evaluated by area efficiency, error-correcting capability, throughput and rate flexibility. With this work we investigate tradeoffs between the four performance aspects and develop several decoder architectures to improve one or several performance aspects while maintaining acceptable values for other aspects. Firstly, we present a high-throughput decoder design for the Quasi-Cyclic (QC) LDPC codes. Two new techniques are proposed for the first time, including parallel layered decoding architecture (PLDA) and critical path splitting. Parallel layered decoding architecture enables parallel processing for all layers by establishing dedicated message passing paths among them. The decoder avoids crossbar-based large interconnect network. Critical path splitting technique is based on articulate adjustment of the starting point of each layer to maximize the time intervals between adjacent layers, such that the critical path delay can be split into pipeline stages. Furthermore, min-sum and loosely coupled algorithms are employed for area efficiency. As a case study, a rate-1/2 2304-bit irregular LDPC decoder is implemented using ASIC design in 90 nm CMOS process. The decoder can achieve an input throughput of 1.1 Gbps, that is, 3 or 4 times improvement over state-of-art LDPC decoders, while maintaining a comparable chip size of 2.9 mm^2. Secondly, we present a high-throughput decoder architecture for rate-compatible (RC) LDPC codes which supports arbitrary code rates between the rate of mother code and 1. While the original PLDA is lack of rate flexibility, the problem is solved gracefully by incorporating the puncturing scheme. Simulation results show that our selected puncturing scheme only introduces the BER performance degradation of less than 0.2dB, compared with the dedicated codes for different rates specified in the IEEE 802.16e (WiMax) standard. Subsequently, PLDA is employed for high throughput decoder design. As a case study, a RC- LDPC decoder based on the rate-1/2 WiMax LDPC code is implemented in CMOS 90 nm process. The decoder can achieve an input throughput of 975 Mbps and supports any rate between 1/2 and 1. Thirdly, we develop a low-complexity VLSI architecture and implementation for LDPC decoder used in China Multimedia Mobile Broadcasting (CMMB) systems. An area-efficient layered decoding architecture based on min-sum algorithm is incorporated in the design. A novel split-memory architecture is developed to efficiently handle the weight-2 submatrices that are rarely seen in conventional LDPC decoders. In addition, the check-node processing unit is highly optimized to minimize complexity and computing latency while facilitating a reconfigurable decoding core. Finally, we propose an LDPC-decoder-like channel detector for sparse ISI channels using belief propagation (BP). The BP-based detection computationally depends on the number of nonzero interferers only and are thus more suited for sparse ISI channels which are characterized by long delay but a small fraction of nonzero interferers. Layered decoding algorithm, which is popular in LDPC decoding, is also adopted in this paper. Simulation results show that the layered decoding doubles the convergence speed of the iterative belief propagation process. Exploring the special structure of the connections between the check nodes and the variable nodes on the factor graph, we propose an effective detector architecture for generic sparse ISI channels to facilitate the practical application of the proposed detection algorithm. The proposed architecture is also reconfigurable in order to switch flexible connections on the factor graph in the time-varying ISI channels.

Η διόρθωση λαθών με κώδικες LDPC είναι μεγάλου ενδιαφέροντος σε σημαντικές νέες τηλεπικοινωνιακές εφαρμογές, όπως δορυφορικό Digital Video Broadcast (DVB) DVB-S2, IEEE 802.3an (10GBASE-T) και IEEE 802.16 (WiMAX). Οι κώδικες LDPC ανήκουν στην κατηγορία των γραμμικών μπλοκ κωδικών. Πρόκειται για κώδικες ελέγχου και διόρθωσης σφαλμάτων μετάδοσης, με κυριότερο χαρακτηριστικό τους τον χαμηλής πυκνότητας πίνακα ελέγχου ισοτιμίας (Low Density Parity Check), από τον οποίο και πήραν το όνομά τους. Η αποκωδικοποίηση γίνεται μέσω μιας επαναληπτικής διαδικασίας ανταλλαγής πληροφορίας μεταξύ δύο τύπων επεξεργαστικών μονάδων. Η υλοποίηση σε υλικό των LDPC αποκωδικοποιητών αποτελεί ένα ραγδαία εξελισσόμενο πεδίο για τη σύγχρονη επιστημονική έρευνα. Σκοπός της παρούσας διπλωματικής εργασίας υπήρξε ο σχεδιασμός, η υλοποίηση και η βελτιστοποίηση αρχιτεκτονικών αποκωδικοποιητών VLSI για κώδικες LDPC. Έχουν αναπτυχθεί διάφοροι αλγόριθμοι αποκωδικοποίησης, οι οποίοι είναι επαναληπτικοί. Μελετήθηκαν αρχιτεκτονικές βασισμένες σε δύο αλγόριθμους, τον log Sum-Product και τον Min-Sum. Ο πρώτος είναι θεωρητικά βέλτιστος, αλλά ο Min-Sum είναι αρκετά απλούστερος και έχει μεγαλύτερο πρακτικό ενδιαφέρον στα πλαίσια μιας ρεαλιστικής εφαρμογής. Συγκεκριμένα, αναπτύχθηκαν δύο αλγόριθμοι αποκωδικοποίησης, οι οποίοι χρησιμοποιούν ως δομικά στοιχεία, τους δύο προαναφερθέντες αλγορίθμους και τη φιλοσοφία του layered decoding. Η μελέτη μας επικεντρώθηκε σε κώδικες, η δομή των πινάκων ελέγχου ισοτιμίας των οποίων, προσφέρεται για υλοποίηση. Για αυτό το λόγο, χρησιμοποιήσαμε κώδικες του προτύπου WiMax 802.16e. Η συνεισφορά της παρούσας εργασίας έγκειται στο σχεδιασμό και την υλοποίηση αποδοτικών αρχιτεκτονικών σε επίπεδο επιφάνειας και ταχύτητας αποκωδικοποίησης (Mbps), καθώς και η διερεύνηση του σχετικού σχεδιαστικού χώρου, χρησιμοποιώντας ως σχεδιαστικές παραμέτρους, τον αλγόριθμο αποκωδικοποίησης, τη χρονοδρομολόγηση των πράξεων, το βαθμό παραλληλίας της αρχιτεκτονικής, το βάθος του pipelining και την αριθμητική αναπαράσταση των δεδομένων. Επιπλέον, είναι σημαντικό να αναφέρουμε πως, στα πλαίσια της σχεδίασης του LDPC αποκωδικοποιητή και με τη βοήθεια του εργαλείου Matlab, αναπτύχθηκαν παραμετρικά scripts για την παραγωγή του VHDL κώδικα. Οι δύο βασικές παράμετροι που χρησιμοποιήθηκαν ήταν το πλήθος των επεξεργαστικών μονάδων και το μήκος λέξης των δεδομένων. Τα scripts αυτά αποτέλεσαν ένα πολύ χρήσιμο εργαλείο κατά τη διαδικασία ανάπτυξης και βελτιστοποίησης της αρχιτεκτονικής, δίνοντας μας τη δυνατότητα να παράγουμε με αυτοματοποιημένο και γρήγορο τρόπο τον VHDL κώδικα, για τις επιμέρους μονάδες του αποκωδικοποιητή. Η υλοποίηση ενός μοντέλου αποκωδικοποιητή σε υλικό, μας δίνει τη δυνατότητα να διεξάγουμε ταχύτατες εξομοιώσεις, σε σχέση με αντίστοιχες υλοποιήσεις σε λογισμικό (π.χ. σε Matlab περιβάλλον). Διαθέτουμε, έτσι, ένα ισχυρό εργαλείο για τη μελέτη της επίδοσης διαφόρων ρεαλιστικών υλοποιήσεων αποκωδικοποιητών. Κατά τη διάρκεια της υλοποίησης, αξιοποιήθηκε αναπτυξιακό σύστημα βασισμένο σε virtex-4 fpga. / LDPC (low-density parity-check) codes are widely applied for error correction, in the development of highly efficient modern digital communication systems, as satellite Digital Video Broadcast (DVB) DVB-S2, IEEE 802.3an (10GBASE-T) and IEEE 802.16 (WiMax). LDPC codes are linear block codes, characterized by a sparse parity-check matrix. They are error detection and correction codes. The most typical decoding procedure is the message passing algorithm that implements the iterative exchange of node-generated messages between two types of processing units, called check and variable nodes. Hardware implementation of an LDPC decoder is a fast growing field for contemporary scientific research. This work presents the results of the design, implementation and optimization of a VLSI decoder for LDPC codes. Several iterative decoding algorithms have been developed. At this work we present architectures based on the log Sum-Product (Log-SP) and Min-Sum algorithm. Log-SP is theoretically optimal; however Min-Sum is substantially simpler and reduces the hardware complexity. Two alternative decoding algorithms have been developed, that use these two algorithms for the check-node LLR update, and the philosophy of layered decoding for the exchange of messages. Our study focused on WiMax 801.16e LDPC codes, whose form, based on permuted identity matrices, is suitable for a hardware realization. The contribution of this work lays within the design and implementation of area and decoding throughput efficient architectures, as well a detailed investigation of design space, using decoding algorithm, message exchange scheduling, pipelining and quantization schemes as design parameters. Furthermore, important to mention is, -the development of parametric Matlab scripts, in order to achieve easy and automated structural VHDL code production. The two key parameters are the number of the processing units and the data length. A hardware realization of a LDPC decoder, gives us a simulation tool that is much faster than corresponding software implementations (for example, a matlab implementation). During the implementation procedure, development board based in virtex-4 fpga has been used.

The VLSI implementation complexity of a low density parity check (LDPC) decoder is largely influenced by the interconnect and the storage requirements. This dissertation presents the decoder architectures for regular and irregular LDPC codes that provide substantial gains over existing academic and commercial implementations. Several structured properties of LDPC codes and decoding algorithms are observed and are used to construct hardware implementation with reduced processing complexity. The proposed architectures utilize an on-the-fly computation paradigm which permits scheduling of the computations in a way that the memory requirements and re-computations are reduced. Using this paradigm, the run-time configurable and multi-rate VLSI architectures for the rate compatible array LDPC codes and irregular block LDPC codes are designed. Rate compatible array codes are considered for DSL applications. Irregular block LDPC codes are proposed for IEEE 802.16e, IEEE 802.11n, and IEEE 802.20. When compared with a recent implementation of an 802.11n LDPC decoder, the proposed decoder reduces the logic complexity by 6.45x and memory complexity by 2x for a given data throughput. When compared to the latest reported multi-rate decoders, this decoder design has an area efficiency of around 5.5x and energy efficiency of 2.6x for a given data throughput. The numbers are normalized for a 180nm CMOS process. Properly designed array codes have low error floors and meet the requirements of magnetic channel and other applications which need several Gbps of data throughput. A high throughput and fixed code architecture for array LDPC codes has been designed. No modification to the code is performed as this can result in high error floors. This parallel decoder architecture has no routing congestion and is scalable for longer block lengths. When compared to the latest fixed code parallel decoders in the literature, this design has an area efficiency of around 36x and an energy efficiency of 3x for a given data throughput. Again, the numbers are normalized for a 180nm CMOS process. In summary, the design and analysis details of the proposed architectures are described in this dissertation. The results from the extensive simulation and VHDL verification on FPGA and ASIC design platforms are also presented.