Polynomial representation:

D(x)= Data word

C(x)= Code word

g(x)= Generator polynomial

s(x)= Syndrome

e(x)= error Polynomial

Single bit error is e(x)=xi where I is the position of the bit in error. If single bit error is caught then xi ≠ divisible by g(x). If generator has more than 1 term and the coefficient of x=1, all single errors can be caught. If sex) is not zero, then one or more bits is corrupted. However, if s(x) is zero, either no bit is corrupted or the decoder failed to detect any errors. In a cyclic code,

I. If s(x)= 0, one or more bits is corrupted.

1. If s(x) =0, either

   • No bit is corrupted. or
   • Some bits are corrupted, but the decoder failed to detect them.

   In our analysis we want to find the criteria that must be imposed on the generator, g(x) to detect the type of error we especially want to be detected. Let us first find the relationship among the sent codeword, error, received codeword, and the generator. We can say Received codeword =c(x) + e(x) In other words, the received codeword is the sum of the sent codeword and the error. The receiver divides the received codeword by g(x) to get the syndrome. We can write this as

$$\frac{Received codeword}{g(x)} = \frac{c(x)}{g(x)} + \frac{e(x)}{g(x)}$$

The first term at the right-hand side of the equality does not have a remainder (according to the definition of codeword). So the syndrome is actually the remainder of the second term on the right-hand side. If this term does not have a remainder (syndrome=0), either e(x) is 0 or e(x) is divisible by g(x). We do not have to worry about the first case (there is no error); the second case is very important. Those errors that are divisible by g(x) are not caught.

Burst Errors

Now let us extend our analysis to the burst error, which is the most important of all. A burst error is of the form e(x) = (xJ + ... + xi). Note the difference between a burst error and two isolated single-bit errors. The first can have two terms or more; the second can only have two terms. We can factor out xi and write the error as xi (xJ-i + ... + 1). If our generator can detect a single error (minimum condition for a generator), then it cannot divide xi. What we should worry about are those generators that divide xJ-i + ... + 1. In other words, the remainder of (xJ-i+ ... + 1)/(xr+ ... + 1) must not be zero. Note that the denominator is the generator polynomial. We can have three cases:

1. If j - i < r, the remainder can never be zero. We can write j - i =L - 1, where L is the length of the error. So L - 1 < r or L < r + 1 or L ≤ r. This means all burst errors with length smaller than or equal to the number of check bits r will be detected.

2. In some rare cases, if j - i = r, or L = r + 1, the syndrome is 0 and the error is undetected. It can be proved that in these cases, the probability of undetected burst error of length r + 1 is (l/2)r-1. For example, if our generator is x14+x3+1, in which r=14, a burst error of length L=15 can slip by undetected with the probability of (1/2)14-1 or almost 1 in 10,000.

3. In some rare cases, if j - i > r, or L > r + 1, the syndrome is 0 and the error is undetected. It can be proved that in these cases, the probability of undetected burst error of length greater than r + 1 is (1/2)r. For example, if our generator is x+ 1, in which r =14, a burst error of length greater than 15 can slip by undetected with the probability of (112)14 or almost 1 in 16,000 cases.

• All burst errors with L ≤ r will be detected.
• All burst errors with L =r + 1 will be detected with probability 1 - (1/2-1).
• All burst errors with L > r + 1 will be detected with probability 1-(1/2).

A good polynomial generator needs to have the following characteristics:

• It should have at least two terms.
• The coefficient of the term x0 should be 1.
• It should not divide Xl + 1, for t between 2 and n - 1.
• It should have the factor x + 1.

Advantages of Cyclic Codes

• Cyclic codes have a very good performance in detecting single-bit errors, double errors, an odd number of errors, and burst errors.
• They can easily be implemented in hardware and software. They are especially fast when implemented in hardware. This has made cyclic codes a good candidate for many networks.