2. Open-ended quiz

Checking criteria: (1) application of the course materials discussed after midterm, (2) concreteness, (3) originality, (4) [no] jumps in the protocol procedure, (5) possibility of performance calculation of the designed scheme, (6) meeting the design requirements

 

Q. Suppose a communication channel induces the following type of errors. Once an error occurs at a bit position, the next bit will also suffer an error with probability 0.9. On the other hand, if a bit does not have an error, the next bit is also clean with probability 0.9. Design your CRC tailored for a communication mechanism using this channel. Mathematically analyze your proposed CRC mechanism in terms of its error detecting capability. 

 

 

A. Data word : d(x), Codeword : c(x), Generator : g(x), Syndrome : s(x), Error : e(x). It is about having a high probability of error detection. Therefore, it is necessary to first analyze e(x) occurring in the channel presented in the problem. While learning standard CRC, we learned how to mathematically verify g(x) suitable for single bit error, two isolated single bit error, odd number of error, and brust error.

The error of the current channel should increase the detection probability for the Brust error among the above 4 errors. When E(x) = x ^ i (x ^ (j - i) +  … + 1), the condition of g(x) is x ^ (j - i) + … while handling single bit errors well. + 1 is not divided. Now consider the following three cases.

 

• If j - i < r, the remainder can never be zero. Any brust errors shorter than the acknowledgment bit r are detected.
• If j - i = r, syndrome = 0 and no error is detected. In this case, the probability of an undetected burst error of length r+1 will be calculated later.
• If j - i > r, syndrome = 0 and no error is detected. In this case too, we will calculate the probability that a burst error with a length greater than r+1 will not be detected.

 

Also in general a good generator is

• It has the above clauses.
• The coefficient of x^0 is 1.
• Do not divide by x^t+1 for t values ​​between 2 and n-1.
• It has (x+1) as a factor.

, which also satisfies g(x) will be designed.

 

The following result is the calculation of the probability of an error occurring up to the 32-n bit when an error occurs in the 32nd bit. (That is, the probability that a burst error of length 32-n occurs) If you look at the probability, you can see that the burst error occurs with a very high probability. This supports the validity of this solution focusing on the burst error.

 

Similar to CRC-32, we can devise g(x) = x^32+ x^31+x^24+x^23+x^16+x^12+x^9+x^5+x+1 have. Of course, a smaller size g(x) such as CRC-8 and CRC-16 can also be used, but in that case, the probability of 2 or 3 increases slightly. Also, since CRC is a HW scheme rather than a SW scheme, there is only a difference in cost even if the size is increased, so it is desirable to select g(x) of a rather large size.

 

The probability of 2 and 3 was calculated in the textbook of this lecture. Based on this, it can be thought that the probability will be reduced than (1/2)^30 in the next channel where the probability is specifically determined. Because the probability calculated in the textbook was calculated as 1/2 the probability that each bit had an error. The current situation can be seen from the above photo, but as the error size increases, it becomes closer to 1/2. Considering the arithmetic mean inequality, we can at least guarantee that the probability is less than the probability calculated in the book ( ex)4/2*2/4 = 4 / 16 > 1/4*3/4 = 3/16) Therefore, cases 2 and 3 are very rare cases.