Scribd Logo
Upload

Welcome to Scribd!

  • 31 views

    Error

    Uploaded by

    surendra saini
    - Error detection and correction works by adding extra bits (codewords) to the data that are used to check for errors. - The distance between two codewords is the number of bit positions they differ in. A greater distance allows for detection and correction of more errors. - Parity codes add an extra parity bit to detect odd numbers of errors. Hamming codes add multiple parity bits in specific positions to detect and correct single bit errors. - To correct single errors, the minimum distance between codewords must be 3. The Hamming code assigns parity bits to power of 2 positions to achieve this.

    Copyright:

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

    Error

    Uploaded by

    surendra saini
    31 views8 pages
    - Error detection and correction works by adding extra bits (codewords) to the data that are used to check for errors. - The distance between two codewords is the number of bit positions they differ in. A greater distance allows for detection and correction of more errors. - Parity codes add an extra parity bit to detect odd numbers of errors. Hamming codes add multiple parity bits in specific positions to detect and correct single bit errors. - To correct single errors, the minimum distance between codewords must be 3. The Hamming code assigns parity bits to power of 2 positions to achieve this.

    Original Description:

    Error correction and detection

    Original Title

    error

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    - Error detection and correction works by adding extra bits (codewords) to the data that are used to check for errors. - The distance between two codewords is the number of bit positions they differ in. A greater distance allows for detection and correction of more errors. - Parity codes add an extra parity bit to detect odd numbers of errors. Hamming codes add multiple parity bits in specific positions to detect and correct single bit errors. - To correct single errors, the minimum distance between codewords must be 3. The Hamming code assigns parity bits to power of 2 positions to achieve this.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    31 views8 pages

    Error

    Uploaded by

    surendra saini
    - Error detection and correction works by adding extra bits (codewords) to the data that are used to check for errors. - The distance between two codewords is the number of bit positions they differ in. A greater distance allows for detection and correction of more errors. - Parity codes add an extra parity bit to detect odd numbers of errors. Hamming codes add multiple parity bits in specific positions to detect and correct single bit errors. - To correct single errors, the minimum distance between codewords must be 3. The Hamming code assigns parity bits to power of 2 positions to achieve this.

    Copyright:

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

    ERROR DETECTION AND

    CORRECTION
    Presented by
    Surendra Kumar Saini
    Error Detection and Correction

    • Basic concept:
    – Extra bits are added to the data bits that we want to represent, to get
    codewords.
    – Codewords are divided into two categories: valid codewords and invalid
    codewords.
    – A bit error changes a valid codeword to an invalid codeword.
    • Definition:
    – The distance between two codewords Ci and Cj, denoted by dist (Ci, Cj),
    denotes the number of bit positions in which the codewords differ.
    – Example: distance between codewords 01001 and 11100 is 3.

    2
    Valid Invalid
    Codewords Codewords

    • We can check whether a given codeword is valid or invalid.


    • For detecting single bit error, the distance between any pair of valid
    codewords must be at least 2.
     For detecting k errors, the distance must be at least (k+1).
    • For single error correction, the distance must be at least 3.

    3
    Parity Code for Error Detection
    • The parity of a given binary word is 3-bit Binary Parity
    defined by whether the number of Word Bit
    1’s is odd or even.
    – We can add an extra bit, called parity 0 0 0 0
    bit, to make the number if 1’s in 0 0 1 1
    every valid codeword even (say).
    – An example for 3-bit words is shown. 0 1 0 1
    – Any odd number of bit errors can be 0 1 1 0
    detected.
    1 0 0 1
    1 0 1 0
    1 1 0 0
    1 1 1 1

    4
    Hamming Code for Single Error Correction

    • A code with minimum distance of 2k+1 can detect up to k bit errors.


    • Basic principle of Hamming code:
    – To each group of m information bits, k parity bits are added to form a (m+k)-
    bit code.
    – Each of the (m+k) bit locations in a codeword is assigned a value.
    – k must satisfy the inequality: 2k ≥ m + k + 1 (e.g. for m=4, k will be 3)
    – The parity check bits are assigned position numbers that are powers of 2 (that
    is, 1, 2, 4, …).
    – The parity check bits are computed based on some well-defined formula.

    5
    b1 b2 b3 b4 b5 b6 b7
    Example: Hamming Code
    Dig p1 p2 m1 p3 m2 m3 m4
    for BCD (m=4)
    it p1 = m1  m2  m4 (1, 3, 5, 7)
    0 0 0 0 0 0 0 0 p2 = m1  m3  m4 (2, 3, 6, 7)
    1 1 1 0 1 0 0 1 p3 = m2  m3  m4 (4, 5, 6, 7)
    2 0 1 0 1 0 1 0
    3 1 0 0 0 0 1 1
    1 2 3 4 5 6 7
    4 1 0 0 1 1 0 0
    p3 0 0 0 1 1 1 1
    5 0 1 0 0 1 0 1
    6 1 1 0 0 1 1 0 p2 0 1 1 0 0 1 1
    7 0 0 0 1 1 1 1 p1 1 0 1 0 1 0 1
    8 1 1 1 0 0 0 0
    9 0 0 1 1 0 0 1

    6
    How to correct errors?

    • Calculate the three check bits:


    c1 = b1  b3  b5  b7
    c2 = b2  b3  b6  b7
    c3 = b4  b5  b6  b7
    • If c3c2c1 = 000, there is no error.
    • Else, the bit position of the error is given by c3c2c1.

    Example valid code word is 1001100

    7
    An Exercise
    • Design a Hamming code for m = 5.
    • For 2k ≥ m + k + 1, we get k = 4.
    • The bit assignments are carried out as follows:

    1 2 3 4 5 6 7 8 9
    b1 b2 b3 b4 b5 b6 b7 b8 b9 p 0 0 0 0 0 0 0 1 1
    p1 p2 m p3 m m m p4 m 4
    1 2 3 4 5 p 0 0 0 1 1 1 1 0 0
    3
    p 0 1 1 0 0 1 1 0 0
    2
    p 1 0 1 0 1 0 1 0 1
    1
    8

    You might also like