Les techniques de décodage itératif pour les codes modernes dominent actuellement le choix pour la correction des erreurs dans un grand nombre d'applications. Les Turbo codes, présentés en 1993, ont déclenché une révolution dans le domaine du codage de canal parce que ils permettent de s'approcher de la limite de Shannon. Ensuite, les codes LDPC (low-density parity-check) ont été redécouverts. Ces codes sont actuellement omniprésents dans le contexte des communications mobiles sans fil, mais aussi dans d'autres domaines d'application. Dans cette thèse, l'accent est mis sur la conception de décodeurs VLSI à basse consommation destinés aux communications sans fil. Les dispositifs nomades sont généralement alimentés par des batteries et ils ont besoin d'une bonne efficacité énergétique et d'une haute performance, le tout dans une surface de silicium minimale. En outre, les décodeurs de canal sont généralement responsables d'une part importante de la consommation d'énergie dans la chaîne de traitement en bande de base d'un récepteur sans fil. Nous nous concentrons sur les décodeurs LDPC. Au niveau algorithmique nous étudions les compromis entre la performance, l'efficacité énergétique et la surface de silicium pour les différents algorithmes de décodage. Au niveau de l'architecture nous étudions le point essentiel des mémoires. Ce point est particulièrement important pour la consommation et la surface finale du décodeur. Enfin, au niveau du système, nous proposons des stratégies pour la gestion dynamique de la puissance pour les décodeurs Turbo et LDPC. Ces stratégies sont basées sur la prédiction et le contrôle dynamique du nombre d'itérations de décodage.

<p>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.</p><p>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.</p><p>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.</p>

We present novel architectures for parallel-node low-density parity-check convolutional code (PN-LDPC-CC) encoders and decoders. Based on a recently introduced implementation-aware class of LDPC-CCs, these encoders and decoders take advantage of increased node-parallelization to simultaneously decrease the energy-per-bit and increase the decoded information throughput. A series of progressively improved encoder and decoder designs are presented and characterized using synthesis results with respect to power, area and throughput. The best of the encoder and decoder designs significantly advance the state-of-the-art in terms of both the energy-per-bit and throughput/area metrics. One of the presented decoders, for an Eb /N0 of 2.5 dB has a bit-error-rate of 106, takes 4.5 mm2 in a CMOS 90-nm process, and achieves an energy-per-decoded-information-bit of 65 pJ and a decoded information throughput of 4.8 Gbits/s. We implement an earlier non-parallel node LDPC-CC encoder, decoder and a channel emulator in silicon. We provide readers, via two sets of tables, the ability to look up our decoder hardware metrics, across four different process technologies, for over 1000 variations of our PN-LDPC-CC decoders. By imposing practical decoder implementation constraints on power or area, which in turn drives trade-offs in code size versus the number of decoder processors, we compare the code BER performance. An extensive comparison to known LDPC-BC/CC decoder implementations is provided.

Design and analysis of random-like codes for various multiple-input and multiple-output communication systems are addressed in this work. Random-like codes have drawn significant interest because they offer capacity-achieving performance. We first consider the analysis and design of low-density parity-check (LDPC) codes for turbo multiuser detection in multipath CDMA channels. We develop techniques for computing the probability density function (pdf) of the extrinsic messages at the output of the soft-input soft-output (SISO) multiuser detectors as a function of the pdf of input extrinsic messages, user spreading codes, channel impulse responses, and signal-to-noise ratios. Using these techniques, we are able to accurately compute the thresholds for LDPC codes and design good irregular LDPC codes. We then apply the tools of density evolution with mixture Gaussian approximations to optimize irregular LDPC codes and to compute minimum operational signal-to-noise ratios for ergodic MIMO OFDM channels. In particular, the optimization is done for various MIMO OFDM system configurations which include different number of antennas, different channel models and different demodulation schemes. We also study the coding-spreading tradeoff in LDPC coded CDMA systems employing multiuser joint decoding. We solve the coding-spreading optimization based on the extrinsic information SNR evolution curves for the SISO multiuser detectors and the SISO LDPC decoders. Both single-cell and multi-cell scenarios will be considered. For each of these cases, we will characterize the extrinsic information for both finite-size systems and the so-called large systems where asymptotic performance results must be evoked. Finally, we consider the design optimization of irregular repeat accumulate (IRA) codes for MIMO communication systems employing iterative receivers. We present the density evolution-based procedure with Gaussian approximation for optimizing the IRA code ensemble. We adopt an approximation method based on linear programming to design an IRA code with the extrinsic information transfer (EXIT) chart matched to that of the soft MIMO demodulator.

