Skip to content

Classical Linear Codes Over GF(2)

Prerequisites And Diagnostic Checks

You can treat this chapter as covered if you can:

  • compute with GF(2), including 1+1=0
  • describe a binary linear code as a subspace of GF(2)^n
  • explain why C = ker(H) is a parity-check definition
  • derive a simple generator matrix and parity-check matrix for a small code

Why This Matters For Conjecture 3

Conjecture 3 is about compiling QLDPC syndrome extraction, but the objects being compiled are ultimately parity checks. The algebraic language underneath those checks is classical binary linear coding theory.

For you, the useful translation is:

  • a parity-check row is a stabilizer-support pattern
  • a matrix row space is a generated constraint space
  • null spaces and dual spaces are the algebra behind CSS commutativity
  • distance is the minimum size of a nontrivial undetected pattern

Worked Example Before Abstraction

The [7,4,3] Hamming code is the first stable example. It stores 4 information bits in 7 physical bits and has minimum distance 3.

The parity-check matrix H has three rows and seven columns. Each column is a nonzero binary 3-vector. A word c is valid exactly when Hc^T=0.

This is the same pattern as a stabilizer syndrome calculation: a parity-check matrix maps an error pattern to a syndrome.

Formal Takeaway

A binary linear code is a subspace C of GF(2)^n. It can be represented by:

  • a generator matrix G, whose row space is C
  • a parity-check matrix H, whose null space is C

The dual code C^\perp consists of all vectors orthogonal to every vector in C. This duality is the bridge to CSS codes.

What This Does And Does Not Prove

This chapter gives the algebraic vocabulary. It does not yet explain why good QLDPC codes require expansion or why expansion creates a hardware bottleneck.

Active Recall

  • Why does Hc^T=0 define a code?
  • What is the difference between the row space of G and the null space of H?
  • Why is the dual code the natural object for CSS commutativity?

Next-Step Handoff

Move from matrices to graphs: the Tanner graph is what makes parity-check structure visible as locality, degree, and expansion.