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 ≤ t ≤ b, and denoted as t/b-error. This paper proposes a new error model of two spotty byte errors occurring simultaneously, i.e., t/b-error and t′/b-error, where t t′, called complex spotty byte errors. This paper presents two complex m-spotty byte error control codes, i.e., St/bEC-(St/b+St′/b)ED codes which correct all single t/b-errors and detect both t/b-errors and t′/b-errors simultaneously, and (St/b+St′/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, St/bEC-(St/b+S)ED codes and (St/b+S) EC codes which require smaller check-bit length than the existing Single t/b-error Correcting and Double t/b-error Detecting (St/bEC-Dt/bED) codes and the Double t/b-error Correcting (Dt/bEC) codes, respectively.

This paper presents a class of binary block codes capable of correcting single synchronization errors and single reversal errors with fewer check bits than the existing codes by 3 bits. This also shows a decoding circuit and analyzes its complexity.

This paper proposes a large capacity high-speed file memory system implemented with wafer scale RAM which adopts a novel defect-tolerant technique. Based on set-associative mapping, the defective memory blocks on the wafer are repaired by switching with the spare memory blocks. In order to repair the clustered defective blocks, these are permuted logically with other blocks by adding some constant value to the input block addresses. The defective blocks remaining even after applying the above two methods are repaired by using error control codes which correct soft errors induced by alpha particles in an on-line operation as well as hard errors induced by the remaining defective blocks. By using the proposed technique, this paper demonstrates a large capacity high-speed WSI file memory system implemented with high fabrication yield and low redundancy rate.

This paper proposes a new class of error locating codes which corrects random single-bit errors and indicates a location of an erroneous b-bit byte which includes e-bit errors, where 2 e b, called SECSe/bEL codes. This type of codes is very suitable for an application to memory systems constructed from byte-organized memory chips because this corrects random single-bit errors induced by soft-errors and also indicates the position of the faulty memory chips. This paper also gives a construction method of the proposed codes using tensor product of the two codes, i.e., the single b-bit byte error correcting codes and the single-bit error correcting and e-bit error detecting codes. This clarifies lower bounds and error control capabilities of the proposed codes.

Error locating codes were first presented in 1963 by J.K. Wolf and B.Elspas. Since then several code design methods have been proposed. However, their algebraic structure has not yet been clarified. It is apparent that necessary and sufficient conditions for error correcting/detecting codes can be expressed by Hamming distance, but, on the other hand, those for error locating codes cannot always be expressed only by Hamming distance. This paper presents necessary and sufficient conditions for error locating codes by using a newly defined metric and a function. The function represents the number of bytes where Hamming distance between corresponding bytes of two codewords has a certain integer range. These conditions show that an error locating code having special code parameters is an error correcting/detecting code. This concludes that error locating codes include existing bit/byte error correcting/detecting codes in their special cases.

This papter proposes a new type of unidirectional error control codes which indicates the location of unidirectional errors clustered in b-bit length, i.e., unidirectional byte error in b (b2) bits. Single unidirectional b-bit byte error locating codes, called SUbEL codes, are first clarified using necessary and sufficient conditions, and then code construction algorithm is demonstrated. The lower bound on check bit length of the SUbEL codes is derived. Based on this, the proposed codes are shown to be very efficient. Using the code design concept presented for the SUbEL codes, it is demonstrated that generalized unidirectional byte error locating codes are easily constructed.

Error correcting and/or detecting codes have been successfully used to improve the reliability of computer memories. To improve for error control in memory systems organized to have b bits per package, a new class of linear codes for simultaneous error correction and error detection is given. We refer to a group of b bits as a byte. This paper provides a new type of byte error detecting codes to correct single bit errors and detect single byte errors (SEC-SbED codes), and to correct single bit errors and detect double bit errors and single byte errors (SEC-DED-SbED codes). Form these codes, this paper demonstrates a new class of rotational SEC-SbED codes and rotational SEC-DED-SbED codes that are optimal for LSI construction of their encoding-decoding circuitries. The decoders for the proposed codes require very small amounts of extra circuitry over that required for SEC-DED (Single Error Correcting - Double Error Detecting) codes. The decoding speed is very high-equal to that of SEC-DED codes.

This paper proposes a unique type of signature testing for VLSIs, called referenceless signature testing. This testing automatically produces a reference value, i.e., correct signature, during its test intervals and compares it with compacted output of the circuit under test, i.e., signature. This makes testing much easier because it does not need the reference value, usually pre-calculated by simulation. This paper also proposes an extended form of this testing which offers economical and highly accurate one by using by-directional LFSRs for RAMs and sequential circuits. The proposed approach is successfully applied to these circuits, because the reference value can be automatically produced with their store operations and bi-directional input sequences for test data. An application of this testing to self-dual combinational circuits is also demonstrated in this paper.

One of the disadvantages of compressed data is their vulnerability, that is, even a single corrupted bit in compressed data may destroy the decompressed data completely. Therefore, Variable-to-Fixed length Arithmetic Coding, or VFAC, with error detecting capability is discussed. However, implementable error recovery method for compressed data has never been proposed. This paper proposes Burst Error Recovery Variable-to-Fixed length Arithmetic Coding, or BERVFAC, as well as Error Detecting Variable-to-Fixed length Arithmetic Coding, or EDVFAC. Both VFAC schemes achieve VF coding by inserting the internal states of the decompressor into compressed data. The internal states consist of width and offset of the sub-interval corresponding to the decompressed symbol and are also used for error detection. Convolutional operations are applied to encoding and decoding in order to propagate errors and improve error control capability. The proposed EDVFAC and BERVFAC are evaluated by theoretical analysis and computer simulations. The simulation results show that more than 99.99% of errors can be detected by EDVFAC. For BERVFAC, over 99.95% of l-burst errors can be corrected for l 32 and greater than 99.99% of other errors can be detected. The simulation results also show that the time-overhead necessary to decode the BERVFAC is about 12% when 10% of the received words are erroneous.

Since semiconductor memory chip has been growing rapidly in its capacity, memory testing has become a crucial problem in RAMs. This paper proposes a new RAM test algorithm, called generalized marching test (GMT), which detects static and dynamic pattern sensitive faults (PSF) in RAM chips. The memory array with N cells is partitioned into B sets in which every two cells has a cell-distance of at least d. The proposed GMT performs the ordinary marching test in each set and finally detects PSF having cell-distance d. By changing the number of partitions B, the GMT includes the ordinary marching test for B1 and the walking test for BN. This paper demonstrates the practical GMT with B2, capable of detecting PSF, as well as other faults, such as cell stuck-at faults, coupling faults, and decoder faults with a short testing time.

This paper proposes a new masking method for asymmetric line faults in LSIs using semi-distance codes, a class of non-linear codes. Faults caused by open or short circuit defects in line areas of LSIs can be made asymmetric by controlling the bus drive and the bus terminal gates. The conditions required for codes to mask these faults are clarified and the codes satisfying these conditions for random faults and adjacent faults, caused by line bridging defects, are constructed by using a new concept of semi-distance. This masking technique has the advantage that no additional circuits, such as error decoders, are needed. The codes have been applied to the bus lines in the address decoders of the 4-Mbit ROMs to improve fabrication yield of the LSIs.

M-spotty byte error control codes are very effective for correcting/detecting errors in semiconductor memory systems that employ recent high-density RAM chips with wide I/O data (e.g., 8, 16, or 32 bits). In this case, the width of the I/O data is one byte. A spotty byte error is defined as random t-bit errors within a byte of length b bits, where 1 ≤ t ≤ b. Then, an error is called an m-spotty byte error if at least one spotty byte error is present in a byte. M-spotty byte error control codes are characterized by the m-spotty distance, which includes the Hamming distance as a special case for t = 1 or t = b. The MacWilliams identity provides the relationship between the weight distribution of a code and that of its dual code. The present paper presents the MacWilliams identity for the m-spotty weight enumerator of m-spotty byte error control codes. In addition, the present paper clarifies that the indicated identity includes the MacWilliams identity for the Hamming weight enumerator as a special case.

Use of parity-based codes in computer systems can provide a cost-effective error detection and correction. Excellent parity-based main memory codes, such as odd-weight-column SEC-DED (Single bit Error Correcting Double bit Error Detecting) codes, can be used to arithmetic logic unit (ALU) by the technique proposed in this paper. They are more economical and better suited for a byte-sliced design of fault-tolerant computer systems than residue codes and triplication organization.

This letter presents a code which corrects single bit errors in any location of the word as well as l-bit burst errors occurred in an important part of the word. The proposed code is designed by product of the parity check matrix of the l-bit burst error correcting codes and the matrix which converts input unequal errors into equal errors. This letter also demonstrates the evaluation of the code, and presents the extended codes with two-level burst error correcting capabilities by interleaving.

Semiconductor memories are highly vulnerable to adjacent double bit errors for two reasons: 1) The bombardment of strong radioactive particles such as cosmic particles on DRAM chips and data bit lines. 2) The coupling noise in recent high density DRAM chips due to the wiring capacitance between two adjacent data bit lines. In addition, byte errors which result from entire chip failures are also a source of concern. Under this situation, codes capable of correcting adjacent double bit errors and simultaneously detecting single byte errors are suitable for application in semiconductor memory systems. This paper proposes two classes of codes called Adjacent Double bit Error Correcting-Single b-bit Byte Error Detecting (ADEC-SbED) codes and Adjacent Double bit within a b-bit byte Error Correcting-Single b-bit byte Error Detecting ((ADEC)b-SbED) codes. For the practical case where byte length is 4 bits, the proposed codes require at most one extra check bit than their bounds. Furthermore, the number check bits required by the proposed (ADEC)4-S4ED code is same as that of the well known SEC-DED code for practical information bit lengths such as 64, 128, 256, etc.

