In state-of-the-art fiber-optics communication systems the fixed forward error correction (FEC) and constellation size are employed. While it is important to closely approach the Shannon limit by using turbo product codes (TPC) and low-density parity-check (LDPC) codes with soft-decision decoding (SDD) algorithm; rate-adaptive techniques, which enable increased information rates over short links and reliable transmission over long links, are likely to become more important with ever-increasing network traffic demands. In this invited paper, we describe a rate adaptive non-binary LDPC coding technique, and demonstrate its flexibility and good performance exhibiting no error floor at BER down to 10(-15) in entire code rate range, by FPGA-based emulation, making it a viable solution in the next-generation high-speed intelligent aggregation networks.

Forward error correction (FEC) is as one of the key technologies enabling the next-generation high-speed fiber optical communications. In this paper, we propose a rate-adaptive scheme using a class of generalized low-density parity-check (GLDPC) codes with a Hamming code as local code. We show that with the proposed unified GLDPC decoder architecture, a variable net coding gains (NCGs) can be achieved with no error floor at BER down to 10(-15), making it a viable solution in the next-generation high-speed fiber optical communications.

No description available.

The unifying theme of this dissertation is the development of new solutions for decoding and inference problems based on convex optimization methods. Th first part considers the joint detection and decoding problem for low-density parity-check (LDPC) codes on finite-state channels (FSCs). Hard-disk drives (or magnetic recording systems), where the required error rate (after decoding) is too low to be verifiable by simulation, are most important applications of this research. Recently, LDPC codes have attracted a lot of attention in the magnetic storage industry and some hard-disk drives have started using iterative decoding. Despite progress in the area of reduced-complexity detection and decoding algorithms, there has been some resistance to the deployment of turbo-equalization (TE) structures (with iterative detectors/decoders) in magnetic-recording systems because of error floors and the difficulty of accurately predicting performance at very low error rates. To address this problem for channels with memory, such as FSCs, we propose a new decoding algorithms based on a well-defined convex optimization problem. In particular, it is based on the linear-programing (LP) formulation of the joint decoding problem for LDPC codes over FSCs. It exhibits two favorable properties: provable convergence and predictable error-floors (via pseudo-codeword analysis). Since general-purpose LP solvers are too complex to make the joint LP decoder feasible for practical purposes, we develop an efficient iterative solver for the joint LP decoder by taking advantage of its dual-domain structure. The main advantage of this approach is that it combines the predictability and superior performance of joint LP decoding with the computational complexity of TE. The second part of this dissertation considers the matrix completion problem for the recovery of a data matrix from incomplete, or even corrupted entries of an unknown matrix. Recommender systems are good representatives of this problem, and this research is important for the design of information retrieval systems which require very high scalability. We show that our IMP algorithm reduces the well-known cold-start problem associated with collaborative filtering systems in practice.

At a time where almost 1.75 billion people around the world use the Internet on a regular basis, optical communication over optical fibers that is used in long distance and high demand applications has to be capable of providing higher communication speed and re-liability. In recent years, strong demand is driving the dense wavelength division multip-lexing network upgrade from 10 Gb/s per channel to more spectrally-efficient 40 Gb/s or 100 Gb/s per wavelength channel, and beyond. The 100 Gb/s Ethernet is currently under standardization, and in a couple of years 1 Tb/s Ethernet is going to be standardized as well for different applications, such as the local area networks (LANs) and the wide area networks (WANs). The major concern about such high data rates is the degradation in the signal quality due to linear and non-linear impairments, in particular polarization mode dispersion (PMD) and intrachannel nonlinearities. Moreover, the higher speed transceivers are expensive, so the alternative approaches of achieving the required rates is preferably done using commercially available components operating at lower speeds.In this dissertation, different LDPC-coded modulation techniques are presented to offer a higher spectral efficiency and/or power efficiency, in addition to offering aggregate rates that can go up to 1Tb/s per wavelength. These modulation formats are based on the bit-interleaved coded modulation (BICM) and include: (i) three-dimensional LDPC-coded modulation using hybrid direct and coherent detection, (ii) multidimensional LDPC-coded modulation, (iii) subcarrier-multiplexed four-dimensional LDPC-coded modulation, (iv) hybrid subcarrier/amplitude/phase/polarization LDPC-coded modulation, and (v) iterative polar quantization based LDPC-coded modulation.

