Ces dernières années ont vu naitre un intérêt grandissant pour les décodeurs correcteurs d'erreurs opérant sur des circuits non fiables. En effet, la miniaturisation croissante des composants électroniques ainsi l'échelonnage agressif de la tension d'alimentation ont pour conséquence la diminution de la fiabilité des systèmes. Par conséquent, les futures générations de circuits électroniques seront intrinsèquement non fiables. En outre, les décodeurs correcteurs d'erreurs sont indispensables non seulement pour assurer une transmission fiable de l'information mais aussi pour concevoir des systèmes de stockage performants.Nous nous intéressons, dans cette thèse, plus particulièrement aux décodeurs à précision finie Min-Sum (MS), Self-Corrected Min-Sum (SCMS) et Stochastiques.Nous commençons par effectuer une analyse statistique du décodeur Min-Sum opérant sur des circuits à comportement probabiliste. Pour ce faire nous introduisons des modèles d'erreurs probabilistes pour les composants logiques et les opérateurs arithmétiques du décodeur et étudions leurs propriétés de symétrie. Puis nous effectuions une analyse asymptotique rigoureuse et en déduisons les équations d'évolution de densité du décodeur Min-Sum bruité. Nous mettons ainsi en évidence l'effet positif, dans certains cas, du bruit issu du circuit sur la capacité de correction du décodeur. Nous révélons ensuite l'existence d'un phénomène de seuil particulier que nous nommons seuil fonctionnel. Ce dernier peut être considéré comme la généralisation du seuil classique pour les décodeurs non fiables. Nous corroborons ensuite les résultats asymptotiques par des simulations Monte-Carlo.Nous implémentons des décodeurs LDPC bruités pour plusieurs paramètres de bruit et montrons que les décodeurs LDPC bruité ont des résultats très proches de ceux des décodeurs non bruités. Nous pouvons par conséquent considérer le circuit d'autocorrection comme un patch bruité appliqué au décodeur MS bruité afin d'améliorer la robustesse du décodeur face au bruit issu des composants non fiables. Nous évaluons par railleurs l'impact de l'ordonnancement et montrons qu'un ordonnancement série dégrade fortement la robustesse des décodeurs bruités MS et SCMS qui ne parviennent plus à atteindre une capacité de correction acceptable.Pour finir nous étudions les performances des décodeurs stochastiques pourvus de mémoires d'arêtes et opérant sur des circuits non fiables. Nous proposons deux modèles d'erreurs décrivant le comportement probabiliste des composants du décodeur. Nous montrons que, dans certains cas, le bruit issu du circuit non fiable permet de réduire le plancher d'erreur. Nous en déduisons alors que le décodeur stochastique est intrinsèquement tolérant aux fautes. / Over the past few years, there has been an increasing interest in error correction decoders built out of unreliable components. Indeed, it is widely accepted that future generation of electronic circuit will be inherently unreliable, due to the increase in density integration and aggressive voltage scaling. Furthermore, error correction decoders play a crucial role both in reliable transmission of information and in the design of reliable storage systems. It is then important to investigate the robustness of error correction decoders in presence of hardware noise.In this thesis we focus on LDPC decoders built out of unreliable computing units. We consider three types of LDPC decoders: the finite-precision Min-Sum (MS) decoder, the Self-Corrected Min-Sum (SCMS) decoder and the Stochastic decoder.We begin our study by the statistical analysis of the finite-precision Min-Sum decoder with probabilistic components. To this end, we first introduce probabilistic models for the arithmetic and logic units of the decoder and discuss their symmetry properties. We conduct a thorough asymptotic analysis and derive density evolution equations for the noisy Min-Sum decoder. We highlight that in some particular cases, the noise introduced by the device can increase the correction capacity of the noisy Min-Sum with respect to the noiseless decoder. We also reveal the existence of a specific threshold phenomenon, referred to as functional threshold, which can be viewed as the generalization of the threshold definition for noisy decoders. We then corroborate the asymptotic results through Monte-Carlo simulations.Since density evolution cannot be defined for decoders with memory, the analysis of noisy Self-corrected Min-Sum decoders and noisy Stochastic decoders was restricted to Monte-Carlo simulations.We emulate the noisy SCMS decoders with various noise parameters and show that noisy SCMS decoders perform close to the noiseless SCMS decoder for a wide range of noise parameters. Therefore, one can think of the self-correction circuit as a noisy patch applied to the noisy MS decoder, in order to improve its robustness to hardware defect. We also evaluate the impact of the decoder scheduling on the robustness of the noisy MS and SCMS decoders and show that when the serial scheduling is used neither the noisy MS decoder nor the noisy SCMS decoder can provide acceptable error correction.Finally, we investigate the performance of stochastic decoders with edge-memories in presence of hardware noise. We propose two error models for the noisy components. We show that in some cases, the hardware noise can be used to lower the error floor of the decoder meaning that stochastic decoders have an inherent fault tolerant capability.

