ECE 405/511
Error Control Coding


Assignment Submission


Assignments should be submitted on Brightspace https://bright.uvic.ca/d2l/home

Assignments


Assignment 1 - Due February 1, 2023 Solutions
  1. Consider a Binary Symmetric Channel (BSC) with p = 0.1 (the probability that a bit is received in error). Compute the probability that a received word contains undetected errors given the following coding schemes
    (a) no coding, word length = 8 bits
    (b) even parity, word length = 8 bits (7 bits of data)
  2. Consider a binary code with codewords of length n = 23. This code can correct three errors or less. Calculate the probability of decoding error P(E) and estimate the Bit Error Rate (BER) if this code is used over a BSC with
    (a) p = 0.1
    (b) p = 0.01
    (c) p = 0.001
    (d) p = 0.0001
  3. Determine the dimension of the binary vector space spanned by the set of vectors
    {(001010),(101000),(001100),(100010),(011111)}
  4. Find a basis for the dual space of the binary vector space spanned by the set of vectors
    {(11100),(01110),(00111)}
    and determine the vectors in this dual space.
  5. Consider the following binary code with 4 codewords
    C = {(00100),(10010),(01001),(11111)}
    (a) What is the minimum distance of this code?
    (b) What is the maximum weight for which the detection of all error patterns is guaranteed?
    (c) What is the maximum weight for which the correction of all error patterns is guaranteed?
    (d) Is this code linear? Provide a proof for your answer.
  6. For the code C in Problem 5, find the maximum likelihood codeword associated with the following received vectors
    (a) r = (10110)
    (b) r = (01010)
  7. Find the length, dimension and minimum distance for the binary linear code defined by the following parity-check matrix
    H =
    |1010001|
    |1001100|
    |0001011|
    |1101001|
    Also find a generator matrix for this code.

Assignment 2 - Due February 13, 2023 Solutions
  1. Consider the binary code defined by the generator matrix
    G =
    |111000|
    |001110|
    |100101|
    (a) Determine a systematic generator matrix for this code.
    (b) Determine a parity check matrix for the generator matrix obtained in (a).
  2. Determine the length, dimension, and minimum distance of the family of extended binary Hamming codes.
  3. Write out the codewords in the extended binary Hamming code with n-k=4 and verify the minimum distance obtained in Problem 2. Is this code self-dual? Justify your answer.
  4. For the binary linear code with parity check matrix
    H =
    |100011|
    |010101|
    |001111|
    (a) Determine the length, dimension and minimum distance of the code.
    (b) Find a generator matrix for this code.
    (c) Determine a syndrome decoding table for this code and use it to decode the following received vectors
    1. r = 110111
    2. r = 011001
  5. Determine using the Hamming bound if it is possible for a binary (9,4,5) code to exist.
  6. Does the Gilbert-Varshamov bound verify that a binary (9,2,6) code exists? Can such a code be constructed?
  7. The ternary Hamming codes have parameters n = (3m-1)/2, k = n - m, and dmin = 3. Show that these codes are perfect.

Assignment 3 - Due March 10, 2023 Solutions
  1. List the possible orders of the elements in the field GF(81) and determine the number of elements in the field that have each allowed order.
  2. Construct a representation of GF(32) using the primitive polynomial x5+x3+1.
  3. Using the representation of GF(8) given in Table B.3 on page 346 of Essentials of Error Control Coding, compute the following.
    (a) α4 + α2 + α + 1
    (b) (α3 + α2)(α6 + α3)
    (c) α6(α5 + α4) + α2
    (d) (α3x2 + αx + 1)( α5x3 + x + α2)
  4. Express the following as products of binary irreducible polynomials.
    (a) x5 +1
    (b) x7 +1
    (c) x15 +1
  5. Let C be the binary cyclic code of length 15 generated by g(x) = x5 + x4 + x2 + 1.
    (a) Show that g(x) is a valid generator polynomial.
    (b) Compute the parity check polynomial for C.
    (c) Determine the dimension of C and the number of codewords in C.
  6. Construct generator and parity check matrices for the code in the previous problem.
  7. List all the possible dimensions of binary cyclic codes of length 33.

