Low Complexity Method for Channel-Dependent Construction of Polar Codes Using Partial Order

In this paper, a novel low-complexity method for channel-dependent construction of polar codes is designed by exploiting the partial order (PO) relation to eliminate redundant computations. The proposed method selects the information set with a threshold, thus avoiding the reliability computation of unnecessary synthetic channels and the cost of sorting. We first introduce two key iterative strategies based on the PO relation of the synthetic channels. Then, we analyze the iteration process of the proposed method through a binary tree and a linear table structure and further derive the theoretical complexity of the proposed method. We validate the theoretical analysis through simulation results. Finally, considering the practical application, we propose a suboptimal simplified version of the proposed method to significantly reduce the complexity. Compared with the sorting method, the proposed simplified method needs only at most 10% of the comparison numbers in the process of the information set selection with negligible performance loss under the cyclic redundancy check-aided successive cancellation list decoding.