Le multicast fiable est certainement la solution la plus efficace pour la distribution de contenu via un<br />tres grand nombre (potentiellement des millions) de recepteurs. Dans cette perspective les protocoles<br />ALC et FLUTE, standardises via l'IETF (RMT WG), ont ete adoptes dans 3GPP/MBMS et dans le<br />DVB-H IP-Datacast dans les contextes des reseaux cellulaires 3G.<br />Ce travail se concentre sur le multicast fiable et a comme requis principal le passage l'echelle massif<br />en terme de nombre de clients. Cette these se base sur les solutions proposees via l'IETF RMT WG.<br />Ces protocoles de multicast fiable sont construit autour de plusieurs briques de base que nous avons<br />etudie en detail:<br />* La brique Forward Error Correction (FEC) :<br />Nous examinons la classe de codes grands blocs Low Density Parity Check (LDPC). Nous concevons<br />des derivees de ces codes, et les analysons en detail. Nous en concluons que les codes<br />LDPC et leur implementation ont des performances tres prometteuses, surtout si ils sont utilisees<br />avec des fichiers de taille importante.<br />* La brique controle de congestion :<br />Nous examinons le comportement dans la phase de demarrage de trois protocoles de controle de<br />congestion RLC, FLID-SL, WEBRC. Nous demontrons que la phase de demarrage a un grand<br />impact sur les performances de telechargement.<br />Cette these a aussi plusieurs contributions au niveau applicatif:<br />* Extensions de FLUTE :<br />Nous proposons un mecanisme permettant d'agreger plusieurs fichiers dans le protocole FLUTE.<br />Ceci ameliore les performance de transmission.<br />* Streaming video :<br />Nous proposons SVSoA, une solution de streaming base sur ALC. Cette approche beneficie de<br />tout les avantages de ALC en terme de passage a l'echelle, controle de congestion et corrections<br />d'erreurs.<br /><br />Mots cles : Multicast fiable, FLUTE, ALC, codes correcteur d'erreurs, Forward Error Correction<br />(FEC), Low Density Parity Check (LDPC) Codes, diffusion de contenu

Οι κώδικες 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.

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

No description available.

Mathematical optimization is applicable to nearly every scientific discipline. This thesis specifically focuses on optimization applications to digital communications and signal processing. Within the digital communications framework, the channel encoder attempts to encode a message from a source (the sender) in such a way that the channel decoder can utilize the encoding to correct errors in the message caused by the transmission over the channel. Low-density parity-check (LDPC) codes are an especially popular code for this purpose. Following the channel encoder in the digital communications framework, the modulator converts the encoded message bits to a physical waveform, which is sent over the channel and converted back to bits at the demodulator. The modulator and demodulator present special challenges for what is known as the two-antenna problem. The main results of this work are two algorithms related to the development of optimization methods for LDPC codes and the two-antenna problem. Current methods for optimization of LDPC codes analyze the degree distribution pair asymptotically as block length approaches infinity. This effectively ignores the discrete nature of the space of valid degree distribution pairs for LDPC codes of finite block length. While large codes are likely to conform reasonably well to the infinite block length analysis, shorter codes have no such guarantee. Chapter 2 more thoroughly introduces LDPC codes, and Chapter 3 presents and analyzes an algorithm for completely enumerating the space of all valid degree distribution pairs for a given block length, code rate, maximum variable node degree, and maximum check node degree. This algorithm is then demonstrated on an example LDPC code of finite block length. Finally, we discuss how the result of this algorithm can be utilized by discrete optimization routines to form novel methods for the optimization of small block length LDPC codes. In order to solve the two-antenna problem, which is introduced in greater detail in Chapter 2, it is necessary to obtain reliable estimates of the timing offset and channel gains caused by the transmission of the signal through the channel. The timing offset estimator can be formulated as an optimization problem, and an optimization method used to solve it was previously developed. However, this optimization method does not utilize gradient information, and as a result is inefficient. Chapter 4 presents and analyzes an improved gradient-based optimization method that solves the two-antenna problem much more efficiently.