Combinatorial Configurations, Exponential Sums And Their Applications In Signal Processing And The Design Of Codes

This thesis concerns various theoretical problems in the area of algebraic coding the-ory, combinatorial design theory and algebraic combinatorics. Meanwhile, it concerns some fundamental problems arising from many practical applications such as digital communica-tion, signal processing and data storage. The substance is to investigate these problems by employing various mathematical tools, including algebraic number theory, character theory, exponential sums and the theory of algebraic function fields.In Chapter 2, we consider the deterministic constructions of compressed sensing ma-trices. Initiated by Candes, Donoho and Tao, the theory of compressed sensing has seen the most significant progress in the area of signal processing in the last decade. A central problem in compressed sensing is the construction of sensing matrices. Noticing that ma-trices with small coherence values give rise to favorable sensing matrices, we succeed in constructing many infinite families of deterministic sensing matrices, from the viewpoints of coding theory, combinatorial design theory and other combinatorial configurations. These works present many optimal or near optimal coherence-based constructions of sensing ma-trices.In the area of algebraic coding theory and sequence design, many problems can be re-duced to the computation of certain exponential sums and their value distributions. Although these computations are very difficult in general, in Chapter 3, we make some progress by in-troducing fresh ideas to deal with exponential sums. More specifically, we obtain the weight distribution of a class of cyclic codes with Niho exponent. We compute the cross-correlation distribution of an m-sequence and its certain decimated sequence. We obtain the weight hierarchy of a class of cyclic codes with arbitrarily many nonzeroes.In Chapter 4, we consider the construction of some combinatorial designs. Partitioned difference families are the underlying structures of many optimal configurations. We present a combinatorial recursive construction to unify several algebraic constructions that employ generalized cyclotomy. Our new construction provides much flexibility for generalizing the existing constructions and for producing new series of partitioned difference families. Group divisible designs are a fundamental building block in combinatorial design theory. The con-struction of nonuniform group divisible designs is a very challenging problem since no proper algebraic or geometric structures are available. We present a new construction to generate several new classes of nonuniform group divisible designs.In Chapter 5, we consider the theory of cyclic codes and its applications. As widely-used cyclic codes in practical applications, the Bose-Chaudhuri-Hocquenghem (BCH) codes are one of the most important error-correcting codes. While classical results mainly concern the primitive BCH codes, we start the first systematic study of non-primitive BCH codes. We determine the fundamental parameters for several classes of non-primitive BCH codes. Quantum codes, which are a foundation of quantum information processing, can be derived from classical error-correcting codes. We use pseudo-cyclic codes to construct quantum max-imum distance separable codes, which unifies many previous constructions and produces new classes of such codes. The symbol-pair code is a new coding framework which is pro-posed to correct errors in the symbol-pair read channel. Employing cyclic and constacyclic codes, we construct three new classes of maximum distance separable symbol-pair codes with minimum pair-distance five or six. Moreover, we propose an algorithm which produces many maximum distance separable symbol-pair codes with minimum pair-distance seven.The appendix involves one problem in the area of algebraic coding theory and two prob-lems in the area of algebraic combinatorics. Remarkably, we obtain the weight distributions of a class of cyclic codes with arbitrarily many nonzeroes, even though direct computation seems hopeless. We achieve this by establishing an unexpected and beautiful connection between the exponential sums concerned and the spectra of graphs. In addition, we make progress in a classical problem related to difference sets and an emerging problem concern-ing pseudo-planar functions. The former problem studies difference sets that do not possess the character divisibility property, as proposed by Jungnickel and Schmidt in 1997. We pro-vide some necessary conditions for the possible candidates lacking the character divisibility property. The latter problem concerns a new concept related to finite projective planes. This work enriches the known constructions of pseudo-planar functions and builds a connection between pseudo-planar functions and association schemes.