Construction And Decoding Of Short Codes

on YouTube ↗43m

" summary

Introduces staircase matrix codes whose generator/parity structure permits parallel Gaussian elimination, enabling an OSD-like decoder with low latency and near-capacity performance; demonstrates a toy Hamming example where GND needs up to 8 guesses while the guessing-codeword decoder needs 5 and proves GCD is ML with ≤ guesses of GND. Presents LC-OSD that cuts maximum and average searches via SLVA over a trellis with local constraints plus early termination. Combines list-GRAND and enumerative search for polar leaves to cut complexity with no loss; shows binary image of RS(31) → length 155 performs near or above RCU in simulations.

AI-written summary · about

" chapters (13)

1. 0:00Introduction to OSD
2. 0:32ML decoding foundations
3. 3:00Decoding algorithms
4. 6:25Complexity analysis
5. 7:46Theoretical efficiency
6. 12:03Review of OSD methods
7. 16:17Constraint-based decoding
8. 20:06Application to RS codes
9. 21:22Staircase coding strategies
10. 27:27Coyd OSD techniques
11. 29:12Joint source-channel coding
12. 32:53Superposition coding
13. 35:45Conclusion and Q&A

" related talks

• 28mCommunication Avoiding Algorithms for Linear Algebra and BeyondJim Demmel · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 01h 03mBeyond Boolean Circuits in Garbled CircuitsDavid Heath · Secure Computation 2025
• 44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)Ran Gelles · Information Theory in Complexity Theory and Combinatorics 2015
• 57mCoding for Interactive CommunicationLeonard J. Schulman · Real-Time Decision Making
• 11mExploiting Combined Locality for Wide-Stripe Erasure Coding in Distributed StorageWei Chen, Patrick P. C. Lee, Yuchong Hu, Liangfeng Cheng, Qiaori Yao, Weichun Wang · FAST '21
• 28mCommunication-Optimal Parallel Algorithm for Strassen's Matrix MultiplicationGrey Ballard · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 27mList Recovery and Local Decoding of Expander CodesMary Wootters · Coding: From Practice to Theory
• 15mTACCL: Guiding Collective Algorithm Synthesis using Communication SketchesOlli Saarikivi, Rachee Singh, Vijay Chidambaram, Jacob Nelson, Aashaka Shah, Saeed Maleki, Meghan Cowan, Madan Musuvathi, Todd Mytkowicz · NSDI 2023