Low-density parity-check (LDPC) codes have been shown to have good error correcting performance approaching Shannon’s limit. Good error correcting performance enables efficient and reliable communication. However, a LDPC code decoding algorithm needs to be executed efficiently to meet cost, time, power and bandwidth requirements of target applications. The constructed codes should also meet error rate performance requirements of those applications. Since their rediscovery, there has been much research work on LDPC code construction and implementation. LDPC codes can be designed over a wide space with parameters such as girth, rate and length. There is no unique method of constructing LDPC codes. Existing construction methods are limited in some way in producing good error correcting performing and easily implementable codes for a given rate and length. There is a need to develop methods of constructing codes over a wide range of rates and lengths with good performance and ease of hardware implementability. LDPC code hardware design and implementation depend on the structure of target LDPC code and is also as varied as LDPC matrix designs and constructions. There are several factors to be considered including decoding algorithm computations,processing nodes interconnection network, number of processing nodes, amount of memory, number of quantization bits and decoding delay. All of these issues can be handled in several different ways. This thesis is about construction of LDPC codes and their hardware implementation. LDPC code construction and implementation issues mentioned above are too many to be addressed in one thesis. The main contribution of this thesis is the development of LDPC code construction methods for some classes of structured LDPC codes and techniques for reducing decoding time. We introduce two main methods for constructing structured codes. In the first method, column-weight two LDPC codes are derived from distance graphs. A wide range of girths, rates and lengths are obtained compared to existing methods. The performance and implementation complexity of obtained codes depends on the structure of their corresponding distance graphs. In the second method, a search algorithm based on bit-filing and progressive-edge growth algorithms is introduced for constructing quasi-cyclic LDPC codes. The algorithm can be used to form a distance or Tanner graph of a code. This method could also obtain codes over a wide range of parameters. Cycles of length four are avoided by observing the row-column constraint. Row-column connections observing this condition are searched sequentially or randomly. Although the girth conditions are not sufficient beyond six, larger girths codes were easily obtained especially at low rates. The advantage of this algorithm compared to other methods is its flexibility. It could be used to construct codes for a given rate and length with girths of at least six for any sub-matrix configuration or rearrangement. The code size is also easily varied by increasing or decreasing sub-matrix size. Codes obtained using a sequential search criteria show poor performance at low girths (6 and 8) while random searches result in good performing codes. Quasi-cyclic codes could be implemented in a variety of decoder architectures. One of the many options is the choice of processing nodes interconnect. We show how quasi-cyclic codes processing could be scheduled through a multistage network. Although these net-works have more delay than other modes of communication, they offer more flexibility at a reasonable cost. Banyan and Benes networks are suggested as the most suitable networks. Decoding delay is also one of several issues considered in decoder design and implementation. In this thesis, we overlap check and variable node computations to reduce decoding time. Three techniques are discussed, two of which are introduced in this thesis. The techniques are code matrix permutation, matrix space restriction and sub-matrix row-column scheduling. Matrix permutation rearranges the parity-check matrix such that rows and columns that do not have connections in common are separated. This techniques can be applied to any matrix. Its effectiveness largely depends on the structure of the code. We show that its success also depends on the size of row and column weights. Matrix space restriction is another technique that can be applied to any code and has fixed reduction in time or amount of overlap. Its success depends on the amount of restriction and may be traded with performance loss. The third technique already suggested in literature relies on the internal cyclic structure of sub-matrices to achieve overlapping. The technique is limited to LDPC code matrices in which the number of sub-matrices is equal to row and column weights. We show that it can be applied to other codes with a lager number of sub-matrices than code weights. However, in this case maximum overlap is not guaranteed. We calculate the lower bound on the amount of overlapping. Overlapping could be applied to any sub-matrix configuration of quasi-cyclic codes by arbitrarily choosing the starting rows for processing. Overlapping decoding time depends on inter-iteration waiting times. We show that there are upper bounds on waiting times which depend on the code weights. Waiting times could be further reduced by restricting shifts in identity sub-matrices or using smaller sub-matrices. This overlapping technique can reduce the decoding time by up to 50% compared to conventional message and computation scheduling. Techniques of matrix permutation and space restriction results in decoder architectures that are flexible in LDPC code design in terms of code weights and size. This is due to the fact that with these techniques, rows and columns are processed in sequential order to achieve overlapping. However, in the existing technique, all sub-matrices have to be processed in parallel to achieve overlapping. Parallel processing of all code sub-matrices requires the architecture to have the number of processing units at least equal to the number sub-matrices. Processing units and memory space should therefore be distributed among the sub-matrices according to the sub-matrices arrangement. This leads to high complexity or inflexibility in the decoder architecture. We propose a simple, programmable and high throughput decoder architecture based on matrix permutation and space restriction techniques. / Thesis(Ph.D.) -- University of Adelaide, School of Electrical and Electronic Engineering, 2007

