The Simplest Error Detection Scheme Used In Data Comm 100887

The Simplest Error Detection Scheme Used In Data Communication Is Pari

The simplest error detection scheme used in data communication is parity-checking. Usually, messages sent consist of characters, each character consists of a number of bits (a bit is the smallest unit of information and is either 1 or 0). In parity-checking, a 1 or 0 is appended to the end of each character at the transmitter to make the total number of 1’s even. The receiver checks the number of 1’s in every character received, and if the result is odd it signals an error. Suppose that each bit is received correctly with probability 0.999, independently of other bits. What is the probability that a 7-bit character is received in error, but the error is not detected by the parity check?

Paper For Above instruction

Parity-checking is one of the most fundamental and straightforward error detection schemes used in data communication systems. Its simplicity makes it appealing, although it offers limited error detection capabilities. In this context, understanding the probability of undetected errors, particularly for small message sizes such as 7-bit characters, is essential for designing reliable communication systems.

At its core, parity-checking involves appending a single parity bit to a data sequence to ensure that the total number of 1’s in the sequence, including the parity bit, adheres to a predetermined even or odd parity rule. In the specific case of even parity used here, the parity bit is set to make the total number of 1’s in the data plus the parity bit even. Consequently, the receiver verifies the integrity of the received data by counting the number of 1’s. If it’s odd, an error is detected; if it’s even, the data is assumed to be error-free, although undetected errors may still exist.

Considering that each bit within the 7-bit character has a 0.999 probability of being received correctly and errors occurring independently, we examine the case where the character is actually received with errors that go unnoticed by the parity check. For an undetected error to occur, the number of erroneous bits must be even because an even number of errors does not change the overall parity, thus escaping detection.

The probability of an individual bit being received incorrectly is 1 - 0.999 = 0.001. Conversely, the probability that a bit is transmitted correctly is 0.999. For the 7-bit character, errors can occur in various patterns, but, due to the parity check, only errors in an even number of bits (0, 2, 4, or 6) will go undetected. Error patterns with zero errors are trivial and do not contribute to errors; these are the cases where all bits are correct. More interesting are cases where exactly 2, 4, or 6 bits are erroneous, since these errors affect the data but not the parity check.

Calculating the Probability of Undetected Errors

To calculate the probability of an undetected error, we sum the probabilities over all even-error patterns:

  • Probability of no errors (0 erroneous bits):

P(0 errors) = (0.999)^7

  • Probability of exactly 2 errors:

P(2 errors) = C(7,2) (0.001)^2 (0.999)^5

  • Probability of exactly 4 errors:

P(4 errors) = C(7,4) (0.001)^4 (0.999)^3

  • Probability of exactly 6 errors:

P(6 errors) = C(7,6) (0.001)^6 (0.999)^1

Combining these, the total probability of an undetected error (where errors occur in an even number of bits) is:

P(undetected error) = P(0 errors) + P(2 errors) + P(4 errors) + P(6 errors)

Calculations for each include the binomial coefficient C(n, k), which counts the ways to choose k erroneous bits out of n total bits:

C(n, k) = n! / (k! * (n - k)!)

Numerical Computation

Using the above formulas:

  • P(0 errors) = (0.999)^7 ≈ 0.99301
  • P(2 errors) = C(7,2) (0.001)^2 (0.999)^5 ≈ 21 1e-6 0.99501 ≈ 2.089 * 1e-5
  • P(4 errors) = C(7,4) (0.001)^4 (0.999)^3 ≈ 35 1e-12 0.997 ≈ 3.490 * 1e-11
  • P(6 errors) = C(7,6) (0.001)^6 (0.999)^1 ≈ 7 1e-18 0.999 ≈ 6.993 * 1e-18

Adding these probabilities gives an approximate probability of an undetected error:

P(undetected error) ≈ 0.99301 + 2.089 1e-5 + 3.490 1e-11 + 6.993 * 1e-18 ≈ 0.99303

This indicates that, even with highly reliable bits, the probability of an undetected error in a 7-bit character using parity-checking is around 0.7%. This is consistent with the known limitations of parity schemes, which can only detect errors in odd numbers of bits.

Implications and Limitations

The analysis highlights the limited efficacy of parity-checking for error detection in practical systems, particularly for small data units like 7 bits. While the probability of error detection is high, the non-zero chance of undetected errors poses risks for applications requiring high reliability. To mitigate this, more advanced error detection and correction techniques such as cyclic redundancy checks (CRC) or Hamming codes are often employed. These methods provide better error detection capabilities, especially for multiple-bit errors, which parity schemes tend to miss.

Overall, understanding these probabilities informs system designers of the limitations inherent in simple parity schemes, guiding decisions toward more robust error management strategies in digital communication systems.

References

  • Blahut, R. E. (2003). Theory and practice of error control codes. Cambridge University Press.
  • Lin, S., & Costello, D. J. (2004). Error control coding. Pearson Education.
  • Peterson, W. W., & Brown, D. T. (1961). Cyclic codes and their error detection properties. Proceedings of the IEEE, 49(1), 3-19.
  • Hamming, R. W. (1950). Error detecting and error correcting codes. Bell System Technical Journal, 29(2), 147-160.
  • Gallager, R. G. (1968). Information theory and reliable communication. John Wiley & Sons.
  • Mitra, P. P. (2009). Digital Signal Processing: A Computer-Based Approach. McGraw-Hill.
  • Wicker, S. B., & Bhargava, V. K. (1999). Reed-Solomon codes and their applications. IEEE Communications Magazine, 37(9), 62-70.
  • Wicker, S. B. (2011). Error Control Systems for Digital Communication and Storage. Prentice Hall.
  • Forney, G. D. (1966). Concatenated codes. MIT Press.
  • Meijer, H., & Brenner, S. (2010). Data communication and networking. Wiley.

Related Assignments