Dissertations / Theses on the topic 'Non-binary codes'

Thesis (M.S.)--Wichita State University, College of Engineering, Dept. of Electrical and Computer Engineering.
"December 2006." Title from PDF title page (viewed on Oct. 29, 2007). Thesis adviser: Kamesh Namuduri. Includes bibliographic references (leaves 47-50).

The introduction of turbo codes in 1993 provided a code structure that could approach Shannon limit performance whilst remaining practically decodeable. Much subsequent work has focused on this remarkable structure, attempting to explain its performance and to extend or modify it. This thesis builds on this research providing insights into the convergence behaviour of the iterative decoder for turbo codes and examining the potential of turbo codes constructed from non-binary component codes. The first chapter of this thesis gives a brief history of coding theory, providing context for the work. Chapter two explains in detail both the turbo encoding and decoding structures considered. Chapter three presents new work on convergence phenomena observed in the iterative decoding process. These results emphasise the dynamic nature of the decoder and allow for both a stopping criteria and ARQ scheme to be proposed. Chapters four and five present the work on non-binary turbo codes. First the problem of choosing good component codes is discussed and an achievability bound on the dominant parameter affecting their performance is derived. Searches for good component codes over a number of small rings are then conducted, and simulation results presented. The new results, and suggestions for further work are summarised in the conclusion of Chapter six.

In this thesis, we propose a new stochastic decoding algorithm for non-binary LDPC codes with d_v = 2, which is based on the concept of a mutliset, a generalization of the set that allows for multiple occurrences of the same element. The algorithm is called Adaptive Multiset Stochastic Algorithm (AMSA) and represents probability mass functions as multisets, which simplifies the structure of the variable node. AMSA reduces the run-time complexity of one decoding cycle to O(q) for regular memory architectures, and to O(1) if a custom SRAM architecture is used. Two fully-parallel AMSA decoders are implemented on FPGA for two versions of a (192,96) (2,4)-regular code, one over GF(64) and the other over GF(256), both achieving a maximum clock frequency of 108 MHz and a throughput of 65 Mbit/s at E_b/N_0 = 2.4 dB. We also propose an SRAM architecture for ASIC implementations that reduces the run-time complexity of a decoding cycle to O(1) and achieves a throughput of 698 Mbit/s at the same noise level. The algorithm has a frame error rate (FER) of 3.5 x 10^-7 at E_b/N_0 = 2.4 dB when using the GF(256) version of the code. To the best of our knowledge, the implemented decoders are the first fully-parallel non-binary LDPC decoders over GF(64) and GF(256) reported in the literature.
Dans cette thèse, nous proposons un nouvel algorithme de décodage stochastique pour des codes LDPC non-binaires avec d_v = 2, qui est basé sur le concept de multiensemble, une généralisation de l'ensemble où un élément peut apparaître plusieurs fois. L'algorithme est appelé Algorithme Stochastique à Multiensembles Adaptifs (ASMA) et représente des fonctions de masse comme multiensembles, ce qui simplifie la structure du nœud de variable. ASMA réduit la complexité d'exécution d'une itération de décodage à O(q) pour les architectures de mémoire ordinaire, et O(1) si une architecture SRAM personnalisée est utilisée. Deux décodeurs ASMA tout-parallèles sont mis en œuvre sur FPGA pour deux versions d'un code (192,96) (2,4)-réguliers, l'un sur GF(64) et le l'autre sur GF(256), et tous les deux atteignent une fréquence d'horloge maximale de 108 MHz et un débit de 65 Mbit/s à E_b/N_0 = 2.4 dB. Nous proposons aussi une architecture SRAM pour les implémentations ASIC qui réduit la complexité d'exécution d'un cycle de décodage à O(1) et atteint 698 Mbit/s au même niveau de bruit. L'algorithme a un taux d'erreur de trame de 3.5 x 10^-7 à E_b/N_0 = 2.4 dB pour la version GF(256) du code. Au meilleur de notre connaissance, les décodeurs présentés ici sont les premiers décodeurs LDPC non-binaires opérant sur GF(64) et GF(256) et tout-parallèles rapportés dans la littérature.

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

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.