Low-density parity-check (LDPC) codes have been shown to have good error correcting performance approaching Shannon’s limit. Good error correcting performance enables efficient and reliable communication. However, a LDPC code decoding algorithm needs to be executed efficiently to meet cost, time, power and bandwidth requirements of target applications. The constructed codes should also meet error rate performance requirements of those applications. Since their rediscovery, there has been much research work on LDPC code construction and implementation. LDPC codes can be designed over a wide space with parameters such as girth, rate and length. There is no unique method of constructing LDPC codes. Existing construction methods are limited in some way in producing good error correcting performing and easily implementable codes for a given rate and length. There is a need to develop methods of constructing codes over a wide range of rates and lengths with good performance and ease of hardware implementability. LDPC code hardware design and implementation depend on the structure of target LDPC code and is also as varied as LDPC matrix designs and constructions. There are several factors to be considered including decoding algorithm computations,processing nodes interconnection network, number of processing nodes, amount of memory, number of quantization bits and decoding delay. All of these issues can be handled in several different ways. This thesis is about construction of LDPC codes and their hardware implementation. LDPC code construction and implementation issues mentioned above are too many to be addressed in one thesis. The main contribution of this thesis is the development of LDPC code construction methods for some classes of structured LDPC codes and techniques for reducing decoding time. We introduce two main methods for constructing structured codes. In the first method, column-weight two LDPC codes are derived from distance graphs. A wide range of girths, rates and lengths are obtained compared to existing methods. The performance and implementation complexity of obtained codes depends on the structure of their corresponding distance graphs. In the second method, a search algorithm based on bit-filing and progressive-edge growth algorithms is introduced for constructing quasi-cyclic LDPC codes. The algorithm can be used to form a distance or Tanner graph of a code. This method could also obtain codes over a wide range of parameters. Cycles of length four are avoided by observing the row-column constraint. Row-column connections observing this condition are searched sequentially or randomly. Although the girth conditions are not sufficient beyond six, larger girths codes were easily obtained especially at low rates. The advantage of this algorithm compared to other methods is its flexibility. It could be used to construct codes for a given rate and length with girths of at least six for any sub-matrix configuration or rearrangement. The code size is also easily varied by increasing or decreasing sub-matrix size. Codes obtained using a sequential search criteria show poor performance at low girths (6 and 8) while random searches result in good performing codes. Quasi-cyclic codes could be implemented in a variety of decoder architectures. One of the many options is the choice of processing nodes interconnect. We show how quasi-cyclic codes processing could be scheduled through a multistage network. Although these net-works have more delay than other modes of communication, they offer more flexibility at a reasonable cost. Banyan and Benes networks are suggested as the most suitable networks. Decoding delay is also one of several issues considered in decoder design and implementation. In this thesis, we overlap check and variable node computations to reduce decoding time. Three techniques are discussed, two of which are introduced in this thesis. The techniques are code matrix permutation, matrix space restriction and sub-matrix row-column scheduling. Matrix permutation rearranges the parity-check matrix such that rows and columns that do not have connections in common are separated. This techniques can be applied to any matrix. Its effectiveness largely depends on the structure of the code. We show that its success also depends on the size of row and column weights. Matrix space restriction is another technique that can be applied to any code and has fixed reduction in time or amount of overlap. Its success depends on the amount of restriction and may be traded with performance loss. The third technique already suggested in literature relies on the internal cyclic structure of sub-matrices to achieve overlapping. The technique is limited to LDPC code matrices in which the number of sub-matrices is equal to row and column weights. We show that it can be applied to other codes with a lager number of sub-matrices than code weights. However, in this case maximum overlap is not guaranteed. We calculate the lower bound on the amount of overlapping. Overlapping could be applied to any sub-matrix configuration of quasi-cyclic codes by arbitrarily choosing the starting rows for processing. Overlapping decoding time depends on inter-iteration waiting times. We show that there are upper bounds on waiting times which depend on the code weights. Waiting times could be further reduced by restricting shifts in identity sub-matrices or using smaller sub-matrices. This overlapping technique can reduce the decoding time by up to 50% compared to conventional message and computation scheduling. Techniques of matrix permutation and space restriction results in decoder architectures that are flexible in LDPC code design in terms of code weights and size. This is due to the fact that with these techniques, rows and columns are processed in sequential order to achieve overlapping. However, in the existing technique, all sub-matrices have to be processed in parallel to achieve overlapping. Parallel processing of all code sub-matrices requires the architecture to have the number of processing units at least equal to the number sub-matrices. Processing units and memory space should therefore be distributed among the sub-matrices according to the sub-matrices arrangement. This leads to high complexity or inflexibility in the decoder architecture. We propose a simple, programmable and high throughput decoder architecture based on matrix permutation and space restriction techniques. / Thesis(Ph.D.) -- University of Adelaide, School of Electrical and Electronic Engineering, 2007

