UNIT
I
Network architecture – layers – Physical
links – Channel Access on links– Hybrid multiple access techniques – Issues
in the data link layer –Framing – Error correction and detection – Link-level
flow control
Error
Detection and Correction
Data can be
corrupted during transmission. For reliable communication, errors must be
detected and corrected.
Types
of Errors
Single-bit
error
The term Single-bit error means that only one bit of a given data unit
(such as byte, character, data unit or packet) is changed from 1 to 0 or from 0
to 1.
Burst
Error
The term Burst Error
means that two or more bits in the data unit have changed from 1 to 0 or from 0
to 1.
Redundancy
One method is to
send every data twice, so that receiver checks every bit of two copies and
detect error.
Drawbacks
Sends n-redundant bits for n-bit message.
Many errors are
undetected if both the copies are corrupted. Instead of adding entire data, some
bits are appended to each unit. This is called redundant bit because the bits
added will not give any new information. These bits are called error detecting
codes.
The three error detecting techniques
are:
1.
Parity
check
2.
Check
sum algorithm
3.
Cyclic
Redundancy Check
Parity
Check
Simple
parity check
Only one redundant
bit, called parity bit is added to every data nit so that the total number of
1’s in unit become even (or odd)
Two
Dimensional Parity
- It is based on simple parity.
- It performs calculation for each bit position across each byte n the frame.
- This adds extra parity byte for entire frame, in addition to a parity bit for each byte.
- Two-dimensional parity catches all 1-, 2-, and 3-bit errors and most 4-bit errors
Fig: Two-dimensional
parity
For example frame containing 6 bytes of data. In this third bit of the
parity byte is 1 since there are an odd number of 1’s is in the third bit
across the 6 bytes in the frame.
In this case, 14
bits of redundant information are added with original information.
Example
for two-dimensional parity
Check
sum algorithm
- In the sender side all the words are added and then transmit the result of sum called checksum with the data.
- The receiver performs the same calculation on the received data and compares the result with the received checksum.
- If any transmitted data, including the checksum itself, is corrupted, then the results will not match, so the receiver knows that an error occurred.
- Instead of sending the checksum as such, one’s complement of that sum will be send to the receiver. If the receiver gets the result as zero then it will be the correct one.
- In this, we can represent unsigned number from 0 to 2n using n bits.
- If the number has more than n bits, the extra leftmost bits need to be added to the n rightmost bits.
- Data can be divided in to 16 bit word and the Checksum is initialized to zero.
Cyclic
Redundancy Check
· Reduce
the number of extra bits and maximize protection
· Given
a bit string 110001 we can associate a polynomial on a single variable x
for it. 1.x5+1.x4+0.x3+0.x2+0.x1+1.x0 = x5+x4+1 and the degree is 5.A k-bit
frame has a maximum degree of k-1.
· Let
M(x) be a message polynomial and C(x) be a generator polynomial
· Let
M(x)/C(x) leave a remainder of 0.
· When
M(x) is sent and M’(x) is received we have M’( x) = M(x)+E(x).
· The
receiver computes M’(x)/C(x) and if the remainder is nonzero, then an error has
occurred.
·
The
only thing the sender and the receiver should know is C(x).
Fig: CRC
Calculation using Polynomial Long Division
Six
generator polynomials that have become international standards are:
– CRC-8 = x8+x2+x+1
– CRC-10 = x10+x9+x5+x4+x+1
– CRC-12 = x12+x11+x3+x2+x+1
– CRC-16 = x16+x15+x2+1
– CRC-CCITT = x16+x12+x5+1
– CRC-32 = x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+ x+1
Error
Correction
Error
Correction can be handled in two ways
1.
When an error is discovered, the receiver can have the
sender to retransmit the entire data unit.
2.
A receiver can use an error correcting code, which
automatically correct certain errors.
Forward
Error Correction
Error correcting
codes are more sophisticated than error-detection codes and require more
redundancy bits.
In
single bit error detection only two states are sufficient.
1) Error
2) No error
Two
states are not enough to detect an error but not to correct it.
Redundancy
Bits
- To calculate the number of redundancy bit(r) required to correct a given number of data bits (m), we must find a relationship between m and r.
- Add m bits of data with r bits. The length of the resulting code is m+r.
- If the total numbers of bits are m+r, then r must be able to indicate at least m+r+1 different states. r bits can indicate 2r different states. Therefore, 2r must be equal to or greater than m+r+1
- 2r >=m+r+1
- For example if the value of m is 7 the smallest r value that can satisfy this equation is 4.
Relationship
between data and redundancy bits
Hamming
Code
R.W.
Hamming provides a practical solution for the error correction.
Positioning
the Redundancy Bits
For example, a
seven-bit ASCII code requires four redundancy bits that can be added to the end
of the data or intersperse with the original data bits. These redundancy bits
are placed in positions 1, 2, 4 and 8. We refer these bits as r1, r2, r3 and r4
Position
of redundancy bits in Hamming code
The combination used
to calculate each of the four r values for a seven-bit data sequence are as
follows
- The r1 bit is calculated using all bits positions whose binary representation include a 1 in the rightmost position
- r2 is calculated using all bit position with a 1 in the second position and so on
r1: bits 1,3,5,7,9,11
r2: bits 2, 3, 6, 7,
10, 11
r3: bits 4, 5, 6, 7
r4: bits 8, 9, 10, 11
Redundancy
bits calculation
Calculating
the r values
- Place each bit of the original character in its appropriate position in the 11-bit unit.
- Calculate the even parities for the various bit combination.
- The parity value for each combination is the value of the corresponding r bit.
For
example:
- The value of r1 is calculated to provide even parity for a combination of bits 3,5,7,9 and 11.
- The value of r2 is calculated to provide even parity with bits 3, 6, 7, 10 and 11.
- The value of r3 is calculated to provide even parity with bits 4,5,6 and 7.
- The value of r4 is calculated to provide even parity with bits 8,9,10 and 11.
Error
detection
- Then it assembles the new parity values into a binary number in order of r position (r8, r4, r2, r1).
- This step gives us the binary number 0111(7 in decimal) which is he precise location of the bit in error.
- Once the bit is identified, the receiver can reverse its value and correct the error.
Burst
Error Correction
- Hamming code cannot correct a burst error directly. it is possible to rearrange the data and then apply the code.
- Instead of sending all the bits in a data unit together, we organize N units in a column and then send the first bit of each, followed by the second bit of each and so on.
- If a burst error of M bits occurs (M<N). then the error does not corrupt M bits of one signal unit; it corrupts only 1 bit of a unit.
- With hamming scheme, we can correct the corrupted bit in each unit.
Burst
Error correction example:
