Solid-state drive (SSD) has advantages over hard-disk drive (HDD) in terms of power consumption, random access time, and resilience to shock and vibration. Large capacity SSD usually requires high-density multi-level cell flash memory fabricated with deep-submicron process. High-density memory chips, however, are vulnerable to soft errors caused by, for example, fluctuations of gate voltage and charge level in the floating gate. This paper proposes a hierarchical three-level error control coding suitable for the dependable SSD. The proposed coding is capable of correcting multiple random bit errors, as well as of recovering from single chip failures. Evaluation shows that the proposed coding scheme provides strong error correction capability. For example, bit error rate (BER) of the SSD is reduced from 1.08 × 10-4to 2.44 × 10-19by using the proposed coding, that is, using two BCH codes with different error correction capabilities for the first and the second levels, and the simple parity-check code for the third level. Extra one spare memory chip in the SSD improves mean time to data loss (MTTDL) from 13 years to 34 years.

M-Spotty byte error control codes are very effective for correcting/detecting errors in semiconductor memory systems using recent high-density RAM chips with wide I/O data, e.g., 8, 16, or 32 bits. In this case, width of the I/O data is called a byte. A spotty byte error is defined as random i-bit errors within a byte of length 6-bit, where t les b. Especially, M-spotty byte error is defined as multiple spotty byte errors in a byte. M-spotty byte error control code is characterized by m-spotty distance which includes Hamming distance as a special case for t = 1 or t = b. The MacWilliams identity provides the relation of weight distribution of a code and that of its dual code. This paper presents the MacWilliams identity for m-spotty weight enumerator of the m-spotty byte error control codes. Also, this clarifies that the indicated identity includes the MacWilliams identity for Hamming weight enumerator as a special case.

Spotty byte error control codes are very effective for correcting/ detecting errors in semiconductor memory systems using recent high-density RAM chips with wide I/O data, e.g., 8, 16, or 32 bits I/O data. A spotty byte error is defined as random t-bit errors within a byte of length b-bit, where t les b, and also m-spotty byte errors as multiple spotty byte errors in a byte. In semiconductor memory systems, in general, errors are occurred in a limited number of RAM chips, that is, occurred in a limited number of bytes. Considering this situation, this paper presents a new class of m-spotty byte error control codes where errors are confined to a limited number of bytes. The proposed codes require much smaller check-bit length than the conventional m-spotty byte error control codes and the RS codes. And also, this paper clarifies a decoding algorithm of the proposed codes