In certain computer and communication systems, the significant number of byte errors are not hard errors, but a few transient bit errors confined to byte regions. This kind of byte errors are called spotty byte errors, meaning, not all, but only 2 or 3 random bits, are corrupted in a byte. Especially, the codewords of memory systems which use recent high density wide I/O data semiconductor DRAM chips are prone to this kind of spotty byte errors. This is because, 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. Under this situation, codes capable of correcting single spotty byte errors are suitable for application in semiconductor memory systems. This paper defines a spotty byte error as a random t-bit error confined to a b-bit byte and proposes a class of codes called Single t/b-error Correcting (St/bEC) codes which are capable of correcting single spotty byte errors occurring in computer and communication systems. For the case where the chip data output is 16 bits, i.e., b=16, the S3/16EC 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 S3/16EC code is capable of detecting more than 95% of all single 16-bit byte errors at information length 64 bits.

Two-dimensional (2D) matrix symbols have higher storage capacity than conventional bar-codes, and hence have been used in various applications, including parts management in factories and Internet site addressing in camera-equipped mobile phones. These symbols generally utilize strong error control codes to protect data from errors caused by blots and scratches, and therefore require a large number of check bits. Because 2D matrix symbols are expressed in black and white dot patterns, blots and scratches often induce clusters of unidirectional errors (i.e., errors that affect black but not white dots, or vice versa). This paper proposes a new class of unidirectional lm ln-clustered error correcting codes capable of correcting unidirectional errors confined to a rectangle with lm rows and ln columns. The proposed code employs 2D interleaved parity-checks, as well as vertical and horizontal arithmetic residue checks. Clustered error pattern is derived using the 2D interleaved parity-checks, while vertical and horizontal positions of the error are calculated using the vertical and horizontal arithmetic residue checks. This paper also derives an upper bound on the number of codewords based on Hamming bound. Evaluation shows that the proposed code provides high code rate close to the bound. For example, for correcting a cluster of unidirectional 40 40 errors in 150 150 codeword, the code rate of the proposed code is 0.9272, while the upper bound is 0.9284.

