Browse Prior Art Database

High Speed Double Error Correction System

IP.com Disclosure Number: IPCOM000074422D
Original Publication Date: 1971-Apr-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 3 page(s) / 44K

Publishing Venue

IBM

Related People

Bossen, DC: AUTHOR

Abstract

Double errors in a coded system can be corrected at high speed by a simple shift register approach which multiplies the shift register content by X/b/ rather than by the standard g(X) polynomial. The number of shifts necessary for providing double-error correction in a linear feedback shift register may be reduced to the number n over b where b = 1, 2,...,r. The amount of additional hardware required over that required for a single-error correction is small, and is essentially a linear function of the reduction factor b. This general class of high-speed error correction systems for arbitrary n and b will be discussed by way of the particular example of the (79,64) BCH code having a value of b = 4. In this arrangement, the double-error correction is obtained in 20 shifts.

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 53% of the total text.

Page 1 of 3

High Speed Double Error Correction System

Double errors in a coded system can be corrected at high speed by a simple shift register approach which multiplies the shift register content by X/b/ rather than by the standard g(X) polynomial.

The number of shifts necessary for providing double-error correction in a linear feedback shift register may be reduced to the number n over b where b = 1, 2,...,r. The amount of additional hardware required over that required for a single-error correction is small, and is essentially a linear function of the reduction factor b. This general class of high-speed error correction systems for arbitrary n and b will be discussed by way of the particular example of the (79,64) BCH code having a value of b = 4. In this arrangement, the double-error correction is obtained in 20 shifts.

The key element in the system is the LFSR which multiplies the contents by X/-b/ rather than by X. Accordingly, if errors are identified in a b-bit area, then n over b shifts are required in the worst case. The feedback connection for the X/- b/ shift register are easily determined from the polynomial g(X).

For the particular example of the (79,64) triple-error detecting BCH code, there are 78-single error patterns to be decoded. It is assumed that the 14-way AND function A(i) is constructed in a multi-level fashion as shown in diagram A.

A(i)/(1)/ is a 4-way AND gate which receives the first 4 bits of the syndrome pattern. A(i)/(2)/ represents the 10-way AND function which represents the last 10 positions of the syndrome. It will be noted that for the entire set of 78 patterns, only 2/4/ = 16 A(i)/(1)/ gates are required, representing all possible 4-bit patterns. The output of any particular A(i)/(1)/ may be distributed to more than one A(i)/(3)/. A syndrome pattern that differs by a single bit in the first 4 positions may be recognized by letting A(i)/E1/, A(i)/E2/, A(i)/E3/, and A(i)/E4/ be the 4-bit patter...