Grant: Discovery Grants Program - Individual
University of New Brunswick
$11,000.00
Error Correcting Codes from Finite Geometries; Existence, Bounds, and Decoding.
EF 2015-16
Résumé
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 of
optimal 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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
New Brunswick, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
262274-2013
Name nom
Alderson, Timothy
Department département
Mathematical Sciences
Organization id
75
Institution établissement
University of New Brunswick
Province en
New Brunswick
Province fr
Nouveau-Brunswick
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2013
Award amount
11000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
3
Nb partie
5
Application title
Error Correcting Codes from Finite Geometries; Existence, Bounds, and Decoding.
Keyword
NSERC
Application summary
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 of
optimal 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.