Workshop

Jointly funded by EPSRC and the Maxwell Institute

Mathematical Techniques in Coding Theory

Thursday, 24 April 2008
e-Science Institute
15 South College Street
Edinburgh, EH8 9AA, UK

Researchers from across the UK and Ireland who are interested in the mathematics of communications and coding theory will meet on 24 April 2008 at the e-Science Institute. Generous support for this event was supplied by the EPSRC funded "Bridging-the-Gaps" scheme between Engineering and Mathematics within the Edinburgh Research Partnership, the Maxwell Institute, ICMS and the e-Science Institute.

Registration:

Registration is free of charge but subject to space. Please quote "Coding Workshop" and send an informal request for registration preferably by email to

Nicola Ferguson
email: nicola.ferguson at ed.ac.uk
Institute for Digital Communications
Alexander Graham Bell Building / The Kings Buildings
School of Engineering and Electronics
The University of Edinburgh
Mayfield Road, Edinburgh, EH9 3JL
Scotland, UK

Schedule:

Abstracts:

Bahram Honary, "Reduced complexity implementation of QC-LDPC codes for DVB applications": An algebraic method for construction of well-structured variable-rate Low Density Parity Check (LPDC) codes is introduced. It enables the system to switch between LDPC codes of different DVB standard rates using a single encoder and decoder structure. This presentation introduces construction of variable rate QC-LDPC code using certain special classes of balanced incomplete block designs (BIBD). In addition, a memory efficient implementation of QC-LDPC codes based on real-time generation of the QC parity-check matrix is discussed. Synthesis results show that significant reduction in memory requirements is achievable.

Joint work with Behzad M. Heravi and Nishit Pandya

Rolando Carrasco, "Construction Methods for Binary and Non-Binary Low Density Parity Check Codes": Low Density Parity Check (LDPC) codes are well known for their excellent error-correcting performance and can now be found in important standards such as Worldwide Interoperability for Microwave Access (WiMax) (IEEE 802.16e) and Digital Video Broadcasting (DVB-S2). Much effort has been made in reducing their decoding complexity and the use of very long LDPC codes considered as the error-correction schemes in future magnetic data storage devices are now being considered, replacing the long-serving Reed-Solomon codes. Currently, LDPC codes are defined over the binary field and performance is dependent on very long code lengths, but in 1998 it was shown that LDPC codes defined over larger finite fields can outperform binary LDPC codes for smaller codeword lengths and in scenarios where long bursts of errors are prevalent. The construction of good non-binary LDPC codes is a relatively new area of research and in this presentation several methods of construction for binary and non-binary LDPC codes are presented. The performance of each class of LDPC codes is evaluated by computer simulation and comparisons are made between them. Finally, a method to reduce the decoding complexity of non-binary LDPC codes is explained using Fast Fourier Transforms (FFTs), which makes the implementation of these codes feasible.

Paddy Farrell, "Decoding Error-Control Codes with Soft Distance as the Metric": Soft-decision decoding of error-correcting codes, which began to be developed in the late 1960s, greatly enhanced the performance of these codes, and led eventually to the emergence a few years ago of powerful iterative decoding techniques for turbo and low density parity check (LDPC) codes. Soft decision decoding was first successfully applied to convolutional codes, using the Viterbi trellis decoding algorithm (VA) with soft distance as the metric, giving maximum likelihood performance. Maximum a posteriori probability (MAP) decoding followed later, in the form of the BCJR trellis algorithm, using probabilities (likelihoods) or log-likelihoods as the metric. Both VA and BCJR methods were then applied to block and turbo code trellises, and finally the big break-through came when iterative belief propagation algorithms on graphs were developed for LDPC codes. For some reason the use of soft distance as a metric for MAP decoding was never explicitly developed, as far as I know, although a distant connection can be made with the min-sum iterative decoding algorithm using negative log likelihoods. In fact it turns out that soft distance can be used as a metric to obtain MAP performance, on either the trellis or the graph of a code, by means of an antilog-sum algorithm which I will describe in this talk.

Liam Marnane, "Hardware implementation of GF(2^m) LDPC decoders": Low Density Parity Check (LDPC) codes over GF(2^m) are an extension of binary LDPC codes that have not been studied extensively. Performances of GF(2^m) LDPC codes have been shown to be higher than binary LDPC codes, but the complexity of the encoders/decoders increases. Hence there is a substantial lack of hardware implementations for LDPC over GF(2m) codes. This talk presents the hardware implementations of decoding algorithms for LDPC over GF(2^m). The results show that the implementation is feasible and the extra complexity of the decoder is balanced by the superior performance of GF(2^m) LDPC codes.

Joint Work with Christian Spagnol and Emanuel Popovici

Marcus Greferath, "Codes over rings - From the history to the perspectives": Ring-linear algebraic coding theory gained importance at the beginning of the previous decade when it was discovered that certain non-linear binary codes of high quality could be understood as linear codes over the ring of integers modulo 4. This talk gives some insight into this amazingly beautiful chapter of applied algebra. We will discuss a collection of results from the literature and from our own previous and current investigations. The talk will finish with examples, open problems and projects for future research.

Daniel J. Costello, Jr, "Minimum Distance Bounds for Serially Concatenated Code Ensembles": It has been shown that the minimum distance of the ensemble of single serially concatenated codes grows only sublinearly with block length as the block length tends to infinity, i.e., the code ensemble is not asymptotically good. In this talk, we show that multiple serially concatenated code ensembles can be asymptotically good, and we present a method to obtain their distance growth rate coefficients. In particular, we obtain growth rate coefficients for repeat multiple accumulate codes (RMACs) of different rates and for a rate 1/2 double serially concatenated code (DSCC) consisting of an outer memory one convolutional code followed by two accumulators. Finally, we compare this DSCC with the RMACs in terms of both distance growth rates and iterative decoding convergence behavior, and we show that RMACs have better distance growth, but worse convergence behavior, than the DSCC.

David Mitchell, "Asymptotically Good LDPC Convolutional Codes Based on Protographs": LDPC convolutional codes have been shown to be capable of achieving the same capacity-approaching performance as LDPC block codes with iterative message-passing decoding. Here, asymptotic methods are used to calculate a lower bound on the free distance for several ensembles of asymptotically good protograph-based LDPC convolutional codes. Further, we show that the free distance to constraint length ratio of the LDPC convolutional codes exceeds the minimum distance to block length ratio of corresponding LDPC block codes.

Gavin Gibson, "Stochastic methods for estimating high dimensional integrals": Stochastic methods represent the most powerful approaches to estimating high-dimensional integrals. This talk will illustrate the application of Markov chain methods to estimate integrals that arise in estimating likelihood ratios for competing stochastic compartment models. It will focus on epidemic applications, where it is necessary to integrate probability functions with respect to unobserved quantities relating to the epidemic (e.g. unobeserved infection times or infectious periods). The talk will also consider how similar approaches might be applied in other scenarios, such as the estimation of error-rates in studies of signal coding methods.

Marco Colombo, "OR methods in Channel Coding and Code Design": In this talk we will provide an overview of some algorithms and results obtained by applying operational research and optimization techniques to the engineering problems of channel coding and code design. In particular, we will spend some time on the use of Linear Programming techniques in the formulation and solution of decoding problems arising from LDPC codes. The purpose of the talk will be to provide a different viewpoint on these important engineering problems. In particular, we will discuss open problems, future challenges and hopes.

Further Links

International Center for Mathematical Sciences

Maxwell Institute Colloquia

Maxwell Institute for Mathematical Sciences

University of Edinburgh School of Mathematics

Heriot-Watt University Department of Mathematics

Edinburgh Research Partnership