<p>Recently, low-density parity-check (LDPC) codes have attracted much attention because of their excellent error correcting performance and highly parallelizable decoding scheme. However, the effective VLSI implementation of and LDPC decoder remains a big challenge and is a crucial issue in determining how well we can exploit the benefits of the LDPC codes in the real applications. In this master thesis report, following a error coding background, we describe Low-Density Parity-Check codes and their decoding algorithm, and also requirements and architectures of LPDC decoder implementations.</p>

<p>The family of Low Density Parity Check (LDPC) codes is a strong candidate to be used as Forward Error Correction (FEC) in future communication systems due to its strong error correction capability. Most LDPC decoders use the Message Passing algorithm for decoding, which is an iterative algorithm that passes messages between its variable nodes and check nodes. It is not until recently that computation power has become strong enough to make Message Passing on LDPC codes feasible. Although locally simple, the LDPC codes are usually large, which increases the required computation power. Earlier work on LDPC codes has been concentrated on the binary Galois Field, GF(2), but it has been shown that codes from higher order fields have better error correction capability. However, the most efficient LDPC decoder, the Belief Propagation Decoder, has a squared complexity increase when moving to higher order Galois Fields. Transmission over a channel with M-PSK signalling is a common technique to increase spectral efficiency. The information is transmitted as the phase angle of the signal.</p><p>The focus in this Master’s Thesis is on simplifying the Message Passing decoding when having inputs from M-PSK signals transmitted over an AWGN channel. Symbols from higher order Galois Fields were mapped to M-PSK signals, since M-PSK is very bandwidth efficient and the information can be found in the angle of the signal. Several simplifications of the Belief Propagation has been developed and tested. The most promising is the Table Vector Decoder, which is a Message Passing Decoder that uses a table lookup technique for check node operations and vector summation as variable node operations. The table lookup is used to approximate the check node operation in a Belief Propagation decoder. Vector summation is used as an equivalent operation to the variable node operation. Monte Carlo simulations have shown that the Table Vector Decoder can achieve a performance close to the Belief Propagation. The capability of the Table Vector Decoder depends on the number of reconstruction points and the placement of them. The main advantage of the Table Vector Decoder is that its complexity is unaffected by the Galois Field used. Instead, there will be a memory space requirement which depends on the desired number of reconstruction points.</p>

This thesis investigates channel-coded physical layer network coding, in which the relay directly transforms the noisy superimposed channel-coded packets received from the two end nodes, to the network-coded combination of the source packets. This is in contrast to the traditional multiple-access problem, in which the goal is to obtain each message explicitly at the relay. Here, the end nodes $A$ and $B$ choose their symbols, $S_A$ and $S_B$, from a small non-binary field, $\mathbb{F}$, and use non-binary PSK constellation mapper during the transmission phase. The relay then directly decodes the network-coded combination ${aS_A+bS_B}$ over $\mathbb{F}$ from the noisy superimposed channel-coded packets received from two end nodes. Trying to obtain $S_A$ and $S_B$ explicitly at the relay is overly ambitious when the relay only needs $aS_B+bS_B$. For the binary case, the only possible network-coded combination, ${S_A+S_B}$ over the binary field, does not offer the best performance in several channel conditions. The advantage of working over non-binary fields is that it offers the opportunity to decode according to multiple decoding coefficients $(a,b)$. As only one of the network-coded combinations needs to be successfully decoded, a key advantage is then a reduction in error probability by attempting to decode against all choices of decoding coefficients. In this thesis, we compare different constellation mappers and prove that not all of them have distinct performance in terms of frame error rate. Moreover, we derive a lower bound on the frame error rate performance of decoding the network-coded combinations at the relay. Simulation results show that if we adopt concatenated Reed-Solomon and convolutional coding or low density parity check codes at the two end nodes, our non-binary constellations can outperform the binary case significantly in the sense of minimizing the frame error rate and, in particular, the ternary constellation has the best frame error rate performance among all considered cases.

Recently, low-density parity-check (LDPC) codes have attracted much attention because of their excellent error correcting performance and highly parallelizable decoding scheme. However, the effective VLSI implementation of and LDPC decoder remains a big challenge and is a crucial issue in determining how well we can exploit the benefits of the LDPC codes in the real applications. In this master thesis report, following a error coding background, we describe Low-Density Parity-Check codes and their decoding algorithm, and also requirements and architectures of LPDC decoder implementations.

