IEEE International Symposium on Information Theory (ISIT)
Automorphism-Enhanced GCD Algorithm for Polar Codes
Qianfan Wang, Xiangping Zheng, Yiwen Wang, Peihong Yuan, Linqi Song, Xiao Ma
Abstract
This paper presents AE–LCGCD, an automorphism-enhanced multi-basis guessing codeword decoding (GCD) algorithm for CRC–polar codes, which avoids on-the-fly Gaussian elimination (GE). The proposed decoder leverages a large set of code automorphisms to construct multiple candidate re-encoding bases, selects the most reliable basis for decoding, and generates candidates via a locally constrained search. To reduce the average number of searches, we propose CRC-gated early-termination rules tailored to AE–LCGCD and prove that, under the proposed rule and without a limit on the number of searches, the decoder is a non-exhaustive ML decoder. To analyze performance, we develop a tight upper bound on the frame error rate (FER) using a saddlepoint approximation. Simulations on 5G CRC–polar codes across low, medium, and high rates show that AE–LCGCD consistently outperforms CRC-aided SCL (CA–SCL), and, in particular, it closely approaches the finite-length bound at high rates. Additionally, the proposed decoder significantly outperforms the conventional LC–GCD in both FER and average number of searches, owing to the improved re-encoding bases enabled by multiple automorphisms.