Codes of small defect from finite geometries: embeddings, bounds, and constructions.

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

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.