Lecture Wireless and mobile computing – Chapter 24: Coding and error control (Review/Recap). The following will be discussed in this chapter: Parity, cyclic redundancy check (CRC) CRC for more than a bit error, CRC algorithms, ECC, block ECC, convolutional code. | Coding and Error Control Review/Recap Lecture 24 Overview Parity Cyclic Redundancy Check (CRC) CRC for More than a Bit Error CRC Algorithms ECC Block ECC Convolutional Code Parity Bit Q:- What is a parity bit? Error Detection Detection methods Error Detection(cont’d) Parity Check A parity bit is added to every data unit so that the total number of 1s(including the parity bit) becomes even for even-parity check or odd for odd-parity check Simple parity check Parity Codes Known as a single error detecting code (SED). Only useful if probability of getting 2 errors is small since parity will become correct again Used in serial communications Low overhead but not very powerful Decoder can be implemented efficiently using a tree of XOR gates Parity Codes Example of a simple block code – Single Parity Check Code In this case, n = k+1, ., the codeword is the dataword with one additional bit For ‘even’ parity the additional bit is, For ‘odd’ parity the additional bit is 1-q That is, the additional bit ensures that there are an ‘even’ or ‘odd’ number of ‘1’s in the codeword Parity Codes – Example 1 Even parity (i) d=(10110) so, c=(101101) d=(11011) so, c=(110110) Parity Codes – Example 2 Coding table for (4,3) even parity code Dataword Codeword Parity Codes To decode Calculate sum of received bits in block (mod 2) If sum is 0 (1) for even (odd) parity then the dataword is the first k bits of the received codeword Otherwise error Code can detect single errors But cannot correct error since the error could be in any bit For example, if the received dataword is (100000) the transmitted dataword could have been (000000) or (110000) with the error being in the first or second place respectively Note error could also lie in other positions including the parity bit Parity Checks Simple parity If performing even parity, add a parity bit such that an even number of 1s are maintained If performing odd parity, add a parity bit such that an odd number of 1s are . | Coding and Error Control Review/Recap Lecture 24 Overview Parity Cyclic Redundancy Check (CRC) CRC for More than a Bit Error CRC Algorithms ECC Block ECC Convolutional Code Parity Bit Q:- What is a parity bit? Error Detection Detection methods Error Detection(cont’d) Parity Check A parity bit is added to every data unit so that the total number of 1s(including the parity bit) becomes even for even-parity check or odd for odd-parity check Simple parity check Parity Codes Known as a single error detecting code (SED). Only useful if probability of getting 2 errors is small since parity will become correct again Used in serial communications Low overhead but not very powerful Decoder can be implemented efficiently using a tree of XOR gates Parity Codes Example of a simple block code – Single Parity Check Code In this case, n = k+1, ., the codeword is the dataword with one additional bit For ‘even’ parity the additional bit is, For ‘odd’ parity the additional bit is 1-q That
