Lecture in Error Detection and Correction | Forouzan

(Last Updated On: March 21, 2020)
review in Error Detection and Correction

Definition of Terms

  • Data can be corrupted during transmission. Some applications require that errors be detected and corrected.
  • In a single-bit error, only one bit in the data unit has changed. A burst error means that two or more bits in the data unit have changed.
  • To detect or correct errors, we need to send extra (redundant) bits with data.
  • Redundancy is the concept of sending extra bits for use in error detection. 
  • There are two main methods of error correction: forward error correction and correction by retransmission.
  • We can divide coding schemes into two broad categories: block coding and convolution coding.
  • In coding, we need to use modulo-2 arithmetic. Operations in this arithmetic are very simple; addition and subtraction give the same results. we use the XOR (exclusive OR) operation for both addition and subtraction.
  • In modulo-N arithmetic, we use only the integers in the range 0 to N −1, inclusive.
  • In block coding, we divide our message into blocks, each of k bits, called datawords. We add r redundant bits to each block to make the length n =  k + r. The resulting n-bit blocks are called codewords.
  • An error-detecting code can detect only the types of errors for which it is designed; other types of errors may remain undetected.
  • The Hamming code is an error correction method using redundant bits. The number of bits is a function of the length of the data bits.
  • In the Hamming code, for a data unit of m bits, use the formula 2 r >= m + r + 1 to determine r, the number of redundant bits needed.
  • By rearranging the order of bit transmission of the data units, the Hamming code can correct burst errors. 
  • The Hamming distance between two words is the number of differences between corresponding bits. The minimum Hamming distance is the smallest Hamming distance between all possible pairs in a set of words.
  • To guarantee the detection of up to s errors in all cases, the minimum Hamming distance in a block code must be dmin = s + 1. To guarantee correction of up to t errors in all cases, the minimum Hamming distance in a block code must be dmin = 2t + 1.
  • In a linear block code, the exclusive OR (XOR) of any two valid codewords creates another valid codeword.
  • A simple parity-check code is a single-bit error-detecting code in which n = k + 1 with dmin = 2.  A simple parity-check code can detect an odd number of errors.
  • All Hamming codes discussed in this book have dmin = 3. The relationship between m and n in these codes is n = 2m – 1
  • Cyclic codes are special linear block codes with one extra property. In a cyclic code, if a codeword is cyclically shifted (rotated), the result is another codeword. 
  • The divisor in a cyclic code is normally called the generator polynomial or simply the generator.
  • In a cyclic code, those e(x) errors that are divisible by g(x) are not caught.
  • If the generator has more than one term and the coefficient of x0 is 1, all single errors can be caught.
  • If a generator cannot divide xt + 1 (t between 0 and n – 1), then all isolated double errors can be detected.
  • A generator that contains a factor of x + 1 can detect all odd-numbered errors.
  • A category of cyclic codes called the cyclic redundancy check (CRC) is used in networks such as LANs and WANs.
  • A pattern of Os and Is can be represented as a polynomial with coefficients of 0 and 1.
  • Traditionally, the Internet has been using a 16-bit checksum, which uses one’s complement arithmetic. In this arithmetic, we can represent unsigned numbers between o and 2n -1 using only n bits.

Error Categories:

  • Single-bit error – has one bit error per data unit.
  • Burst error – has two or more bit errors per data unit.

Three common redundancy methods

  • Parity check– An extra bit (parity bit) is added to the data unit. The parity check can detect only an odd number of errors; it cannot detect an even number of errors. In the two-dimensional parity check, a redundant data unit follows n data units. 
  • Cyclic redundancy check (CRC) – a powerful redundancy checking technique, appends a sequence of redundant bits derived from binary division to the data unit. The divisor in the CRC generator is often represented as an algebraic polynomial. 
  • Checksum –  used in the Internet by several protocols although not at the data link layer.

At least three types of error cannot be detected by the current checksum

  • First, if two data items are swapped during transmission, the sum and the checksum values will not change. 
  • Second, if the value of one data item is increased (intentionally or maliciously) and the value of another one is decreased (intentionally or maliciously) the same amount, the sum and the checksum cannot detect these changes.
  • Third, if one or more data items is changed in such a way that the change is a multiple of 216 − 1, the sum or the checksum cannot detect the changes.

