Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > Let G(x) be the generator polynomial used for...
Start Learning for Free
Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?
- a)G(x) contains more than two terms
- b)G(x) does not divide 1+x k , for any k not exceeding the frame length
- c)1+x is a factor of G(x)
- d)G(x) has an odd number of terms.
Correct answer is option 'C'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
Let G(x) be the generator polynomial used for CRC checking. What is th...
Let me first explain building blocks to this problem. Before answering this, we should know the relationship between Sent
codeword, Received codeword, CRC generator and error polynomial.
let's take an example:
Sent codeword = 10010 (=x4+x)
Received codeword = 10110 (error at 2nd bit ) (=x4+x2+x)
GATE Overflow September 2017 161 of 740
codeword, Received codeword, CRC generator and error polynomial.
let's take an example:
Sent codeword = 10010 (=x4+x)
Received codeword = 10110 (error at 2nd bit ) (=x4+x2+x)
GATE Overflow September 2017 161 of 740
Now, i can write Sent codeword = Received codeword + error (10010 = 10110 + 00100, here we do modulo 2
arithmetic i.e 1+1 =0 without carry )
in polynomial also we can see x4+x = x4+x2+x+x2 = x4+2x2+x = x4+x (here multiplier with 2 means 0 bcoz it
coressopnds to binary modulo 2 arithmetic which is 1+1 = 0 (not 2) )
arithmetic i.e 1+1 =0 without carry )
in polynomial also we can see x4+x = x4+x2+x+x2 = x4+2x2+x = x4+x (here multiplier with 2 means 0 bcoz it
coressopnds to binary modulo 2 arithmetic which is 1+1 = 0 (not 2) )
or
We can also write Received codeword = Sent codeword + error (Check it using same mrthod as above)
Sent codeword C(x), Received codeword R(x) and error E(x).
Now we have R(x) = C(x) + E(x). and let CRC polynomial be G(x). G(x) always divides C(x), and if there is an error then
G(x) should not divide R(x). Lets check -
R(x) mod G(x) =(C(x) + E(x)) mod G(x) (for simplicity i am writing mod as division )
Sent codeword C(x), Received codeword R(x) and error E(x).
Now we have R(x) = C(x) + E(x). and let CRC polynomial be G(x). G(x) always divides C(x), and if there is an error then
G(x) should not divide R(x). Lets check -
R(x) mod G(x) =(C(x) + E(x)) mod G(x) (for simplicity i am writing mod as division )
If G(x) divides E(x) also this would mean G(x) divides R(x). We know that, If G(x) does not properly divide R(x) then there
is an error but we are never sure if there is error or not when G(x) divides R(X).
As we saw, G(x) divides R(x) or not totally depends on G(x) divides E(x) or not. whole strength of G(x) lies if it does not
divide any possible E(x).
Lets see again E(x). if there is an error in 3rd and 4th bit from left (LSb is 0th bit ) then E(X) = x4+x3.( it does not matter
error is from toggling 1 to 0 or 0 to 1) Check with above example.
Now come to question. it says G(x) should detect odd number of bits in error?. If number of bits are odd then terms in E(x)
would be odd.
for instance if 1st, 2nd and 5th bit got corrupted then E(x) = x5+x2+x.
It is clear that if any function f(x) has a factor of x-k, then at x=k, f(x) would be zero. I.e.f(x) = 0 at x=k.
is an error but we are never sure if there is error or not when G(x) divides R(X).
As we saw, G(x) divides R(x) or not totally depends on G(x) divides E(x) or not. whole strength of G(x) lies if it does not
divide any possible E(x).
Lets see again E(x). if there is an error in 3rd and 4th bit from left (LSb is 0th bit ) then E(X) = x4+x3.( it does not matter
error is from toggling 1 to 0 or 0 to 1) Check with above example.
Now come to question. it says G(x) should detect odd number of bits in error?. If number of bits are odd then terms in E(x)
would be odd.
for instance if 1st, 2nd and 5th bit got corrupted then E(x) = x5+x2+x.
It is clear that if any function f(x) has a factor of x-k, then at x=k, f(x) would be zero. I.e.f(x) = 0 at x=k.
- We want to detect odd number of bits that means received message R(x) contains an odd number of inverted bits, then
E(x) must contain an odd number of terms with coefficients equal to 1.
- As a result, E(1) must equal to 1 (remeber 1+1 = 0, 1+1+1 = 1. Any Odd number of times sum of one's is = 1). E(1) is not zero, this means x+1 is not a factor of E(x).
- Now I want G(x) not to be a factor of E(x), So that G(x) wont divide E(x) and i would happily detect odd number of bits.
- So, if we make sure that G(1) = 0, we can conclude that G(x) does not divide any E(x) corresponding to an odd number of error bits. In this case, a CRC based on G(x) will detect any odd number of errors.
- As long as 1+x is a factor of G(x), G(x) can never divide E(x). Because we know E(x) dont have factor of 1+x .
Option C.
Most Upvoted Answer
Let G(x) be the generator polynomial used for CRC checking. What is th...
Condition for G(x) to detect odd number of bits in error
To detect an odd number of bits in error, the generator polynomial G(x) should satisfy a specific condition. Let's examine each option to understand why option 'C' is the correct answer.
a) G(x) contains more than two terms:
The number of terms in the generator polynomial does not have any direct relation to the ability to detect an odd number of bits in error. The number of terms can vary based on the desired error-detection capabilities and the specific polynomial chosen.
b) G(x) does not divide 1 x k, for any k not exceeding the frame length:
If the generator polynomial G(x) divides 1 x k, it means that the polynomial G(x) has a factor of 1 x. In other words, the polynomial G(x) has a root at x = 0. This condition is not desirable for error detection because it would make the error-detection mechanism ineffective. Therefore, this option does not hold true.
c) 1 x is a factor of G(x):
For G(x) to detect an odd number of bits in error, the generator polynomial should not have 1 x as a factor. If 1 x is a factor of G(x), it means that G(x) has a root at x = 0. In this case, when an odd number of bits are in error, the received polynomial will also have a root at x = 0. Consequently, the received polynomial will be divisible by G(x), leading to a false negative result. Therefore, G(x) should not have 1 x as a factor to detect an odd number of bits in error.
d) G(x) has an odd number of terms:
The number of terms in G(x) does not directly impact the ability to detect an odd number of bits in error. The number of terms can be even or odd, and it does not affect the error-detection capabilities.
Conclusion:
Among the given options, the condition that should be satisfied by G(x) to detect an odd number of bits in error is that G(x) should not have 1 x as a factor. Therefore, the correct answer is option 'C'.
To detect an odd number of bits in error, the generator polynomial G(x) should satisfy a specific condition. Let's examine each option to understand why option 'C' is the correct answer.
a) G(x) contains more than two terms:
The number of terms in the generator polynomial does not have any direct relation to the ability to detect an odd number of bits in error. The number of terms can vary based on the desired error-detection capabilities and the specific polynomial chosen.
b) G(x) does not divide 1 x k, for any k not exceeding the frame length:
If the generator polynomial G(x) divides 1 x k, it means that the polynomial G(x) has a factor of 1 x. In other words, the polynomial G(x) has a root at x = 0. This condition is not desirable for error detection because it would make the error-detection mechanism ineffective. Therefore, this option does not hold true.
c) 1 x is a factor of G(x):
For G(x) to detect an odd number of bits in error, the generator polynomial should not have 1 x as a factor. If 1 x is a factor of G(x), it means that G(x) has a root at x = 0. In this case, when an odd number of bits are in error, the received polynomial will also have a root at x = 0. Consequently, the received polynomial will be divisible by G(x), leading to a false negative result. Therefore, G(x) should not have 1 x as a factor to detect an odd number of bits in error.
d) G(x) has an odd number of terms:
The number of terms in G(x) does not directly impact the ability to detect an odd number of bits in error. The number of terms can be even or odd, and it does not affect the error-detection capabilities.
Conclusion:
Among the given options, the condition that should be satisfied by G(x) to detect an odd number of bits in error is that G(x) should not have 1 x as a factor. Therefore, the correct answer is option 'C'.
Attention Computer Science Engineering (CSE) Students!
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Similar Computer Science Engineering (CSE) Doubts
Top Courses for Computer Science Engineering (CSE)View all
Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?a)G(x) contains more than two termsb)G(x) does not divide 1+x k , for any k not exceeding the frame lengthc)1+x is a factor ofG(x)d)G(x) has an odd number of terms.Correct answer is option 'C'. Can you explain this answer?
Question Description
Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?a)G(x) contains more than two termsb)G(x) does not divide 1+x k , for any k not exceeding the frame lengthc)1+x is a factor ofG(x)d)G(x) has an odd number of terms.Correct answer is option 'C'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?a)G(x) contains more than two termsb)G(x) does not divide 1+x k , for any k not exceeding the frame lengthc)1+x is a factor ofG(x)d)G(x) has an odd number of terms.Correct answer is option 'C'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?a)G(x) contains more than two termsb)G(x) does not divide 1+x k , for any k not exceeding the frame lengthc)1+x is a factor ofG(x)d)G(x) has an odd number of terms.Correct answer is option 'C'. Can you explain this answer?.
Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?a)G(x) contains more than two termsb)G(x) does not divide 1+x k , for any k not exceeding the frame lengthc)1+x is a factor ofG(x)d)G(x) has an odd number of terms.Correct answer is option 'C'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?a)G(x) contains more than two termsb)G(x) does not divide 1+x k , for any k not exceeding the frame lengthc)1+x is a factor ofG(x)d)G(x) has an odd number of terms.Correct answer is option 'C'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?a)G(x) contains more than two termsb)G(x) does not divide 1+x k , for any k not exceeding the frame lengthc)1+x is a factor ofG(x)d)G(x) has an odd number of terms.Correct answer is option 'C'. Can you explain this answer?.
Solutions for Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?a)G(x) contains more than two termsb)G(x) does not divide 1+x k , for any k not exceeding the frame lengthc)1+x is a factor ofG(x)d)G(x) has an odd number of terms.Correct answer is option 'C'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE).
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?a)G(x) contains more than two termsb)G(x) does not divide 1+x k , for any k not exceeding the frame lengthc)1+x is a factor ofG(x)d)G(x) has an odd number of terms.Correct answer is option 'C'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?a)G(x) contains more than two termsb)G(x) does not divide 1+x k , for any k not exceeding the frame lengthc)1+x is a factor ofG(x)d)G(x) has an odd number of terms.Correct answer is option 'C'. Can you explain this answer?, a detailed solution for Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?a)G(x) contains more than two termsb)G(x) does not divide 1+x k , for any k not exceeding the frame lengthc)1+x is a factor ofG(x)d)G(x) has an odd number of terms.Correct answer is option 'C'. Can you explain this answer? has been provided alongside types of Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?a)G(x) contains more than two termsb)G(x) does not divide 1+x k , for any k not exceeding the frame lengthc)1+x is a factor ofG(x)d)G(x) has an odd number of terms.Correct answer is option 'C'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?a)G(x) contains more than two termsb)G(x) does not divide 1+x k , for any k not exceeding the frame lengthc)1+x is a factor ofG(x)d)G(x) has an odd number of terms.Correct answer is option 'C'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Suggested Free Tests
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup