Memory Reliability Improvement Based on Maximized Error-Correcting Codes

Error-correcting codes (ECC) offer an efficient way to improve the reliability and yield of memory subsystems. ECC-based protection is usually provided on a memory word basis such that the number of data-bits in a codeword corresponds to the amount of information that can be transferred during a single memory access operation. Consequently, the codeword length is not the maximum allowed by a certain check-bit number since the number of data-bits is constrained by the width of the memory data interface. This work investigates the additional error correction opportunities offered by the absence of a perfect match between the numbers of data-bits and check-bits in some widespread ECCs. A method is proposed for the selection of multi-bit errors that can be additionally corrected with a minimal impact on ECC decoder latency. These methods were applied to single-bit error correction (SEC) codes and double-bit error correction (DEC) codes. Reliability improvements are evaluated for memories in which all errors affecting the same number of bits in a codeword are independent and identically distributed. It is shown that the application of the proposed methods to conventional DEC codes can improve the mean-time-to-failure (MTTF) of memories with up to 30 %. Maximized versions of the DEC codes are also proposed in which all adjacent triple-bit errors become correctable without affecting the maximum number of triple-bit errors that can be made correctable.     

Optimized parallel decoding of difference set codes for high speed memories

The interest in using advanced Error Correction Codes (ECCs) to protect memories and caches is growing. This is because as process technology downscales, errors are more frequent and also tend to affect multiple bits. For SRAM memories and caches, latency is a limiting factor and ECCs have to provide low decoding times that can in most cases be only achieved with the use of a parallel decoder. One important issue with parallel decoders is that they typically require large circuit area to be implemented. One type of ECCs that has been explored for memory protection is Difference Set (DS) codes. In this research note, an optimized parallel decoding scheme for DS codes is presented and evaluated. The results show that the circuit area and the decoding delay are reduced compared to a traditional implementation. In addition, the new scheme enables a reduction in the number of parity check bits thus reducing the memory size.     

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.     

Fault tolerant encoders for Single Error Correction and Double Adjacent Error Correction codes

Error correction codes (ECCs) are commonly used to deal with soft errors in memory applications. Typically, Single Error Correction-Double Error Detection (SEC-DED) codes are widely used due to their simplicity. However, the phenomenon of more than one error in the memory cells has become more serious in advanced technologies. Single Error Correction-Double Adjacent Error Correction (SEC-DAEC) codes are a good choice to protect memories against double adjacent errors that are a major multiple error pattern. An important consideration is that the ECC encoder and decoder circuits can also be affected by soft errors, which will corrupt the memory data. In this paper, a method to design fault tolerant encoders for SEC-DAEC codes is proposed. It is based on the fact that soft errors in the encoder have a similar effect to soft errors in a memory word and achieved by using logic sharing blocks for every two adjacent parity bits. In the proposed scheme, one soft error in the encoder can cause at most two errors on adjacent parity bits, thus the correctness of memory data can be ensured because those errors are correctable by the SEC-DAEC code. The proposed scheme has been implemented and the results show that it requires less circuit area and power than the encoders protected by the existing methods.     

Location-correcting codes

We study codes over GF(q) that can correct t channel errors assuming the error values are known. This is a counterpart to the well-known problem of erasure correction, where error values are found assuming the locations are known. The correction capabilities of these so-called t-location correcting codes (t-LCCs) are characterized by a new metric, the decomposability distance, which plays a role analogous to that of the Hamming metric in conventional error-correcting codes (ECCs). Based on the new metric, we present bounds on the parameters of t-LCCs that are counterparts to the classical Singleton, sphere packing and Gilbert-Varshamov bounds for ECCs. In particular, we show examples of perfect LCCs, and we study optimal (MDS-Like) LCCs that attain the Singleton-type bound on the redundancy. We show that these optimal codes are generally much shorter than their erasure (or conventional ECC) analogs. The length n of any t-LCC that attains the Singleton-type bound for t>1 is bounded from above by t+O(√(q)), compared to length q+1 which is attainable in the conventional ECC case. We show constructions of optimal t-LCCs for t∈{1, 2, n-2, n-1, n} that attain the asymptotic length upper bounds, and constructions for other values of t that are optimal, yet their lengths fall short of the upper bounds. The resulting asymptotic gap remains an open research problem. All the constructions presented can be efficiently decoded     

