Error Correcting Codes from Finite Geometries; Existence, Bounds, and Decoding.

有限几何的纠错码；

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

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.

MDS码具有最强的纠错能力。普遍存在的Reed-Solomon码作为线性MDS码的原型，并且已经在密码学、硬盘存储、深空通信和数字音频记录等不同领域中找到了应用。在过去的5年中，通过美国专利局授予的6000多项专利涉及MDS代码。这些观察表明了这一领域对加拿大科学和工程界的重要性。 （n，k，d）_q码C是在大小为q的字母表A上的q^k个n元组（码字）的集合，使得C的最小（汉明）距离为d（即，没有两个码字在多达n-d+1个坐标中一致）。如果C是一个向量空间，则称C是线性的。由Singleton界可以得出d<= n-k+1，C的Singleton亏损为S（C）=n-k+1-d. S（C）=0的码称为MDS（Maximum Distance Separable）码。 (1)编码理论中一个长期存在的基本问题是：（*）确定固定k，q和S（C）的n的最大值。我们将研究（*）的非线性以及线性码。在MDS码的情况下，问题1是一个难以解决的问题（即使在线性情况下，其中S。球最近取得了很大的进展）。对于线性MDS码，该问题在50多年前由B首次提出。塞格雷。线性MDS码的主要猜想断言，对于k=3和k=q-1，n \leq q+2都是偶数，并且在所有其他情况下n \leq q q+1。 (2)（OOC和相关代码）：该研究计划将使用有限几何来开发（最佳）光正交码（OOC）和相关代码的构造。应用程序需要具有许多码字的OOC（最优性）。我们已经提供了无限族的结构， 最佳光正交码（OOC）在过去的几年里。通过他们与NRC的连接，拟议的研究将调查有效地解码使用我们的技术构建的代码的可能性。