L'objet de cette thèse est l'étude des codes LDPC quantiques. Dans un premier temps, nous travaillons sur des constructions topologiques de codes LDPC quantiques. Nous proposons de construire une famille de codes couleur basée sur des pavages hyperboliques. Nous étudions ensuite les paramètres d'une famille de codes basée sur des graphes de Cayley.Dans une seconde partie, nous examinons les performances de ces codes. Nous obtenons une borne supérieure sur les performances des codes LDPC quantiques réguliers sur le canal à effacement quantique. Ceci prouve que ces codes n'atteignent pas la capacité du canal à effacement quantique. Dans le cas du canal de dépolarisation, nous proposons un nouvel algorithme de décodage des codes couleur basé sur trois décodages de codes de surface. Nos simulations numériques montrent de bonnes performances dans le cas des codes couleur toriques.Pour finir, nous nous intéressons au phénomène de percolation. La question centrale de la théorie de la percolation est la détermination du seuil critique. Le calcul exacte de ce seuil est généralement difficile. Nous relions la probabilité de percolation dans certains pavages réguliers du plan hyperbolique à la probabilité d'erreur de décodage pour une famille de codes hyperboliques. Nous en déduisons une borne sur le seuil critique de ces pavages hyperboliques basée sur des résultats de théorie de l'information quantique. Il s'agit d'une application de la théorie de l'information quantique à un problème purement combinatoire. / This thesis is devoted to the study of quantum LDPC codes. The first part presents some topological constructions of quantum LDPC codes. We introduce a family of color codes based on tilings of the hyperbolic plane. We study the parameters of a family of codes based on Cayley graphs.In a second part, we analyze the performance of these codes. We obtain an upper bound on the performance of regular quantum LDPC codes over the quantum erasure channel. This implies that these codes don't achieve the capacity of the quantum erasure channel. In the case of the depolarizing channel, we propose a new decoding algorithm of color codes based on three surface codes decoding. Our numerical results show good performance for toric color codes.Finally, we focus on percolation theory. The central question in percolation theory is the determination of the critical probability. Computing the critical probability exactly is usually quite difficult. We relate the probability of percolation in some regular tilings of the hyperbolic plane to the probability of a decoding error for hyperbolic codes on the quantum erasure channel. This leads to an upper bound on the critical probability of these hyperbolic tilings based on quantum information. It is an application of quantum information to a purely combinatorial problem.

