Building and Analyzing Linear Codes

Hello! Welcome to your ninth lesson in the "Quantum Error Correction Fundamentals" module.

In the last few lessons, we've gone deep into the mechanics of a specific, powerful quantum code: the 9-qubit Shor code. We built it from the ground up, from encoding to syndrome measurement and finally to decoding and correction. You'll have noticed that the Shor code cleverly combines two simpler ideas: a 3-qubit code for bit-flips and another for phase-flips. These underlying codes behave very much like classical error-correcting codes.

This observation provides the motivation for today's lesson. To build more sophisticated and efficient quantum codes, we first need a solid grasp of their classical counterparts. We will therefore step back from the quantum realm for a moment to explore the mathematical framework of classical linear codes.

Our learning outcome for this lesson is to: Construct a classical linear code from its generator matrix, verify its parameters, and derive the parity-check matrix of its dual code.

This foray into classical coding theory is not a detour; it's a direct path to understanding the next major family of quantum codes, the Calderbank-Shor-Steane (CSS) codes, which are constructed directly from classical ones.

1. The Anatomy of a Classical Linear Code

At its heart, a classical binary code is simply a predefined subset of all possible n-bit strings. We send only strings from this subset (the codewords), and if the received string is not in the set, we know an error occurred.

A linear code has the convenient property that it forms a vector subspace over the field of two elements, ${\mathbb{F}}_2=\{0,1\}$ (where addition is XOR). This means the sum (bitwise XOR) of any two codewords is also a valid codeword.

This subspace structure allows us to describe the entire code very compactly using linear algebra. We characterize a linear code C by three parameters, written as an [n, k, d] triplet:

• n (block length): The total number of bits in a codeword.
• k (message length): The dimension of the code subspace. It means the code contains $2^k$ codewords, corresponding to the $2^k$ possible k-bit messages we can encode.
• d (minimum distance): The minimum Hamming distance between any two distinct codewords. For a linear code, this is equivalent to the minimum Hamming weight (number of 1s) of any non-zero codeword. This parameter determines the code's error-detecting and error-correcting capability. A code with distance d can detect up to d-1 errors and correct up to floor((d-1)/2) errors.

2. The Generator Matrix, G

A linear code C of dimension k can be fully specified by a basis of k linearly independent codewords. We arrange these basis vectors as the rows of a $k\times n$ matrix called the generator matrix, G.

Any of the $2^k$ codewords can then be generated by taking a linear combination of these basis vectors. More simply, to encode a k-bit message vector m, we compute the matrix-vector product:
$c=mG$
All arithmetic is performed modulo 2.

A particularly convenient form for G is the standard form, G = [I_k | A], where I_k is the k x k identity matrix and A is a k x (n-k) matrix. This form makes the encoding process transparent: the first k bits of the codeword are simply the message bits themselves, and the remaining n-k bits are parity checks computed from the message.

To make this concrete, let's examine the famous Hamming [7,4,3] code.

As shown in the notes, the generator for the Hamming [7,4,3] code is a $4\times 7$ matrix. It encodes $k=4$ message bits into an $n=7$ bit codeword. The minimum distance is d=3, meaning it can correct any single-bit error.

3. The Parity-Check Matrix, H

There's another, equally powerful way to define a linear code: as the set of all vectors that satisfy a certain set of linear equations. These equations are captured by the parity-check matrix, H.

A vector c is a codeword in C if and only if it satisfies:
$H{c}^T=0$
This equation provides a simple test (a "parity check") for whether a given n-bit string is a valid codeword. The matrix H has dimensions $(n-k)\times n$.

The generator and parity-check matrices are intimately related. Since every codeword c is formed by c = mG, and every codeword must satisfy Hc^T = 0, it must be true that:
$H(mG{)}^T=H{G}^T{m}^T=0\text{for any message }m$
This implies the fundamental relationship:
$H{G}^T=0$
(Or equivalently, G H^T = 0). This means that every row of H is orthogonal to every row of G. The row space of H is the orthogonal complement of the row space of G.

