Multiple error detection and correction based on redundant residue number systems

This paper presents some results on multiple error detection and correction based on the Redundant Residue Number System (RRNS). RRNS is often used in parallel processing environments because of its ability to increase the robustness of information passing between the processors. The proposed multiple error correction scheme utilizes the Chinese Remainder Theorem(CRT) together with a novel algorithm that significantly simplifies the error correcting process for integers. An extension of the scheme further reduces the computational complexity without compromising its error correcting capability. Proofs and examples are provided for the coding technique.     

Error Correction Schemes with Erasure Information for Fast Memories

Two error correction schemes are proposed for word-oriented binary memories that can be affected by erasures, i.e. errors with known location but unknown value. The erasures considered here are due to the drifting of the electrical parameter used to encode information outside the normal ranges associated to a logic 0 or a logic 1 value. For example, a dielectric breakdown in a magnetic memory cell may reduce its electrical resistance sensibly below the levels which correspond to logic 0 and logic 1 values stored in healthy memory cells. Such deviations can be sensed during memory read operations and the acquired information can be used to boost the correction capability of an error-correcting code (ECC). The proposed schemes enable the correction of double-bit errors based on the combination of erasure information with single-bit error correction and double-bit error detection (SEC-DED) codes or shortened (SEC) codes. The correction of single-bit errors is always guaranteed. Ways to increase the number of double-bit and triple-bit errors that can be detected by shortened SEC and SEC-DED codes are considered in order to augment the error correction capability of the proposed solutions.     

冗余余数系统低复杂度快速纠错算法设计

余数系统由于具有增强传输信息在并行系统中鲁棒性的优势,已被广泛应用在无线局域网(WLAN)以及码分多址通信技术(CDMA)等领域。而余数系统中的纠错检错是保证传输数据可靠性和高效性的关键问题。该文根据有限环上剩余类的性质提出溢出判定定理,不重复判断定理和唯一性区间搜索定理,并在此基础上进一步提出采用模运算代替传统中国剩余定理进行快速恢复的单错误纠错算法,将复杂度降低为O(k,r);提出不重复判定纠错算法;并对于一般错误情形,设计通过比较算子实现的搜索纠错算法。其中搜索纠错算法能直接实现系统最大纠错能力,且避免依靠复杂模运算算子实现,系统吞吐率得以提高;与传统算法相比,计算复杂度由多项式级降低至对数级。     

Muting algorithms based on the use of side information generated byerror control systems

Muting algorithms for mobile radio are developed through the use of side information generated by error control systems. The simplest of these algorithms uses the error detection capabilities of block codes to determine whether a received digital data packet contains bit errors. Erroneous packets are muted by converting them to an appropriate erasure value. The more complex algorithms combine error correction and detection to minimize the muting rate while maintaining a high level of data quality. Implementations of these algorithms using Hamming and Reed-Solomon codes are investigated     

New Error Control Algorithms for Residue Number System Codes

We propose and describe new error control algorithms for redundant residue number systems (RRNSs) and residue number system product codes. These algorithms employ search techniques for obtaining error values from within a set of values (that contains all possible error values). For a given RRNS, the error control algorithms have a computational complexity of t·O(log₂ n + log₂ m?) comparison operations, where t denotes the error correcting capability, n denotes the number of moduli, and m? denotes the geometric average of moduli. These algorithms avoid most modular operations. We describe a refinement to the proposed algorithms that further avoids the modular operation required in their respective first steps, with an increase of ?log₂ n? to their computational complexity. The new algorithms provide significant computational advantages over existing methods.     

The effect of alpha-particle-induced soft errors on memory systems with error correction

Using Poisson statistics, a model for the survival probability of integrated memory circuits having both hard and soft error bit failure mechanisms is developed. Calculations are made over a range of soft error generation rates and erasure intervals for both single and double error correction. It is shown that even if the soft errors are erased effectively instantaneously, there is still an impact on the probability of system survival which is a function of soft error generation rate, and that in the case of instantaneous erasure of soft errors, a system with N bit error correction will have a probability of survival at least as good as the same system with N-1 bit error correction, no matter how high the soft error generation rate.     

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.     

Performance analysis of coded M-ary orthogonal signaling usingerrors-and-erasures decoding over frequency-selective fading channels

The performance of M-ary orthogonal signaling schemes employing Reed-Solomon (RS) codes and redundant residue number system (RRNS) codes is investigated over frequency-selective Rayleigh fading channels. “Errors-and-erasures” decoding is considered, where erasures are judged based on two low-complexity, low-delay erasure insertion schemes-Viterbi's ratio threshold test (RTT) and the proposed output threshold test (OTT). The probability density functions (PDF) of the ratio associated with the RTT and that of the demodulation output in the OTT conditioned on both the correct detection and erroneous detection of M-ary signals are derived, and the characteristics of the RTT and OTT are investigated. Furthermore, expressions are derived for computing the codeword decoding error probability of RS codes or RRNS codes based on the above PDFs, The OTT technique is compared to Viterbi's RTT, and both of these are compared to receivers using “error-correction only” decoding over frequency-selective Rayleigh-fading channels. The numerical results show that by using “errors-and-erasures” decoding, RS or RRNS codes of a given code rate can achieve higher coding gain than that without erasure information, and that the OTT technique outperforms the RTT, provided that both schemes are operated at the optimum decision thresholds     

Decoding algorithms with input quantization and maximum errorcorrection capability