De nos jours, l’architecture du réseau mobile est en pleine évolution pour assurer la montée en débit entre les Centraux (CO) (réseaux coeurs) et différents terminaux comme les mobiles, ordinateurs, tablettes afin de satisfaire les utilisateurs. Pour faire face à ces défis du futur, le réseau C-RAN (Cloud ou Centralized-RAN) est connu comme une solution de la 5G. Dans le contexte C-RAN, toutes les BBUs (Base Band Units) sont centralisées dans le CO, seules les RRH (Remote Radio Head) restent situées à la tête de la station de base (BS). Un nouveau segment entre les BBUs et RRHs apparait nommé « fronthaul ». Il est basé sur des transmissions D-ROF (digital radio-overfiber) et transporte le signal radio numérique à un débit binaire élevé en utilisant le protocole CPRI (Common Public Radio Interface). En prenant en compte le CAPEX et l’OPEX, le projet ANR LAMPION a proposé la technologie RSOA (Reflective Semiconductor Optical Amplifier) auto alimenté afin de rendre la solution plus flexible et s’affranchir d’émetteurs/récepteurs colorés dans le cadre de transmission WDM-PON (Wavelength Division Multiplexing Passive Optical Network). Néanmoins, il est nécessaire d’ajouter un FEC (forward error corrector) dans la transmission pour assurer la qualité de service. Donc l’objectif de cette thèse est de trouver le FEC le plus adéquat à appliquer dans le contexte C-RAN. Nos travaux se sont focalisés sur l’utilisation de codes LDPC, choisis après comparaisons des performances avec les autres types de codes. Nous avons précisé les paramètres (rendement du code, taille de la matrice, cycle, etc.) nécessaires pour les codes LDPC afin d'obtenir les meilleures performances. Les algorithmes LDPC à décisions dures ont été choisis après considération du compromis entre complexités de circuit et performance. Parmi ces algorithmes à décision dures, le GDBF (gradient descent bit-flipping) était la meilleure solution. La prise en compte d’un CAN 2-Bit dans le canal nous a amené à proposer une variante : le BWGDBF (Balanced weighted GDBF). Des optimisations ont également été faites en regard de la convergence de l'algorithme et de la latence. Enfin, nous avons réussi à implémenter notre propre algorithme sur le FPGA Spartan 6 xc6slx16. Plusieurs méthodes ont été proposées pour atteindre une latence de 5 μs souhaitée dans le contexte C-RAN. Cette thèse a été soutenue par le projet ANR LAMPION (Lambada-based Access and Metropolitan Passive Optical networks). / Nowadays, the architecture of the mobile network is in full evolution to ensure the increase in terms of bit rate between the Central (CO) (core networks) and various terminals such as mobiles, computers, tablets in order to satisfy the users. To address these challenges of the future, the C-RAN (Cloud or Centralized-RAN) network is known as a 5G solution. In the C-RAN context, all BBUs (Base Band Units) are centralized in the CO, only the RRH (Remote Radio Head) remain at the head of the base station (BS). A new segment between BBUs and RRHs appears called "fronthaul". It is based on D-ROF (digital radio-overfiber) transmissions and carries the digital radio signal at a high bit rate using the Common Public Radio Interface (CPRI) protocol. Taking into account CAPEX and OPEX, the ANR LAMPION project has proposed the Self-seeded Reflective Semiconductor Optical Amplifier (RSOA) technology in order to make the solution more flexible and overcome the need for colored transmitters / receivers in the context of PON-WDM (Wavelength Division Multiplexing Passive Optical Network). Nevertheless, it is necessary to add a FEC (forward error corrector) in the transmission to ensure the quality of service. So the objective of this thesis is to find the most suitable FEC to apply in the C-RAN context. Our work has focused on the use of LDPC codes, chosen after performance comparisons with other types of codes. We have specified the parameters (code performance, matrix size, cycle, etc.) required for LDPC codes to obtain the best performance. Hard-decision LDPC algorithms were chosen after considering the tradeoff between circuit complexities and performance. Among these hard-decision algorithms, the GDBF (gradient descent bit-flipping) was the best solution. Taking into account a CAN 2-Bit in the channel led us to propose a variant: the BWGDBF (Balanced weighted GDBF). Optimizations have also been made with respect to the convergence of the algorithm and latency. Finally, we managed to implement our own algorithm on the Spartan FPGA 6 xc6slx16. Several methods have been proposed to achieve a latency of 5 μs desired in the C-RAN context. This thesis was supported by the project ANR LAMPION (Lambada-based Access and Metropolitan Passive Optical Networks).

