Grant: Discovery Grants Program - Individual
University of New Brunswick
$15,000.00
Codes from Finite Geometries: Extensions, Constructions, and Decoding.
EF 2019-20
Résumé
An (n,k,d)_q code C is a collection of q^k strings of length n called codewords over an alphabet A of size q such that the minimum (Hamming) distance of C is d. The distance between two codewords is the number of coordinates in which they differ. d is the minimum pairwise distance in C. If C is a vector space, then C is linear.***Error correcting codes (ECC) allow the reliable transmission of information. A given a message is transmitted over a channel. During transmission, noise produces distortions. ECC are used to correct the errors. Brief description of nearest neighbour decoding: First a correspondence is established between the all possible strings of length k and the codewords of an (n,k,d)_q code C. Next, the message is split into chunks of length k, and each piece, m, is encoded to its corresponding codeword E(m). Instead of m, E(m) is sent. There are extra symbols transmitted (redundancy), which costs extra time and bandwidth. At the other end, the distorted version of E(m) is received, R(m). If R(m) is a codeword, then the transmission is deemed successful, and the R(m) is decoded to the corresponding message of length k. If the number of errors that occur is at most d-1, then R(m)=E(m). Otherwise, R(m) is translated to the nearest codeword N(m). If the number of errors that occur is at most (d-1)/2, then N(m) = E(m). Hence, a “good” code is one that strikes a balance between strong error correcting abilities, and (expensive) redundancy. ***My research will investigate the existence of good codes. The aim will be to determine (in certain cases) the maximum length, n, of an (n,k,d)_q code for fixed k, d, and q.***There are many bounds pertaining to linear codes, but relatively few for non-linear. In previous work we showed that if a linear code can be made one symbol longer then this extension can be done in such a way as to preserve linearity. I shall expand these results to extensions of length t > 1. The existence of certain codes (such as the Kerdock code) show that one cannot hope for a non-conditional result, but some progress can be made in binary/small dimensional cases.***I shall also investigate bounds on the length of linear codes that achieve the maximum number of distinct weights (possible distances from zero), the structure of such codes, and generalize investigations to other metrics.***Another class of codes, optical orthogonal codes (OOC) are essential for certain fiber-optic communication systems. Optimal OOC enable the largest possible number of asynchronous users to transmit information efficiently and reliably. Higher dim'l codes (arrays vs strings) are now accommodated by hardware. Previously, I provided constructions of optimal OOCs. I shall continue development of new optimal OOC, and plan to establish the best environments for certain codes (performance analyses), and through their connection with finite geometries, I will investigate efficient decoding techniques for the codes I have constructed.
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
RGPIN-2019-04103
Name nom
Alderson, Tim
Department département
Mathematics and Statistics
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
2019
Competition year année de concours
2019
Award amount
15000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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
Installment
inst:1 - 5
Partie
1
Nb partie
5
Application title
Codes from Finite Geometries: Extensions, Constructions, and Decoding.
Keyword
NSERC
Application summary
An (n,k,d)_q code C is a collection of q^k strings of length n called codewords over an alphabet A of size q such that the minimum (Hamming) distance of C is d. The distance between two codewords is the number of coordinates in which they differ. d is the minimum pairwise distance in C. If C is a vector space, then C is linear.***Error correcting codes (ECC) allow the reliable transmission of information. A given a message is transmitted over a channel. During transmission, noise produces distortions. ECC are used to correct the errors. Brief description of nearest neighbour decoding: First a correspondence is established between the all possible strings of length k and the codewords of an (n,k,d)_q code C. Next, the message is split into chunks of length k, and each piece, m, is encoded to its corresponding codeword E(m). Instead of m, E(m) is sent. There are extra symbols transmitted (redundancy), which costs extra time and bandwidth. At the other end, the distorted version of E(m) is received, R(m). If R(m) is a codeword, then the transmission is deemed successful, and the R(m) is decoded to the corresponding message of length k. If the number of errors that occur is at most d-1, then R(m)=E(m). Otherwise, R(m) is translated to the nearest codeword N(m). If the number of errors that occur is at most (d-1)/2, then N(m) = E(m). Hence, a “good” code is one that strikes a balance between strong error correcting abilities, and (expensive) redundancy. ***My research will investigate the existence of good codes. The aim will be to determine (in certain cases) the maximum length, n, of an (n,k,d)_q code for fixed k, d, and q.***There are many bounds pertaining to linear codes, but relatively few for non-linear. In previous work we showed that if a linear code can be made one symbol longer then this extension can be done in such a way as to preserve linearity. I shall expand these results to extensions of length t > 1. The existence of certain codes (such as the Kerdock code) show that one cannot hope for a non-conditional result, but some progress can be made in binary/small dimensional cases.***I shall also investigate bounds on the length of linear codes that achieve the maximum number of distinct weights (possible distances from zero), the structure of such codes, and generalize investigations to other metrics.***Another class of codes, optical orthogonal codes (OOC) are essential for certain fiber-optic communication systems. Optimal OOC enable the largest possible number of asynchronous users to transmit information efficiently and reliably. Higher dim'l codes (arrays vs strings) are now accommodated by hardware. Previously, I provided constructions of optimal OOCs. I shall continue development of new optimal OOC, and plan to establish the best environments for certain codes (performance analyses), and through their connection with finite geometries, I will investigate efficient decoding techniques for the codes I have constructed.