On Randomized Linear Network Codes and Their Error Correction Capabilities
On Randomized Linear Network Codes and Their Error Correction Capabilities
复制标题
DOI：
10.1109/tit.2009.2018173
复制
发表时间：
2009-07
影响因子：
2.5
通讯作者：
Huseyin Balli;Xijin Yan;Zhen Zhang
中科院分区：
文献类型：
--
作者：
Huseyin Balli;Xijin Yan;Zhen Zhang
在Ho等人中引入并分析了用于单源多播的随机线性网络代码。 （信息理论的IEEE交易，2006年10月），其中主要结果是代码故障概率的上限。在本文中，这些界限得到了改善，并通过分析故障概率的限制行为来研究新边界的紧密度，因为现场大小是无穷大的。在单源多播的线性随机编码设置中，张定义的代码的最小距离（信息理论的IEEE交易，2008年1月）是一个随机变量，采用非负整数值，可满足最近在Singleton绑定的不平等，最近建立在界线中的不平等值Yeung and CAI（信息与系统中的通信，2006年），用于网络错误校正代码。我们根据我们的改进的上限为故障概率而得出了随机线性网络代码最小距离的概率质量函数的结合。在单胎结合中具有最高最小距离的代码称为最大距离可分离（MDS）。在张报告的MDS代码存在所需的场大小（IEEE信息理论的交易，2008年1月）和Matsumoto（Arxiv：cs.it/0610121，2006年10月）所需的界限所需的界限表明，这种代码仅在字段时才存在尺寸很大。将代码的降解定义为Singleton绑定中最高最小距离与代码的实际最小距离之间的差。最小距离的概率质量函数的界限导致与给定最大降解的网络误差校正代码所需的场大小结合。结果表明，允许轻微降解会大大减少所需的场大小。
Randomized linear network code for single source multicast was introduced and analyzed in Ho et al. (IEEE Transactions on Information Theory, October 2006) where the main results are upper bounds for the failure probability of the code. In this paper, these bounds are improved and tightness of the new bounds is studied by analyzing the limiting behavior of the failure probability as the field size goes to infinity. In the linear random coding setting for single source multicast, the minimum distance of the code defined in Zhang, (IEEE Transactions on Information Theory, January 2008) is a random variable taking nonnegative integer values that satisfy the inequality in the Singleton bound recently established in Yeung and Cai (Communications in Information and Systems, 2006) for network error correction codes. We derive a bound on the probability mass function of the minimum distance of the random linear network code based on our improved upper bounds for the failure probability. Codes having the highest possible minimum distance in the Singleton bound are called maximum distance separable (MDS). The bound on the field size required for the existence of MDS codes reported in Zhang, (IEEE Transactions on Information Theory, January 2008) and Matsumoto (arXiv:cs.IT/0610121, Oct. 2006) suggests that such codes exist only when field size is large. Define the degradation of a code as the difference between the highest possible minimum distance in the Singleton bound and the actual minimum distance of the code. The bound for the probability mass function of the minimum distance leads to a bound on the field size required for the existence of network error correction codes with a given maximum degradation. The result shows that allowing minor degradation reduces the field size required dramatically.