The aim of this thesis are problematics about LDPC codes. There are described metods to create parity check matrix, where are important structured metods using finite geometry: Euclidean geometry and projectice geometry. Next area in this thesis is decoding LDPC codes. There are presented four metods: Hard-Decision algorithm, Bit-Flipping algorithm, The Sum-Product algorithm and Log Likelihood algorithm, where is mainly focused on iterative decoding methods. Practical output of this work is program LDPC codes created in environment Matlab. The program is divided to two parts -- Practise LDPC codes and Simulation LDPC codes. The result reached by program Simulation LDPC codes is used to create a comparison of creating and decoding methods LDPC codes. For comparison of decoding methods LDPC codes were used BER characteristics and time dependence each method on various parameters LDPC code (number of iteration or size of parity matrix).

Dans cette thèse, nous présentons nos travaux dans le domaine de l'algorithme de décodage non-binaire pour les classes générales de codes LDPC non-binaires. Les Low-Density Parity-Check (LDPC) codes ont été initialement présentés par Gallager en 1963, et après quelques avancées théoriques fondamentales, ils ont été pris en compte dans les normes comme le DVB-S2, WI-MAX, DSL, W-LAN etc. Plus tard, Les codes LDPC non-binaires (NB-LDPC) ont été proposés dans la littérature, et ont montré de meilleures performances lorsque la taille du code est petite ou lorsqu'il est utilisé sur des canaux non-binaires. Toutefois, les avantages de l'utilisation des codes LDPC non-binaires entrainent une complexité de décodage fortement accrue. Pour un code défini dans GF (q), la complexité est de l'ordre O(q^2). De même, la mémoire nécessaire pour stocker les messages est d'ordre O(q). Par conséquent, l'implémentation d'un décodeur LDPC-définie sur un ordre q> 64 devient pratiquement impossible.L'objectif principal de la thèse est de développer des algorithmes a complexité réduite, pour les codes LDPC non-binaires qui démontrent un rendement excellent et qui soient implémentable. Pour optimiser les performances de décodage, non seulement l'algorithme de décodage est important, mais aussi la structure du code joue un rôle important. Avec cet objectif à l'esprit, une nouvelle famille de codes appelés codes cluster-NB-LDPC a été élaboré et des améliorations spécifiques du décodeur NB pour les codes de cluster-NB-LDPC ont été proposés. Notre principal résultat est que nous étions en mesure de proposer des décodeurs de codes cluster-NB-LDPC avec une complexité réduite par rapport à décodeurs d'habitude pour les codes LDPC-NB sur les corps de Galois, sans aucune perte de performance en matière de la capacité de correction d'erreur. / In this thesis we present our work in the domain of non-binary decoding algorithm for general classes of non-binary LDPC codes. Low-Density Parity-Check (LDPC) codes were originally presented by Gallager in 1963, and after some fundamental theoretical advancements, they were considered in standards like DVB-S2, WI-MAX, DSL, W-LAN etc. Later on, non-binary LDPC (NB-LDPC)codes were proposed in the litterature, and showed better performance for small lengths or when used on non-binary channels. However, the advantages of using NB-LDPC codes comes with the consequence of an heavily increased decoding complexity. For a code defined in GF(q), the complexity is of the order O(q^2). Similarly, the memory required for storing messages is of order O(q). Consequently, the implementation of an LDPC-decoder defined over a field order q > 64 becomes practically impossible.The main objective of the thesis is to develop reduced complexity algorithms for non-binary LDPC codes that exhibit excellent performance and is practically im-plementable. For better decoding performance, not only the decoding algorithm is important, but also the structure of the code plays an important role. With this goal in mind, a new family of codes called cluster-NB-LDPC codes was developped and specific improvements of the NB decoder for cluster-NB-LDPC codes were proposed. Our principal result is that we were able to propose decoders for cluster-NB-LDPC codes with reduced complexity compared to usual decoders for NB-LDPC codes on fields, without any performance loss in error correction capability.

