Scribd Logo
Upload

Welcome to Scribd!

  • 7 views

    Error Detection

    Uploaded by

    Ankur Aggarwal

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Error Detection

    Uploaded by

    Ankur Aggarwal
    7 views28 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    7 views28 pages

    Error Detection

    Uploaded by

    Ankur Aggarwal

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 28

    ERROR DETECTION

    • When data is transmitted from one device to


    another device, the system does not guarantee
    whether the data received by the device is identical
    to the data transmitted by another device.

    • An Error is a situation when the message received


    at the receiver end is not identical to the message
    transmitted.
    TYPES OF ERRORS

    Single-Bit Error:
    The only one bit of a given data unit is changed from 1 to 0 or from 0 to 1.
    Burst Error:
    • The two or more bits are changed from 0 to 1 or from 1 to 0 is known as Burst
    Error.
    • The Burst Error is determined from the first corrupted bit to the last corrupted
    bit.
    • Single-Bit Error mainly occurs in Parallel Data Transmission. For example, if eight
    wires are used to send the eight bits of a byte, if one of the wire is noisy, then
    single-bit is corrupted per byte.

    • The duration of noise in Burst Error is more than the duration of noise in Single-
    Bit.

    • Burst Errors are most likely to occur in Serial Data Transmission.

    • The number of affected bits depends on the duration of the noise and data rate.
    ERROR DETECTING TECHNIQUES:

    The most popular Error Detecting Techniques are:

    • Single parity check


    • Two-dimensional parity check
    • Checksum
    • Cyclic redundancy check
    PARITY CHECK

    • PARITY CHECKING is one method used to check whether data has been
    changed or corrupted following transmission from one device or medium to
    another device or medium.

    • A byte of data is allocated a PARITY BIT. This is allocated before transmission


    takes place.

    • Systems that use EVEN PARITY have an even number of 1-bits; systems that
    use ODD PARITY have an odd number of 1-bits.
    Consider the following byte:

    • If this byte is using even parity, then the parity bit needs to be 0 since there is
    already an even number of 1-bits
    • If odd parity is being used, then the parity bit needs to be 1 to make the number
    of 1-bits odd.

    Therefore, the byte just before transmission would be:

    either (even parity) or (odd parity)


    FIND THE PARITY BITS FOR EACH OF THE FOLLOWING BYTES:

    a 1101101 even parity used


    b 0001111 even parity used
    c 0111000 even parity used
    d 1110100 odd parity used
    e 1011011 odd parity used
    DRAWBACKS OF SINGLE PARITY CHECKING

    • It can only detect single-bit errors which are very rare.


    • If two bits are interchanged, then it cannot detect the
    errors.
    WHICH OF THE FOLLOWING BYTES HAVE AN ERROR
    FOLLOWING DATA TRANSMISSION?

    a 11101101 even parity used


    b 01001111 even parity used
    c 00111000 even parity used
    d 11110100 odd parity used
    e 11011011 odd parity used
    TWO-DIMENSIONAL PARITY CHECK

    • Performance can be improved by using Two-Dimensional Parity


    Check which organizes the data in the form of a table.
    • Parity check bits are computed for each row, which is equivalent to the
    single-parity check.
    • In Two-Dimensional Parity check, a block of bits is divided into rows, and
    the redundant row of bits is added to the whole block.
    • At the receiving end, the parity bits are compared with the parity bits
    computed from the received data.
    The following block of data was received after transmission from a
    remote computer; odd parity being used by both sender and receiver. One
    of the bits has been changed during the transmission stage. Locate where
    this error is and suggest a corrected byte value.
    CHECKSUM

    • Checksum is a calculated value that is used to determine the integrity of data.


    Checksum serves as a unique identifier for the data (a file, a text string, or a
    hexadecimal string).
    • If the data changes then so does the checksum value. This makes it easy to
    verify the integrity of the data.
    • Checksum value is also called hash value. The data that is calculated can be a
    file, a text string, or a hexadecimal string.
    Case-01: Result = 0

    If the result is zero,


    Receiver assumes that no error occurred in the data during the transmission.
    Receiver accepts the data.

    Case-02: Result ≠ 0

    If the result is non-zero,


    Receiver assumes that error occurred in the data during the transmission.
    Receiver discards the data and asks the sender for retransmission.
    The Sender follows the given steps:
    • The block unit is divided into k sections, and each of n bits.
    • All the k sections are added together by using one's complement to get the
    sum.
    • The sum is complemented and it becomes the checksum field.
    • The original data and checksum field are sent across the network.

    The Receiver follows the given steps:


    • The block unit is divided into k sections and each of n bits.
    • All the k sections are added together by using one's complement algorithm
    to get the sum.
    • The sum is complemented.
    • If the result of the sum is zero, then the data is accepted otherwise the data
    is discarded.
    Example: Suppose that the sender wants to send 4 frames each of 8 bits,
    where the frames are 11001100, 10101010, 11110000 and 11000011.
    ECHO CHECK

    • With an echo check, the receiving computer sends a copy of


    the data immediately back to the sending computer for
    comparison.
    • The sending computer compares the two sets of data to
    check if any errors occurred during the transmission process.
    • If an error has occurred, the data will be transmitted again.

    Drawback of echo checks


    • If the two sets of data are different you will have no way of
    knowing whether the error occurred when originally sent, or
    when it was sent back
    • Echo checks require a lot of extra data to be transmitted
    AUTOMATIC REPEAT REQUESTS (ARQS)

    • ARQ uses positive and negative acknowledgements (messages sent to


    the receiver indicating that data has/has not been received correctly) and
    timeout (this is the time interval allowed to elapse before an
    acknowledgement is received)
    • the receiving device receives an error detection code as part of the data
    transmission
    • this is used to detect whether the received data contains any
    transmission errors
    • if no error is detected, a positive acknowledgement is sent back to the
    sending device
    CYCLIC REDUNDANCY CHECK

    • Cyclic Redundancy Check (CRC) is an error detection method.


    • It is based on binary division
    CRC Generator
    • CRC generator is an algebraic polynomial represented as a bit pattern.
    • Bit pattern is obtained from the CRC generator using the following rule-
    The power of each term gives the position of the bit and the coefficient gives the
    value of the bit.
    • Example-

    Consider the CRC generator is x7 + x6 + x4 + x3 + x + 1.


    The corresponding binary pattern is obtained as-

    Thus, for the given CRC generator, the corresponding binary pattern is 11011011.
    • Step-01: Calculation Of CRC At Sender Side-
    • A string of n 0’s is appended to the data unit to be transmitted.
    • Here, n is one less than the number of bits in CRC generator.
    • Binary division is performed of the resultant string with the CRC generator.
    • After division, the remainder so obtained is called as CRC.
    • It may be noted that CRC also consists of n bits.

    • Step-02: Appending CRC To Data Unit-


    • The CRC is obtained after the binary division.
    • The string of n 0’s appended to the data unit earlier is replaced by the CRC remainder.

    • Step-03:Transmission To Receiver-
    • The newly formed code word (Original data + CRC) is transmitted to the receiver.
    • The following two cases are possible-
    • Case-01: Remainder = 0
    If the remainder is zero,
    Receiver assumes that no error occurred in the data during the transmission.
    Receiver accepts the data.

    • Case-02: Remainder ≠ 0
    If the remainder is non-zero,
    Receiver assumes that some error occurred in the data during the transmission.
    Receiver rejects the data and asks the sender for retransmission.
    EXAMPLE:
    A bit stream 10011101 is transmitted using the standard CRC method. The generator polynomial is x3+1.
    • What is the actual bit string transmitted?
    • Suppose the third bit from the left is inverted during transmission. How will receiver detect this error?

    • Solution-

    Part-01:

    • The generator polynomial G(x) = x3 + 1 is encoded as 1001.


    • Clearly, the generator polynomial consists of 4 bits.
    • So, a string of 3 zeroes is appended to the bit stream to be transmitted.
    • The resulting bit stream is 10011101000.
    Now,
    • The code word to be transmitted is obtained by
    replacing the last 3 zeroes of 10011101000 with the
    CRC.
    • Thus, the code word transmitted to the receiver =
    10011101100.
    • Part-02:

    According to the question,


    • Third bit from the left gets inverted during transmission.
    • So, the bit stream received by the receiver = 10111101100.

    Now,
    • Receiver receives the bit stream = 10111101100.
    • Receiver performs the binary division with the same generator polynomial as-
    • The remainder obtained on division is a non-zero
    value.
    • This indicates to the receiver that an error occurred
    in the data during the transmission.
    • Therefore, receiver rejects the data and asks the
    sender for retransmission.

    You might also like