Universidade de Aveiro
Paulo J. S. G. Ferreira

Real and DFT codes

The papers in this section deal with the problem of detecting and correcting errors using codes over the complex field, or DFT codes. If the positions of the errors are known, the interpolation problem (erasure correction) can be formulated in terms of sampling and frames (check the sections Frames, codes and reconstruction and Missing samples). When the positions of the errors are unknown, the problem is nonlinear.

The numerical performance of DFT codes depends heavily on the error pattern, and for low-pass codes the difficulties are felt mainly for bursty error patterns (contiguous losses). One way of circumventing them is to use two-channel DFT codes, coupled with an interleaver (a structure similar to a parallel concatenated turbo code). Another is to use codes based on random matrices.


José M. N. Vieira, Dorabella M. S. Santos and Paulo J. S. G. Ferreira. Error detection with real-number codes based on random matrices. In: Proceedings of the 12th IEEE Digital Signal Processing Workshop, DSPW-2006, Grand Teton National Park, Wyoming, U.S.A., pp. 526-530, Sep. 2006.

DFT codes are a well-known class of cyclic real-number codes. Their numerical stability degrades in the case of bursty erasures or errors. Chen and Dongarra have proposed a method based on random orthogonal matrices that is capable of decoding bursty erasures in a stable way. This paper introduces an efficient method, also based on random orthogonal matrices, to handle errors (not just erasures) efficiently.


P. J. S. G. Ferreira and J. M. N. Vieira. Locating and Correcting Errors in Images. In: Proceedings of the Fourth IEEE International Conference on Image Processing, ICIP-97, vol. I, Santa Barbara, CA, U.S.A., pp. 691-694, Oct. 1997.

This paper discusses a noniterative algorithm for locating the incorrect pixels of an image, assuming only partial knowledge of its Fourier transform. Note that this is a nonlinear problem: the unknown quantities are the positions and values of the N incorrect pixels. We show that the positions can be evaluated in O(N^2) or even O(N log N) flops by solving a set of N linear equations and computing a FFT. The determination of N is part of the algorithm, whose stability is also briefly discussed. The values of the N incorrect pixels can then be estimated using any of the interpolation methods known. For 1D signals, see the paper Detection and correction of missing samples.


P. J. S. G. Ferreira and J. M. N. Vieira. Detection and correction of missing samples. In: Proceedings of the 1997 Workshop on Sampling Theory and Applications, SampTA'97, Aveiro, Portugal, pp. 169-174, June 1997.

This paper deals with the following problem: to identify a subset of the samples of a band-limited signal that has been corrupted by (impulsive) noise. It is assumed that the Fourier transform of the signal is partially known (typically because the signal is band-limited). This is a nonlinear problem which is closely connected to several other signal processing problems. The stability of the proposed noniterative solution is examined. The method was applied to images in Locating and Correcting Errors in Images.


J. M. N. Vieira and P. J. S. G. Ferreira. Interpolation, spectrum analysis, error-control coding, and fault-tolerant computing. In: Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 97, vol. III, Munich, Germany, pp. 1831-1834, Apr. 1997.

The paper shows that four often studied problems in signal processing, spectrum analysis, information theory, and computing are closely related or even equivalent in a certain sense (if one of them can be solved, so can any of the others, and using essentially the same algorithms). The problems are (i) a nonlinear band-limited finite-dimensional interpolation problem (ii) the problem of estimating a signal that is the superposition of a finite number of harmonics (iii) an error-control coding problem in the real field, and (iv) certain techniques that occur in algorithm-based fault tolerant computing. The advantages of recognizing these problems as equivalent are obvious: the techniques commonly used in one field can be imported to the others, the duplication of research efforts is prevented, and the overall degree of understanding of the four problems increases. New algorithms are suggested as a result of these investigations.