Dans cette thèse, nous présentons nos travaux dans le domaine des algorithmes de décodage des codes LDPC non-binaires généralisés. Les codes LDPC binaires ont été initialement proposés par Gallager en 1963, et après quelques avancées théoriques fondamentales, ils ont été proposés dans des standards tels que DVB-S2, WI-MAX, DSL, W-LAN etc. Plus tard, les codes LDPC non-binaires (NB-LDPC) ont été pro- posés dans la littérature, et ont montré une meilleure performance pour de petites tailles de code ou lorsqu'ils sont utilisés sur des canaux non-binaires. Cependant, les avan- tages de l'utilisation de codes NB-LDPC impliquent une augmentation importante de la complexité de décodage. Pour un code défini dans un corps de Galois GF (q), la complexité est d'ordre O (q2). De même, la mémoire requise pour le stockage des messages est d'ordre O (q). Ainsi, l'implémentation d'un décodeur LDPC défini sur un corps de Galois pour q > 64 devient impossible dans la pratique. L'objectif prin- cipal de cette thèse est de développer des algorithmes avec une bonne performance et complexité réduite de sorte qu'ils deviennent implémentables. Pour une performance de décodage optimisée, non seulement l'algorithme est important, mais également la structure du code joue un rôle clé. Avec cet objectif à l'esprit, une nouvelle famille de codes appelés " cluster-NB-LDPC codes " a été élaborée ainsi que des améliorations spécifiques du décodeur non-binaire pour ces codes. Le résultat principal est que nous avons pu proposer des décodeurs pour les codes cluster-NB-LDPC avec une complex- ité réduite par rapport aux décodeurs classiques pour les codes NB-LDPC définis sur les corps de Galois, sans aucune perte de performance dans la capacité de correction vi Résumé d'erreur. Dans la première partie de la thèse, nous avons modifié l'algorithme EMS pour les cluster-codes. La généralisation directe de l'algorithme EMS aux codes cluster-NB- LDPC n'est pas réaliste . Il y a une perte de performance et une augmentation de la complexité. Par conséquent, nous proposons quelques modifications dans la procé- dure, qui non seulement améliore considérablement les performances de décodage, mais diminue également la complexité. Au niveau des noeuds de parité, cet algo- rithme conserve les mêmes limites sur le nombre d'opérations que l'algorithme EMS pour GF (q)-codes, O (nmlognm) avec nm << q. Nous proposons ensuite une autre méthode, basée sur la diversité des codes cluster, afin d'améliorer les performances de l'algorithme EMS pour les codes cluster-LDPC. Il contribue également à réduire la complexité globale du décodeur. Finalement, nous comparons les performances de décodage en utilisant cette méthode et analysons l'effet sur la complexité de décodage. Dans la dernière partie du chapitre, nous proposons une nouvelle direction pour le décodage des codes LDPC. Elle est basée sur la création des listes des mots de code qui correspondent à des noeuds de parité. Les listes sont construite de manière récur- sive dans une structure en arbre, ce qui en fait un bon candidat pour l'implémentation matérielle. Il s'agit d'une méthode nouvelle et doit encore être améliorée mais à pre- miére vue nous avons obtenu de bons résultats avec un nombre réduit d'operations.