The family of Low Density Parity Check (LDPC) codes is a strong candidate to be used as Forward Error Correction (FEC) in future communication systems due to its strong error correction capability. Most LDPC decoders use the Message Passing algorithm for decoding, which is an iterative algorithm that passes messages between its variable nodes and check nodes. It is not until recently that computation power has become strong enough to make Message Passing on LDPC codes feasible. Although locally simple, the LDPC codes are usually large, which increases the required computation power. Earlier work on LDPC codes has been concentrated on the binary Galois Field, GF(2), but it has been shown that codes from higher order fields have better error correction capability. However, the most efficient LDPC decoder, the Belief Propagation Decoder, has a squared complexity increase when moving to higher order Galois Fields. Transmission over a channel with M-PSK signalling is a common technique to increase spectral efficiency. The information is transmitted as the phase angle of the signal. The focus in this Master’s Thesis is on simplifying the Message Passing decoding when having inputs from M-PSK signals transmitted over an AWGN channel. Symbols from higher order Galois Fields were mapped to M-PSK signals, since M-PSK is very bandwidth efficient and the information can be found in the angle of the signal. Several simplifications of the Belief Propagation has been developed and tested. The most promising is the Table Vector Decoder, which is a Message Passing Decoder that uses a table lookup technique for check node operations and vector summation as variable node operations. The table lookup is used to approximate the check node operation in a Belief Propagation decoder. Vector summation is used as an equivalent operation to the variable node operation. Monte Carlo simulations have shown that the Table Vector Decoder can achieve a performance close to the Belief Propagation. The capability of the Table Vector Decoder depends on the number of reconstruction points and the placement of them. The main advantage of the Table Vector Decoder is that its complexity is unaffected by the Galois Field used. Instead, there will be a memory space requirement which depends on the desired number of reconstruction points.

The area of cooperative communications has received tremendous research interest in recent years. This interest is not unwarranted, since cooperative communications promises the ever-so-sought after diversity and multiplexing gains typically associated with multiple-input multiple-output (MIMO) communications, without actually employing multiple antennas. In this dissertation, we consider several cooperative communication channels, and for each one of them, we develop information theoretic coding schemes and derive their corresponding performance limits. We next develop and design practical coding strategies which perform very close to the information theoretic limits. The cooperative communication channels we consider are: (a) The Gaussian relay channel, (b) the quasi-static fading relay channel, (c) cooperative multiple-access channel (MAC), and (d) the cognitive radio channel (CRC). For the Gaussian relay channel, we propose a compress-forward (CF) coding strategy based on Wyner-Ziv coding, and derive the achievable rates specifically with BPSK modulation. The CF strategy is implemented with low-density parity-check (LDPC) and irregular repeataccumulate codes and is found to operate within 0.34 dB of the theoretical limit. For the quasi-static fading relay channel, we assume that no channel state information (CSI) is available at the transmitters and propose a rateless coded protocol which uses rateless coded versions of the CF and the decode-forward (DF) strategy. We implement the protocol with carefully designed Raptor codes and show that the implementation suffers a loss of less than 10 percent from the information theoretical limit. For the MAC, we assume quasi-static fading, and consider cooperation in the low-power regime with the assumption that no CSI is available at the transmitters. We develop cooperation methods based on multiplexed coding in conjunction with rateless codes and find the achievable rates and in particular the minimum energy per bit to achieve a certain outage probability. We then develop practical coding methods using Raptor codes, which performs within 1.1 dB of the performance limit. Finally, we consider a CRC and develop a practical multi-level dirty-paper coding strategy using LDPC codes for channel coding and trellis-coded quantization for source coding. The designed scheme is found to operate within 0.78 dB of the theoretical limit. By developing practical coding strategies for several cooperative communication channels which exhibit performance close to the information theoretic limits, we show that cooperative communications not only provide great benefits in theory, but can possibly promise the same benefits when put into practice. Thus, our work can be considered a useful and necessary step towards the commercial realization of cooperative communications.

Recently, a novel technique for multi-user spread-spectrum mobile systems, the called interleave-division multiple-access (IDMA) scheme, was proposed by L. Ping etc. The advantage of IDMA is that it inherits many special features from code-division multiple-access (CDMA) such as diversity against fading and mitigation of the other-cell user interference. Moreover, it¡¦s capable of employing a very simple chip-by-chip iterative multi-user detection strategy. In this thesis, we investigate the performance of combining IDMA and orthogonal frequency-division multiplexing (OFDM) scheme. In order to improve the bit error rate performance, we applied low-density parity-check (LDPC) coding to the proposed scheme, named by LDPC Coded OFDM-IDMA Systems. Based on the aid of iterative multi-user detection algorithm, the multiple-access interference (MAI) and inter-symbol interference (ISI) could be canceling efficiently. In short, the proposed scheme provides an efficient solution to high-rate multiuser communications over multipath fading channels.