If G is in standard form G = [I_k | A], the corresponding parity-check matrix can be constructed directly as H = [A^T | I_{n-k}] (working in ${\mathbb{F}}_2$).

4. The Dual Code, C^⊥

The orthogonality condition GH^T = 0 leads to a beautiful and powerful concept: the dual code.

Given a linear [n,k] code C, its dual code, denoted C^⊥, is the set of all n-bit vectors that are orthogonal to every codeword in C. Formally:
$C^{\perp }=\{\mathbf{v}\in {\mathbb{F}}_2^n\mid \mathbf{v}\cdot \mathbf{c}=0\text{ for all }\mathbf{c}\in C\}$
Here, the dot product is the standard vector dot product, calculated modulo 2.

From our discussion of G and H, the connection should be clear:

• The rows of H are, by definition, orthogonal to all codewords generated by G.
• Therefore, the rows of H are themselves codewords of the dual code C^⊥.

In fact, the (n-k) rows of H form a complete basis for C^⊥. This gives us the central result for dual codes:

The parity-check matrix of a code C is the generator matrix of its dual code C^⊥.

It follows immediately that the generator matrix of C is the parity-check matrix of C^⊥.
The roles are perfectly swapped:

• G_C = H_{C^⊥}
• H_C = G_{C^⊥}

This also tells us about the dimensions. If C is an [n, k] code, its generator matrix G_C has k rows. Its parity-check matrix H_C has n-k rows. Since H_C is the generator matrix for C^⊥, the dual code C^⊥ must have dimension n-k. So, if C is an [n, k]-code, C^⊥ is an [n, n-k]-code.

The following resource provides the formal definitions and proofs for these concepts.

5. Practical Construction and Verification

Let's consolidate these ideas with a concrete exercise. Consider a linear code C defined by the following generator matrix:

Your task is to analyze this code and its dual.

1. Verify the parameters [n, k, d] for C:
   • What are n and k?
   • List all $2^k$ codewords by computing mG for all possible 2-bit messages m.
   • Find the minimum distance d by finding the minimum weight of the non-zero codewords.
2. Derive the parity-check matrix H for C:
   • The given G is in standard form [I_k | A]. Identify A.
   • Construct H using the formula H = [A^T | I_{n-k}].
3. Derive the generator matrix for the dual code C^⊥:
   • What is the relationship between H_C and G_{C^⊥}?
4. Derive the parity-check matrix for the dual code C^⊥:
   • What is the relationship between G_C and H_{C^⊥}?

Conclusion

In this lesson, we established the fundamental algebraic framework for classical linear error-correcting codes. You are now equipped to describe, analyze, and manipulate these codes using their generator and parity-check matrices.

Key Takeaways:

• A linear code is a vector subspace of ${\mathbb{F}}_2^n$, characterized by the parameters [n, k, d].
• A k x n generator matrix G defines the code by providing a basis; codewords are generated via c = mG.
• An (n-k) x n parity-check matrix H defines the code as the null space of H; codewords are checked via Hc^T = 0.
• These matrices are related by the orthogonality condition GH^T = 0.
• The dual code C^⊥ consists of all vectors orthogonal to the code C. If C is an [n, k] code, C^⊥ is an [n, n-k] code.
• The generator and parity-check matrices of a code and its dual are swapped: G_{C^⊥} = H_C and H_{C^⊥} = G_C.

Preview of the next lesson:
Now that we have a firm grip on classical codes and their duals, we are ready to build a powerful class of quantum codes. In the next lesson, we will see how to construct a Calderbank-Shor-Steane (CSS) code from a pair of classical linear codes, C_1 and C_2. The critical requirement for this construction is a relationship between C_1 and the dual of C_2. Your understanding of dual codes from today's lesson will be essential.