Fault Tolerant Single Error Correction Encoders

Soft errors are an important issue for circuit reliability. To mitigate their effects on the system functionality, different techniques are used. In many cases Error Correcting Codes (ECC) are used to protect circuits. Single Error Correction (SEC) codes are commonly used in memories and can effectively remove errors as long as there is only one error per word. Soft errors however may also affect the circuits that implement the Error Correcting Codes: the encoder and the decoder. In this paper, the protection against soft errors in the ECC encoder is studied and an efficient fault tolerant implementation is proposed.     

Efficient error detection in Double Error Correction BCH codes for memory applications

To prevent soft errors from causing data corruption, memories are commonly protected with Error Correction Codes (ECCs). To minimize the impact of the ECC on memory complexity simple codes are commonly used. For example, Single Error Correction (SEC) codes, like Hamming codes are widely used. Power consumption can be reduced by first checking if the word has errors and then perform the rest of the decoding only when there are errors. This greatly reduces the average power consumption as most words will have no errors. In this paper an efficient error detection scheme for Double Error Correction (DEC) Bose–Chaudhuri–Hocquenghem (BCH) codes is presented. The scheme reduces the dynamic power consumption so that it is the same that for error detection in a SEC Hamming code.     

Basic encoders for Abelian convolutional codes

A specific criterion is presented to check the noncatastrophic property of encoders for a convolutional code with a certain type of automorphism. In most cases to which the criterion is applicable, only a very small amount of computation is required.     

A note on tailbiting codes and their feedback encoders

Tailbiting codes encoded by feedback convolutional encoders are studied. A condition for when tailbiting will work is given and it is described how the encoder starting state can be obtained for feedback encoders in both controller and observer canonical forms. Finally, results from a search for systematic feedback encoders that encode tailbiting codes with good decoding bit error probabilities are presented     

Punctured recursive convolutional encoders and their applicationsin turbo codes

Puncturing is the predominant strategy to construct high code rate convolutional encoders, and infinite impulse response (IIR) convolutional encoders are an essential building block in turbo codes. In this paper, various properties of convolutional encoders with these characteristics are developed. In particular the closed-form representation of a punctured convolutional encoder and its generator matrix is constructed, necessary and sufficient conditions are given such that the punctured encoders retain the IIR property, and various lower bounds on distance properties, such as effective free distance, are developed. Finally, necessary and sufficient conditions are given on the inverse puncturing problem: representing a known convolutional encoder as a punctured encoder     

Designing fault-secure parallel encoders for systematic linear error correcting codes

We consider the open problem of designing fault-secure parallel encoders for various systematic linear ECC. The main idea relies on generating not only the check bits for error correction but also, separately and in parallel, the check bits for error detection. Then, the latter are compared against error detecting check bits which are regenerated from the error correcting check bits. The detailed design is presented for encoders for CRC codes. The complexity evaluation of FPGA implementations of encoders with various degrees of parallelism shows that their fault-secure versions compare favorably against their unprotected counterparts both with respect to complexity and the maximal frequency of operation. Future research will include the design of FS decoders for CRC codes as well as the generalization of the presented ideas to design of FS encoders and decoders for other systematic linear ECC like nonbinary BCH codes and Reed-Solomon codes.     

Design of parallel fault-secure encoders for systematic cyclic block transmission codes

In this paper, we consider the problem of designing parallel fault-secure encoders for various systematic cyclic linear codes used in data transmission. It is assumed that the data to be encoded before transmission are stored in a fault-tolerant RAM memory system protected against errors using a cyclic linear error detecting and/or correcting code. The main idea relies on taking advantage of the RAM check bits to control the correct operation of the cyclic code encoder as well. A slightly modified encoder allows not only for encoding the transmission data stream but also, independently and in parallel, to generate the reference check bits which allow for concurrent error detection in the encoder itself. The error detection capacity proves to be effective and grants good levels of protection as shown by error injection campaigns on encoders for various standard linear cyclic error detecting and error correcting codes. Moreover, the complexity evaluation of the FPGA implementations of the encoders shows that their fault-secure versions compare favorably against the unprotected ones, both with respect to hardware complexity and the maximal frequency of operation.     

可纠正单个错误的并行CRC解码器的设计

在数据传输的过程中通常使用循环冗余校验（CRC）,以检查数据传送过程中是否发生了错误.通常当解码器发现数据帧中有错误发生时都会要求重新发送该数据帧.针对有的同步协议要求解码器同时具有纠正帧头部分发生的单个错误的功能.以CRC的基本原理为基础,分别从算法和程序实现上,介绍了一种高效的硬件实现并行8位CRC-ITU-T检查并纠正发生在16位原始数据和16位CRC码中单个传输错误的校验器.最后给出了相应的综合结果和时序仿真图.     

Error control codes for QAM signalling

A class of block codes is described which exploits the properties of quadrature amplitude modulation signal constellations whose points lie on a square grid. The simplest codes in the class have block lengths 4 and 8 and offer coding gains of 3 dB and 4.5 dB, respectively.     

Error recovery for variable length codes

When an error occurs in the encoded bit stream produced by a variable length code, the decoder may lose synchronization. A state model for synchronization recovery is developed, and a method for determining the expected span of source symbols lost is presented. The performance of various codes with respect to error recovery is discussed. Two examples are given where equivalent optimal codes have a marked difference in their error recovery characteristics. Some open problems are indicated.     

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.     

关于计算机服务器系统的容错技术

