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.
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)