Error Correcting Codes from Finite Geometries; Existence, Bounds, and Decoding.

点击翻译按钮获取中文摘要

MDS codes possess the strongest possible error correction ability. The ubiquitous Reed-Solomon codes serve as an archetype of linear MDS codes and have found applications in such diverse areas as cryptography, hard disk storage, deep space communications, and digital audio recording. Over the past 5 years over 6000 patents granted through the U.S. patent office have involved MDS codes. These observations indicate the importance of this field to the scientific and engineering community in Canada.An (n,k,d)_q-code C is a collection of q^k n-tuples (codewords) over an alphabet A of size q such that the minimum (Hamming) distance of C is d (that is, no two codewords agree in as many as n-d+1 coordinates). If C is a vector space, C is said to be linear. From the Singleton bound it follows that d<= n-k+1, the Singleton defect of C is S(C)=n-k+1-d. Codes with S(C)=0 are called MDS (Maximum Distance Separable) codes.(1) A long-standing fundamental problem in coding theory is the following: (*) Determine the maximum value of n for fixed k, q, and S(C). We will investigate (*) for nonlinear as well as linear codes. In the setting of MDS codes Problem 1 is a difficult unsolved problem (even in the linear case, where S. Ball has recently made much progress). For linear MDS codes the problem was first posed over 50 years ago by B. Segre. The Main Conjecture for linear MDS codes asserts that n \leq q+2 for k=3 and k=q-1 both with q even and that n \leq q+1 in all other cases. (2) (OOCs and related codes): This research program will use finite geometries to develop constructions of (optimal) Optical Orthogonal Codes (OOCs) and related codes. Applications require OOCs with many codewords (optimality). We have provided constructions of infinite families ofoptimal Optical Orthogonal Codes (OOCs) over the past few years. Through their connection with NRC's, the proposed research will investigate the possibility of efficiently decoding the codes constructed using our techniques.