Traditional cyclic redundancy checking (CRC) techniques have emerged as a strong solution for handling errors in emergingwireless and DSL designs.
Cyclic redundancy checking (CRC) isn't just for modems anymore. It's a great way to perform bit error rate (BER)
heuristics on any digital data transmission system of any length. Understanding the various types of cyclic codes is
helpful in accurate live-traffic error testing, as well as for predictive efforts.
The past few years have seen a steady increase in the deployment of digital networks. This trend is making its way
from the service provider's internal networks out to the end-user (across the local loop). Toward this end, new
digital-access technologies are being developed which include broadband wireless access and DSL technology. Due to
the expansion of digital networks, the need for measuring the BER has become increasingly important as a means to
determine quantitatively the quality of the transmission system. While these measurements are important, they must
be made nonintrusively so as to maximize the customer's data throughput.
Typically, digital data is carried in frames, which consist of overhead that provides bits for payload synchronization,
embedded control channels (EOCs), and error detection or correction. The framing bits provide a pattern, which allows
the receiver to synchronize with the payload, which contains multiple subchannels. For example, in DS1 there are 24
subchannels and in E1 there are 32 subchannels. The EOC is used to provide network-maintenance functions such as
requesting loopbacks, sending alarms, and collecting statistics.
Many digital framing structures also provide some bits for detection of channel errors. This includes the most popular
digital carriers such as DS1, DS3, and DSL.
The most common way to provide error detection is by employing CRC codes, which are an important subclass of linear
block codes. A linear-code C is cyclic if every cyclic shift of a code word in C is also a code word in C. An (n,k) linear
code uses n - k parity bits and k information bits. Two examples of linear codes are the CRC-6 code used for DS1 and
the parity code used for DS3. Both of these are parts of the North American digital hierarchy.
In analyzing codes, with regard to being able to predict the BER, it is necessary to determine the detection-probability
PD. A block-codes detection probability PD is the probability of detecting an error for a given block size. Our main
concern will be to examine how, through statistical means, PD can be estimated.
Since PD is a function of the BER, the BER can be determined with a certain confidence and accuracy given that the
statistical relationship between the PD and BER is known for the given code.
Polynomial representation
For a cyclic code, the binary digits of the code word are represented as coefficients of a polynomial. The polynomial is
written with the LSB (first bit transmitted) as the highest-order coefficient and the MSB (last bit transmitted) as the
first coefficient. For example, the binary message M = b0 b1 b2 b3 would be represented by the polynomial m(x) = b0
+ b1x1 + b2x2 + b3x3.
The original k information bits are appended with n - k parity bits at the end. The resulting transmitted message is n
bits long. The parity bits are calculated by multiplying the message polynomial by x(n - k) and then dividing by the
generator polynomial g(x).
Equation 1
The remainder after division is the parity polynomial r(x). It is appended to the message polynomial m(x) to form the
transmitted polynomial s(x).
Equation 2
Every transmitted polynomial is a multiple of the generator polynomial. This can be proved by noting that r(x) has a
degree less than g(x):
Equation 3
The received polynomial u(x) contains the transmitted polynomial plus an error polynomial e(x) that represents the
channel errors:
Equation 4
The receiver divides the received polynomial by g(x) and takes the remainder:
Equation 5
An error is detected only if e(x) is not a multiple of g(x), in which case the remainder is zero:
Equation 6
Figure 1 shows a sequential circuit for calculating the remainder. The coefficients in the circuit are the polynomial
coefficients for the generator polynomial g(x). The lowest- and highest-order coefficients are always equal to 1. The
message polynomial m(x) is shifted in starting from the highest order first. After the register is shifted n times, the
contents of the shift register will be the coefficients of the remainder polynomial r(x).
Equation 6 shows that the probability of detection depends only on the error polynomial e(x). Therefore, you can use
the sequential circuit shown in Figure 2 to develop a mathematical model for the detection process.
An assumption that is most often made is that the channel is memoryless, which implies that the errors are not
correlated. A channel error occurs with probability p and does not occur with probability q = 1 - p.
The circuit in Figure 2 has m = 2n-k states: S0 = [0 0 0 ... 0], S1 = [0 0 0 ... 1, Sn-k-1 = [1 1 1 ... 1]. An error is
represented by a coefficient of 1, which causes the circuit to shift to the next state. An absence of an error is
represented by a coefficient of 0, which causes the circuit to remain in the current state. The circuit exhibits first-order
Markov dependence and can be modeled as a Markov chain. A system exhibits Markov dependence if the conditional
probability of moving from the current state to the next state depends only on the current state. As a result of this
property, the probability of moving from state i at step m to state j at step n is:
Equation 7
Equation 7 is the discrete time form of the Chapman-Kolmogorov equation. It is extremely important in the study of
Markov chains and will be used later to solve for the n-step transition matrix.
It is convenient to represent the transition probabilities in matrix form. This matrix is referred to as the n-step
probability transition matrix P(n) and is shown in Equation 8. The entries aj,k represent the probability of moving from
state j at step n to state k at step n + 1.
Equation 8
This matrix is initialized to zero at step-0 and is shifted n times. For simplicity, the initial one-step transition matrix
P(1) shall be denoted by P, suppressing the step index.
The transition matrix after the nth shift is equal to the one-step transition matrix P raised to the nth power.
Equation 9
From which the probability of detection after n shifts is the probability of not being in state zero:
Equation 10
Proof 1
Consider the two-state, one-step transition matrix:
Proof 1.1
From the Chapman-Kolmogorov equation (Equation 7) the following probabilities for moving from state i to j after two
steps are derived.
Proof 1.2
from which:
Proof 1.3
Note that the two-step transition matrix is equal to the one-step transition matrix squared:
Proof 1.4
Next, solving for the three-step matrix yields:
Proof 1.5
Continuing this process we come to:
Proof 1.6
Two popular CRC codes are described in the next section. These are the single-parity bit code used in the DS3 signal
for-mat and the CRC-6 code used in the DS1 signal format. A description of these codes is given to provide concrete
examples of CRC codes and to demonstrate the techniques for determining the detection probability for CRC codes in
general.
Parity code
The parity code is used in the North American DS3 digital signal format. The generator polynomial for the this code is:
Equation 11
The parity code can only detect error patterns with an odd number of terms.
Proof 2 5
Define an error vector with errors at a, b, c, etc:
Proof 2.1
Letting x = 1 yields:
Proof 2.2
The left-hand side can equal zero only if there are an even number of terms. Therefore, from this result and from
Equation 6, only error patterns with an odd number of errors can be detected by the parity code.
The initial transition matrix for the parity code is:
Equation 12
It can be shown that Pn=QDnQ-1 where Q is a matrix whose columns are the eigenvectors of P, and D is a diagonal
matrix whose diagonal contains the eigenvalues of P.4 The eigenvalues of P are:
Equation 13
The corresponding eigenvectors of P are:
Equation 14
Solving for Pn and substituting q = 1 - p yields:
Equation 15
From this, the detection probability for a single parity code is:
Equation 16
Detection probability levels off at a value of p(MAX), which depends on the block size n. Being able to predict the true
bit error from the detection probability is limited to the region below this knee. The knee can be extended to occur at
higher error rates by decreasing the block size.
Typically, the digital line is engineered for a BER of 1E-8 or better. For digital lines, a minor and major alarm can be
defined, which are often set at 1E-6 and 1E-3, respectively. A minor alarm is an indication that the line has degraded
and may need servicing, but the service is still considered available. A major alarm is an indication that the line is
down and has degraded to the point where service is no longer available. For example, in the DS1 format if there are
332 or more CRC errors in a second, a failed signal state (FSS) is declared. This corresponds to a BER of about 1E-3.
Beyond the minor alarm threshold it is not important to be able to determine the exact BER. There-fore, codes should
be designed such that the knee of the detection probability corresponds to the major alarm threshold.
CRC-6 code
The CRC-6 code is used in the North American DS1 digital signal format. The generator polynomial for the CRC-6 code
is:
Equation 17
Figure 3 shows the circuit for calculating a CRC-6 checksum.
A closed-form expression for the CRC-6 code is difficult to find using techniques similar to the previous section.
However, by intuitive reasoning you can determine an approximation. It can be shown that for sufficiently long error
vectors the ratio of detected error vectors to total error vectors is:5
Equation 18
For the CRC-6 code, this translates into a ratio of detection ratio of approximately 63/64. Therefore, an approximation
for the detection probability is proposed that says the detection of probability is:
Equation 19
MATLAB simulation was used to calculate the actual detection probability for CRC-6 with n = 4,632 bits. Table 1
compares the actual detection probabilities with the detection probabilities predicted in Equation 19.
|
Table 1: PD for CRC with n=4,632
|
|
|
PD |
| p |
|
Actual |
| 10-2 |
.9843 |
.9843Actual |
| 10-3 |
.9754 |
.9748Actual |
| 10-4 |
.3685 |
.3649Actual |
| 10-5 |
.045 |
.045Actual |
| 10-6 |
.0045 |
.0045Actual |
Detection probability
In this section we propose a linear unbiased estimator for determining the detection probability PD. Start by defining a
variable Xk such that Xk = 1 if a code word has detected an error with probability PD and Xk = 0 if no error is detected
with probability 1 - PD. Xk is an independent Bernoulli variable whose probability density is:
Equation 20
The mean and variance of Xk is found using the moment generating function Gx(z):
Equation 21
The mean of Xk is:
Equation 22
The variance of Xi is:
Equation 23
We have established by Equation 22 that the mean of random variable Xk is the detection probability PD. The ultimate
goal is to be able to estimate the mean of Xk. It is important that the estimator chosen is unbiased and consistent.
An unbiased estimator is one whose sample mean equals the target parameter, which in this case is PD. An estimator
is consistent if the sample variance approaches zero as the number of samples approaches infinity. In other words, the
more samples taken the better the estimate.
The following is an unbiased and consistent estimator for the detection probability:
Equation 24
Yiis unbiased.
Proof 3
Proof 3.1
Yiis consistent.
Proof 4
Proof 4.1
from which:
Proof 4.2
The probability distribution for Yiis f(y), and if the number of samples taken is large, this tends to be normally
distributed with mean 
y and variance 
y2.
Equation 25
In dealing with estimates it is necessary to determine the required accuracy of the estimate. This is done by
specifying a confidence level C and accuracy bound A. The accuracy A is the allowed variation from the target
parameter being estimated. The confidence level C is the percentage of times the estimate meets the required
accuracy.
For example, assume that an estimate of a parameter is required to be within 80% of the true value greater than 99%
of the time. Then A = 0.8 and C = 0.99. The confidence level can be found by subtracting the mean from f(y) and
integrating from:
Equation 26
where:
Equation 27
Defining a change of variable
, substituting 
into Equation 26, and noting that f(y) is an even function, then the
confidence level can be expressed as:
Equation 28
where:
Equation 29
An expression for the minimum number of samples required to achieve a specific confidence and accuracy is:
Equation 30
The procedure for determining the minimum required sample size is illustrated in Example 1.
Example 1
A CRC-6 code is used for DS1 signal. The bit rate is fB = 1.544 Mbps. The block size is n = 4632. A minor alarm
threshold is set at 1E-6. You must measure BER to detect when a line condition exceeds the minor alarm. There-fore
the BER greater than or equal to 1E-6. It is desirable to estimate the BER with an accuracy A = 90% and confidence C
= 95%. Find the minimum sample size and the minimum sample time required to meet the given confidence and
accuracy.
Solution:
Use Table 2, which expresses ERF values, to find B.
|
Table 2: ERF(B) Values
|
| B |
ERF(B) |
B |
ERF(B) |
| 0 |
0 |
1.3000 |
0.9340 |
| 0.1000 |
0.1125 |
1.4000 |
0.9523 |
| 0.2000 |
0.2227 |
1.5000 |
0.9661 |
| 0.3000 |
0.3286 |
2.0000 |
0.9953 |
| 0.4000 |
0.4284 |
2.1000 |
0.9970 |
| 0.5000 |
0.4284 |
2.2000 |
0.9981 |
| 0.6000 |
0.5205 |
2.3000 |
0.9989 |
| 0.7000 |
0.6039 |
2.4000 |
0.9993 |
| 0.8000 |
0.6778 |
2.5000 |
0.9996 |
| 0.9000 |
0.7969 |
2.6000 |
0.9998 |
| 1.0000 |
0.8427 |
2.7000 |
0.9999 |
| 1.1000 |
0.8802 |
2.8000 |
0.9999 |
| 1.2000 |
0.9103 |
|
|
Ex. 1
Use Equation 19 to solve for PD:
Ex. 2
Use Equation 30 to solve for the minimum sample size:
Ex. 3
The total sample time is:
Ex. 4
Figure 4 plots the detection probability parity code.
The knee of the CRC-6 code occurs at a slightly higher value of p than the parity code. However, the CRC-6 code uses
six redundant bits as compared to one for the parity code. If six parity bits were used, each parity bit calculating parity
over n/6 bits, then the knee for the parity code could be extended to approXimately the same point as the CRC-6 code.
Estimating the BER
The previous section described the means to estimate the detection probability PD. The next step is to translate this
into an estimate of the BER. From Equation 16, the BER estimate for the parity is given by:
Equation 31
From Equation 19, the BER estimate for the CRC-6 is given by:
Equation 32
The BER can be calculated directly from Equations 31 and 32 for parity or CRC codes respectively. However, for
real-time applications it may be easier to use a table look-up method. This requires a table of the precalculated
detection probabilities and corresponding BER for a particular code to be stored in memory.
The linear estimator given by Equation 24 is continuously estimating the detection probability. Since the sample time
is fixed, a given detection probability corresponds to a specific number of errors for the specified sample time. The
number of errors detected in the sample time forms the address to the table lookup, where the corresponding BER can
be read from the table. MATLAB simulations were used to estimate the detection probability for the Parity Code. The
results are shown in Figure 5.
Despite trade-offs in terms of accuracy and confidence of BER estimates due to sample size, it should be apparent
that CRC codes are useful tools for predicting the line BER on customer traffic. This provides a useful tool for system
engineers to qualify the digital networks they manage.
About the Author
Jeffrey S. Pattavina is the chief technical advisor for development of broadband wireless access at Harris Corp. He has
over 20 years experience developing access and test equipment in the voice and data communications industry. He
holds an MSEE from Northeastern University and can be reached at ptvn@snet.net.
References
- Peterson, W.W. and E.J., Weldon, Error Correction Codes, 2nd ed. MIT Press, 1972.
- Shu, L. and D.J., Costello, Error Control Coding: Fundamentals and Applications, Prentice-Hall, 1983.
- Sripad, A.B. and J.W., Smith, Performance of the Cyclic Redundancy Check Code in the New 1.544-MB/s Extended
Framing Format, AT&T Bell Laboratories: IEEE, 1984.
- Bhat, Narayan. Elements of Applied Stochastic Processes, 2nd ed. John Whiley & Sons, 1984.
Peterson, W.W. and D.T., Brown, Cyclic Codes for Error Detection, Proceedings of the IRE, 1960.
White, J.A., Schmidt, J.W., and G.K., Bennett. Analysis of Queueing Systems, Academic Press, 1975.
