Evaluation of soft output decoding for turbo codes is presented. Coding theory related to this research is studied, including convolutional encoding and Viterbi decoding. Recursive systematic convolutional (RSC) codes and nonuniform interleavers commonly used in turbo code encoder design are analyzed. Fundamentals such as reliability estimation, log-likelihood algebra, and soft channel outputs for soft output Viterbi algorithm (SOVA) turbo code decoding are examined. The modified Viterbi metric that incorporates a-priori information used for SOVA decoding is derived. A low memory implementation of the SOVA decoder is shown. The iterative SOVA turbo code decoding algorithm is described with illustrative examples. The performance of turbo codes are evaluated through computer simulation. It has been found that the SOVA turbo code decoding algorithm, as described in the literature, did not perform as well as the published results. Modifications to the decoding algorithm are suggested. The simulated turbo code performance results shown after these modifications more closely match with current published research work. / Master of Science

ITC/USA 2007 Conference Proceedings / The Forty-Third Annual International Telemetering Conference and Technical Exhibition / October 22-25, 2007 / Riviera Hotel & Convention Center, Las Vegas, Nevada / Next generation satellite communication systems require efficient coding schemes that enable high data rates, require low overhead, and have excellent bit error rate performance. A newly rediscovered class of block codes called Low Density Parity Check (LDPC) codes has the potential to revolutionize forward error correction (FEC) because of the very high coding rates. This paper presents a brief overview of LDPC coding and decoding. An LDPC algorithm developed by Goddard Space Flight Center is discussed, and an overview of an accompanying VHDL development by L-3 Communications Cincinnati Electronics is presented.

The thesis examines two related combinatorial objects, namely fingerprinting codes and separating hash families. Fingerprinting codes are combinatorial objects that have been studied for more than 15 years due to their applications in digital data copyright protection and their combinatorial interest. Four well-known types of fingerprinting codes are studied in this thesis; traceability, identifiable parent property, secure frameproof and frameproof. Each type of code is named after the security properties it guarantees. However, the power of these four types of fingerprinting codes is limited by a certain condition. The first known attempt to go beyond that came out in the concept of two-level traceability codes, introduced by Anthapadmanabhan and Barg (2009). This thesis extends their work to the other three types of fingerprinting codes, so in this thesis four types of two-level fingerprinting codes are defined. In addition, the relationships between the different types of codes are studied. We propose some first explicit non-trivial con- structions for two-level fingerprinting codes and provide some bounds on the size of these codes. Separating hash families were introduced by Stinson, van Trung, and Wei as a tool for creating an explicit construction for frameproof codes in 1998. In this thesis, we state a new definition of separating hash families, and mainly focus on improving previously known bounds for separating hash families in some special cases that related to fingerprinting codes. We improve upper bounds on the size of frameproof and secure frameproof codes under the language of separating hash families.