4 ABSTRACT Tremendous amount of research has been conducted in modern coding theory in the past few years and much of the work has been done in developing new coding techniques. Low density parity check (LDPC) codes are class of linear block error correcting codes which provide capacity performance on a large collection of data transmission and storage channels while Root LDPC codes in this thesis work are admitting implementable decoders with manageable complexity. Furthermore, work has been conducted to develop graphical methods to represent LDPC codes. This thesis implement one of the LDPC kind “Root LDPC code” using iterative method and calculate its threshold level for binary and non-binary Root LDPC code. This threshold value can serve as a starting point for further study on this topic. We use C++ as tool to simulate the code structure and parameters. The results show that non-binary Root LDPC code provides higher threshold value as compare to binary Root LDPC code.
postal address: Björnkullaringen 26, LGH 1029 14151 Huddinge Stockholm Sweden. Mobile: +46-720 490 967

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.

Les systèmes de téléphonie mobile de 4ème et 5ème générations ont adopté comme techniques de codage de canal les turbocodes, les codes LDPC et les codes polaires binaires. Cependant, ces codes ne permettent pas de répondre aux exigences, en termes d’efficacité spectrale et de fiabilité, pour les réseaux de communications futurs (2030 et au-delà), qui devront supporter de nouvelles applications telles que les communications holographiques, les véhicules autonomes, l’internet tactile … Un premier pas a été fait il y a quelques années vers la définition de codes correcteurs d’erreurs plus puissants avec l’étude de codes LDPC non binaires, qui ont montré une meilleure performance que leurs équivalents binaires pour de petites tailles de code et/ou lorsqu'ils sont utilisés sur des canaux non binaires. En contrepartie, les codes LDPC non binaires présentent une complexité de décodage plus importante que leur équivalent binaire. Des études similaires ont commencé à émerger du côté des turbocodes. Tout comme pour leurs homologues LDPC, les turbocodes non binaires présentent d’excellentes performances pour de petites tailles de blocs. Du point de vue du décodage, les turbocodes non binaires sont confrontés au même problème d’augmentation de la complexité de traitement que les codes LDPC non binaire. Dans cette thèse nous avons proposé une nouvelle structure de turbocodes non binaires en optimisant les différents blocs qui la constituent. Nous avons réduit la complexité de ces codes grâce à la définition d’un algorithme de décodage simplifié. Les codes obtenus ont montré des performances intéressantes en comparaison avec les codes correcteur d’erreur de la littérature
Nowadays communication standards have adopted different binary forward error correction codes. Turbo codes were adopted for the long term evolution standard, while binary LDPC codes were standardized for the fifth generation of mobile communication (5G) along side with the polar codes. Meanwhile, the focus of the communication community is shifted towards the requirement of beyond 5G standards. Networks for the year 2030 and beyond are expected to support novel forward-looking scenarios, such as holographic communications, autonomous vehicles, massive machine-type communications, tactile Internet… To respond to the expected requirements of new communication systems, non-binary LDPC codes were defined, and they are shown to achieve better error correcting performance than the binary LDPC codes. This performance gain was followed by a high decoding complexity, depending on the field order.Similar studies emerged in the context of turbo codes, where the non-binary turbo codes were defined, and have shown promising error correcting performance, while imposing high complexity. The aim of this thesis is to propose a new low-complex structure of non-binary turbocodes. The constituent blocks of this structure were optimized in this work, and a new low complexity decoding algorithm was proposed targeting a future hardware implementation. The obtained results are promising, where the proposed codes are shown to outperform existing binary and non-binary codes from the literature

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.

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

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.

