Browse Prior Art Database

Byte-Wide ECC/CRC Code and Syndrome Calculator

IP.com Disclosure Number: IPCOM000062118D
Original Publication Date: 1986-Oct-01
Included in the Prior Art Database: 2005-Mar-09
Document File: 4 page(s) / 72K

Publishing Venue

IBM

Related People

Nielson, MC: AUTHOR [+2]

Abstract

This article discloses logic circuitry for performing both CRC (Cyclic Redundancy Check) codes and Fire codes, which are Error Correcting Codes (ECC). The described technique is useful in data retrieval, e.g., from magnetic media, or communications over noisy channels. Redundant information is used when storing or transmitting data to enable detection and correction of errors during retrieval or receiving of the stored or transmitted data, respectively. Two popular redundancy schemes use CRC and Fire codes. CRC codes are commonly used to detect errors when reading from floppy disks and Fire codes are usually used to detect and to correct errors when reading from hard disks. Typically, the codes are calculated serially, i.e., processed one bit of data at a time.

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

Page 1 of 4

Byte-Wide ECC/CRC Code and Syndrome Calculator

This article discloses logic circuitry for performing both CRC (Cyclic Redundancy Check) codes and Fire codes, which are Error Correcting Codes (ECC). The described technique is useful in data retrieval, e.g., from magnetic media, or communications over noisy channels. Redundant information is used when storing or transmitting data to enable detection and correction of errors during retrieval or receiving of the stored or transmitted data, respectively. Two popular redundancy schemes use CRC and Fire codes. CRC codes are commonly used to detect errors when reading from floppy disks and Fire codes are usually used to detect and to correct errors when reading from hard disks. Typically, the codes are calculated serially, i.e., processed one bit of data at a time. The codes operate by treating the data as a polynomial in X, the exponent of X corresponding to the power of a bit position in the binary vector. For example, the binary data stream represented by 1 1 0 0 0 1 is represented as a polynomial in X by x5 + x4 + 1. The polynomial representation enables the data stream to be manipulated mathematically as a Galois Field, specifically described as GF(0,1, +,*). The specification indicates the Galois Field uses the operands 0 and 1 with the operations addition (modulo-2), which is equivalent to the Boolean operator XOR (Exclusive-OR), and multiplication, which is equivalent to the Boolean operator AND. Subtraction modulo-2 is the same as addition. Division is accomplished by repeated subtraction. If v(i) represents the binary vector v left- shifted i spaces, then if Xiv(X) is divided by Xn+1, the remainder will be v(i)(X). That is, with q(X) representing the resulting quotient, Xiv(X) = q(X)(Xn+1) + v(i)(X). Furthermore, v(i)(X) = Xiv(X) if the degree of Xiv(X) is not greater than n- 1. Letting m(X) represent k message bits, v(X) = m(X)g(X) = (m0 + m1X + m2X2 + . . . + mk-1Xk-1)g(X) where g(X) is called the generator polynomial; it generates n-k parity bits, resulting in an (n-k)-th degree polynomial. Furthermore, g(X) is a factor of Xn+1 such that Xn+1 = g(X)h(X). Therefore, if g(X) is a polynomial of degree n-k and a factor of Xn+1, g(X) generates an (n,k) cyclic code. One widely used generator polynomial, e.g., in synchronous data transmission systems, is g(X) = x16 + X15 + X2 + 1 which detects all odd numbers of error bits, all possible single error bursts of length not greater than 16 bits, 99.9969% of all possible error bursts of 17-bit length, and 99.9984% of all possible longer bursts. The errors are detected by dividing the message, m(X), by g(X) and transmitting the remainder of n-k parity bits, p(X) with the message bits. At the receiving end, the entire vector of n bits is divided by g(X). If the remainder is zero, the message was received correctly. If the remainder is not zero, then at least one error occurred in the transmission. The logic circuits for serially dividing a...