Les code en métrique rang attirent l’attention depuis quelques années en raison de leur application possible au codage réseau linéaire aléatoire (random linear network coding), à la cryptographie à clé publique, au codage espace-temps et aux systèmes de stockage distribué. Une construction de codes algébriques en métrique rang de cardinalité optimale a été introduite par Delsarte, Gabidulin et Roth il y a quelques décennies. Ces codes sont considérés comme l’équivalent des codes de Reed – Solomon et ils sont basés sur l’évaluation de polynômes linéarisés. Ils sont maintenant appelés les codes de Gabidulin. Cette thèse traite des codes en bloc et des codes convolutifs en métrique rang avec l’objectif de développer et d’étudier des algorithmes de décodage efficaces pour ces deux classes de codes. Après une introduction dans le chapitre 1, le chapitre 2 fournit une introduction rapide aux codes en métrique rang et leurs propriétés. Dans le chapitre 3, on considère des approches efficaces pour décoder les codes de Gabidulin. Lapremière partie de ce chapitre traite des algorithmes rapides pour les opérations sur les polynômes linéarisés. La deuxième partie de ce chapitre résume tout d’abord les techniques connues pour le décodage jusqu’à la moitié de la distance rang minimale (bounded minimum distance decoding) des codes de Gabidulin, qui sont basées sur les syndromes et sur la résolution d’une équation clé. Ensuite, nous présentons et nous prouvons un nouvel algorithme efficace pour le décodage jusqu’à la moitié de la distance minimale des codes de Gabidulin. Le chapitre 4 est consacré aux codes de Gabidulin entrelacés et à leur décodage au-delà de la moitié de la distance rang minimale. Dans ce chapitre, nous décrivons d’abord les deux approches connues pour le décodage unique et nous tirons une relation entre eux et leurs probabilités de défaillance. Ensuite, nous présentons un nouvel algorithme de décodage des codes de Gabidulin entrelacés basé sur l’interpolation des polynômes linéarisés. Nous prouvons la justesse de ses deux étapes principales — l’interpolation et la recherche des racines — et montrons que chacune d’elles peut être effectuée en résolvant un système d’équations linéaires. Jusqu’à présent, aucun algorithme de décodage en liste en temps polynomial pour les codes de Gabidulin n’est connu et en fait il n’est même pas clair que cela soit possible. Cela nous a motivé à étudier, dans le chapitre 5, les possibilités du décodage en liste en temps polynomial des codes en métrique rang. Cette analyse est effectuée par le calcul de bornes sur la taille de la liste des codes en métriques rang en général et des codes de Gabidulin en particulier. Étonnamment, les trois nouvelles bornes révèlent toutes un comportement des codes en métrique rang qui est complètement différent de celui des codes en métrique de Hamming. Enfin, dans le chapitre 6, on introduit des codes convolutifs en métrique rang. Ce qui nous motive à considérer ces codes est le codage réseau linéaire aléatoire multi-shot, où le réseau inconnu varie avec le temps et est utilisé plusieurs fois. Les codes convolutifs créent des dépendances entre les utilisations différentes du réseau aun de se adapter aux canaux difficiles. Basé sur des codes en bloc en métrique rang (en particulier les codes de Gabidulin), nous donnons deux constructions explicites des codes convolutifs en métrique rang. Les codes en bloc sous-jacents nous permettent de développer un algorithme de décodage des erreurs et des effacements efficace pour la deuxième construction, qui garantit de corriger toutes les séquences d’erreurs de poids rang jusqu’à la moitié de la distance rang active des lignes. Un résumé et un aperçu des problèmes futurs de recherche sont donnés à la fin de chaque chapitre. Finalement, le chapitre 7 conclut cette thèse. / Rank-metric codes recently attract a lot of attention due to their possible application to network coding, cryptography, space-time coding and distributed storage. An optimal-cardinality algebraic code construction in rank metric was introduced some decades ago by Delsarte, Gabidulin and Roth. This Reed–Solomon-like code class is based on the evaluation of linearized polynomials and is nowadays called Gabidulin codes. This dissertation considers block and convolutional codes in rank metric with the objective of designing and investigating efficient decoding algorithms for both code classes. After giving a brief introduction to codes in rank metric and their properties, we first derive sub-quadratic-time algorithms for operations with linearized polynomials and state a new bounded minimum distance decoding algorithm for Gabidulin codes. This algorithm directly outputs the linearized evaluation polynomial of the estimated codeword by means of the (fast) linearized Euclidean algorithm. Second, we present a new interpolation-based algorithm for unique and (not necessarily polynomial-time) list decoding of interleaved Gabidulin codes. This algorithm decodes most error patterns of rank greater than half the minimum rank distance by efficiently solving two linear systems of equations. As a third topic, we investigate the possibilities of polynomial-time list decoding of rank-metric codes in general and Gabidulin codes in particular. For this purpose, we derive three bounds on the list size. These bounds show that the behavior of the list size for both, Gabidulin and rank-metric block codes in general, is significantly different from the behavior of Reed–Solomon codes and block codes in Hamming metric, respectively. The bounds imply, amongst others, that there exists no polynomial upper bound on the list size in rank metric as the Johnson bound in Hamming metric, which depends only on the length and the minimum rank distance of the code. Finally, we introduce a special class of convolutional codes in rank metric and propose an efficient decoding algorithm for these codes. These convolutional codes are (partial) unit memory codes, built upon rank-metric block codes. This structure is crucial in the decoding process since we exploit the efficient decoders of the underlying block codes in order to decode the convolutional code.

No description available.

No description available.