This thesis presents a novel VLSI design of multi-code rate Low-Density Parity-Check code (LDPC) decoder for IEEE 802.16e standard. In order to support the different code rates adopted by the standard, this thesis proposes a programmable LDPC decoder architecture based on the edge-serial approach. This edge-serial architecture can perform the sequential check-node computation according to the internal sequence update commands. Any complex and irregular parity-check matrix can all be realized in the proposed architecture if the number of bit-nodes each check node connects does not exceed a certain bound. In addition to the high flexibility, this thesis also proposes several design optimization techniques suitable for the LDPC decoder. First, the designs of the LDPC decoders in the past all put more emphasis on the realization of check node function. This thesis instead applies a novel bit-node major approach which can lead to more compact design. Secondly, a fine-grain message update method is used which allows more rapid message passing such that the decoder can converge in less cycles. In addition, almost half of the message memory can be reduced. Furthermore, based on the bit-node major decoder design, the early termination scheme can be utilized to partially terminate the function of some bit nodes to reduce the decoding cycles. The other salient features also include the rescheduling of the message update order to allow the overlap of different decoding iterations in order to reduce effect of the possible message update hazard due to the long internal pipeline latency. Based on the proposed optimization methods, our experimental results show that the hardware cost can be reduced by 23.1% while the decoding cycles can be reduced by 27.4%. The proposed LDPC decoder architecture has been realized by using 0.18 &#x00B5;m technology with the total gate count of 316k. Our experimental shows that the proposed LDPC decoder can run up to 235 MHz and deliver the average of 116 Mbps throughput.

Cette thèse se consacre à l'étude de décodeurs itératifs, pour des codes correcteurd'erreurs binaires et non-binaires à faible densité (LDPC). Notre objectif est de modéliserdes décodeurs de complexité faibles et de faible latence tout en garantissantde bonne performances dans la région des très faibles taux d'erreur (error floor).Dans la première partie de cette thèse, nous étudions des décodeurs itératifssur des alphabets finis (Finite Alphabet iterative decoders, FAIDs) qui ont étérécemment proposés dans la littérature. En utilisant un grand nombre de décodeursFAIDs, nous proposons un nouvel algorithme de décodage qui améliore la capacité decorrections d'erreur des codes LDPC de degré dv = 3 sur canal binaire symétrique.La diversité des décodeurs permet de garantir une correction d'erreur minimale sousdécodage itératif, au-delà de la pseudo-distance des codes LDPC. Nous donnonsdans cette thèse un exemple detailé d'un ensemble de décodeur FAIDs, qui corrigetous les évènements d'erreur de poids inférieur ou égal à 7 avec un LDPC de petitetaille (N=155,K=64,Dmin=20). Cette approche permet de corriger des évènementsd'erreur que les décodeurs traditionnels (BP, min-sum) ne parviennent pas à corriger.Enfin, nous interprétons les décodeurs FAIDs comme des systèmes dynamiques etnous analysons les comportements de ces décodeurs sur des évènements d'erreur lesplus problématiques. En nous basant sur l'observation des trajectoires périodiquespour ces cas d'étude, nous proposons un algorithme qui combine la diversité dudécodage avec des sauts aléatoires dans l'espace d'état du décodeur itératif. Nousmontrons par simulations que cette technique permet de s'approcher des performancesd'un décodage optimal au sens du maximum de vraisemblance, et ce pourplusieurs codes.Dans la deuxième partie de cette thèse, nous proposons un nouvel algorithmede décodage à complexité réduite pour les codes LDPC non-binaires. Nous avonsappellé cet algorithme Trellis-Extended Min-Sum (T-EMS). En transformant le domainede message en un domaine appelée domaine delta, nous sommes capable dechoisir les déviations ligne par ligne par rapport à la configuration la plus fiable,tandis que les décodeurs habituels comme le décodeur EMS choisissent les déviationscolonne par colonne. Cette technique de sélection des déviations ligne parligne nous permet de réduire la complexité du décodage sans perte de performancepar rapport aux approches du type EMS. Nous proposons également d'ajouter une colonne supplémentaire à la représentation en treillis des messages, ce qui résoudle problème de latence des décodeurs existants. La colonne supplémentaire permetde calculer tous les messages extrinséque en parallèle, avec une implémentationmatérielle dédiée. Nous présentons dans ce manuscrit, aussi bien les architecturesmatérielles parallèle que les architectures matérielles série pour l'exécution de notrealgorithme T-EMS. L'analyse de la complexité montre que l'approche T-EMS estparticulièrement adapté pour les codes LDPC non-binaires sur des corps finis deGalois de petite et moyenne dimensions.

