A family of low-density lattice codes (LDLC) is studied based on Construction-A for lattices. The family of Construction-A codes is already known to contain a large capacity-achieving subset. Parallels are drawn between coset non-binary low-density parity-check (LDPC) codes and nested low-density Construction-A lattices codes. Most of the related research in LDPC domain assumes optimal power allocation to encoded codeword. The source coding problem of mapping message to power optimal codeword for any LDPC code is in general, NP-hard. In this thesis, we present a novel method for encoding and decoding lattice based on non-binary LDPC codes using message-passing algorithms. / text

Η εργασία αυτή είχε ως σκοπό τη μελέτη της λειτουργίας των κωδικών LDPC, τη χρήση τους σε συστήματα μετάδοσης δεδομένων και την υλοποίησή τους σε κύκλωμα με επεξεργαστές ARM και FPGA. Ο στόχος ήταν να κατασκευαστεί ένα μοντέλο συνεχούς αποστολής και λήψης εικόνων μέσω μη αξιόπιστων μέσων. Αρχικά μελετήσαμε τα θεωρητικά θέματα που αφορούν τους κώδικες LDPC. Μετά ακολούθησε η προσομοίωση των διαδικασιών κωδικοποίησης, αποκωδικοποίησης και η μοντελοποίηση καναλιού. Η εφαρμογή των κωδίκων LDPC βασίστηκε στην προδιαγραφή ETSI EN 302 307. Αυτή η προδιαγραφή αφορά τις δορυφορικές επικοινωνίες και τυποποιεί τις αντίστοιχες εφαρμογές. Το επόμενο βήμα ήταν η υλοποίηση των λειτουργιών του κωδικοποιητή και του αποκωδικοποιητή LDPC. Τέλος, ελέγχθηκε η ορθή λειτουργία των εργασιών κωδικοποίησης και αποκωδικοποίησης και ελήφθησαν οι μετρήσεις σε σχέση με την απόδοση του υλικού. / This thesis was designed to study the function of the LDPC codes, their use in data transmission systems and their implementation in circuit with ARM processors and FPGA. The aim was to construct a model of continuous send and receive pictures via unreliable media (channels introduce errors). Initially we studied the theoretical issues surrounding the LDPC codes. After that we simulated the procedures of coding, decoding and channel modeling. The implementation of LDPC codes was based on the specification ETSI EN 302 307. This specification relates to satellite communications and standardizes the respective applications. The next step was the implementation of the functions of the LDPC encoder and decoder. Finally the proper functioning of coding and decoding operations was checked and measurements relative to the performance of the hardware were taken.

Αξιοσημείωτη επίδραση στην εξέλιξη και ανάπτυξη των επικοινωνιακών συστημάτων έχει παρουσιάσει το όριο χωρητικότητας διαύλου, το οποίο εισήγαγε ο Claude Shannon. Σήμερα γνωρίζουμε αρκετούς κώδικες διόρθωσης σφαλμάτων οι οποίοι προσεγγίζουν αρκετά τη μέγιστη χωρητικότητα του διαύλου. Ανάμεσα σε αυτούς, εξέχουσα θέση κατέχουν οι Turbo και οι LDPC κώδικες, οι οποίοι ανήκουν στην κατηγορία των κωδίκων τύπου-Turbo. Στην παρούσα διπλωματική εργασία γίνεται ανάλυση της λειτουργίας και της επίδοσης των LDPC κωδίκων σε AWGN δίαυλο. Συγκεκριμένα, υπολογίζεται ο ρυθμός σφάλματος ψηφίου (BER) ενός σήματος που μεταδίδεται διαμέσου ενός AWGN διαύλου και τα αποτελέσματα που προκύπτουν συγκρίνονται με τα αντίστοιχα ενός σήματος που δεν έχει υποστεί κωδικοποίηση. Επίσης, μελετάται η απόδοση του κώδικα για διάφορες τιμές επαναλήψεων του αλγορίθμου αποκωδικοποίησης. / The channel capacity limit, which was determined by Claude Shannon, has caused a great impact on the evolution of communication systems. We know of error correction codes that closely approach this limit. Turbo codes and LDPC codes, which are a class of Turbo-like codes, are of great significance. The present thesis analyses the performance of LDPC codes in an AWGN channel. Particularly, it studies the bit error rate (BER) of a signal which is conveyed through an AWGN channel and compares the results with the ones of the corresponding uncoded signal. Furthermore, the thesis studies the performance of the code for a number of iterations of the decoding algorithm.

Η διόρθωση λαθών με κώδικες 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.

Στη διπλωματική εργασία μελετήθηκε ο σχεδιασμός και η βελτιστοποίηση αρχιτεκτονικών αποκωδικοποιητων LDPC. Μελετήθηκε η δυνατότητα απλούστευσης του πολύπλοκου δικτύου διασύνδεσης των επεξεργαστικών στοιχείων της αρχιτεκτονικής που αποτελεί καθοριστικό παράγοντα της πολυπλοκότητας της υλοποίησης σε υλικό των αποκωδικοποιητών. Αναπτύχθηκε συστηματικός τρόπος αντιμετώπισης του προβλήματος αυτού, ανεξαρτήτως συγκεκριμένου κώδικα LDPC. / The design and optimization of LDPC decoders architecture was studied. An architecture with simplified interconnections and a systematic algorithm to derive it, regardless of the LDPC code, was proposed.