Οι κώδικες LDPC ανήκουν στην κατηγορία των block κωδικών. Πρόκειται για κώδικες ελέγχου σφαλμάτων μετάδοσης και πιο συγκεκριμένα για κώδικες διόρθωσης σφαλμάτων. Αν και η εφεύρεσή τους (από τον Gallager) τοποθετείται χρονικά στις αρχές της δεκαετίας του 60, μόλις τα τελευταία χρόνια κατάφεραν να κεντρίσουν το έντονο ενδιαφέρον της επιστημονικής-ερευνητικής κοινότητας για τις αξιόλογες επιδόσεις τους. Πρόκειται για κώδικες ελέγχου ισοτιμίας με κυριότερο χαρακτηριστικό τον χαμηλής πυκνότητας πίνακα ελέγχου ισοτιμίας (Low Density Parity Check) από τον οποίο και πήραν το όνομά τους. Δεδομένου ότι η κωδικοποίηση των συγκεκριμένων κωδικών είναι σχετικά απλή, η αποκωδικοποίηση τους είναι εκείνη η οποία καθορίζει σε μεγάλο βαθμό τα χαρακτηριστικά του κώδικα που μας ενδιαφέρουν, όπως είναι η ικανότητα διόρθωσης σφαλμάτων μετάδοσης (επίδοση) και η καταναλισκόμενη ισχύς. Για το λόγο αυτό έχουν αναπτυχθεί διάφοροι αλγόριθμοι αποκωδικοποίησης, οι οποίοι είναι επαναληπτικοί. Παρόλο που οι ανεπτυγμένοι αλγόριθμοι και οι διάφορες εκδοχές τους δεν είναι λίγοι, δεν έχει ακόμα καταστεί εφικτό να αναλυθεί θεωρητικά η επίδοσή τους. Στην παρούσα εργασία παρατίθενται οι κυριότεροι αλγόριθμοι αποκωδικοποίησης κωδικών LDPC, που έχουν αναπτυχθεί μέχρι σήμερα. Οι αλγόριθμοι αυτοί υλοποιούνται και συγκρίνονται βάσει των αποτελεσμάτων εξομοιώσεων. Ο πιο αποδοτικός από αυτούς είναι ο αποκαλούμενος αλγόριθμος log Sum-Product και στηρίζει σε μεγάλο βαθμό την επίδοσή του σε μία αρκετά πολύπλοκή συνάρτηση, την Φ(x). Η υλοποίηση της τελευταίας σε υλικό επιβάλλει την πεπερασμένη ακρίβεια αναπαράστασής της, δηλαδή τον κβαντισμό της. Το σφάλμα κβαντισμού που εισάγεται από την διαδικασία αυτή θέτει ένα όριο στην επίδοση του αλγορίθμου. Η μελέτη που έγινε στα πλαίσια της εργασίας οδήγησε στον προσδιορισμό δύο μηχανισμών εισαγωγής σφάλματος κβαντισμού στον αλγόριθμο log Sum-Product και στη θεωρητική έκφραση της πιθανότητας εμφάνισης κάθε μηχανισμού κατά την πρώτη επανάληψη του αλγορίθμου. Μελετήθηκε επίσης ο τρόπος με τον οποίο το εισαγόμενο σφάλμα κβαντισμού επιδρά στην απόφαση του αλγορίθμου στο τέλος της κάθε επανάληψης και αναπτύχθηκε ένα θεωρητικό μοντέλο αυτού του μηχανισμού. Το θεωρητικό μοντέλο δίνει την πιθανότητα αλλαγής απόφασης του αλγορίθμου λόγω του σφάλματος κβαντισμού της συνάρτησης Φ(x), χωρίς όμως να είναι ακόμα πλήρες αφού βασίζεται και σε πειραματικά δεδομένα. Η ολοκλήρωση του μοντέλου, ώστε να είναι πλήρως θεωρητικό, θα μπορούσε να αποτελέσει αντικείμενο μελλοντικής έρευνας, καθώς θα επιτρέψει τον προσδιορισμό του περιορισμού της επίδοσης του αλγορίθμου για συγκεκριμένο σχήμα κβαντισμού της συνάρτησης, αποφεύγοντας χρονοβόρες εξομοιώσεις. / Low-Density Parity-Check (LDPC) codes belong to the category of Linear Block Codes. They are error detection and correction codes. Although LDPC codes have been proposed by R. Gallager since 1962, they were scarcely considered in the 35 years that followed. Only in the end-90's they were rediscovered due to their decoding performance that approaches Shannon limit. As their name indicates they are parity check codes whose parity check matrix is sparse. Since the encoding process is simple, the decoding procedure determines the performance and the consumed power of the decoder. For this reason several iterative decoding algorithms have been developed. However theoretical determination of their performance has not yet been feasible. This work presents the most important iterative decoding algorithms for LDPC codes, that have been developed to date. These algorithms are implemented in matlab and their performance is studied through simulation. The most powerful among them, namely Log Sum-Product, uses a very nonlinear function called Φ(x). Hardware implementation of this function enforces finite accuracy, due to finite word length representation. The roundoff error that this procedure imposes, impacts the decoding performance by means of two mechanisms. Both mechanisms are analyzed and a theoretical expression for each mechanism activation probability, at the end of the first iteration of the algorithm, is developed. The impact of the roundoff error on the decisions taken by the log Sum-Product decoding algorithm at the end of each iteration is also studied. The mechanism by means of which roundoff alters the decisions of a finite word length implementation of the algorithm compared to the infinite precision case, is analyzed and a corresponding theoretical model is developed. The proposed model computes the probability of changing decisions due to finite word length representation of Φ(x), but it is not yet complete, since the determination of the corresponding parameters is achieved through experimental results. Further research focuses on the completion of the theoretical model, since it can lead to a tool that computes the expected degradation of the decoding performance for a particular implementation of the decoder, without the need of time-consuming simulations.

