Browse Prior Art Database

High-Speed Error Correction Coding

IP.com Disclosure Number: IPCOM000035169D
Original Publication Date: 1989-Jun-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 4 page(s) / 117K

Publishing Venue

IBM

Related People

Bossen, DC: AUTHOR [+2]

Abstract

Most error-correcting codes (ECC) used in semiconductor memory systems are the SEC-DED codes that correct all single errors and detect all double errors in an ECC code word. The error correction for these codes is typically implemented in the following three sequential steps: 1. The syndrome is generated from the word read from the memory. 2. The syndrome is decoded using a set of AND gates to generate error signals. (There are as many error signals as the number of data bits.) 3. Each of the error signal is XORed with its corresponding data bit for the error correction.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 4

High-Speed Error Correction Coding

Most error-correcting codes (ECC) used in semiconductor memory systems are the SEC-DED codes that correct all single errors and detect all double errors in an ECC code word. The error correction for these codes is typically implemented in the following three sequential steps: 1. The syndrome is generated from the word read from the memory. 2. The syndrome is decoded using a set of AND gates to generate error signals. (There are as many error signals as the number of data bits.) 3. Each of the error signal is XORed with its corresponding data bit for the error correction.

In this article, two approaches are provided to increase the speed of error correction for SEC-DED codes. The first approach is to construct codes that reduce the number of logic levels in generating the error syndrome. The second approach is to combine the steps in error correcting procedure so that the total logical delay can be reduced. Using these approaches, the number of logic levels in error correction can be greatly reduced.

The construction of codes for high-speed error correction has been reported in [2]. The parity check matrix of a code constructed in [2] has two ones in each data column. This enables the use of 2-way ANDs in generating error signals. Although this scheme reduces the complexity in syndrome decoding, there is little improvement in the overall logic delay.

(Image Omitted)

The number of levels of logic delay in the generation of a syndrome bit is proportional to the logarithm base 2 of the number of ones in the parity check equation for the syndrome bit. Thus, it is desirable to keep the number of ones in each row of the parity check matrix of the ECC at a minimum, for example, at 2, 4, 8 or 16. The price paid for the reduction of logic delay is the increase of the number of check bits.

Consider the weight-2 column codes of [2] with an overall parity check. Let k and r be the number of data bits and the number of check bits in a code word. Then parameters satisfy the condition: k < (r-1) (r-2)/2. Now, limit the number of ones in each row of the parity check matrix to a maximum of 2**m, and let k(m) be the number of data bits for the new code. If 2-way XOR gates are used to generate the error syndrome. Then, it requires m levels of logic delay in the syndrome generation. Obviously, k(m) < k, and it is easy to show that and k(m) < ((2**m)-1) (r-1)/2.

Table I lists the maximum number of data bits for some check bits with m=2, 3 and 4. For example, a (82,63) code with 63 data bits and 19 bits is shown that requires m=3 levels of 2-way XOR delay in generating the error syndrome. A conventional SEC-DED code for 63 data bits requires 8 check bits with 6 levels of 2-way XOR delay in generating the error syndrome.

(Image Omitted)

1

Page 2 of 4

TABLE I R K K(2) K(3) K(4) D 6 8 7 10 10 8 21 10 21 21 10 36 13 31 36 13 66 18 42 66 19 153 27 63 135 20 171 28 66 142

The parity check matrix of an (82,63) code is shown i...