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.

In this thesis, we investigate the basics of Low-Density Parity-Check (LDPC) codes over binary and non-binary alphabets. We especially focus on the message passing decoding algorithms, which have different message definitions such as a posteriori probabilities, log-likelihood ratios and Fourier transforms of probabilities. We present the simulation results that compare the performances of small block length binary and non-binary LDPC codes, which have regular and irregular structures over GF(2),GF(4) and GF(8) alphabets. We observe that choosing non-binary alphabets improve the performance with careful selection of mean column weight by comparing LDPC codes with variable node degrees of 3, 2.8 and 2.6, since it is effective in the order of GF(2), GF(4) and GF(8) performances.

This thesis investigates applications of puncturing in error-correction coding and physical layer security with an emphasis on binary and non-binary LDPC codes. Theoretical framework for the analysis of punctured binary LDPC codes at short block lengths is developed and a novel decoding scheme is designed that achieves considerably faster convergence than conventional approaches. Subsequently, optimized puncturing and shortening is studied for non-binary LDPC codes over binary input channels. Framework for the analysis of punctured/shortened non-binary LDPC codes over the BEC channel is developed, which enables the optimization of puncturing and shortening patterns. Insight from this analysis is used to develop algorithms for puncturing and shortening of non-binary LDPC codes at finite block lengths that perform well. It is confirmed that symbol-wise puncturing is generally bad and that bit-wise punctured non-binary LDPC codes can significantly outperform their binary counterparts, thus making them an attractive solution for future communication systems; both for error-correction and distributed compression. Puncturing is also considered in the context of physical layer security. It is shown that puncturing can be used effectively for coding over the wiretap channel to hide the message bits from eavesdroppers. Further, it is shown how puncturing patterns can be optimized for enhanced secrecy. Asymptotic analysis confirms that eavesdroppers are forced to operate at BERs very close to 0.5, even if their signal is only slightly worse than that of the legitimate receivers. The proposed coding scheme is naturally applicable at finite block lengths and allows for efficient, almost-linear time encoding. Finally, it is shown how error-correcting codes can be used to solve an open problem of compressing data encrypted with block ciphers such as AES. Coding schemes for multiple chaining modes are proposed and it is verified that considerable compression gains are attainable for binary sources.

