Polar Codes I
summary
Transforms X^n by the Kronecker power matrix F (Un = Xn F^{⊗m}) over GF(2) and proves the conditional entropies of U_i polarize to 0 or 1: for any fixed δ the fraction in (δ,1−δ)→0 as n→∞, and δ can shrink like exp(−√n). For source coding send the ~nH(X) high‑entropy coordinates; decoder reconstructs the rest with error ≤2^{−√n}. Binary‑input channel version yields synthetic bit‑channels with capacities near 0 or 1; encoding/decoding runs in about N log N.
AI-written summary · about