Redundancy Adding extra bits for detecting or correcting errors at the destination Types of Errors Single-Bit Error Only one bit of a given data unit is changed Burst Error Two or more bits in the data unit have changed Due to duration of noise longer than duration of a bit Block Coding Dataword & Codeword A message is divided into blocks, each of k bits, called datawords r redundant bits are added to each block to make the length n = k + r; the resulting n-bit blocks are called codewords 2
Block Coding (cont.) Hamming Distance (between two words) # of differences between the corresponding bits Hamming distance d(x,y) between two words x and y Minimum Hamming Distance (in a set of words) The smallest Hamming distance between all possible pairs Block Coding (cont.) Minimum Distance for Error Correction To guarantee the correction of up to t errors in all cases, the min Hamming distance in a block code must be d min = 2t + 1 d min C(n, k), where n = codeword size, k = dataword size 5 7 Block Coding (cont.) Minimum Distance for Error Detection To guarantee the detection of up to s errors in all cases, the min Hamming distance in a block code must be d min = s + 1 Linear Block Codes Definition A code in which the exclusive OR of two valid codewords creates another valid codeword Minimum Distance for Linear Block Codes # of 1s in the nonzero valid codeword with the smallest number of 1s 6 8
Simple Parity-Check Code Two-Dimensional Parity Check Code (cont.) Single-bit error detecting code: d min = 2 One extra bit, called the parity bit, is selected to make the total # of 1s in the codeword even (or odd) Can detect an odd number of errors 9 11 Two-Dimensional Parity Check Code Two-Dimensional Parity Check Code (cont.) The dataword is organized in a table (rows and columns) For each row and each column, 1 parity-check bit is calculated Can detect up to three errors 10 12
Hamming Code Single-bit error correcting code: d min = Can detect up to two errors or correct one single error Error Correction (cont.) Data and Redundancy Bits Number of data bits m Number of redundancy bits r Total bits m + r 1 2 5 6 7 2 5 6 7 9 10 11 1 15 Error Correction Error Correction by Retransmission When error is discovered, receiver has sender retransmit the entire data unit Forward Error Correction Receiver uses an error-correcting code, which automatically corrects certain errors More sophisticated than error detection codes and require more redundancy bits Number of Redundancy Bits m: # of data bits r: # of redundancy bits 2 m+r 2 m (m + r + 1) 2 r m + r + 1 Error Correction (cont.) Hamming Code Redundancy Bit Calculation 1 16
Error Correction (cont.) Hamming Code Example of Redundancy Bit Calculation Burst Error Correction using Hamming Code Error Correction (cont.) 17 19 Error Correction (cont.) Hamming Code Error Detection using Hamming Code Cyclic Redundancy Check (CRC) Most powerful technique Append a sequence of redundant bits, called CRC or CRC remainder, to end of a data unit so that resulting data unit becomes exactly divisible by a predetermined binary number 18 20
Cyclic Redundancy Check (cont.) CRC Encoder Use modulo-2 division Cyclic Redundancy Check (cont.) Polynomials 21 2 Cyclic Redundancy Check (cont.) CRC Decoder Cyclic Redundancy Check (cont.) Standard Polynomials Name CRC-8 CRC-10 ITU-16 ITU-2 Polynomial x 8 + x 2 + x + 1 x 10 + x 9 + x 5 + x + x 2 + 1 x 16 + x 12 + x 5 + 1 x 2 + x 26 + x 2 + x 22 + x 16 + x 12 + x 11 + x 10 + x 8 + x 7 + x 5 + x + x 2 + x + 1 Application ATM header ATM AAL HDLC LANs Performance of CRC Detect all burst errors affecting odd number of bits Detect all burst errors of length less than or equal to the degree of the polynomial Detect with a very high probability burst errors of length greater than the degree of the polynomial 22 2
Cyclic Redundancy Check (cont.) Another Example of CRC CRC 보충설명 (cont.) 절차 T = 2 n M + F, 2 n M / P = Q + R / P 만일 R = F, T / P = (2 n M + R) / P = Q + R / P + R / P = Q + (2R) / P = Q 송신측 : 2 n M 을 P 로나누어서, 나머지를 FCS 로사용수신측 : T 를 P 로나누어서나머지가없으면오류없음 (ex) M = 1010001101, P = 110101 2 n M / P 를하면 Q = 1101010110, R = 01110 따라서 T = 101000110101110 = 2 n M + R 25 27 CRC 보충설명 인자 k : 메시지의비트수 n : FCS(Frame Check Sequence) 의비트수 T : 전송될 (k+n) 비트프레임 (n < k) M : k 비트메시지, T 의첫 k 개비트 F : n 비트 FCS, T 의마지막 n 개비트 P : (n+1) 비트패턴 (divisor) Modulo 2 연산 carryless binary addition exclusive-or CRC 보충설명 (cont.) Divisor P FCS 보다 1 비트큼 오류종류에따라결정됨 최상위, 최하위비트는 1 다항식표현법 dummy variable X 사용, 이진수의비트에해당하는이진계수사용 (ex) M = 110011 인경우, M(X) = X 5 + X + X + 1 다항식표현의경우, 오류 E(X) 가 P(X) 로나누어지면오류검출이안됨 26 28
CRC 보충설명 (cont.) Checksum (cont.) 검출가능한오류의종류 모든단일비트오류검출가능 E(X) = X i, P(X) 의첫항과마지막항은 1 이므로적어도 2 개항을가짐 P(X) 가최소 개항인수를가지면, 모든두비트오류검출가능 E(X) = X i + X j = X i (1 + X j-i ), where i > j P(X) 가 (X+1) 인자를가지면, 홀수개오류검출가능 만일 E(X) 가홀수개항을가지고 (X+1) 로나누어질수있다고가정하면, E(X) = (X+1)F(X) 이고 E(1) = (1+1)F(X) = 0F(X) = 0, 그러나 E(X) 가홀수개항을가지므로 E(1) 은 1 이되어야함 모순. 따라서홀수개의항을갖는 E(X) 는 (X+1) 로나누어질수없음 Checksum Generator Unit is divided into k sections, each of n bits All sections are added using ones complement to get the sum Sum is complemented and becomes the checksum Checksum is sent with the data 29 1 Checksum Checksum (cont.) Checksum Checker Unit is divided into k sections, each of n bits All sections are added using ones complement to get the sum Sum is complemented If the result is zero, the data are accepted: otherwise, they are rejected 0 2
Checksum (cont.)