Au cours des 15 dernières années, des progrès spectaculaires dans l'analyse et la conception des codes définis par des graphes bipartites et décodables par des algorithmes itératifs ont permis le développement de systèmes de correction d'erreurs, avec des performances de plus en plus proches la limite théorique de Shannon. Dans ce contexte, un rôle déterminant a été joué par la famille des codes à matrice de parité creuse, appelés codes LDPC (pour " Low-Density Parity-Check ", en anglais), introduit par Gallager au début des années 60 et décrits plus tard en termes de graphes bipartites. Négligés pendant de longues années, ces codes ont été redécouverts à la fin des années 90, après que la puissance du décodage itératif a été mise en évidence grâce à l'invention des Turbo-codes. Ce n'est qu'au début des années 2000 que les techniques nécessaires à l'analyse et l'optimisation des codes LDPC ont été développées, techniques qui ont permis ensuite la construction des codes avec des performances asymptotiques proches de la limite de Shannon. Cette remarquable avancée a motivé l'intérêt croissant de la communauté scientifique et soutenu le transfert rapide de cette technologie vers le secteur industriel. Plus récemment, un intérêt tout particulier a été porté aux codes LDPC définis sur des alphabets non-binaires, grâce notamment à leur meilleure capacité de correction en " longueur finie ". Bien que Gallager ait déjà proposé l'utilisation des alphabets non-binaires, en utilisant l'arithmétique modulaire, les codes LDPC non-binaires définis sur les corps finis n'ont étés étudiés qu'à partir de la fin des années 90. Il a été montré que ces codes offrent de meilleures performances que leurs équivalents binaires lorsque le bloc codé est de longueur faible à modérée, ou lorsque les symboles transmis sur le canal sont eux-mêmes des symboles non- binaires, comme par exemple dans le cas des modulations d'ordre supérieur ou des canaux à antennes multiples. Cependant, ce gain en performance implique un coût non négligeable en termes de complexité de décodage, qui peut entraver l'utilisation des codes LDPC non binaires dans des systèmes réels, surtout lorsque le prix à payer en complexité est plus important que le gain en performance. Cette thèse traite de l'analyse et de la conception des codes LDPC non binaires pour des canaux à évanouissements. L'objectif principal de la thèse est de démontrer que, outre le gain en performance en termes de capacité de correction, l'emploi des codes LDPC non binaires peut apporter des bénéfices supplémentaires, qui peuvent compenser l'augmentation de la complexité du décodeur. La " flexibilité " et la " diversité " représentent les deux bénéfices qui seront démontrées dans cette thèse. La " flexibilité " est la capacité d'un système de codage de pouvoir s'adapter à des débits (rendements) variables tout en utilisant le même encodeur et le même décodeur. La " diversité " se rapporte à sa capacité d'exploiter pleinement l'hétérogénéité du canal de communication. La première contribution de cette thèse consiste à développer une méthode d'approximation de l'évolution de densité des codes LDPC non-binaires, basée sur la simulation Monte-Carlo d'un code " infini ". Nous montrons que la méthode proposée fournit des estimations très fines des performances asymptotiques des codes LDPC non-binaires et rend possible l'optimisation de ces codes pour une large gamme d'applications et de modèles de canaux. La deuxième contribution de la thèse porte sur l'analyse et la conception de système de codage flexible, utilisant des techniques de poinçonnage. Nous montrons que les codes LDPC non binaires sont plus robustes au poinçonnage que les codes binaires, grâce au fait que les symboles non-binaires peuvent être partialement poinçonnés. Pour les codes réguliers, nous montrons que le poinçonnage des codes non-binaires obéit à des règles différentes, selon que l'on poinçonne des symboles de degré 2 ou des symboles de degré plus élevé. Pour les codes irréguliers, nous proposons une procédure d'optimisation de la " distribution de poinçonnage ", qui spécifie la fraction de bits poinçonnés par symbole non-binaire, en fonction du degré du symbole. Nous présentons ensuite des distributions de poinçonnage optimisées pour les codes LDPC non binaires, avec des performances à seulement 0,2 - 0,5 dB de la capacité, pour des rendements poinçonnés variant de 0,5 à 0,9. La troisième contribution de la thèse concerne les codes LDPC non binaires transmis sur un canal de Rayleigh à évanouissements rapides, pour lequel chaque symbole modulé est affecté par un coefficient d'évanouissement différent. Dans le cas d'une correspondance biunivoque entre les symboles codés et les symboles modulés (c.-à-d. lorsque le code est définit sur un corps fini de même cardinalité que la constellation utilisée), certains symboles codés peuvent être complètement noyés dans le bruit, dû aux évanouissements profonds du canal. Afin d'éviter ce phénomène, nous utilisons un module d'entrelacement au niveau bit, placé entre l'encodeur et le modulateur. Au récepteur, le module de désentrelacement apporte de la diversité binaire en entrée du décodeur, en atténuant les effets des différents coefficients de fading. Nous proposons un algorithme d'entrelacement optimisé, inspirée de l'algorithme " Progressive Edge-Growth " (PEG). Ainsi, le graphe bipartite du code est élargi par un nouvel ensemble de nœuds représentant les symboles modulés, et l'algorithme proposé établit des connections entre les nœuds représentant les symboles modulés et ceux représentant les symboles codés, de manière à obtenir un graphe élargi de maille maximale. Nous montrons que l'entrelaceur optimisé permet d'obtenir un gain de performance par rapport à un entrelaceur aléatoire, aussi bien en termes de capacité de correction que de détection d'erreurs. Enfin, la quatrième contribution de la thèse consiste en un schéma de codage flexible, permettant d'atteindre la diversité maximale d'un canal à évanouissements par blocs. La particularité de notre approche est d'utiliser des codes Root-LDPC non binaires couplés avec des codes multiplicatifs non binaires, de manière à ce que le rendement de codage puisse facilement s'adapter au nombre de blocs d'évanouissement. Au niveau du récepteur, une simple technique de combinaison de diversité est utilisée en entrée du décodeur. Comme conséquence, la complexité du décodage reste inchangée quel que soit le nombre de blocs d'évanouissement et le rendement du code utilisé, tandis que la technique proposée apporte un réel bénéfice en termes de capacité de correction.

