IEEE Transactions on Information Theory · 2013 · 814 citations · 18 references
ComputingComputer ScienceMathematicsAlgorithmsInformation TheoryTheory Of ComputationChannel CapacityChannel CodingCoding TheoryCommunication ComplexityComputational ComplexityError-correcting CodesChannel Capacity ApproximationsChannel Coding TheoremsChannelsCode ConstructionsConstructionPolar Codes
A method for efficiently constructing polar codes is presented and analyzed. Although polar codes are explicitly defined, straightforward construction is intractable since the resulting polar bit-channels have an output alphabet that grows exponentially with the code length. Thus, the core problem that needs to be solved is that of faithfully approximating a bit-channel with an intractably large alphabet by another channel having a manageable alphabet size. We devise two approximation methods which “sandwich” the original bit-channel between a degraded and an upgraded version thereof. Both approximations can be efficiently computed and turn out to be extremely close in practice. We also provide theoretical analysis of our construction algorithms, proving that for any fixed ε > 0 and all sufficiently large code lengths n, polar codes whose rate is within ε of channel capacity can be constructed in time and space that are both linear in n.
18
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
Ido Tal, Alexander Vardy · 2011 · 556 citations
On the rate of channel polarization
Erdal Arıkan, Emre Telatar · 2009 · 492 citations · Full text
Engineering, Electrical Engineering, Digital Communication +7