One of the facets of the mobile or wireless environment is that errors quite often occur in bursts. Thus, strong codes are required to provide protection against such errors. This in turn motivates the employment of decoding algorithms which are simple to implement, yet are still able to attempt to take the dependence or memory of the channel model into account in order to give optimal decoding estimates. Furthermore, such algorithms should be able to be applied for a variety of channel models and signalling alphabets. The research presented within this thesis describes a number of algorithms which can be used with linear block codes. Given the received word, these algorithms determine the symbol which was most likely transmitted, on a symbol-by-symbol basis. Due to their relative simplicity, a collection of algorithms for memoryless channels is reported first. This is done to establish the general style and principles of the overall collection. The concept of matrix diagonalisation may or may not be applied, resulting in two different types of procedure. Ultimately, it is shown that the choice between them should be motivated by whether storage space or computational complexity has the higher priority. As with all other procedures explained herein, the derivation is first performed for a binary signalling alphabet and then extended to fields of prime order. These procedures form the paradigm for algorithms used in conjunction with finite state channel models, where errors generally occur in bursts. In such cases, the necessary information is stored in matrices rather than as scalars. Finally, by analogy with the weight polynomials of a code and its dual as characterised by the MacWilliams identities, new procedures are developed for particular types of Gilbert-Elliott channel models. Here, the calculations are derived from three parameters which profile the occurrence of errors in those models. The decoding is then carried out using polynomial evaluation rather than matrix multiplication. Complementing this theory are several examples detailing the steps required to perform the decoding, as well as a collection of simulation results demonstrating the practical value of these algorithms.

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.

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

The Internet has fundamentally changed the way of modern communication. Current trends indicate that high-capacity demands are not going to be saturated anytime soon. From Shannon's theory, we know that information capacity is a logarithmic function of signal-to-noise ratio (SNR), but a linear function of the number of dimensions. Ideally, we can increase the capacity by increasing the launch power, however, due to the nonlinear characteristics of silica optical fibers that imposes a constraint on the maximum achievable optical-signal-to-noise ratio (OSNR). So there exists a nonlinear capacity limit on the standard single mode fiber (SSMF). In order to satisfy never ending capacity demands, there are several attempts to employ additional degrees of freedom in transmission system, such as few-mode fibers (FMFs), which can dramatically improve the spectral efficiency. On the other hand, for the given physical links and network equipment, an effective solution to relax the OSNR requirement is based on forward error correction (FEC), as the response to the demands of high speed reliable transmission. In this dissertation, we first discuss the model of FMF with nonlinear effects considered. Secondly, we simulate the FMF based OFDM system with various compensation and modulation schemes. Thirdly, we propose tandem-turbo-product nonbinary byte-interleaved coded modulation (BICM) for next-generation high-speed optical transmission systems. Fourthly, we study the Q factor and mutual information as threshold in BICM scheme. Lastly, an experimental study of the limits of nonlinearity compensation with digital signal processing has been conducted.

碩士
國立臺灣科技大學
電子工程系
96
Because of the rapid and widespread development of communication techniques, transmission style has developed from wire communication into wireless communication. It is necessary that we apply channel coding techniques in data transmission when we transmit data in wireless enviroment, which typically suffers from serious signal fading and degradation. Turbo codes are very powerful error correcting for added white Gaussian noise (AWGN) channel. In this thesis, we consider a non-binary turbo codes system, including non-binary systematic (NBS) turbo code and non-binary non-systematic (NBNS) turbo code. The performances of those techniques mentioned above are evaluated by computer simulation in added white Gaussian noise (AWGN) channels. Then, we compare those two techniques. Besides, this thesis also combines non-binary systematic convolutional code and turbo trellis-coded modulation. Encoded signals are transmitted in AWGN channel. We employ turbo trellis-coded modulation decoder and non-binary systematic convolutional code decoder in the receiver. Finally, this thesis also uses extrinsic information transfer chart (EXIT chart) to describe the mutual information transfer characteristics of the decoders in the receiver. And then we analyze the convergence behavior of the turbo system. The exchange of extrinsic information is visualized as a decoding trajectory in the extrinsic information transfer chart. This allows the prediction of turbo cliff position and bit error rate after an arbitrary number of iterations.

