1
Coding Theory — Core Definitions
▶
1.1
Overview
1.2
Basic objects: codewords and codes
1.3
Distance, weight, and rate
1.4
Basic lemma: distance vs. block length
2
Singleton Bound
▶
2.1
Overview
2.2
Main result
3
Hamming Bound
▶
3.1
Overview
3.2
Volume formula
3.3
Disjointness of decoding balls
3.4
Hamming bound
4
Entropy and Asymptotic Bounds
▶
4.1
Overview
4.2
Asymptotic upper bound on ball size
4.3
Entropy algebra lemmas
4.4
Analytic helpers
4.5
Stirling-based binomial lower bound
4.6
Positivity of \(q\)-ary entropy
5
Linear Codes and the Uniformity Lemma
▶
5.1
Overview
5.2
Distance equals minimum weight in linear codes
5.3
Uniform distributions and random matrices
5.4
Uniformity lemma
6
Gilbert–Varshamov Bound
▶
6.1
Overview
6.2
Probabilistic bound on low-weight outputs
6.3
Union bound over bad matrices
6.4
Gilbert–Varshamov bound
7
List Decoding
▶
7.1
Overview
7.2
List-decodable codes
7.3
Counting lemmas
7.4
List-decoding capacity
8
Johnson Bound
▶
8.1
Overview
8.2
Basic definitions
8.3
Embedding and inner-product bounds
8.4
Rankin bound
8.5
Johnson bound
9
CSS Codes (Not Yet Formalized)
▶
9.1
Overview
9.2
Symplectic vector space
9.3
CSS construction
9.4
CSS code parameters
10
Quantum Hamming Bound
▶
10.1
Overview
10.2
Pauli strings
10.3
\(n\)-qubit Hilbert space
10.4
Knill–Laflamme conditions
10.5
Error sphere and sphere-packing
10.6
Quantum Hamming bound
11
Quantum Singleton Bound
▶
11.1
Overview
11.2
Symplectic vector space
11.3
Support, weight, and isotropic subspaces
11.4
Code parameters and erasure correctability
11.5
Key lemma: two disjoint correctable sets
11.6
Quantum Singleton bound
Dependency graph
TCSLib
1
Coding Theory — Core Definitions
1.1
Overview
1.2
Basic objects: codewords and codes
1.3
Distance, weight, and rate
1.4
Basic lemma: distance vs. block length
2
Singleton Bound
2.1
Overview
2.2
Main result
3
Hamming Bound
3.1
Overview
3.2
Volume formula
3.3
Disjointness of decoding balls
3.4
Hamming bound
4
Entropy and Asymptotic Bounds
4.1
Overview
4.2
Asymptotic upper bound on ball size
4.3
Entropy algebra lemmas
4.4
Analytic helpers
4.5
Stirling-based binomial lower bound
4.6
Positivity of \(q\)-ary entropy
5
Linear Codes and the Uniformity Lemma
5.1
Overview
5.2
Distance equals minimum weight in linear codes
5.3
Uniform distributions and random matrices
5.4
Uniformity lemma
6
Gilbert–Varshamov Bound
6.1
Overview
6.2
Probabilistic bound on low-weight outputs
6.3
Union bound over bad matrices
6.4
Gilbert–Varshamov bound
7
List Decoding
7.1
Overview
7.2
List-decodable codes
7.3
Counting lemmas
7.4
List-decoding capacity
8
Johnson Bound
8.1
Overview
8.2
Basic definitions
8.3
Embedding and inner-product bounds
8.4
Rankin bound
8.5
Johnson bound
9
CSS Codes (Not Yet Formalized)
9.1
Overview
9.2
Symplectic vector space
9.3
CSS construction
9.4
CSS code parameters
10
Quantum Hamming Bound
10.1
Overview
10.2
Pauli strings
10.3
\(n\)-qubit Hilbert space
10.4
Knill–Laflamme conditions
10.5
Error sphere and sphere-packing
10.6
Quantum Hamming bound
11
Quantum Singleton Bound
11.1
Overview
11.2
Symplectic vector space
11.3
Support, weight, and isotropic subspaces
11.4
Code parameters and erasure correctability
11.5
Key lemma: two disjoint correctable sets
11.6
Quantum Singleton bound