Sec.2.3 Error Detection 57 for UHF and VHF TV broadcast,for FM broadcast,and many specialized applications. Packet radio networks,discussed in Section 4.6,use this frequency band.Typical data rates in this band are highly variable;the DARPA (U.S.Department of Defense Ad- vanced Research Projects Agency)packet radio network,for example,uses 100,000 and 400.000bps. Below 30 MHz,long-distance propagation beyond line-of-sight is possible by re- flection from the ionosphere.Ironically,the 3 to 30 MHz band is called the high- frequency(HF)band,the terminology coming from the early days of radio.This band is very noisy,heavily used (e.g.,by ham radio),and subject to fading.Fading can be viewed as a channel filtering phenomenon with the frequency response changing rela- tively rapidly in time:this is caused by time-varying multiple propagation paths from source to destination.Typical data rates in this band are 2400 bps and less. Microwave links (above 1000 MHz)must use line-of-sight paths.The antennas (usually highly directional dishes)yield typical path lengths of 10 to 200 km.Longer paths than this can be achieved by the use of repeaters.These links can carry 1000 Mbps or so and are usually multiplexed between long-distance telephony.TV program distribution,and data. Satellite links use microwave frequencies with a satellite as a repeater.They have similar data rates and uses as microwave links.One satellite repeater can receive signals from many ground stations and broadcast back in another frequency band to all those ground stations.The satellite can contain multiple antenna beams,allowing it to act as a switch for multiple microwave links.In Chapter 4,multiaccess techniques for sharing individual frequency bands between different ground stations are studied. This section has provided a brief introduction to physical channels and their use in data transmission.A link in a subnet might use any of these physical channels,or might share such a channel on a TDM or FDM basis with many other uses.Despite the complexity of this subject(which we have barely touched).these links can be regarded simply as unreliable bit pipes by higher layers. 2.3 ERROR DETECTION The subject of the next four sections is data link control.This section treats the detec- tion of transmission errors,and the next section treats retransmission requests.Assume initially that the receiving data link control (DLC)module knows where frames begin and end.The problem then is to determine which of those frames contain errors.From the layering viewpoint.the packets entering the DLC are arbitrary bit strings (i.e.,the function of the DLC layer is to provide error-free packets to the next layer up,no matter what the packet bit strings are).Thus,at the receiving DLC,any bit string is acceptable as a packet and errors cannot be detected by analysis of the packet itself.Note that a transformation on packets of k bits into some other representation of length K cannot help;there are 2 possible packets and all possible bit strings of length K must be used to represent all possible packets.The conclusion is that extra bits must be appended to a packet to detect errors
Sec. 2.3 Error Detection 57 for UHF and VHF TV broadcast, for FM broadcast, and many specialized applications. Packet radio networks, discussed in Section 4.6, use this frequency band. Typical data rates in this band are highly variable; the DARPA (U.S. Department of Defense Advanced Research Projects Agency) packet radio network, for example, uses 100,000 and 400,000 bps. Below 30 MHz, long-distance propagation beyond line-of-sight is possible by reflection from the ionosphere. Ironically, the 3 to 30 MHz band is called the highfrequency (HF) band, the terminology coming from the early days of radio. This band is very noisy, heavily used (e.g., by ham radio), and subject to fading. Fading can be viewed as a channel filtering phenomenon with the frequency response changing relatively rapidly in time; this is caused by time-varying multiple propagation paths from source to destination. Typical data rates in this band are 2400 bps and less. Microwave links (above 1000 MHz) must use line-of-sight paths. The antennas (usually highly directional dishes) yield typical path lengths of 10 to 200 km. Longer paths than this can be achieved by the use of repeaters. These links can carry 1000 Mbps or so and are usually multiplexed between long-distance telephony, TV program distribution, and data. Satellite links use microwave frequencies with a satellite as a repeater. They have similar data rates and uses as microwave links. One satellite repeater can receive signals from many ground stations and broadcast back in another frequency band to all those ground stations. The satellite can contain multiple antenna beams, allowing it to act as a switch for multiple microwave links. In Chapter 4, multiaccess techniques for sharing individual frequency bands between different ground stations are studied. This section has provided a brief introduction to physical channels and their use in data transmission. A link in a subnet might use any of these physical channels, or might share such a channel on a TOM or FDM basis with many other uses. Despite the complexity of this subject (which we have barely touched), these links can be regarded simply as unreliable bit pipes by higher layers. 2.3 ERROR DETECTION The subject of the next four sections is data link control. This section treats the detection of transmission errors, and the next section treats retransmission requests. Assume initially that the receiving data link control (DLC) module knows where frames begin and end. The problem then is to determine which of those frames contain errors. From the layering viewpoint, the packets entering the OLe are arbitrary bit strings (i.e., the function of the DLC layer is to provide error-free packets to the next layer up, no matter what the packet bit strings are). Thus, at the receiving DLC, any bit string is acceptable as a packet and errors cannot be detected by analysis of the packet itself. Note that a transformation on packets of f{ bits into some other representation of length f{ cannot help; there are 2K possible packets and all possible bit strings of length K must be used to represent all possible packets. The conclusion is that extra bits must be appended to a packet to detect errors
58 Point-to-Point Protocols and Links Chap.2 2.3.1 Single Parity Checks The simplest example of error detection is to append a single bit,called a pariry check, to a string of data bits.This parity check bit has the value 1 if the number of I's in the bit string is odd,and has the value 0 otherwise (see Fig.2.13).In other words,the parity check bit is the sum,modulo 2,of the bit values in the original bit string (k modulo j, for integer k and positive integer j,is the integer m,0<m <j,such that k-m is divisible by j). In the ASCII character code,characters are mapped into strings of seven bits and then a parity check is appended as an eighth bit.One can also visualize appending a parity check to the end of a packet,but it will soon be apparent that this is not a sufficiently reliable way to detect errors. Note that the total number of I's in an encoded string (i.e.,the original bit string plus the appended parity check)is always even.If an encoded string is transmitted and a single error occurs in transmission,then,whether a 1 is changed to a 0 or a 0 to a 1,the resulting number of 1's in the string is odd and the error can be detected at the receiver. Note that the receiver cannot tell which bit is in error,nor how many errors occurred;it simply knows that errors occurred because of the odd number of I's. It is rather remarkable that for bit strings of any length,a single parity check enables the detection of any single error in the encoded string.Unfortunately,two errors in an encoded string always leave the number of I's even so that the errors cannot be detected.In general,any odd number of errors are detected and any even number are undetected. Despite the appealing simplicity of the single parity check,it is inadequate for reliable detection of errors;in many situations,it only detects errors in about half of the encoded strings where errors occur.There are two reasons for this poor behavior.The first is that many modems map several bits into a single sample of the physical channel input(see Section 2.2.5),and an error in the reception of such a sample typically causes several bit errors.The second reason is that many kinds of noise,such as lightning and temporarily broken connections,cause long bursts of errors.For both these reasons, when one or more errors occur in an encoded string,an even number of errors is almost as likely as an odd number and a single parity check is ineffective. 2.3.2 Horizontal and Vertical Parity Checks Another simple and intuitive approach to error detection is to arrange a string of data bits in a two-dimensional array (see Fig.2.14)with one parity check for each row and one for each column.The parity check in the lower right corner can be viewed as a parity check on the row parity checks,on the column parity checks,or on the data array.If an even number of errors are confined to a single row,each of them can be detected by the S1 82 5334 S5 SA Figure 2.13 Single parity check.Final bit 1 011000 c is the modulo 2 sum of si to sk,where =7 here
58 2.3.1 Single Parity Checks Point-to-Point Protocols and Links Chap. 2 r The simplest example of error detection is to append a single bit, called a parity check, to a string of data bits. This parity check bit has the value 1 if the number of 1's in the bit string is odd, and has the value 0 otherwise (see Fig. 2.13). In other words, the parity check bit is the sum, modulo 2, of the bit values in the original bit string (k modulo j, for integer k and positive integer j, is the integer m, 0 :-:::: m < j, such that k - m is divisible by j). In the ASCII character code, characters are mapped into strings of seven bits and then a parity check is appended as an eighth bit. One can also visualize appending a parity check to the end of a packet, but it will soon be apparent that this is not a sufficiently reliable way to detect errors. Note that the total number of l's in an encoded string (i.e., the original bit string plus the appended parity check) is always even. If an encoded string is transmitted and a single error occurs in transmission, then, whether a I is changed to a 0 or a 0 to a I, the resulting number of l's in the string is odd and the error can be detected at the receiver. Note that the receiver cannot tell which bit is in error, nor how many errors occurred; it simply knows that errors occurred because of the odd number of l's. It is rather remarkable that for bit strings of any length, a single parity check enables the detection of any single error in the encoded string. Unfortunately, two errors in an encoded string always leave the number of 1's even so that the errors cannot be detected. In general, any odd number of errors are detected and any even number are undetected. Despite the appealing simplicity of the single parity check, it is inadequate for reliable detection of errors; in many situations, it only detects errors in about half of the encoded strings where errors occur. There are two reasons for this poor behavior. The first is that many modems map several bits into a single sample of the physical channel input (see Section 2.2.5), and an error in the reception of such a sample typically causes several bit errors. The second reason is that many kinds of noise, such as lightning and temporarily broken connections, cause long bursts of errors. For both these reasons, when one or more errors occur in an encoded string, an even number of errors is almost as likely as an odd number and a single parity check is ineffective. 2.3.2 Horizontal and Vertical Parity Checks Another simple and intuitive approach to error detection is to arrange a string of data bits in a two-dimensional array (see Fig. 2.14) with one parity check for each row and one for each column. The parity check in the lower right comer can be viewed as a parity check on the row parity checks, on the column parity checks, or on the data array. If an even number of errors are confined to a single row, each of them can be detected by the Figure 2.13 Single parity check. Final bit c is the modulo 2 sum of 81 to 8b where k = 7 here
Sec.2.3 Error Detection 59 1001 0 1 0 1 01110 1 0 0 11100 0 1 0 Horizontal checks 100011 1 0 0011 00 1 1 101111 1 0 Vertical checks (a) 100101 0 1 011101 0 0 11① 0 0⊙ 1 0 10001 1 0 Figure 2.14 Horizontal and vertical parity 00①10 @ 1 checks.Each horizontal parity check checks its own row,and each column parity 10111 1 1 0 check checks its own column.Note,in part (b).that if each circled bit is changed,all (b) parity checks are still satisfied. corresponding column parity checks;similarly,errors in a single column can be detected by the row parity checks.Unfortunately,any pattern of four errors confined to two rows and two columns [i.e.,forming a rectangle as indicated in Fig.2.14(b)]is undetectable. The most common use of this scheme is where the input is a string of ASCIl encoded characters.Each encoded character can be visualized as a row in the array of Fig.2.14;the row parity check is then simply the last bit of the encoded character.The column parity checks can be trivially computed by software or hardware.The major weakness of this scheme is that it can fail to detect rather short bursts of errors (e.g., two adjacent bits in each of two adjacent rows).Since adjacent errors are quite likely in practice,the likelihood of such failures is undesirably high. 2.3.3 Parity Check Codes The nicest feature about horizontal and vertical parity checks is that the underlying idea generalizes immediately to arbitrary parity check codes.The underlying idea is to start with a bit string (the array of data bits in Fig.2.14)and to generate parity checks on various subsets of the bits (the rows and columns in Fig.2.14).The transformation from the string of data bits to the string of data bits and parity checks is called a parity check code or linear code.An example of a parity check code (other than the horizontal and vertical case)is given in Fig.2.15.A parity check code is defined by the particular collection of subsets used to generate parity checks.Note that the word code refers to the transformation itself:we refer to an encoded bit string (data plus parity checks)as a code word. Let K be the length of the data string for a given parity check code and let L be the number of parity checks.For the frame structure in Fig.2.2,one can view the data
Sec. 2.3 Error Detection 59 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 0 1 0 Horizontal 1 1 checks 1 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 Vertical checks (a) 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 1 CD 0 0 ® 1 0 1 0 0 0 1 1 1 0 Figure 2.14 Horizontal and vertical parity 0 0 CD 1 0 ® 1 1 checks. Each horizontal parity check checks its own row, and each column parity 0 0 check checks its own column. Note, in part (b), that if each circled bit is changed, all (b) parity checks are still satisfied. corresponding column parity checks; similarly, errors in a single column can be detected by the row parity checks. Unfortunately, any pattern of four errors confined to two rows and two columns [i.e., forming a rectangle as indicated in Fig. 2.14(b)] is undetectable. The most common use of this scheme is where the input is a string of ASCII encoded characters. Each encoded character can be visualized as a row in the array of Fig. 2.14; the row parity check is then simply the last bit of the encoded character. The column parity checks can be trivially computed by software or hardware. The major weakness of this scheme is that it can fail to detect rather short bursts of errors (e.g., two adjacent bits in each of two adjacent rows). Since adjacent errors are quite likely in practice, the likelihood of such failures is undesirably high. 2.3.3 Parity Check Codes The nicest feature about horizontal and vertical parity checks is that the underlying idea generalizes immediately to arbitrary parity check codes. The underlying idea is to start with a bit string (the array of data bits in Fig. 2.14) and to generate parity checks on various subsets of the bits (the rows and columns in Fig. 2.14). The transformation from the string of data bits to the string of data bits and parity checks is called a parity check code or linear code. An example of a parity check code (other than the horizontal and vertical case) is given in Fig. 2.15. A parity check code is defined by the particular collection of subsets used to generate parity checks. Note that the word code refers to the transformation itself; we refer to an encoded bit string (data plus parity checks) as a code word. Let K be the length of the data string for a given parity check code and let L be the number of parity checks. For the frame structure in Fig. 2.2, one can view the data
60 Point-to-Point Protocols and Links Chap.2 S1 82 83 CI C2 C3 C4 10 011 0 0 1001 11 C1=S+83 0 011 1 0 1 C2=S1十2十83 1101 001 3=s1+82 1010 0 11 C4S2十s3 1 0 00 0 000 0 0 0 0 1110 10 Figure 2.15 Example of a parity check code.Code words are listed on the left,and the rule for generating the parity checks is given on the right. string as the header and packet,and view the set of parity checks as the trailer.Note that it is important to detect errors in the control bits of the header as well as to detect errors in the packets themselves.Thus,K+L is the frame length,which for the present is regarded as fixed.For a given code,each of the possible 2 data strings of lengthK is mapped into a frame (i.e.,code word)of length K+L.In an error-detection system, the frame is transmitted and the receiving DLC module determines if each of the parity checks is still the modulo 2 sum of the corresponding subset of data bits.If so,the frame is regarded by the receiver as error-free,and if not,the presence of errors is detected. If errors on the link convert one code word into another,the frame is regarded by the receiver as error-free,and undetectable errors are said to have occurred in the frame. Given any particular code,one would like to be able to predict the probability of undetectable errors in a frame for a particular link.Unfortunately,this is very difficult. First,errors on links tend to be dependent and to occur in bursts;there are no good models for the length or intensity of these bursts,which vary widely among links of the same type.Second,for any reasonable code,the frequency of undetectable errors is very small and is thus both difficult to measure experimentally and dependent on rare. difficult-to-model events.The literature contains many calculations of the probability of undetectable errors,but these calculations are usually based on the assumption of independent errors;the results are usually orders of magnitude away from reality. As a result of these difficulties,the effectiveness of a code for error detection is usually measured by three parameters:(1)the minimum distance of the code,(2)the burst-detecting capability,and (3)the probability that a completely random string will be accepted as error-free.The minimum distance of a code is defined as the smallest number of errors that can convert one code word into another.As we have seen,the minimum distance of a code using a single parity check is 2,and the minimum distance of a code with horizontal and vertical parity checks is 4. The length of a burst of errors in a frame is the number of bits from the first error to the last,inclusive.The burst-detecting capability of a code is defined as the largest integer B such that a code can detect all bursts of length B or less.The burst-detecting capability of the single parity check code is 1,whereas the burst-detecting capability of
60 Point-to-Point Protocols and Links Chap. 2 81 82 83 c, C2 C3 C4 1 0 0 I 1 1 0 0 1 0 0 1 1 1 C1 = 8\ + 83 0 0 1 1 1 0 1 C2 = 81 + 82 + 83 1 1 0 1 0 0 1 C3 = 81 + 82 1 0 1 0 0 1 1 C4 = 82 + 83 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 I 0 1 0 Figure 2.15 Example of a parity check code. Code words are listed on the left. and the rule for generating the parity checks is given on the right. string as the header and packet, and view the set of parity checks as the trailer. Note that it is important to detect errors in the control bits of the header as well as to detect errors in the packets themselves. Thus, K +L is the frame length, which for the present is regarded as fixed. For a given code, each of the possible 2K data strings of length K is mapped into a frame (i.e., code word) of length K + L. In an error-detection system, the frame is transmitted and the receiving OLe module determines if each of the parity checks is still the modulo 2 sum of the corresponding subset of data bits. Ifso, the frame is regarded by the receiver as error-free, and if not, the presence of errors is detected. If errors on the link convert one code word into another, the frame is regarded by the receiver as error-free, and undetectable errors are said to have occurred in the frame. Given any particular code, one would like to be able to predict the probability of undetectable errors in a frame for a particular link. Unfortunately, this is very difficult. First, errors on links tend to be dependent and to occur in bursts; there are no good models for the length or intensity of these bursts, which vary widely among links of the same type. Second, for any reasonable code, the frequency of undetectable errors is very small and is thus both difficult to measure experimentally and dependent on rare, difficult-to-model events. The literature contains many calculations of the probability of undetectable errors, but these calculations are usually based on the assumption of independent errors; the results are usually orders of magnitude away from reality. As a result of these difficulties, the effectiveness of a code for error detection is usually measured by three parameters: (1) the minimum distance of the code, (2) the burst-detecting capability, and (3) the probability that a completely random string will be accepted as error-free. The minimum distance of a code is defined as the smallest number of errors that can convert one code word into another. As we have seen, the minimum distance of a code using a single parity check is 2, and the minimum distance of a code with horizontal and vertical parity checks is 4. The length of a burst of errors in a frame is the number of bits from the first error to the last, inclusive. The burst-detecting capability of a code is defined as the largest integer B such that a code can detect all bursts of length B or less. The burst-detecting capability of the single parity check code is I, whereas the burst-detecting capability of
Sec.2.3 Error Detection 61 a code with horizontal and vertical parity checks is I plus the length of a row(assuming that rows are sent one after the other). By a completely random string of length K+L is meant that each such string is received with probability 2.Since there are 2 code words,the probability of an undetected error is the probability that the random string is one of the code words;this occurs with probability 2(the possibility that the received random string happens to be the same as the transmitted frame is ignored).This is usually a good estimate of the probability of undetectable errors given that both the minimum distance and the burst- detecting capability of the code are greatly exceeded by the set of errors on a received frame. Parity check codes can be used for error correction rather than just for error de- tection.For example,with horizontal and vertical parity checks,any single error can be corrected simply by finding the row and column with odd parity.It is shown in Prob- lem 2.10 that a code with minimum distance d can be used to correct any combination of fewer than d/2 errors.Parity check codes (and convolutional codes,which are closely related but lack the frame structure)are widely used for error correction at the physical layer.The modern approach to error correction is to view it as part of the modulation and demodulation process,with the objective of creating a virtual bit pipe with relatively low error rate. Error correction is generally not used at the DLC layer,since the performance of an error correction code is heavily dependent on the physical characteristics of the channel. One needs error detection at the DLC layer,however,to detect rare residual errors from long noisy periods. 2.3.4 Cyclic Redundancy Checks The parity check codes used for error detection in most DLCs today are cyclic redundancy check (CRC)codes.The parity check bits are called the CRC.Again,let L be the length of the CRC (i.e.,the number of check bits)and let K be the length of the string of data bits (i.e..the header and packet of a frame).It is convenient to denote the data bits as SK-1 SK-2,...,s1,So,and to represent the string as a polynomial s(D)with coefficients 8K-1,S0, s(D)=3K-1D-1+3K-2DK-2+.+50 (2.14) The powers of the indeterminate D can be thought of as keeping track of which bit is which;high-order terms are viewed as being transmitted first.The CRC is represented as another polynomial, c(D)=cL-1DL-1+..+cD+co (2.15) The entire frame of transmitted information and CRC can then be represented as (D)=s(D)D+c(D),that is,as x(D)=sK-1Dl+K-l+.+s0D+cL-1D-1+…+0 (2.16)
Sec. 2.3 Error Detection 61 a code with horizontal and vertical parity checks is I plus the length of a row (assuming that rows are sent one after the other). By a completely random string of length K + L is meant that each such string is received with probability 2-[{-L. Since there are 2]{ code words, the probability of an undetected error is the probability that the random string is one of the code words; this occurs with probability 2- L (the possibility that the received random string happens to be the same as the transmitted frame is ignored). This is usually a good estimate of the probability of undetectable errors given that both the minimum distance and the burstdetecting capability of the code are greatly exceeded by the set of errors on a received frame. Parity check codes can be used for error correction rather than just for error detection. For example, with horizontal and vertical parity checks, any single error can be corrected simply by finding the row and column with odd parity. It is shown in Problem 2.10 that a code with minimum distance d can be used to correct any combination of fewer than d/2 errors. Parity check codes (and convolutional codes, which are closely related but lack the frame structure) are widely used for error correction at the physical layer. The modem approach to error correction is to view it as part of the modulation and demodulation process, with the objective of creating a virtual bit pipe with relatively low error rate. Error correction is generally not used at the DLC layer, since the performance of an error correction code is heavily dependent on the physical characteristics of the channel. One needs error detection at the DLC layer, however, to detect rare residual errors from long noisy periods. 2.3.4 Cyclic Redundancy Checks The parity check codes used for error detection in most DLCs today are cyclic redundancy check (CRC) codes. The parity check bits are called the CRe. Again, let L be the length of the CRC (i.e., the number of check bits) and let K be the length of the string of data bits (i.e., the header and packet of a frame). It is convenient to denote the data bits as S[(_I, S]{-2, ... , SI, S(), and to represent the string as a polynomials(D) with coefficients SK-l,···,So, (2.14) The powers of the indeterminate D can be thought of as keeping track of which bit is which; high-order terms are viewed as being transmitted first. The CRC is represented as another polynomial, (2.15) The entire frame of transmitted information and CRC can then be represented as xeD) = s(D)DL + c(D), that is, as (2.16)