An Incomplete List of Topics for the MA 4891 Final Exam

Below is an annotated list of topics for the final exam. Several sections have a small amount of notes under them you can use to study, and each has where the topic appears either in Hall’s text or in Prof. Martin’s videos and handouts.

If you would prefer this in PDF form (some of the math appears much nicer in it), you can find that here. It updates as often as this page does, as they are generated from the same source (so the PDF funnily contains a link to itself!)

Prepared with much help from Ethan Washock and Gina Quinn.

• Finite fields (Hall Appendix A)
  • Considered prereq, no notes (unless someone wants some)
• Vector spaces (Hall Appendix A)
  • Considered prereq, no notes (unless someone wants some)
• Error detection versus error correction
• Bounds
  • Hamming (Hall 21)
    • Let C be an e-error-correcting code in Aⁿ with |A| = m. Then:
      $$\lvert C \rvert \le \frac{m^n}{\sum_{i=0}^e \binom{n}{i} (m - 1)^i}$$
      
  • Plotkin (Hall 36)
    • TODO notes
  • Singleton (Hall 44)
    • If C is an [n, k] linear code, then d_min(C) ≤ n − k + 1, and |C| ≤ q^{n − d + 1}.
    • A code that meets the Singleton bound with equality is called Maximum Distance Separable (MDS), where every subset of n − k + 1 coordinate positions supports (contains the nonzero entries) a codeword in an MDS code.
      
  • Gilbert-Varshamov (Hall 23)
    • TODO notes
• Perfect codes (Hall 22)
  • A code C which achieves the Hamming bound for
    $$e = \left\lfloor \frac{d - 1}{2} \right\rfloor$$
    
• Channel models (Hall’s intro, 1-6)
  • Prof. Martin’s module
• Maximum likelihood decoding (Hall 8) vs. nearest neighbor decoding (Hall 18)
• Linear codes (Hall Ch. 4)
  • Examples
    • Also see Hamming codes below.
  • Cosets
  • Decoding (see Prof. Martin’s handout)
    • Syndrome decoding (w/ syndromes in Hall 49)
    • Iterative syndrome decoding
  • Dual codes (Hall 42)
    • The dual code of a code C in 𝔽ⁿ, denoted C^⊥, is the set of codewords x such that the dot product of x with any codeword in C is 0. That is:
      C^⊥ = {x∈𝔽ⁿ ∣ x⋅c=0,∀c∈C}
      
    • If C is an [n, k] linear code over 𝔽, then its dual C^⊥ is an [n, n − k] linear code over 𝔽 and C^⊥ ⊥ = C.
• The hexacode
  • Defined over the field 𝔽₄ = {0, 1, α, β}, (where β = α²).
  • Has length 6 and dimension 3.
  • We can write a hexacodeword as three pairs, ab cd ef, allowing us to state an equivalent definition with three rules. That is, a 6-tuple is a hexacodeword if and only if:
    • The one-rule (also used to calculate the slope s ∈ 𝔽_q):
      a + b = c + d = e + f = s
      
    • The alpha-rule:
      a + c + e = a + d + f = b + c + f = b + d + e = αs
      
    • The beta-rule:
      a + c + f = a + d + e = b + c + e = b + d + f = βs
      
  • See Prof. Martin’s worksheet for the following:
    • the 3-problem, the correction of up to three erasures.
    • the 5-problem, the correction of (at max) one error and an erasure.
    • G₂₃
    • the extended binary Golay code (G₂₄)
      • decoding errors and erasures for G₂₄
• Hamming codes (Hall Ch. 5)
  • A linear code over 𝔽_q is a Hamming code of redundency r, written Ham_r(q), if it has a check matrix whose collection of columns contains a unique nonzero scalar multiple of every r-tuple from 𝔽_q (Hall 59).
  • Thm: A Hamming code of redundancy r ( ≥ 2) over the field 𝔽, |𝔽| = q, is a linear
    $$\left[\frac{q^r - 1}{q - 1}, \frac{q^r - 1}{q - 1} - r, 3 \right]$$
    code and is a perfect 1-error-correcting code. (Can you prove it?)
• Evaluation codes (Hall 45)
  • TODO notes
• Reed-Solomon codes (Hall Ch. 6)
  • Decoding: TODO find in Hall, add notes
• Reed-Muller codes (Hall 66)
  • TODO notes
• Quantum error detection
  • Prof. Martin’s module of videos (some linked below)
  • Definition (see module)
  • Knill-Laflamme Theorem

    • Prof. Martin’s video on the theorem

    • The statement of the theorem (I strongly recommend watching the video again for a more in-depth presentation):

      Let Q be a subspace of the n-qubit quantum register A having dimension at least three (n ≥ 2). Let 𝒯 ⊆ Mat_2ⁿ(ℂ) be any set of 2ⁿ × 2ⁿ matrices. Then the following are equivalent:

      1. Q allows correction of all errors in 𝒯.
      2. All errors in 𝒯^†𝒯 = {E^†E′ : E, E′ ∈ 𝒯} are detectable relative to Q.
      3. For all E and E′ in 𝒯, for all x, y ∈ Q, if x ⊥ y, then Ex ⊥ E′y.
      4. For all E and E′ in 𝒯, there exists a constant λ_(E, E′) such that, for all x ∈ Q,
         $$\left<Ex, E'x\right> = \lambda_{(E,E')} \lVert x \rVert^2$$
         
      5. For each E in 𝒯^†𝒯, there is a constant λ_E such that
         π_QEπ_Q = λ_Eπ_Q
         where π_Q is the matrix representing the orthogonal projection of A onto Q.

    • Prof. Martin’s video (continuing) on its proof

• Cyclic codes (Hall Ch. 8)
  • BCH codes (Hall 8.3, starts 111)
  • TODO notes