Scribd Logo
Upload

Welcome to Scribd!

  • 72 views

    Hamming

    Uploaded by

    Haris Junianto
    This document discusses error detection and correction in computer systems. It introduces parity bits which can detect single-bit errors by making the total number of 1 bits either even or odd. Hamming codes allow for both error detection and correction by adding check bits and generating a syndrome value that identifies the position of any errors. The example shows how a Hamming code uses check bits and syndrome comparison to detect and locate a single-bit error at a specific position in a data word.

    Copyright:

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

    Hamming

    Uploaded by

    Haris Junianto
    72 views10 pages
    This document discusses error detection and correction in computer systems. It introduces parity bits which can detect single-bit errors by making the total number of 1 bits either even or odd. Hamming codes allow for both error detection and correction by adding check bits and generating a syndrome value that identifies the position of any errors. The example shows how a Hamming code uses check bits and syndrome comparison to detect and locate a single-bit error at a specific position in a data word.

    Original Title

    Hamming.ppt

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses error detection and correction in computer systems. It introduces parity bits which can detect single-bit errors by making the total number of 1 bits either even or odd. Hamming codes allow for both error detection and correction by adding check bits and generating a syndrome value that identifies the position of any errors. The example shows how a Hamming code uses check bits and syndrome comparison to detect and locate a single-bit error at a specific position in a data word.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    72 views10 pages

    Hamming

    Uploaded by

    Haris Junianto
    This document discusses error detection and correction in computer systems. It introduces parity bits which can detect single-bit errors by making the total number of 1 bits either even or odd. Hamming codes allow for both error detection and correction by adding check bits and generating a syndrome value that identifies the position of any errors. The example shows how a Hamming code uses check bits and syndrome comparison to detect and locate a single-bit error at a specific position in a data word.

    Copyright:

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

    Error Detection / Correction

    Reference:

    Computer Organization & Architecture


    7th Edition
    William Stallings
    Prentice Hall 2006

    Error Detection / Correction


    Why might we need Error
    detection/correction?
    Even & Odd Parity
    Error detection

    Hamming code
    Used for error detection & error correction

    Parity bits
    ASCII 7 bit code (hex 00 to 7F)
    Could use 8th bit for parity bit:
    X1011010
    Even parity: make total number of 1 bits is even

    01011010
    Odd parity: make total number of 1 bits odd

    11011010
    If a parity bit is added to a bit stream,
    then there is a basis to check for bit(s)
    being corrupted.

    Error Correcting Code Function

    Syndrome

    Data

    Code

    The output of the Compare to the Corrector is termed the syndrome, and is
    K bits long

    Increased word length for error correcting

    A Layout of Data and Check Bits that Achieves Our Design Criteria:

    Bit position

    12

    11

    10

    Bit number

    1100

    1011

    1010

    1001

    1000

    0111

    0110

    0101

    0100

    0011

    0010

    0001

    D8

    D7

    D6

    D5

    D4

    D3

    D2

    C2

    C1

    Data bit
    Check bit

    C8

    D1
    C4

    C1 is a parity check on every data bit whose position is xxx1


    C1 = D1 exor D2 exor D4 exor D5

    exor D7

    C2 is a parity check on every data bit whose position is xx1x


    C2 = D1 exor D3 exor D4 exor D6 exor D7

    C4 is a parity check on every data bit whose position is x1xx


    C4 = D2 exor D3 exor D4

    exor D8

    C8 is a parity check on every data bit whose position is 1xxx


    C8 = D5 exor D6 exor D7 exor D8

    Why this ordering? Because we want the syndrome, the Hamming test word,
    to yield the address of the error.

    Example:
    Data stored = 00111001
    Check bits:

    Putting it together:

    Example:

    Example:
    Word fetched:

    Check Bits:

    Comparing:
    C8 C4 C2 C1
    0 1

    1 1 Orig Check Bits

    0 0 0 1 New Check Bits


    0 1

    Putting it all together:

    1 0 Syndrome

    0110 = 6 bit position 6


    is wrong, i.e. bit D3 is
    wrong

    Increased word length for error correcting

    You might also like