随着信息技术的发展，计算机服务器系统在我国的得到了非常广泛的应用，小到中小企业，大到电力、国防、卫生等重点行业都离不开计算机服务器系统提供7*24小时不间断的工作。因此，一旦计算机服务器系统发生故障，就可能会带来巨大的经济损失。基于此，本文对计算机服务器系统的容错技术进行了探讨。     

Enhanced Low Complex Double Error Correction Coding with Crosstalk Avoidance for Reliable On-Chip Interconnection Link

As the technology scales down, shrinking geometry and layout dimension, on- chip interconnects are exposed to different noise sources such as crosstalk coupling, supply voltage fluctuation and temperature variation that cause random and burst errors. These errors affect the reliability of the on-chip interconnects. Hence, error correction codes integrated with noise reduction techniques are incorporated to make the on-chip interconnects robust against errors. The proposed error correction code uses triplication error correction scheme as crosstalk avoidance code (CAC) and a parity bit is added to it to enhance the error correction capability. The proposed error correction code corrects all the error patterns of one bit error, two bit errors. The proposed code also corrects 7 out of 10 possible three bit error patterns and detects burst errors of three. Hybrid Automatic Repeat Request (HARQ) system is employed when burst errors of three occurs. The performance of the proposed codec is evaluated for residual flit error rate, codec area, power, delay, average flit latency and link energy consumption. The proposed codec achieves four magnitude order of low residual flit error rate and link energy minimization of over 53 % compared to other existing error correction schemes. Besides the low residual flit error rate, and link energy minimization, the proposed codec also achieves up to 4.2 % less area and up to 6 % less codec power consumption compared to other error correction codes. The less codec area, codec power consumption, low link energy and low residual flit error rate make the proposed code appropriate for on chip interconnection link.     

面向分布式网络数据的容错控制策略

随着多核处理器核心数量的增多,系统容量的扩大,在制造和运行过程中产生的故障将会增多,容错能力对于系统的可靠性将变得更加重要。而一个片上系统的正常工作,将会非常依赖于片上网络系统传输数据的可靠性。芯片的制造偏差和组件故障、多处理器系统芯片集成不规则IP以及动态的电源门控都将导致片上网络中出现不规则拓扑结构。片上网络应当具备可以重新配置网络路由方式并将数据传输路径绕过无法正常工作的位置。文中设计了一种用于路由计算的特定约束跳转配置方法,为了保证其健壮性,采用基于局部信息的通信方式,设计实现了分布式的路由器传输路径配置单元,并完成了该方法的算法实现。     

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

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

Labelings and encoders with the uniform bit error property withapplications to serially concatenated trellis codes

The well-known uniform error property for signal constellations and codes is extended to encompass information bits. We introduce a class of binary labelings for signal constellations, called bit geometrically uniform (BGU) labelings, for which the uniform bit error property holds, i.e., the bit error probability does not depend on the transmitted signal. Strong connections between the symmetries of constellations and binary Hamming spaces are involved. For block-coded modulation (BCM) and trellis-coded modulation (TCM) Euclidean-space codes, BGU encoders are introduced and studied. The properties of BGU encoders prove quite useful for the analysis and design of codes aimed at minimizing the bit, rather than symbol, error probability. Applications to the analysis and the design of serially concatenated trellis codes are presented, together with a case study which realizes a spectral efficiency of 2 b/s/Hz     

VLSI容错设计研究进展(1)——缺陷的分布模型及容错设计的关键技术

随着芯片面积的增加及电路复杂性的增强，芯片的成品率逐渐下降，为了保证合理的成品率，人们将容错技术结合入了集成电路。文中首先概述了缺陷及其分布，然后概述了容错技术，并详细地叙述了动态容错技术中的两个关键问题：故障诊断及冗余单元的分配问题。     

Rateless Forward Error Correction for Topology-Transparent Scheduling

Topology-transparent scheduling for mobile wireless ad hoc networks has been treated as a theoretical curiosity. This paper makes two contributions towards its practical deployment: (1) We generalize the combinatorial requirement on the schedules and show that the solution is a cover-free family. As a result, a much wider number and variety of constructions for schedules exist to match network conditions. (2) In simulation, we closely match the theoretical bound on expected throughput. The bound was derived assuming acknowledgments are available immediately. We use rate less forward error correction (RFEC) as an acknowledgment scheme with minimal computational overhead. Since the wireless medium is inherently unreliable, RFEC also offers some measure of automatic adaptation to channel load. These contributions renew interest in topology-transparent scheduling when delay is a principal objective.     

Error probability for block codes over channels with blockinterference

A methodology is presented to evaluate analytically the error probability for block codes over block interference channels. The proposed analysis is based on the knowledge of the moments of the bit-error probability over the interference, thus allowing, for instance, fast performance evaluation of block-coded slow frequency hopping (SFH) systems with antenna diversity over fading channels. As an example of application, slow frequency hopping multiple access (SFHMA) systems with nonideal interleaving are analyzed in the presence of fading, cochannel interference, and additive Gaussian noise     

Forward Error Correction for an ARQ Scheme

This paper examines the use of BCH error-correcting codes in improving the performance of a stop-and-wait automatic repeat-request (ARQ) scheme over random error and Rayleigh fading channels. Two models are analyzed. The first model considers the effect of forward error correction on the mean wasted time per message. The second model assumes a Poisson arrival process for the messages and examines the effect of forward error correction on the mean time between the arrival of a message and its successful transmission. In both models, our results indicate that the performance of the ARQ scheme can be substantially improved by the use of forward error correction.