Error Detecting Codes

Error Detecting Codes Nguyen Quoc Dinh October 14, 2009 How do some error detection codes, namely, Horizontal and Vertical Party (HVP), and Cyclic Redundancy Check (CRC) work. Which factors make CRC is widely used than HVP.

1

Horizontal and Vertical Parity algorithm

The motivation of HVP algorithm comes from a single parity check bit. A single parity check bit is the bit that is insert in to the end of a frame that make this frame contains odd or even number of 1’s; this bit is called odd parity bit or even parity bit, respectively. Horizontal and Vertical Parity algorithm dose not insert only 1 but many bits. Let’s consider a MxN bits, we divide this frame into a matrix MxN, then plug-in a single parity check bit to each row and column as Fig. 1.

Figure 1: Horizontal and vertical parity bits

Receiver of this frame will check the parity bit of each single column and row, if satisfying the old or even rule, this frame, after reject the added parity bits, will be accepted as a desired frame.

Probability of undetected error Assume that each bit is independent, and gets its error probability error is q. 1

Figure 2: An undetected error case of HVP algorithm

This could be easy to find out that the Horizontal and Parity algorithm could accept a fault frame if those are the even errors that make rectangular configuration, as Fig. 2. Therefore, the probability of undetected error: f oor(N/2) f loor(M/2) 

p=

X

X

i=1

j=1

N 2i



 M 2i+2j q (1 − q)N −2i)(M −2j) , 2j

(1)

in which, N is the number of row and M is number of column, 2*i and 2*j is the total number of error bits on rows and columns respectively.

2

Cyclic Redundancy Check

Although the HVP scheme may sometimes be decent, in practice, polynomial code method is widely used, which is also known as CRC. This algorithm treats all bit streams as binary polynomials; for example, 101011 has 6 bits and thus represents a six-term polynomial x5 + x3 + x1 + x0 . We define: - M the original frame to be transmitted, before adding the Frame Check Sequence (FCS). It is k bits long. - F the resulting FCS. It is n bits long. - T the transmitted frame, the cascading of M and F. It is k + n bit long. - P the predefined CRC Polynomial. It is n+1 bits. When getting the original frame (M), transmitter produce the FCS F. Then F would be connected in series after the original frame M, makes T. The purpose of this process is that the FCS leads reminder of equals to 0 [1]. 2

T P

n

As [1], we get F = remainder( MPx ). Receiver, after obtain frame T, follows 2 processes of the CRC scheme to check if this frame would be accepted: 1. Divide it by P. 2. Check the reminder. If not zero then there is an error in the frame. As proved in [1], a polynomial code with n + 1 check bits will detect all burst errors of length ≤ n. In case the burst length > n, the CRC could or could not detect error depend on certain generator polynomial and kinds of error.

The most commonly used generator polynomials [2] CRC-12

1 + x + x2 + x3 + x11 + x12

CRC-16

1 + x2 + x15 + x16

CRC-CCITT

1 + x5 + x12 + x16

CRC-32

1 + x + x2 + x4 + x5 + x7 + x8 + x10 + x11 + x12 + x16 + x22 + x23 + x26 + x32

Example 1 Encode process, for transmitter. In this example we will consider the standard CRC-12, i.e. we use the polynomial G(x) = 1 + x + x2 + x3 + x11 + x12 for encoding. To encode the word 110110, we start by forming its corresponding polynomial M (x) = x + x2 + x4 + x5 . Since the degree of G(x) is n + 1 = 13, we have x12 M (x) = x12 (x + x2 + x4 + x5 ) = x13 + x14 + x16 + x17 . Dividing this polynomial by G(x), x12 M (x) = (x2 + x5 )G(x) + (x2 + x3 + x4 + x6 + x7 + x8 ), thus the remainder is F (x) = x2 + x3 + x4 + x6 + x7 + x8 . Finally we get T (x) = x12 M (x) + F (x) = x2 + x3 + x4 + x6 + x7 + x8 + x13 + x14 + x16 + x17 , which gives us the codeword 110110000111011100.

Example 2 Decode process, for receiver. Suppose that we are using CRC-12 and that the words 111001111010110101 and 100000001001010101 have been received. These words correspond to the polynomials M1 (x) = 1 + x + x2 + x5 + x6 + x7 + x8 + x10 + x12 + x13 + x15 + x17 and M2 (x) = 1 + x8 + x11 + x13 + x15 + x17 , respectively. Dividing by G(x) = 1+x+x2 +x3 +x11 +x12 yields M1 (x) = (x+x4 +x5 )G(x)+(1+x3 +x5 +x6 +x7 +x10 ) and M2 (x) = (1 + x + x4 + x5 )G(x). From this we see that M1 (x) is not divisible G(x), but M2 (x) is. Thus the first received word is not a codeword but the second one is.

3

Advantage of CRC The CRC method has its own advantages that make it is widely employed. The relationship between the bits and the polynomials provide us some mathematical leverage that will make it possible to prove facts about the sorts of errors. Therefore, error bound could be calculated. While the computation of parity bits through polynomial division may seem rather complicated, implement algorithm for computing CRC bits and/or verifying the correctness of the CRC associated with a received message is very simple [3].

References [1] Andrew S. Tanenbaum. Computer Networks. Prentice Hall, fourth edition, August 2002. [2] http://en.wikipedia.org/wiki/Cyclic_redundancy_check. [3] http://www3.rad.com/networks/1994/err_con/crc_how.htm.

4