Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-03-07
2003-02-11
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S757000, C714S807000
Reexamination Certificate
active
06519738
ABSTRACT:
REFERENCES
The following references, which are incorporated herein by reference in their entirety, are referenced in the remainder of this patent document:
[1] ISO 3309, Information processing systems Data communication High-level data link control procedures Frame structure, 1984.
[2] W. W. Peterson and D. T. Brown, Cyclic codes for error detection, Proc. IRE, vol. 49, pp. 228-235, January 1961.
[3] R. E. Blahut, Theory and Practice of Error Control Codes. Reading, Mass. : Addison-Wesley, 1983.
[4] IBM Corporation, Synchronous Data Link Control Concepts, GA27-3093-3, June 1986.
[5] A. M. Patel, A multi-channel CRC register, in AFIPS Conference Proceedings, vol. 38, pp. 11-14, Spring 1971.
[6] A. Perez, Byte-wise CRC calculations, IEEE Micro, vol. 3, pp. 40-50, June 1983.
[7] G. Albertengo and R. Sisto, Parallel CRC generation, IEEE Micro, vol. 10, pp. 63-71, October 1990.
[8] T-B. Pei and C. Zukowski, High-speed parallel CRC circuits in VLSI, IEEE Trans. Commun., vol. 40, pp. 653-657, April 1992.
[9] R. J. Glaise and X. Jacquart, Fast CRC calculation, in Proc. 1993 IEEE Intl. Conf. on Computer Design: VLSI in Computers and Processors, Cambridge, Mass., pp. 602-605, October 1993.
[10] S. L. Ng and B. Dewar, Parallel realization of the ATM cell header CRC, Computer Commun., vol. 19, pp. 257-263, March 1996.
[11] M. Braun et.al., Parallel CRC computation in FPGAs, in Proc. 6th Intl. Workshop on Field Programmable Logic and Applications, Darmstadt, Germany, pp. 156-165, September 1996.
[12] S. Li and J. A. Pasco-Anderson, Efficient CRC remainder coefficient generation and checking device and method, U.S. Pat. No. 5,619,516, Apr. 8, 1997.
[13] R. J. Glaise, A two-step computation of cyclic redundancy code CRC-32 for ATM networks, IBM J. Res. Devel., vol. 41, pp. 705-709, November 1997.
[14] ITU-T Rec. I.432, B-ISDN User-Network Interface Physical Layer Specifications, pp. 16-20, March 1993.
[15] J. J. D Azzo and C. H. Houpis, Linear Control System Analysis and Design. New York: McGraw-Hill, 1981.
[16] K. Hoffman and R. Kunze, Linear Algebra. Englewood Cliffs, N.J.: Prentice Hall, 1971.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The following invention relates generally to error detection in a telecommunications environment and specifically to speeding up cyclic redundancy code (CRC) calculations to speed up error detection.
2. Related Art
The cyclic redundancy code (CRC) of a block of data, which is also called a frame check sequence (FCS), provides a standard technique for error detection in communication networks. The block of data to be protected is represented as a polynomial whose coefficients are all either 0 or 1. The frame check sequence, or CRC, is essentially the remainder resulting from the division of this polynomial by the CRC's generator polynomial.
The use of a cyclic redundancy check, or CRC, is a standard means for error detection in communication networks. A block, or frame, of binary data to be protected is represented as a polynomial over GF(2), the field of integers modulo 2. Computation of the CRC is defined in terms of division of this polynomial by a so-called generator polynomial, with the division carried out using arithmetic in GF(2). The CRC is appended to the data frame before transmission as a frame-check sequence, and is checked at the receiving end using an essentially identical polynomial division process.
The reference implementations of CRC calculation are based on a shift register with feedback that processes the input data one bit at a time. With the advent of communication interfaces operating at speeds greater than 100 Mbits/s, it has been found advantageous to design circuitry for parallel CRC computation, i.e., that operates on eight or more bits at a time. Ideally, an implementation that processes M bits at a time can achieve a full M-times speed-up, meaning that its throughput should be M times that of a bit-at-a-time implementation. In fact, all of the reported implementations to date achieve only partial speed-up.
The terms cyclic redundancy check (CRC) and frame check sequence (FCS) can be used synonymously, or can be related to one another. Technically, FCS refers to the CRC (or derivation thereof) when it is appended to the data transmission at the transmitting end to ensure that there has been a reliable transmission at the receiving end.
A formal definition of the CRC employed in data communication applications is given in a number of communication standards. The International Standards Organization (ISO) definition of a CRC is defined as follows: the K-bit frame-check sequence (where K is the bit length of the CRC) must be the ones complement of the modulo 2 sum: (a) the remainder of z
N
·U
0
(z) divided (modulo 2) by the generator polynomial G(z), where the number of bits in the input sequence to be protected by the CRC is N, and U
0
(z) is an initialization polynomial of degree less than K; and (b) the remainder of z
K
·U
p
(z) divided (modulo 2) by the generator polynomial G(z), where U
p
(z) is the polynomial representing the input sequence to be protected by the CRC. (Hereinafter, K is used to refer to the bit length of the CRC.)
For purposes of the present invention, the term CRC is be used to refer to the sum of the two remainders referred to in the definition above. The FCS that is appended to the data frame is equal to the ones complement of what is referred to as CRC in the present invention. In GF(2), finding the ones complement of a number is equivalent to adding 1 to the number.
The input sequence is a time series u(n) that takes on values 0 or 1, with time index n, starting from 0 (such that u(0) is the first bit to be processed), and the polynomial representation referred to in the CRC definition is:
U
p
(
z
)
=
∑
n
=
0
N
-
1
u
(
n
)
z
N
-
1
-
n
.
(
1
)
The generator polynomial G(z) is a polynomial of degree K. The ISO standard generator polynomials for K=16 and K=32 are (see reference [1], for example):
G
16
(
z
)=
z
16
+z
12
+z
5
+1
G
32
(
z
)=
z
32
+z
26
+z
23
+z
22
+z
16
+z
12
+z
11
+z
10
+z
8
+z
7
z
5
+z
4
+z
2
+z+
1 (2)
The initialization polynomial is generally either zero or the polynomial of degree K−1 all of whose coefficients are 1.
The error detection properties of the CRC depend on the characteristics of polynomials over the field GF(2), are well known (see reference [2], for example), and are not an issue in the present disclosure. Rather, the present invention addresses efficient means for high-speed CRC computation.
The reference implementation for computing the CRC is derived from a circuit for polynomial division that employs a shift register with feedback (see reference [3], for example), although other methods recognized by skilled artisans are also available.
One form of this reference implementation, generalized from reference [4], is shown in FIG.
1
. The blocks labeled z
−1
are unit delay elements that make up the shift register. For the block whose output is X
K
(n), for example, the input is equal to X
K
(n+1). The scale factors of the gain elements are the coefficients of the divisor polynomial G(z); i.e.,
G
(
z
)
=
∑
k
=
0
K
g
k
z
k
(
3
)
where the coefficients are assumed to be normalized with g
k
=1. The input sequence contains the finite-length block of data to be protected, for n=0, 1, . . . , N−1. After the last element of the input sequence has been processed, i.e., at n=N, the shift register contains the remainder of the division required by the CRC definition. More precisely, letting the shift register be initialized so that its contains a representation of the initialization polynomial U
o
(Z); i.e., if
U
o
(
z
)
=
∑
k
=
0
K
-
1
u
ok
z
k
(
4
Baker Stephen M.
International Business Machines - Corporation
Reid Scott W.
LandOfFree
Method and apparatus for high-speed CRC computation based on... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for high-speed CRC computation based on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for high-speed CRC computation based on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3133845