基于代数几何的译码算法

With the rapid development of the subject of big data and the rapid increase of information data size, reliable data storage becomes more important in our realistic life. In the face of data corruption caused by hardware failure, how to make the most rapid and effective error correction decoding is an issue of great concern to engineers. List decoding was introduced in 1950s, and it is a relaxed version of unique decoding, which can correct more errors，which has become a hot and important research topic in coding theory. Based on the theory of arithmetic algebraic geometry, this project is to study several types of error-correcting codes which are commonly used in current data storage systems. We will analyze the algebra structures of different types of errors and the list-decodablity for random cases, find the tradeoffs among list decoding radius, rate and minimum distance. By using the results of algebraic geometry and the techniques for constructing classic codes, we attempt to construct good error-correcting codes with efficient list decoding algorithms and optimal list decoding radius, especially for the codes over small finite field. Implementation of this project will explore some new construction techniques of list decoding algorithm, further enrich the theoretical system of list decoding in further, and provide new ideas for solving practical problems such as effectively recover data corruption caused by hardware failure.

随着大数据学科的飞速发展以及信息和电子数据的快速增加，可靠的数据存储变得尤为重要。在对抗硬件故障造成的数据损坏中，如何最快速有效的进行纠错译码是工程中的关键问题。上世纪50年代提出的列表译码较经典的唯一译码可以纠正更多的错误，现已成为纠错码中的一个重要研究领域。本项目是基于有限域上代数几何理论去研究目前数据存储系统中常用的几类纠错编码的译码问题。通过分析不同类型错误的代数结构及对应的随机码的列表译码参数，找到列表译码半径与信息率以及最小距离之间的关系，同时利用代数几何的结论和经典码的技巧构作好的具有有效列表译码算法的纠错码，尤其是小域上的码。本项目的实施将发掘列表译码算法中的新的构造技巧，进一步完善列表译码算法的理论体系，为恢复由硬件故障造成的数据损失等应用问题提供新的解决思路。

随着大数据学科的飞速发展以及信息和电子数据的快速增加，可靠的数据存储变得尤为重要。本项目是基于有限域上代数理论去研究目前数据存储系统中常用错误的修复问题。1）分布式存储中使用的矩阵码的译码问题。通过建立不同度量之间的代数强弱关系，推导出强度量具有更优的列表译码性质；构造了达到Singleton界的列表可译的覆盖度量码。2）线性码的正交包研究。给出了循环码的伽罗华正交包的若干代数刻画；具体构造了具有小的正交包维数的线性码，并将结果运用到纠缠辅助量子纠错码的构造上。3）准扭码的相关研究。研究了常循环码的若干对偶刻画，并证明了准扭码是一类渐进好码。