Browse Prior Art Database

Catamaran Cyclic Redundancy Checks Improvements

IP.com Disclosure Number: IPCOM000111175D
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 2 page(s) / 94K

Publishing Venue

IBM

Related People

Eggenberger, J: AUTHOR [+2]

Abstract

Cyclic Redundancy Checks (CRC) are frequently used to detect errors in data. It is always possible that a pattern of errors can be undetected by a CRC which would cause the data to be verified as correct while in fact, it was in error. Multiple CRC can be used to increase error detection capability. A method for designing multiple CRC is shown which increases the likelihood that an error which was not detected by one of the CRC would be detected by the others.

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

Catamaran Cyclic Redundancy Checks Improvements

      Cyclic Redundancy Checks (CRC) are frequently used to detect
errors in data.  It is always possible that a pattern of errors can
be undetected by a CRC which would cause the data to be verified as
correct while in fact, it was in error.  Multiple CRC can be used to
increase error detection capability.  A method for designing multiple
CRC is shown which increases the likelihood that an error which was
not detected by one of the CRC would be detected by the others.

      CRC (Cyclic Redundancy Checks) are frequently used to detect
errors in data.  A CRC check symbol is calculated from the data
symbols and appended.  The CRC check symbol is calculated as:

          CRC lparen k rparen eq sum from i of T sup lparen k times i
0paren times D sub i
where D sub i are the sequence of data symbols indexed by i, T is a
transformation representing multiplication by a primitive field
element and k is an integer.

      To verify the data, the CRC check symbol is re-calculated from
the potentially erroneous data symbols.  This calculated CRC check
symbol is added to (exclusive ORed with) the appended CRC check
symbol as read to generate syndrome.  If this syndrome is zero, the
data is assumed to be correct.  If the syndrome is non-zero, the data
is assumed to be contaminated with errors.

      It is always possible that a combination of errors will produce
a zero syndrome, causing the erroneous data to be accepted as valid.
If there are two or more data symbols in error and the errors are
random, the probability false validation is 1 divslash A, where A is
the number of symbols in the symbol alphabet.  It is, of course, a
desirable goal to reduce this probability of false validation to an
acceptably low value.

      One way to reduce the probability of false validation is to use
a large value of A, that is, base the CRC on symbols involving a
large number of bits.  However, if the CRC is used in conjunction
with an error correcting code (ECC), the CRC syndromes must be
adjusted for each correction made by the ECC.  The computations for
this adjustment are more conveniently done if the ECC and the CRC are
both based on the same symbol alphabet, and the ECC requirements can
prohibit a large enough symbol alphabet to reduce the probability of
false validation to an acceptably low value.

      Another way to reduce the probability of false validation is to
use multiple CRC check symbols.  A number of CRC check symbols can be
generated acco...