Gap to Capacity of Finite Length Polar Codes

on YouTube ↗33m

" summary

Extends finite-length polar scaling from binary to q-ary channels and gives a concrete numerical method: compute a concave upper bound on the information-combining map G via concave minimization over the simplex, show QSC channels nearly attain the extremum for q=3, and derive a scaling exponent bound mu ≈ 6.5 for ternary polar codes. Uses Bhattacharyya-style martingale arguments and numerical convex optimization; encoding/decoding remains O(n log n) and the bound improves with the concave upper bound on G.

AI-written summary · about

" chapters (13)

1. 0:00Start
2. 0:59Problem Definition
3. 1:59Blocklength Scaling of Binary Polar Codes
4. 3:19How can we generalize / improve results?
5. 5:29Polar codes, Decoding
6. 7:26Analysis of Polarization (CONT'D)
7. 9:33How can finite length scaling be shown? (CONT'D)
8. 11:55Outline of analysis of -ary polarization (CONT'D)
9. 13:39The main difficulty
10. 19:11Properties of g(G1, G₂)
11. 23:49Numerical Results (CONT'D)
12. 27:13Lower bound on I (W)-I (W)
13. 29:38Conclusion

" related talks

• 45mTeaching an old code a new trickRüdiger Urbanke · Random Instances and Phase Transitions (Simons Institute, 2016)
• 43mCoded matrix computation: numerical stability, partial stragglers and sparse input matricesAditya Ramamoorthy · Application-Driven Coding Theory 2024
• 48mSpatial Coupling as a Proof TechniqueNicolas Macris · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 11mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 27mWeak Decoupling, Polynomial Folds, and Approximate Optimization over the SphereVijay Bhattiprolu · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)
• 56mEntropy, Capacity, and CountingNisheeth Vishnoi · Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019)
• 26mAdaptive Coding over Countable AlphabetsStéphane Boucheron · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 49mDiscrete Optimization using Log-Concave PolynomialsNima Anari · Hyperbolic Polynomials and Hyperbolic Programming