International Telemetering Conference Proceedings / November 04-07, 1991 / Riviera Hotel and Convention Center, Las Vegas, Nevada / Shortened cyclic codes are not cyclic, but many cyclic shifts of various code words are still part of the shortened code set. This paper addresses the probability of false synchronization obtained through polynomial division of a serial shortened cyclic code stream in a “sliding” window correlator.

The study of coding theory aims to detect and correct the errors during the transmission of the data. It enhances the quality of data transmission and provides better control over the noisy channels.The perfect codes are collected and analyzed in the premises of the Hamming metric.This classification yields that there exists only a few perfect codes. The perfect codes do not guarantee the perfection by all means but just satisfy certain bound and properties. The detection and correction of errors is always very important for better data transmission.

Low-density parity-check (LDPC) codes have been intensively studied in the past decade for their capacity-approaching performance. LDPC code implementation complexity and the error-rate floor are still two significant unsolved issues which prevent their application in some important communication systems. In this dissertation, we make efforts toward solving these two problems by introducing the design of a class of LDPC codes called structured irregular repeat-accumulate (S-IRA) codes. These S-IRA codes combine several advantages of other types of LDPC codes, including low encoder and decoder complexities, flexibility in design, and good performance on different channels. It is also demonstrated in this dissertation that the S-IRA codes are suitable for rate-compatible code family design and a multi-rate code family has been designed which may be implemented with a single encoder/decoder.The study of the error floor problem of LDPC codes is very difficult because simulating LDPC codes on a computer at very low error rates takes an unacceptably long time. To circumvent this difficulty, we implemented a universal quasi-cyclic LDPC decoder on a field programmable gate array (FPGA) platform. This hardware platform accelerates the simulations by more than 100 times as compared to software simulations. We implemented two types of decoders with partially parallel architectures on the FPGA: a circulant-based decoder and a protograph-based decoder. By focusing on the protograph-based decoder, different soft iterative decoding algorithms were implemented. It provides us with a platform for quickly evaluating and analyzing different quasi-cyclic LDPC codes, including the S-IRA codes. A universal decoder architecture is also proposed which is capable of decoding of an arbitrary LDPC code, quasi-cyclic or not. Finally, we studied the low-floor problem by focusing on one example S-IRA code. We identified the weaknesses of the code and proposed several techniques to lower the error floor. We successfully demonstrated in hardware that it is possible to lower the floor substantially by encoder and decoder modifications, but the best solution appeared to be an outer BCH code.

Neste trabalho, usamos uma abordagem de anéis de grupo para caracterizar códigos cíclicos sobre anéis de cadeia, seus duais e algumas condições sobre códigos auto-duais. Caracterizamos também os códigos cíclicos livres sobre anéis de cadeia e por fim exibimos uma fórmula para o peso de qualquer código cíclico sobre anéis de cadeia de comprimento e p^n 2p^n. / In this thesis, we use an approach of group rings to characterize cyclic codes over chain rings, their duals and some conditions on self-dual codes. It also features free cyclic codes over chain rings and finally we show a formula for the weight of any cyclic code over chain rings of length p^n and 2p^n.

Neste trabalho, usamos uma abordagem de anéis de grupo para caracterizar códigos cíclicos sobre anéis de cadeia, seus duais e algumas condições sobre códigos auto-duais. Caracterizamos também os códigos cíclicos livres sobre anéis de cadeia e por fim exibimos uma fórmula para o peso de qualquer código cíclico sobre anéis de cadeia de comprimento e p^n 2p^n. / In this thesis, we use an approach of group rings to characterize cyclic codes over chain rings, their duals and some conditions on self-dual codes. It also features free cyclic codes over chain rings and finally we show a formula for the weight of any cyclic code over chain rings of length p^n and 2p^n.

