While the use of a single parity bit allows detection of single bit errors, a second error will go undetected, as will any even number of bit errors. Unless the probability of a error is very low and a message is very short (the case when a parity bit is added to a 7-bit ASCII character) the chances of some error event going undetected may be high. In contrast, by using many extra bits the CRC can potentially detect multiple bit errors.
The exact number of extra bits and their makeup depends on a generating polynomial. For example, one such polynomial is:
The number of CRC bits corresponds to the degree of the generating polynomial. The above polynomial of degree 16 generates a 16-bit CRC. Typically, the CRC bits are used for error detection only.
In this example, let M(x) represent the binary message 110010, and let P(x) = x3 + x2 + 1 = (1101).
The polynomial P(x) will be used to generate three check bits called CRC(x) which will be appended to M(x). Note that this P(x) is prime.
The check bits will be chosen such that the entire message+crc will be an exact multiple of P(x). The steps to achieving this goal are shown below.
Step 1 - Multiply the message M(x) by x3, where 3 is the number of bits in the CRC as given by the degree of P(x).
Add 3 three zeros to the binary M(x).
Step 2 - Divide the product M(x) x3 by the generating polynomial P(x).
We wish to find "the remainder, modulo P(x)"
Compute the following:
100100 (ignore this quotient) ------------ 1101 ) 110010000 1101 ---- 1100 1101 ---- 100 = remainder = R(x)Observe that if R(x) were in place of the appended zeros, the remainder would become 000.
Let CRC(x) = R(x).
Check the math with the online polynomial calculator.
Q: What can be done to make x divisible by y?
A: If 41 ≡ 2 mod 13, then (41-2) ≡ 0 mod 13.
In general, if the division x/y gives remainder z, then (x-z)/y gives remainder zero.
Step 3 - Add the remainder CRC(x) to the product M(x) x3 to give the code message polynomial C(x):
Put the remainder CRC(x)=100 in place of the three zeros added in Step 1.
The transmission C(x) = (110010100) is now an exact multiple of P(x) = (1101); division C(x)/P(x) gives zero remainder, or C(x) ≡ 0 mod P(x). Upon reception, it is expected that an errored message will no longer be a multiple of P(x).
>> Hgen = comm.CRCGenerator([1 1 0 1]); % specify polynomial as [1 1 0 1] or [3 2 0] >> M = [1 1 0 0 1 0]; % M(x) = message bits >> C = step(Hgen, M'); % supply message bits as a column vector >> disp( C' ); % C(x) = codeword returned as column vector 1 1 0 0 1 0 1 0 0The output C(x) includes three CRC bits appended (highlighted). This codeword may now be transmitted.
Upon reception, an entire received codeword R(x) = "message + crc" can be checked simply by dividing R(x)/P(x) using the same generating polynomial. If the remainder after division equals zero, then no error was found.
100100 (ignore this quotient) ------------ 1101 ) 110010100 1101 ---- 1101 1101 ---- 000 = remainder (no error)
Check the math with the online polynomial calculator.
>> Hdet = comm.CRCDetector([1 1 0 1]); % specify polynomial as [1 1 0 1] or [3 2 0] >> R = C; % R(x) = received data = the (unerrored) codeword >> [data,error] = step(Hdet, R ); % check the received data R(x) with no error >> disp( error ); 0The zero result indicates no error was found. A result equal to 1 would indicate a detected error.
A single bit error in bit position K in a message C(x) can be represented by adding the term E(x) = xK, (binary 1 followed by K-zeros).
sent: 110010100 = C(x) error: 000001000 = E(x) = x3 --------- received: 110011100 = C(x) + E(x) (error in bit 3) |
The above error is detected when the CRC division gives a non-zero remainder:
100101 (ignore this quotient) ------------ 1101 ) 110011100 = C(x) + E(x) 1101 ---- 1111 1101 ---- 1000 1101 ---- 101 = remainder (error!)
Check the math with the online polynomial calculator.
C(x) + E(x) C(x) E(x) E(x) ----------- = ----- + ----- = ----- P(x) P(x) P(x) P(x) |
The remainder is a function only of the errored bits E(x). |
It follows that the error control performance can be fully explored by examining only the possible errors E(x) independently of any message bits.
For example, the above result is the same if only the error E(x) is checked using P(x):
1 (ignore this quotient) ------------ 1101 ) 000001000 = E(x) alone 1101 ---- 101 = remainder (error!)
Check the math with the online polynomial calculator.
The general performance of the CRC for all possible single bit errors E(x) may now be stated. Since E(x) = xK has no factors other than x, a single bit error will never produce a term exactly divisible by P(x). All single bit errors will be detected.
If E(x) = xK + xK+1, the error pattern includes two adjacent bits (e.g. E(x) = (000011000) for K=3).
Since this E(x) has no factors other than (x+1) and x, any adjacent bit errors will never produce a term exactly divisible by P(x). All double bit (adjacent-bit) errors will be detected
Two Bit Errors
The general two-bit error E(x)=xN+xM is not detected if E(x) is a multiple of P(x). In particular, the E(x)=(10000001) having two bad bits 7-bits apart would not be detected for P(x) = (1101) because (10000001)=(11)(1011)(1101). (Check the math)
The allowable separation between two bad bits is related to the choice of P(x) and will be maximum for a primitive P(x). For example, the degree 4 irreducible P(x)=(11111) is not primitive and the two bit error E(x)=(100001) would not be detected since E(x)=(100001)=(11)(11111) is an exact multiple of P(x). By instead choosing the primitive P(x)=(11001) of the same degree, all two bit errors up to E(x) = x15 + 1 = (1000000000000001) will be detected.
>> Hdet = comm.CRCDetector([1 1 0 1]); % specify polynomial P(x) as [1 1 0 1] or [3 2 0] >> E = [ 1 0 0 0 0 0 0 1 ]; % This E(x) will be undetected for this P(x) >> [data,error] = step(Hdet, E'); % Check the error pattern E(x) alone. >> disp( error ); 0The two bit error E(x) = (1 0 0 0 0 0 0 1) was not detected. Any error E(x) that is a multiple of P(x) would not be detected.
In general, bit errors and bursts up to N-bits long will be detected for a P(x) of degree N. For arbitrary bit errors longer than N-bits, the odds are one in 2N than a totally false bit pattern will nonetheless lead to a zero remainder.
In essence, 100% detection is assured for all errors E(x) not an exact multiple of P(x). For a 16-bit CRC using a primitive P(x) this means:
Ultimately, the CRC bits are expected to ensure a minimum Hamming distance between all possible transmitted codewords; consequently, the error detection performance of a given P(x) depends on the codeword length. Given a known codeword size and a sufficently large Hamming distance, error correction is also possible.