多播网络编码中线性可解性若干新问题研究

In network coding theory, multicast network coding is the earliest and most fundamental research topic. According to a series of classical results, the size of a base field is a key factor that affects the linear solvability of multicast networks over this base field. However, we have recently revealed, by establishing explicit multicast networks, that the existence of a linear solution over a base field does not necessarily imply the existence of a linear solution over every larger base field. This result asserted, for the first time in the literature, that the size is not the only algebraic identity of a base field that affects the linear solvability of multicast networks, and unveiled that the algebraic structure of multiplicative subgroups of a base field is a new influencing factor. In this project, we aim at developing the theory of linear network coding (LNC) along this new research thread. First, we shall further elucidate the inherent role of the algebraic structure of multiplicative subgroups in a field on linear solvability of multicast networks. Next, we shall generalize the expected results in field-based scalar LNC to vector LNC based on vector spaces and convolutional network coding based on polynomial rings. Third, we shall re-examine and compare these three types of LNC from the perspective of required encoding alphabet size to yield a solution. Last, we shall propose a new algebraic structure to model a special class of LNC schemes based on circular-shift operations, which endow lower encoding and decoding complexities, and study the linear solvability of circular-shift LNC on multicast networks. We expect that the theoretical results to be delivered in this project can provide more comprehensive fundamental support to other research subareas in network coding theory.

多播网络编码是网络编码理论中最基础的研究方向。其中一系列经典成果均显示基域大小是影响多播网络线性可解性的一个重要因素。然而，项目组近期研究成果首次明确指出基域大小不是影响多播网络线性可解性的唯一代数结构参量，并论证了基域中乘法子群代数结构也是一个重要影响因素。本项目拟沿这条全新思路，对新衍生出的多播网络编码若干开问题展开研究。首先，拟进一步阐明基域的乘法子群与多播网络线性可解性的本质联系。其次，拟将基于有限域的标量网络编码中取得的新成果进一步扩展至基于向量空间的向量网络编码以及基于多项式环的卷积网络编码。再次，拟从多播网络线性解所需编码符号集大小的角度从新审视比较这三类网络编码、建立三者间新关联。最后，拟提出新型代数结构建模具有更低编译码复杂度的循环移位网络编码并研究其于多播网络的线性可解性。本项目以新视角预期取得的线性网络编码相关成果会为网络编码其它研究子领域提供更全面的基础理论支持。

在本项目资助下，项目组成员建立了一套以循环移位操作代替经典有限域操作的全新线性网络编码框架，在IEEE信息论汇刊(T-IT)等国际知名期刊中发表了一系列循环移位网络编码相关论文，并获授权多项相关发明专利。与传统基于有限域的标量网络编码相比，循环移位网络编码不但同样可以渐进达到多播网络的网络容量，其编译码复杂度还可大幅降低。循环移位网络编码可以潜在替代目前大部分已知的标量网络编码传输方案，从而降低应用网络编码所带来的额外编译码开销，具有重要的应用前景。以所建立的循环移位网络编码理论为基础，项目组成员已与华为建立紧密合作，进一步研发出高效率低能耗可落地的网络编码技术。目前，在存储编码领域，项目负责人基于循环移位网络编码理论提出的循环移位纠删码技术已被华为实际落地应用。在项目执行期间，项目组成员共发表项目相关SCI检索期刊论文10篇、EI检索国际会议论文4篇，并获授权编码相关发明专利8项；项目负责人联合培养的博士生唐汉琦的毕业论文《循环移位网络编码》被评为北京科技大学优秀博士论文；项目负责人于2018年在中国电子学会信息论学术年会中开展了循环移位网络编码为主题的特邀大会报告，并于2018年分别获得了北京市科学技术三等奖（排名第三）以及中国电子协会信息论青年新星奖。