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 3, 2025 Solutions
  1. Consider a Binary Symmetric Channel (BSC) with p = 0.01 (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 = 5 bits
    (b) even parity, word length = 6 bits (5 bits of data)
  2. Consider a binary code with codewords of length n = 23 and dimension k = 12. This code can correct three errors or less. It is used with (nonconherent) BFSK modulation over an AWGN channel with SNR = 13 dB.
    (a) Calculate the probability of error p without coding.
    (b) Calculate the probability of decoding error P(E) and estimate the Bit Error Rate (BER).
    (c) What is the coding gain in dB?
  3. Find a basis for the dual space of the binary vector subspace spanned by the set of vectors
    {(10011),(11100),(00111)}
    and determine the vectors in this dual space.
  4. Determine the dimension of the binary vector subspace spanned by the set of vectors
    {(01111),(11001),(01110),(11000)}
  5. Consider the following binary code with 4 codewords
    C = {(011000),(100100),(010111),(101011)}
    (a) Is this code linear? Provide a proof for your answer.
    (b) What is the minimum distance of this code?
    (c) What is the maximum weight for which the detection of all error patterns is guaranteed?
    (d) What is the maximum weight for which the correction of all error patterns is guaranteed?
  6. For the code C in Problem 5, find the maximum likelihood codeword associated with the following received vectors
    (a) r = (100000)
    (b) r = (011111)
    (c) r = (111100)
  7. Find the length, dimension, rate, and minimum distance for the binary linear code with the following generator matrix
    G =
    |111000|
    |001110|
    |100101|
    Determine a systematic generator matrix for this code and give a parity check matrix for this systematic generator matrix.

Assignment 2 - Due February 17, 2023 Solutions
  1. Determine, the length, dimension and minimum distance for the code with parity check matrix
    H =
    |011100|
    |101010|
    |110001|
    Determine a syndrome decoding table for this code and use it to decode the following received vectors
    (a) r = 110011
    (b) r = 111000
  2. Construct an optimal code with length n = 17 and minimum distance d = 4. Provide a systematic generator matrix.
  3. Determine using the Hamming bound if it is possible for (11,5,5) and (10,4,5) codes to exist. If the bound is satisfied, does the code exist?
  4. Does the Gilbert-Varshamov bound (as given in the course slides) verify that a (10,3,5) code exists? Determine by construction whether such a code exists.
  5. Construct a self-dual code with length n = 6. Determine the dimension and minimum distance of this code.
  6. The ISBN-13 code prepends the ISBN-10 code with 3 digits (often 978) and recalculates the parity symbol using the weights 131313131313 as c13 = (10 - (c1 + 3c2 + c3 + … + c11 + 3c12) mod 10) mod 10. Thus, the course textbook by Gazi has ISBN-13 number 978-3-030-33379-9. Provide a proof or counterexample for the following questions.
    (a) Can all single digit errors be detected?
    (b) Can all transpositions of digits be detected?
    (c) Can all erasures be corrected?
  7. (a) Express all the nonzero elements of GF(11) as powers of a single element in GF(11).
    (b) List the possible orders of the elements in the field GF(125) and determine the number of elements in the field that have each allowed order.

Assignment 3 - Due March 10, 2025 Solutions
  1. Construct a representation of GF(32) using the primitive polynomial x5 + x2 + 1.
  2. Using the representation of GF(8) obtained using the primitive polynomial x3 + x + 1 compute the following
    (a) α4 + α2 + α + 1
    (b) (α3 + α2)(α6 + α3)
    (c) α6(α5 + α4) + α2
    (d) (α3x2 + αx + 1)( α5x3 + x + α2)
  3. 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.
  4. For the code in the previous problem
    (a) Construct nonsystematic generator and parity check matrices for the code in the previous problem
    (b) Construct systematic generator and parity check matrices for the code in the previous problem
    (c) Determine the minimum distance
  5. List all the possible dimensions of
    (a) binary cyclic codes of length 21
    (b) binary cyclic codes of length 33
  6. 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) = x9 +x4 + x2 + 1
    (b) m(x) = x7 + x3 + x
  7. Using the generator polynomial in Problem 6, compute the code polynomial and associated codeword vector for the following messages using the systematic encoding technique.
    (a) m(x) = x9 +x4 + x2 + 1
    (b) m(x) = x7 + x3 + x

Assignment 4 - Due March 26, 2025 Solutions
  1. Using the generator polynomial g(x) = x5 + x4 + x2 + 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
  2. Design a systematic encoding circuit and the corresponding syndrome computation circuit for the code C in the previous problem.
  3. Design a CRC-10 (10 bit) code that can detect all odd-weight error patterns. What are the code parameters (n,k,d)? What are the code parameters for packets of size 32 bytes? Compute the fraction of all burst errors of the following lengths detected by this code
    (a) 9
    (b) 10
    (c) 11
    (d) 12
    (e) 13

  4. (a) Let α be an element of order 1023 in GF(1024). Find the conjugates of α with respect to GF(2), GF( 4), and GF(32).
    (b) Determine the degree of the minimal polynomial with respect to GF(2) for field elements of order 9, 21, and 1023.
  5. 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.
  6. 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).
  7. Are there any good binary BCH codes of length 19? Are there any good 8-ary BCH codes of length 19? Provide support for your answers.

Assignment 5 - Due April 4, 2025 Solutions
    (Use the Galois field representations 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 = (100100000000000)
      (b) r = (001110010000000)
    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. Decode the following received vectors.
      (a) r = (0101010000000000000000000000000)
      (b) r = (1111011000000011011000000000000)
    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 binary BCH code in Problem 3. Decode the following received words where f indicates the presence of an erasure.
      (a) r = (0f000f00f000000)
      (b) r = (0001100fff00100)