Shannon showed that the codes with random-like codeword weight distribution are capable of approaching the channel capacity. However, the random-like property can be achieved only in codes with long-length codewords. On the other hand, the decoding complexity for a random-like codeword increases exponentially with its length. Therefore, code designers are combining shorter and simpler codes in a pseudorandom manner to form longer and more powerful codewords. In this research, a method for designing non-binary compound codes with moderate to high coding rate is proposed. Based on this method, non-binary single parity-check (SPC) codes are considered as component codes and different iterative decoding algorithms for decoding the constructed compound codes are proposed. The soft-input soft-output component decoders, which are employed for the iterative decoding algorithms, are constructed from optimal and sub-optimal a posteriori probability (APP) decoders. However, for non-binary codes, implementing an optimal APP decoder requires a large amount of memory. In order to reduce the memory requirement of the APP decoding algorithm, in the first part of this research, a modified form of the APP decoding algorithm is presented. The amount of memory requirement of this proposed algorithm is significantly less than that of the standard APP decoder. Therefore, the proposed algorithm becomes more practical for decoding non-binary block codes. The compound codes that are proposed in this research are constructed from combination of non-binary SPC codes. Therefore, as part of this research, the construction and decoding of the non-binary SPC codes, when SPC codes are defined over a finite ring of order q, are presented. The concept of finite rings is more general and it thus includes non-binary SPC codes defined over finite fields. Thereafter, based on production of non-binary SPC codes, a class of non-binary compound codes is proposed that is efficient for controlling both random-error and burst-error patterns and can be used for applications where high coding rate schemes are required. Simulation results show that the performance of the proposed codes is good. Furthermore, the performance of the compound code improves over larger rings. The analytical performance bounds and the minimum distance properties of these product codes are studied.
Thesis (Ph.D.)-University of KwaZulu-Natal, Durban, 2013.

A family of low-density lattice codes (LDLC) is studied based on Construction-A for lattices. The family of Construction-A codes is already known to contain a large capacity-achieving subset. Parallels are drawn between coset non-binary low-density parity-check (LDPC) codes and nested low-density Construction-A lattices codes. Most of the related research in LDPC domain assumes optimal power allocation to encoded codeword. The source coding problem of mapping message to power optimal codeword for any LDPC code is in general, NP-hard. In this thesis, we present a novel method for encoding and decoding lattice based on non-binary LDPC codes using message-passing algorithms.
text

Distributed coding is a new paradigm for video transmission, based on the Wyner-Ziv theorem. In this thesis, a new Wyner-Ziv codec was proposed using non-binary Low-Density Parity-Check (LDPC) codes. Non-binary LDPC codes, developed for use in channel coding, have been extended for source coding to compress correlated non-binary sources, such as video. The approach is based on considering the correlation as a virtual q-ary symmetric channel and applying the syndrome concept. The system considered focused on the compression of a equiprobable memoryless non-binary source with side information at the decoder. Results obtained through simulations demonstrated that for rates 1/2 and 3/4, the non-binary compression scheme performed better than the equivalent binary compression scheme. The nonbinary scheme, when extended for distributed video coding, produced the original frame with negligible error.
"December 2006."
Thesis (M.S.)--Wichita State University, College of Engineering, Dept. of Electrical and Computer Engineering.

