article

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

Authors:

Mark Karpovsky,

Konrad J. KulikowskiAuthors Info & Claims

Journal of Electronic Testing: Theory and Applications, Volume 26, Issue 5

Pages 559 - 580

https://doi.org/10.1007/s10836-010-5168-5

Published: 01 October 2010 Publication History

Abstract

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.

References

[1]

Berger JM (1961) A note on an error detection code for asymmetric channels. Inf Control 4:68-73.

[2]

Bhattacharryya D, Nandi S (1997) An efficient class of SEC-DED-AUED codes. In: Thirdinternational symposium on parallel architectures, algorithms, and networks.

[3]

Bose B (1984) Unidirectional error correction/detection for VLSI memory. In: Proceedings of the 11th annual international symposium on computer architecture.

[4]

Carlet C, Ding C (2004) Highly nonlinear mappings. J Complex 20(2-3):205-244.

Digital Library

[5]

Chen CL (1983) Error-correcting codes with byte error-detection capability. IEEE Trans Comput C-32:615-621.

[6]

Chen CL (1996) Symbol error correcting codes for memory applications. In: Proceedings of the twenty-sixth annual international symposium on fault-tolerant computing (FTCS'96).

[7]

Dunning LA (1985) SEC-BED-DED codes for error control in byte-organized memory systems. IEEE Trans Comput 34:557-562.

Digital Library

[8]

Dutta A, Touba NA (2007) Multiple bit upset tolerant memory using a selective cycle avoidance based SEC-DED-DAEC code. In: 25th IEEE VLSI test symposium (VTS'07).

[9]

Eto A, Hidaka M, Okuyama Y, Kimura K, Hosono M (1998) Impact of neutron flux on soft errors in mos memories. In: Electron devices meeting.

[10]

Etzion T, Vardy A (1994) Perfect binary codes: constructions, properties, and enumeration. IEEE Trans Inf Theory 40: 754-763.

Digital Library

[11]

Gaubatz G, Sunar B, Karpovsky MG (2006) Non-linear residue codes for robust public-key arithmetic. In: Workshop on fault diagnosis and tolerance in cryptography (FDTC'06).

[12]

Georgakos G, Huber P, Ostermayr M, Amirante E, Ruckerbauer F (2007) Investigation of increased multi-bit failure rate due to neutron induced seu in advanced embedded srams. In: Symposium on VLSI circuits digest of technical paper.

[13]

Halfhil TR (2005) Z-ram shrinks embedded memory. Micro-processor Report, Tech. Rep.

[14]

Hamming RW (1950) Error correcting and error detecting codes. Bell Syst Tech J.

[15]

Hsiao MY (1970) A class of optimal minimum odd-weight-column SEC-DED codes. IBM J Res Develop 14:395-401.

Digital Library

[16]

Johnston AH (2000) Scaling and technology issues for soft error rates. In: Ser. 4th annual research conference on reliability.

[17]

Karpovsky MG, Taubin A (2004) A new class of nonlinear systematic error detecting codes. IEEE Trans Inf Theory 50(8):1818-1820.

Digital Library

[18]

Karpovsky M, Kulikowski K, Taubin A (2004) Differential fault analysis attack resistant architectures for the advanced encryption standard. In: Ser. proc. IFIP world computing congress, Cardis, pp 177-193.

[19]

Karpovsky M, Kulikowski K, Taubin A (2004) Robust protection against fault-injection attacks on smart cards implementing the advanced encryption standard. In: Ser. proc. int. conference on dependable systems and networks (DNS 2004).

[20]

Karpovsky MG, Kulikowski K, Wang Z (2007) Robust error detection in communication and computation channels. In: Int. workshop on spectral techniques.

[21]

Karpovsky MG, Stankovic RS, Astola JT (2008) Spectral logic and its applications for the design of digital devices. Wiley.

[22]

Kulikowski K, Wang Z, Karpovsky MG (2008) Comparative analysis of fault attack resistant architectures for private and public key cryptosystems. In: Proc of int. workshop on fault-tolerant cryptographic devices.

[23]

Lala P (1978) An adaptive double error correction scheme for semiconductor memory systems. Digit Process 4:237-243.

[24]

Lala PK (2003) A single error correcting and double error detecting coding scheme for computer memory systems. In: Proceedings of the 18th IEEE international symposium on defect and fault tolerance in VLSI systems.

[25]

Lisbôa, CA, Erigson MI, Carro L (2007) System level approaches for mitigation of long duration transient in future technologies. In: 12th IEEE European test symposium (ETS'07).

[26]

MacWilliams F, Sloane N (1983) The theory of error-correcting codes. North Holland.

[27]

Maiz J, Hareland S, Zhang K, Armstrong P (2003) Characterization of multi-bit soft error events in advanced srams. In: IEEE int'l electronic device meeting, pp 519-522.

[28]

Maxwell MS (2005) Almost perfect nonlinear functions and related combinatorial structures. PhD dissertation, ISU.

[29]

Mollard M (1986) A generalized parity function and its use in the construction of perfect codes. SIAM J Algebr Discrete Methods 7:113-115.

Digital Library

[30]

Moore SK (2007) Masters of memory. IEEE Spectrum 44(1):45-49.

Digital Library

[31]

Penzo L, Sciuto D, Silvano C (1995) Construction techniques for systematic SEC-DED codes with single byte error detection and partial correction capability for computer memory systems. IEEE Trans Inf Theory 41(2):584-591.

Digital Library

[32]

Phelps KT (1983) A combinatorial construction of perfect codes. SIAM J Algebr Discrete Methods 4:398-403.

[33]

Phelps KT, Levan M (1995) Kernels of nonlinear hamming codes. Designs Codes Cryptogr 6(3):247-257.

Digital Library

[34]

Rao TRN, Fujiwara E (1989) Error-control coding for computer systems. Prentice-Hall, Upper Saddle River, NJ.

[35]

Reddy S (1978) A class of linear codes for error control in byte-per-card organized digital systems. IEEE Trans Comput C-27:455-459.

[36]

Satoh S, Tosaka Y, Wender SA (2000) Geometric effect of multiple-bit soft errors induced by cosmic ray neutrons on drams.

[37]

Swift M, Guertin, SM (2000) In-flight observations of multiple-bit upset in DRAMs. IEEE Trans Nucl Sci 47(6): 2386-2391.

[38]

Tam S (2006) Application note: single error correction and double error detection. XILINX.

[39]

Vasil'ev JL (1962) On nongroup close-packed codes. Probl Kibern 8:375-378.

[40]

Wang Z, Karpovsky M, Kulikowski K (2009) Replacing linear hamming codes by robust nonlinear codes results in a reliability improvement of memories. In: IEEE/IFIP international conference on dependable systems and networks, 2009. DSN '09, 29 June-2 July 2009, pp 514-523

[41]

Wang Z, Karpovsky M, Joshi A (2010) Reliable MLC NAND flash memories based on nonlinear t-error-correcting codes. In: IEEE/IFIP international conference on dependable systems and networks, 2010. DSN '10.

[42]

Whitaker S, Cameron K, Maki G, Canaris J, Owsley P (1991) VLSI reed-solomon processor for the hubble space telescope. In: VLSI signal processing IV. IEEE Press.

Cited By

Overill RVolkamer MWressnegger C(2020)Cosmic raysProceedings of the 15th International Conference on Availability, Reliability and Security10.1145/3407023.3409188(1-6)Online publication date: 25-Aug-2020
https://dl.acm.org/doi/10.1145/3407023.3409188
Rabii HKeren O(2019)A new class of security oriented error correcting robust codesCryptography and Communications10.1007/s12095-018-0340-311:5(965-978)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1007/s12095-018-0340-3
Kovalevskaya D(2018)Mollard Code as a Robust Nonlinear CodeProblems of Information Transmission10.1134/S003294601801003954:1(34-47)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1134/S0032946018010039
Show More Cited By

Design of Memories with Concurrent Error Detection and Correction by Nonlinear SEC-DED Codes
1. Mathematics of computing

Recommendations

Nonlinear multi-error correction codes for reliable MLC NAND flash memories

Multi-level cell (MLC) NAND flash memories are popular storage media because of their power efficiency and large storage density. Conventional reliable MLC NAND flash memories based on BCH codes or Reed-Solomon (RS) codes have a large number of ...
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 ...
New Linear SEC-DED Codes with Reduced Triple Bit Error Miscorrection Probability
IOLTS '08: Proceedings of the 2008 14th IEEE International On-Line Testing Symposium

This paper solves the problem of minimizing triple bit error miscorrection for single-error-correcting, double-error-detecting codes (SEC-DED codes) which are used to protect all kinds of memory against errors. A lower bound for triple bit error ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Electronic Testing: Theory and Applications

Journal of Electronic Testing: Theory and Applications Volume 26, Issue 5

October 2010

95 pages

ISSN:0923-8174

Issue’s Table of Contents

Copyright © Copyright © 2010 Springer Science+Business Media, LLC.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 October 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Overill RVolkamer MWressnegger C(2020)Cosmic raysProceedings of the 15th International Conference on Availability, Reliability and Security10.1145/3407023.3409188(1-6)Online publication date: 25-Aug-2020
https://dl.acm.org/doi/10.1145/3407023.3409188
Rabii HKeren O(2019)A new class of security oriented error correcting robust codesCryptography and Communications10.1007/s12095-018-0340-311:5(965-978)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1007/s12095-018-0340-3
Kovalevskaya D(2018)Mollard Code as a Robust Nonlinear CodeProblems of Information Transmission10.1134/S003294601801003954:1(34-47)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1134/S0032946018010039
Levina ATaranov S(2016)New construction of algebraic manipulation detection codes based on wavelet transformProceedings of the 18th Conference of Open Innovations Association FRUCT10.1109/FRUCT-ISPIT.2016.7561526(187-192)Online publication date: 25-Apr-2016
https://dl.acm.org/doi/10.1109/FRUCT-ISPIT.2016.7561526
Gemmeke TSabry MStuijt JRaghavan PCatthoor FAtienza DFettweis GNebel W(2014)Resolving the memory bottleneck for single supply near-threshold computingProceedings of the conference on Design, Automation & Test in Europe10.5555/2616606.2616854(1-6)Online publication date: 24-Mar-2014
https://dl.acm.org/doi/10.5555/2616606.2616854
Ge SWang ZLuo PKarpovsky MLee RShi W(2013)Secure memories resistant to both random errors and fault injection attacks using nonlinear error correction codesProceedings of the 2nd International Workshop on Hardware and Architectural Support for Security and Privacy10.1145/2487726.2487731(1-8)Online publication date: 23-Jun-2013
https://dl.acm.org/doi/10.1145/2487726.2487731
Wang ZKarpovsky MJoshi A(2012)Nonlinear multi-error correction codes for reliable MLC NAND flash memoriesIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2011.215718320:7(1221-1234)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1109/TVLSI.2011.2157183

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents