Data transmission can contain errors. – Single-bit. – Burst errors of length n. (n: distance between the first and last errors in data block) • How to detect errors. – If only data is transmitted, errors cannot be detected. Send more information with data that satisfies a special relationship. -Add redundancy | Error Detection Data transmission can contain errors Single-bit Burst errors of length n (n: distance between the first and last errors in data block) How to detect errors If only data is transmitted, errors cannot be detected Send more information with data that satisfies a special relationship Add redundancy Winter 2005 ECE ECE 766 Computer Interfacing and Protocols Error Detection Methods Vertical Redundancy Check (VRC) Append a single bit at the end of data block such that the number of ones is even Even Parity (odd parity is similar) 0110011 01100110 0110001 01100011 VRC is also known as Parity Check Performance: Detects all odd-number errors in a data block Winter 2005 ECE ECE 766 Computer Interfacing and Protocols Error Detection Methods Longitudinal Redundancy Check (LRC) Organize data into a table and create a parity for each column 11100111 11011101 00111001 10101001 11100111 11011101 00111001 10101001 10101010 11100111 11011101 00111001 10101001 10101010 Original Data LRC Winter 2005 ECE ECE 766 Computer Interfacing and Protocols Error Detection Methods Performance: Detects all burst errors up to length n (number of columns) Misses burst errors of length n+1 if there are n-1 uninverted bits between the first and last bit If the block is badly garbled, the probability of acceptance is Checksum Used by upper layer protocols Similar to LRC, uses one’s complement arithmetic Winter 2005 ECE ECE 766 Computer Interfacing and Protocols Cyclic Redundancy Check Powerful error detection scheme Rather than addition, binary division is used Finite Algebra Theory (Galois Fields) Can be easily implemented with small amount of hardware Shift registers XOR (for addition and subtraction) Winter 2005 ECE ECE 766 Computer Interfacing and Protocols Cyclic Redundancy Check Let us assume k message bits and n bits of redundancy Associate bits with coefficients of a polynomial 1 0 1 1 0 1 1 1x6+0x5+1x4+1x3+0x2+1x+1 = x6+x4+x3+x+1 xxxxxxxxxx . | Error Detection Data transmission can contain errors Single-bit Burst errors of length n (n: distance between the first and last errors in data block) How to detect errors If only data is transmitted, errors cannot be detected Send more information with data that satisfies a special relationship Add redundancy Winter 2005 ECE ECE 766 Computer Interfacing and Protocols Error Detection Methods Vertical Redundancy Check (VRC) Append a single bit at the end of data block such that the number of ones is even Even Parity (odd parity is similar) 0110011 01100110 0110001 01100011 VRC is also known as Parity Check Performance: Detects all odd-number errors in a data block Winter 2005 ECE ECE 766 Computer Interfacing and Protocols Error Detection Methods Longitudinal Redundancy Check (LRC) Organize data into a table and create a parity for each column 11100111 11011101 00111001 10101001 11100111 11011101 00111001 10101001 10101010 11100111 11011101 00111001 10101001 10101010