Coding is an essential technology for efficient fiber-optic communications and secure quantum communications. In particular, low-density parity-check (LDPC) coding is favoured due to its strong error correction capability and high-throughput implementation feasibility. In fiber-optic communications, it has been realized that advanced high-order modulation formats and soft-decision forward error correction (FEC) such as LDPC codes are the key technologies for the next-generation high-speed optical communications. Therefore, energy-efficient LDPC coding in combination with advanced modulation formats is an important topic that needs to be studied for fiber-optic communications. In secure quantum communications, large-alphabet quantum key distribution (QKD) is becoming attractive recently due to its potential in improving the efficiency of key exchange. To recover the carried information bits, efficient information reconciliation is desirable, for which the use of LDPC coding is essential. In this dissertation, we first explore different efficient LDPC coding schemes for optical transmission of polarization-division multiplexed quadrature-amplitude modulation (QAM) signals. We show that high energy efficiency can be achieved without incurring extra overhead and complexity. We then study the transmission performance of LDPC-coded turbo equalization for QAM signals in a realistic fiber link as well as that of pragmatic turbo equalizers. Further, leveraging the polarization freedom of light, we expand the signal constellation into a four-dimensional (4D) space and evaluate the performance of LDPC-coded 4D signals in terms of transmission reach. Lastly, we study the security of a proposed weak-coherent-state large-alphabet QKD protocol and investigate the information reconciliation efficiency based on LDPC coding.

Soft iterative detection and decoding techniques have been shown to be able to achieve near-capacity performance in multiple-antenna systems. To obtain the optimal soft information by marginalization over the entire observation space is intractable; and the current literature is unable to guide us towards the best way to obtain the suboptimal soft information. In this thesis, several existing soft-input soft-output (SISO) detectors, including minimum mean-square error-successive interference cancellation (MMSE-SIC), list sphere decoding (LSD), and Fincke-Pohst maximum-a-posteriori (FPMAP), are examined. Prior research has demonstrated that LSD and FPMAP outperform soft-equalization methods (i.e., MMSE-SIC); however, it is unclear which of the two scheme is superior in terms of performance-complexity trade-off. A comparison is conducted to resolve the matter. In addition, an improved scheme is proposed to modify LSD and FPMAP, providing error performance improvement and a reduction in computational complexity simultaneously. Although list-type detectors such as LSD and FPMAP provide outstanding error performance, issues such as the optimal initial sphere radius, optimal radius update strategy, and their highly variable computational complexity are still unresolved. A new detection scheme is proposed to address the above issues with fixed detection complexity, making the scheme suitable for practical implementation. / Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2008-07-08 19:29:17.66