Le sujet porte sur une classe de codes correcteurs d erreurs dits codes cycliques tordus, et ses applications a l'Informatique quantique et aux codes quasi-cycliques. Les codes cycliques classiques ont une structure d'idéaux dans un anneau de polynômes. Ulmer a introduit en 2008 une généralisation aux anneaux dits de polynômes tordus, une classe d'anneaux non commutatifs introduits par Ore en 1933. Dans cette thèse on explore le cas du corps a quatre éléments et de l'anneau produit de deux copies du corps a deux éléments. / The topic of the thesis is the study of skew cyclic codes, with application to Quantum Computing and quasi-cyclic codes. Classical cyclic codes have a natural structure of ideals in a polynomial ring. This was generalized by Ulmer in 2008 to skew polynomial rings, a class of non commutative rings introduced by Ore in 1933. The latter codes are not classically cyclic if the alphabet ring admits a non trivial automorphism. In this work is explored the cases of the finite field of order four and of a product ring of two copies of the finite field of order two.

We study the Hamming distance and the structure of repeated-root cyclic codes, and their generalizations to constacyclic and polycyclic codes, over finite fields and Galois rings. We develop a method to compute the Hamming distance of these codes. Our computation gives the Hamming distance of constacyclic codes of length $np^s$ in many cases. In particular, we determine the Hamming distance of all constacyclic, and therefore cyclic and negacyclic, codes of lengths p^s and 2p^s over a finite field of characteristic $p$. It turns out that the generating sets for the ambient space obtained by torsional degrees and strong Groebner basis for the ambient space are essentially the same and one can be obtained from the other. In the second part of the thesis, we study matrix product codes. We show that using nested constituent codes and a non-constant matrix in the construction of matrix product codes with polynomial units is a crucial part of the construction. We prove a lower bound on the Hamming distance of matrix product codes with polynomial units when the constituent codes are nested. This generalizes the technique used to construct the record-breaking examples of Hernando and Ruano. Contrary to a similar construction previously introduced, this bound is not sharp and need not hold when the constituent codes are not nested. We give a comparison of this construction with a previous one. We also construct new binary codes having the same parameters, of the examples of Hernando and Ruano, but non-equivalent to them.

En considérant les polynômes sur le corps fini de Galois à deux éléments, notre intention porte sur la divisibilité des trinômes x^am+x^bs+1, pour m>s≥1, par un polynôme irréductible de degré r, pour cela, nous avons réalisé le résultat :S'il existe m, s des entiers positifs tels que le trinôme x^am+x^bs+1 soit divisible par un polynôme irréductible de degré r sur F2, alors a et b ne sont pas divisibles par (2r- 1). Pour ce type de trinômes nous conjecturons que le rapport πM(a,b)/ πM(1,1) tend vers une limite finie (dépendant de a et b) quand M tend vers l'infini. Notre recherche porte ensuite sur les codes cycliques de rendement 1/2 sur les deux corps finis F3 et F5 et nous accentuons notre recherche sur ceux iso duaux. Le problème central dans la théorie du codage est trouver la plus grande distance minimum dq pour laquelle un code de paramètres [n, q, d] sur Fq existe. Dans ce contexte nous avons réussi à optimiser cette distance pour les codes cycliques de taux 1/2 sur F3 et F5 en allant jusqu’à la longueur 74 pour les codes ternaires et 42 pour ceux sur F5. Nous avons aussi réussi à construire sept classes de codes cycliques iso-duaux sur le corps fini à 3 éléments et trois classes de codes cycliques iso-duaux sur le corps fini à 5 éléments. / Considering polynomials over the Galois finite fields for two elements, our intention stand over the divisibility of the trinomials x^am+x^bs+1, for m>s ≥ 1, by an irreducible polynomial of degree r, for this, we contribute to the result :If there exist positive integers m, s such that the trinomial x^am+x^bs+1 is divisible by an irreducible polynomial of degree r over F2, then a and b are not divisible by (2^r- 1). For this type of trinomials we conjectured that the ratios πM(a,b)/ πM(1,1) tend to a finite limit (dependently of a and b) when M tend to infinity. Our research stand at sequel on the cyclic codes of rate 1/2 over the two finite fields F3 and F5 and we check our research over whose are isodual. The so-called fundamental problem in coding theory is finding the largest value of dq for which a code of parameters [n, q, d] over Fq exists. In this context we have successfully optimize this distance for the cyclic codes of rate 1/2 over F3 and F5 up to length 74 for the ternary cyclic codes and 42 for whose over F5. We have also successful to construct seven classes of isodual cyclic codes over the field of 3 elements and three classes over the field of 5 elements.

No description available.

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