Error detecting capability

Question

Let f(x) = x + 1 and let g(x) = x^3 + x^2 + 1. Information bits 11 0111

a. What is the error detecting capability of g(x)? i.e. Can it detect errors of 1 bit?

b. The code word 1100101000 gets garbled to 1000101010 (2 bit error). Can g(x) detect this? Full explain.

Answer 1

a) m(x)=x^5+x^4+x^2+x+1  as 110111
g(x)= x^3 + x^2 + 1 as 1101

A single bit error e(x) = xi, where i is the position of bit. If a single bit error is caught, then xi  is not divisible (means there is a remainder) by g(x).

g(x) = x^3 + x^2 + 1 and multiplying g(x) by any non-zero polynomial e(x) must produce at least two terms and the coefficient of x0 is not zero i.e. 1 then e(x) can not be divided by g(x) as given in the problem. Hence, it detect errors of 1 bit.

e.g.
Sent :         110111000  =  F(x)
Error:          000001000  =  E(x) = x3          
                                             ---------
Received:  110110000   =  F(x) + E(x)    (Error in bit 3)

b) The problem mentioned above is an example of two isolated single. This type of error as e(x) = xj + xi. The value of I an j defines the position of the errors, and the difference j-I defines the distance between the two errors. We can write e(x) = xi (x j-I + 1). If g(x) has more than one term and one term is x0, it cannot divide xi. So, if g(x) is to divide e(x), it must divide x j-I + 1. In other word g(x) must not divide x j-I + 1.

In the above example g(x) = x^3 + x^2 + 1 can not divide x8-2 +1 = x6+1 . But it can not detect two errors that are four position apart. Means two errors can be anywhere but if their distance is 4, they remain undetected.