Scribd Logo
Upload

Welcome to Scribd!

  • 59 views

    Cyclic Codes

    Uploaded by

    Shahjahan Afridi
    Hamming codes are linear block codes used for error correction. They add parity bits to information words to create codewords. Parity bits are calculated by adding specific bits of the information word. Codewords are represented as polynomials and cyclic codes are a type of linear block code where cyclic shifts of codewords produce other valid codewords. Cyclic codes can be encoded and decoded using polynomial operations with a generator polynomial. Encoding involves multiplying the information polynomial by the generator polynomial. Decoding uses a syndrome polynomial and error-syndrome table to identify and correct errors.

    Copyright:

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

    Cyclic Codes

    Uploaded by

    Shahjahan Afridi
    59 views15 pages
    Hamming codes are linear block codes used for error correction. They add parity bits to information words to create codewords. Parity bits are calculated by adding specific bits of the information word. Codewords are represented as polynomials and cyclic codes are a type of linear block code where cyclic shifts of codewords produce other valid codewords. Cyclic codes can be encoded and decoded using polynomial operations with a generator polynomial. Encoding involves multiplying the information polynomial by the generator polynomial. Decoding uses a syndrome polynomial and error-syndrome table to identify and correct errors.

    Original Description:

    Cyclic Codes

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Hamming codes are linear block codes used for error correction. They add parity bits to information words to create codewords. Parity bits are calculated by adding specific bits of the information word. Codewords are represented as polynomials and cyclic codes are a type of linear block code where cyclic shifts of codewords produce other valid codewords. Cyclic codes can be encoded and decoded using polynomial operations with a generator polynomial. Encoding involves multiplying the information polynomial by the generator polynomial. Decoding uses a syndrome polynomial and error-syndrome table to identify and correct errors.

    Copyright:

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

    Cyclic Codes

    Uploaded by

    Shahjahan Afridi
    Hamming codes are linear block codes used for error correction. They add parity bits to information words to create codewords. Parity bits are calculated by adding specific bits of the information word. Codewords are represented as polynomials and cyclic codes are a type of linear block code where cyclic shifts of codewords produce other valid codewords. Cyclic codes can be encoded and decoded using polynomial operations with a generator polynomial. Encoding involves multiplying the information polynomial by the generator polynomial. Decoding uses a syndrome polynomial and error-syndrome table to identify and correct errors.

    Copyright:

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

    Block Codes

    (Hamming codes / Cyclic Codes)


    Hamming Codes
    • Hamming codes are (n,k) linear codes having following properties
    𝑛 = 2𝑞 − 1
    𝑘 = 2𝑞 − 𝑞 − 1
    𝑞 ≥ 3 = 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑝𝑎𝑟𝑖𝑡𝑦 𝑏𝑖𝑡𝑠
    • Parity bits:
    • 𝑃1 = 𝑖1 + 𝑖2 + 𝑖3
    • 𝑃2 = 𝑖2 + 𝑖3 + 𝑖4
    • 𝑃1 = 𝑖1 + 𝑖2 + 𝑖4
    • Code-word = 𝑖1 , 𝑖2 , 𝑖3 , 𝑖4 , 𝑃1 , 𝑃2 , 𝑃3
    Information words Codewords
    0000 0000000
    0001 0001011
    0010 0010110
    0011 0011101
    0100 0100111
    0101 0101100
    0110 0110001
    0111 0111010
    1000 1000101
    1001 1001110
    1010 1010011
    1011 1011000
    1100 1100010
    1101 1101001
    1110 1110100
    1111 1111111
    Error checking in hamming codes
    • Consider v = 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 , 𝑣6 , 𝑣7
    • For error-checking find syndrome s = 𝑠1 , 𝑠2 , 𝑠3
    • 𝑠1 = 𝑣1 + 𝑣2 + 𝑣3 + 𝑣5
    • 𝑠2 = 𝑣2 + 𝑣3 + 𝑣4 + 𝑣6
    • 𝑠3 = 𝑣1 + 𝑣2 + 𝑣4 + 𝑣7
    Error-syndrome mapping

    error S
    0000000 000
    0000001 001
    0000010 010
    0000100 100
    0001000 011
    0010000 110
    0100000 111
    1000000 101
    Hamming Coding and Decoding
    • Example: Hamming (7,4) code incur single error, if v= 1011001, find
    bits transmitted
    • Solution:
    • 𝑠1 = 1+0+1+0 = 0
    • 𝑠2 = 0+1+1+0 = 0
    • 𝑠3 = 1+0+1+1 = 1
    • S = 001  error = 0000001
    • Bits transmitted = v + error = 1011001 + 0000001 = 1011000
    Cyclic Codes
    • Cyclic code is a linear code that has the property that a cyclic shift on
    any of its code-word produces another code-word.
    • CW = {𝐶𝑛−1 , 𝐶𝑛−2 , 𝐶𝑛−3 ,………, 𝐶1 , 𝐶0 }
    • CW = {𝐶𝑛−3 , 𝐶𝑛−4 , ……….., 𝐶0 , 𝐶𝑛−1 , 𝐶𝑛−2 } Shift left
    • CW = {𝐶1 , 𝐶0 , 𝐶𝑛−1 ,………, 𝐶3 , 𝐶2 } Shift right
    • Example (7,4) Hamming code
    • 0011101 Left shift by two places results in 1110100 is also a CW
    • 0011101 Right shift by two places results in 0100111 is also a CW
    Polynomial Representation
    • An n-bit (𝑎𝑛−1 , 𝑎𝑛−2 , 𝑎𝑛−3 , ………, 𝑎1 , 𝑎0 ) word can be represented by the
    polynomial
    𝑃 𝑥 = 𝑎𝑛−1 𝑥 𝑛−1 + 𝑎𝑛−2 𝑥 𝑛−2 + 𝑎𝑛−3 𝑥 𝑛−3 +……… + 𝑎1 𝑥 1 + 𝑎0 𝑥 0

    • For example 0011101 can be written as


    𝑃 𝑥 = 𝑎6 𝑥 6 + 𝑎5 𝑥 5 + 𝑎4 𝑥 4 + 𝑎3 𝑥 3 + 𝑎2 𝑥 2 + 𝑎1 𝑥 1 + 𝑎0 𝑥 0
    𝑃 𝑥 = 0𝑥 6 + 0𝑥 5 + 1𝑥 4 + 1𝑥 3 + 1𝑥 2 + 0𝑥 1 + 1𝑥 0
    𝑃 𝑥 = 𝑥4 + 𝑥3 + 𝑥2 + 1
    • Degree of polynomial is the highest power of 𝑥 that has non-zero coefficient
    • Mod-2 operations on polynomials (Add, Multiplication, Division)
    Generator Polynomial Cyclic Encoding
    • The polynomial which is used to generate all code-words

    For CW = {𝐶𝑛−1 , 𝐶𝑛−2 , 𝐶𝑛−3 ,………, 𝐶1 , 𝐶0 }


    𝐺 𝑥 = 𝐶𝑛−1 𝑥 𝑛−1 + 𝐶𝑛−2 𝑥 𝑛−2 + 𝐶𝑛−3 𝑥 𝑛−3 +……… + 𝐶1 𝑥 + 𝐶0 𝑥 0

    • For the first non-zero code-word in (7,4) hamming code 0001011


    𝐺 𝑥 = 𝑥3 + 𝑥 + 1
    • To find new code-word multiply 𝐺 𝑥 with 𝑥
    Non-Systematic Cyclic Encoding
    • When information bits 𝑖 = (𝑖𝑛−1 , 𝑖𝑛−2 , 𝑖𝑛−3 , ………, 𝑖1 , 𝑖0 ) are given, then
    first find 𝑖 𝑥
    𝑖 𝑥 = 𝑖𝑛−1 𝑥 𝑛−1 + 𝑖𝑛−2 𝑥 𝑛−2 + 𝑖𝑛−3 𝑥 𝑛−3 +……… + 𝑖1 𝑥 + 𝑖0

    • Code-word 𝐶 𝑥 = 𝑖 𝑥 ∗ 𝐺 𝑥
    • Example: if i = (0101), find code-word CW
    • 𝑖 𝑥 = 𝑥2 + 1
    • 𝐶 𝑥 = (𝑥 2 + 1)*(𝑥 3 +𝑥 + 1)
    • 𝐶 𝑥 = 𝑥5 + 𝑥3 + 𝑥2 + 𝑥3 + 𝑥 + 1
    • 𝐶 𝑥 = 𝑥 5 + 𝑥 2 + 𝑥 + 1 = 0100111
    Systematic Cyclic Encoding

    • Step 01: Multiply 𝑖 𝑥 with 𝑥 𝑛−𝑘  𝑖 𝑥 *𝑥 𝑛−𝑘

    • Step 02: Divide 𝑖 𝑥 *𝑥 𝑛−𝑘 by 𝐺 𝑥 to find remainder 𝑅 𝑥

    • Step 03: Add 𝑅 𝑥 with 𝑖 𝑥 *𝑥 𝑛−𝑘 to find the code-word

    CW = 𝑖 𝑥 *𝑥 𝑛−𝑘 + 𝑅 𝑥
    Systematic Cyclic Encoding
    • Example: For (7,4) if 𝑖 = (0101), find code-word CW
    • 𝑖 𝑥 = 𝑥2 + 1
    • Step 01: 𝑖 𝑥 ∗𝑥 𝑛−𝑘 = (𝑥 2 + 1)*𝑥 3 = 𝑥 5 + 𝑥 3
    • Step 02: 𝑥 5 + 𝑥 3 / 𝑥 3 + 𝑥 + 1  𝑅 𝑥 = 𝑥 2
    • Step 03: 𝑖 𝑥 ∗𝑥 𝑛−𝑘 + 𝑅 𝑥 = 𝑥 5 + 𝑥 3 + 𝑥 2 = 0101100
    Decoding cyclic codes
    • If the received word is 𝑣 𝑥
    • Step 01: find syndrome polynomial 𝑆 𝑥 = 𝑅′ 𝑥 = 𝑣 𝑥 / 𝐺 𝑥
    • Note: For error-free 𝑣 𝑥 = 𝐶 𝑥 ⇒ 𝑆 𝑥 = 𝑅′ 𝑥 = 0
    𝑣 𝑥 = 𝐶 𝑥 + 𝑒 𝑥 ⇒ 𝑅′ 𝑥 = 𝑣 𝑥 / 𝐺 𝑥
    ⇒ 𝑅′ 𝑥 = (𝐶 𝑥 + 𝑒 𝑥 ) / 𝐺 𝑥 = 𝑒 𝑥 / 𝐺 𝑥

    𝐶′ 𝑥 = 𝑣 𝑥 + 𝑒 𝑥
    Error- Syndrome table
    error E(x) S(x)
    0000000 0 0
    0000001 1 1
    0000010 𝑥 𝑥
    0000100 𝑥2 𝑥2
    0001000 𝑥3 𝑥+1
    0010000 𝑥4 𝑥2 + 𝑥
    0100000 𝑥5 𝑥2 + 𝑥 + 1
    1000000 𝑥6 𝑥2 + 1
    Decoding Cyclic codes
    • Example: Decode the code-word 1010011 of (7,4) codes when error incurred
    is 1000000
    • Solution:
    𝐶 𝑥 = 𝑥6 + 𝑥4 + 𝑥 + 1
    𝑒 𝑥 = 𝑥6
    𝑟𝑒𝑐𝑒𝑖𝑒𝑣𝑒𝑑 𝑠𝑖𝑔𝑛𝑎𝑙 = 𝑣 𝑥 = 𝐶 𝑥 + 𝑒 𝑥 = 𝑥 6 + 𝑥 4 + 𝑥 + 1 + 𝑥 6
    = 𝑥 4 + 𝑥 + 1 = 0010011
    Decoding: 𝑆 𝑥 = 𝑟𝑒𝑚𝑎𝑖𝑛𝑑𝑒𝑟𝑜𝑓 𝑣 𝑥 / 𝐺 𝑥 = 𝑥 2 + 1
    From table 𝑆 𝑥 = 𝑥 2 + 1 corresponds to 𝑒 𝑥 = 𝑥 6
    So 𝐶 ′ 𝑥 = 𝑣 𝑥 + 𝑒 𝑥 = 𝑥 4 + 𝑥 + 1 + 𝑥 6 = 𝑥 6 + 𝑥 4 + 𝑥 + 1 = 1010011

    You might also like