The Taub Faculty of Computer Science Events and Talks

Non-binary low-density parity-check (LDPC) codes significantly outperform their binary counterparts. Moreover, non-binary LDPC codes are especially good for the channels with burst errors and high-order modulations. Unfortunately, their decoding complexity is still large, that is why iterative hard and soft-reliability based decoding majority algorithms are of considerable interest for high-throughput practical applications. We investigate the error-correcting capabilities of non-binary LDPC codes decoded with a hard-decision low-complexity majority algorithm, which is a generalization of the bit-flipping algorithm for binary LDPC codes. We perform the worst case analysis and estimate the decoding radius realized by this algorithm. By the decoding radius we mean the number of errors which is guaranteed to be corrected. Our contribution is as follows. We first improve the estimate on the relative decoding radius for the classical majority algorithm (single threshold case). Then we suggest the majority decoding algorithm with multiple thresholds. A lower estimate on the decoding radius realized by the new algorithm is derived. The estimate is shown to be at least 1.2 times better than the estimate for a single threshold majority decoder. At the same time the transition to multiple thresholds does not affect the order of complexity.