Linear Network Error Correction Codes in Packet Networks

In this paper, we study basic properties of linear network error correction codes, their construction and error correction capability for various kinds of errors. Our discussion is restricted to the single-source multicast case. We define the minimum distance of a network error correction code. This plays the same role as it does in classical coding theory. We construct codes that can correct errors up to the full error correction capability specified by Singleton bound for network error correction codes recently established by Cai and Yeung. We propose a decoding principle for network error correction codes, based on which we introduce two decoding algorithms and analyze their performance. We formulate the global kernel error correction problem and characterize the error correction capability of codes for this kind of error.     

字节式单向错误纠错码

介绍了一种有效的字节式单向错误纠错码及其编码和译码算法。从对校验位数下限值的讨论可以看出,这里介绍的码优于字节式对称错误纠错码,并且近似最优。本文还介绍了字节式非对称错误纠错码。     

On the Probability of Undetected Error for Linear Block Codes

The problem of computing the probability of undetected error is considered for linear block codes used for error detection. The recent literature is first reviewed and several results are extended. It is pointed out that an exact calculation can be based on either the weight distribution of a code or its dual. Using the dual code formulation, the probability of undetected error for the ensemble of all nonbinary linear block codes is derived as well as a theorem that shows why the probability of undetected error may not be a monotonic function of channel error rate for some poor codes. Several bounds on the undetected error probability are then presented. We conclude with detailed examples of binary and nonbinary codes for which exact results can be obtained. An efficient technique for measuring an unknown weight distribution is suggested and exact results are compared with experimental results.     

针对前向纠错编码的脉冲干扰技术研究

数字通信系统通常采用前向纠错编码提高系统可靠性,传统干扰方法针对采用前向纠错编码通信系统的干扰效果较差,为了克服此缺点,提出了通过控制错误分布的脉冲干扰方法。分析了典型卷积码和RS码的纠错能力,根据2种纠错编码的特性分别探讨了干扰信号设计原则和方法。计算机仿真表明,针对不同的编码样式采用特定脉冲干扰参数,能够取得更好的干扰效果。     

纠错算术码的检错时延分布研究

算术码是一种高效的熵编码,但是对误码十分敏感,由此引入了纠错算术码。以往研究中发现基于比特填充法的纠错算术码,其检错时延分布近似几何分布。文中通过研究基于比特跟随法的纠错算术码的检错时延分布,建立了符号检错时延分布的伽马分布模型,并通过曲线拟合得到了伽马分布的参数与影响因素之间的数学关系。拟合计算得出的数据与实验数据比较证实了新模型的可靠性。     

On Metrics for Error Correction in Network Coding

The problem of error correction in both coherent and noncoherent network coding is considered under an adversarial model. For coherent network coding, where knowledge of the network topology and network code is assumed at the source and destination nodes, the error correction capability of an (outer) code is succinctly described by the rank metric; as a consequence, it is shown that universal network error correcting codes achieving the Singleton bound can be easily constructed and efficiently decoded. For noncoherent network coding, where knowledge of the network topology and network code is not assumed, the error correction capability of a (subspace) code is given exactly by a new metric, called the injection metric, which is closely related to, but different than, the subspace metric of KÖtter and Kschischang. In particular, in the case of a non-constant-dimension code, the decoder associated with the injection metric is shown to correct more errors then a minimum-subspace-distance decoder. All of these results are based on a general approach to adversarial error correction, which could be useful for other adversarial channels beyond network coding.      

On the Error Correction of Regular LDPC Codes Using the Flipping Algorithm

The iterative bit flipping algorithm is applied to the standard regular low-density parity-check (LDPC) code ensemble. In the past, it was shown, for a typical code in the ensemble with left degree at least five and block length sufficiently large, that this algorithm can correct a linear (in the block length) number of worst case errors. In this paper, this result is extended to the case where the left degree is at least four. For the case where the left degree is larger than four, an improvement, compared to existing results, of several orders of magnitude is obtained on the fraction of worst case errors that can be corrected. It is also shown how the results can be further improved when random errors produced by the channel (as opposed to worst case errors) are considered.     

基于LT码的LBCMP迭代纠错方法

针对删除信道中发生错误的数据包,提出联合信道编码的LBCMP迭代纠错方法,该方法充分利用错误数据包中含有的正确信息,将LT编码包作为冗余纠错包与线性分组码相结合,并采用MP迭代译码方法进行纠错.理论分析及实验结果表明,采用LBCMP迭代方法可以减少为恢复错误数据包所需要的信源编码包数量.     

线性分组码的神经网络译码

介绍了神经网络与线性分组码之间的关系，并在文献[1]的基础上证明了软判决译码与求解能量函数最大值之间的等价性，然后以(7，4，3)汉明码为例介绍了神经网络在循环码硬判决、软判决译码中的应用。     

非线性的模拟量绝对值纠错编码方法研究

为了更有效、实时地进行无线图像通信, 基于编码理论和非线性理论, 提出一种针对模拟量的三分支“咬尾”绝对值纠错编码方法和最大似然译码算法, 并与三分支“咬尾”Baker码相比较。经过仿真, 在图像传输中, 三分支“咬尾”绝对值纠错编码方法在高斯信道中的纠错性能远远超出后者, 恢复图像的PSNR有2 dB以上的增益, 并且其编译码的复杂度也大幅降低, 提升了通信有效性和实时性, 在信道的干扰或噪声大的图像通信中具有应用优势。     