This thesis is about non-binary convolutional turbo codes--codes constructed via parallel concatenation of two circular recursive systematic convolutional (CRSC) encoders linked by an interleaver. The focus of the work is on the understanding and design of non-binary convolutional turbo codes. This includes investigation of central components that influence non-binary convolutional turbo code performances, such as the component encoders and the interleaver, as well as the procedure of iterative decoding. The investigations are carried out for transmission on additive white Gaussian noise channels. First, this thesis presents the theoretical background of channel coding and turbo coding. Next, a general and efficient maximum a posteriori (MAP) soft-input soft-output (SISO) decoding algorithm is presented. And then, the simplified Max-Log-MAP algorithm is derived for the double-binary convolutional turbo code, which follows the specifications of turbo coding/decoding in the DVB-RCS standard (Digital Video Broadcasting standard for Return Channel via Satellite), for twelve different block sizes and seven coding rates. The quantizer of turbo-decoder is designed for the goal of implementation. The effect of quantiztion on the performance of the decoder is analyzed and simulated. The correction coefficient of the simplified Max-Log-MAP algorithm is also discussed. The DVB-RCS standard turbo code uses quaternary alphabet and QPSK modulation. In order to increase the bandwidth efficiency, we present an extended nonbinary turbo-coding scheme consisting of 8-ary triple-binary codes combined with 8PSK modulation. A comprehensive study over AWGN channel is carried out to show the good performance of the concatenated codes, the influence of various parameters and the symbol-by-symbol Max-Log-MAP algorithm

碩士
國立中正大學
通訊工程學系
98
The achievable rate regions for Gaussian broadcast channels were established by Cover. Since then, how to attain the achievable rate regions becomes an open problem. In this thesis, we attempt to design non-binary low-density parity-check codes (LDPC) to approach the achievable rate regions for Gaussian broadcast channels. In order to analysis the code, we generalize several properties of non-binary LDPC codes. The permutation-invariance and symmetry properties of the proposed codes enable the approximation of the LLR vector as the Gaussian random vector which can be described by a single parameter. By this characteristic, we apply extrinsic information transfer (EXIT) charts to design non-binary LDPC codes for Gaussian broadcast channels. In addition, we adopt non-uniform signal constellations modulation to further obtain shaping gain. Simulation results show that the proposed codes approach achievable rate regions for Gaussian broadcast channels.

碩士
國立交通大學
電子工程學系 電子研究所
103
Non-binary LDPC codes extended from binary LDPC codes have outstanding decoding performance and combat burst error. Recently, stochastic computation is a promising decoding method for non-binary LDPC codes. Although the previous stochastic works reduce the complexity by using symbol-serial representation of probability, the stochastic decoder for non-binary LDPC codes still has bottlenecks for VLSI implementation due to high computational complexity and huge storage requirements. In this thesis, three novel stochastic decoders: TFM-based, probability-RHS-based, and log-RHS-based are proposed. All of proposed decoders are synthesized in UMC 90-nm process with high area efficiency due to our improved architectures which have low computational complexity and less storage requirements. Finally, the log-RHS-based stochastic decoder for a (168, 84) regular-(2, 4) code over GF(16) is fabricated in chip with 3.75 mm2 core area including testing consideration and 96.6% chip density. According to the measurement results, this decoder can support a throughput of 1.32 Gb/s under 368 MHz clock frequency with 1014 k gate counts and its power consumption is 588 mW. Compared with the related state-of-the-art designs, this work has not only 2 times improvement in hardware efficiency but also 7 times improvement in energy efficiency. Moreover, to the best of our knowledge, this is the first chip of stochastic decoder for non-binary LDPC codes.

