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

有限几何形状的小缺陷代码：嵌入、边界和构造。

• 批准号: 262274-2007
• 负责人: Alderson, Timothy
• 金额: $ 0.66万
• 依托单位: University of New Brunswick
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=365433
• 关键词: Codes; small; defect; finite; geometries

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.

所提出的研究涉及有限几何形状产生的纠错码。（n，k，d）_q-码是在一个大小为q的字母表上的q^k个n元组（码字）的集合，使得没有两个码字在多达n-d个坐标上一致。一个码是线性的，如果它是一个向量空间。C的单态亏损为S（C）=n-k+1-d。编码理论中的一个基本问题是：问题1：确定固定k，q和S（C）的n的最大值。我们将在小缺陷码的情况下与问题1进行冲突。S（C）=0的码称为MDS（Maximum Distance Separable）码。线性MDS码和射影空间中的弧是等价的对象。MDS码具有最强的纠错能力，从深空通信到光盘记录都有其广泛的应用，但所有已知的线性MDS码都是短码，长码对许多应用都有好处。下一个最好的码是S（C）=1的码，即AMDS（Almost-MDS）码。没有重复坐标的线性AMDS码是近MDS（NMDS）。PG（k，q）中的线性（n，k，d）q-NMDS码与（n，k+1）-弧是等价的。三次曲线的有理点提供（n，k+1）-弧。与MDS码不同，有许多AMDS码超过曲线提供的界限（长度）的例子。我们将调查问题1和相关的扩展，嵌入，和MDS和AMDS码的唯一性问题。