Reed-Solomon码的深洞问题

Coding theory is the cross discipline of mathematics and computer science. It provides methods (error correcting codes) and mathematical fundamental for reliable communications. One main task of error correcting codes is by the way of adding the least redundancy to make the message have the largest error correcting ability. The other main task is how to correct the error in the received message fast and efficiently. Since Reed-Solomon codes have advantages of good error-correcting ability and fast encoding/decoding algorithms, they become one of the earliest algebraic coding techniques applied in engineering. They have many important applications, the most prominent of which include consumer technologies such as CDs, DVDs, Blu-ray Discs, etc. The improved decoding algorithms and the limitation of their performances have been attracting the attension of many mathematicians and computer scientists for many decades. Deep holes of Reed-Solomon codes play an important role in the decoding of Reed-Solomon codes. The main issue of this project is to study the deep holes of Reed-Solomon codes, especially projective Reed-Solomon codes, extended Reed-Solomon codes and primitive Reed-Solomon codes. As an extension of our research, we will also study the covering radii and deep holes of MDS codes.

编码理论是数学与计算机科学交叉学科，为可靠通信提供方法（纠错码）与数学基础。纠错码的一个重要任务是通过增加尽量少的冗余使得所传输消息具有尽量大的纠错能力，另一个重要任务就是如何对于接收向量进行快速有效地纠错。Reed-Solomon码因为其较强的纠错能力与快速的编译码算法等优点，是最早被应用在工程中的代数编码技术之一，被广泛的应用于各种商业用途，最显著的是在CD、DVD和蓝光光盘等上的使用。于是，Reed-Solomon码的译码算法的改进与译码性能界就成了这几十年来的热点问题。然而，Reed-Solomon码的深洞在其译码中起重要作用，本项目旨在研究Reed-Solomon码的深洞问题，特别是投影Reed-Solomon码、扩展Reed-Solomon码和本原Reed-Solomon码，拟完全解决这三类Reed-Solomon码的深洞问题。同时，本项目还将研究MDS码的覆盖半径与深洞问题。

Reed-Solomon码是工程中应用最广泛的代数编码之一，其具有较强的纠错能力与快速的编译码算法等优点。在理论计算机中，Reed-Solomon码的译码算法的改进与译码性能界就成了这几十年来的热点问题。然而，Reed-Solomon码的深洞在其译码中起重要作用，本项目旨在研究Reed-Solomon码的深洞问题。本项目取得的重要结果如下：1. 对于投影Reed-Solomon码，找到了三大类深洞，结合使用了传统的编码方法，有限几何方法以及群的作用，并且证明了对于余维数为3,4的投影Reed-Solomon码这三类深洞构成了其所有深洞。2. 对于余维数为5的投影Reed-Solomon码，还会有其它深洞，难度增加了很多，目前这部分工作仍然在整理中。3. 对于一些特殊参数的Reed-Solomon码，我们利用组合的方法，也给出了一些深洞的构造。4. 作为该问题的一个自然延拓是考虑MDS码的覆盖半径和深洞问题，我们纠正了前人文献中的错误，并且指出至今该问题还有待解决。5. 新的模型下的性能优越的编码的构造：“符号对”阅读信道下的MDS码的构造，我们利用有限几何完全解决了极小距离等于5的构造问题，同时利用椭圆曲线给出了较大极小距离的一般性构造；非对称错误信道下的编码构造问题，我们利用函数域给出了一般性构造，取一些具体的函数域时，得到的编码其性能超越了前人的构造。