Error Detection

Question 1

Two– dimensional parity: A simple error detection scheme

Answer 1

Even parity, odd parity and two–dimensional parity. Consider a 7–bit code, and a redundancy bit:
• Even parity- If the number of 1s in the code is odd, the redundant bit is set to 1 in order to make the total number of 1s in the byte an even number
• Odd parity- If the number of 1s in the code is even, the redundant bit is set to 0
• Two–dimensional parity- Apply these rules to each bit position across each of the bytes in the frame

Question 2

Checksum algorithms

Answer 2

Redundant bits are called checksum if the error detection algorithm is based on addition.
• Add all the transmitted data, where each word (=16 bits) is interpreted as an integer. The result is called the checksum.
• The receiver performs the same calculation on the received data and compares the result with the received checksum.
• If the two results are the same, the transmission is free of errors.

Internet checksum- made over a sequence of 16-bit integers using 1’s complement arithmetic -
Keep adding 16 bit numbers using 1’s complement. Negate the result and transmit as a final word. The sum of the entire block should be zero (all 1s)

1’s complement has the following rules-

1) To negate a number, invert every bit (so basically NOT)
2) To add two numbers perform normal addition, but if there’s a carry out add 1 to the result

Question 3

Cyclic redundancy check (CRC)

Answer 3

CRCs use the theory of polynomials. A message of length (n + 1) can be represented as a polynomial of degree n with coefficients of either 0 or 1.
CRC’s can catch all 1 or 2 bit errors, odd number bits of errors, and bursts (consecutive bits errors).

Question 4

Computing a CRC

Answer 4

1) Sender and receiver agree on a divisor polynomial C(x) of degree k.
2) Sender transmits a message of length (n+1) bits, plus k bits from C(x). Denote this extended message T(x). The divisor polynomial C(x) is chosen so that it is an exact divisor of T(x).
3) Receiver checks to determine if C(x) is a divisor of T(x) after transmission. If it is, it is assumed that an error has not occurred. Otherwise, a transmission error has occurred.

Question 5

CRC Algorithm

Answer 5

So we want to create a polynomial for transmission that is derived from the original message M(x), is k bits longer than M(x), and is exactly divisible by C(x)
Algorithm:
1) Multiply M(x) by x^k, that is, add k zeros to the end of the message. This the zero–extended message is T(x)
2) Divide T(x) by C(x) and calculate the remainder
3) Subtract the remainder from T(x) by performing an exclusive–OR (XOR) operation between T(x) and the remainder

Question 6

Divisor Polynomials

Answer 6

If we are transmitting a message P(x), the presence of errors changes it to P(x) + E(x) where E(x) represents the errors.

Question 7

How should the divisor polynomial C(x) be chosen?

Answer 7

Choose C (x) so that it is not a divisor of E(x) for the common types of error
Let C(x) be of degree k ≥ 1. Then
• If the coefficients of x^k and x^0 are non–zero, then all single bit errors can be
detected
• If C(x) has 3 or more terms, then all double bit errors can be detected
• A sequence of consecutive error bits can be detected if it is less than k bits long

Question 8

Advantages and disadvantages of error correction against error correction and detection

Answer 8

Error correction is mathematically more involved than error detection
Error correction requires substantially more redundancy than does error detection
Error correction does not require that corrupt frames be retransmitted