Problem 1:

a)State whether the following is TRUE or FALSE. (2 Marks)

  1. A (7,4) code whose parity check matrix H has a row of all 1’s meansall codewords have an even weight (TRUE)
  1. Any irreducible polynomial is primitive(FALSE)
  1. Any irreducible polynomial of degree m is divides Xn+1 where n=2m-1

(FALSE)

  1. The polynomial X10+X6+X4+X2+1 is a primitive polynomial(FALSE)

b)The following operations on rows or columns of the generatormatrix G or the parity-check matrix H may result in an INCREASE (I), DECREASE (D) orNO CHANGE (N) of the minimum Hamming weight (dmin) of alinear block code.Next to each operation, circle ALL the possible outcomes that might occur to the minimum Hamming weight as a result of such operation (4 Marks)

Adding onerowofG to another row of G and conserving the number of rows / (IDN )
Exchanging two columns of H. / (IDN )
Deleting a column of G. / (IDN )
Deleting a row of H. / (IDN )
Adding one column of H to another column of H and conserving the number of columns / (IDN )
Exchanging two columns of G. / (IDN )
Deleting a column of H. / (IDN )
Deleting a row of G. / (IDN )

Problem 2:

A certain (10,3) binary linear block code has a systematic generator matrix (6 Marks)

  1. Find the weight distribution of the code
  1. Find dmin
  1. What is the error correction capability of this code
  1. If the code is used for error detection only, what is the probability of undetected errors if probability of channel error is p = 0.1

Problem 3:

Consider a block code Cconstructed to encode a message of length k = 3. The encoding process in Cis conducted over two steps. In the first step an even paritycode (the number of ones should be even) is applied to the message. Following that a (7,4) Hamming code is used with the generator matrix:

  1. What is the rate of the code C
  1. Find a generator matrix that could construct the code C in one step.

Problem 4:

a)Calculate the syndrome s(X) of an error in bit position 1(i.e., coefficient X1) of a codewordin an (n,k) cyclic code. (3 Marks)

b)Let g(X)=X8+X6+X4+X2+1 be a polynomial over the binary field. Find the lowest rate cyclic code whose generator is g(X). What is the rate of this code. Find dmin of this code. (3 Marks)

c)Consider a cyclic code of rate 5/8 (Hint: Decompose X8+1 to find the generator polynomial)

(9 Marks)

  1. Write down the generator matrix
  1. Write down the parity check matrix
  1. Draw the ENCODER CIRCUIT

  1. Use the ENCODER CIRCUIT to encode if X4+X+1 in systematic form

Input / Register Contents
Initial / 0 0 0
1 / 1 1 1
0 / 1 0 0
0 / 0 1 0
1 / 1 1 0
1 / 1 0 0

Problem 5:

Consider the generator matrix that generates a code of length 16 with the generator matrix:

Consider the following details about such code where Ai is the number of codewords of weight i

-A16 = 1,

-A6 = 0,

-A12 = 4

  1. Prove that all codewords have even weight
  1. What is dmin of this code (Explain your answer)

Prove that this code is a cycle code (hint: use features of g(x) to prove that)

Problem 6:

Consider the syndrome table shown below. Does a linear block code exist with this syndrome to coset leader mapping? If your answer is “yes”, give any one of the following: the code’s generator matrix, parity check matrix, or codewords. If your answer is “no”, explain why such a code does not exist and correct the syndrome columns such that the table becomes valid? (6 Marks)

Syndrome / Coset Leader
0 0 0 / 0 0 0 0 0
0 0 1 / 1 0 0 0 0
0 1 0 / 0 1 0 0 0
0 1 1 / 0 0 0 1 1
1 0 0 / 0 0 1 0 0
1 0 1 / 0 0 0 1 0
1 1 0 / 0 0 0 0 1
1 1 1 / 1 0 0 0 1

Extra Sheet 1:

Extra Sheet 2:

1