Search

Reed-Solomon (RS) codes are used in many storage systems for failure recovery. In popular software implementations, RS codes are defined by using a parity check matrix that is either a Cauchy matrix padded with an identity or a Vandermonde matrix. The encoding complexity can be reduced by searching for a Cauchy matrix that has a smaller number of 1s in its bit matrices or exploiting Reed-Muller (RM) transform in the Vandermonde matrix multiplication. This paper proposes two new approaches. In our first approach, different constructions of finite fields are explored to further reduce the number of ‘1’s in the bit matrices of the Cauchy matrix and a new searching method is developed to find the minimum number of ‘1’s. Our second approach defines RS codes using parity check matrices in the format of a Vandermonde matrix concatenated with an identity matrix so that the RS en/decoding can be simplified. A modified scheme is developed to enable the application of the RM transform such that the number of multiplications can be reduced.

Error control codes (ECCs) have been widely used to maintain the reliability of memories, but ordinary ECC codes are not suitable for memories with long codewords. For portable products, power reduction in memories with DRAM-like cells can be done by reducing the refresh frequency, but the loss of data integrity should be taken care of seriously. To solve these issues, we have proposed a parallel encoding and decoding ECC scheme to reduce refresh power for an industrial pseudo-SRAM (PSRAM) with long codewords. In this paper, we briefly review the scheme and propose a systematic way to generate the parity check matrix for the new ECC scheme. We also modify the parity correction mechanism to reduce the operating power of the scheme. As for the 70 ns access time of the 256-MB PSRAM with 64-bit codewords and 16-bit I/O, experimental results show that the new ECC scheme can be integrated with the READ/WRITE operations with about 0.2 percent circuit area overhead and less than 3.5 ns encoding/decoding time. The new ECC architecture provides a flexible solution for memories with different widths of ECC codewords and I/O ports, without the error masking effect or reduction in reliability.

A common method of constructing t-error correcting/all unidirectional error detecting (t-EC/AUED) codes is to choose a t-EC code and then to append a tail such that the new code can detect all unidirectional errors. The tail is a function of the weight of the codeword. We present a technique to reduce the weight distribution of the t-EC code so that the tail needed will be shorter in some cases. The weight distribution span of the code is reduced by eliminating the all-zero codeword and replacing it with a codeword of weight greater than 2t+1.

A parity check matrix is given for a systematic (12,8) binary code which connects all single errors and detects eight of the nine double adjacent errors within any of the three 4-b nibbles. It is shown that no (12,8) binary systematic parity check code can correct all 12 single errors and simultaneously detect all nine double adjacent errors within 4-b nibbles. A (12,8) binary systematic parity check code is given that corrects all 12 single errors and simultaneously detects eight of the nine double adjacent errors within 4-b nibbles. >

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.

A fast burst error-correction decoder is proposed. It can be used for high-speed decoding of a burst error-correcting Fire code having the generator polynomial G(x) = (1 + xC)p(x), where p(x) is irreducible and of degree m and the degree of G (x) is r = c + m, r being the number of redundancy bits. The decoder needs at most r -1 cycles to find both the error burst pattern and its location, whereas conventional decoding needs up to n cycles [1] (n is the number of bits in a codeword), or a fraction of n [2]. The decoding scheme is based on new aspects of the structure of the error syndrome and the parity check matrix of Fire code recently observed by the author. These aspects allow partial syndrome processing in the decoding process. This makes hardware costs relatively low and enables very high-speed decoding. The decoding scheme makes use of modern mapping devices such as programmable read only memories (PROM's) and field programmable logic arrays (FPLA's), resulting in relatively compact and cheap hardware. The encoder/decoder could probably be implemented as a single-chip LSI circuit.

This paper demonstrates two improvements in coding techniques that could be used for memory word coding. First, within the fixed structure of a Hamming single-error-correcting, double-error-detecting (SEC/DED) code, an improvement can be obtained in circuit cost and operational speed over more conventional code implementations. Second, the mechanics of error correction in a fault-tolerant computer may be carried out via conventional hardware means or by use of the existing system facilities, such as the combination of the microprogram unit, local store, and the arithmetic-logic unit. These improvements may be obtained by the use of Rotational Coding schemes in conjunction with a technique calied "lookaside correction." This paper first shows a generalized algorithm for specifying the parity check matrix of Rotational Codes. The structure implemented by the parity check matrix in this paper is not merely encoding and decoding circuitry, but translates between Rotational Code forms and byte-parity encoded forms. The unique feature of these translators is that use of the Rotational Code permits the error correction to be performed on only a subset of the data word bits, and only if a single-error condition has been detected. The correction mechanism may be either a hardware logic circuit or firmware. The paper concludes with a comparison of the circuit requirements and correctional speed of the Hamming (72, 64) single-error-correcting, double-error-detecting code, as it normally would be implemented, and a Rotational Code translator also operating on 64 data bits and 8 check bits.