Today our class is on error control and the parity checks. Digital transmission systems introduce errors with different per bit error probability. Applications require certain reliability level. Error control is used when transmission system doesn't meet application requirement, that ensures a data stream is transmitted to a certain level of accuracy despite errors. There are two basic error control approaches. The first one is error detection that comes with retransmission. The other is error correction that doesn't require retransmission. We focus on error detection. For error detection, one important term is called a codeword. An n-bit codeword is indeed a frame of m-bit data plus k-bit redundant check bits. The basic idea of error detection is simple. The information produced by an application is encoded, so that as a codeword that is input to the communication channel, satisfies a specific pattern. The receiver checks the code of word coming out of the channel to see whether the pattern is satisfied. If it is not, the receiver can be certain that an error has occurred, and therefore sets an alarm to the user. One question you may ask is, is there a blind spot? A quick answer is yes, when the communication channels transforms and input a codeword into another valid output codeword. The simplest code is the single parity check code that takes k information bits and appends a single check bit to form a codeword. The parity check bit ensures that the total numbers of 1s in the codeword is even, that is, the codeword has even parity. The parity bit is calculated by modulo 2 arithmetic. Receiver checks to see if the number of 1s is even in its received codeword. One can tell that this coding scheme can have blind spots or error patterns that change an odd number of bits are detectable. But all even numbered patterns are undetectable. This technique is used in ask 2 code where characters are represented by 7 bits and the 8th bit is the parity bit. Let's see an example. The information frame has 7 bits 0, 1, 0, 1, 1, 0, 0. The parity check bit is calculated as one. If a single bit error in bit of 3 occurs, the error is detected. But if there are 2 error bits, the error is not detected. Single parity check code adds 1 redundant bit per m information bits. So the overhead is just 1/(m + 1). Suppose we transmit a codeword that has n bits. A clear vector, e1, e2, through en is defined where e = 1 if an error occurs in the i transmitted bit and e = 0 otherwise. Many transmission channels introduce bit errors at random. Let p be the probability of an error in a single bit transmission. That's, the probability of a bit with error in transmission is 1- p. In our n-bit codeword, the probability of 1-bit error is to choose 1 out of n, multiplies by p, multiplies 1- p plus n- 1. Because 1-bit error was probability of P. And each of the other n-1 correct bits occurs with probability 1-p. The probability of an error vector that has j bit errors is to choose j out of n multiples by p+j, multiplies by 1-p plus n-j. Note that some error patterns are more probable than others. For example, in an 8-bit codeword, the probability of the first bit error is p multiplies 1 minus p plus 7. In a 8-bit codeword, the probability of the first two bits in error is p plus 2 multiplies 1 minus p power 6. In a worthwhile channel, p must be less than 0.5. Therefore, p over 1 minus p is less than 1. It follows that patterns with 1-bit error are more likely than patterns with 2-bit errors and so forth. The undetectable error by single parity check occurs if there are even number of bit errors. For a n-bit codeword, the probability of any 2 bit error is choose any 2 out of n, multiplies by p powers 2, multiplies by (1-p) powers n-2. There are case of n=32, the probability p = 10 powers -3. Roughly only 1 out of 2,000 error patterns is undetectable by single parity. But is it possible to dictate more errors if we add more check bits? A simple method to improving error detection capability of a single parity check, is to arrange columns that consist of k information bits followed up by a check bit at the bottom of each column. The right most bit in each row is the check bit of other bits in the row. So in fact as a last column is the parity column. The result encoded a matrix of bits satisfies the pattern that all rows have even parity and all columns have even parity. For one or two errors occur anywhere in the matrix of bit scale in transmission. And at least one row or one parity check will fail, an error is detected. If three errors occur anywhere in the matrix, at least one row or one parity check will fail and errors detected. But some virus are undetectable. As a summary, single parity bit code used in ASCII. Its overhead is low, but able to detect any odd number of errors, including the most popular 1-bit errors. Two dimensional parity check codes was used in old systems, it was able to detect 1, 2 and 3 bit errors, but it's overhead is high,
