Scribd Logo
Upload

Welcome to Scribd!

  • 14 views

    Assgn2 Soln PDF

    Uploaded by

    toxiccyber471
    assgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdf

    Copyright:

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

    Assgn2 Soln PDF

    Uploaded by

    toxiccyber471
    14 views2 pages
    assgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdf

    Original Title

    assgn2_soln.pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    assgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdf

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    14 views2 pages

    Assgn2 Soln PDF

    Uploaded by

    toxiccyber471
    assgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdfassgn1_soln.pdf

    Copyright:

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

    An introduction to coding theory

    Assignment-2 Solutions
    February 8, 2017

    Solution 1: (b) Minimum distance of a linear block code dmin is equal to the minimum number of columns of parity
    check matrix H that add up to a zero vector. The generator matrix given in the problem is in systematic form, i.e.,
    G = [P : In ]. Therefore, the parity check matrix H in systematic form [In−k : PT ]. The parity check matrix is given
    by
     
    1 0 0 1 1 0
    H= 0 1 0 1 1 1 
    0 0 1 0 1 1

    In this matrix, E.g. columns 3, 4, 5 add up to a zero vector. Hence, the minimum distance of the code is 3.

    Solution 2: (b) A code with minimum distance dmin can detect dmin − 1 errors. Here, dmin = 3 and there-
    fore, this code can detect 2 bit errors.

    Solution 3: (a) The code has a minimum distance of 3. Therefore it can only correct b dmin2 −1 c = 1 bit er-
    ror.

    Solution 4: (a) A code with minimum distance dmin can simultaneously detect λ errors and correct l errors if
    and only in dmin ≥ λ + l + 1. In this problem, we have dmin = 3, λ = 1 and l = 1. Therefore, the statement is true.

    Solution 5: (b) A code with minimum distance dmin can simultaneously correct ν errors and e erasures if and
    only if dmin ≥ 2ν + e + 1. In this problem we have dmin = 3, ν = 1, and e = 1. Therefore, the statement is false.

    Solution 6: (a) The undetected error probability is given by:


    n
    X
    Pu (E) = Ai pi (1 − p)n−i (1)
    i=1

    where Ai = Number of codewords with Hamming weight i.


    p = Crossover probability of binary symmetric channel (BSC).
    Table 1 shows the set of possible codewords generated using G.

    u2 u1 u0 v5 v4 v3 v2 v1 v0 Weight
    000 000000 0
    001 011001 3
    010 111010 4
    011 100011 3
    100 110100 3
    101 101101 4
    110 001110 3
    111 010111 4

    Table 1: Set of codewords generated by G.

    Therefore we have A0 = 1, A1 = 0, A2 = 0, A3 = 4, A4 = 3, A5 = 0, and A6 = 0. Using these values and the


    formula in eq. (1), we can find the undetected error probability Pu (E).

    1
    Solution 7: (b) If two error patterns belong to same coset, they would have same syndrome s = eHT . In this
    problem, the syndromes corresponding to 010000 and 110000 are 001 and 011 respectively. Therefore, they do not
    belong to same coset.

    Solution 8: (c) For a received codeword r, the syndrome s can be calculated by s = rHT . For r = (1 0 0 0 0 1), we
    will have s = (1 0 0).

    Solution 9: (c) Equivalent parity check matrix H in the systematic form [PT : In−k ] can be obtained by ele-
    mentary row operations.
         
    0 0 0 1 0 1 1 0 1 1 0 0 1 0 1 1 0 0
    R1 :=R1 +R2 exchange R2 , R3
    H =  1 0 1 0 0 1  −−−−−−−−→  1 0 1 0 0 1  −−−−−−−−−−→  0 1 0 1 1 0 
    0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 0 1
     
    1 0 1 1 0 0
    R :=R2 +R1
    −−2−−−− −−→  1 1 1 0 1 0  = [PT : In−k ]
    1 0 1 0 0 1

    Therefore, the generator matrix G in systematic form is


     
    1 0 0 1 1 1
    G = [In : P] =  0 1 0 0 1 0 
    0 0 1 1 1 1

    Solution 10: (a) The codeword for information sequence u = [0 1 1] is


     
    1 0 0 1 1 1
    c = uG = [0 1 1]  0 1 0 0 1 0  = [011101]
    0 0 1 1 1 1

    You might also like