Multilevel Decoders Surpassing Belief Propagation on the Binary Symmetric Channel Shiva Kumar Planjery Dept. of Electrical and Computer Eng. University of Arizona Tucson, AZ 85721, U.S.A. Email: shivap@ece.arizona.edu David Declercq ETIS ENSEA/UCP/CNRS UMR 8051 95014 Cergy-Pontoise, France Email: declercq@ensea.fr Shashi Kiran Chilappagari, Bane Vasi ´ c Dept. of Electrical and Computer Eng. University of Arizona Tucson, AZ 85721, U.S.A. Email: { shashic,vasic } @ece.arizona.edu Abstract —In this paper, we propose a new class of quantized message-passing decoders for LDPC codes over the BSC. The messages take values (or levels) from a finite set. The update rules do not mimic belief propagation but instead are derived using the knowledge of trapping sets. We show that the update rules can be derived to correct certain error patterns that are uncorrectable by algorithms such as BP and min-sum. In some cases even with a small message set, these decoders can guarantee correction of a higher number of errors than BP and min-sum. We provide particularly good 3-bit decoders for 3-left-regular LDPC codes. They significantly outperform the BP and min- sum decoders, but more importantly, they achieve this at only a fraction of the complexity of the BP and min-sum decoders. Low-density parity-check (LDPC) [2] codes have received much attention in the past several years owing to their excep- tional performance under iterative decoding. A wide spectrum of iterative decoders of varying complexity have been devel- oped ranging from simple hard-decision algorithms such as Gallager-A/B algorithms to the more sophisticated belief prop- agation (BP) algorithm. Recently, the design of quantized BP decoders and other low-complexity variants of BP have gained prominence due to the high-speed requirements and hard- ware constraints for practical realizations of these decoders. The first quantized decoders including a three-level decoder coined Gallager-E algorithm were proposed by Richardson and Urbanke [3]. They also developed the technique of density evolution to determine the asymptotic decoding thresholds of a code. Low complexity approximations to BP with minimal loss in the asymptotic decoding thresholds have been proposed by Chen et al. [4]. The class of quantized BP decoders have been investigated by Lee and Thorpe [5]. Quantized min-sum decoders have been proposed by Smith, Kschischang and Yu [6]. A common theme in all the aforementioned works is that the underlying basis for design of the quantized decoders is to maximize the decoding thresholds which holds only in the asymptotic case. Therefore, these quantization schemes do not guarantee a good performance on a practical finite-length code especially in the high signal-to-noise (SNR) region. In addition, the effects of quantization can also contribute to the error-floor phenomenon. Richardson introduced the notion of trapping sets in [7] to characterize error floors. Trapping sets can be present in any finite-length code irrespective of how good the decoding threshold is and hence, codes optimized for good decoding thresholds can still exhibit high error floors. Characterization of error floors and design of LDPC codes with low error floors has recently been a subject of wide interest [8], [9], [10], [11]. In this paper, we propose multilevel decoders for LDPC codes over the binary symmetric channel (BSC). A key distinction from the traditional quantized decoders is that the messages are not quantized values of beliefs and the update rules are not approximations of the rules used in BP. Instead, they are derived using trapping sets and trapping set ontology [12]. As we showed in [13] in the case of BSC, failure characterization is combinatorial in nature, and in the error floor region reduces to the problem of guaranteed error- correction capability of a code. In [14] we showed the potential of multilevel decoding for the case of four levels. In this paper, we provide two 3-bit decoders for 3-left-regular codes that outperform floating-point BP and min-sum in the error floor region inspite of having much lower complexity. The rest of the paper is organized as follows. Section II provides preliminaries. Section III provides the general framework of multilevel decoders. In Section IV, we provide the description of the 3-bit decoders for 3-left-regular codes. Finally results and conclusions are presented in Sections V and VI. Let G = ( V ∪ C, E ) denote the Tanner graph of a binary LDPC code C with the set of variable nodes V = { v$_{1}$, · · · , v$_{n}$ } and set of check nodes C = { c$_{1}$, · · · , c$_{m}$ } . E is the set of edges in G . The code has length n and code rate R . For a vector v = ( v$_{1}$, v$_{2}$, . . . , v$_{n}$ ) , the support of v denoted as supp ( v ) , is defined as the set of all variable nodes such that v$_{i}$ = 0 . A code C is said to be d$_{v}$ -left-regular if all variable nodes in V of graph G have the same degree d$_{v}$ . The degree of a node is the number of its neighbors. Let r = ( r$_{1}$, r$_{2}$ . . . , r$_{n}$ ) be the input to the decoder from the BSC. A trapping set T ( r ) is a non-empty set of variable nodes in G that are not eventually corrected by the decoder [7]. A standard notation for a trapping set is ( a, b ) where a = | T ( r ) | and b is the number of odd-degree check nodes in the sub- graph induced by T ( r ) . The critical number of a trapping II. PRELIMINARIES I. INTRODUCTION arXiv:1001.3421v2 [cs.IT] 3 Mar 2011