Polar Codes over q-ary Alphabets and Polynomially Fast Convergence to Shannon Capacity
summary
Shows that q-ary polar codes over prime-size alphabets achieve capacity with block length polynomial in 1/epsilon and encoding/decoding time N log N, but the exponent C grows (currently polynomial) with q. The proof replaces martingale arguments with an entropic increase inequality for prime q, uses the Bhattacharyya parameter to strengthen rough polarization after ~log(1/epsilon) levels, and gives a multi-level construction for non-prime q; constants and the true optimal C remain open.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:15Channel Coding
- 1:10Random Codes
- 1:41Problem Formalism
- 2:37Codes that are close to capacity
- 3:57Binary Polar Codes
- 5:50Main Result
- 7:50Channel Polarization
- 12:482 x 2 "Base" Polarizing Matrix
- 13:57Recursive Construction
- 16:07Convergence
- 19:47Direct Analysis of Polarization
- 20:48Amplification to Fine Polarization
- 23:00Binary Case of Entropic Inequality
- 26:30Solution for Non-Prime q
- 27:05Conclusion
related talks
01h 14mPolar Codes III
32mMust One Learn the Channel to Communicate at Capacity?
40mTutorial on Capacity in Coding for Interactive Communication (Part 2 of 2)
51mOn constant T-depth circuits
22mVerifying the Equivalence of Parameterized Quantum Circuits
20mWith a Few Square Roots, Quantum Computing is as Easy as Pi
55mLower Bounds Against PC With Extension Variables
32mOptimal Quantum Programs