Scribd Logo
Upload

Welcome to Scribd!

  • 107 views

    6 HammingCode

    Uploaded by

    admer
    Hamming code allows for error detection and correction in digital communications. It works by adding check bits to the original data bits such that any single bit error can be detected and corrected. The check bits are calculated using parity checks on subsets of the data bits. When data is received, the check bits are recalculated and compared to the received check bits using XOR to generate a syndrome. If the syndrome is non-zero, it identifies the position of the erroneous bit.

    Copyright:

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

    6 HammingCode

    Uploaded by

    admer
    107 views19 pages
    Hamming code allows for error detection and correction in digital communications. It works by adding check bits to the original data bits such that any single bit error can be detected and corrected. The check bits are calculated using parity checks on subsets of the data bits. When data is received, the check bits are recalculated and compared to the received check bits using XOR to generate a syndrome. If the syndrome is non-zero, it identifies the position of the erroneous bit.

    Original Description:

    error control

    Original Title

    6_HammingCode

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Hamming code allows for error detection and correction in digital communications. It works by adding check bits to the original data bits such that any single bit error can be detected and corrected. The check bits are calculated using parity checks on subsets of the data bits. When data is received, the check bits are recalculated and compared to the received check bits using XOR to generate a syndrome. If the syndrome is non-zero, it identifies the position of the erroneous bit.

    Copyright:

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

    6 HammingCode

    Uploaded by

    admer
    Hamming code allows for error detection and correction in digital communications. It works by adding check bits to the original data bits such that any single bit error can be detected and corrected. The check bits are calculated using parity checks on subsets of the data bits. When data is received, the check bits are recalculated and compared to the received check bits using XOR to generate a syndrome. If the syndrome is non-zero, it identifies the position of the erroneous bit.

    Copyright:

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

    Error Detection / Correction

    Hamming code

    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 detecting Code Example


    Error Detection/correction coding:

    Word:

    With Error:

    With even parity:

    Identifying error:

    Hamming Distance
    The

    Hamming distance is the number of bits that


    have to be changed to get from one bit pattern to
    another.
    Example: 10010101 & 10011001 have a hamming distance of 2
    For

    any coding whose members have a Hamming


    distance of two, any one bit error can be detected.
    Why?

    Hamming Distance
    For any coding whose members have a Hamming distance
    of three, any one bit error can be detected and
    corrected. Why?
    And any two bit error can be detected. Why?

    Error Correcting Code Function

    Syndrome

    Data

    Code

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

    Hamming Code Syndrome


    If we compare the read K bits compared with the write K bits,
    using an EXOR function, the result is called the syndrome.

    If the syndrome is all zeros, there were no errors.


    If there is a 1 bit somewhere, we know it represents an error.

    Hamming Code Design determining K


    To store an M bit word with detection/correction takes M+K bit words
    If K =1, we can detect single bit errors but not correct them
    If 2K - 1 >= M + K , we can detect, identify, and correct all single bit
    errors, i.e. the syndrome contains the information to correct any
    single bit error

    Example: For M = 8:

    and K = 3: 23 1 = 7 < 8 + 3 (doesnt work)


    and K = 4: 24 1 = 15 > 8 + 4 (works!)
    Therefore, we must choose K =4,
    i.e., the minimum size of the syndrome is 4

    Hamming Code Syndrome


    If we compare the read K bits with the write K bits,
    using an exclusive or function, the result is called
    the syndrome.
    - If the syndrome is all zeros, there were no errors,
    i.e. the bits were exactly alike
    - If there is a 1 bit somewhere, we know that 1
    represents an error.

    Increased word length for error correcting

    Hamming Code Syndrome Design Criteria

    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

    SEC-DEC Example
    Requires One Extra Check Bit
    Single Error Correction:
    Word

    With Errors

    With Even Parity

    Identifying Error

    Single Error Correction,


    Double Error Detection:
    Word

    SEC Attempt

    With Even Parity

    IS SEC Correct?

    With Two Errors

    Extra Bit Confirms DE

    Increased word length for error correcting

    You might also like