级联的网络纠错编码理论的研究

The theory of network error correction coding is one of the most important branches of network coding theory, which focuses on the error control problem under the background of network coding. There are two different types of research lines, called traditional coding approach and subspace coding approach, respectively. When theoretical research and practical applications are under consideration simultaneously, we find that two types of codes have limitations on some different performances, respectively. In order to solve these problems, we propose an idea of concatenated network error correction coding. In this project, we will study the concatenated network error correction coding by applying the knowledge and the methods from the fields of information theory, coding theory, network coding theory, network error correction coding, subspace coding, algebra and graph theory. And the main research problems include the structure of concatenated network error correction codes, their error detection and error correction capabilities, some important coding bounds and the corresponding achievability, the existence and construction of the optimal codes, and the rule and algorithms of the encoding and decoding. The results of the research will enrich network coding theory and will be significant to the theoretical research and practical applications. In addition, the results will be also helpful to promote the development of the network coding technology in our country.

网络纠错编码是网络编码理论的一个重要分支，主要研究网络编码背景下的差错控制问题，其主要有两个不同研究方法：分别称为传统编码和子空间编码。基于理论和应用两方面的考虑，我们发现两类码分别在不同的重要性能指标上存在着缺陷，但两者恰好互补。为解决这些问题，我们提出了级联网络纠错编码的思想。本项目拟综合利用信息论、编码理论、网络编码、网络纠错编码、子空间编码以及代数和图论的知识去研究级联网络纠错编码。具体研究内容包括：级联网络纠错码的结构，检错和纠错能力，性能界及其可达性，最优码的存在与构造算法，以及编译码规则和算法。这项研究的进展将丰富网络编码理论，具有较重要的理论价值和应用前景，此外，也有利于我国网络编码技术的发展。

网络编码是信息论领域近年来的一个重要的研究方向，其思想为网络的中间结点对接收到的信息可以进行编码。网络纠错编码是网络编码理论的一个重要分支，主要研究网络编码背景下的差错控制问题，其主要有两个不同研究方法：分别称为传统编码和子空间编码。在本项目中，我们引入级联网络纠错码以实现变率网络纠错编码，特别是网络纠错MDS码。我们利用信息论、编码理论、网络编码、网络纠错编码、子空间编码以及代数和图论的知识去研究级联网络纠错编码。我们探索了所提出的网络纠错码的结构，检错纠错能力。研究这种网络纠错码的性能界，给出了这种级联网络纠错编码理论中的Singleton界。对于该性能界证明了其可达性以及达到该性能界的最优码的存在性，并且给出了多项式时间构造算法。具体来说，对于基础理论研究，证明性能界的可达性，或等价地，证明了最优码的存在性。对于实际应用，研究具有较低时间复杂度的网络纠错码构造算法。特别地，对于任何给定的纠错能力，我们设计一个具有低时间复杂度的码构造算法。.在安全网络编码中，有限域大小是一个非常重要的指标，其很大程度上决定了网络编码的计算复杂度和存储复杂度。我们利用网络的拓扑结构，使用信息论和图论的方法对于所有的获得了安全网络编码的基域的大小的一个紧的下界，该结果大大改进了已知的上界。在安全网络编码理论中，两个基本研究问题是：在某种安全性的约束下，能够传输的最大信息量是多少？以及为了保证安全性所需的最小随机量是多少？我们研究该基本问题，其主要结果指出最优的随机量仅依赖于安全约束，特别地，其独立于信息传输量。也就是说，我们并不能通过降低信息率来降低所需的随机量。对于完备安全与非完备安全，我们均得到了相应的结论。此外，我们也研究了局部保持的安全网络编码。.我们研究了网络函数计算问题。其数学理论可归结为是网络上的函数计算问题，即，要求通过网络上的数据运算和传输来计算一个数学函数，其可以看作是更一般化的网络编码理论。最重要的一个并且仍未解决的信息论问题是其函数的网络计算容量问题。我们该研究成果确定了函数的网络计算容量的一个最紧的上界，该上界是目前为止所知的最好的上界。其适用于任何的网络与任何的函数。该上界对于一个著名的网络函数计算问题达到其计算容量，这是该问题自11年提出后首次得到对其可紧的上界。该研究进展丰富了网络编码理论，具有重要的理论价值和应用前景，有利于我国网络编码技术发展。