On-chip error correcting techniques for new-generation flash memories

In new-generation flash memories, issues such as disturbs and data retention become more and more critical as a consequence of reduced cell size and decreased oxide thickness. Furthermore, the progressive increase in the cell count within a single die tends to decrease device reliability. In particular, reliability issues turn out to be more critical in multilevel (ML) flash memories, due to the reduced spacing between adjacent programmed levels. It is therefore deemed that the use of on-chip error correction codes (ECCs) will gain widespread acceptance in large-capacity flash memories. ECCs for flash memories must have very fast and compact encoding/decoding circuitry so as to have a minimum impact on memory access time. The area penalty due to check cells must also be minimized. Moreover, specific codes must be developed for ML storage. This paper presents error control coding techniques and schemes for new-generation flash memories, focusing on ML devices. The basic concepts of error control coding are reviewed, and the on-chip ECC design procedure is analyzed. Dedicated codes such as polyvalent ECCs, able to correct data stored in ML memories working at a variable number of bits per cell, and bit-layer organized ECCs are described.     

Coding for system-on-chip networks: a unified framework

Global buses in deep-submicron (DSM) system-on-chip designs consume significant amounts of power, have large propagation delays, and are susceptible to errors due to DSM noise. Coding schemes exist that tackle these problems individually. In this paper, we present a coding framework derived from a communication-theoretic view of a DSM bus to jointly address power, delay, and reliability. In this framework, the data is first passed through a nonlinear source coder that reduces self and coupling transition activity and imposes a constraint on the peak coupling transitions on the bus. Next, a linear error control coder adds redundancy to enable error detection and correction. The framework is employed to efficiently combine existing codes and to derive novel codes that span a wide range of tradeoffs between bus delay, codec latency, power, area, and reliability. Using simulation results in 0.13-/spl mu/m CMOS technology, we show that coding is a better alternative to repeater insertion for delay reduction as it reduces power dissipation at the same time. For a 10-mm 4-bit bus, we show that a bus employing the proposed codes achieves up to 2.17/spl times/ speed-up and 33% energy savings over a bus employing Hamming code. For a 10-mm 32-bit bus, we show that 1.7/spl times/ speed-up and 27% reduction in energy are achievable over an uncoded bus by employing low-swing signaling without any loss in reliability.     

基于一种交织码的多位翻转容错技术研究

随着技术的发展和核心电压的降低,存储器更易受瞬时错误（软错误）影响,成为影响航天器件可靠性的主要原因。错误检测与纠正（EDAC）码（也称错误纠正码）常用来对SRAM型存储器中的瞬时错误进行纠正,由单个高能粒子引起的多位翻转错误（SEMU）是普通纠一检二（SEC-DED）编码所无法处理的。提出了一种交织度为2的(26,16)交织码,该码由两个能纠正一位随机错误、二位突发错误的(13,8)系统码组成,(26,16)交织码能够纠正单个码字中小于二位的随机错误和小于四位突发错误（DEC-QAEC）。通过理论分析和硬件平台实验表明,该交织码在存储资源占用率、实时性相当情况下可靠性优于同等长度的SEC DED码,能有效提高SRAM型存储器抗多位翻转错误的能力。      

Using Error Correcting Codes Without Speed Penalty in Embedded Memories: Algorithm, Implementation and Case Study

