Coding and Error Control Review/Recap - Lecture 24

Coding and Error ControlReview/RecapLecture 24OverviewParityCyclic Redundancy Check (CRC)CRC for More than a Bit ErrorCRC AlgorithmsECCBlock ECCConvolutional Code2Parity BitQ:- What is a parity bit?3Error DetectionDetection methodsError Detection(cont’d) Parity CheckA 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 checkParity CodesKnown as a single error detecting code (SED). Only useful if probability of getting 2 errors is small since parity will become correct againUsed in serial communicationsLow overhead but not very powerfulDecoder can be implemented efficiently using a tree of XOR gates7Parity CodesExample of a simple block code – Single Parity Check CodeIn this case, n = k+1, i.e., the codeword is the dataword with one additional bitFor ‘even’ parity the additional bit is,For ‘odd’ parity the additional bit is 1-qThat is, the additional bit ensures that there are an ‘even’ or ‘odd’ number of ‘1’s in the codewordParity Codes – Example 1Even parity(i) d=(10110) so, c=(101101)d=(11011) so, c=(110110)Parity Codes – Example 2Coding table for (4,3) even parity codeDatawordCodewordParity CodesTo decodeCalculate 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 codewordOtherwise errorCode can detect single errorsBut cannot correct error since the error could be in any bitFor 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 respectivelyNote error could also lie in other positions including the parity bit12Parity ChecksSimple parityIf performing even parity, add a parity bit such that an even number of 1s are maintainedIf performing odd parity, add a parity bit such that an odd number of 1s are maintainedFor example, send 1001010 using even parityFor example, send 1001011 using even parityParity Checks (continued)Simple parity (continued)What happens if the character 10010101 is sent and the first two 0s accidentally become two 1s?Thus, the following character is received: 11110101Will there be a parity error?Problem: Simple parity only detects odd numbers of bits in errorParity Checks (continued)Longitudinal parity Adds a parity bit to each character then adds a row of parity bits after a block of charactersThe row of parity bits is actually a parity bit for each “column” of charactersThe row of parity bits plus the column parity bits add a great amount of redundancy to a block of charactersParity Checks (continued)Parity Checks (continued)Parity Checks (continued)Both simple parity and longitudinal parity do not catch all errorsSimple parity only catches odd numbers of bit errorsLongitudinal parity is better at catching errors but requires too many check bits added to a block of dataWe need a better error detection method What about arithmetic checksum?19Detection -examplesExample 1Suppose the sender wants to send the word world. In ASCII the five characters are coded as 1110111 1101111 1110010 1101100 1100100The following shows the actual bits sent 11101110 11011110 11100100 11011000 11001001Detection – examplesExample 2Now suppose the word world in Example 1 is received by the receiver without being corrupted in transmission. 11101110 11011110 11100100 11011000 11001001The receiver counts the 1s in each character and comes up with even numbers (6, 6, 4, 4, 4). The data are accepted. Detection – examplesExample 3Now suppose the word world in Example 1 is corrupted during transmission. 11111110 11011110 11101100 11011000 11001001The receiver counts the 1s in each character and comes up with even and odd numbers (7, 6, 5, 4, 4). The receiver knows that the data are corrupted, discards them, and asks for retransmission.Two –Dimensional Parity CheckDetection - exampleExample 4Suppose the following block is sent: 10101001 00111001 11011101 11100111 10101010 However, it is hit by a burst noise of length 8, and some bits are corrupted. 10100011 10001001 11011101 11100111 10101010 When the receiver checks the parity bits, some of the bits do not follow the even-parity rule and the whole block is discarded. 10100011 10001001 11011101 11100111 10101010 25Parity CodesTo construct an even-parity code, add a parity bit such that the total number of 1s is even.1-bit parity codes can detect single bit errors, but they do not detect 2 bit errors.000 1000 0000110 1110 0110001 0001 1001011 1011 0011010 0010 1010111 0111 1111101 1101 0101100 0100 1100Odd-parity codeEven-parity codeInformation bitsThe serial port on a computer is set to transmit a file using 8 data bits followed by 1 parity bit. The port is set for even parity. Another computer receives the following 9-bit strings. Which are valid and which contain an error?a. 001011010b. 111111111c. 101010100Example Problem 2The serial port on a computer is set to transmit a file using 8 data bits followed by 1 parity bit. The port is set for even parity. Another computer receives the following 9-bit strings. Which are valid and which contain an error?a. 001011010  even # of 1s,  no errorb. 111111111  odd # of 1s,  error c. 101010100  even # of 1s,  no errorExample Problem 2 -SolutionParity CodesThe parity bit can be generated using several XOR gates.Parity Checker CircuitData is 101100130Parity BitQ:- What is a parity bit?Ans:- A parity bit appended to an array of binary digits to make the sum of all the binary digits, including the parity bit, always odd (odd parity) or always even (even parity).31CRCQ:- What is the CRC?32Error DetectionDetection methodsRedundancyFour Types of Redundancy Checks are Used in Data CommunicationsVertical Redundancy Check VRCPerformanceIt can detect single bit errorIt can detect burst errors only if the total number of errors is odd.Longitudinal Redundancy Check(LRC)PerformanceLRC increases the likelihood of detecting burst errors.If two bits in one data units are damaged and two bits in exactly the same positions in another data unit are also damaged, the LRC checker will not detect an errorVRC and LRCCyclic Redundancy Check (CRC)Cyclic Redundancy CheckGiven a k-bit frame or message, the transmitter generates an n-bit sequence, known as a frame check sequence (FCS), so that the resulting frame, consisting of (k+n) bits, is exactly divisible by some predetermined number.The receiver then divides the incoming frame by the same number and, if there is no remainder, assumes that there was no error.Binary DivisionPolynomialPolynomial and DivisorStandard PolynomialsChecksumAt the SenderThe unit is divided into k sections, each of n bits.All sections are added together using one’s complement to get the sum.The sum is complemented and becomes the checksum.The checksum is sent with the dataAt the ReceiverThe unit is divided into k sections, each of n bits.All sections are added together using one’s complement to get the sum.The sum is complemented.If the result is zero, the data are accepted: otherwise, they are rejected.PerformanceThe checksum detects all errors involving an odd number of bits.It detects most errors involving an even number of bits.If one or more bits of a segment are damaged and the corresponding bit or bits of opposite value in a second segment are also damaged, the sums of those columns will not change and the receiver will not detect a problem.Error CorrectionIt can be handled in two ways:receiver can have the sender retransmit the entire data unit.The receiver can use an error-correcting code, which automatically corrects certain errors.Single-bit Error Correction To correct an error, the receiver reverses the value of the altered bit. To do so, it must know which bit is in error.Number of redundancy bits neededLet data bits = mRedundancy bits = rTotal message sent = m+rThe value of r must satisfy the following relation:2r ≥ m+r+1Error CorrectionHamming CodeHamming CodeHamming CodeExample of Hamming CodeSingle-bit ErrorError DetectionHamming Distance CalculationStep - Ensure the two strings are of equal length. The Hamming distance can only be calculated between two strings of equal length. String 1: "1001 0010 1101" String 2: "1010 0010 0010"Step 2- Compare the first two bits in each string. If they are the same, record a "0" for that bit. If they are different, record a "1" for that bit. In this case, the first bit of both strings is "1," so record a "0" for the first bit.Step 3- Compare each bit in succession and record either "1" or "0" as appropriate. String 1: "1001 0010 1101" String 2: "1010 0010 0010" Record: "0011 0000 1111"Step 4- Add all the ones and zeros in the record together to obtain the Hamming distance. Hamming distance = 0+0+1+1+0+0+0+0+1+1+1+1 = 6Tip:-If using a computer, "XOR" can be used to compare the two strings and obtain the "record."60CRCQ:- What is the CRC?Ans:- The CRC is an error detecting code in which the code is the remainder resulting from dividing the bits to be checked by a predetermined binary number.6162CRC Vs. ParityQ:- The CRC is an error detecting code in which the code is the remainder resulting from dividing the bits to be checked by a predetermined binary number.63CRC Vs. ParityQ:- The CRC is an error detecting code in which the code is the remainder resulting from dividing the bits to be checked by a predetermined binary number.Ans:- The CRC has more bits and therefore provides more redundancy. That is, it provides more information that can be used to detect errors.6465CRC AlgorithmQ:- List three different ways in which the CRC algorithm can be described.66Cyclic Redundancy Check (CRC)67Burst errors will most likely go undetected by a simple parity check schemeInstead, a more elaborate technique called Cyclic Redundancy Check (CRC) is typically implementedCRC appends redundant bits to the frame trailer called Frame Check Sequence (FCS)FCS is later utilized at RX for error detectionIn a given frame containing n bits, we define:k = number of original data bits(n – k) = number of bits in the FCS field (i.e. additional bits)So, that the total frame length is k + (n – k) = n bitsCRC Generation68CRC generation is all about finding the FCS given the data (D) and a divisor (P)There are three equivalent ways to generate the CRC code:Modulo-2 Arithmetic MethodPolynomial MethodDigital Logic Method69Modulo 2 ArithmeticBinary arithmetic without carryEquivalent to XOR operationi.e:0  0 = 0; 1  0 = 1; 0  1 = 1; 1  1 = 01  0 = 0; 0  1 = 0; 1  1 = 1Examples: 1010+1010___________ 0000CRC Error Detection Process70Given k-bit data (D), the TX generates an (n – k)-bit FCS field (F) such that the total n-bit frame (T) is exactly divisible by some (n-k+1)-bit predetermined devisor (P) (i.e. gives a zero remainder)In general, the received frame may or may not be equal, in value, to the sent frameLet the received frame be (T’)In error-free transmission T’ = TThe RX then divides (T’) by the same known divisor (P) and checks if there is any remainderIf division yields a remainder then the frame is erroneousIf the division yields zero remainder then the frame is error-free unless many erroneous bits in T’ resulted in a new exact division by P (This is very unlikely but possible, causing an undetected error!)CRC Generation71Data D:T = 2 (n – k)  D + FLSB? P is 1-bit longer than F(n-k) left shifts(multiplications by 2)CRC Generation72T = 2(n – k)  D + F, What is F that makes T divides P exactly ?Claim: F is the remainder obtained from dividing {2(n – k)  D} by divisor P where Q is the quotient and F is the remainderIf this is the correct F, T should now divide P with Zero remainderNote: For F to be a remainder when dividing by P, it should be 1-bit smallerCRC Generation – Modulo-2 Arithmetic MethodAt TX: CRC Generation (using previous rules):Multiply: 2(n – k)  D (left shift by (n-k) bits)Divide: 2(n – k)  D / PUse the resulting (n – k)-bit remainder as the FCSAt RX: CRC Checking: RX divides the received T (i.e. T’) by the known divisor (P) and checks if there is any remainder73Example – Modulo-2 Arithmetic MethodGivenD = 1 0 1 0 0 0 1 1 0 1P = 1 1 0 1 0 1Find the FCS fieldSolution:First we note that:The size of the data block D is k = 10 bitsThe size of P is (n – k + 1) = 6 bits  Hence the FCS length is n – k = 5  Total size of the frame T is n = 15 bits74Example – Modulo-2 Arith. Method75Solution (continued):Multiply 2(n – k)  D2(5)  1 0 1 0 0 0 1 1 0 1 = 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0This is a simple shift to the left by five positionsDivide 2(n – k)  D / P (see next slide for details)1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 ÷ 1 1 0 1 0 1 yields:Quotient Q = 1 1 0 1 0 1 0 1 1 0Remainder R = 0 1 1 1 0So, FCS = R = 0 1 1 1 0: Append it to D to get the full frame T to be transmittedT = 1 0 1 0 0 0 1 1 0 1 0 1 1 1 0 M FCS76Example – Modulo-2 Arith. Method# of bits < # of bits in P, result of division is 0Checks you should do (exercise): - Verify correct operation, i.e. that 2(n-k)D = P*Q + R- Verify that obtained T (101000110101110) divides P (110101) exactly (i.e. with zero remainder)= FCS = F