Page 108 - DCAP406_DCAP_207_Computer Networks

Unit 7: Data Link Layer

receiver puts all the eight bits through an even-parity checking function. If the receiver Notes
sees 11100001, it counts for 1st, an even number, and the data unit passes. But what if the
data unit has been damaged in transit? What if, instead of 11100001, the receiver sees
11100101? The receiver known that an error has been introduced into the data somewhere
and therefore rejects the whole unit. Note that for the sake of simplicity, we are discussing
here even-parity checking, where the number of 1s should be an even number. Some
system may use odd-parity checking, where the number of 1s should be odd. The principle
is the same; the calculation is different.

Figure 7.4: Original Data plus LRC

(b) Longitudinal Redundancy Check: In longitudinal redundancy check (LRC), a block of bits
is organized in a table (rows and columns). For example, instead of sending a block of 32
bits, we organize them in a table made of four rows and eight columns, as shown in figure.
We then calculate the parity bit for each column and create a new row of eight bits, which
are the parity bits for the whole block.

Notes Note that the first parity bit in the fifth row is calculated based on all forst bits. The
second parity bit is calculated based on all second bits, and so on. We then attach the eight
parity bits to the send them to the receiver.

(c) Cyclic Redundancy Check: The third and most powerful of the redundancy checking
techniques if the cyclic redundancy check (CRC). Unlike VRC and LRC, instead of adding
bits together to achieve a desired parity, a sequence of redundant bits, called the CRC and
CRC remainder, is appended to the end of a data unit so that the resulting data unit
becomes exactly divisible by a second, predetermined binary number. At its destination,
the incoming data unit is divided by the same number. If at this step there is no remainder,
the data unit is assumed to be intact and is therefore accepted. A remainder indicated that
the data unit has been damaged in transit and therefore must be rejected.
The redundancy bits used by CRC are derived by dividing the data unit by a predetermined
divisor, the remainder is the CRC. To be valid, a CRC must have two qualities: it must
have exactly one less bit than the divisor, and appending it to the end of the data string
must make the resulting bit sequence exactly divisible by the divisor. Both the theory and
the application of CRC error detection are straightforward. The only complexity is a
deriving the CRC. In order to clarify this process, we will start with an overview and add
complexity as we go. Figure 7.5 provides an outline of the three basic steps.

LOVELY PROFESSIONAL UNIVERSITY 101