En esta tesis se han investigado los algoritmos de decodificación para códigos de comprobación de paridad de baja densidad (LDPC) y las arquitecturas para la implementación hardware de éstos. El trabajo realizado se centra en los algoritmos del tipo de intercambio de mensajes para códigos estructurados los cuales se incluyen en varios estándares de comunicaciones. Inicialmente se han evaluado las prestaciones de los algoritmos existentes Sum-product, Min-Sum y las principales variantes de este último (Min-Sum con escalado y Min-Sum con offset). Además, se ha realizado un análisis de precisión finita utilizando los códigos LDPC de los estándares IEEE 802.3an, IEEE 802.11n e IEEE 802.16e. Posteriormente se han propuesto dos algoritmos basados en el algoritmo Min-Sum, denominados Min-Sum entero y Min-Sum modificado con corrección. La complejidad de éstos es menor que las de los algoritmos estudiados anteriormente y además permiten una implementación hardware eficiente. Por otra parte, se han estudiado diferentes métodos de actualización de los algoritmos de decodificación: por inundación, por capas horizontales (layered) y por capas verticales (shuffled), y se ha propuesto un nuevo método por capas verticales entrelazadas (x-shuffled) que consigue mejorar la tasa de decodificación. Tras el estudio algorítmico, se han realizado implementaciones hardwar} con diferentes arquitecturas para los algoritmos y métodos de actualización evaluados y propuestos. En la mayoría de algoritmos implementados se requiere el cálculo de los dos primeros mínimos, por lo que inicialmente se realiza un estudio de las arquitecturas hardware para realizar este cálculo y se ha propuesto una nueva arquitectura de menor complejidad. En segundo lugar se ha realizado una comparación de las prestaciones hardware de los diferentes algoritmos con las arquitecturas de referencia: completamente paralela y parcialmente paralela basada en memorias. También se han propuesto dos arquitecturas enfocadas a la alta velocidad, la cuales se implementan con el algoritmo Sum-Product. La primera es una modificación de la arquitectura Sliced Message-Passing que consigue una reducción en el área de la implementación, y la segunda, es una arquitectura específica para el método de actualización propuesto x-shuffled que alcanza tasas de decodificación muy altas. Finalmente, se han implementado los algoritmos propuestos con la arquitectura layered obteniendo implementaciones hardware eficientes con baja área y muy alta tasa de decodificación. Estas últimas consiguen un ratio entre tasa de decodificación y área mejor que las implementaciones existentes en la literatura. Por último, se ha evaluado el comportamiento de los algoritmos de decodificación estudiados en la zona de baja tasa de error, donde las prestaciones se suelen degradar debido a la aparición de un suelo de error. Para ello se ha implementado un simulador hardware usando dispositivos FPGA. La tasa de datos alcanzada con el simulador hardware diseñado es superior a la de otros simuladores documentados en la literatura. En la zona de baja tasa de error el algoritmo propuesto Min-Sum modificado con corrección presenta un mejor comportamiento que el resto de algoritmos evaluados, consiguiendo bajar el suelo de error varios órdenes de magnitud. / Angarita Preciado, FE. (2013). Diseño de decodificadores de altas prestaciones para código LDPC [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/31646

En esta tesis se estudia el dise¿no de decodificadores no-binarios para la correcci'on de errores en sistemas de comunicaci'on modernos de alta velocidad. El objetivo es proponer soluciones de baja complejidad para los algoritmos de decodificaci'on basados en los c'odigos de comprobaci'on de paridad de baja densidad no-binarios (NB-LDPC) y en los c'odigos Reed-Solomon, con la finalidad de implementar arquitecturas hardware eficientes. En la primera parte de la tesis se analizan los cuellos de botella existentes en los algoritmos y en las arquitecturas de decodificadores NB-LDPC y se proponen soluciones de baja complejidad y de alta velocidad basadas en el volteo de s'¿mbolos. En primer lugar, se estudian las soluciones basadas en actualizaci'on por inundaci 'on con el objetivo de obtener la mayor velocidad posible sin tener en cuenta la ganancia de codificaci'on. Se proponen dos decodificadores diferentes basados en clipping y t'ecnicas de bloqueo, sin embargo, la frecuencia m'axima est'a limitada debido a un exceso de cableado. Por este motivo, se exploran algunos m'etodos para reducir los problemas de rutado en c'odigos NB-LDPC. Como soluci'on se propone una arquitectura basada en difusi'on parcial para algoritmos de volteo de s'¿mbolos que mitiga la congesti'on por rutado. Como las soluciones de actualizaci 'on por inundaci'on de mayor velocidad son sub-'optimas desde el punto de vista de capacidad de correci'on, decidimos dise¿nar soluciones para la actualizaci'on serie, con el objetivo de alcanzar una mayor velocidad manteniendo la ganancia de codificaci'on de los algoritmos originales de volteo de s'¿mbolo. Se presentan dos algoritmos y arquitecturas de actualizaci'on serie, reduciendo el 'area y aumentando de la velocidad m'axima alcanzable. Por 'ultimo, se generalizan los algoritmos de volteo de s'¿mbolo y se muestra como algunos casos particulares puede lograr una ganancia de codificaci'on cercana a los algoritmos Min-sum y Min-max con una menor complejidad. Tambi'en se propone una arquitectura eficiente, que muestra que el 'area se reduce a la mitad en comparaci'on con una soluci'on de mapeo directo. En la segunda parte de la tesis, se comparan algoritmos de decodificaci'on Reed- Solomon basados en decisi'on blanda, concluyendo que el algoritmo de baja complejidad Chase (LCC) es la soluci'on m'as eficiente si la alta velocidad es el objetivo principal. Sin embargo, los esquemas LCC se basan en la interpolaci'on, que introduce algunas limitaciones hardware debido a su complejidad. Con el fin de reducir la complejidad sin modificar la capacidad de correcci'on, se propone un esquema de decisi'on blanda para LCC basado en algoritmos de decisi'on dura. Por 'ultimo se dise¿na una arquitectura eficiente para este nuevo esquema / García Herrero, FM. (2013). Architectures for soft-decision decoding of non-binary codes [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/33753 / Premios Extraordinarios de tesis doctorales

This thesis is focused on the design and implementation of binary low-density parity-check (LDPC) code decoders for high-speed modern communication systems. The basic of LDPC codes and the performance and bottlenecks, in terms of complexity and hardware efficiency, of the main soft-decision and hard-decision decoding algorithms (such as Min-Sum, Optimized 2-bit Min-Sum and Reliability-based iterative Majority-Logic) are analyzed. The complexity and performance of those algorithms are improved to allow efficient hardware architectures. A new decoding algorithm called One-Minimum Min-Sum is proposed. It reduces considerably the complexity of the check node update equations of the Min-Sum algorithm. The second minimum is estimated from the first minimum value by a means of a linear approximation that allows a dynamic adjustment. The Optimized 2-bit Min-Sum algorithm is modified to initialize it with the complete LLR values and to introduce the extrinsic information in the messages sent from the variable nodes. Its variable node equation is reformulated to reduce its complexity. Both algorithms were tested for the (2048,1723) RS-based LDPC code and (16129,15372) LDPC code using an FPGA-based hardware emulator. They exhibit BER performance very close to Min-Sum algorithm and do not introduce early error-floor. In order to show the hardware advantages of the proposed algorithms, hardware decoders were implemented in a 90 nm CMOS process and FPGA devices based on two types of architectures: full-parallel and partial-parallel one with horizontal layered schedule. The results show that the decoders are more area-time efficient than other published decoders and that the low-complexity of the Modified Optimized 2-bit Min-Sum allows the implementation of 10 Gbps decoders in current FPGA devices. Finally, a new hard-decision decoding algorithm, the Historical-Extrinsic Reliability-Based Iterative Decoder, is presented. This algorithm introduces the new idea of considering hard-decision votes as soft-decision to compute the extrinsic information of previous iterations. It is suitable for high-rate codes and improves the BER performance of the previous RBI-MLGD algorithms, with similar complexity. / Esta tesis se ha centrado en el diseño e implementación de decodificadores binarios basados en códigos de comprobación de paridad de baja densidad (LDPC) válidos para los sistemas de comunicación modernos de alta velocidad. Los conceptos básicos de códigos LDPC, sus prestaciones y cuellos de botella, en términos de complejidad y eficiencia hardware, fueron analizados para los principales algoritmos de decisión soft y decisión hard (como Min-Sum, Optimized 2-bit Min-Sum y Reliability-based iterative Majority-Logic). La complejidad y prestaciones de estos algoritmos se han mejorado para conseguir arquitecturas hardware eficientes. Se ha propuesto un nuevo algoritmo de decodificación llamado One-Minimum Min-Sum. Éste reduce considerablemente la complejidad de las ecuaciones de actualización del nodo de comprobación del algoritmo Min-Sum. El segundo mínimo se ha estimado a partir del valor del primer mínimo por medio de una aproximación lineal, la cuál permite un ajuste dinámico. El algoritmo Optimized 2-bit Min-Sum se ha modificado para ser inicializado con los valores LLR e introducir la información extrínseca en los mensajes enviados desde los nodos variables. La ecuación del nodo variable de este algoritmo ha sido reformulada para reducir su complejidad. Ambos algoritmos fueron probados para el código (2048,1723) RS-based LDPC y para el código (16129,15372) LDPC utilizando un emulador hardware implementado en un dispositivo FPGA. Éstos han alcanzado unas prestaciones de BER muy cercanas a las del algoritmo Min-Sum evitando, además, la aparición temprana del fenómeno denominado suelo del error. Con el objetivo de mostrar las ventajas hardware de los algoritmos propuestos, los decodificadores se implementaron en hardware utilizando tecnología CMOS de 90 nm y en dispositivos FPGA basados en dos tipos de arquitecturas: completamente paralela y parcialmente paralela utilizando el método de actualización por capas horizontales. Los resultados muestran que los decodificadores propuestos e implementados son más eficientes en área-tiempo que otros decodificadores publicados y que la baja complejidad del algoritmo Modified Optimized 2-bit Min-Sum permite la implementación de decodificadores en los dispositivos FPGA actuales consiguiendo una tasa de 10 Gbps. Finalmente, se ha presentado un nuevo algoritmo de decodificación de decisión hard, el Historical-Extrinsic Reliability-Based Iterative Decoder. Este algoritmo introduce la nueva idea de considerar los votos de decisión hard como decisión soft para calcular la información extrínseca de iteracions anteriores. Este algoritmo es adecuado para códigos de alta velocidad y mejora el rendimiento BER de los algoritmos RBI-MLGD anteriores, con una complejidad similar. / Aquesta tesi s'ha centrat en el disseny i implementació de descodificadors binaris basats en codis de comprovació de paritat de baixa densitat (LDPC) vàlids per als sistemes de comunicació moderns d'alta velocitat. Els conceptes bàsics de codis LDPC, les seues prestacions i colls de botella, en termes de complexitat i eficiència hardware, van ser analitzats pels principals algoritmes de decisió soft i decisió hard (com el Min-Sum, Optimized 2-bit Min-Sum y Reliability-based iterative Majority-Logic). La complexitat i prestacions d'aquests algoritmes s'han millorat per aconseguir arquitectures hardware eficients. S'ha proposat un nou algoritme de descodificació anomenat One-Minimum Min-Sum. Aquest redueix considerablement la complexitat de les equacions d'actualització del node de comprovació del algoritme Min-Sum. El segon mínim s'ha estimat a partir del valor del primer mínim per mitjà d'una aproximació lineal, la qual permet un ajust dinàmic. L'algoritme Optimized 2-bit Min-Sum s'ha modificat per ser inicialitzat amb els valors LLR i introduir la informació extrínseca en els missatges enviats des dels nodes variables. L'equació del node variable d'aquest algoritme ha sigut reformulada per reduir la seva complexitat. Tots dos algoritmes van ser provats per al codi (2048,1723) RS-based LDPC i per al codi (16129,15372) LDPC utilitzant un emulador hardware implementat en un dispositiu FPGA. Aquests han aconseguit unes prestacions BER molt properes a les del algoritme Min-Sum evitant, a més, l'aparició primerenca del fenomen denominat sòl de l'error. Per tal de mostrar els avantatges hardware dels algoritmes proposats, els descodificadors es varen implementar en hardware utilitzan una tecnologia CMOS d'uns 90 nm i en dispositius FPGA basats en dos tipus d'arquitectures: completament paral·lela i parcialment paral·lela utilitzant el mètode d'actualització per capes horitzontals. Els resultats mostren que els descodificadors proposats i implementats són més eficients en àrea-temps que altres descodificadors publicats i que la baixa complexitat del algoritme Modified Optimized 2-bit Min-Sum permet la implementació de decodificadors en els dispositius FPGA actuals obtenint una taxa de 10 Gbps. Finalment, s'ha presentat un nou algoritme de descodificació de decisió hard, el Historical-Extrinsic Reliability-Based Iterative Decoder. Aquest algoritme presenta la nova idea de considerar els vots de decisió hard com decisió soft per calcular la informació extrínseca d'iteracions anteriors. Aquest algoritme és adequat per als codis d'alta taxa i millora el rendiment BER dels algoritmes RBI-MLGD anteriors, amb una complexitat similar. / Català Pérez, JM. (2017). Design and implementation of decoders for error correction in high-speed communication systems [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/86152

Dans cette thèse, nous nous sommes intéressés au problème de codage de sources avec information adjacente au décodeur seulement. Plus précisément, nous avons considéré le cas où la distribution jointe entre la source et l'information adjacente n'est pas bien connue. Dans ce contexte, pour un problème de codage sans pertes, nous avons d'abord effectué une analyse de performance à l'aide d'outils de la théorie de l'information. Nous avons ensuite proposé un schéma de codage pratique efficace malgré le manque de connaissance sur la distribution de probabilité jointe. Ce schéma de codage s'appuie sur des codes LDPC non-binaires et sur un algorithme de type Espérance-Maximisation. Le problème du schéma de codage proposé, c'est que les codes LDPC non-binaires utilisés doivent être performants. C'est à dire qu'ils doivent être construits à partir de distributions de degrés qui permettent d'atteindre un débit proche des performances théoriques. Nous avons donc proposé une méthode d'optimisation des distributions de degrés des codes LDPC. Enfin, nous nous sommes intéressés à un cas de codage avec pertes. Nous avons supposé que le modèle de corrélation entre la source et l'information adjacente était décrit par un modèle de Markov caché à émissions Gaussiennes. Pour ce modèle, nous avons également effectué une analyse de performance, puis nous avons proposé un schéma de codage pratique. Ce schéma de codage s'appuie sur des codes LDPC non-binaires et sur une reconstruction MMSE. Ces deux composantes exploitent la structure avec mémoire du modèle de Markov caché. / In this thesis, we considered the problem of source coding with side information available at the decoder only. More in details, we considered the case where the joint distribution between the source and the side information is not perfectly known. In this context, we performed a performance analysis of the lossless source coding scheme. This performance analysis was realized from information theory tools. Then, we proposed a practical coding scheme able to deal with the uncertainty on the joint probability distribution. This coding scheme is based on non-binary LDPC codes and on an Expectation-Maximization algorithm. For this problem, a key issue is to design efficient LDPC codes. In particular, good code degree distributions have to be selected. Consequently, we proposed an optimization method for the selection of good degree distributions. To finish, we considered a lossy coding scheme. In this case, we assumed that the correlation channel between the source and the side information is described by a Hidden Markov Model with Gaussian emissions. For this model, we performed again some performance analysis and proposed a practical coding scheme. The proposed scheme is based on non-binary LDPC codes and on MMSE reconstruction using an MCMC method. In our solution, these two components are able to exploit the memory induced by the Hidden Markov model.

Depuis deux décennies, la révolution technologique est avant tout numérique entrainant une forte croissance de la quantité de données à stocker. Le rythme de cette croissance est trop importante pour les solutions de stockage matérielles, provoquant une augmentation du coût de l'octet. Il est donc nécessaire d'apporter une amélioration des solutions de stockage ce qui passera par une augmentation de la taille des réseaux et par la diminution des copies de sauvegarde dans les centres de stockage de données. L'objet de cette thèse est d'étudier l'utilisation des codes en graphe dans les réseaux de stockage de donnée. Nous proposons un nouvel algorithme combinant construction de codes en graphe et allocation des noeuds de ce code sur le réseau. Cet algorithme permet d'atteindre les hautes performances des codes MDS en termes de rapport entre le nombre de disques de parité et le nombre de défaillances simultanées pouvant être corrigées sans pertes (noté R). Il bénéficie également des propriétés de faible complexité des codes en graphe pour l'encodage et la reconstruction des données. De plus, nous présentons une étude des codes LDPC Spatiallement-Couplés permettant d'anticiper le comportement de leur décodage pour les applications de stockage de données.Il est généralement nécessaire de faire des compromis entre différents paramètres lors du choix du code correcteur d'effacement. Afin que ce choix se fasse avec un maximum de connaissances, nous avons réalisé deux études théoriques comparatives pour compléter l'état de l'art. La première étude s'intéresse à la complexité de la mise à jour des données dans un réseau dynamique établi et déterminons si les codes linéaires utilisés ont une complexité de mise à jour optimale. Dans notre seconde étude, nous nous sommes intéressés à l'impact sur la charge du réseau de la modification des paramètres du code correcteur utilisé. Cette opération peut être réalisée lors d'un changement du statut du fichier (passage d'un caractère hot à cold par exemple) ou lors de la modification de la taille du réseau. L'ensemble de ces études, associé au nouvel algorithme de construction et d'allocation des codes en graphe, pourrait mener à la construction de réseaux de stockage dynamiques, flexibles avec des algorithmes d'encodage et de décodage peu complexes. / For two decades, the numerical revolution has been amplified. The spread of digital solutions associated with the improvement of the quality of these products tends to create a growth of the amount of data stored. The cost per Byte reveals that the evolution of hardware storage solutions cannot follow this expansion. Therefore, data storage solutions need deep improvement. This is feasible by increasing the storage network size and by reducing data duplication in the data center. In this thesis, we introduce a new algorithm that combines sparse graph code construction and node allocation. This algorithm may achieve the highest performance of MDS codes in terms of the ratio R between the number of parity disks and the number of failures that can be simultaneously reconstructed. In addition, encoding and decoding with sparse graph codes helps lower the complexity. By this algorithm, we allow to generalize coding in the data center, in order to reduce the amount of copies of original data. We also study Spatially-Coupled LDPC (SC-LDPC) codes which are known to have optimal asymptotic performance over the binary erasure channel, to anticipate the behavior of these codes decoding for distributed storage applications. It is usually necessary to compromise between different parameters for a distributed storage system. To complete the state of the art, we include two theoretical studies. The first study deals with the computation complexity of data update and we determine whether linear code used for data storage are update efficient or not. In the second study, we examine the impact on the network load when the code parameters are changed. This can be done when the file status changes (from a hot status to a cold status for example) or when the size of the network is modified by adding disks. All these studies, combined with the new algorithm for sparse graph codes, could lead to the construction of new flexible and dynamical networks with low encoding and decoding complexities.

Submitted by Carmen Torres (carmensct@globo.com) on 2018-02-09T18:11:30Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_MapeamentoBitsAdaptacao.pdf: 986310 bytes, checksum: 6e1b30f6ca34fc67df43f3141680c73a (MD5) / Approved for entry into archive by Edisangela Bastos (edisangela@ufpa.br) on 2018-02-16T16:12:49Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_MapeamentoBitsAdaptacao.pdf: 986310 bytes, checksum: 6e1b30f6ca34fc67df43f3141680c73a (MD5) / Made available in DSpace on 2018-02-16T16:12:49Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_MapeamentoBitsAdaptacao.pdf: 986310 bytes, checksum: 6e1b30f6ca34fc67df43f3141680c73a (MD5) Previous issue date: 2017-09-29 / CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico / Os codigos com matriz de vericação de paridade de baixa densidade (LDPC) tem sido adotados como estrategia de correção de erros em diversos padrões de sistemas de comunicação, como nos sistemas G.hn (padrão que unifica as redes domesticas) e IEEE 802.11n (padrão para redes sem o locais). Nestes sistemas com modulação de amplitude em quadratura (QAM) codicados com LDPC, mapear propriamente os bits codificados para os diferentes sub-canais, considerando o fato de os sub-canais terem diferentes qualidades, garante uma melhora no desempenho geral do sistema. Nesse sentido, esta Tese apresenta uma nova técnica de mapeamento de bits, baseada na suposição de que bits transmitidos em sub-canais \bons" ajudam bits transmitidos em sub-canais \ruins". Isto e possível através de algumas restrições impostas ao grafo de Tanner associado, semelhantes aos códigos Root-LDPC. A otimização deste mapeamento de bits utilizando curvas de transferência de informação extrínseca (EXIT charts) também e apresentada. Observa-se que esse mapeamento tem a vantagem de um espaço de busca de otimização reduzido quando aplicado ao sistema com modo de transmissão de portadora única. Além disso, em situações nas quais o espaço de busca não e tão reduzido, como em aplicações baseadas em multiplexação por divisão de frequência ortogonal (OFDM), chegou-se a uma simples regra pratica associada as restrições do mapeamento de bits que praticamente elimina a necessidade de uma otimização. Por fim, um estudo do impacto do nível de desequilíbrio de contabilidade através dos sub-canais sobre o desempenho do mapeamento de bits e apresentado. Os resultados das simulações mostram que a estratégia de mapeamento de bits melhora o desempenho do sistema, e que, na presença de variações do canal, o sistema pode, adaptativamente, aplicar um novo mapeamento de bits sem a necessidade de recorrer a uma otimização complexa, podendo ser muito útil em sistemas práticos. / Low-Density parity-check (LDPC) codes are being adopted as the error correction strategy in di erent system standards, such as the G.hn (home networking standard) and the IEEE 802.11n (wireless local standard). In these LDPC-coded quadrature amplitude modulation (QAM) systems, mapping the LDPC coded bits properly to the di erent sub-channels considering the fact that sub-channels have di erent qualities ensures an improved overall system performance. Accordingly, this thesis presents a new bit mapping technique based on the assumption that bits transmitted in \good" sub-channels, help bits transmitted in \bad" sub-channels. This can be made possible through some restrictions to be imposed on the associated Tanner graph, akin to Root-LDPC codes. An optimization of the root-like bit mapping through extrinsic information transfer (EXIT) charts analysis is also presented. We show that this mapping has the advantage of a reduced optimization search space when applied to single-carrier based systems. Moreover, in situations where the search space is not só reduced, such as in orthogonal frequency division multiplexing (OFDM)-based applications, we arrive at a rule of thumb associated with the bit mapping constraints that practically eliminates the need for an optimization. Finally, a study of the impact of the level of reliability imbalance across the sub-channels on the performance of the root-like bit mapping is presented. Simulation results show that the new bit mapping strategy improves performance, and that in the presence of channel variations, the system can, adaptively, apply a new bit mapping without the need of a complex optimization, which can be very useful in practical systems.

In this effort, we consider the performance of a dedicated short range communication (DSRC) system for inter-vehicle communications (IVC). The DSRC standard employs convolutional codes for forward error correction (FEC). The performance of the DSRC system is evaluated in three different channels with convolutional codes, regular low density parity check (LDPC) codes and quasi-cyclic (QC) LDPC codes. In addition, we compare the complexity of these codes. It is shown that LDPC and QC-LDPC codes provide a significant improvement in performance compared to convolutional codes. / Graduate

[pt] Os códigos IRA (Irregular Repeat-Accumulate) são uma classe de códigos criada com o objetivo de permitir codificação em tempo linear garantindo comunicação robusta a taxas próximas à capacidade do canal. Eles foram introduzidas por Jin, Khandekar and McEliece em 2000. O artigo no qual foram apresentados provou que os códigos IRA alcançavam a capacidade do canal de apagamento e mostravam desempenho cmparável ao dos códigos Turbo no canal AWGN (Additive White Gaussian Noise). Os desenvolvimentos teóricos por trás dos códigos IRA vieram da busca pelos primeiros códigos LDPC (Low Density Parity Check), ou códigos em grafos, que atingiriam a capacidade do canal AWGN. Os códigos LDPC - propostos originalmente por Robert Gallager em 1963 - se tornaram objeto de grande interesse nas últimas décadas após um longo período de ostracismo desde sua concepção, desenvolvendo seu potencial para codificação de canal em aplicações tão diversas quanto comunicações por satélite, redes sem fio e streaming via IP, bem como codificação distribuída de fonte. O objetivo desta dissertação é a avaliação dos códigos IRA e os efeitos de diferentes métodos de construção de grafos em seu desempenho. O uso das muitas variações do algoritmo PEG (Progressive Edge-Growth) foi testado em simulações no canal AWGN. / [en] Irregular Repeat-Accumulate codes are motivated by the challenge of providing a class of codes that use linear-time encoding and decoding while communicating reliably at rates close to channel capacity. They were introduced by Hui Jin, Khandekar and McEliece in 2000, their article proves that IRA codes achieve channel capacity for the binary erasure channel and exhibit remarkably good performance on the AWGN channel. The theoretical developments supporting IRA codes stem from the efforts ar the development of capacity achieving Low-Density Parity-Check codes. LDPC codes were first proposed by Robert Gallager in 1963 and became the subject of intense research during the past decade after being dormant for a long period since its conception. Efforts by many researchers have developed its potential for channel coding in applications as diverse as satellite communications, wireless networks and streaming over IP, as well as studies on its usage in Distributed Source Coding. The goal of this dissertation is the evaluation of IRA codes and the effects of different graph construction methods in its performance. The use of the many variations of the Progressive Edge-Growth algorithm with IRA codes was tested in simulations on the AWGN channel.

Les standards « Long-term evolution » (LTE) et LTE-Advanced (LTE-A) devraient influencer fortement l’avenir de la cinquième génération (5G) des réseaux mobiles. Ces normes exigent de hauts débits de données et une qualité de service de très bon niveau, ce qui permet d’assurer un faible taux d’erreur, avec une faible latence. Par ailleurs, la complexité doit être limitée. Dans le but de déterminer des solutions technologiques modernes qui satisfont ces contraintes fortes, nous étudions dans la thèse des systèmes de communication sans fil MIMO codés. D’abord, nous imposons un simple code convolutif récursif systématique (RSC) pour limiter la complexité et la latence. En considérant des récepteurs itératifs, nous optimisons alors la performance en termes de taux d’erreur de ces systèmes en définissant un précodage linéaire MIMO et des techniques de mapping appropriées. Dans la deuxième partie de la thèse, nous remplaçons le RSC par un LDPC non-binaire (NB-LDPC). Nous proposons d’utiliser les techniques de précodage MIMO afin de réduire la complexité des récepteurs des systèmes MIMO intégrant des codes NB-LDPC. Enfin, nous proposons également un nouvel algorithme de décodage itératif à faible complexité adapté aux codes NB-LDPC. / The long-term evolution (LTE) and the LTE-Advanced (LTE-A) standardizations are predicted to play essential roles in the future fifth-generation (5G) mobile networks. These standardizations require high data rate and high quality of service, which assures low error-rate and low latency. Besides, as discussed in the recent surveys, low complexity communication systems are also essential in the next 5G mobile networks. To adapt to the modern trend of technology, in this PhD thesis, we investigate the multiple-input multiple-output (MIMO) wireless communication schemes. In the first part of this thesis, low-complex forward error correction (FEC) codes are used for low complexity and latency. By considering iterative receivers at the receiver side, we exploit MIMO linear precoding and mapping methods to optimize the error-rate performance of these systems. In the second part of this thesis, non-binary low density parity check (NB-LDPC) codes are investigated. We propose to use MIMO precoders to reduce the complexity for NB-LDPC encoded MIMO systems. A novel low complexity decoding algorithm for NB-LDPC codes is also proposed at the end of this thesis.

The aim of the dissertation was to design a realistic, low-complexity non-binary (NB) low density parity check (LDPC) coded space-time-frequency (STF) coded multiple-input multiple-output (MIMO) orthogonal frequency division multiplexing (OFDM) system with an iterative joint decoder and detector structure at the receiver. The goal of the first part of the dissertation was to compare the performance of different design procedures for NB-LDPC codes on an additive white Gaussian noise (AWGN) channel, taking into account the constraint on the code length. The effect of quantisation on the performance of the code was also analysed. Different methods for choosing the NB elements in the parity check matrix were compared. For the STF coding, a class of universal STF codes was used. These codes use linear pre-coding and a layering approach based on Diophantine numbers to achieve full diversity and a transmission rate (in symbols per channel use per frequency) equal to the number of transmitter antennas. The study of the system considers a comparative performance analysis of di erent ST, SF and STF codes. The simulations of the system were performed on a triply selective block fading channel. Thus, there was selectivity in the fading over time, space and frequency. The effect of quantisation at the receiver on the achievable diversity of linearly pre-coded systems (such as the STF codes used) was mathematically derived and verified with simulations. A sphere decoder (SD) was used as a MIMO detector. The standard method used to create a soft-input soft output (SISO) SD uses a hard-to-soft process and the max-log-map approximation. A new approach was developed which combines a Hopfield network with the SD. This SD-Hopfield detector was connected with the fast Fourier transform belief propagation (FFT-BP) algorithm in an iterative structure. This iterative system was able to achieve the same bit error rate (BER) performance as the original SISO-SD at a reduced complexity. The use of the iterative Hopfield-SD and FFT-BP decoder system also allows performance to be traded off for complexity by varying the number of decoding iterations. The complete system employs a NB-LDPC code concatenated with an STF code at the transmitter with a SISO-SD and FFT-BP decoder connected in an iterative structure at the receiver. The system was analysed in varying channel conditions taking into account the effect of correlation and quantisation. The performance of different SF and STF codes were compared and analysed in the system. An analysis comparing different numbers of FFT-BP and outer iterations was also done. AFRIKAANS : Die doel van die verhandeling was om ’n realistiese, lae-kompleksiteit nie-binˆere (NB) LDPC gekodeerde ruimte-tyd-frekwensie-gekodeerde MIMO-OFDM-sisteem met iteratiewe gesamentlike dekodeerder- en detektorstrukture by die ontvanger te ontwerp. Die eerstem deel van die verhandeling was om die werkverrigting van verskillende ontwerpprosedures vir NB-LDPC kodes op ’n gesommeerde wit Gausruiskanaal te vergelyk met inagneming van die beperking op die lengte van die kode. Verskillende metodes om die nie-bineêre elemente in die pariteitstoetsmatriks te kies, is gebruik. Vir die ruimte-tyd-frekwensiekodering is ’n klas universele ruimte-tyd-frekwensiekodes gebruik. Hierdie kodes gebruik lineêre pre-kodering en ’n laagbenadering gebaseer op Diofantiese syfers om volle diversiteit te bereik en ’n oordragtempo (in simbole per kanaalgebruik per frekwensie) gelyk aan die aantal senderantennes. Die studie van die sisteem oorweeg ’n vergelykende werkverrigtinganalisie van verskillende ruimte-tyd-, ruimte-freksensie- en ruimte-tyd-frekwensiekodes. Die simulasies van die sisteem is gedoen op ’n drievoudig selektiewe blokwegsterwingskanaal. Daar was dus selektiwiteit in die wegsterwing oor tyd, ruimte en frekwensie. Die effek van kwantisering by die ontvanger op die bereikbare diversiteit van lineêr pre-gekodeerde sisteme (soos die ruimte-tyd-frekwensiekodes wat gebruik is) is matematies afgelei en bevestig deur simulasies. ’n Sfeerdekodeerder (SD) is gebruik as ’n MIMO-detektor. Die standaardmetode wat gebuik is om ’n sagte-inset-sagte-uitset (SISO) SD te skep, gebruik ’n harde-na-sagte proses en die maksimum logaritmiese afbeelding-benadering. ’n Nuwe benadering wat ’n Hopfield-netwerk met die SD kombineer, is ontwikkel. Hierdie SD-Hopfield-detektor is verbind met die FFT-BP-algoritme in iteratiewe strukture. Hierdie iteratiewe sisteem was in staat om dieselfde bisfouttempo te bereik as die oorspronklike SISO-SD, met laer kompleksiteit. Die gebruik van die iteratiewe Hopfield-SD en FFT-BP-dekodeerdersisteem maak ook daarvoor voorsiening dat werkverrigting opgeweeg kan word teen kompleksiteit deur die aantal dekodering-iterasies te varieer. Die volledige sisteem maak gebruik van ’n QC-NB-LDPC-kode wat met ’n ruimte-tyd-frekwensiekode by die sender aaneengeskakel is met ’n SISO-SD en FFT-BP-dekodeerder wat in ’n iteratiewe struktuur by die ontvanger gekoppel is. Die sisteem is onder ’n verskeidenheid kanaalkondisies ge-analiseer met inagneming van die effek van korrelasie en kwantisering. Die werkverrigting van verskillende ruimte-frekwensie- en ruimte-tyd-frekwensiekodes is vergelyk en in die sisteem ge-analiseer. ’n Analise om ’n wisselende aantal FFT-BP en buite-iterasies te vergelyk, is ook gedoen. Copyright / Dissertation (MEng)--University of Pretoria, 2010. / Electrical, Electronic and Computer Engineering / unrestricted