La théorie des codes géométriques s'est développée au début des années 80 sur l'impulsion d'un article de V.D. Goppa publié en 1981. Etant donnée une courbe algébrique projective lisse X sur un corps fini, on dispose de deux constructions de codes correcteurs d'erreurs. Une construction dite fonctionnelle qui fait intervenir certaines fonctions rationnelles sur X et une construction différentielle qui fait appel à certaines 1-formes différentielles rationnelles sur X . L'étude de ces codes construits sur des courbes a donné lieu à la publication de plusieurs centaines d'articles. Parallèlement à ces travaux, une généralisation de la construction fonctionnelle à des variétés algébriques de dimension quelconque est proposée par Y. Manin dans un article publié en 1984. On dénombre quelques dizaines de travaux publiés portant sur l'étude de tels codes. Cependant, aucun développement n'a été effectué dans le sens d'une généralisation de la construction différentielle. Dans cette thèse nous proposons une construction différentielle de codes sur des surfaces algébriques. Nous étudions ensuite les propriétés de ces codes et plus particulièrement leurs relations avec les codes fonctionnels. De façon un peu surprenante, on observe l'apparition d'une différence majeure avec le cas des courbes. En effet, si sur une courbe l'orthogonal d'un code fonctionnel est différentiel, ce fait est en général faux sur une surface. Ce résultat motive l'étude des orthogonaux de codes fonctionnels. Des formules pour l'estimation de la distance minimale de tels codes sont données en utilisant des propriétés de systèmes linéaires sur une variété. On montre également que, sous certaines conditions sur la surface, ces codes sont somme de codes différentiels et que des réponses à certains problèmes ouverts de géométrie algébrique "à la Bertini" fourniraient des informations supplémentaires sur les paramètres de ces codes.

Masters of Science / Codes Related to and Derived from Hamming Graphs T.R Muthivhi M.Sc thesis, Department of Mathematics, University of Western Cape For integers n; k 1; and k n; the graph 􀀀k n has vertices the 2n vectors of Fn2 and adjacency de ned by two vectors being adjacent if they di er in k coordinate positions. In particular, 􀀀1 n is the classical n-cube, usually denoted by H1(n; 2): This study examines the codes (both binary and p-ary for p an odd prime) of the row span of adjacency and incidence matrices of these graphs. We rst examine codes of the adjacency matrices of the n-cube. These have been considered in [14]. We then consider codes generated by both incidence and adjacency matrices of the Hamming graphs H1(n; 3) [12]. We will also consider codes of the line graphs of the n-cube as in [13]. Further, the automorphism groups of the codes, designs and graphs will be examined, highlighting where there is an interplay. Where possible, suitable permutation decoding sets will be given.

In mobile communications, using multiple transmit and receive antennas has shown considerable improvement over single antenna systems. The performance increase can be characterized by more reliable throughput obtained through diversity and the higher achievable data rate through spatial multiplexing. The combination of multiple-input multiple-output (MIMO) wireless technology with the IEEE 802.16e-2005 (WiMAX) standard has been recognized as one of the most promising technologies with the advent of next generation broadband wireless communications. The dissertation introduces a performance evaluation of modern multi-antenna coding techniques on a MIMO-WiMAX platform developed to be capable of simulating space-selective, time-selective and frequency-selective fading conditions, which are known as triply-selective fading conditions. A new concatenated space-time-frequency low-density parity check (LDPC) code is proposed for high performance MIMO systems, where it is shown that the newly defined coding technique outperforms a more conventional approach by concatenating space-time blocks with LDPC codes. The analysis of the coding techniques in realistic mobile environments, as well as the proposed STFC-LDPC code, can form a set of newly defined codes, complementing the current coding schemes defined in the WiMAX standard. / Dissertation (MEng)--University of Pretoria, 2009. / Electrical, Electronic and Computer Engineering / unrestricted

>Magister Scientiae - MSc / For integers n, k 2:: 1, and k ~ n, the graph r~has vertices the 2n vectors of lF2 and adjacency defined by two vectors being adjacent if they differ in k coordinate positions. In particular, r~is the classical n-cube, usually denoted by Hl (n, 2). This study examines the codes (both binary and p-ary for p an odd prime) of the row span of adjacency and incidence matrices of these graphs. We first examine codes of the adjacency matrices of the n-cube. These have been considered in [14]. We then consider codes generated by both incidence and adjacency matrices of the Hamming graphs Hl(n,3) [12]. We will also consider codes of the line graphs of the n-cube as in [13]. Further, the automorphism groups of the codes, designs and graphs will be examined, highlighting where there is an interplay. Where possible, suitable permutation decoding sets will be given.