Two Main Methods of Error Correction

  • Forward error correction– the receiver tries to correct the corrupted codeword.
  • Error correction by retransmission – the corrupted message is discarded (the sender needs to retransmit the message).

In block coding, errors be detected by using the following two conditions:

  • a. The receiver has (or can find) a list of valid codewords.
  • b. The original codeword has changed to an invalid one.
Note: You can proceed to take the multiple choice exam regarding this topic. Error Detection and Correction – Set 1 MCQs

List of Data Communications Lectures

credit: Behrouz A. Forouzan©2014 www.PinoyBIX.org
DOWNLOAD PDF / PRINT
Print Friendly, PDF & Email
Please do Subscribe on YouTube!

P inoyBIX educates thousands of reviewers and students a day in preparation for their board examinations. Also provides professionals with materials for their lectures and practice exams. Help me go forward with the same spirit.

“Will you subscribe today via YOUTUBE?”

Subscribe

Add Comment

PinoyBIX Engineering. © 2014-2020 All Rights Reserved | How to Donate? | Follow me on Blogarama DMCA.com Protection Status

Math Solution

Advanced Math problem age work mixture digit motion Analytic Geometry 01 problem Analytic Geometry 02 problem clock variation progression misc Combination problem Differential Calculus 01 Problem Differential Calculus 02 Problem Differential Equations Problem Fundamentals in Algebra Fundamentals in Algebra Problem Integral Calculus problem Permutation problem Plane Geometry problem Plane Trigonometry problem Probability problem quadratic equation binomial theorem logarithms Solid Geometry problem Spherical Trigonometry problem System of Numbers Problem Venn Diagram Problem

Questions and Answers in Mathematics

Advanced Math Age Work Mixture Digit Motion Algebra and General Mathematics Analytic Geometry 01 Analytic Geometry 02 Calculus Clock Variation Progression Misc Differential Calculus 01 Differential Calculus 02 Differential Equations Engineering Mathematics Geometry Integral Calculus Plane Geometry Plane Trigonometry Probability and Statistics Quadratic Equation Binomial Theorem Logarithms Solid Geometry Spherical Trigonometry System of Numbers Trigonometry

video

Pre-board in Electronics Engineering

Answers Pre-board in Electronics Engineering - Answers

Questions and Answers

Basic Television - Grob TV Boylestad Questions and Answers Computer Principles Electrical Circuit Electricity and Magnetism Fundamentals Electronic Circuits Floyd Questions and Answers Floyd Self-test Gibilisco Questions and Answers Grob Questions and Answers Industrial Electronics Principles and Applications Malvino Questions and Answers Microelectronics Power Generators / Sources / Principles and Applications Solid State Devices Tests and Measurements Vacuum Tubes

Pre-board in Communications Engineering

Answers

Questions and Answers

Acoustics Antennas Blake Questions and Answers Broadcasting and Cable TV System Digital Communication Networks Forouzan Frenzel Self-test Kennedy Questions and Answers Microwave Communications Miscellaneous Questions in Communications Modulation Navigational Aids and Radar Systems Noise Optical Fiber Communications Radiation and Wave Propagation Satellite Communications Transmission Fundamentals Wire and Wireless Communications

GEAS Solution

Dynamics problem Economics problem Physics problem Statics problem Strength problem Thermodynamics problem

Pre-board in GEAS

Questions and Answers in GEAS

Engineering Economics Engineering Laws and Ethics Engineering Management Engineering Materials Engineering Mechanics General Chemistry Giancoli Physics Physics Strength of Materials Thermodynamics
Online Tool: Electrical Charge Conversions
Online Tool: Electrical Charge Conversions
Online Tool: Color Code Conversions
Online Tool: Color Code Conversions
Online Tool: Weight Measurement Conversions
Online Tool: Weight Measurement Conversions
Online Tool: Temperature Measurement Conversions
Online Tool: Temperature Measurement Conversions