Wednesday, December 7th

Quiz the Fifth

On this quiz:

  • Coding theory definitions: codeword, code, alphabet, binary, ternary, n-ary, code and decode, length of a code, Hamming distance, Hamming weight, nearest neighbour decoding, error detection, error correction, information rate (AKA code rate)
  • Coding theory notation: (n,M,d)-code, [n,k,d]-code or [n,k]-code
  • what is a linear code
  • information bits and check bits (or information symbols and check symbols)
  • generating matrix of a linear code (G)
  • parity check matrix of a linear code (H) and how to create it from G
  • the minimum distance of a linear code in terms of minimum Hamming weight
  • coset leaders and syndromes
  • how to code to and decode with a linear code by use of coset leaders and syndromes
  • codes to know, including such things as being able to derive n,M,d etc. :  the triple repetition code (Example 1 page 393), the parity check code (Example 2 page 393), the 2D parity check (Example 3, page 394), the Hamming [7,4] linear code (Example 4, page 395)
  • Bounds on codes:  be able to prove the Singleton Upper Bound (top of page 403).
  • Quantum Key Exchange, be able to explain how it all works, including the basic physics of polarized photons, and be able to implement it as Alice, Bob or Physics
  • Quantum Computing: know mathematically what qubits are (unit vectors) and what operations a quantum computer can perform (unitary transformations).  Be able to do the algebra/math of such a computation, e.g. create a NOT gate or CNOT gate, handle multiple qubits at once.
  • Know the broad outlines of Shor’s algorithm sufficiently for giving a general description of the stages and principles (for example, what role does the quantum fourier transform play, what part does the quantum computer do and what part does the classical computer do afterward).  I can’t ask you to implement it, since you aren’t a quantum computer.