Στα πλαίσια αυτής της διπλωματικής εργασίας μελετήσαμε μεθόδους κωδικοποίησης με χρήση πινάκων ισοτιμίας μεγάλων διαστάσεων που έχουν χρησιμοποιηθεί και εφαρμοσθεί μέχρι τώρα σε προηγούμενες μελέτες. Επιλέξαμε τη σχεδίαση ενός αποκωδικοποιητή, που στηρίζεται στο WiMAX – 802.16e ΙΕΕΕ πρότυπο μετάδοσης και συγκεκριμένα με χρήση πομπού και δέκτη με περισσότερες από μία κεραίες. Παρουσιάζουμε, λοιπόν τη θεωρία που συσχετίζεται με το θέμα αυτό τόσο από την πλευρά της κωδικοποίησης όσο κι από την πλευρά της ασύρματης ΜΙΜΟ μετάδοσης και το πρότυπο WiMAX. Αναλύουμε κάθε τμήμα του συστήματός που προσομοιώνουμε και παραθέτουμε τα αποτελέσματα της προσομοίωσης. / -

Among the recent advances in the area of low-density parity-check (LDPC) codes, protograph-based LDPC codes have the advantages of a simple design procedure and highly structured encoders and decoders. These advantages can also be exploited in the design of protograph-based generalized LDPC (G-LDPC) codes. In this dissertation we provide analytical tools which aid the design of protograph-based LDPC and G-LDPC codes. Specifically, we propose a method for computing the codeword-weight enumerators for finite-length protograph-based G-LDPC code ensembles, and then we consider the asymptotic case when the block-length goes to infinity. These results help the designer identify good ensembles of protograph-based G-LDPC codes in the minimum distance sense (i.e., ensembles which have minimum distances grow linearly with code length). Furthermore, good code ensembles can be characterized by good stopping set, trapping set, or pseudocodeword properties, which assist in the design of G-LDPC codes with low floors. We leverage our method for computing codeword-weight enumerators to compute stopping-set, and pseudocodeword enumerators for the finite-length and the asymptotic ensembles of protograph-based G-LDPC codes. Moreover, we introduce a method for computing trapping set enumerators for finite-length (and asymptotic) protograph-based LDPC code ensembles. Trapping set enumerators for G-LDPC codes represents a more complex problem which we do not consider here. Inspired by our method for computing trapping set enumerators for protograph-based LDPC code ensembles, we developed an algorithm for estimating the trapping set enumerators for a specific LDPC code given its parity-check matrix. We used this algorithm to enumerate trapping sets for several LDPC codes from communication standards. Finally, we study coded-modulation schemes with LDPC codes and pulse position modulation (LDPC-PPM) over the free-space optical channel. We present three different decoding schemes and compare their performances. In addition, we developed a new density evolution tool for use in the design of LDPC codes with good performances over this channel.

The ever-increasing demands for transmission capacity are the cause for the quick evolution of optical communication systems. Channel transmission at 100 Gb/s is already being considered by network operators. The major transmission impairments at these high rates are intra-channel and inter-channel nonlinearities, nonlinear phase noise, and polarization mode dispersion. By implementing LDPC-coded modulation schemes with soft decoding and Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm for equalization we have demonstrated significant improvements in system performance experiencing several impairments simultaneously. The new turbo-equalization scheme is used as a mean to simultaneously mitigate both linear and nonlinear impairments. This approach is general and applicable to both direct and coherent detection.We provide comprehensive study of LDPC codes suitable for implementation in high-speed optical transmission systems. We determine channel capacity based on the forward step of the BCJR algorithm and show that by using LDPC codes we can closely approach the maximum transmission capacity that is possible. We propose the multilevel maximum a posteriori probability (MAP) turbo equalization scheme based on multilevel BCJR algorithm and an LDPC decoder, which considers independent symbols transmitted over both polarizations as two dimensional super-symbols. The use of multilevel modulation schemes provide higher spectral efficiency, while all related signal processing is performed at lower symbol rates, where dealing with PMD compensation and fiber nonlinearities mitigation is more manageable. We show significant improvement in system performance over a system employing an equalizer that considers symbols transmitted in different polarizations as independent.