Spotty byte error control codes are very effective for correcting/detecting errors in semiconductor memory systems using recent high-density RAM chips with wide I/O data, e.g. 8, 16, or 32 bits. A spotty byte error is defined as t-bit errors within a byte of length b-bit, where 1 /spl les/ t /spl les/ b, and denoted as t/b-error. This paper proposes a new error model of two spotty byte errors occurred simultaneously, i.e., t/b-error and t'/b-error, where t /spl ne/ t', called complex spotty byte errors. This paper presents two complex m-spotty byte error control codes, i.e., (S/sub t/b/EC-(S/sub t/b/+S/sub t'/b/)ED) codes which correct all single t/b-errors and detect both t/b-errors and t'/b-errors simultaneously, and ((S/sub t/b/+S/sub t'/b/)EC) codes which correct both single t/b-errors and single t'/b-errors simultaneously. This paper also presents practical examples of the codes with parameter t' = 1, that is, S/sub t/b/EC-(S/sub t/b/+S)ED codes and (S/sub t/b/+S) EC codes which require smaller check-bit length than the existing S/sub t/b/EC-D/sub t/b/ED codes and the D/sub t/b/EC codes, respectively.

Burst error correcting codes, such as fire codes, have traditionally been decoded using linear feedback shift registers (LFSR). However, such sequential decoding schemes are not suitable for modern ultra high-speed channels that demand high-speed parallel decoding employing only combinational logic circuitry. This work proposes a parallel decoding method for cyclic burst error correcting codes. Under this method, a binary companion matrix T defines the entire decoding process. Hence, the decoding method can be implemented using only combinational logic.

Nonbinary M-ary words processed by data entry systems often suffer from asymmetric errors. In character recognition systems, for example, two symbols a/sub i/ and a/sub j/ with similar shapes have a high probability of being mistaken for one another. Among the many types of data processed by data entry systems, M-ary words selected from a specified codebook, such as postal codes and product numbers, should be strongly protected from asymmetric errors because these words are often used for indexing a database. We propose a new class of nonsystematic M-ary asymmetric error correcting codes which can be utilized to generate these codebooks. In order to effectively correct asymmetric errors, the new class of codes is designed based on a multilevel coding method and a set partitioning algorithm. Evaluation shows that the proposed codes have a low decoded symbol error rate.

Nonbinary M-ary symbols such as alphanumeric characters are commonly used in data entry devices, e.g., keyboards and character recognition devices. The M-ary symbols processed by these devices are sometimes mistaken for other symbols due to errors such as mistyping in keyboards or misreading in character recognition systems. These errors are generally asymmetric, not symmetric. For example, the symbols corresponding to adjacent keys in a keyboard have a high error probability due to mistapping. Similarly, in character recognition systems, two symbols having similar shape have high error probability to be misrecognized. These asymmetric errors can be corrected or detected by using M-ary asymmetric symbol error control codes. We propose a new class of M-ary single asymmetric symbol error correcting codes by using a new class of rings obtained from a direct product of Galois fields. Asymmetric symbol errors are expressed by an error directionality graph, based on which the error correction capability of the codes is determined. The code is defined by a parity check matrix over the ring and functions which map a set of M-ary symbols into the ring. One of the functions is derived from the graph coloring problem of the error directionality graph. The proposed codes have greater information symbol length than the existing M-ary single symmetric symbol error correcting codes.

Correcting multiple random bit errors that corrupt a single DRAM chip becomes very important in certain applications, such as semiconductor memories used in computer and communication systems, mobile systems, aircraft, and satellites. This is because, in these applications, the presence of strong electromagnetic waves in the environment or the bombardment of an energetic particle on a DRAM chip is highly likely to upset more than just one bit stored in that chip. On the other hand, entire chip failures are often presumed to be less likely events and, in most applications, detection of errors caused by single chip failures are preferred to correction due to check bit length considerations. Under this situation, codes capable of correcting random multiple bit errors that are confined to a single chip output and simultaneously detecting errors caused by single chip failures are attractive for application in high speed memory systems. This paper proposes a class of codes called Single t/b-error Correcting-Single b-bit byte Error Detecting (S/sub t/b/EC-S/sub b/ED) codes which have the capability of correcting random t-bit errors occurring within a single b-bit byte and simultaneously indicating single b-bit byte errors. For the practical case where the chip data output is 8 bits, i.e., b = 8, the S/sub 3/8/EC-S/sub 8/ED code proposed in this paper, for example, requires only 12 check bits at information length 64 bits. Furthermore, this S/sub 3/8/EC-S/sub 8/ED code is capable of correcting errors caused by single subarray data faults, i.e., single 4-bit byte errors, as well. This paper also shows that perfect S/sub (b-t)/b/EC-S/sub b/ED codes, i.e., perfect S/sub t/b/EC-S/sub b/ED codes for the case where t = b - 1, do exist and provides a theorem to construct these codes.

Recent high density wide I/O DRAM chips are highly vulnerable to multiple random bit errors. Therefore, correcting multiple random bit errors that corrupt a single DRAM chip becomes very important in certain applications, such as semiconductor memories used in computer and communication systems, mobile systems, aircraft and satellites. This is because, in these applications, the presence of strong electromagnetic waves in the environment or the bombardment of an energetic particle on a DRAM chip is likely to upset more than just one bit stored in that chip. Under this situation, codes capable of correcting random multiple bit errors that are confined to a single DRAM chip output are suitable for application in high speed semiconductor memory systems. This paper proposes a class of codes called single t/b-error correcting (S/sub t/b/EC) codes which are capable of correcting random t-bit errors occurring within a single b-bit byte. For the case where the chip data output is 16 bits, i.e., b = 16, the S/sub 3/16/EC code proposed in this paper requires only 16 check bits, that is, only one chip is required for check bits at practical information lengths such as 64, 128 and 256 bits. Furthermore, this S/sub 3/16/EC code is capable of detecting more than 95% of all single 16 bit byte errors at information length 64 bits.

This paper proposes a class of systematic codes called single t/B-error correcting - single b-bit byte error correcting - single b-bit block error detecting (S/sub t/B/EC-S/sub b/EC-S/sub B/ED) codes for high speed semiconductor memory systems. The proposed codes correct multiple random t-bit errors occurring within a chip and b-bit byte errors caused by sub-array data faults while simultaneously indicating B-bit block errors caused by complete chip failures.

Error control codes are now successfully applied to computer systems and communication systems. When we consider some types of computer words or communication messages, the information in some part of the word is more important than the other. Address and control information in computer words and communication messages and pointer information in database words are good examples. The more important the part of the word is, or the less reliable the part is, the more strongly it should be protected from errors. Based on this, this paper proposes a new class of codes, called unequal error control codes, which have some unequal error control levels in the codeword, that is, have some distinct code functions in the codeword and protect the part of the word from errors according to its importance or reliability level. From a simple and practical viewpoint, this paper adopts the model of the codeword which includes two unequal levels: one having strong error control level in some part of the codeword, called fixed-byte, and the other having relatively weak error control level outside the fixed-byte. This paper deals with three basic unequal error control codes. For all types of codes, the paper clarifies necessary and sufficient conditions and bounds on code length and demonstrates code construction method of the optimal codes and evaluation of these codes from the perspectives of error correction/detection capability and decoder hardware complexity.

A new class of error control codes, single byte error correcting and single byte plus single bit error detecting codes, are presented. The codes are suitable for semiconductor memory systems organized in a b-bit-per-chip manner, b/spl ges/2, and more efficient than previously known codes with as strong error control capabilities.

We propose a probabilistic measure for self-checking (SC) circuits that is analogous to reliability of fault-tolerant systems. This measure is defined as the probability to achieve totally self-checking (TSC) goal at the lth cycle: TSCG(t). TSCG provides insight to the worst case dynamic behavior of SC circuits with respect to the application environment and component failure rates. TSCG surpasses the TSC definitions in determining the applicability of a circuit in a given application environment. An SC circuit achieves TSC goal when no erroneous information or data is propagated beyond the boundary of this circuit. TSCG is therefore the probability that this fault confinement mechanism is intact. The SC properties are obtained through adding hardware redundancy to the original digital design, which means that an SC circuit has a higher failure rate than the original circuit. Further, there are tradeoffs between the level of hardware redundancy, the reliability, and the TSCG. We give several examples to clearly demonstrate these tradeoffs for different design environments. We emphasize that the TSCG is intended to provide a mean of dynamic error handling performance evaluation of SC designs. The TSC definitions and alike are still intact, since a cost-effective SC circuit must begin with a TSC circuit. The TSCG gives confidence in the use of cost-efficient error control codes and/or reduction in error handling capability. Analogous to reliability, the TSCG can be used in product specifications. This is a crucial step toward the practical applications of TSC or CED circuits.

Error-locating codes (EL codes), first proposed by J.K. Wolf and B. Elspas in 1963, have the potential to be used to identify the faulty module for fault isolation and reconfiguration in fault-tolerant computer systems. This paper proposes a new class of EL codes suitable for memory systems organized with b-bit (b/spl ges/2) byte-organized semiconductor memory chips that are mounted on memory cards each having B-bit width. The proposed linear code, called the S/sub b/B/EL code, identifies erroneous memory card locations containing a faulty byte-organized chip. Another linear code proposed in this paper, the SEC-S/sub b/B/EL code, corrects single-bit errors induced by alpha particles and, for byte errors, it locates erroneous card positions containing a faulty chip. This paper describes design methods of the proposed codes and shows an evaluation of the decoding hardware and the error detection capabilities.>

This paper presents a new design for a ←self-checking checker for nonencoded multiinput combinational circuits. A built-in testing method is also stressed. The proposed checker, called a generalized prediction checker (GPC), has an extended and generalized form of conventional parity prediction checkers, and includes a duplication checker as a special case. A parity check matrix H imparts arbitrary error detection ability to the new GPC. The GPC is made perfectly self-testing by applying a new method that adds one extra input to the cascaded multiinput comparator and to the cascaded XOR tree circuit in the GPC. This extra input may take any value during normal operation. The ←self-checking GPC is implemented for specific circuit examples and verified. For these examples, the ←self-checking GPC's show 100 percent fault coverage for single stuck faults in both the circuit under check and the checker itself. Using this checker, the built-in testing method taking advantage of the checker's automatic fault detection ability is shown to be suitable for testing combinational circuits.

This correspondence demonstrates a new kind of error-checking scheme for multioutput combinational circuits and its use for a built-in testing method. In the error-checking logic employed, the output from the circuits being checked is partitioned into several groups. The predicted group parity is compared to that produced from the output in each group. This checking circuit, called a group-parity prediction (GPP) checker, can be implemented systematically. To ensure that the GPP checker is self-testing, several conditions are required. The self-testing GPP checkers are implemented for some concrete examples of multioutput combinational circuits. With respect to these examples, the self-testing GPP checker shows 87-100 percent error detection ability, and 91-100 percent fault coverage for single stuck faults. Using this self-testing GPP checker, a self-verification testing method, which takes advantage of the automatic fault-detection capability of a checker, is shown to be applicable to testing combinational circuits.

In a memory that uses byte-organized memory chips, each containing b (≥2) output bits, a single chip failure is likely to affect many bits within a byte. Single byte error correcting–double byte error detecting codes (SbEC–DbED codes) are used in this kind of memory system to increase reliability.