Irregular Gallager-type error-correcting codes - a statistical mechanics perspective

Introduction

Irregular Gallager-type error-correcting codes - a statistical mechanics perspective is a EPSRC funded project. This project is led by David Saad working with Jort van Mourik (the postdoctoral RA). The research will also affect industrial applications by improving the efficiency of the encoding/decoding process, thus making it easier to obtain higher robustness against message corruption and shorter decoding times. This will result in expanding the performance of existing equipment, making higher rate robust communication feasible.

Research Funding

EPSRC: 109,649 GBP

Duration

The project started in the June, 2000, and will last for 2 years.

Project Background

Gallager-type error correcting codes are based on randomly generated sparse matrices employed in both generating the code worked and decoding the corrupted received message. These have been recently rediscovered and are among the leading error-correcting codes, especially in their irregular configuration. Although some theoretical work has been carried out in this are, the more substantial performance evaluation comes fro, numerical studies.

In a recent study we offered a statistical mechanics framework for examining analytically the efficiency of regular Gallager-type codes. The insight gained from the analysis facilitated the constructions of new Gallager-type codes with cascading connections which outperform other state-of -the-art codes. This project, based on extending the current theoretical framework, will focus on examining the efficiency and usefulness of general (mainly irregular) Gallager-type codes, aiming at optimising the connectivity distribution. In addition, we will investigate the efficacy of belief-propagation based decoding techniques in various scenarios and transmission channels. We will use the theoretical framework to suggest novel methods and /or improvements to existing encoding/decoding techniques. These will be examined both analytically and via numerical simulations.

Objectives

Develop the theoretical framework for studying irregular Gallager-type codes.
Exploit this framework for investigating the method's dependence on the choice of parameters and for optimising the connectivity distribution.
Study the relation between existing decoding techniques and methods of statistical physics and to evaluate analytically the efficacy of existing decoding techniques.
Devise and demonstrate new methods for improving the decoding/encoding process.

Achievements

Regular and Irregular Gallager-type Error-Correcting Codes.

Further Information

We attempt to produce online versions of all relevant publications arising from this project. You can see a list of all the available technical reports by following the link below: