NCR-9505975, California Institute of Technology, "Coding Theory and Applications", PI-McEliece: Three topics in modern coding theory are studied: Trellis complexity of convolutional codes, subgroup subcodes of Reed Solomon codes, and turbo-codes. The first involves a novel way of reducing the Viterbi decoding complexity of a large class of convolutional codes, including many codes currently used in practice (e.g. punctured convolutional codes and the unit memory convolutional codes). This is a surprising spinoff of the large body of recent work on the trellis complexity of block codes. The second considers a new class of algebraic block codes, the class of "SSRS" codes, which promises to break the "bottleneck" of Reed-Solomon codes, i.e. the restriction that the code length be no more that the size of the code alphabet. Finally the new class of "turbo-codes", recently introduced in France, will be studied. Turbo codes represent the biggest single step forward in many years in high gain low complexity coding. It is hoped to develop a credible theory to explain the remarkable experimental results and enable the work to be pressed forward systematically. ***************************************************************************** Aubrey M. Bush Program Director, Acting Deputy Divison Director Division of Networking and Communications Research and Infrastructure National Science Foundation
