The Simplest Error Detection Scheme Used In Data Communicati

The Simplest Error Detection Scheme Used In Data Communication Is P

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 simplest and most widely used error detection mechanisms in digital communication systems. Its fundamental principle relies on the parity bit, which is appended to each data character to ensure that the total number of 1's in the character, including the parity bit, is even (for even parity). This method effectively detects single-bit errors within a character, as any single error will flip the parity, signaling an error at the receiver. However, it has limitations, particularly in its inability to detect errors involving an even number of bits, such as two-bit errors within the same character.

This paper explores the probability that a 7-bit character is received in error, but the error goes undetected by the parity check, assuming each bit has a probability of 0.999 of being transmitted correctly and that errors occur independently across bits. The analysis begins by considering the probabilities of various error configurations within the character, proceeding to identify the specific conditions under which errors are undetected. The core focus is on understanding the likelihood of multiple-bit errors that preserve the parity, thus evading detection, and quantifying this probability within the framework of decreasing error rates.

In the communication system modeled here, each 7-bit character is transmitted with a parity bit to make the total number of 1's even. When an error occurs, it can affect any subset of bits, flipping their values from 0 to 1 or vice versa. The probability that a given bit is transmitted correctly is 0.999, while the probability of an error (bit flip) is 0.001. Since errors are independent, the probability that exactly k bits out of 7 are incorrectly received follows a binomial distribution with parameters n=7 and p=0.001:

P(error in exactly k bits) = C(7, k) (0.001)^k (0.999)^{7 - k}

For an error to go undetected by the parity check, the total number of erroneous bits must be even. This is because flipping an even number of bits from the original pattern results in the same parity (since each bit flip changes the parity count by 1, and an even number of flips restores the original parity), making the error indistinguishable from a correct message in terms of parity.

Therefore, the probability that a message is corrupted with an even number of errors (k=2, 4, or 6) but the parity check fails to detect it is the sum of the probabilities of these configurations:

  • Exactly 2 bits are in error
  • Exactly 4 bits are in error
  • Exactly 6 bits are in error

Calculating each term:

1. For k=2:

P(k=2) = C(7, 2) (0.001)^2 (0.999)^5 = 21 (1e-6) (0.99502) ≈ 21 1e-6 0.99502 ≈ 2.089e-5

2. For k=4:

P(k=4) = C(7, 4) (0.001)^4 (0.999)^3 = 35 (1e-12) (0.997} ≈ 35 1e-12 0.997 ≈ 3.4895e-11

3. For k=6:

P(k=6) = C(7, 6) (0.001)^6 (0.999)^1 = 7 (1e-18) 0.999 ≈ 7 1e-18 0.999 ≈ 6.993e-18

Adding these probabilities gives the total probability that a 7-bit message contains an even number of errors undetected by parity checking:

Total probability ≈ 2.089e-5 + 3.4895e-11 + 6.993e-18 ≈ 2.089e-5

Since the probabilities for 4 and 6 errors are negligible compared to 2 errors, the dominant term in the probability of undetected error is the two-bit error case. Hence, the probability that a 7-bit character is erroneously received but the parity check does not detect it is approximately 2.1 * 10-5. This small probability reflects the effectiveness of parity checks against single-bit errors but also highlights their weakness in failing to detect certain multiple-bit errors, especially near the error rate of the channel.

References

  • Cover, T. M., & Thomas, J. A. (2012). Elements of Information Theory. John Wiley & Sons.
  • Wicker, S. B., & Bhargava, V. K. (1994). Reed-Solomon Codes and Their Applications. IEEE Communications Magazine.
  • Lin, S., & Costello, D. J. (2004). Error Control Coding (2nd ed.). Pearson Academic Press.
  • Blahut, R. E. (2003). Algebraic Codes for Data Transmission. Cambridge University Press.
  • Proakis, J. G., & Salehi, M. (2008). Digital Communications. McGraw-Hill.
  • MacKay, D. J. C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press.
  • Carter, J. L., & Wegman, M. N. (1979). Universal Classes of Hash Functions. Journal of Computer and System Sciences.
  • Hamming, R. W. (1950). Error Detecting and Error Correcting Codes. Bell System Technical Journal.
  • Peterson, W. W., & Weldon, E. J. (1972). Error-Correcting Codes. MIT Press.
  • Lin, S., & Costello, D. J. (1983). Error Control Coding: Fundamentals and Applications. Prentice-Hall.

Related Assignments