Cyclic Redundancy Checks(CRC)

Subscribe Send me a message home page


This post is a reading note of post.

Cyclic Redundency Check is a parity bit based error detection scheme. It is based on polynomial division and arithmetics over the field of integers mod 2.

The idea is to considere the transmitted message as a polynomial and use a generator polynomial \(G(x)\) to create redundant bits. Suppose we want to transmit a message \(b_nb_{n-1}...b_1b_0\), we can considere this message to represent a \(n\) degree polynomial. $$B(x) = \sum^{n}_{i=0} b_{i}x^i$$ Now multiply \(B(x)\) by \(x^k\), where \(k\) is the degree of the generator polynomial \(G(x)\) and we get $$x^kB(x) = Q(x)G(x) + R(x)$$ We then append the coefficients of \(R(x)\) to the end of the message. This message(e.g. \(b_nb_{n-1}...b_1b_0r_{k-1}r_{k-2}...r_0\)) is the actual message we will transmit. Note that this "append" operation consists of two sub-operations: (1) shift the original mesasge to left k times and (2) add the coefficients of \(R(x)\). Translating it to polynomial representation, we get $$x^kB(x) + R(x) = (Q(x)G(x) + R(x)) + R(x) = Q(x)G(x) + 2R(x) = Q(x)G(x)$$

The term \(2R(x)\) disappears becasue all of its coefficients are even numbers, which is zero in the field of integers mod 2.

The receiver of the message can check if the polynomial representation of the received message can be divided by \(G(x)\). If it cannot be divided by \(G(x)\), it means some of the bits are damaged during the transmission.

Now the question is what we can infer if the received message can be divided by \(G(x)\). Of course, it depends on \(G(x)\). In the post, the author discussed the following two use cases.
Case 1: Compare CRC to single bit parity check.
\(G(x)\) should be constructed in such a way that it makes CRC have at least the same performance as the single bit parity check, which can detect the error if an odd number of bits are inverted during the transmission of the message. Let denote \(E(x)\) the error polynomial, therefore we have $$E(x) = T'(x) - T(X)$$ where \(T'(x)\) is the received message and \(T(x)\) is the expected message. When there is an odd number of bits are inverted, \(E(x)\) has an odd number of non-zero coefficients. It follows that \(E(1) = 1\). For \(E(x)\) is assumed to be divided by \(G(x)\), we can write \(E(x) = A(x)G(x)\) and we conclude \(G(1) = 1\) if we want CRC to be as good as single bit parity check.

If we choose \(G(x) = x + 1\), CRC becomes the single bit parity check. The order of \(G(x)\) in this case is 1 therefore we can only append one single bit to the original message.
Case 2: less than k consecutive damaged bits
Assuming there are less than k consecutive damaged bits in the transmitted message, we can write $$E(x) = x^{n_1} + x^{n_2} + ... + x^{n_j}$$ where \(n_1 - n_j < k\). Rewriting the expression, we have $$E(x) = x^{n_j}(x^{n_1 - n_j} + x^{n_2 - n_j} + ... + 1)$$ If we choose \(G(x) = x^k + 1\), we can prove \(G(x)\) cannot divide \(E(x)\). It cannot devide \(x^{n_j}\) because \(G(0) = 1\). It cannot divide \(x^{n_1 - n_j} + x^{n_2 - n_j} + ... + 1\) because it has higher degree. Therefore if we choose \(G(x) = x^k + 1\), messages that have less than k consecutive damaged bits during the transmission will be detected(becuase when this happens, the received message will not be divided by \(G(x)\)).

----- END -----

Send me a message Subscribe to blog updates

Want some fun stuff?

/static/shopping_demo.png


Comments