# Low Complexity List Decoding for Polar Codes with Multiple CRC Codes
## 1 Introduction  
Polar codes are the first family of error correcting codes that provably achieve the capacity for symmetric binary-input discrete memoryless channels (B-DMCs) with low complexity successive cancellation (SC) decoding [1]. [PERSON] introduced the channel polarization that splits the capacities of information channels to one or zero as block length becomes longer [1]. As a dual phenomenon of the channel polarization, the conditional entropies in source coding context are also polarized when the joint entropy is broken down by the chain rule (this phenomenon is called the \"source polarization\") [2]. The source coding using polar codes based on the source polarization is also proven to be optimal for both lossless [3] and lossy source coding [4]. In addition, polar codes have been extended to multi-terminal problems such as multiple access and broadcast channels in channel coding [5; 6; 7; 8], and Slepian-Wolf and Gelfand-Pinsker problems in source coding [9; 10; 11]. From the channel coding perspective, even though the SC decoding of polar codes achieves the capacity, it was not as competitive in finite length performance as low-density parity-check (LDPC) codes and turbo codes [12; 13]. However, when both the concatenation of polar codes with cyclic redundancy check (CRC) codes and the SC list (SCL) decoding that keeps the best multiple decoding paths are used, the finite-length polar coding performance becomes comparable to the LDPC coding [12]. Furthermore, a parity-check concatenation was proposed to improve the performanceof polar codes based on CRC-aided SCL decoding [14]. Recently, thanks to their excellent error performance and fine rate flexibility [15], polar codes have been adopted as a channel code for the control channel of 5G new radio of the 3 rd generation partnership project [16]. In order for polar codes to show comparable error performance to the LDPC codes in moderate block lengths, the SCL decoding requires a rather large list size, e.g., \(L=32\). The list size \(L\) determines the maximum number of decoding paths and affects the complexity of log-likelihood ratio (LLR) calculation and sorting of path metrics (PMs). It is a linear factor in the decoding complexity. According to [17; 18], even for a list size smaller than 10, the SCL decoder has larger complexity than the LDPC decoder, which leads to a considerable gap in power consumption between those decoders. Therefore, a low complexity realization of the SCL decoding is important from a practical perspective, and some recent research has reduced the decoding complexity by efficiently managing decoding paths. In [19], decoding paths do not split when one of two child-paths is dominant. In addition, the decoding paths that have low reliability are eliminated during decoding in [20]. The operational decoding complexity of those schemes was lowered by the reduced average number of decoding paths. Lately, some studies have used multiple CRC codes to address different complexity issues of the decoding [21; 22; 23]. The scheme in [21] aims to reduce the memory complexity by selecting only the most likely path after each CRC operation where more than one CRC is applied. In [22], the complexity reduction due to CRC-based early stopping of decoding was reported. Finally, the method in [23] reduces the worst decoding latency and space complexity for storing intermediate LLRs. This paper addresses polar coding with multiple CRC codes similarly to [21; 22; 23], but we focus more on optimization of the scheme in terms of decoding complexity. First, we define the operational complexity, and then minimize it by optimizing CRC positions. In addition, the optimization of CRC positions is extended to a modified decoding that uses a complexity reduction trick called \"instant decision\" (first proposed in [24]). It is shown that the optimized CRC placement considerably lowers the decoding complexity of the multi-CRC scheme in a wide range of signal-to-noise ratio (SNR). The rest of this paper is organized as follows.