Applications of structural matroid theory to minor-closed classes of codes

结构拟阵理论在小闭类码中的应用

• 批准号: RGPIN-2016-04131
• 负责人: Nelson, Alexander
• 金额: $ 2.26万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=614855
• 关键词: Applications; structural; matroid; theory; minor

Coding theory is the study of methods of sending information in a way that is tolerant of transmission errors. Its varied applications in the modern world range from reading data from a scratched disc, to broadcasting messages between planets. Different transmission methods, or codes, are required for different uses; one important type is a binary linear code, in which each message is interpreted as strings of zeroes and ones, and is encoded into a longer zero-one string (or codeword) with a special form. Two desirable properties of a code, difficult to maximize simultaneously, are its rate, a measure of how efficiently it transmits information, and its minimum distance, a measure of its tolerance to errors. I propose to use deep new ideas in an area of mathematics known as matroid theory to study theoretical limits on how well a code or class of codes can perform in this sense, as well as how rapidly codes can be decoded by computers. A matroid is an abstract mathematical object that can be thought of as a configuration of points in multidimensional geometric space. A special type of matroid is a binary matroid, which corresponds to a binary linear code. Two subclasses of the binary matroids are the graphic and cographic matroids, which are matroids whose structure arises from a network of nodes and edges; all three of these mentioned classes have the desirable property of being minor-closed. A rich theory has developed that describes the structure of minor­ closed classes of binary matroids, and consequently of binary codes. In particular, though nearly all binary codes are neither graphic nor cographic, a recent seminal result of Geelen, Gerards and Whittle shows that in every minor-closed subclass of binary codes, almost all the members are 'close' to being graphic or cographic. This latter result has huge implications in coding theory; roughly, any property that is known to be true for the graphic/cographic codes should apply more widely to minor-closed classes. One such property is the maximum-likelihood decoding threshold, a measure of exactly what error rate a code can tolerate while still performing effectively. With S. van Zwam, I recently determined this threshold for the graphic codes, and propose to extend it to all minor-closed classes of binary linear codes. Another property concerns the algorithmic problem of decoding codewords; for graphic/cographic codes it is known that decoding can be performed efficiently by a computer, but for binary codes it is known that decoding is 'NP-hard'; I propose to use matroid structure theory to understand precisely what the theoretical barrier is to efficient decoding that creates this divide. This research should have a significant contribution on our understanding of the theoretical capability and limits of information transmission, and will also strengthen the mostly untapped link between the fields of coding theory and structural matroid theory.

编码理论是研究以容忍传输错误的方式发送信息的方法。它在现代世界的各种应用范围从阅读数据从一个划痕光盘，以广播信息之间的行星。不同的用途需要不同的传输方法或代码;一种重要的类型是二进制线性代码，其中每个消息都被解释为0和1的字符串，并以特殊形式编码为更长的0 - 1字符串（或码字）。编码的两个理想特性很难同时最大化，一个是它的速率，一个是它传输信息的效率，另一个是它的最小距离，一个是它对错误的容忍度。我建议使用数学领域的新思想，即拟阵理论，来研究一个代码或一类代码在这个意义上的性能以及计算机解码代码的速度的理论极限。 拟阵是一个抽象的数学对象，可以被认为是多维几何空间中的点的配置。一种特殊类型的拟阵是二进制拟阵，它对应于二进制线性码。二进制拟阵的两个子类是图拟阵和余图拟阵，它们的结构源于节点和边的网络;所有这三个提到的类都具有小闭的理想性质。一个丰富的理论已经发展，描述了结构的次要的封闭类的二进制拟阵，因此，二进制码。特别是，虽然几乎所有的二进制码既不是图形也不是上图，但Geelen，Gerards和Whittle最近的一个开创性结果表明，在二进制码的每个小封闭子类中，几乎所有的成员都“接近”是图形或上图。 后一个结果在编码理论中有着巨大的意义;粗略地说，任何已知对图/上图码为真的性质都应该更广泛地应用于小闭类。一个这样的属性是最大似然解码阈值，这是一个衡量代码在有效执行的同时可以容忍多大错误率的指标。链球菌货车Zwam，我最近确定了这个阈值的图形码，并建议将其扩展到所有的小封闭类的二元线性码。另一个属性涉及的算法问题的解码码字;图形/cographic代码，它是已知的，解码可以有效地由计算机执行，但对于二进制代码，它是已知的解码是“NP难”;我建议使用拟阵结构理论，以准确地了解什么是有效的解码，创建这种划分的理论障碍。 这项研究应该对我们理解信息传输的理论能力和限制有重大贡献，也将加强编码理论和结构拟阵理论领域之间尚未开发的联系。