The growing popularity of a class of linear block codes called the low-density parity-check (LDPC) codes can be attributed to the low complexity of the iterative decoders, and their potential to achieve performance very close to the Shannon capacity. This makes them an attractive candidate for ECC applications in communication systems. This report proposes methods to systematically construct regular and irregular LDPC codes.A class of regular LDPC codes are constructed from incidence structures in finite geometries like projective geometry and affine geometry. A class of irregular LDPC codes are constructed by systematically splitting blocks of balanced incomplete block designs to achieve desired weight distributions. These codes are decoded iteratively using message-passing algorithms, and the performance of these codes for various channels are presented in this report.The application of iterative decoders is generally limited to a class of codes whose graph representations are free of small cycles. Unfortunately, the large class of conventional algebraic codes, like RS codes, has several four cycles in their graph representations. This report proposes an algorithm that aims to alleviate this drawback by constructing an equivalent graph representation that is free of four cycles. It is theoretically shown that the four-cycle free representation is better suited to iterative erasure decoding than the conventional representation. Also, the new representation is exploited to realize, with limited success, iterative decoding of Reed-Solomon codes over the additive white Gaussian noise channel.Wiberg, Forney, Richardson, Koetter, and Vontobel have made significant contributions in developing theoretical frameworks that facilitate finite length analysis of codes. With an exception of Richardson's, most of the other frameworks are much suited for the analysis of short codes. In this report, we further the understanding of the failures in iterative decoders for the binary symmetric channel. The failures of the decoder are classified into two categories by defining trapping sets and propagating sets. Such a classification leads to a successful estimation of the performance of codes under the Gallager B decoder. Especially, the estimation techniques show great promise in the high signal-to-noise ratio regime where the simulation techniques are less feasible.

Ever since the publication of Shannon's seminal work in 1948, the search for capacity achieving codes has led to many interesting discoveries in channel coding theory. Low-density parity-check (LDPC) codes originally proposed in 1963 were largely forgotten and rediscovered recently. The significance of LDPC codes lies in their capacity approaching performance even when decoded using low complexity sub-optimal decoding algorithms. Iterative decoders are one such class of decoders that work on a graphical representation of a code known as the Tanner graph. Their properties have been well understood in the asymptotic limit of the code length going to infinity. However, the behavior of various decoders for a given finite length code remains largely unknown.An understanding of the failures of the decoders is vital for the error floor analysis of a given code. Broadly speaking, error floor is the abrupt degradation in the frame error rate (FER) performance of a code in the high signal-to-noise ratio domain. Since the error floor phenomenon manifests in the regions not reachable by Monte-Carlo simulations, analytical methods are necessary for characterizing the decoding failures. In this work, we consider hard decision decoders for transmission over the binary symmetric channel (BSC).For column-weight-three codes, we provide tight upper and lower bounds on the guaranteed error correction capability of a code under the Gallager A algorithm by studying combinatorial objects known as trapping sets. For higher column weight codes, we establish bounds on the minimum number of variable nodes that achieve certain expansion as a function of the girth of the underlying Tanner graph, thereby obtaining lower bounds on the guaranteed error correction capability. We explore the relationship between a class of graphs known as cage graphs and trapping sets to establish upper bounds on the error correction capability.We also propose an algorithm to identify the most probable noise configurations, also known as instantons, that lead to error floor for linear programming (LP) decoding over the BSC. With the insight gained from the above analysis techniques, we propose novel code construction techniques that result in codes with superior error floor performance.

Continuous Phase Modulation is a popular digital modulation scheme for systems which have tight spectral efficiency and Peak-to-Average ratio (PAR) constraints. In this thesis we propose a method of estimating the capacity for a Continuous Phase Modulation (CPM) system and also describe techniques for design of codes for this system. We note that the CPM modulator can be decomposed into a trellis code followed by a memoryless modulator. This decomposition enables us to perform iterative demodulation of the signal and improve the performance of the system. Thus we have the option of either performing iterative demodulation, where the channel decoder and the demodulator are invoked in an iterative fashion, or a non-iterative demodulation, where the demodulation is performed only once followed by the decoding of the message. We highlight the recent results in the estimation of capacity for channels with memory and apply it to a CPM system. We estimate two different types of capacity of the CPM system over an Additive White Gaussian Noise (AWGN). The first capacity assumes that optimum demodulation and decoding is done, and the second one assumes that the demodulation is done only once. Having obtained the capacity of the system we try to approach this capacity by designing outer codes matched to the CPM system. We utilized LDPC codes, since they can be designed to perform very close to capacity limit of the system. The design complexity for LDPC codes can be reduced by assuming that the input to the decoder is Gaussian distributed. We explore three different ways of approximating the CPM demodulator output to a Gaussian distribution and use it to design LDPC codes for a Bit Interleaved Coded Modulation (BICM) system. Finally we describe the design of Multi Level Codes (MLC) for CPM systems using the capacity matching rule.

No description available.

