Two Bit Error Correction and Three Bit Error Detection Scheme with Minimal Latency

Overview

This page describes an error detection and correction scheme which:

• Corrects 1-bit and 2-bit errors and detects 3-bit errors for a 32-bit data path,
• Detects a large percentage of higher-order (4-bit, 5-bit, etc) bit errors,
• Uses no more than 16 check bits (2-bit correction requires  2^r >= r + d + 1 + comb((d+r)|2), which is satisfied for d =32 if r > = 11),
• Works for any combination of data or check bit errors, and
• Can be implemented with minimal latency.

To achieve low latency, a separate data path and control path were developed, and the number and type of check bits was changed from the traditional approach used for error detection and correction.  While the traditional approach uses one monolithic check matrix and requires the control path to wait for the data path computations, the approach here is to detect the error type (i.e. no error, single, double, or triple-bit error) using two fast SEC/DED codes.  This way the error type can be detected well ahead of the double-bit correction logic to complete.  The primary drawback to this scheme is that the number of check bit is more than the minimum required.

Description

The heart of the scheme is the check matrix, which is made up of the following components:

• A sub-matrix (in green background in the matrix below) which has 7 check bits, odd-weight, minimum ones evenly distributed, checking a 32-bit data path.  This sub-matrix is capable of correcting single-bit errors and detecting double-bit errors.  Using an odd-weight allows the circuit to be simple, and evenly distributing the ones in the matrix makes the circuit fast.  Further merits of this code are discussed in the IBM Journal of Research and Development.  The check bits for this sub-matrix are referred to as ck_A.

• A second sub-matrix (in blue background in the matrix below) similar to the first, but with 8 check bits. This sub-matrix is also capable of correcting single-bit errors and detecting double-bit errors.  These check bits are referred to as ck_B.  The check bit selection was such that triple data bit errors, possibly masquerading as single-bit errors in both the ck_A and ck_B sub-matrices, don’t masquerade as the same data bit.  Since triple-bit errors will not masquerade as the same single-bit error, the two syndromes can be decoded to detect triple-bit errors.  

• A parity bit (in yellow background in the matrix below) is generated over the check bits in the second sub-matrix.  By detecting single bit errors in the second sub-matrix's check bits, the validity of its single-bit error correction can be determined.

The scheme developed works for any combination of data or check bit errors.  It will detect, for example, 2 data bits and 1 check bit in error.  Likewise, it will detect (or ignore) 3 check bits in error.  

Instead of a monolithic check matrix with a Hamming distance of 5 (needed for 2-bit correction, distance  = 2d+1 for d bits corrected), the two sub-matrices both have minimum distance of 4.  Both are capable of correcting single-bit errors and detecting double-bit errors.  

The number of check bits is 16, which is well above 11, the minimum required.  A goal of 16 check bits was arrived at by rounding up to the next byte boundary (the minimum of 11 bits needed was rounded up to 16).  This relaxation, although potentially very costly for a memory of custom width, has no impact when standard memory devices are used (which have byte granularity).  The benefit of this relaxation was that it permitted the control logic to be driven strictly by low latency circuits, as described in more detail in the "A More Realistic Block Diagram of Decode Circuit" and "Control Logic" sections below.

Check Matrix

Block Diagram of the Decode Circuit with Comments

A More Realistic Block Diagram of Decode Circuit

The block diagram shown above is notional only.  The dbl_decode_1 block contains 496 AND gates (32 items taken 2 at a time) which present around 150 to 200 loads on each of the syndrome signals (Synd_A and Synd_B).  In addition, there are 32 OR gates in the dbl_decode_2 block, each of which has 31 inputs.  These high fan-in and fan-out circuits will have timing problems during logic implementation.  Since the circuits are combinational, the logic can be split over several clock cycles.  The block diagram below shows the additional pipeline stages (i.e. pipeline registers at intersections with the blue lines) needed for a more realistic implementation.  Since the control logic can determine what kind of error occurred before the results from the double-bit decode is available, it is capable of returning the no-correction or single-bit correction data with little penalty over a single-bit-only error correction circuit.  Obviously, the control logic must have some control over the timing of returned data if it needs to wait (albeit rarely) for the corrected double-bit error data.

Control Logic

One of the requirements for a low-latency circuit is that the inputs to the control circuit not depend on the results of the high-latency (double bit locator) circuits.  Thus, the control logic is designed to compute the error type using the following information:

• the syndromes from the two sub-matrices,
• parity of the B sub-matrix,
• an indication if the A and B syndromes point to the same single bit being in error ("sgl/tpl"), and
• in indication if the B syndrome indicates no errors ("lb0") . 

To detect the type of error that has occurred, the control logic takes advantage of the fact that the two single-bit syndromes will both have an even number of bits high for a double-bit error.  The following table, which shows the input values for error combination cases for 0, 1, 2, and 3 bit errors, was generated based on this fact.  This table was used to create the control logic in the javascript code.  Note that some error combinations do not require corrections (i.e. errors in the check bits only), so these errors are "ignored".

Response to Higher-Order Bit-Errors

The scheme's response to higher-order bits errors for all error combinations up to 7 bits was simulated with the results shown in the table below.  In general, about half of the even-bit-errors are detected, and about 90% of the odd-bit-errors are detected.