Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Math 422 Midterm Winter 2020

Problem 1 [12 pts] Let C be the linear [7, k, d] code over F2  with generator matrix

(i) Find k and the number of codewords in C , with justification.

(ii) Find a parity check matrix for C in standard form. Hint: to check if you’ve made mistakes, multiply your parity-check matrix by the transpose of the given generator matrix.

(iii) Is C a Hamming code? Justify your answer.

(iv) Encode the message [1111].

(v) Suppose a codeword from C is sent and you receive the vector y = [0 0 0 0 1 1 0]. Decode y using syndrome decoding.  Show your work by computing the syndrome of y with respect to the parity check matrix you found in part (ii) of this problem. Hint: this can be done without writing down a syndrome table.

Problem 2 [10 pts] Consider the 3-ary (defined over Z/3Z) code

. Note that we are listing all of the codewords of C here. Also, double check your work to catch mistakes.

(i) Determine d(C). Show your work.

(ii) How many errors can C detect? How many errors can C correct?

(iii) Suppose a codeword is transmitted and y = [10001] is received.  Decode y using nearest neighbor decoding if possible. If it is not possible (or ambiguous as we called it in class), then explain why it is not possible.

Problem 3 [10 pts]

(i) Does there exist a digit ? such that

0 一 13 一 1?9139 一 9

is an ISBN-10 code? Find the digit ? if it is possible. Otherwise, explain why it is not possible.

(ii) Find all xl, x2  such that                                                 xl 一 13 一 32x2870 一 0

is an ISBN-10 code. Your answer will involve finding a relation between xl  and x2 .

Problem 4  [10 pts] Let q  = p   for some prime p  ↓ N and α  ↓ N. We can consider the fi- nite field Fg  with q elements.

(i) Let n ↓ N. Briefly, define the Hamming code Ham(n, q) along with an associated Hamming matrix H.

(ii) Let n  ↓ N and set m  =  (qn  一 1)/(q 一 1). Let C be a q-ary linear  [m, m 一 n, 3] code (this means that C ↓ Fg(m), dim(C) = m 一 n, and d(C) = 3). Prove that C is isomorphic to Ham(n, q). Hint: what can you say about a parity-check matrix for C, and how does this relate to the definition of a Hamming matrix