No description available.

Les codes correcteurs d’erreurs Non-Binaires Low Density Parity Check (NB-LDPC) sont connus pour avoir de meilleure performance que les codes LDPC binaires. Toutefois, la complexité de décodage des codes non-binaires est bien supérieure à celle des codes binaires. L’objectif de cette thèse est de proposer de nouveaux algorithmes et de nouvelles architectures matérielles de code NB-LDPC pour le décodage des NBLDPC. La première contribution de cette thèse consiste à réduire la complexité du nœud de parité en triant en amont ses messages d’entrées. Ce tri initial permet de rendre certains états très improbables et le matériel requis pour les traiter peut tout simplement être supprimé. Cette suppression se traduit directement par une réduction de la complexité du décodeur NB-LDPC, et ce, sans affecter significativement les performances de décodage. Un modèle d’architecture, appelée "architecture hybride" qui combine deux algorithmes de l’état de l’art ("l’Extended Min Sum" et le "Syndrome Based") a été proposé afin d’exploiter au maximum le pré-tri. La thèse propose aussi de nouvelles méthodes pour traiter les nœuds de variable dans le contexte d’une architecture pré-tri. Différents exemples d’implémentations sont donnés pour des codes NB-LDPC sur GF(64) et GF(256). En particulier, une architecture très efficace de décodeur pour un code de rendement 5/6 sur GF(64) est présentée. Cette architecture se caractérise par une architecture de check node nœud de parité entièrement parallèle. Enfin, une problématique récurrente dans les architectures NB-LDPC, qui est la recherche des P minimums parmi une liste de taille Ns, est abordée. La thèse propose une architecture originale appelée first-then-second minimum pour une implantation efficace de cette tâche. / The Non-Binary Low Density Parity Check (NB-LDPC) codes constitutes an interesting category of error correction codes, and are well known to outperform their binary counterparts. However, their non-binary nature makes their decoding process of higher complexity. This PhD thesis aims at proposing new decoding algorithms for NB-LDPC codes that will be shaping the resultant hardware architectures expected to be of low complexity and high throughput rate. The first contribution of this thesis is to reduce the complexity of the Check Node (CN) by minimizing the number of messages being processed. This is done thanks to a pre-sorting process that sorts the messages intending to enter the CN based on their reliability values, where the less likely messages will be omitted and consequently their dedicated hardware part will be simply removed. This reliability-based sorting enabling the processing of only the highly reliable messages induces a high reduction of the hardware complexity of the NB-LDPC decoder. Clearly, this hardware reduction must come at no significant performance degradation. A new Hybrid architectural CN model (H-CN) combining two state-of-the-art algorithms - Forward-Backward CN (FB-CN) and Syndrome Based CN (SB-CN) - has been proposed. This hybrid model permits to effectively exploit the advantages of pre-sorting. This thesis proposes also new methods to perform the Variable Node (VN) processing in the context of pre-sorting-based architecture. Different examples of implementation of NB-LDPC codes defined over GF(64) and GF(256) are presented. For decoder to run faster, it must become parallel. From this perspective, we have proposed a new efficient parallel decoder architecture for a 5/6 rate NB-LDPC code defined over GF(64). This architecture is characterized by its fully parallel CN architecture receiving all the input messages in only one clock cycle. The proposed new methodology of parallel implementation of NB-LDPC decoders constitutes a new vein in the hardware conception of ultra-high throughput rate decoders. Finally, since the NB-LDPC decoders requires the implementation of a sorting function to extract P minimum values among a list of size Ns, a chapter is dedicated to this problematic where an original architecture called First-Then-Second-Extrema-Selection (FTSES) has been proposed.

