[Music] in this section we're going to revisit a topic that we covered in section 3.3 when we were studying the udp protocol we encountered the internet checksum remember the internet checksum is used to detect bit level errors in datagrams by udp in this case we're down at the link layer so of course we're interested in frames we're going to add to our earlier discussion in two important ways first by way of example we're going to introduce this notion that bit level errors cannot only be detected at the receiver but they also be corrected and corrected without re-transmissions that's a pretty cool idea secondly we're going to take a look at a error detection technique known as the cyclic redundancy check that's used in practice and is much more powerful than internet check summing so not too much to cover so this should be short and sweet here's the error detection scenario that we studied earlier now in a link layer context the network layer will pass a datagram down to the link layer for transmission the sending side link will then take the datagram add some header fields to create a frame with d bits here and then it's going to compute and append error detection and correction bits edc here the frame's then transmitted over a link that can introduce bit errors the receiver then performs a check to see if the bit frames have been corrupted we'll see how that's done in just a second and if the frame passes the check it'll extract the datagram pass it up to the network layer otherwise the frame will be dropped or perhaps a retransmission procedure be initiated with axenax just as we studied in chapter 3. what we want to focus on now is how this check is done to understand that we'll need to understand how these edc bits are computed for here on the sender side perhaps the simplest case of error detection and correction that we can think of is simple parity checking where a single parity bit is set to 0 or 1 so that the total number of bits among the original d bits and this additional parity bit is even in the case of even parity in this example here there's an odd number of parity bits in the first d bits so the parity bit set to one so that now there's an even number of one bits among the d plus one bits at the receiver side the check is simple the receiver simply determines whether or not there's an even number of one-valued bits in the received data including the parity bit if there's an odd number of one-valued bits the receiver knows there's at least one bit error if there's an even number of one-valued bits the receiver knows well either there's no errors or possibly that there's an even number of errors well that's the simple one-dimensional parity check and we can generalize this to a two-dimensional parity check laying the bits out on a grid like here and computing a parity bit for each row and for each column and then have the receiver check both row and column parity well we're using additional bits here so you'd hope that this additional overhead would somehow buy us better protection and of course it does you should convince yourself now that two bit errors can always be detected but the two-dimensional parity check buys us something more something really special in the case of a single bit error it also allows the receiver not only to detect that there's been a bit error but also detect where that bit error occurred and correct it without re-transmission how cool is that let's take a look at an example of two-dimensional parity here's the case with our d bits again arranged into a grid for the first row we now compute the row parity bit to be one for the second row the parity bit is zero for the third row the parity bits one and we can compute column parity bits as well now let's suppose a bits flipped in transmission as in this example here in this case the receiver says hey there's a parity error in row 2 and there's a parity error in column 2 as well and so it knows that the bit in row 2 column 2 has been flipped the error can be detected and corrected without re-transmission well this is just a simple example of what are called forward error correction techniques they're used in dvds compact discs in digital subscriber line dsl access networks and in deep space communication where sender to receiver delays are very long you'd much rather correct an error on receipt rather than having to request and wait for a re-transmission there's a whole field of study on error correcting codes it's a great area to look at if you love math and math with very practical and very cool application well we've covered the internet checksum already in section 3.3 and in some ways the checksum is very similar to parity instead of adding up bits though we're adding up bytes with the internet checksum but conceptually the behavior is the same on the sender side we simply add up the bytes compute the checksum and send the checksum along with the data being checksummed the receiver action is also conceptually similar to what we've seen above well we've said and seen that the internet checksum isn't particularly strong and so it's not used as far as i know in any link layer protocols instead a much more powerful techniques used in ethernet in wi-fi it's known as a cyclic redundancy check crc so let's take a look at the cyclic redundancy check here again we have d data bits that we want to protect a crc has what's known as a generator g which is a carefully chosen bit pattern of r plus 1 bits that's been standardized agreed upon by all since both the sender and the receiver will need to use the same value of g the crc 32 ieee standard has a 32-bit generator so we see here the d data bits that we want to send along with the r crc bits if we think about these d plus r bits the given bits capital d and the crc bits capital r we'd compute the d plus r bits that we want to send first by left shifting the data bits to the left our positions and then adding in or xoring in the rcrc bits and here's what the sender does it's going to compute the rcrc bits such that this quantity here is exactly divisible by the agreed upon generator g since the receiver knows g it's going to take the received bits divided by g and if there's a non-zero remainder then it will be able to detect an error crcs are more powerful than the error detection techniques we've studied in that they can detect all bursts that's all runs of consecutive bit errors of less than r plus 1 bits that's pretty powerful and it's because of these powerful properties that the crc32 for example is used in both ethernet and wi-fi frames for error detection at the link layer but we still have one important question to answer how does the sender compute r well we know that the sender wants to compute r such that the bit pattern sent is exactly divisible by g well let's xor r and each side of this equation giving this which is really just a mathematical way of saying that if we divide this quantity here d times 2 to the r by g r is the remainder and this then gives us an algorithm for computing r let's look at an example this is just a toy example with a small 4-bit generator g here here's d and here's d left shifted by 3 and now if we want to follow our algorithm over here we divide this quantity here by g and here's an animation of doing that division and the result that we get the remainder is the value of r that would be sent that's all there is to it although in practice again the standard generators are a lot longer than four bits what well that wraps up our quick study of error detection and correction at the link layer i hope you found the notion of forward error correction as neat as i did when i first learned about it and i hope you also enjoyed learning about cyclic redundancy checks it's a little bit dry something that's really good to know about since as we've seen crc codes are widely used in practice you