← All blueprints
Essential Coding Theory — Blueprint
1
The Fundamental Question
1
The Basics
▶
2
A Look at Some Nicely Behaved Codes: Linear Codes
▶
2.3.1 On the Distance of a Linear Code
3
Probability as Fancy Counting and the q-ary Entropy Function
▶
3.1
A Crash Course on Probability
3.2
The Probabilistic Method
3.3
The q-ary Entropy Function
2
The Combinatorics
▼
4
What Can and Cannot Be Done – I
▶
Asymptotically good code families
4.1
Asymptotic Version of the Hamming Bound
4.2
Gilbert-Varshamov Bound
4.3
Singleton Bound
4.4
Plotkin Bound
5
The Greatest Code of Them All: Reed-Solomon Codes
6
What Happens When the Noise is Stochastic: Shannon’s Theorem
7
Bridging the Gap Between Shannon and Hamming: List Decoding
8
What Cannot be Done – II
▶
8.1
Elias-Bassalygo bound
8.2
The linear programming bounds
8.3
A Breather
3
The Codes
▶
9
When Polynomials Save the Day: Polynomial Based Codes
10
From Large to Small Alphabets: Code Concatenation
▶
10.1
Code Concatenation: The Basic Idea
10.2
Zyablov Bound
10.3
Advanced Concatenation and Strongly Explicit Constructions
10.4
Summary of Concatenation
11
When Graphs Come to the Party: Expander Codes
▶
11.1
Graphs
11.2
Expander Graphs
11.3
Basic Expander Codes
11.4
Codes from Weaker Expanders
11.5
Distance Amplification
11.6
Existence of Lossless Expanders
4
The Algorithms
▶
12
Efficient Decoding of Reed-Solomon Codes
▶
12.1
Unique decoding of Reed-Solomon codes
12.2
List Decoding Reed-Solomon Codes
12.3
Extensions
13
Decoding Reed-Muller Codes
▶
13.1
A natural decoding algorithm
13.2
Majority logic decoding
13.3
Decoding by reduction to Reed-Solomon decoding
14
Decoding Concatenated Codes
▶
14.1
A Natural Decoding Algorithm
14.2
Decoding From Errors and Erasures
14.3
Generalized Minimum Distance Decoding
15
Efficiently Achieving the Capacity of the BSC_p
▶
15.1
Achieving Capacity of BSC_p
15.2
Decoding Error Probability
15.3
The Inner Code
15.4
The Outer Code
15.5
Discussion
16
Information Theory Strikes Back: Polar Codes
▶
16.1 Achieving Gap to Capacity
16.2 Reduction to Linear Compression
16.3 The Polarization Phenomenon
16.4 Polar Codes, Encoder and Decoder
16.5 Analysis: Speed of Polarization
16.7 Summary and Additional Information
17
Efficiently Achieving List Decoding Capacity
▶
17.1
Folded Reed-Solomon Codes
17.2
List Decoding Folded Reed-Solomon Codes: I
17.3
List Decoding Folded Reed-Solomon Codes: II
18
Fast Encoding: Linear Time Encodable Codes
▶
18.1
Overview of the construction
18.2
Low-density Error-Reduction Codes
18.3
The error-correcting code: Recursive construction
18.4
Analysis
19
Recovering Very Locally: Locally Recoverable Codes
5
The Applications
▶
20
Cutting Data Down to Size: Hashing
21
Securing Your Fingerprints: Fuzzy Vaults
▶
21.1
Some quick background on fingerprints
21.2
The Fuzzy Vault Problem
21.3
The Final Fuzzy Vault
22
Finding Defectives: Group Testing
▶
22.4.1 Kautz–Singleton Construction
22.5.1 Connection to Group Testing
23
Complexity of Coding Problems
▶
23.1
Nearest Codeword Problem (NCP)
23.2
Decoding with Preprocessing
23.3
Approximate NCP
23.4
Distance bounded decoding
23.5
Minimum distance problem
23.6
Conclusions
24
Giving Computational Complexity a Helping Hand
▶
24.1
Communication Complexity
24.2
Derandomization and Pseudorandomness
24.3
Hardcore Predicates
24.4
Average case complexity
6
Appendices
▶
25
Appendix B. Some Useful Facts
▶
25.1
B.1 Some Useful Inequalities
25.2
B.2 Some Useful Identities and Bounds
26
Appendix C. Background on Asymptotic Notation, Algorithms and Complexity
▶
C.1 Asymptotic Notation
C.2 Bounding Algorithm run time
C.3 Randomized Algorithms
C.4 Efficient Algorithms
C.5 More on intractability
27
Appendix D. Basic Algebraic Algorithms
▶
D.2 Groups, Rings, Fields
D.3 Polynomials
D.4 Vector Spaces
D.5 Finite Fields
D.6 Algorithmic Aspects of Finite Fields
D.7 Algorithmic Aspects of Polynomials
28
Appendix E. Some Information Theory Essentials
Dependency graph
2 The Combinatorics
4
What Can and Cannot Be Done – I
Asymptotically good code families
4.1
Asymptotic Version of the Hamming Bound
4.2
Gilbert-Varshamov Bound
4.2.1
Greedy Construction
4.2.2
Linear Code Construction
4.3
Singleton Bound
4.4
Plotkin Bound
5
The Greatest Code of Them All: Reed-Solomon Codes
6
What Happens When the Noise is Stochastic: Shannon’s Theorem
7
Bridging the Gap Between Shannon and Hamming: List Decoding
8
What Cannot be Done – II
8.1
Elias-Bassalygo bound
8.2
The linear programming bounds
Krawtchouk polynomials and the linear program
Dual view and the MRRW bound
8.3
A Breather