Computational Study of Discrete Mathematics Problems Arising in Digital Communication

Petr Lisonek

Abstract

This project is an exploratory computational study of various discrete mathematics problems arising in digital communication. Solutions to problems such as these have for many years played a powerful enabling role in areas of application such as data storage and transmission, position determination, synchronization, data compression, optical time domain reflectometry, and signal transmission from deep space. The project lies on the boundary between discrete mathematics, computing science, and communications engineering.Current Projects:1. The structure of q-ary linear codes of minimum distance 4 and 5.These are the smallest cases for which the problem of finding optimal codes remains unsolved (except when q=2 and d=4). These codes admit a simple geometric characterization in terms of point sets in finite projective spaces and their study provides an interesting link between algebra, combinatorics and geometry. One possible approach to finding good codes is to refine the minimum distance condition to a more detailed measure, such as studying the size and structure of the set of words of minimum weight. These codes are applied in digital communication (detecting and correcting errors ccurring during data storage/transmission) and in the design of statistical experiments.2. The determination of the asymptotic maximum merit factor of binary sequences.This is one of the fundamental problems of digital communication, studied since the 1950s. In equivalent guise it is an old unsolved problem in complex analysis. Extensive computational exploration has recently shed new light on this problem.3. The structure of Golay complementary sequences.These sequences have a long history of application to digital communication, most recently as a means of controlling power in wireless multicarrier transmission. The recent discovery of a connection between these sequences and Reed-Muller codes produces practical coding schemes for wireless transmission having powerful algebraic error-correction and tight power control.