Grant: Discovery Grants Program - Individual
University of New Brunswick
$9,000.00
Codes of small defect from finite geometries: embeddings, bounds, and constructions.
FY 2009-10
Summary
The proposed research concerns error correcting codes arising from finite geometries. We shall investigate constructions of good codes using substructures of finite projective spaces. An (n,k,d)_q-code is a collection of q^k n-tuples (codewords) over an alphabet of size q such that no two codewords agree in as many as n-d coordinates. A code is linear if it is a vector space. The singleton defect of C is S(C)=n-k+1-d. A fundamental problem in coding theory is the following:
Problem 1: Determine the maximum value of n for fixed k, q, and S(C).
We shall skirmish with Problem 1 for codes of small defect.
Codes with S(C)=0 are called MDS (Maximum Distance Separable) codes. Linear MDS codes and arcs in projective spaces are equivalent objects. MDS codes possess the strongest possible error correction ability and have found many applications from deep space communications to compact disk recording. However, all known linear MDS codes are necessarily short and many applications would benefit from longer codes. This begs the question as to whether longer (nonlinear) MDS codes may be found.
The next best codes are those with S(C)=1, the AMDS (Almost-MDS) codes. A linear AMDS code without repeated coordinates is Near-MDS (NMDS). Linear (n,k,d)_q-NMDS codes and (n,k+1)-arcs in PG(k,q) are equivalent objects. Rational points of cubic curves provide (n,k+1)-arcs. Unlike MDS codes, there are many examples of AMDS codes exceeding the bounds (on length) provided by curves. We shall investigate Problem 1 and related extending, embedding, and uniqueness problems for MDS and AMDS codes.
Program
Discovery Grants Program - Individual
Recipient
Location
New Brunswick, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
262274-2007
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
2009
Competition year année de concours
2007
Award amount
9000
Program id
RGPIN
Program nane 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
337
Committee name en
Pure & Applied Maths - B
Committee name fr
Maths pures et appliquées - B
Area of application code
9999
Area of application group en
Not available
Area of application group fr
Non disponible
Area of application en
Not available
Area of application fr
Non disponible
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
Codes of small defect from finite geometries: embeddings, bounds, and constructions.
Keyword
NA
Application summary
The proposed research concerns error correcting codes arising from finite geometries. We shall investigate constructions of good codes using substructures of finite projective spaces. An (n,k,d)_q-code is a collection of q^k n-tuples (codewords) over an alphabet of size q such that no two codewords agree in as many as n-d coordinates. A code is linear if it is a vector space. The singleton defect of C is S(C)=n-k+1-d. A fundamental problem in coding theory is the following:
Problem 1: Determine the maximum value of n for fixed k, q, and S(C).
We shall skirmish with Problem 1 for codes of small defect.
Codes with S(C)=0 are called MDS (Maximum Distance Separable) codes. Linear MDS codes and arcs in projective spaces are equivalent objects. MDS codes possess the strongest possible error correction ability and have found many applications from deep space communications to compact disk recording. However, all known linear MDS codes are necessarily short and many applications would benefit from longer codes. This begs the question as to whether longer (nonlinear) MDS codes may be found.
The next best codes are those with S(C)=1, the AMDS (Almost-MDS) codes. A linear AMDS code without repeated coordinates is Near-MDS (NMDS). Linear (n,k,d)_q-NMDS codes and (n,k+1)-arcs in PG(k,q) are equivalent objects. Rational points of cubic curves provide (n,k+1)-arcs. Unlike MDS codes, there are many examples of AMDS codes exceeding the bounds (on length) provided by curves. We shall investigate Problem 1 and related extending, embedding, and uniqueness problems for MDS and AMDS codes.