Coding and Cryptography

Question 1

(i) Define a linear binary code, defining n, k, and d.
(ii) What is the information rate?
(iii) Define the dual code of a linear code, and show that the rank(C)+rank(C^perp)=n, and (C^perp)^perp=C.
(iv) Define the generator matrix and parity check matrix and explain how C can be found from these.
(v) Define equivalence of codes, and prove every code is equivalent to one with generator matrix (I_K | B).

Question 2

(i) Define the d’th Hamming code.
(ii) Find the min-dist of H_d and the rank of H_d.
(iii) Show that Hamming codes are perfect.

Question 3

(i) Define a Reed-Muller code RM(d,r).
(ii) Prove the vectors v_{i_1} intersect … v_{i_s}, 1 <= i_1 < i_2 < .. < i_s <= d, 0 <= s <= d are a basis of F_2^n. Deduce the rank of RM(d,r).
(iii) Define the bar product of linear codes. What is the condition that you always forget?
(iv) Find the rank and min-dist of a bar product.

Question 4

Prove that

(i) RM(d,r)=RM(d-1,r)|RM(d-1,r-1), 0 < r < d
(ii) RM(d,r) has min distance 2^(d-r).

What is the info rate of RM(d,r)?

Question 5

(i) Define a cyclic code and biject the cyclic codes of length n with ideals of a certain quotient ring. Then explain how this corresponds to a single polynomial satisfying some property. Properly define the generator poly, and explain why it is trivially unique.

(ii) Find a basis of a cyclic code in terms of the generator poly.
(iii) Find the generator matrix given the generator poly. What is the parity check matrix?
(iv) Given the factorization of x^n-1 in F_2, how many cyclic codes are there?

Question 6

(i) What is the cyclic code of length n with defining set A? Do not forget the many things behind this definition.
(ii) Define the BCH code with design distance delta.
(iii) Prove that the BCH code has min-dist at least what you expect it to be.

Answer 6

(i) Let n be odd, and let K=F_{2^r}. Consider the set of n’th roots of 1 in K. When is there a prim n’th root in K? Since K* = C_{2^r-1}, this happens iff n|2^r-1. Let A a subset of the n’th roots of 1. We define the cyclic code with defining set A as the polys in K[X]/(X^n-1) which vanish on A.
(ii) The BCH code takes A={alpha,alpha^2,…,alpha^{delta-1}}, where alpha a prim-n’th root of 1.
(iii) Consider H, the matrix with (delta-1) rows, the i’th row being 1, alpha^i, alpha^2i, …, alpha^{(n-1)i}. Note that the elements of C are precisely the kernel of H, which are dependency relations on the n columns. Note that if we take any delta-1 of these columnst , we get a vandermonde-matrix which is non-singular. Hence the weight is at least delta.

Question 7

There is a section on decoding BCH codes that is pure torture.

Question 8

(i) Define a general feedback shift register and a linear feedback shift register
(ii) Define a stream.
(iii) Define the aux. poly & feedback poly of a LFSR, the generating poly of a stream.
(iv) What is a relation between G and the feedback poly p^{inverted hat} that looks really cool at first glance but is actually trivial?

Question 9

Describe the Berlekamp-Messey method and give an example for the code
110001110001

Question 10

Describe the Rabin cryptosystem. Show that breaking the Rabin cryptosystem is essentially as difficult as factoring N.

Question 11

Describe the RSA cryptosystem.

Question 12

Describe the Diffie-Hellman key exchange.

Question 13

State and Prove Gibb’s Inequality

Question 14

State and Prove Kraft’s Inequality I, and II.

Question 15

State and prove Macmillan’s Inequality. Explain what this means for the theory of decodable codes.

Question 16

Describe Huffman’s algorithm and prove that it gives an optimal code.

Question 17

Describe Huffman’s algorithm and prove that it gives an optimal code.

Question 18

State and Prove Shannon’s Noiseless coding theorem

Question 19

State and Prove Shannon’s Noiseless coding theorem

Question 20

State and prove the Sphere-Packing or Hamming bound.

State and prove the GSV bound.

Question 21

Things about entropies:

i) Define H(X), H(X|Y
(ii) Show that H(X)=H(X|Y)+H(Y)