Construction of Polar Codes Exploiting Channel Transformation Structure

Polar Codes are the first binary linear codes that provably achieve the symmetric capacity of arbitrary binary-input discrete memoryless channels. Their construction is explicit as implied by the transformations that lead to channel polarization, and low-complexity encoding and decoding methods are available. While being explicitly defined, exact construction is intractable as it depends on calculating channel parameters of channels whose output alphabets grow exponentially in the code length. To overcome this problem, heuristics have been proposed. In this work, we show how to accelerate one popular construction method by introducing two modifications to the channel transformation step, leaving quality of the results unaffected.