插入删除纠错码的列表译码机理与算法研究

Since insertion and deletion of symbols fundamentally change the transmitted data structure, the technique of traditional error-correcting codes is no longer applicable, so the study of insertion and deletion codes (insdel codes for short) becomes one of cutting-edge and popular topics in coding theory. Recently, insdel codes along with their constructions and decoding algorithms are widely used in communications, computing, biology, linguistics, etc. Unique decoding of insdel codes can only have decoding radius up to the half of the minimum insertion and deletion distance. In order to surpass the limitation of the unique decoding of insdel codes, the list decoding of insdel codes is an important and interesting research direction. This project focuses on the following: Firstly, by analyzing the bound for the size of insertion and deletion balls, we derive the limit of list decoding radius for insdel codes. Secondly, we investigate the list decodability of random (linear) insdel codes. We analyze whether the list decoding radius of random (linear) insdel codes can achieve the limit of the list decoding radius. Thirdly, based on the concatenated codes and the properties of list-recoverable codes, we focus on the construction of list-decodable insdel codes with good parameters and the design of their efficient list decoding algorithms.

由于符号插入与删除导致数据传输差错模式发生了根本性变化，传统的纠错码技术不再适用，因此插入删除纠错码（简称，插删码）成为编码领域研究的前沿热点课题之一。插删码及其构造与译码算法正广泛应用于通信、计算机、生物学和语言学等。由于插删码唯一译码的译码半径不能超过最小插入删除距离的一半，为突破插删码唯一译码的局限性，插删码的列表译码成为颇受关注的一个重要和热点方向。本项目主要研究：第一，通过分析插入删除球大小的界，探索插删码列表译码半径的极限值；第二，研究随机（线性）插删码的列表可译性，并分析随机（线性）插删码的列表译码半径能否达到其列表译码半径的极限值；第三，通过级联码方案并结合列表可恢复码的特性，构造具有良好参数性质的列表可译的插删码并设计其有效的列表译码算法。

随着计算机和网络技术的发展，在实际应用中差错模式发生根本性的变化导致经典纠错码技术失效，从而出现插入删除纠错码（简称，插删码）的编码方案。插删码及其构造与译码算法正广泛应用于通信、计算机、生物学和语言学等。由于插删码唯一译码的译码半径不能超过最小插入删除距离的一半，为突破插删码唯一译码的局限性，插删码的列表译码成为颇受关注的一个重要和热点方向。本项目首先通过分析插入删除球大小的界，给出插删码列表译码半径的极限值；随后，研究随机（线性）插删码的列表可译性；最后，通过级联码方案并结合列表可恢复码的特性，构造具有良好参数性质的列表可译的插删码并设计其有效的列表译码算法。特别地，给出2维Reed-Solomon码在插删度量下的明确构造。