Linköping Studies in Science and Technology
Dissertation No. 513

Error-Correcting Codes Based on Chaotic Dynamical Systems

Håkan Andersson

Akademisk avhandling

som för avläggande av teknologie doktorsexamen vid Linköpings tekniska högskola kommer att offentligt försvaras i ISYs seminarierum, Linköpings universitet, fredagen den 27 februari, kl 10.15. Fakultetsopponent är Dr. Thomas Mittelholzer, r3 security engineering, Aathal, Schweiz.

Abstract

This dissertation treats a novel class of error-correcting codes based on chaotic dynamical systems. The codes are defined over a continuous alphabet whereas the information that is to be transmitted belongs to a discrete set of symbols. Simple expressions can be given for the encoders, and the codewords can be described by a parity-check relation. However, the most interesting approach is to view the codewords as orbits of iterated dynamical systems described by integer matrices.

Under some rather natural assumptions, the codes are shown to be group codes. The minimum distance is proved to be well-defined and strictly greater than zero. An algorithm for calculating it is also given. Initially, no robust sliding-window encoder inverses exist, but this deficiency is remedied by the introduction of fractal signal sets. The problem of catastrophic encoders is also solved by the introduction of these totally disconnected signal sets.

Decoding strategies are discussed, and it is shown why the Viterbi algorithm does not work in higher dimensions for this type of codes. So-called list decoding emerges as a good alternative and its merits are considered. Simulations and comparisons with binary antipodal signaling are performed. The setting of the work is in two dimensions. However, the strength of this code construction is that it easily generalizes to higher dimensions.

Department of Electrical Engineering
Linköping University, S-581 83 Linköping, Sweden
Linköping 1998

ISBN 91-7219-127-9 ISSN 0345-7524