Scribd Logo
Upload

Welcome to Scribd!

  • 73 views

    DCN Error Correction

    Uploaded by

    Vishnu Balachandran
    This document discusses various methods for detecting and correcting errors that may occur when transmitting digital data, including single-bit errors and burst errors. It introduces redundancy-based techniques like parity checks, cyclic redundancy checks (CRC), and checksums that allow detecting errors by comparing the original and received data. More advanced error correction codes like Hamming codes are also presented, which add enough redundant bits to identify and correct single-bit errors during transmission. The document provides examples to illustrate how these different error detection and correction techniques work.

    Copyright:

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

    DCN Error Correction

    Uploaded by

    Vishnu Balachandran
    73 views6 pages
    This document discusses various methods for detecting and correcting errors that may occur when transmitting digital data, including single-bit errors and burst errors. It introduces redundancy-based techniques like parity checks, cyclic redundancy checks (CRC), and checksums that allow detecting errors by comparing the original and received data. More advanced error correction codes like Hamming codes are also presented, which add enough redundant bits to identify and correct single-bit errors during transmission. The document provides examples to illustrate how these different error detection and correction techniques work.

    Original Description:

    the documents covers some part of error correction

    Original Title

    DCN error correction

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses various methods for detecting and correcting errors that may occur when transmitting digital data, including single-bit errors and burst errors. It introduces redundancy-based techniques like parity checks, cyclic redundancy checks (CRC), and checksums that allow detecting errors by comparing the original and received data. More advanced error correction codes like Hamming codes are also presented, which add enough redundant bits to identify and correct single-bit errors during transmission. The document provides examples to illustrate how these different error detection and correction techniques work.

    Copyright:

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

    DCN Error Correction

    Uploaded by

    Vishnu Balachandran
    This document discusses various methods for detecting and correcting errors that may occur when transmitting digital data, including single-bit errors and burst errors. It introduces redundancy-based techniques like parity checks, cyclic redundancy checks (CRC), and checksums that allow detecting errors by comparing the original and received data. More advanced error correction codes like Hamming codes are also presented, which add enough redundant bits to identify and correct single-bit errors during transmission. The document provides examples to illustrate how these different error detection and correction techniques work.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 6

    Error Detection and Correction

    ..
    Asst.Prof.Anan Phonphoem, Ph.D.

    Errors

    Single-Bit

    Burst (Multiple-bit)

    [email protected]
    http://www.cpe.ku.ac.th/~anan
    Computer Engineering Department
    Kasetsart University, Bangkok, Thailand
    1

    Single-bit error

    Burst error (Multiple-bit error)

    How do we know that data is


    corrupted (errors occur)?

    Redundancy

    How to detect the error?


    Does not know at the signal level
    Comparison
    Redundancy

    2 copies of everything (slow, high overhead)


    Extra info.

    Vertical Redundancy Check


    (VRC) - parity
    Detection Methods

    VRC

    LRC

    CRC

    Checksum

    Longitudinal Redundancy
    Check (LRC)

    Example
    Suppose the sender wants to send the word world. In
    ASCII the five characters are coded as
    1110111 1101111 1110010 1101100 1100100
    w

    d
    n bits

    The following shows the actual bits sent

    Can detect n bits burst error


    >n bits can be detected high prob.

    11101110 11011110 11100100 11011000 11001001

    10

    Cyclic Redundancy Check


    (CRC)

    Two-dimensional parity
    (LRC + VRC)

    11

    12

    Binary Division
    in a CRC generator

    Binary Division
    in a CRC checker

    13

    Polynomial

    14

    Polynomial and Divisor

    15

    Choosing the polynomial

    16

    Standard Polynomials

    2 properties
    Should not divisible by x
    Should be divisible by (x+1)
    Example
    Cannot choose x (binary 10) or x2 + x (binary 110)

    Name

    Polynomial

    Application

    CRCCRC-8

    x8 + x2 + x + 1
    x10 + x9 + x5 + x4 + x 2 + 1

    ATM header

    CRCCRC-10

    x16

    ITUITU-16

    Because both are divisible by x.

    x32

    Can choose x + 1 (binary 11)

    ITUITU-32

    Because it is not divisible by x, but is divisible by x + 1.

    x26 +

    x12

    x23

    x5 +

    x22

    x16

    ATM AAL
    HDLC

    x12

    +
    +
    +
    +
    +
    x11 + x10 + x8 + x7 + x5 + x4 + x2
    +x+1

    LANs

    Also choose x2 + 1 (binary 101)


    Because it is divisible by x + 1 (binary division).

    17

    18

    CRC

    Checksum

    Notes:
    Segment
    Add using ones complement
    Sum is complemented

    Very effective detection method


    Can detect all burst of length < degree
    of polynomial
    Detect other errors high prob.

    19

    Data Unit and Checksum

    20

    When the error is detected:

    How can we correct them?

    Discarded and resent


    Automatically correct without resent

    In theory, any error binary code can be


    corrected

    But adding complexity


    Redundancy
    Limited up to 3 errors because of overhead

    21

    Error Correction

    22

    Number of redundancy bit

    Total bit = m+r


    r must be able to indicate all positions
    including no error m+r+1
    r bit can indicate 2r states
    So 2r >= m+r+1
    For ASCII (7bits) m = 7

    23

    24 >= 7+4+1
    24

    Hamming Code

    Hamming Code

    Example: 7-bit ASCII needed r = 4

    25

    Hamming Code

    26

    Example of Hamming Code

    Each bit is
    covered
    by at least
    2 checkers

    27

    Single-bit error

    28

    Error Detection

    29

    30

    Burst Error Correction

    Rearrange the data to become one bit error


    31

    You might also like