Scalable Polar Code Construction for Successive Cancellation List Decoding: A Graph Neural Network-Based Approach

While constructing polar codes for successive-cancellation decoding can be implemented efficiently by sorting the bit-channels, finding optimal polar-code constructions for the successive-cancellation list (SCL) decoding in an efficient and scalable manner still awaits investigation. This paper proposes a graph neural network (GNN)-based reinforcement learning algorithm, named the iterative message-passing (IMP) algorithm, to solve the polar-code construction problem for SCL decoding. The algorithm operates only on the local structure of the graph induced by polar-code's generator matrix. The size of the IMP model is independent of the blocklength and the code rate, making it scalable to construct polar codes with long blocklengths. Moreover, a single trained IMP model can be directly applied to a wide range of target blocklengths, code rates, and channel conditions, and corresponding polar codes can be generated without separate training. Numerical experiments show that the IMP algorithm finds polar-code constructions that significantly outperform the classical constructions under cyclic-redundancy-check-aided SCL (CA-SCL) decoding. Compared to other learning-based construction methods tailored to SCL/CA-SCL decoding, the IMP algorithm constructs polar codes with comparable or lower frame error rates, while reducing the training complexity significantly by eliminating the need of separate training at each target blocklength, code rate, and channel condition.