碩士
國立中正大學
通訊工程研究所
106
The low density parity check (LDPC) codes is a kind of error correction codes. The error correction performance of LDPC codes is close to Shannon limit. Thus, LDPC codes are widely applied to various communication systems. In general, these codes can be described by Tanner graph. Finding and removing cycles are essential, because the cycles are generally considered to affect the performance of LDPC codes in Tanner graph. To extend this study with Galois field, non-binary LDPC codes have better capability of error correction to against noise, especially for short code length. However, the computational complexity and memory requirement are relatively high in the decoding process and code construction. In this paper, we propose a cycle counting algorithm based on cycle check table with less complexity. Basically, the cycle check table records the connection of nodes in Tanner Graph. Each layer in the table contains three rows. The first row has the record of target node. The second row denotes the previous node of the node in the first row, and the third row has the indices of the position of the node in previous row. In cycle searching, there are two conditions needed to be satisfied within cycle check table. The fist condition is that there are two same nodes in the first row of Nth layer. The second condition is that the nodes in previous path of two nodes which satisfy the first condition are different. To evaluate the proposed scheme, the computational complexity of proposed algorithm is , and the memory requirement is , where m is the number of parity check equations, n is the code block length, wr and wc are the row weight and column weight, respectively, wmax is the maximum of wr and wc, and N is the half length of cycles. The proposed algorithm can perform 9.44 times faster than the conventional method while considering the LDPC codes with code length 3000 and girth (g) 6. Besides, we can find the length longer than 2g-2 which is the upper bound of some existing methods. Eventually, the proposed algorithm is applied to the construction of parallelized-decoding LDPC codes over Galois field to improve the capability of LDPC codes.

碩士
國立清華大學
通訊工程研究所
100
Two versions of a new parallel symbol-flipping decoding algorithm for non-binary low-density parity-check (NB-LDPC) codes are proposed. Simulation results show that the soft-decision parallel symbol-flipping decoding outperforms quite a number of existing reliability-based message-passing algorithms. It provides an effective trade-off between error performance anddecoding complexity compared with the q-ary sum-product algorithm. The algorithm can be simplified to hard-decision parallel symbol-flipping decoding for applications in communication or storage systems where either soft information is not available or a simple decoder is needed. They are particularly effective for decoding NB-LDPC codes whose parity-check matrices have large row/column weights.

碩士
國立交通大學
電子研究所
101
Non-binary LDPC codes which extended from binary LDPC codes have ex- cellent decoding performance, and it is robust to various channel impairments. With the remarkable decoding ability, the high computational complexity and huge memory usage are the main challenges for non-binary LDPC codes to be imple- mented in practical. This thesis presents a high hardware efficient architecture for implementing non-binary LDPC decoder using improved Extended Min-Sum de- coding algorithm with layered scheduling. Based on the enhancement in the check node processing and efficient memory storing, the proposed decoder can double the throughput and have half reduction in storing the edge messages. Using 90- nm CMOS process technology, a (2,4)-regular non-binary QC-LDPC decoder over GF(26) is implemented. In the post-layout simulation results, the decoder through- put can reach over 100 Mbps at 10 iterations. Compared with state-of-the-art de- signs, this implementation has at least 4.3 times improvement in hardware effi- ciency (throughput-to-gate-count-ratio), and the decoding performance still keep competitive.

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

This dissertation investigates four methods for attacking stream ciphers that are based on nonlinear combining generators: -- Two exhaustive-search correlation attacks, based on the binary derivative and the Lempel-Ziv complexity measure. -- A fast-correlation attack utilizing the Viterbi algorithm -- A decimation attack, that can be combined with any of the above three attacks. These are ciphertext-only attacks that exploit the correlation that occurs between the ciphertext and an internal linear feedback shift-register (LFSR) of a stream cipher. This leads to a so-called divide and conquer attack that is able to reconstruct the secret initial states of all the internal LFSRs within the stream cipher. The binary derivative attack and the Lempel-Ziv attack apply an exhaustive search to find the secret key that is used to initialize the LFSRs. The binary derivative and the Lempel-Ziv complexity measures are used to discriminate between correct and incorrect solutions, in order to identify the secret key. Both attacks are ideal for implementation on parallel processors. Experimental results show that the Lempel-Ziv correlation attack gives successful results for correlation levels of p = 0.482, requiring approximately 62000 ciphertext bits. And the binary derivative attack is successful for correlation levels of p = 0.47, using approximately 24500 ciphertext bits. The fast-correlation attack, utilizing the Viterbi algorithm, applies principles from convolutional coding theory, to identify an embedded low-rate convolutional code in the pn-sequence that is generated by an internal LFSR. The embedded convolutional code can then be decoded with a low complexity Viterbi algorithm. The algorithm operates in two phases: In the first phase a set of suitable parity check equations is found, based on the feedback taps of the LFSR, which has to be done once only once for a targeted system. In the second phase these parity check equations are utilized in a Viterbi decoding algorithm to recover the transmitted pn-sequence, thereby obtaining the secret initial state of the LFSR. Simulation results for a 19-bit LFSR show that this attack can recover the secret key for correlation levels of p = 0.485, requiring an average of only 153,448 ciphertext bits. All three attacks investigated in this dissertation are capable of attacking LFSRs with a length of approximately 40 bits. However, these attacks can be extended to attack much longer LFSRs by making use of a decimation attack. The decimation attack is able to reduce (decimate) the size of a targeted LFSR, and can be combined with any of the three above correlation attacks, to attack LFSRs with a length much longer than 40 bits.
Dissertation (MEng (Electronic Engineering))--University of Pretoria, 2007.
Electrical, Electronic and Computer Engineering
unrestricted