Drastic device shrinking, power supply reduction, increasing complexity and increasing operating speeds affect adversely the reliability of nowadays Integrate Circuits (ICs). In many modern designs, embedded memories occupy the largest part of the die and comprise the large majority of transistors. Furthermore, memories are designed as tight as allowed by the process, and are therefore more prone to failures than other circuits. Error correcting codes (ECCs) are an efficient mean for protecting memories against failures. A major drawback of ECCs is the speed penalty induced by the encoding and decoding circuits. In this paper, we present an architecture enabling implementing ECCs without speed penalty. Furthermore, as the manual implementation of this solution is impractical for complex System-on-Chips (SoCs), we propose an algorithm and a set of generic rules allowing automatic insertion of the delay-free ECCs in any complex architecture at Register Transfer Level (RTL). With respect to a naive insertion in the design of the new architecture, the algorithm enable up to 20 % hardware reduction. The Finite State Machines (FSM) that controls the new ECC architecture is also generated automatically. Experimental evaluations show that the hardware overhead of the speed penalty free ECCs protected memory compared to a standard implementation of ECC protected memory is about 2.5 % with an additional power consumption of 6 %.     

Low cost design of microprocessor EDAC circuit

An optimization method of error detection and correction (EDAC) circuit design is proposed. The method involves selecting or constructing EDAC codes of low cost hardware, associated with operation scheduling implementation based on 2-input XOR gates structure, and two actions for reducing hardware cells, which can reduce the delay penalties and area costs of the EDAC circuit effectively. The 32-bit EDAC circuit hardware implementation is selected to make a prototype, based on the 180 nm process. The delay penalties and area costs of the EDAC circuit are evaluated. Results show that the time penalty and area cost of the EDAC circuitries are affected with different parity-check matrices and different hardware implementation for the EDAC codes with the same capability of correction and detection code. This method can be used as a guide for low-cost radiation-hardened microprocessor EDAC circuit design and for more advanced technologies.     

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.     

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.     

DSD (double soft decision) concatenated FEC scheme in mobilesatellite communication systems

In order to realize a higher-code-gain forward error correction scheme in mobile satellite communication systems, a novel concatenated coding scheme employing soft decision decoding for not only inner codes but also outer codes (double soft decision, or DSD, concatenated forward error correction scheme) is proposed. Soft-decision outer decoding can improve the bit error probability of inner decoded data. In this scheme, likelihood information from an inner Viterbi decoder is used in the decoding of outer codes. A technique using the path memory circuit status 1.0 ratio for likelihood information is proposed, and is shown to be the most reliable even though it requires the simplest hardware among the alternative methods. A computer simulation clarifies that the DSD scheme improves Pe performance to one-third of that of the conventional hard-decision outer decoding. Moreover, to reduce the interleaving delay time in fading channels or inner decoded data of concatenated codes, a parallel forward error correction scheme is proposed     

Power Consumption of Fault Tolerant Busses

On-chip interconnects in very deep submicrometer technology are becoming more sensitive and prone to errors caused by power supply noise, crosstalk, delay variations and transient faults. Error-correcting codes (ECCs) can be employed in order to provide signal transmission with the necessary data integrity. In this paper, the impact of ECCs to encode the information on a very deep submicrometer bus on bus power consumption is analyzed. To fulfill this purpose, both the bus wires (with mutual capacitances, drivers, repeaters and receivers) and the encoding-decoding circuitry are accounted for. After a detailed analysis of power dissipation in deep submicrometer fault-tolerant busses using Hamming single ECCs, it is shown that no power saving is possible by choosing among different Hamming codes. A novel scheme, called dual rail, is then proposed. It is shown that dual rail, combined with a proper bus layout, can provide a reduction of energy consumption. In particular, it is shown how the passive elements of the bus (bottom and mutual wire capacitances), active elements of the bus (buffers) and error-correcting circuits contribute to power consumption, and how different tradeoffs can be achieved. The analysis presented in this paper has been performed considering a realistic bus structure, implemented in a standard 0.13-mum CMOS technology.     

一种简化的LDPC码BP译码算法的研究

