| The following is an internal memo from Lih Weng, who is an expert at cyclic
codes, on the error probabilities for a block CRC. The CRC in question is
32 bits long and covers larger blocks, but I believe Lih's method can be
applied simply to a 16-bit CRC covering 4096 bits. I have taken the liberty
of editing Lih's memo to remove references to any specific products, as
this is an unrestricted conference.
***************
|d|i|g|i|t|a|l| I-N-T-E-R-O-F-F-I-C-E M-E-M-O-R-A-N-D-U-M
***************
FROM: Lih J. Weng
SUBJ: Some CRC Code Error Probabilities
This memo provides some probabilities calculation which may be used to
help the evaluation of the CRC code performance.
1. The Basic Assumptions
The bounds and probabilities obtained in this memo are based on the
following assumptions:
(a) The maximum number of data bits protected by the CRC code is
36000 bits or 4500 Bytes. (Including the 32 CRC code redundancy
bits the overall maximum code length is 36032 bits or 4504 bytes.)
(b) There are two possible error mode: the long bursty mode and the
short bursty modes. In the case of the long bursty mode the errors
last longer than 32 bits; and in the short bursty mode the errors
last no more than 8 bits. Furthermore, during the short bursty
mode, the occurrences of the bursts are statistically independent.
The short burst error rate, denoted by ps, is related to the
bit error rate BER very closely by
ps = BER/Ba
where Ba is the average short burst length. If there is no accurate
indication of the average short burst length, ps can be bounded
by
BER/B < ps < BER
where B is the maximum length of short burst. In the case of B=8,
the about bounds are within one order of magnitude.
2. Some Properties of the Shortened CRC Code and Derivation of
Probability of Undetected Errors
< editor's note: a shortened code is a code used to cover fewer bits than
it is capable of covering. CRC codes are used for burst error detection,
and an N-bit CRC can cover any N-bit burst in up to 2**N bits of message
(including the CRC itself). When it is used on fewer bits than this is
is a "shortened CRC code". A 16-bit CRC on 512 bytes is a shortened code. >
First of all, the CRC code is a cyclic code; this implies that
any successive 32 bits can be treated as the redundant bits.
Therefore, whenever there is a long burst in the frame, a portion
(which consists of 32 bits) of the burst can be treated as the
redundant bits. Since bits inside the span of a long burst are
random, there is only one 32-bit pattern which is the legitimate
redundant bits for all the other bits outside this 32-bit span;
consequently, for any long burst, the probability that the burst
is not detected by the CRC code is 2^(-32). It should be noted
that this undetected probability due to long bursts are independent
of the burst length itself as long as the burst length exceeds
32 bits.
< editor's note again. The distance of a code in this context is the smallest
number of bits that are different between any pair of legal messages with
their CRC appended. In general, the larger the distance, the better the code.
The distance of a simple parity code is 2. The distance of most any of the
communications CRC's are 3 in their unshortened form but can grow (as in
this case) when they are shortened.>
The minimum distance of the unshortened CRC code is 3. However,
the minimum distance of the shortened code is at least 4 if the
code length is limited to 36032 bits. The shortened code is
quite powerful in dealing with bursts. It is found (with a long
computer search) that the code can detect any combination of
two bursts if the length of the bursts are no longer than 8 bits in
length and that the code block length is no longer that 48941 bits.
In short, it is impossible to miss the detection of the short bursts
if there are only one or two short bursts inside a code block.
The predominant case of undetected error occurs when there are
three short bursts within a code block. It is may take a long
time to determine the exact probability of undetected error if
there are three short bursts inside a code block. However, an
upper bound of the undetected probability can be obtained by the
following argument:
Since any combination of two bursts cannot be a codeword, the
only way a given pattern of three bursts to form a codeword is
that the remainder of the two bursts when divided by the CRC
generator polynomial is equal to the remainder of another single
burst divided by the generator. There are no more than [2^(B-1)]*N
remainders for all possible single bursts in a code block of
N bits (B is the maximum length of short burst in bits). Therefore,
The undetected error probability when there are three bursts is upper
bounded by
[2^(B-1)]*N*Prob(one pattern of 3 short bursts).
With the above facts, the worst probability of the undetected
errors is bounded by (assuming B=8)
Prob(undetected errors) < Prob(One or more long bursts)/2^32
+ (2^7)*N*Prob(one pattern of 3 short bursts)
Since 2^32 = 2.3283E-10 and N<=36032
The probability of undetected errors is bounded by
Prob(undetected errors) < 2.3283E-10*Prob(one or more long bursts)
+ 4.612096E6*Prob(one pattern of 3 short bursts)
With the assumption that the short bursts are statistically
independent and making use of the short-hand notation ps for the
probability of short burst, the bound can be rewritten as
Prob(undetected errors) < 2.3283E-10*Prob(one or more long bursts)
+ 4.612096E6*ps^3
|
|
From: Computer Networks by Andrew Tanenbaum, Prentice Hall, 1981, p 132.
A 16-bit checksum, such as CRC-16 or CRC-CCITT, catches all single and double
errors, all errors with an odd number of bits, all bursts errors of length
16 or less, 99.997% of 17-bit error bursts, and 99.998% of 18-bit and longer
bursts.
|