Browse Prior Art Database

Error Detecting code With Enhanced Error Detecting Capability

IP.com Disclosure Number: IPCOM000081227D
Original Publication Date: 1974-Apr-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 3 page(s) / 15K

Publishing Venue

IBM

Related People

Hodges, P: AUTHOR

Abstract

The code is a burst-error-correcting code, similar to a Fire code, based on four polynomials: P(0)(X) = X/22/ 1 Cycle length = 22 P(1)(X) = X/11/ X/7/ X/6/ X 1 Cycle length = 89 P(2)(X) = X/12/ X/11/ X/10/ X/9/ X/8/ X/7/ X/6/ X/5/ X/4/ X/3/ X/2/ X 1 Cycle length = 13 P(3)(X) = X/11/ X/9/ X/7/ X/6/ X/5/ X 1 Cycle length = 23.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 58% of the total text.

Page 1 of 3

Error Detecting code With Enhanced Error Detecting Capability

The code is a burst-error-correcting code, similar to a

Fire code, based on four polynomials: P(0)(X) = X/22/ 1 Cycle length = 22

P(1)(X) = X/11/ X/7/ X/6/ X 1 Cycle length = 89

P(2)(X) = X/12/ X/11/ X/10/ X/9/ X/8/ X/7/ X/6/

X/5/ X/4/ X/3/ X/2/ X 1 Cycle length = 13

P(3)(X) = X/11/ X/9/ X/7/ X/6/ X/5/ X 1

Cycle length = 23.

On encoding seven check bytes are generated, according to the generator polynomial (of degree 56) G(X) = P(0)(X)x P(1)(X)x P(2)(X)x P(3)(X).

The check bytes are generated by shifting data into a feedback shift register. Data bits are premultiplied by X/56/ so that the remainder (check bits) is completely generated when the last data bit has been shifted in. Check bits are appended to the data by shifting out the contents of the register without feedback. (The shift may be done with feedback into the low-order position to preserve the contents of the register -- s cyclic shift.)

For decoding, data and check bits are shifted into four feedback shift registers. Each of these shift registers corresponds to one of the component polynomials. Four syndromes result.

If all four syndromes are zero, the data is accepted as correct. If there are both zero and nonzero syndromes, there is an uncorrectable error in data and/or check bits; i.e., there is an error that is beyond the burst-correcting capability of the code.

If all four syndromes are nonzero, correction can be attempted according to the following procedure:
(1) Check P for correctable burst pattern (</-11-bit span).
(2) If pattern is correctable, shift P until the burst

pattern is in the low-order positions of

the register. Count the number of

shifts required (C(0)).
(3) Shift P(1) with feedback until it matches the error

pattern in P(0). Count the number

of shifts required (C(1)). If>/- 89 shifts without

a match, the error is uncorrectable.
(4) Shift P(2) with feedback until it matches the error

pattern in P(0). Count the number

of shifts required (C(2)). If>/- 13 shifts without

a match, the error is uncorrectable.
(5) Shift P(3) with feedback until it matches the error

pattern in P(0). Count the number of

shifts required (C(3). If>/- 23 shifts without

a match, the error is uncorrectable.
(6) The displacement of the last error bit (low-order bit

1

Page 2 of 3

of P(0)) relative to the last check bit is

-(A(0)C(0) A(1)C(1) A(2)C(2) A(3)C(3)) (mod M)

where

A(0) = 452,387

A(1) = 72,358

A(2) = 315,238

A(3) = 330,902

M = Block length of the code = 22x89x12x23 = 585,442.

The code haA a block length of 585,442 bits, including the 56 check bits for error correction or detection purposes. There is no distinction between data and check bits.

The code provides for detection of a single-burst error spanning 11 bits or less. In a Fire code, this combination of correction and detection would require the pattern detector, P(0)(X), to be of degree 32. The use of multipl...