Combinatorial Configurations,Lattice Tilings And Their Applications In Information Science

This thesis involves various problems in the area of algebraic coding theory,algebraic com-binatorics, lattice tilings and their applications in information theory. This dissertation aims to investigate these problems via a combinatorial perspective, with applications of tools from abstract algebra, algebraic number theory and character theory.In Chapter 2, two special shapes for tilings are considered. One includes the cross, semi-cross and quasi-cross. Some physical effects that limit the reliability and performance of multilevel flash memories induce errors that have low magnitudes and are dominantly asymmetric. This motivated the application of the asymmetric limited magnitude error model in flash memory, and the asymmetric limited magnitude codes are equivalent to the lattice tiling problems by cross,semi-cross and quasi-cross. For this problem, we present a new construction of quasi-perfect codes, which generalizes most of the previously known constructions. We also give a new general construction of perfect codes, and obtain some new parameters of perfect codes. Meanwhile, we prove some nonexistence results for perfect codes. In particular, we have completely solved the problems left by Schwartz (European J. Combin., vol. 36, pp. 130-142, Feb. 2014). The other is the sphere under lp metric. In 1970, Golomb and Welch posed the long standing conjecture which states that there is no perfect r error correcting Lee codes of length n for n > 3 and r > 1.We prove some nonexistence results for perfect codes in Zn under the lp metric. In particular,our results further substantiate the Golomb-Welch conjecture. Since it is widely believed that the Golomb-Welch conjecture is true, constructing codes close to perfect makes sense. We then give an algebraic construction of quasi-perfect lp codes.In Chapter 3, we consider the theory of self-orthogonal codes and their applications in quan?tum codes. Self-dual codes are special classes of self-orthogonal codes, and they are one of the most interesting classes of linear codes,since they have strong connections with several other areas including lattices, designs, projective planes and invariant theory. Generally, it is hard to construct self-dual codes with relatively large minimum distance. We construct several classes of self-dual codes by using double circulant configuration and fourth power residues, which are a generaliza-tion of the quadratic double circulant self-dual codes. Numerical experiments show that some of our codes have better parameters than previously known codes. Quantum codes were introduced to protect quantum information from decoherence during quantum computations and quantum com?munications. A powerful construction of quantum codes is employing classical codes with certain self-orthogonality. We use classical constacyclic codes and generalized Reed-Solomon codes to construct several classes of quantum MDS codes. We also present a construction of classical linear codes based on certain classes of polynomials. Through these classical linear codes, we obtain some new quantum codes which have better parameters than the ones available in the literature.In Chapter 4, we consider two other problems related to information theory. One is semi-regular relative difference sets. Semi-regular relative difference sets have been extensively studied due to their close connections with mutually unbiased bases. The research is concentrated on two aspects - non-existence and existence results. There has been much research on (pa,pb,pa, pa-b)relative difference sets with p a prime, while there are only a few results on (mn,n ,mn, m.) relative difference sets with gcd(m, n) = 1. The nonexistence results on (mn, n,mn,m) relative difference sets with gcd(m,n) = 1 have only been obtained for the following five cases: (1) m = p,n =q. p > q; (2) m = pq. n = 3. p, q > 3; (3) m = 4, n ? p; (4) m = 2 and (5) n = p, where p, q are distinct odd primes. For the existence results, there are only four constructions of semi-regular relative difference sets in groups of size not a prime power with the forbidden subgroup having size larger than 2. We present some more non-existence results on (mn, n, mn, m) relative difference sets with gcd(m,n) = 1. In particular, our result is a generalization of the main result of Hiramine's work (J. Combin. Theory Ser. A, 117(7):996-1003, 2010). Meanwhile, we give a construction of non-abelian (16q, q, 16q, 16) relative difference sets, where q is a prime power with q ? 1 (mod 4) and q > 4.2 × 108. The other is Grassmannian packings. The problem of packing n-dimensional subspaces of Rm was introduced by Conway, Hardin and Sloane in 1996. The goal is to find a set of n-dimensional subspaces such that they are as far apart as possible. It can be seen as a generalization of the problem of spherical codes or equiangular lines. We present three constructions of optimal packings in Grassmannian spaces from difference sets and latin squares.In Section 5, we briefly introduce some other works.