Decoding that uses soft-decision information but with multiple low-complexity decoders are investigated. These decoders correct only errors and erasures. The structure of the receiver consists of a bank of z demodulators followed by errors- and erasures-correcting decoders operating in parallel. Each demodulator has a threshold for determining when to erase a given symbol. We assign a cost f(&thetas;) to the noise for causing an erasure when the receiver uses a particular threshold &thetas; and a (larger) cost f(&thetas;¯) for causing an error. The goal in designing the receiver is to choose the thresholds to maximize the noise cost which is necessary to cause a decoding error. We demonstrate that the above formulation is solvable for many channels including the M-ary input-output channel, the additive channel with coherent demodulation, and an additive channel with orthogonal modulation and noncoherent demodulation. Then we show that the maximum worst case error-correcting capability of the parallel decoding algorithms is the same as the maximum worst case error-correcting capability of a correlation decoder with the same number of quantization regions     

范德蒙阵列纠删码在嵌入式系统中的应用

针对范德蒙阵列纠删码算法,介绍了纠删码编译码过程,重点论述了范德蒙码编码算法和译码算法,提出了适合在嵌入式系统实现时的快速算法;在Matlab软件中构建了数字卫星广播系统(DVB-S)模型并进行了信道误码分布仿真,获得了DVB-S系统的误码分布,分析了在系统中使用范德蒙纠删码的可行性;提出了纠删码与系统中的纠错码级联使用模型,并对算法的纠错性能进行仿真,仿真结果表明级联模型能大大提高无线传输系统的可靠性。     

Performance of simple cross-interleaved Reed-Solomon decoding strategies for compact disc players

The complexity and performance of three simple error detection and correction strategies frequently used for the decoding of the cross-interleaved Reed-Solomon codes in digital compact disc ( CD) are compared. It is assumed that the number of byte errors in the input codeword is always a multiple of l a positive integer. By varying l from 1 to 32, the random to burst error performance of the various strategies is obtained. Specifically, it is shown that unless random errors are the main cause of concern, the best strategies seem to be those using erasure corrections. The results presented will be useful for deciding the decoding strategies to be adopted for CD players as well as in potential applications such as optical mass storage devices using the CD format     

Comparison of decoding algorithms of binary linear block codes inRayleigh fading channels with diversity reception

The word error probability of binary linear block codes is evaluated in Rayleigh fading channels with diversity reception for three decoding algorithms: error correction (EC), error/erasure correction (EEC), and maximum likelihood (ML) soft decoding algorithms. The performance advantage of EEC over EC in the required average SNR decreases as the number of diversity channels increases. The performance advantage of EEC over EC does not depend on the specific value of word error probability although the advantage of ML soft decoding over EC increases for lower word error probability     

LT码的性能分析及参数优化规则

As a new class of forward error correcting encoding algorithm, Luby Transform codes are suitable for the erasure channel environment based on the packet communication. The encoding, decoding algorithms and the implementation of LT codes are summarized in the paper. Meanwhile simulations of the ideal soliton distribution and robust soliton distribution are conducted to evaluate the performance of LT codes in terms of successful decoding probability, mean degree and decoding time over the erasure channel. The parameter optimization rules of LT codes are deeply discussed and proposed in the paper. The research results are of great practical importance for improving the real time performance in the erasure correction applications.     

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

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

Erasures and noise in splitting multiple access algorithms

A system with many nodes accessing a common receiver is considered. The forward channel is a time-slotted collision-type common radio channel. Due to a nonreliable forward channel, the receiver may misinterpret the actual event of a slot. For instance, an idle or a success slot can be interpreted as a conflict and a conflict or a success slot can be interpreted as an idle slot. The former kind of error is called a noise error, while the latter is called an erasure. Splitting multiple-access algorithms are introduced that can handle erasures as well as noise errors. A remarkable feature of the algorithms is that they ensure that, under stable operation, all packets are eventually successfully transmitted, including the erased packets (those packets that were involved in an erasure). The property that is exploited in devising these algorithms is that nodes whose packets were erased can detect that situation as they transmit and acknowledge that the slot was idle. Consequently, they can either retransmit immediately or wait until some agreed point in time (such as the end of a collision resolution interval) and then transmit. The performances of the proposed algorithms are evaluated according to the maximal throughput they can support for Poisson arrival process. The performance degradation due to erasures and noise errors is quantified.     

单容错网络存储编码并行算法研究

在海量存储系统中,利用冗余数据编码技术是提高存储系统可靠性的较好方法。文中对网络存储编码的相关算法进行了研究,针对单容错网络磁盘阵列的编码操作,重点研究了RAID5编码的并行算法。针对集中式奇偶校验编码算法在运行时间上的缺陷,提出了将编码计算过程与组通信操作相融合的思想,设计了更为高效的基于多对一归约操作的并行编码算法。实验结果表明,基于组通信的算法相对于集中式算法性能优势明显。     

Research of Methods for Lost Data Reconstruction in Erasure Codes over Binary Fields

In the process of encoding and decoding, erasure codes over binary fields, which just need AND operations and XOR operations and therefore have a high computational efficiency, are widely used in various fields of information technology. A matrix decoding method is proposed in this paper. The method is a universal data reconstruction scheme for erasure codes over binary fields. Besides a pre-judgment that whether errors can be recovered, the method can rebuild sectors of loss data on a fault-tolerant storage system constructed by erasure codes for disk errors. Data reconstruction process of the new method has simple and clear steps, so it is beneficial for implementation of computer codes. And more, it can be applied to other non-binary fields easily, so it is expected that the method has an extensive application in the future.     

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.