Goal: Compute the probability of exceeding the guarenteed error detection capability of CRC codes.

Consider a linear cyclic block code C(n, k, d) used for error detection. Here,

k is the message (data) size,
n is the block size,
d is the minimum (Hamming) distance of the code, and
r = n - k is the redundancy (parity) size.

A typical CRC code can detect all random errors upto d - 1 and bursts of length upto r. These are usually referred to as the random error correction capability and burst error correction capability of the code.

To be more specific, we first define the following characteristics of an error pattern. Let E be an error pattern is a string of 0's and 1's of size n

E = (e_0, e_1, ..., e_k, ..., e_n-1), where e_k in {0, 1}

We define the following characteristics of E:

W = wt(E) = weight(E) = number of ones in E
L = bl(E) = length(E) = (burst) length of the pattern starting from the first 1 to the last 1.
- If E = (e_0 = ... = e_i-1 = 0, e_i = 1, e_j = 1, e_j+1 = ... = e_n-1 = 0), where i and j are the positions of the first and the last 1, then the (burst) lenght of E is j - i + 1.

For a given error model, and a block size n, we are interested in the following PMFs:

The error weight distribution, pW(w) = Pr{W = w}, w in {0, 1, ..., n}, and
the burst length distribution, pL(l) = Pr{L = l}, l in {0, 1, ..., n}.
The joint PMF, pWL(w, l) = Pr{W = w, L = l} may also be useful.

Error weight distribution

The procedure for computing the error weight distribution, pW(w) has already been discussed...

Burst length distribution

Strategy To compute the burst length distribution of E, we first define an enumeration procedure that systematically enumerates all the bursts of all the possible lengths. The probability calculations then simply follow this procedure by computing the conditional probabilities at each step. The conditional probabilities are based on the given error model, in this case specified as a finitie-state Markov chain used to model the decision feedback equalizer (DFE) used in the receiver frontend of the PHY.

Nomenclature Consider the 10 bit error pattern 00001xxx10, where x represents don't care, i.e. the error bit could be either a 0 or a 1. This pattern is composed of 3 parts:

a 4 bit prefix, 0000,
a 5 bit burst, 1xxx1, and
a 1 bit suffix, 0.

We will use the 3-tuple (10, 5, 1) to represent this error pattern. In general, an error pattern with total size n, burst length l, and suffix length s will be represented by the 3-tuple (n, l, s). Obviously, 0 <= l <= n, and 0 <= s <= n - 1.

Enumeration Consider a block of n bits, that we build 1 bit at a time. Suppose that we are on the k'th iteration. Then, all the error pattern Ek will be of the form (k, l, s), with 0 <= l <= k and 0 <= s <= k - l. For example, if k = 10, the above mentioned error pattern, (10, 5, 1) = 00001xxx10 is one of the possibilities.

Clearly, this pattern was a result of the most recent bit being error free (0) subsequent to a 9 bit pattern (9, 5, 0) = 00001xxx1. We write this as

(10, 5, 1) = (9, 5, 0) -> 0

where "->" reads as, "followed by".

Carrying this back one more step, we see that this time the most recent bit must have been an error bit (1), but there are more than one 8 bit patterns that would give the same result. Namely,

00001xxx1 (9, 5, 0) = 00001xx1 (8, 4, 0) -> 1,
                    = 00001x10 (8, 3, 1) -> 1,
                    = 00001100 (8, 2, 2) -> 1, or
                    = 00001000 (8, 1, 3).

Therfore, in general we can write:

     (k, l, s) = (k - 1, l, s - 1) -> 0, for s != 0, otherwise
     (k, l, 0) = (k - 1, l - 1 - s', s') -> 1, for s' = 0, 1, ..., l - 2.

Probabilities Given this enumaration procedure, and the Markov chain error model, the joint probability of the error patterns and state transitions can be computed using the following recurrence relations:

Pr{Ek=(k, l, s), sa->sb} = Sum(over all sx)[ Pr{Ek-1=(k - 1, l, s - 1), sa->sx} * Pr{ek=0, sx->sb}} ] +
                           Sum(over all sx)[ Pr{Ek-1=(k - 1, l - 1, 0), sa->sx} * Pr{ek=1, sx->sb}} ] +
                           Sum(over all sx)[ Pr{Ek-1=(k - 1, l - 2, 1), sa->sx} * Pr{ek=1, sx->sb}} ] +
                           ...
                           Sum(over all sx)[ Pr{Ek-1=(k - 1, 1, l - 2), sa->sx} * Pr{ek=1, sx->sb}} ].

The joint probabilities of an n bit error pattern En and ending-state Sn can now be calculated as

Pr{En=(n, l, s), Sn=sb} = Sum(over all sa)[ Pr{S0=sa} * Pr{En=(n, l, s), sa->sb} ],

where Pr{S0=sa} is the probability of being in state sa in steady-state.

Next, we calculate the probability of an n bit error pattern En by summing over all the ending states Sn

Pr{En=(n, l, s)} = Sum(over all sb)[ Pr{En=(n, l, s), Sn=sb} ].

Finally, the desired burst length distribution for the n bit block can be calculated by summing over all suffix lengths for a given burst length

pL(l) = Sum(over all s)[ Pr{En=(n, l, s)} ].