It is believed that quantum computers would be able to solve complex problems more quickly than any other deterministic or probabilistic computer. Quantum computers basically exploit the rules of quantum mechanics for speeding up computations. However, building a quantum computer remains a daunting task. A quantum computer, as in any quantum mechanical system, is susceptible to decohorence of quantum bits resulting from interaction of the stored information with the environment. Error correction is then required to restore a quantum bit, which has changed due to interaction with external state, to a previous non-erroneous state in the coding subspace. Until now the methods for quantum error correction were mostly based on stabilizer codes over finite fields. The aim of this thesis is to construct quantum error correcting codes over finite Frobenius rings. We introduce stabilizer codes over quadratic algebra, which allows one to use the hamming distance rather than some less known notion of distance. We also develop propagation rules to build new codes from existing codes. Non binary codes have been realized as a gray image of linear Z4 code, hence the most natural class of ring that is suitable for coding theory is given by finite Frobenius rings as it allow to formulate the dual code similar to finite fields. At the end we show some examples of code construction along with various results of quantum codes over finite Frobenius rings, especially codes over Zm.

碩士
國立臺灣科技大學
電子工程系
96
Channel coding is one of the most popular topics of today’s wireless communications. It is an essential technique when the channel is noisy and fading. There are many kinds of channel coding, such as turbo code, convolutional code, Hamming code and LDPC code. LDPC (low-density parity-check) code has been shown to have excellent performance. It is the channel coding technique that we adopt in this thesis. In our research, we find that the performance of non-binary LDPC over GF(q) outperforms that of binary LDPC. However, non-binary LDPC has higher computation complexity. To solve this problem, we use FFT transform to reduce the complexity. It is pointed out that use of multiple antenna raises performance and gain for transmitting and receiving in wireless transmission. Therefore, we use space-time block code to provide diversity and capacity in this thesis. We also use OFDM to eliminate ISI. In combining OFDM and LDPC codes, power allocation to make each subcarriers have the same SNR(signal-to-noise ratio) is necessary and is the main topic of this thesis. Sub-carrier selection helps us to strike a balance between data transmission rate and BER(bit error rate) performance. In addition, we derive a scheme to determine the number of subcarriers to be retained when the acceptable BER is specified.

Bibliography: leaves 181-201.
ix, 201 leaves : ill. ; 30 cm.
Title page, contents and abstract only. The complete thesis in print form is available from the University Library.
This thesis investigates non-binary spread-spectrum multiple-access communications. The research considers wide generation techniques, system performance, how performance is influenced by the different properties of the codes, and how those properties relate to the code generation technqiue. The research refines the code design philosophy and investigates this by developing a novel code generation technique.
Thesis (Ph.D.)--University of Adelaide, Dept. of Electrical and Electronic Engineering, 1995?