Assignment 4 - Due March 24, 2023 Solutions
  1. Let C be the binary cyclic code of length 15 generated by g(x) = x5 + x4 + x2 + 1. Compute the code polynomial and associated codeword vector for the following messages using the polynomial multiplication encoding technique.
    (a) m(x) = x2
    (b) m(x) = x8 +x7 + x6 + x5 + x4
  2. Using the generator polynomial in 1, compute the code polynomial and associated codeword vector for the following messages using the systematic encoding technique.
    (a) m(x) = x2
    (b) m(x) = x8 +x7 + x6 + x5 + x4
  3. Using the generator polynomial in 1, compute the syndrome s(x) and associated syndrome vector for the following received polynomials
    (a) r(x) = x10
    (b) r(x) = x8 + x6 + x +1
  4. Design a systematic encoding circuit and the corresponding syndrome computation circuit for the code C in 1.
  5. Design a CRC-6 (6 bit) code which can detect all odd-weight error patterns. What are the code parameters (n,k,d)? Compute the fraction of all burst errors of the following lengths detected by this code
    (a) 5
    (b) 6
    (c) 7
    (d) 8
    (e) 9
  6. Consider a binary narrow-sense BCH code of length 15 and design distance 3.
    (a) Compute a generator polynomial for this code.
    (b) Determine the rate of this code.
    (c) Construct generator and parity check matrices for this code.
  7. Consider a binary BCH code of length 15 and design distance 4.
    (a) Compute a generator polynomial for the corresponding narrow-sense code.
    (b) Compute a generator polynomial for the corresponding code with the highest possible rate through appropriate selection of the consecutive roots.
    (c) Compare the rates of the codes in (a) and (b).

Assignment 5 - Due April 6, 2023 Solutions
    (Use the Galois fields representation given here: WickerTables)
    1. Compute a generator polynomial for a binary BCH code of length 21 and design distance 8. What is the rate of this code? Compare this with the rate of the best known linear code for the same length and distance at: www.codetables.de.
    2. Determine the parameters (n,k) for the narrow-sense binary BCH codes of length 51 and odd design distances. Provide the generator polynomials in terms of the minimal polynomials Mi(x).
    3. Consider the double error correcting narrow-sense binary BCH code of length 15 with generator polynomial g(x) = 1+ x4 +x6 + x7 + x8. Use Peterson's technique to decode the following received vectors.
      (a) r = (010000000000000)
      (b) r = (001110110000000)
    4. Consider the triple error correcting narrow-sense binary BCH code of length 31 with generator polynomial g(x) = 1+ x+ x2 +x3 + x5 + x7 + x8 +x9 + x10 + x11 +x15. Use Peterson's technique to decode the following received vectors.
      (a) r = (1010000000000000000000000000000)
      (b) r = (1100000101101100011000000000000)
    5. Consider a narrow-sense Reed-Solomon code of length 15 and design distance 3.
      (a) Compute a generator polynomial for this code.
      (b) Determine the rate of this code and the number of codewords.
      (c) Construct generator and parity check matrices for this code.
    6. Compute a generator polynomial for a narrow-sense double error correcting Reed-Solomon code of length 31.
    7. Consider the double error correcting narrow-sense Reed-Solomon code of length 7 over GF(8) with generator polynomial g(x) = (x-α)(x-α2)(x-α3)(x-α4) = x4 +α3x3 + x2+ αx + α3. Use the Berlekamp-Massey algorithm to decode the received word r = (0α511α5α20) where the lowest degree symbol is on the left. Draw the linear feedback shift register (LFSR) defined by the connection polynomial and verify that it generates the desired syndromes.