# A Universal Low-Complexity Demapping Algorithm for Non-Uniform Constellations
## 1 Introduction  
[PERSON] defined the channel capacity limitation in his landmark paper Shannon (1955). Bit-interleaved coded modulation (BICM) is commonly utilized to approach Shannon capacity in modern communication systems. The BICM transmitter consists of a cascaded forward error correction (FEC) encoder, bit interleaver, and constellation mapper, and the capacity of the BICM system is called BICM capacity (BICM, 1995). A gap between the BICM capacity and Shannon capacity appears when gray labeled uniform quadrature amplitude modulation (QAM) constellation is applied, which becomes larger as the constellation order increases. Signal shaping is an efficient way to reduce this gap, which can be classified into probabilistic shaping and geometrical shaping (BICM, 1995). Probabilistic shaping sends symbols with unequal probability. Since a shaping decoder is needed in the receiver, there are difficulties in its application. Geometrical shaping changes the position of constellation points, and the receiver only needs to store new constellations. Non-uniform constellation (NUC) belongs to the latter. NUC can be classified into one-dimensional NUC (1D-NUC) and two-dimensional NUC (2D-NUC). The former restricts the shape of NUC to a square, while the latter has no constraint on the shape of NUC. Compared with 1D-NUC, 2D-NUC can provide higher shaping gain, but the optimization and demapping complexity is also greatly increased. NUC has been applied in Digital VideoBroadcasting-Next Generation Handheld (DVB-NGH) [4] and Advanced Television Systems Committee 3 rd Generation (ATSC 3.0) [5], and its application in 5G New Radio (NR) is considered in [6]. A soft demapping algorithm is usually utilized to calculate the log-likelihood ratio (LLR) of each bit to obtain optimal performance in the decoding phase. The Log-MAP algorithm is a commonly used algorithm, which can be simplified to the Max-Log-MAP algorithm by applying the Max-Log approximation. For the Max-Log-MAP demapping algorithm, the Euclidean distances (EDs) between the received symbol and all constellation points need to be calculated. Then, these EDs are compared to determine the required EDs to calculate the LLR of each bit. 1D-NUC can be decomposed into two independent non-uniform pulse amplitude modulation (NU-PAM) constellations, so only one-dimensional EDs need to be calculated and compared. 2D-NUC cannot be decomposed, so two-dimensional EDs of all constellation points need to be calculated and compared. A large number of ED calculations and comparisons in the Max-Log-MAP algorithm lead to the high demapping complexity of 2D-NUC and high-order 1D-NUC. The condensed symbols reduction (CSR) algorithm proposed in [7] and the quadrant search reduction (QSR) algorithm proposed in [8] can efficiently reduce the number of EDs that need to be calculated and compared. The CSR algorithm is based on the condensation characteristic of NUC. For a constellation cluster containing several constellation points, the ED only needs to be calculated and compared once. CSR algorithm is suitable for NUCs designed for low and medium code rates (CRs) FEC codes. As CR increases, the constellation points are barely condensed, and the complexity of the CSR algorithm is still high. QSR algorithm is based on the quadrant symmetry characteristic of NUC. When symbols are received in a particular quadrant, they are more likely to be sent from certain constellation points. QSR algorithm selects these constellation points and creates a subset, ED calculation and comparison only need to be performed on the constellation points contained in the subset. Otherwise, the QSR algorithm is sensitive to noise, the number of constellation points in the subset is greatly increased when facing the lower signal to noise ratio (SNR). Therefore, the QSR algorithm is suitable for NUCs designed for medium and high CRs. Moreover, there is a problem when the QSR algorithm creates the subset. It considers which constellation point the received symbol is sent from.