Scribd Logo
Upload

Welcome to Scribd!

  • 30 views

    Error Detection and Correction: Author: Junian Triajianto (5108 100 038)

    Uploaded by

    Pattrick Arokiasamy
    The document discusses various types of errors that can occur during data transmission and different approaches to detect and correct such errors. It explains that error-correcting codes add redundant bits to allow detection and correction of errors without retransmission, while error-detecting codes only detect errors and require retransmission to correct them. Specifically, it describes Hamming codes which can detect and correct single-bit errors through the use of check bits arranged based on powers of two. The document also provides examples of how Hamming codes and cyclic redundancy checks (CRCs) work to detect errors using polynomial arithmetic operations.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPTX, PDF, TXT or read online from Scribd

    Error Detection and Correction: Author: Junian Triajianto (5108 100 038)

    Uploaded by

    Pattrick Arokiasamy
    30 views23 pages
    The document discusses various types of errors that can occur during data transmission and different approaches to detect and correct such errors. It explains that error-correcting codes add redundant bits to allow detection and correction of errors without retransmission, while error-detecting codes only detect errors and require retransmission to correct them. Specifically, it describes Hamming codes which can detect and correct single-bit errors through the use of check bits arranged based on powers of two. The document also provides examples of how Hamming codes and cyclic redundancy checks (CRCs) work to detect errors using polynomial arithmetic operations.

    Original Title

    errordetectionandcorrection-100419234118-phpapp02

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses various types of errors that can occur during data transmission and different approaches to detect and correct such errors. It explains that error-correcting codes add redundant bits to allow detection and correction of errors without retransmission, while error-detecting codes only detect errors and require retransmission to correct them. Specifically, it describes Hamming codes which can detect and correct single-bit errors through the use of check bits arranged based on powers of two. The document also provides examples of how Hamming codes and cyclic redundancy checks (CRCs) work to detect errors using polynomial arithmetic operations.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    30 views23 pages

    Error Detection and Correction: Author: Junian Triajianto (5108 100 038)

    Uploaded by

    Pattrick Arokiasamy
    The document discusses various types of errors that can occur during data transmission and different approaches to detect and correct such errors. It explains that error-correcting codes add redundant bits to allow detection and correction of errors without retransmission, while error-detecting codes only detect errors and require retransmission to correct them. Specifically, it describes Hamming codes which can detect and correct single-bit errors through the use of check bits arranged based on powers of two. The document also provides examples of how Hamming codes and cyclic redundancy checks (CRCs) work to detect errors using polynomial arithmetic operations.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 23

    Author: Junian Triajianto [5108 100 038]

    ERROR DETECTION
    AND CORRECTION
    What Kind of error?

    DATA SENT

    ≠
    DATA RECEIVED
    DIFFERENT SOURCES
    OF NOISE
    Noise Sources
     Spurious noises, which
    often corrupt the signal
    and can arise from
    thermal noise, cross
    talk, background
    noise, impulse noise
    (i.e. spikes), etc.
    Attenuation
     Attenuation occurs as the signal gradually
    becomes less strong as the distance
    over which it travels increases. This is due to
    the dissipation of energy
    Delay Distortion
     Delay distortion arises as different parts of
    the signal move faster than others
    SOLUTION
    Different Approaches
     Error-correcting codes
     Error-detecting codes
    Error-Correcting Codes
     often referred to as forward error
    correction
     useful when errors frequently
    occur, as it does not require that
    the data be retransmitted
    Hamming Distance
     An n-bit unit containing data and check bits
    is often referred to as an n-bit codeword
     the number of positions at which the

    corresponding bits are different


    between two codewords
     The error-detecting and error-
    correcting properties of a code
    depend on its Hamming distance
    Hamming Distance Examples
     1011101
    1001001
    hamming distance: 2

     1111111
    1101001
    hamming distance: 3
    Parity 1-bit Protection
     add one extra bit of
    information to each data item
     Odd or Even? It’s up to you
     Can Only handle 1-bit error.
     How about 2-bits error? Never
    mind.
    Hamming Code
     The bits that are powers of 2
    (1, 2, 4, 8, 16, etc.) are check
    bits

     The rest (3, 5, 6, 7, 9, etc.) are


    filled up with the m data bits

     Each check bit forces the


    parity of some collection
    of bits, including itself, to
    be even (or odd)
    Hamming Code (Coverage)
    Hamming Code example
     Codeword: 0110101
    Hamming Code Example
    Hamming Code Trick
     The trick so that Hamming
    codes can correct burst
    errors:
     Arrange k consecutive
    codewords in a single matrix.
     Transmit the data one column
    at a time (normally the data
    would be transmitted one row at
    a time).
    Error-Detecting Codes (1)
     Error-correcting codes are widely used on
    wireless links that are noisy.
     However, they generate too large transmission
    overhead for reliable links such as copper wire or
    fiber. Therefore, here error-detection codes are
    used.
     When error is detected, the data is retransmitted.
     The goal for error correcting codes is to add
    redundancy to the data so that the errors are not
    only detected but can be at the same time
    corrected (without retransmission).
    Error-Detecting Codes (2)
     For error-detecting codes the goal is to
    only detect the errors with the minimal
    transmission overhead. They are
    based on polynomial code also known
    as CRC (Cyclic Redundancy Check)
     A k-bit frame is regarded as polynomial
    with coefficients 0 and 1 with terms from
    xk-1 to x0
     For example: 110001 -> x 5 + x4 + x 0
    Polynomial arithmetic is done modulo 2 using the rules of algebraic field theory.
    Both addition and subtraction are identical to exclusive OR. For exampe:

    10011011 11110000
    +11001010 -10100110
    -------------- -------------
    01010001 01010110
    The algorithm for computing the
    checksum
     Let r be the degree of G(x). Append r zero bits to
    the low-order end of the frame so it now contains m
    + r bits and corresponds to the polynomial xrM(x).
     Divide the bit string corresponding to G(x) into the
    bit string corresponding to xrM(x), using modulo 2
    division.
     Subtract the remainder (which is always r or fewer
    bits) from the bit string corresponding to xrM(x)
    using modulo 2 subtraction. The result is the
    checksummed frame to be transmitted. Call its
    polynomial T(x).
    Calculation of the
    polynomial code
    checksum.
    Upon receiving the check-summed frame, the receiver divides it by G(x):

    [T(x) + E(x)] / G(x)

    Since T(x) / G(x) is always zero, the result is always E(x) / G(x).

    The errors containing G(x) as a factor will slip by, all other errors will be caught.

    Single bit errors will be detected:


    We have E(x)=xi for a single bit error,
    E(x) / G(x) will not be zero, since G(x) must have the first and last bit equal to 1.

    All errors consisting of an odd number of inverted bits will be detected


    if G(x) is divisible by (x + 1).
    E(x) consists of odd number of terms, e.g., x5 + x2 + x0
    and therefore, cannot be divisible by (x+1).
    Since E(x) has an odd number of terms E(1)=1.
    If E(x) = (x + 1) Q(x), then E(1) = (1 + 1) Q(1) = 0, a contradiction.

    The polynomial G(x) used in IEEE 802 standard is

    x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x1 + 1

    You might also like