On the Performance of Low-complexity Decoders of LDPC and Polar Codes

Efficient decoding is crucial to high-throughput and low-power wireless communication scenarios. A theoretical analysis of the performance-complexity tradeoff toward low-complexity decoding is required for a better understanding of the fundamental limits in the above-mentioned scenarios. This study aims to explore the performance of decoders with complexity constraints. Specifically, we investigate the performance of LDPC codes with different numbers of belief-propagation iterations and the performance of polar codes with an SSC decoder. We found that the asymptotic error rates of both polar codes and LDPC codes are functions of complexity $T$ and code length $N$, in the form of $2^{-a2^{b\frac{T}{N}}}$, where $a$ and $b$ are constants that depend on channel and coding schemes. Our analysis reveals the different performance-complexity tradeoffs for LDPC and polar codes. The results indicate that if one aims to further enhance the decoding efficiency for LDPC codes, the key lies in how to efficiently pass messages on the factor graph. In terms of decoding efficiency, polar codes asymptotically outperform $(J, K)$-regular LDPC codes with a code rate $R \le 1-\frac{J(J-1)}{2^J+(J-1)}$ in the low-complexity regime $(T \le O(NlogN))$.