Double binary convolutional turbo codes, using Circular Recursive Systematic Convolutional (CRSC) codes as component codes, have been shown to outperform binary turbo codes. These codes are adopted in the Digital Video Broadcasting--Return Channel via Satellite (DVB-RCS) standard. The outstanding coding performance of these codes intrigues the investigation of hardware implementation issues. In this thesis, first a simplified Max_Log_MAP algorithm is derived for the Non-binary convolutional turbo code, and then different aspects of the implementation issues of the decoder with VLSI are explored. In addition, a complete decoder VLSI design of non-binary convolutional turbo code for DVB/RCS will be presented. After discussing several quantization and normalization schemes, a new optimal renormalization approach will be proposed. With this new approach, the decoder can be speeded up considerably. In order to save area, a practical simplification method of branch metric calculation is introduced, which makes the whole design much more efficient. From an architectural point of view, an optimal full pipelined structure is designed with the forward path metric and backward path metric recursive circuits being optimized for speed and other functions including concise interleaver generation, data input, branch metric calculation being optimized for area. In the last part of this thesis, another pipelined area saving method is proposed. The design is modeled in Very high speed integrated circuit Hardware Description Language (VHDL) and synthesized on a single chip FPGA (Xilinx Virtex-E). According to the RTL level and gate level simulation results and the in-chip test result, the decoder can work up to 7 Mbits/s data rate at 6 iterations with VirtexE FPGA.

This thesis investigates channel-coded physical layer network coding, in which the relay directly transforms the noisy superimposed channel-coded packets received from the two end nodes, to the network-coded combination of the source packets. This is in contrast to the traditional multiple-access problem, in which the goal is to obtain each message explicitly at the relay. Here, the end nodes $A$ and $B$ choose their symbols, $S_A$ and $S_B$, from a small non-binary field, $\mathbb{F}$, and use non-binary PSK constellation mapper during the transmission phase. The relay then directly decodes the network-coded combination ${aS_A+bS_B}$ over $\mathbb{F}$ from the noisy superimposed channel-coded packets received from two end nodes. Trying to obtain $S_A$ and $S_B$ explicitly at the relay is overly ambitious when the relay only needs $aS_B+bS_B$. For the binary case, the only possible network-coded combination, ${S_A+S_B}$ over the binary field, does not offer the best performance in several channel conditions. The advantage of working over non-binary fields is that it offers the opportunity to decode according to multiple decoding coefficients $(a,b)$. As only one of the network-coded combinations needs to be successfully decoded, a key advantage is then a reduction in error probability by attempting to decode against all choices of decoding coefficients. In this thesis, we compare different constellation mappers and prove that not all of them have distinct performance in terms of frame error rate. Moreover, we derive a lower bound on the frame error rate performance of decoding the network-coded combinations at the relay. Simulation results show that if we adopt concatenated Reed-Solomon and convolutional coding or low density parity check codes at the two end nodes, our non-binary constellations can outperform the binary case significantly in the sense of minimizing the frame error rate and, in particular, the ternary constellation has the best frame error rate performance among all considered cases.

碩士
元智大學
通訊工程學系
99
This thesis discusses about using non-binary LDPC codes to resist the intentional multi-tone follower jamming for frequency hopping systems. We calculate the capacities for several jamming channels so that we can evaluate the influences to communication quality. When the channels are also Rayleigh faded or with AWGN, soft decoding is applied to the decoder and the probabilities of channel values for decoding are theoretically formulated. We especially focus on resisting two tone follower jamming by using different code rates of non-binary regular LDPC codes. By using the technique of ratio threshold test (RTT), the calculation of the probabilities of channel values can be simplified. Based on RTT, we propose a linear diversity combing detector to combat multi-tone follower jamming. Simulation results show that the code rates of non-binary LDPC codes can be increased when using these techniques and the system can achieve the purpose on resisting the multi-tone follower jamming.