L'utilisation d'algorithmes itératifs est aujourd'hui largement répandue dans tous les domaines du traitement du signal et des communications numériques. Dans les systèmes de communications modernes, les algorithmes itératifs sont utilisés dans le décodage des codes ''low-density parity-check'' (LDPC), qui sont une classe de codes correcteurs d'erreurs utilisés pour leurs performances exceptionnelles en terme de taux d'erreur. Dans un domaine plus récent qu'est le ''compressed sensing'', les algorithmes itératifs sont utilisés comme méthode de reconstruction afin de recouvrer un signal ''sparse'' à partir d'un ensemble d'équations linéaires, appelées observations. Cette thèse traite principalement du développement d'algorithmes itératifs à faible complexité pour les deux domaines mentionnés précédemment, à savoir le design d'algorithmes de décodage à faible complexité pour les codes LDPC, et le développement et l'analyse d'un algorithme de reconstruction à faible complexité, appelé ''Interval-Passing Algorithm (IPA)'', dans le cadre du ''compressed sensing''.Dans la première partie de cette thèse, nous traitons le cas des algorithmes de décodage des codes LDPC. Il est maintenu bien connu que les codes LDPC présentent un phénomène dit de ''plancher d'erreur'' en raison des échecs de décodage des algorithmes de décodage traditionnels du types propagation de croyances, et ce en dépit de leurs excellentes performances de décodage. Récemment, une nouvelle classe de décodeurs à faible complexité, appelés ''finite alphabet iterative decoders (FAIDs)'' ayant de meilleures performances dans la zone de plancher d'erreur, a été proposée. Dans ce manuscrit nous nous concentrons sur le problème de la sélection de bons décodeurs FAID pour le cas de codes LDPC ayant un poids colonne de 3 et le cas du canal binaire symétrique. Les méthodes traditionnelles pour la sélection des décodeurs s'appuient sur des techniques asymptotiques telles que l'évolution de densité, mais qui ne garantit en rien de bonnes performances sur un code de longueurs finies surtout dans la région de plancher d'erreur. C'est pourquoi nous proposons ici une méthode de sélection qui se base sur la connaissance des topologies néfastes au décodage pouvant être présente dans un code en utilisant le concept de ''trapping sets bruités''. Des résultats de simulation sur différents codes montrent que les décodeurs FAID sélectionnés grâce à cette méthode présentent de meilleures performance dans la zone de plancher d'erreur comparé au décodeur à propagation de croyances.Dans un second temps, nous traitons le sujet des algorithmes de reconstruction itératifs pour le compressed sensing. Des algorithmes itératifs ont été proposés pour ce domaine afin de réduire la complexité induite de la reconstruction par ''linear programming''. Dans cette thèse nous avons modifié et analysé un algorithme de reconstruction à faible complexité dénommé IPA utilisant les matrices creuses comme matrices de mesures. Parallèlement aux travaux réalisés dans la littérature dans la théorie du codage, nous analysons les échecs de reconstruction de l'IPA et établissons le lien entre les ''stopping sets'' de la représentation binaire des matrices de mesure creuses. Les performances de l'IPA en font un bon compromis entre la complexité de la reconstruction sous contrainte de minimisation de la norme $ell_1$ et le très simple algorithme dit de vérification.

