Polar Codes III
summary
Construction uses repeated Kronecker powers of the 2×2 binary matrix F to build length-N polar transforms; encoding and decoding run in N log N encoding/decoding time using the FFT‑like butterfly. A martingale argument proves channel capacities fraction → I(W) and almost sure polarization to 0 or 1. Successive‑cancellation gives error ~exp(−c sqrt(N)); list decoding plus a small CRC reaches near‑ML performance comparable to practical turbo/LDPC codes. Construction is polynomial time.
AI-written summary · about
chapters (11)
- 0:00Start
- 0:35Size 8 construction
- 11:01Polarization martingale
- 45:59Polar code example: W = BECC , N = 8, rate 1/2
- 48:56Encoding complexity
- 49:07Successive Cancellation Decoding (SCD)
- 56:28Decoding on W
- 57:41Complexity for successive cancelation decoding
- 58:08Construction complexity
- 59:30Polar coding summary
- 59:52List decoder for polar codes
related talks
34mPolar Codes over q-ary Alphabets and Polynomially Fast Convergence to Shannon Capacity
32mReed-Muller and Other Subcodes of the Sierpinski Matrix
32mDeterministic Rateless Codes for BSC
33mDeletion Codes in the High-noise and High-rate Regimes
32mMust One Learn the Channel to Communicate at Capacity?
51mOn constant T-depth circuits
39mStructure of the Fourier Spectrum of Boolean Functions and Complexity
01h 01mTrue Complexity of Multilinear Systems