The byte error locating codes specify the byte location in which errors are occurred without indicating the precise location of erroneous bit positions. This type of codes is considered to be useful for fault isolation and reconfiguration in the fault-tolerant computer systems. In this paper, difference between the code function of error-location and that of error-correction/error-detection is clarified. With using the concepts of unidirectional byte distance, unordered byte number and ordered byte number, the necessary and sufficient conditions of the unidirectional byte error locating codes are demonstrated.

Error correcting and/or error detecting codes have been successfully used to improve the reliability of computer memories. To improve for error control in memory systems organized to have b bit per package, a new class of linear codes for simultaneous error correction and error detection is given. We refer to a group of b bit as a byte. This paper provides a new class of binary error correcting codes to correct single bit errors and detect single byte errors (SEC-Sb ED codes), and to correct single bit errors and detect double bit errors and single byte errors (SEC-DED-Sb ED codes). Also, an improved byte error correction method which is called erasure correction method is proposed using the SEC-Sb ED codes. The decoders for the proposed codes require very small amounts of extra circuitry over that required for SEC-DED (Single Error Correcting-Double Error Detecting) codes. The decoding speed is very high-equal to that of SEC-DED codes. The proposed SEC-DED-Sb ED codes for b4 require about one more check bit and for b8 require about four more check bits than SEC-DED codes.

This paper demonstrates that the practical implementation of single b-Adjacent bit-group Error Correcting (SbEC) Code gives a modularized high reliability memory unit. By the application of rotational coding techniques to this code, not only a high speed parallel encoding/decoding network (memory translator), but also a memory unit can be organized in modular distributed forms, well suited for applying the LSI logic technologies to this memory translator and for achieving the high reliability and high maintainability memory unit. The parity check matrix of this code, which is easily decodable, can be expressed by the rotational operating matrix and the basic generating-submatrix. The basic hardware implementation of each modular organized translator consists of three circuitry portions which can be well designed for LSI logic. As an illustrative example, the most practical and optimum rotational (72, 64) S2EC code is implemented. The translator of this code is organized in four modular distributed forms. LSI logic patterns of each translator module require 30 to 50 input-output leads and 100 to 270 gates. The operational speed of this translator is almost equal to that of the conventional high speed SEC-DED (Single Error Correcting - Double Error Detecting) codes. As a result, this memory unit consists of four identical modules, each of which includes not only one of these translator modules, but also a storage portion and a input-output selector portion.