The efficient and reliable communication of data from multiple sources to a single receiver plays an important role in emerging applications such as wireless sensor networks. The correlation among observations picked-up by spatially distributed sensors in such a network can be exploited to enhance the efficiency and reliability of communication. In particular, information theory shows that optimal communication of information from correlated sources requires distributed joint source-channel (DJSC) coding. This dissertation develops new approaches to designing DJSC codes based on low density parity check (LDPC) codes. The existence of low complexity code optimization algorithms and decoding algorithms make these codes ideal for joint optimization and decoding of multiple codes operating on correlated sources. The well known EXIT analysis-based LDPC code optimization method for channel coding in single-user point-to-point systems is extended to the optimization of two-user LDPC codes for DJSC coding in multi-access channels (MACs) with correlated users. Considering an orthogonal MAC with two correlated binary sources, an asymptotically optimal DJSC code construction capable of achieving any rate-pair in the theoretically-achievable two-user rate-region is presented. A practical approach to realizing this scheme using irregular LDPC codes is then developed. Experimental results are presented which demonstrate that the proposed codes can approach theoretical bounds when the codeword length is increased. For short codeword length and high inter-source correlation, these DJSC codes are shown to significantly outperform separate source and channel codes. Next, the DJSC code design for the transmission of a pair of correlated binary sources over a Gaussian MAC (GMAC) is investigated. The separate source and channel coding is known to be sub-optimal in this case. For the optimization of a pair of irregular LDPC codes, the EXIT analysis for message passing in a joint factor-graph decoder is analyzed, and an approach to modeling the probability density functions of messages associated with graph nodes which represent the inter-source dependence is proposed. Simulation results show that, for sufficiently large codeword lengths and high inter-source correlation, the proposed DJSC codes for GMAC can achieve rates higher than the theoretical upper bound for separate source and channel coding.

The efficient and reliable communication of data from multiple sources to a single receiver plays an important role in emerging applications such as wireless sensor networks. The correlation among observations picked-up by spatially distributed sensors in such a network can be exploited to enhance the efficiency and reliability of communication. In particular, information theory shows that optimal communication of information from correlated sources requires distributed joint source-channel (DJSC) coding. This dissertation develops new approaches to designing DJSC codes based on low density parity check (LDPC) codes. The existence of low complexity code optimization algorithms and decoding algorithms make these codes ideal for joint optimization and decoding of multiple codes operating on correlated sources. The well known EXIT analysis-based LDPC code optimization method for channel coding in single-user point-to-point systems is extended to the optimization of two-user LDPC codes for DJSC coding in multi-access channels (MACs) with correlated users. Considering an orthogonal MAC with two correlated binary sources, an asymptotically optimal DJSC code construction capable of achieving any rate-pair in the theoretically-achievable two-user rate-region is presented. A practical approach to realizing this scheme using irregular LDPC codes is then developed. Experimental results are presented which demonstrate that the proposed codes can approach theoretical bounds when the codeword length is increased. For short codeword length and high inter-source correlation, these DJSC codes are shown to significantly outperform separate source and channel codes. Next, the DJSC code design for the transmission of a pair of correlated binary sources over a Gaussian MAC (GMAC) is investigated. The separate source and channel coding is known to be sub-optimal in this case. For the optimization of a pair of irregular LDPC codes, the EXIT analysis for message passing in a joint factor-graph decoder is analyzed, and an approach to modeling the probability density functions of messages associated with graph nodes which represent the inter-source dependence is proposed. Simulation results show that, for sufficiently large codeword lengths and high inter-source correlation, the proposed DJSC codes for GMAC can achieve rates higher than the theoretical upper bound for separate source and channel coding.

Since their rediscovery in 1995, low-density parity-check (LDPC) codes have received wide-spread attention as practical capacity-approaching code candidates. It has been shown that the class of codes can perform arbitrarily close to the channel capacity, and LDPC codes are also used or suggested for a number of important current and future communication standards. However, the problem of implementing an energy-efficient decoder has not yet been solved. Whereas the decoding algorithm is computationally simple, withuncomplicated arithmetic operations and low accuracy requirements, the random structure and irregularity of a theoretically well-defined code does not easily allow efficient VLSI implementations. Thus the LDPC decoding algorithm can be said to be communication-bound rather than computation-bound. In this thesis, a modification to the sum-product decoding algorithm called early-decision decoding is suggested. The modification is based on the idea that the values of the bits in a block can be decided individually during decoding. As the sum-product decoding algorithm is a soft-decision decoder, a reliability can be defined for each bit. When the reliability of a bit is above a certain threshold, the bit can be removed from the rest of the decoding process, and thus the internal communication associated with the bit can be removed in subsequent iterations. However, with the early decision modification, an increased error probability is associated. Thus, bounds on the achievable performance as well as methods to detect graph inconsistencies resulting from erroneous decisions are presented. Also, a hybrid decoder achieving a negligible performance penalty compared to the sum-product decoder is presented. With the hybrid decoder, the internal communication is reduced with up to 40% for a rate-1/2 code with a length of 1152 bits, whereas increasing the rate allows significantly higher gains. The algorithms have been implemented in a Xilinx Virtex 5 FPGA, and the resulting slice utilization andenergy dissipation have been estimated. However, due to increased logic overhead of the early decision decoder, the slice utilization increases from 14.5% to 21.0%, whereas the logic energy dissipation reduction from 499 pJ to 291 pJ per iteration and bit is offset by the clock distribution power, increased from 141 pJ to 191 pJ per iteration and bit. Still, the early decision decoder shows a net 16% estimated decrease of energy dissipation.