Codes, graphs and graph based codes

Andrew Brown
EPFL, 2007
Thèse EPFL

Résumé

This work is concerned with codes, graphs and their links. Graph based codes have recently become very prominent in both information theory literature and practical applications. While most research has centered around their performance under iterative decoding, another line of study has focused on more combinatorial aspects such as their weight distribution. This is the angle we explore in the first part of this thesis, investigating the trade-off between rate and relative distance. More precisely, we show, using a probabilistic argument, that there exist graph-based codes approaching the asymptotic Gilbert-Varshamov bound, and that are encodable in time O(n1+ε) for any ε > 0, where n is the block length. The second part is concerned with more practical issues, more specifically the erasure channel. Although the codes mentioned above have been shown to perform very well in this setting, this nonetheless requires their lengths to be quite large. When short blocks are required, certain algebraic constructions become viable solutions. In particular Reed-Solomon (RS-) codes are used in a wide range of applications. However, there do not appear to be any practical uses of the more general Algebraic-Geometric (AG-) codes, despite numerous advantages. We explore in this work the use of very short AG-codes for transmissions over the erasure channel. We present their advantages over RS-codes in terms of the encoder/decoder running times, and evaluate the drawbacks by designing an efficient algorithm for computing the error probabilities of AG-codes. The work was done as part of an industrial collaboration with specific transmission problems in mind, and we include some practical data to illustrate the theoretical improvements. Graphs and codes can be related in different ways, and a graph being a good expander often yields a code with certain desirable properties. In the third part we deal with graph products and their expansion properties. Just as the derandomized squaring operation essentially takes the square of a graph and removes some edges according to a second graph, we introduce the derandomized tensoring operation which removes edges from the tensor product of two graphs according to a third graph. We obtain a bound on the expansion of the product in terms of the expansions of the constituent graphs. We also apply the same ideas to a code product, leading to the derandomized code concatenation operation and its analysis.

Official source

https://infoscience.epfl.ch/record/103755?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Andrew Brown
EPFL, 2007
Thèse EPFL

Résumé

Official source

https://infoscience.epfl.ch/record/103755?ln=fr

À propos de ce résultat

Concepts associés (7)

Concepts associés

Chargement

Publications associées (5)

Chargement

Afficher plus

Publications associées

Chargement

Publications associées (5)

Asymptotic and finite-length analysis of low-density parity-check codes

Changyan Di

This thesis addresses the topic of Low-Density Parity-Check (LDPC) code analysis, both asymptotically and for finite block lengths. Since in general it is a difficult problem to analyze individual code instances, ensemble averages are studied by following Gallager's original idea and results of Luby et al. Often, one can relate the insights gained by studying ensemble averages to statements regarding individual codes by proving that most elements in the ensemble behave "close" to the average. One important such average is the average weight distribution, another is the average pseudo-codeword distribution, where pseudo-codewords play the same role under iterative decoding as codewords do for maximum likelihood decoding. One of the main contributions of this thesis is the calculation of such averages for fully irregular LDPC code ensembles. Much of classical coding theory is aimed at the construction of codes with large minimum distance. This is so since away from capacity accurate bounds on the performance of a code can be given in terms of its minimum distance (or more generally, in terms of its weight distribution). Therefore, it is of interest to investigate what role the minimum distance plays for iteratively decoded LDPC code ensembles. In particular, sequences of capacity-achieving LDPC code ensembles of increasing length when transmission takes place over the Binary Erasure Channel (BEC) are investigated. It is shown that, under certain technical conditions, the minimum distance of such ensembles grows sub-linearly in the block length, a result which is somewhat surprising from a classical point of view. Specific attention is also given to the design of LDPC code ensembles, where an inherent trade-off is observed between achieving large minimum distance (which is relevant for the so called error-floor regime) and achieving a large threshold (which in the limit of long block lengths determines the worst channel on which transmission can be accomplished reliably). Most results on iterative coding systems to date address their asymptotic performance, i.e., their performance when the block length tends to infinity. For small and moderate block lengths the behavior of a code can deviate significantly from its asymptotic limit. It is therefore of high practical value to be able to analyze the finite-length performance of LDPC code ensembles. In this thesis, an exact such analysis is presented for iteratively decoded LDPC code ensembles over the BEC. In particular, expressions for the exact average bit and block erasure probabilities are computed by solving a set of recursions. Such an analysis is the starting point for a finite-length optimization, a topic which is slated for future work. The methods used in this thesis include a combinatorial approach (familiar to the coding society) as well as the powerful techniques developed in the statistical physics community, for example, the replica method or the mean-field approximation. Although the statistical physics techniques are ideally suited for the analysis of iterative coding systems, they are to date only accessible to a relatively small community. Therefore, an overview of these techniques is first presented using a language familiar to the coding theory community. Next, in order to highlight the differences and common points between the combinatorial and the statistical physics approaches, both techniques are applied to the weight distribution problem. It turns out that for regular ensembles, both methods yield the same result, while for irregular ensembles, they do differ in general.

EPFL2004

Chargement

Asymptotic and finite-length optimization of LDPC codes

Abdelaziz Amraoui

This thesis addresses the problem of information transmission over noisy channels. In 1993, Berrou, Glavieux and Thitimajshima discovered Turbo-codes. These codes made it possible to achieve a very good performance at low decoding complexity. In hindsight, it was recognized that the underlying principle of using sparse graph codes in conjunction with message-passing decoding was the same as the one proposed in Gallager's remarkable thesis of 1963, although Gallager's work had all but been forgotten in the intervening 30 years. In 1997, there occurred a breakthrough in the analysis of this type of codes. Luby, Mitzenmacher, Shokrollahi, Spielman and Stemann were able to give a complete characterization of the behavior of Low-Density Parity-Check code ensembles in the infinite blocklength case when used over the binary erasure channel. Soon thereafter, Richardson and Urbanke extended their results to binary-input memoryless symmetric channels. In this thesis we present tools to analyze the performance of these types of codes and ways to optimize their parameters. The optimization for the infinite blocklength case is relatively straightforward and we give a simple and efficient method of doing so. However, this does not really solve the problem in practice, since the asymptotic analysis has only limited relevance for the short or moderate blocklengths that are typically used in practice. This brings us to the main objective of this thesis, which is to bridge the gap between the asymptotic case and the practical finite-length case. We follow the lead of Luby et al. by considering the binary erasure channel. We show that the performance of LDPC codes obeys a well-defined scaling law as the blocklength increases. This scaling law refines the asymptotic analysis and provides a good way to understand and approximate the behavior of LDPC codes of short to moderate length. We show how to compute the scaling parameters involved and demonstrate how to use the resulting approximation as a design and optimization tool.

EPFL2006

Chargement

This paper investigates the use of algebraic-geometric codes for data transmission over a packet network, by comparing their encoding/decoding speeds to those of the ubiquitous Reed-Solomon Codes. We take advantage of the fact that AG codes allow the construction of longer codes over a given alphabet, which in turn means we can create an [n, k]-code over a smaller field in which the encoding/decoding algorithms run faster. We also obtain some probabilistic bounds on the overheads required for the codes we use.

2004

Chargement

Afficher plus

Asymptotic and finite-length analysis of low-density parity-check codes

Changyan Di

EPFL2004

Asymptotic and finite-length optimization of LDPC codes

Abdelaziz Amraoui

EPFL2006