低密度奇偶校验码(LDPC码)是一种逼近香农限的线性分组码,译码的复杂度较低;在LDPC码译码算法中性能较好的是置信传播译码(BP)算法,他能够在迭代译码过程中确定码字是否已译出,但是复杂度高,运算量大。采用一种改进的BP译码算法,在迭代译码过程中对校验节点的更新信息进行曲线拟合,以减小译码运算量,有利于硬件的并行实现,减少译码延时。仿真结果表明,改进的BP算法译码性能和原来的BP算法接近,而且复杂度较低。     

极化码的多比特译码算法研究

针对极化码的连续消除列表（successive cancellation list,SCL）译码算法的高时延问题,提出了基于对数似然比的多比特SCL（multi-bit SCL,MSCL）译码算法,可以在一个判决时刻同时译出多个码字比特,在不损失译码性能的前提下,将译码时延由3N-2个时钟降为4N/M-2个时钟,相比于现有的多比特SCL译码算法,MSCL译码算法具有更低的路径度量值计算复杂度。为了降低循环冗余校验（cyclical redundancy check, CRC）辅助的SCL（CRC aided SCL,CA-SCL）译码算法的译码时延以及存储空间,提出了分段CRC辅助的MSCL（segmented CRC-aided MSCL,SCA-MSCL）译码算法,并提出了分段信息码字长度修正算法,来保证在信息位索引集A不变的前提下,实现每一分段结尾处对应的信息位索引能够被M整除。SCA-MSCL算法可以借助多个CRC判决来尽可能早地输出译码码字,从而减少译码器的存储空间以及译码时延。     

一种基于之型分量码的系统GLDPC码

本文以规则低密度生成矩阵码为基础,构建了一种以之型码为分量码的系统广义低密度奇偶校验(Generalized Low-Density Parity-Check,GLDPC)码,称为ZS-GLDPC码.该码具有线性编码复杂度,可采用和积译码算法实现迭代译码,其译码复杂度低于以汉明码为分量码的GLDPC码.在均匀交织器的前...     

New Mix codes for multiple bit upsets mitigation in fault-secure memories

Nowadays, multibit error correction codes (MECCs) are effective approaches to mitigate multiple bit upsets (MBUs) in memories. As technology scales, combinational circuits have become more susceptible to radiation induced single event transient (SET). Therefore, transient faults in encoding and decoding circuits are more frequent than before. Firstly, this paper proposes a new MECC, which is called Mix code, to mitigate MBUs in fault-secure memories. Considering the structure characteristic of MECC, Euclidean Geometry Low Density Parity Check (EG-LDPC) codes and Hamming codes are combined in the proposed Mix codes to protect memories against MBUs with low redundancy overheads. Then, the fault-secure scheme is presented, which can tolerate transient faults in both the storage cell and the encoding and decoding circuits. The proposed fault-secure scheme has remarkably lower redundancy overheads than the existing fault-secure schemes. Furthermore, the proposed scheme is suitable for ordinary accessed data width (e.g., 2ⁿ bits) between system bus and memory. Finally, the proposed scheme has been implemented in Verilog and validated through a wide set of simulations. The experiment results reveal that the proposed scheme can effectively mitigate multiple errors in whole memory systems. They can not only reduce the redundancy overheads of the storage array but also improve the performance of MECC circuits in fault-secure memory systems.     

Design and performance of turbo Gallager codes

The most powerful channel-coding schemes, namely, those based on turbo codes and low-density parity-check (LDPC) Gallager codes, have in common the principle of iterative decoding. However, the relative coding structures and decoding algorithms are substantially different. This paper shows that recently proposed novel coding structures bridge the gap between these two schemes. In fact, with properly chosen component convolutional codes, a turbo code can be successfully decoded by means of the decoding algorithm used for LDPC codes, i.e., the belief-propagation algorithm working on the code Tanner graph. These new turbo codes are here nicknamed "turbo Gallager codes." Besides being interesting from a conceptual viewpoint, these schemes are important on the practical side because they can be decoded in a fully parallel manner. In addition to the encoding complexity advantage of turbo codes, the low decoding complexity allows the design of very efficient channel-coding schemes.