An Analytical Study of the Min-Sum Approximation for Polar Codes

The min-sum approximation is widely used in the decoding of polar codes. Although it is a numerical approximation, hardly any penalties are incurred in practice. We give a theoretical justification for this. We consider the common case of a binary-input, memoryless, and symmetric channel, decoded using successive cancellation and the min-sum approximation.
Under mild assumptions, we show the following. For the finite length case, we show how to exactly calculate the error probabilities of all synthetic (bit) channels in time \(O(N^{1.585})\), where \(N\) is the codeword length. This implies a code construction algorithm with the above complexity. For the asymptotic case, we develop two rate thresholds, denoted \(R_L = R_L(\lambda)\) and \(R_U =R_U(\lambda)\), where \(\lambda(\cdot)\) is the labeler of the channel outputs (essentially, a quantizer). For any \(0 < \beta < \frac{1}{2}\) and any code rate \(R < R_L\), there exists a family of polar codes with growing lengths such that their rates are at least \(R\) and their error probabilities are at most \(2^{-N^\beta}\). That is, strong polarization continues to hold under the min-sum approximation. Conversely, for code rates exceeding \(R_U\), the error probability approaches \(1\) as the code-length increases, irrespective of which bits are frozen. We show that \(0 < R_L \leq R_U \leq C\), where \(C\) is the channel capacity. The last inequality is often strict, in which case the ramification of using the min-sum approximation is that we can no longer achieve capacity.

M.Sc. student under the supervision of Prof. Ido Tal and  Prof. Shlomo Shamai (Shitz).