Cette thèse se concentre sur l’amélioration conjointe de l'efficacité spectrale et de l'efficacité en puissance de schémas de transmission par satellite. L’émergence de nouveaux services et l'augmentation du nombre d’acteurs dans le domaine nécessitent de disposer de débits de plus en plus importants avec des ressources de plus en plus limitées. Les progrès réalisés ces dernières années sur la technologie embarquée et dans le domaine des communications numériques permettent de considérer des schémas de transmission à plus haute efficacité spectrale et en puissance. Cependant, l’enjeu majeur des schémas de transmission proposes actuellement reste de rentabiliser les ressources disponibles. L’étude développée dans cette thèse explore les possibilités d’amélioration conjointe de l’efficacité spectrale et de l’efficacité en puissance en proposant la combinaison de la modulation Cyclic Code-Shift-Keying (CCSK), dont l’efficacité en puissance augmente avec l’élévation du degré de la modulation, avec une technique de multiplexage par codage de type Code-Division Multiplexing (CDM) pour pallier la dégradation de l’efficacité spectrale liée à l’étalement du spectre induit par la modulation CCSK. Deux approches basées sur l’utilisation de séquences de Gold de longueur N sont définies: Une approche multi-flux avec un décodeur sphérique optimal en réception. La complexité liée à l’optimalité du décodeur conduit à des valeurs d'efficacité spectrale limitées mais l’étude analytique des performances, vérifiée par des simulations, montre une augmentation de l'efficacité en puissance avec l'efficacité spectrale. Une approche mono-flux justifiée par l’apparition de redondance dans les motifs résultant du multiplexage des séquences. L’approche mono-flux propose des valeurs d’efficacité spectrale équivalente aux schémas retenus dans le standard DVB-S2 avec une amélioration de l’efficacité en puissance à partir d’un certain seuil de rapport signal à bruit par rapport à ces schémas. Par la suite, l'étude porte sur la transposition de plusieurs symboles de modulation sur les porteuses d’un système OFDM et sur les bénéfices et avantages d’une telle approche. Elle se conclut sur l’apport d’un codage canal basé sur des codes par bloc non binaires Reed-Solomon et LDPC. La forme d’onde proposée offre des points de fonctionnement à haute efficacité spectrale et haute efficacité en puissance avec des perspectives intéressantes. Dans le contexte actuel, son application reste limitée par ses fluctuations d’amplitude mais est envisageable dans un contexte de transmission multiporteuse, comme attendu dans les années à venir. / This thesis focuses on jointly improving the spectral efficiency and the power efficiency of satellite transmission schemes. The emergence of new services and the increasing number of actors in this field involve higher transmission rates with increasingly limited resources. Recent progress in the embedded technologies and in digital communications offered to consider transmission schemes with higher spectral and power efficiency. Nevertheless, the major current challenge consists in making efficient use of resources. The study developed in this thesis explores the possibilities of jointly improving the spectral and power efficiency by offering a combination of the Cyclic-Code-Shift Keying modulation (CCSK), which power efficiency increases with the degree of modulation, with a multiplexing technique such as Code-Division Multiplexing (CDM) to offset the deterioration on the spectral efficiency due to the spread spectrum induced by CCSK. Two approaches based on the use of Gold sequences of length N are defined : A multi-stream approach with an optimal receiver implemented through sphere decoding. The complexity due to the receiver optimality leads to limited spectral efficiencies but the study of performance, confirmed by simulations, shows an increase in power efficiency with spectral efficiency. A single-stream approach justified by the appearance of redundancy in the patterns following the sequences multiplexing. The single-stream approach offers spectral efficiencies equivalent to the adopted schemes in the DVB-S2 standard, with improved power efficiency from a certain level of signal to noise ratio compared to those schemes. Subsequently, the study focuses on the implementation of several modulation symbols on the subcarriers of an OFDM modulator and the benefits and advantages of such an approach. It concludes with the contribution of channel coding based on nonbinary block codes such as Reed-Solomon and LDPC codes. The proposed waveform offers operating points with high spectral efficiency and high power efficiency with attractive perspectives. In the current context, its application is limited by its amplitude fluctuations but is possible in a multicarrier transmission context, as expected in the years to come.

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

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.