← 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
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.2.1
The Basic List-Decoder
12.2.2
Algorithm 2: Weighted-Degree List-Decoder
12.2.3
Algorithm 3: Multiplicity List-Decoder
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
13.3.1
A bijection from F_q^m\( vs. \)F_q^m
13.3.2
Analysis of extension degree
14
Decoding Concatenated Codes
14.1
A Natural Decoding Algorithm
14.2
Decoding From Errors and Erasures
14.3
Generalized Minimum Distance Decoding
14.3.1 GMD algorithm – I
14.3.2 GMD Algorithm – II
14.3.3 Derandomized GMD algorithm
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.4.1
Using a binary code as the outer code
15.4.2
Wrapping Up
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.3.1 Information Theory Review
16.3.2 Polarized Matrices and Decompression
16.3.3 A Polarizing Primitive
16.4 Polar Codes, Encoder and Decoder
16.4.1 The Code and Polarization Claims
16.4.2 Encoding
16.4.3 Decoding
16.5 Analysis: Speed of Polarization
16.5.1 Overview of Analysis
16.5.2 Local Polarization
16.5.3 Local vs. Global Polarization
16.7 Summary and Additional Information
17
Efficiently Achieving List Decoding Capacity
17.1
Folded Reed-Solomon Codes
17.1.1
The Intuition Behind Folded Reed-Solomon Codes
17.2
List Decoding Folded Reed-Solomon Codes: I
17.3
List Decoding Folded Reed-Solomon Codes: II
17.3.1
Error Correction Capability
17.3.2
Bounding the Output List Size
17.3.3
Algorithm Implementation and Runtime Analysis
17.3.4
Wrapping Up
18
Fast Encoding: Linear Time Encodable Codes
18.1
Overview of the construction
18.2
Low-density Error-Reduction Codes
18.2.1
The Code
18.2.2
Gen-Flip
Algorithm
18.2.3
Error-Reduction Guarantee
18.3
The error-correcting code: Recursive construction
18.4
Analysis
18.4.1
Encoding Analysis
18.4.2
Decoding Algorithm
18.4.3
Analysis of the decoder
19
Recovering Very Locally: Locally Recoverable Codes