Low-density parity-check (LDPC) codes have been intensively studied in the past decade for their capacity-approaching performance. LDPC code implementation complexity and the error-rate floor are still two significant unsolved issues which prevent their application in some important communication systems. In this dissertation, we make efforts toward solving these two problems by introducing the design of a class of LDPC codes called structured irregular repeat-accumulate (S-IRA) codes. These S-IRA codes combine several advantages of other types of LDPC codes, including low encoder and decoder complexities, flexibility in design, and good performance on different channels. It is also demonstrated in this dissertation that the S-IRA codes are suitable for rate-compatible code family design and a multi-rate code family has been designed which may be implemented with a single encoder/decoder.The study of the error floor problem of LDPC codes is very difficult because simulating LDPC codes on a computer at very low error rates takes an unacceptably long time. To circumvent this difficulty, we implemented a universal quasi-cyclic LDPC decoder on a field programmable gate array (FPGA) platform. This hardware platform accelerates the simulations by more than 100 times as compared to software simulations. We implemented two types of decoders with partially parallel architectures on the FPGA: a circulant-based decoder and a protograph-based decoder. By focusing on the protograph-based decoder, different soft iterative decoding algorithms were implemented. It provides us with a platform for quickly evaluating and analyzing different quasi-cyclic LDPC codes, including the S-IRA codes. A universal decoder architecture is also proposed which is capable of decoding of an arbitrary LDPC code, quasi-cyclic or not. Finally, we studied the low-floor problem by focusing on one example S-IRA code. We identified the weaknesses of the code and proposed several techniques to lower the error floor. We successfully demonstrated in hardware that it is possible to lower the floor substantially by encoder and decoder modifications, but the best solution appeared to be an outer BCH code.

In wireless communications, the use of multiple antennas at both the transmitter and the receiver is a key technology to enable high data rate transmission without additional bandwidth or transmit power. Multiple-input multiple-output (MIMO) schemes are widely used in many wireless standards, allowing higher throughput using spatial multiplexing techniques. MIMO soft detection poses significant challenges to the MIMO receiver design as the detection complexity increases exponentially with the number of antennas. As the next generation wireless system is pushing for multi-Gbps data rate, there is a great need for high-throughput low-complexity soft-output MIMO detector. The brute-force implementation of the optimal MIMO detection algorithm would consume enormous power and is not feasible for the current technology. We propose a reduced-complexity soft-output MIMO detector architecture based on a trellis-search method. We convert the MIMO detection problem into a shortest path problem. We introduce a path reduction and a path extension algorithm to reduce the search complexity while still maintaining sufficient soft information values for the detection. We avoid the missing counter-hypothesis problem by keeping multiple paths during the trellis search process. The proposed trellis-search algorithm is a data-parallel algorithm and is very suitable for high speed VLSI implementation. Compared with the conventional tree-search based detectors, the proposed trellis-based detector has a significant improvement in terms of detection throughput and area efficiency. The proposed MIMO detector has great potential to be applied for the next generation Gbps wireless systems by achieving very high throughput and good error performance. The soft information generated by the MIMO detector will be processed by a channel decoder, e.g. a low-density parity-check (LDPC) decoder or a Turbo decoder, to recover the original information bits. Channel decoder is another very computational-intensive block in a MIMO receiver SoC (system-on-chip). We will present high-performance LDPC decoder architectures and Turbo decoder architectures to achieve 1+ Gbps data rate. Further, a configurable decoder architecture that can be dynamically reconfigured to support both LDPC codes and Turbo codes is developed to support multiple 3G/4G wireless standards. We will present ASIC and FPGA implementation results of various MIMO detectors, LDPC decoders, and Turbo decoders. We will discuss in details the computational complexity and the throughput performance of these detectors and decoders.

This thesis presents a clockless stochastic low-density parity-check (LDPC) decoder implemented on a Field-Programmable Gate Array (FPGA). Stochastic computing reduces the wiring complexity necessary for decoding by replacing operations such as multiplication and division with simple logic gates. Clockless decoding increases the throughput of the decoder by eliminating the requirement for node signals to be synchronized after each decoding cycle. With this partial-update algorithm the decoder’s speed is limited by the average wire delay of the interleaver rather than the worst-case delay. This type of decoder has been simulated in the past but not implemented on silicon. The design is implemented on an ALTERA Stratix IV EP4SGX230 FPGA and the frame error rate (FER) performance, throughput and power consumption are presented for (96,48) and (204,102) decoders.

A method for designing low-density parity-check (LDPC) codes for bandwidth-efficient high-order coded modulation is proposed. Code structure utilizes the multi-edge-type LDPC code ensemble to achieve an improved match between codeword bit protection ca- pabilities and modulation bit-channel capacities over existing LDPC coded modulation techniques. The multi-dimensional EXIT vector field for the specific multi-edge parame- terization is developed for the analysis and design of code ensembles. A multi-dimensional EXIT decoding convergence condition is derived to enable efficient optimization. Code design results in terms of ensemble thresholds and finite-length Monte-Carlo simulations indicate that the new technique improves on the state-of-the-art performance, with sig- nificantly lower design and implementation complexity.

A method for designing low-density parity-check (LDPC) codes for bandwidth-efficient high-order coded modulation is proposed. Code structure utilizes the multi-edge-type LDPC code ensemble to achieve an improved match between codeword bit protection ca- pabilities and modulation bit-channel capacities over existing LDPC coded modulation techniques. The multi-dimensional EXIT vector field for the specific multi-edge parame- terization is developed for the analysis and design of code ensembles. A multi-dimensional EXIT decoding convergence condition is derived to enable efficient optimization. Code design results in terms of ensemble thresholds and finite-length Monte-Carlo simulations indicate that the new technique improves on the state-of-the-art performance, with sig- nificantly lower design and implementation complexity.