Near lossless source coding with side information only at the decoder, was first considered by Slepian and Wolf in 1970s, and rediscovered recently due to applications such as sensor network and distributed video coding. Suppose X is a source and Y is the side information. The coding scheme proposed by Slepian and Wolf, called SW coding, in which information only flows from the encoder to the decoder, was shown to achieve the rate H(X|Y) asymptotically for stationary ergodic source pairs, but not for non-ergodic case, shown by Yang and He. Recently, a new source coding paradigm called interactive encoding and decoding(IED) was proposed for near lossless coding with side information only at the decoder, where information flows in both ways, from the encoder to the decoder and vice verse. The results by Yang and He show that IED schemes are much more appealing than SW coding schemes to applications where the interaction between the encoder and the decoder is possible. However, the IED schemes proposed by Yang and He do not have an intrinsic structure that is amenable to design and implement in practice. Towards practical design, we restrict the encoding method to linear block codes, resulting in linear IED schemes. It is then shown that this restriction will not undermine the asymptotical performance of IED. Another step of practical design of IED schemes is to make the computational complexity incurred by encoding and decoding feasible. In the framework of linear IED, a scheme can be conveniently described by parity check matrices. Then we get an interesting trade-off between the density of the associated parity check matrices and the resulting symbol error probability. To implement the idea of linear IED and follow the instinct provided by the result above, Low Density Parity Check(LDPC) codes and Belief Propagation(BP) decoding are utilized. A successive LDPC code is proposed, and a new BP decoding algorithm is proposed, which applies to the case where the correlation between $Y$ and $X$ can be modeled as a finite state channel. Finally, simulation results show that linear IED schemes are indeed superior to SW coding schemes.

As one of the most powerful error-correcting codes, Low-density parity check codes are widely used in digital communications. Because of the performance of LDPC codes are capable to close the shannon limited extraordinarily, LDPC codes are to be used in the new Digital Video Broadcast-Satellite-Second Generation(DVB-S2) and it is the first time that LDPC codes are included in the broadcast standard in 2003. In this thesis, a restructured parity-check matrices which can be divided into sub-matrices for LDPC code in DVB-S2 is provided. Corresponded to this restructured parity-check matrix, a reconstructed decoding table is invented. The encoding table of DVB-S2 standard only could obtain the unknown check nodes from known variable nodes, while the decoding table this thesis provided could obtain the unknown variable nodes from known check nodes what is exactly the Layered-massage passing algorithm needed. Layered-message passing algorithm which also known as "Turbo-decoding message passing" is used to reduce the decoding iterations and memory storage for messages. The thesis also investigate Bp algorithm, lambda-min algorithm, Min-sum algorithm and SISO-s algorithm, meanwhile, simulation results of these algorithms and schedules are also presented.

Near lossless source coding with side information only at the decoder, was first considered by Slepian and Wolf in 1970s, and rediscovered recently due to applications such as sensor network and distributed video coding. Suppose X is a source and Y is the side information. The coding scheme proposed by Slepian and Wolf, called SW coding, in which information only flows from the encoder to the decoder, was shown to achieve the rate H(X|Y) asymptotically for stationary ergodic source pairs, but not for non-ergodic case, shown by Yang and He. Recently, a new source coding paradigm called interactive encoding and decoding(IED) was proposed for near lossless coding with side information only at the decoder, where information flows in both ways, from the encoder to the decoder and vice verse. The results by Yang and He show that IED schemes are much more appealing than SW coding schemes to applications where the interaction between the encoder and the decoder is possible. However, the IED schemes proposed by Yang and He do not have an intrinsic structure that is amenable to design and implement in practice. Towards practical design, we restrict the encoding method to linear block codes, resulting in linear IED schemes. It is then shown that this restriction will not undermine the asymptotical performance of IED. Another step of practical design of IED schemes is to make the computational complexity incurred by encoding and decoding feasible. In the framework of linear IED, a scheme can be conveniently described by parity check matrices. Then we get an interesting trade-off between the density of the associated parity check matrices and the resulting symbol error probability. To implement the idea of linear IED and follow the instinct provided by the result above, Low Density Parity Check(LDPC) codes and Belief Propagation(BP) decoding are utilized. A successive LDPC code is proposed, and a new BP decoding algorithm is proposed, which applies to the case where the correlation between $Y$ and $X$ can be modeled as a finite state channel. Finally, simulation results show that linear IED schemes are indeed superior to SW coding schemes.