Papers on-line

Published papers by Edward A. Ratzer looking at error-correcting coding solutions for the following communication problems are below

My PhD thesis can also be downloaded below.


PhD Thesis

Error-correction on non-standard communication channels

Thesis submitted September 2003, successfully defended November 2003

Many communication systems are poorly modelled by the standard channels assumed in the information theory literature, such as the binary symmetric channel or the additive white Gaussian noise channel. Real systems suffer from additional problems including time-varying noise, cross-talk, synchronization errors and latency constraints. In this thesis, low-density parity-check codes and codes related to them are applied to non-standard channels.

First, we look at time-varying noise modelled by a Markov channel. A low-density parity-check code decoder is modified to give an improvement of over 1dB.

Secondly, novel codes based on low-density parity-check codes are introduced which produce transmissions with Pr(bit=1) ¹ Pr(bit=0). These non-linear codes are shown to be good candidates for multi-user channels with crosstalk, such as optical channels.

Thirdly, a channel with synchronization errors is modelled by random uncorrelated insertion or deletion events at unknown positions. Marker codes formed from low-density parity-check codewords with regular markers inserted within them are studied. It is shown that a marker code with iterative decoding has performance close to the bounds on the channel capacity, significantly outperforming other known codes.

Finally, coding for a system with latency constraints is studied. For example, if a telemetry system involves a slow channel some error correction is often needed quickly whilst the code should be able to correct remaining errors later. A new code is formed from the intersection of a convolutional code with a high rate low-density parity-check code. The convolutional code has good early decoding performance and the high rate low-density parity-check code efficiently cleans up remaining errors after receiving the entire block. Simulations of the block code show a gain of 1.5dB over a standard NASA code.

Buy paperback Buy hardback Compressed PS (593k) PS (2.5Mb) PDF (937k)


Synchronization

Codes for Channels with Insertions, Deletions and Substitutions

Paper by Edward A. Ratzer and David J. C. MacKay presented at the 2nd International Symposium on Turbo Codes and Applications

We compare the performance of two codes for channels with insertion and deletion errors: marker codes and watermark codes. Both codes are decoded using the sum-product algorithm. Marker codes can be viewed as an extreme case of irregular watermark codes. Our experiments give evidence that irregular constructions can improve watermark codes' performance.

Compressed PS (170k) PS (614k) PDF (1.2Mb)

Marker codes for channels with insertions and deletions

Presented at the 3rd International Symposium on Turbo Codes and Applications

Coding for channels with synchronization errors is studied. Marker codes, each consisting of a low-density parity-check code with inserted markers, are developed. At low insertion-deletion probabilities marker codes are shown to outperform watermark codes. Full iterative decoding enhances performance to close to the capacity bounds. The low-density parity-check codes are optimized and the best known rate R = 0.5 code for the insertion-deletion channel presented. The codes are also shown to be effective on the bit-deletion channel.

Conference camera-ready: Compressed PS (127k) PS (359k) PDF (116k)
Longer version as published in the Annals of Telecommunications: PDF (197k)

Reliable Communication Over Insertion-Deletion Channels

Cambridge University Tripos Part III Project Report

The performance of various different types of marker codes was studied and the maximum rate of reliable transmission using them over channels that experience insertion and deletion errors was experimentally measured.  Improved performance over watermark codes was discovered for noise levels up to approximately pins=pdel=8%.

Compressed PS (190k)  PS (970k)  PDF (123k)


Cross-talk

Sparse Low-Density Parity-Check Codes for Channels with Cross-Talk

Paper by Edward A. Ratzer and David J.C. MacKay presented at the IEEE Information Theory Workshop 2003

Low-density parity-check codes are modified to produce transmissions in which the symbols 1 and 0 are used with different frequencies. These codes are good candidates for multi-user channels with crosstalk, such as optical channels.

Compressed PS (58k) PS (210k) PDF (81k)

Sparse Data Blocks and Multi-User Channels

To be presented at the IEEE International Symposium on Information Theory 2003

An efficient algorithm for creating sparse data blocks of fixed size is presented. The use of sparse data blocks with a systematic error-correcting code is shown to increase the communication rate on multi-user channels.

Compressed PS (142k) PS (380k) PDF (120k)
Abstract PDF (63k)


Latency

Intersected low-density parity-check and convolutional codes

To be presented at the 7th International Symposium on Communication Theory and Applications

We look at the intersection of convolutional codes with high rate low-density parity-check codes. Threshold values are obtained with EXIT charts. Simulations show a gain of 1.5dB over a standard deep-space code.

Compressed PS (49k) PS (234k) PDF (103k)

Intersected Low-Density Parity-Check and Convolutional Codes

Short paper presented at the Postgraduate Research Conference in Electronics, Photonics, Communications and Software 2003

Key Results: Proposed a new code which compares favourably with other sparse-graph block codes. The graph structure allows analysis by EXIT charts.
How does the work advance the state-of-the-art?: A gain of 1.5dB is found over a standard deep-space coding scheme while still maintaining some of the computational advantages of the original scheme.
Motivation (Problems addressed): To try and get the best of the stream and block coding worlds.

Compressed PS (31k) PS (125k) PDF (39k)

Convolutional code performance as a function of decoding delay

Paper presented at the 6th International Symposium on Communication Theory and Applications

Unterminated rate 3/4 convolutional codes are studied experimentally using the forward-backward algorithm over a 1% binary symmetric channel. A lower bit error probability is found for systematic compared to non-systematic generator matrices. It is further found that a decoding delay of 7m is needed to fully exploit the error-correcting capabilities of the code.

Compressed PS (54k) PS (219k) PDF (99k) PSgz poster (317k)


Bursts

Low-density parity-check codes on Markov channels

Presented at the Second IMA Conference on Mathematics in Communications

Low-density parity-check codes are studied over Markov channels with time-varying gaussian or bit-flipping noise. The belief propagation decoding algorithm is extended to include channel estimation and the gains this extension produce are experimentally determined.

Compressed PS (186k) PS (646k) PDF (219k)


Back to homepage


Edward Ratzer,
Christ's College,
Cambridge CB2 3BU