Browse Prior Art Database

Technique for Cyclic Redundancy Check Modification Useful in Certain Data Networks

IP.com Disclosure Number: IPCOM000112890D
Original Publication Date: 1994-Jun-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 6 page(s) / 256K

Publishing Venue

IBM

Related People

Corr, F: AUTHOR [+5]

Abstract

It is known that, when some bits are intentionally modified in a data frame protected by a Cyclic Redundancy Check (CRC) sequence, it is possible to compute a CRC for the modified frame without exposing the integrity of the bits that were not changed as described in [1]. This disclosure describes an implementation of Irvin's algorithm that requires a minimum of per-frame processing, no special hardware and modest table space, even when multiple bit manipulation is performed on the data frame.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 20% of the total text.

Technique for Cyclic Redundancy Check Modification Useful in Certain
Data Networks

      It is known that, when some bits are intentionally modified in
a data frame protected by a Cyclic Redundancy Check (CRC) sequence,
it is possible to compute a CRC for the modified frame without
exposing the integrity of the bits that were not changed as described
in [1].  This disclosure describes an implementation of Irvin's
algorithm that requires a minimum of per-frame processing, no special
hardware and modest table space, even when multiple bit manipulation
is performed on the data frame.

      Transmitted data is often protected against errors in
communication systems by the use of Cyclic Redundancy Check (CRC)
algorithms.  A Frame-Check Sequence (FCS) is computed at the
transmitter for a data frame by application of a CRC algorithm to the
frame's contents.  The FCS is then appended to the data frame and so
is transmitted along with the data.  The receiver applies an
equivalent CRC algorithm to the contents of the frame it receives and
compares the resulting FCS with that in the frame.  If the two FCSs
match, then the probability that there is an error in the received
data is essentially zero.  The error detection properties of the CRC
algorithm are derived using the theory of polynomials whose
coefficients are drawn from the field of integers modulo 2 (i.e., 0
and 1) by considering a data sequence (i.e., a sequence of 1s and 0s)
to be represented by such a polynomial [2].

      In some networks, one or more bits in the header of a frame may
be modified by a switching node as it routes the frame.  If the
header and the data are protected by a single FCS resulting from the
application of a CRC algorithm to the entire frame (as is the case
for the HDLC frame format, for example), then the node will have to
replace the FCS in the frame with one that takes into account the
bits that have been changed.  If the new FCS is simply recomputed by
applying the CRC algorithm to the contents of the modified frame,
then errors that may have affected supposedly unmodified bits in the
data while the header bits were being changed (for example due to
noise or other problems inside the switching node) would be
undetected by any succeeding CRC checks.  The reference [1]  has
described an algorithm that computes a new FCS based on the received
FCS (i.e., of the unmodified frame) and the bits that are
intentionally modified in the frame.  This algorithm maintains
protection of all bits not intentionally modified against errors both
on transmission channels and within switching nodes.

For a CRC of length K bits, Irvin's algorithm operates as follows:

1.  Form a dummy frame of length L bits consisting of all zeros,
    where L is the length in bits of the data frame, not including
    the CRC sequence, being routed.

2.  Change from zero to one those bits in the dummy frame that occur
    in the same positions as the bits in the data fr...