Fig. 5. FER results on the n = 4085 , R = 0 . 82 , MacKay code Fig. 4. FER results on the n = 768 , R = 0 . 75 , Quasicyclic code Fig. 3. FER results on the n = 155 , R = 0 . 4 , Tanner code decoder guarantees correction of all error patterns up to 5 errors. An interesting point to note is that the highly complex linear programming (LP) decoding fails to correct all 5-errors on the Tanner code, whereas the 3-bit decoder is able to, which illustrates the power of multilevel decoding. Multilevel decoding was established as a powerful decoding technique for LDPC codes. From our concluding example, we highlighted the importance of the isolation assumption as a crucial strategy for deriving good rules. Also from the results, it is evident that there is a certain aspect of universality to these decoders; the same 3-bit decoder performs well on a variety of codes. This suggests that deriving good rules based on trapping sets appears to take the structure of the local neighborhood into local computations of messages, which is a tiny step closer in our pursuit to approach maximum-likelihood decoding. Our future work includes deriving bounds and relating the isolation theorem with guaranteed error-correction capability. This work was funded by NSF under the grants IHCS- 0725403, CCF-0634969, CCF-0830245. VI. DISCUSSION AND CONCLUSIONS ACKNOWLEDGMENT REFERENCES 10 −2 10 −1 10 −8 10 −7 10 −6 10 −5 10 −4 10 −3 10 −2 10 −1 cross−over probability ( α ) Frame Error rate (FER) Min−Sum BP 7−level linear−threshold 5−level nonlinear−threshold 10 −3 10 −2 10 −6 10 −5 10 −4 10 −3 10 −2 10 −1 10 0 cross−over probability ( α ) Frame Error Rate (FER) Min−Sum BP 7−level linear−threshold 10 −3 10 −2 10 −8 10 −7 10 −6 10 −5 10 −4 10 −3 10 −2 10 −1 10 0 cross−over probability ( α ) Frame Error Rate (FER) Min−Sum BP 7−level linear−threshold [1] S. K. Planjery, D. Declercq, S. K. Chilappagari, and B. Vasic, “Mul- tilevel decoders surpassing belief propagation on the binary symmetric channel,” in Proc. Int. Symp. On Inform. Theory (ISIT 2010) . [2] R. G. Gallager, Low Density Parity Check Codes . Cambridge, MA: M.I.T. Press, 1963. [3] T. Richardson and R. Urbanke, “Capacity of low-density parity-check codes under message-passing decoding,” IEEE Trans. Inform. Theory , vol 47, pp. 599–618, Feb. 2001. [4] J. Chen, A. Dholakia, E. Eleftheriou, M. Fossorier, and X.-Y. Hu, “Reduced-complexity decoding of LDPC codes,” IEEE Trans. Commun. , vol. 53, no. 8, pp. 1288–1299, Aug. 2005. [5] J. K. Lee and J. Thorpe, “Memory-efficient decoding of LDPC codes,” in Proc. Int. Symp. on Inform. Theory (ISIT 2005) , Adelaide, Australia, pp. 459–463., Sept. 2005. [6] B. Smith, F. R. Kschischang and W. Yu, “Low-density parity-check codes for discretized min-sum decoding,” in Proc. 23rd Biennial Symp. on Commun. , pp. 14–17, 2006. [7] T. Richardson, “Error floors of LDPC codes,” in Proc. 41st Annual Allerton Conf. on Commun., Control and Computing , 2003. [8] S. K. Chilappagari, S. Sankaranarayanan, and B. Vasic, “Error floors of LDPC codes on the binary symmetric channel,” in Proc. IEEE Int. Conf. on Commun. (ICC 06) , vol. 3, Istanbul, Turkey, pp. 1089–1094, 2006. [9] S. K. Chilappagari, A. R. Krishnan, and B. Vasic, “LDPC codes which can correct three errors under iterative decoding,” in Proc. IEEE Inform. on Theory Workshop , pp. 406–410, May 2008. [10] Y. Wang, J. S. Yedidia, and S. C. Draper, “Multi-stage decoding of LDPC codes,” in Proc. IEEE Int. Symp. on Inform. Theory (ISIT 09) , Seoul, Korea, pp. 2151–2155, July 2009. [11] Z. Zhang, L. Dolecek, B. Nikolic, V. Anantharam, and M. Wainwright, “Lowering LDPC error floors by postprocessing,” in IEEE Global Telecommunications Conf. (GLOBECOM 08) , New Orleans, LA, pp. 1–6, Dec. 2008. [12] B. Vasic, S. K. Chilappagari, D. V. Nguyen, and S. K. Planjery, “Trapping set ontology,” Proc. 47th Annual Allerton Conf. on Commun., Control, and Computing , Sept. 2009. [13] M. Ivkovic, S. K. Chilappagari, and B. Vasic, “Eliminating trapping sets in low-density parity-check codes by using Tanner graph covers,” IEEE Trans. Inform. Theory , vol. 54, no. 8, pp. 3763–3768, 2008. [14] L. Sassatelli, S. K. Chilappagari, B. Vasic, and D. Declercq, “Two-bit message passing decoders for LDPC codes over the binary symmetric channel,” in Proc. IEEE Int. Symp. on Inform. Theory (ISIT 09) , Seoul, Korea, pp. 2156–2160, July 2009. [15] S. K. Chilappagari and B. Vasic, “Error correction capability of column- weight-three LDPC codes,” IEEE Trans. Inform. Theory , vol. 55, no. 5, pp. 2055–2061, May 2009. [16] B. J. Frey, R. Koetter, and A. Vardy, “Signal-space characterization of iterative decoding,” IEEE Trans. Inform. Theory , vol. 47, no. 2, pp. 766– 781, Feb. 2001. [17] “Error Floors of LDPC Codes.” [Online]. Available: http://www.ece. arizona.edu/ $^{∼}$vasiclab/Projects/CodingTheory/ErrorFloorHome.html