一类新的线性码及重量分布

定义了一类新的线性码，它具有结构简单、码率较大的特点。利用一般方法产生了纠多个错的线性码。计算出这类线性码的重量分布，关于码的自同构群也得到了一些结果。     

Coherent网络中的纠错码

网络编码对网络中的传输错误或恶意攻击十分敏感,如果网络拓扑和网络码对于网络的收点和发点都是已知的,这种类型的网络称为Coherent网络。在Coherent网络中,网络汉明重量的概念拉近了网络纠错码和传统纠错码之间的距离,传统纠错码的一些理论和方法有望在将来应用于网络纠错码。类似于传统纠错码,极小距离反映了网络纠错码的纠错能力。利用陪集码理论去描述和研究网络纠错码是一个令人感兴趣的研究方向。     

Implementing Double Error Correction Orthogonal Latin Squares Codes in SRAM-based FPGAs

This paper studies the implementation of Double Error Correction Orthogonal Latin Squares (OLS) in Xilinx Field Programmable Gate Arrays (FPGAs). Several existing options to implement the decoder are considered and evaluated. The results show that the decoder complexity can be significantly optimized by appropriately selecting the implementation that is better suited to the internal FPGA structure. A new implementation tailored for the FPGA structure is proposed, which has a more efficient physical resource utilization compared with the existing ones. It is shown that the improvement on resource utilization is also highly correlated with the soft error vulnerability. The proposed decoder scheme has a reduced soft error cross section compared with other implementations. Based on these results, it seems that optimizing the ECC implementation for FPGAs can be effective and may be useful for other codes.     

On Minimal Tree Realizations of Linear Codes

A tree decomposition of the coordinates of a code is a mapping from the coordinate set to the set of vertices of a tree. A tree decomposition can be extended to a tree realization, i.e., a cycle-free realization of the code on the underlying tree, by specifying a state space at each edge of the tree, and a local constraint code at each vertex of the tree. The constraint complexity of a tree realization is the maximum dimension of any of its local constraint codes. A measure of the complexity of maximum-likelihood (ML) decoding for a code is its treewidth, which is the least constraint complexity of any of its tree realizations.It is known that among all tree realizations of a linear code that extends a given tree decomposition, there exists a unique minimal realization that minimizes the state-space dimension at each vertex of the underlying tree. In this paper, we give two new constructions of these minimal realizations. As a by-product of the first construction, a generalization of the state-merging procedure for trellis realizations, we obtain the fact that the minimal tree realization also minimizes the local constraint code dimension at each vertex of the underlying tree. The second construction relies on certain code decomposition techniques that we develop. We further observe that the treewidth of a code is related to a measure of graph complexity, also called treewidth. We exploit this connection to resolve a conjecture of Forney's regarding the gap between the minimum trellis constraint complexity and the treewidth of a code. We present a family of codes for which this gap can be arbitrarily large.     

高速光网络系统中的前向纠错技术

介绍了高速光网络系统中前向纠错(FEC)的重要性、基本功能、应用方式、应用分析及实现方案。     

宽带无线网络中的纠错编码

随着高速多媒体业务的迅速发展,如何提高第三代移动通信系统（3G）以及新一代移动通信系统（Beyond3G）的性能和容量愈发受到人们的重视。在业务无线接入时的服务质量（QoS）问题上,高效的纠错编码是必不可少且行之有效的解决方法之一。文中简要回顾了纠错码在前两代移动通信中的应用,并着重介绍了目前的研究热点——Turbo码和LDPC码的研究现状及发展前景。     

Design of Memories with Concurrent Error Detection and Correction by Nonlinear SEC-DED Codes

In this paper we propose memory protection architectures based on nonlinear single-error-correcting, double-error-detecting (SEC-DED) codes. Linear SEC-DED codes widely used for design of reliable memories cannot detect and can miscorrect lots of errors with large Hamming weights. This may be a serious disadvantage for many modern technologies when error distributions are hard to estimate and multi-bit errors are highly probable. The proposed protection architectures have fewer undetectable errors and fewer errors that are miscorrected by all codewords than architectures based on linear codes with the same dimension at the cost of a small increase in the latency penalty, the area overhead and the power consumption. The nonlinear SEC-DED codes are generalized from the existing perfect nonlinear codes (Vasil’ev codes, Probl Kibern 8:375–378, 1962; Phelps codes, SIAM J Algebr Discrete Methods 4:398–403, 1983; and the codes based on one switching constructions, Etzion and Vardy, IEEE Trans Inf Theory 40:754–763, 1994). We present the error correcting algorithms, investigate and compare the error detection and correction capabilities of the proposed nonlinear SEC-DED codes to linear extended Hamming codes and show that replacing linear extended Hamming codes by the proposed nonlinear SEC-DED codes results in a drastic improvement in the reliability of the memory systems in the case of repeating errors or high multi-bit error rate. The proposed approach can be applied to RAM, ROM, FLASH and disk memories.     

准循环码和七个新的二元线性码

本文利用一类准循环码的结构进行计算机搜索，再加上通常的码的变换，共得到了七个新的二元线性码，它们都改进了文「１」中二元线性码极小距离的下界，其中有三个是最优的。     

线性不等保护能力码的码长上界及应用

本文详细研究了线性不等保护能力码的码长上界,得到了一些优于文献[1]的结果,本文还讨论了新上界在线性不等保护能力码构造上的应用。