线性网络纠错码的构造算法与性能分析

结题报告

项目介绍

AI项目解读

基本信息

批准号：
61171082
项目类别：
面上项目
资助金额：
60.0万
负责人：
符方伟
依托单位：
南开大学
学科分类：
F0101.信息论
结题年份：
2015
批准年份：
2011
项目状态：
已结题
起止时间：
2012-01-01 至2015-12-31

项目参与者：
光炫；张俊；李信然；任文丽；邱晓聪；卓勇霖；张群；朱文斌；申林志；
关键词：
网络编码性能分析随机网络编码线性网络纠错码构造算法

项目摘要

综合利用信息论、编码理论、网络编码理论、概率论、代数和图论的知识和方法研究线性网络纠错码的理论、构造算法和性能分析。设计线性网络纠错码的多项式时间构造算法，对于给定的纠错能力，该算法能够在多项式时间范围内构造出一个具有给定的纠错能力的线性网络纠错码，并且估计该算法所需的基域的大小。特别地，该算法可以构造出线性网络纠错的MDS码，并且所需的基域的大小可以小于目前已知的结果。研究随机线性网络纠错编码的性能分析，给出随机线性网络纠错码的失败概率的估计。研究通用的线性网络纠错码，在理论上证明通用网络MDS码的存在性，设计通用网络MDS码的多项式时间构造算法。将四类重要的线性网络编码的概念推广到线性网络纠错编码，推导这四类线性网络纠错码的Singleton界和设计相应的线性网络MDS码的构造算法。这项研究的进展将丰富网络编码的理论，使我们能够提高网络通信的效率和可靠性能，促进我国网络编码技术的发展。

结项摘要

在本项目中，我们综合利用信息论、编码理论、网络编码理论、概率论、代数和图论的知识和方法研究线性网络纠错码的理论、构造算法和性能分析。我们设计了线性网络纠错码的多项式时间构造算法，对于给定的纠错能力，该算法能够在多项式时间范围内构造出一个具有给定的纠错能力的线性网络纠错码，并且估计了该算法所需的基域的大小。特别地，该算法可以构造出线性网络纠错的MDS码，并且所需的基域的大小可以小于目前已知的结果。我们研究随机线性网络纠错编码的性能分析，给出了随机线性网络纠错码的失败概率的好的估计。我们研究通用的线性网络纠错码，在理论上证明了通用网络MDS码的存在性，设计了通用网络MDS码的多项式时间构造算法。我们研究安全网络编码，给出一些新的构造算法和性能界。我们将四类重要的线性网络编码的概念推广到线性网络纠错编码，研究和推导出这四类重要的线性网络纠错码的Singleton界和相应的线性网络纠错的MDS码的构造方法。这项研究的进展将丰富网络编码的理论，使我们能够提高网络通信的效率和可靠性能，促进我国网络编码技术的发展。