Low Density Parity Check (LDPC) codes are the parity check codes of long block length, whose parity check matrices have relatively few non-zero entries. To improve the performance at relatively short block lengths, LDPC codes are constructed by either pseudo-random or quasi-cyclic methods instead of random construction methods. In this thesis, pseudo-random code construction methods, the effects of closed loops and the graph connectivity on the performance of pseudo-random LDPC codes are investigated. Moreover, quasi-cyclic LDPC codes, which have encoding and storage advantages over pseudo-random LDPC codes, their construction methods and performances are reviewed. Finally, performance comparison between pseudo-random and quasi-cyclic LDPC codes is given for both regular and irregular cases.

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. / Iterative algorithms are now widely used in all areas of signal processing and digital communications. In modern communication systems, iterative algorithms are used for decoding low-density parity-check (LDPC) codes, a popular class of error-correction codes that are now widely used for their exceptional error-rate performance. In a more recent field known as compressed sensing, iterative algorithms are used as a method of reconstruction to recover a sparse signal from a linear set of measurements. This thesis primarily deals with the development of low-complexity iterative algorithms for the two aforementioned fields, namely, the design of low-complexity decoding algorithms for LDPC codes, and the development and analysis of a low complexity reconstruction algorithm called Interval-Passing Algorithm (IPA) for compressed sensing.In the first part of this thesis, we address the area of decoding algorithms for LDPC codes. It is well-known that LDPC codes suffer from the error floor phenomenon in spite of their exceptional performance, where traditional iterative decoders based on the belief propagation (BP) fail for certain low-noise configurations. Recently, a novel class of decoders called ''finite alphabet iterative decoders (FAIDs)'' were proposed that are capable of surpassing BP in the error floor at much lower complexity. In this work, we focus on the problem of selection of particularly good FAIDs for column-weight-three codes over the Binary Symmetric channel (BSC). Traditional methods for decoder selection use asymptotic techniques such as the density evolution method, which do not guarantee a good performance on finite-length codes especially in theerror floor region. Instead, we propose a methodology for selection that relies on the knowledge of potentially harmful topologies that could be present in a code, using the concept of noisy trapping set. Numerical results are provided to show that FAIDs selected based on our methodology outperform BP in the error floor on several codes.In the second part of this thesis, we address the area of iterative reconstruction algorithms for compressed sensing. Iterative algorithms have been proposed for compressed sensing in order to tackle the complexity of the LP reconstruction method. In this work, we modify and analyze a low complexity reconstruction algorithm called the IPA which uses sparse matrices as measurement matrices. Similar to what has been done for decoding algorithms in the area of coding theory, we analyze the failures of the IPA and link them to the stopping sets of the binary representation of the sparse measurement matrices used. The performance of the IPA makes it a good trade-off between the complex L1-minimization reconstruction and the very simple verification decoding.