Le codage de canal est une opération mathématique qui améliore la qualité des transmissions numériques en corrigeant les bits erronés en réception. Les contraintes des usages comme la qualité de réception, les débits d'utilisation, la latence de calcul, la surface ou encore la consommation électrique favorisent l'usage de différents codes dans la standardisation des protocoles de communication. La tendance industrielle est à la convergence des réseaux de communication pour des usages variés. Ce large choix de codage devient un handicap pour la conception de transmetteurs à bas coûts. Les réseaux médias favorisent des codes correcteurs d'erreurs avancés comme les turbocodes et les codes LDPC pour répondre aux contraintes de qualité de réception. Or ces procédés ont un coût de décodage important sur les récepteurs finaux. Une architecture adaptée à plusieurs types de codes capable d'évoluer en fonction d'une modification du protocole d'accès devient inévitable pour élaborer de nouveaux scénarios d'usages. Ce mémoire présente le principe du codage de canal et la plupart des codes correcteurs d'erreurs avancés sélectionnés dans les standards de communication courants. Les caractéristiques communes des codes QC-LDPC et des turbocodes sont soulignées. Les principaux algorithmes ainsi que certaines architectures de décodage sont présentés. La complexité matérielle des principaux algorithmes de décodage est évaluée. Ils sont comparés pour un même code et à un niveau de correction équivalent pour les codes QC-LDPC. Une étude similaire est réalisée sur les turbocodes. Les algorithmes de décodage sont appliqués sur des codes de tailles et de rendements proches et dimensionnés pour atteindre une correction similaire afin de sélectionner un algorithme de décodage conjoint aux deux familles de code. Les codes QC-LDPC et les turbocodes se structurent à l'aide d'une représentation en treillis commune. La technique de fenêtrage couramment appliquée au décodage des turbocodes est étudiée pour le décodage d'un code QC-LDPC. Enfin, l'entrelacement des codes QC-LDPC est mis en évidence et reconsidéré en fonction des contraintes matérielles. Un coeur de décodage de treillis compatible avec les standards 3GPP LTE et IEEE 802.11n est proposé. Plusieurs structures de décodage sont ensuite introduites incorporant un ou plusieurs de ces coeurs. L'intégration sur cible FPGA est détaillée. Un scénario d'utilisation avec un contexte de décodage évoluant à chaque message reçu est proposé ce qui souligne l'impact de la reconfiguration sur les débits de décodage. La structure multistandard nécessite 4,2 % (respectivement 5,3 %) de ressources matérielles supplémentaires à une structure compatible avec le standard 3GPP LTE (resp. IEEE 802.11n) seul. La dégradation du débit maximal due à la reconfiguration entre le décodage des mots de code est d'au plus 1 %. Une architecture à plusieurs coeurs est également portée sur une cible ASIC de 65 nm. Cette architecture fonctionne à une fréquence de 500 Mhz sur une surface de 2,1 mm2 décodant les mots de code 3GPP LTE et IEEE 802.11n, et acceptant une reconfiguration dynamique entre deux mots de code consécutifs.

Ce travail est dédié à la conception, l’analyse et l’évaluation des performances de nouveaux schémas de codage appropriés aux systèmes de stockage distribué. La première partie de ce travail est consacrée à l’étude des performances des codes spatialement couplés pour les canaux à effacements. Une nouvelle méthode de couplage spatial des ensembles classiques de contrôle de parité à faible densité (LDPC) est proposée. La méthode est inspirée du codage en couches. Les arêtes des ensembles locaux et celles définissant le couplage spatial sont construites séparément. Nous proposons également de saturer le seuil d’un ensemble Root-LDPC par couplage spatial de ses bits de parité dans le but de faire face aux évanouissements quasi-statiques. Le couplage spatial est dans un deuxième temps appliqué à un ensemble Root-LDPC, ayant une double diversité, conçu pour un canal à effacements par blocs à 4 états. Dans la deuxième partie de ce travail, nous considérons les codes produits non-binaires avec des composantes MDS et leur décodage algébrique itératif ligne-colonne sur un canal à effacements. Les effacements indépendants et par blocs sont considérés. Une représentation graphique compacte du code est introduite avec laquelle nous définissions la notion de coloriage à double diversité. Les ensembles d’arrêt sont définis et une caractérisation complète est donnée. La performance des codes produits à composantes MDS, avec et sans coloration, à double diversité est analysée en présence d’effacements indépendants et par blocs. Les résultats numériques montrent aussi une excellente performance en présence d’effacements à probabilité inégale due au coloriage ayant une double diversité. / This work is dedicated to the design, analysis, and the performance evaluation of new coding schemes suitable for distributed storage systems. The first part is devoted to spatially coupled codes for erasure channels. A new method of spatial coupling for low-density parity-check ensembles is proposed. The method is inspired from overlapped layered coding. Edges of local ensembles and those defining the spatial coupling are separately built. We also propose to saturate the whole Root-LDPC boundary via spatial coupling of its parity bits to cope with quasi-static fading. Then, spatial coupling is applied on a Root-LDPC ensemble with double diversity designed for a channel with 4 block-erasure states. In the second part of this work, we consider non-binary product codes with MDS components and their iterative row-column algebraic decoding on the erasure channel. Both independent and block erasures are considered. A compact graph representation is introduced on which we define double-diversity edge colorings via the rootcheck concept. Stopping sets are defined and a full characterization is given in the context of MDS components. A differential evolution edge coloring algorithm that produces colorings with a large population of minimal rootcheck order symbols is presented. The performance of MDS-based product codes with and without double-diversity coloring is analyzed in presence of both block and independent erasures. Furthermore, numerical results show excellent performance in presence of unequal erasure probability due to double-diversity colorings.