Indexing
All Issues
Submission
Author Guidelines
Reviewers
Editorial Members
Publication Fee
Vol.1 , No. 3, Publication Date: May 31, 2018, Page: 104-117
, low end-to-end delay and reliable services. In order to address these challenges, several channel coding scheme are proposed. In this paper, detailed overviews of the major concepts in error detection and correction codes are presented. The paper provided fundamentals of Low Density Parity Check (LDPC) codes, and a comprehensive survey of the binary and non-binary LDPC codes is provided.&picture=http://www.aascit.org/aascit/decorators/img/journal/812.jpg)
| [1] | Salah Abdulghani Alabady, College of Engineering, Computer Engineering Department, University of Mosul, Mosul, Iraq. |
Forward error detection and correction codes have been widely either used of storage applications or transferred through a wireline or wireless communication media systems for many years. Due to the unreliable wireless links, broadcast nature of wireless transmissions, interference, moreover, noisy transmission channel, frequent topology changes, and the various quality of wireless channel, there are challenge to provide high data rate service, high throughput, high packet delivery ratio (PDR), low end-to-end delay and reliable services. In order to address these challenges, several channel coding scheme are proposed. In this paper, detailed overviews of the major concepts in error detection and correction codes are presented. The paper provided fundamentals of Low Density Parity Check (LDPC) codes, and a comprehensive survey of the binary and non-binary LDPC codes is provided.
Keywords
Hamming, RS, LDPC, Detection and Correction Codes
Reference
| [01] | R. Gallager, "Low density parity check codes, number 21 in Research monograph series," MIT Press, Cambridge, Mass, 1963. |
| [02] | R. A. Carrasco, and M. Johnston, Non-Binary Error Control Coding for Wireless Communication and Data Storage: Wiley Publishing, 2009. |
| [03] | L. Bhargava, and R. Bose, “Novel hardware implementation of LLR-based non-binary LDPC decoders,” in IEEE National Conference on Communications (NCC), 2013, pp. 1-5. |
| [04] | Y. Kou, S. Lin, and M. P. C. Fossorier, “Low-density parity-check codes based on finite geometries: A rediscovery and new results,” IEEE Transactions on Information Theory, vol. 47, no. 7, pp. 2711-2736, 2001. |
| [05] | A. Voicila, D. Declereq, F. Verdier, M. Fossorier, and P. Urard, “Low-complexity, low-memory EMS algorithm for non-binary LDPC codes,” in IEEE International Conference on Communications, ICC'07, 2007, pp. 671-676. |
| [06] | C. L. Wang, X. H. Chen, Z. W. Li, and S. H. Yang, “A Simplified Min-Sum Decoding Algorithm for Non-Binary LDPC Codes,” IEEE transactions on communications, vol. 61, no. 1, pp. 24-32, 2013. |
| [07] | A. Salbiyono, and T. Adiono, “LDPC decoder performance under different number of iterations in mobile WiMax,” in International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS), 2010, pp. 1-4. |
| [08] | M. P. C. Fossorier, M. Mihaljevic, and H. Imai, “Reduced complexity iterative decoding of low-density parity check codes based on belief propagation,” IEEE transactions on communications, vol. 47, no. 5, pp. 673-680, 1999. |
| [09] | D. Yang, and W. C. Lee, “Adaptive Hybrid Automatic Repeat Request (ARQ) with a Novel Packet Reuse Scheme for Wireless Communications,” in The 9th International Conference on Advanced Communication Technology, Okamoto, Kobe, Japan, 2007, pp. 597-601. |
| [10] | D. J. Claypool, and K. M. McNeill, “Automatic repeat request (ARQ) over TDMA-based mesh network,” in IEEE Military Communications Conference (MILCOM 2008), San Diego, CA, USA, 2008, pp. 1-7. |
| [11] | S. Lin, and D. J. Costello, Error control coding: fundamentals and applications: Pearson Education India, 2004. |
| [12] | Y. Jiang, A practical guide to error-control coding using MATLAB: Artech House, 2010. |
| [13] | R. W. Hamming, “Error detecting and error correcting codes,” Bell System technical journal, vol. 29, no. 2, pp. 147-160, 1950. |
| [14] | T. K. Moon, Error correction coding: Wiley Online Library, 2005. |
| [15] | T. K. Moon, Error Correction Coding: Mathematical Methods and Algorithms: Wiley-Interscience, 2005. |
| [16] | S. B. Wicker, Error control systems for digital communication and storage: Prentice-Hall, Inc., 1994. |
| [17] | I. S. Reed, and G. Solomon, “Polynomial codes over certain finite fields,” Journal of the Society for Industrial & Applied Mathematics, vol. 8, no. 2, pp. 300-304, 1960. |
| [18] | B. Sklar, and F. J. Harris, “The ABCs of linear block codes,” IEEE Signal Processing Magazine, vol. 21, pp. 14-35, 2004. |
| [19] | R. Gallager, “Low-density parity-check codes,” IRE Transactions on Information Theory, vol. 8, no. 1, pp. 21-28, 1962. |
| [20] | D. J. MacKay, and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” Electronics letters, vol. 32, no. 18, pp. 1645, 1996. |
| [21] | J. Campello, D. S. Modha, and S. Rajagopalan, "Designing LDPC codes using bit-filling." pp. 55-59. |
| [22] | D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Transactions on Information Theory, vol. 45, no. 2, pp. 399-431, Mar, 1999. |
| [23] | H. Zhong, and T. Zhang, “Block-LDPC: A practical LDPC coding system design approach,” IEEE Transactions on Circuits and Systems I-Regular Papers, vol. 52, no. 4, pp. 766-775, Apr, 2005. |
| [24] | L. Chun-Hao, W. Chien-Yi, L. Chun-Hao, and C. Tzi-Dar, “An O(qlogq) Log-Domain Decoder for Non-Binary LDPC Over GF(q),” in IEEE Asia Pacific Conference on Circuits and Systems, (APCCAS), 2008, pp. 1644-1647. |
| [25] | M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, “Improved low-density parity-check codes using irregular graphs,” IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 585-598, 2001. |
| [26] | B. M. Leiner, LDPC Codes–a brief Tutorial, 2005. |
| [27] | Y.-L. Wang, Y.-L. Ueng, C.-L. Peng, and C.-J. Yang, “Processing-Task Arrangement for a Low-Complexity Full-Mode WiMAX LDPC Codec,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 58, no. 2, pp. 415-428, 2011. |
| [28] | A. E. Cohen, and K. K. Parhi, “A Low-Complexity Hybrid LDPC Code Encoder for IEEE 802.3an (10GBase-T) Ethernet,” Ieee Transactions on Signal Processing, vol. 57, no. 10, pp. 4085-4094, 2009. |
| [29] | G. Falcao, J. Andrade, V. Silva, and L. Sousa, "Real-time DVB-S2 LDPC decoding on many-core GPU accelerators." in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2011, pp. 1685-1688. |
| [30] | S.-M. Kim, C.-S. Park, and S.-Y. Hwang, “A novel partially parallel architecture for high-throughput LDPC Decoder for DVB-S2,” IEEE Transactions on Consumer Electronics, vol. 56, no. 2, pp. 820-825, 2010. |
| [31] | N. Miladinovic, and M. P. C. Fossorier, “Improved bit-flipping decoding of low-density parity-check codes,” IEEE Transactions on Information Theory, vol. 51, no. 4, pp. 1594-1606, 2005. |
| [32] | S. A. Muaini, A. Al-Dweik, and M. Al-Qutayri, “BER performance of turbo product LDPC codes with non-sequential decoding,” in 6th Joint IFIP Wireless and Mobile Networking Conference (WMNC), 2013, pp. 1-6. |
| [33] | T. C. Chen, “Channel-independent weighted bit-flipping decoding algorithm for low-density parity-check codes,” IET Communications, vol. 6, no. 17, pp. 2968-2973, 2012. |
| [34] | L. Safarnejad, and M. R. Sadeghi, “FFT Based Sum-Product Algorithm for Decoding LDPC Lattices,” IEEE Communications Letters, vol. 16, no. 9, pp. 1504-1507, 2012. |
| [35] | M. Johnston, B. S. Sharif, C. C. Tsimenidis, and L. Chen, “Sum-Product Algorithm Utilizing Soft Distances on Additive Impulsive Noise Channels,” IEEE Transactions on Communications, vol. 61, no. 6, pp. 2113-2116, 2013. |
| [36] | N. Noorshams, and M. J. Wainwright, “Stochastic Belief Propagation: A Low-Complexity Alternative to the Sum-Product Algorithm,” IEEE Transactions on Information Theory, vol. 59, no. 4, pp. 1981-2000, 2013. |
| [37] | W. Li, Z. Yang, and H. Hu, “Sequential Particle-Based Sum-Product Algorithm for Distributed Inference in Wireless Sensor Networks,” IEEE Transactions on Vehicular Technology, vol. 62, no. 1, pp. 341-348, 2013. |
| [38] | M. Karimi, and A. H. Banihashemi, “Message-Passing Algorithms for Counting Short Cycles in a Graph,” IEEE Transactions on Communications, vol. 61, no. 2, pp. 485-495, 2013. |
| [39] | N. Ruozzi, and S. Tatikonda, “Message-Passing Algorithms: Reparameterizations and Splittings,” IEEE Transactions on Information Theory, vol. 59, no. 9, pp. 5860-5881, Sep, 2013. |
| [40] | S. H. Lee, M. Shamaiah, H. Vikalo, and S. Vishwanath, “Message-Passing Algorithms for Coordinated Spectrum Sensing in Cognitive Radio Networks,” IEEE Communications Letters, vol. 17, no. 4, pp. 812-815, 2013. |
| [41] | M. C. Davey, and D. J. MacKay, “Low density parity check codes over GF (q),” in Information Theory Workshop, 1998, pp. 70-71. |
| [42] | G. Falcao, V. Silva, J. Marinho, and L. Sousa, “LDPC Decoders for the WiMAX (IEEE 802.16 e) based on Multicore Architectures,” in WIMAX New Developments, Upena D Dalal and Y P Kosta (Ed.) 2009. |
| [43] | K. S. Kim, S. H. Lee, Y. H. Kim, and J. Y. Ahn, “Design of binary LDPC code using cyclic shift matrices,” Electronics letters, vol. 40, no. 5, pp. 325-326, 2004. |
| [44] | R. M. Tanner, “A Recursive Approach to Low Complexity Codes,” IEEE Transactions on Information Theory, vol. 27, no. 5, pp. 533-547, 1981. |
| [45] | V. D. Kolesnik, “Probabilistic decoding of majority codes,” Problemy Peredachi Informatsii, vol. 7, no. 3, pp. 3-12, 1971. |
| [46] | R. Lucas, M. P. Fossorier, Y. Kou, and S. Lin, “Iterative decoding of one-step majority logic deductible codes based on belief propagation,” IEEE Transactions on Communications,, vol. 48, no. 6, pp. 931-937, 2000. |
| [47] | T. J. Richardson, and R. L. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding,” IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 599-618, 2001. |
| [48] | F. R. Kschischang, B. J. Frey, and H. A. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 498-519, 2001. |
| [49] | X. Chen, and A. Men, “Reduced complexity and improved performance decoding algorithm for nonbinary LDPC codes over GF (q),” in 11th IEEE International Conference on Communication Technology, (ICCT) 2008, pp. 406-409. |
| [50] | S. M. Song, B. Zbou, S. Lin, and K. Abdel-Ghaffar, “A Unified Approach to the Construction of Binary and Nonbinary Quasi-Cyclic LDPC Codes Based on Finite Fields,” IEEE Transactions on Communications, vol. 57, no. 1, pp. 84-93, 2009. |
| [51] | G. J. Han, and X. C. Liu, “A Unified Early Stopping Criterion for Binary and Nonbinary LDPC Codes Based on Check-Sum Variation Patterns,” IEEE Communications Letters, vol. 14, no. 11, pp. 1053-1055, 2010. |
| [52] | P. Venkateshwari, and M. Anbuselvi, “Decoding performance of binary and non-binary LDPC codes for IEEE 802.11 n standard,” in IEEE International Conference on Recent Trends In Information Technology (ICRTIT), 2012, pp. 292-296. |
| [53] | S. Y. Chung, G. D. Forney, T. J. Richardson, and R. Urbanke, “On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit,” IEEE Communications Letters, vol. 5, no. 2, pp. 58-60, 2001. |
| [54] | M. Ardakani, and F. R. Kschischang, “Properties of optimum binary message-passing decoders,” IEEE Transactions on Information Theory, vol. 51, no. 10, pp. 3658-3665, 2005. |
| [55] | T. M. N. Ngatched, F. Takawira, and M. Bossert, “An Improved Decoding Algorithm for Finite-Geometry LDPC Codes,” IEEE Transactions on Communications, vol. 57, no. 2, pp. 302-306, 2009. |
| [56] | H. Saeedi, and A. H. Banihashemi, “Design of Irregular LDPC Codes for BIAWGN Channels with SNR Mismatch,” IEEE Transactions on Communications, vol. 57, no. 1, pp. 6-11, 2009. |
| [57] | S. K. Chilappagari, and B. Vasic, “Error-Correction Capability of Column-Weight-Three LDPC Codes,” IEEE Transactions on Information Theory, vol. 55, no. 5, pp. 2055-2061, 2009. |
| [58] | D. Oh, and K. K. Parhi, “Min-Sum Decoder Architectures With Reduced Word Length for LDPC Codes,” Ieee Transactions on Circuits and Systems I-Regular Papers, vol. 57, no. 1, pp. 105-115, 2010. |
| [59] | L. Sassatelli, and D. Declercq, “Nonbinary Hybrid LDPC Codes,” IEEE Transactions on Information Theory, vol. 56, no. 10, pp. 5314-5334, 2010. |
| [60] | G. S. Yue, and X. D. Wang, “An Implementation-Friendly Binary LDPC Decoding Algorithm,” IEEE Transactions on Communications, vol. 58, no. 1, pp. 95-100, 2010. |
| [61] | B. Belean, S. Nedevschi, and M. Borda, “Application specific hardware architecture for high-throughput short-length LDPC decoders,” in IEEE International Conference on Intelligent Computer Communication and Processing (ICCP), 2013, pp. 307-310. |
| [62] | T. Xia, H.-C. Wu, S. Y. Chang, X. Liu, and S. C.-H. Huang, "Blind identification of binary LDPC codes for M-QAM signals." in IEEE Global Communications Conference (GLOBECOM), 2014, pp. 3532-3536. |
| [63] | H. Chen, L. Luo, Y. Sun, X. Li, H. Wan, L. Luo, and T. Qin, “Iterative reliability-based modified majority-logic decoding for structured binary LDPC codes,” Journal of Communications and Networks, vol. 17, no. 4, pp. 339-345, 2015. |
| [64] | S. Harikumar, J. Ramesh, M. Srinivasan, and A. Thangaraj, "Threshold upper bounds and optimized design of protograph LDPC codes for the Binary Erasure Channel." in Seventh International Workshop on Signal Design and its Applications in Communications (IWSDA), 2015, pp. 186-190. |
| [65] | I. E. Bocharova, B. D. Kudryashov, V. Skachek, and Y. Yakimenka, "Low complexity algorithm approaching the ML decoding of binary LDPC codes." in IEEE International Symposium on Information Theory (ISIT), 2016, pp. 2704-2708. |
| [66] | I. E. Bocharova, B. D. Kudryashov, E. Rosnes, V. Skachek, and O. Ytrehus, "Wrap-around sliding-window near-ML decoding of binary LDPC codes over the BEC." in 9th International Symposium on Turbo Codes and Iterative Information Processing (ISTC), 2016, pp. 16-20. |
| [67] | S. Eleruja, U.-F. Abdu-Aguye, M. Ambroze, M. Tomlinson, and M. Zak, "Design of binary LDPC codes for Slepian-Wolf coding of correlated information sources." in IEEE Global Conference on Signal and Information Processing (GlobalSIP), 2017, pp. 1120-1124. |
| [68] | X. Liu, F. Xiong, Z. Wang, and S. Liang, “Design of Binary LDPC Codes with Parallel Vector Message Passing,” IEEE Transactions on Communications, 2017. |
| [69] | X. He, L. Zhou, and J. Du, “A New Multi-Edge Metric-Constrained PEG Algorithm for Designing Binary LDPC Code With Improved Cycle-Structure,” IEEE Transactions on Communications, vol. 66, no. 1, pp. 14-25, 2018. |
| [70] | L. Barnault, and D. Declercq, “Fast decoding algorithm for LDPC over GF (2q),” in Information Theory Workshop, 2003, pp. 70-73. |
| [71] | H. Wymeersch, H. Steendam, and M. Moeneclaey, “Log-domain decoding of LDPC codes over GF (q),” in IEEE International Conference on Communications, 2004, pp. 772-776. |
| [72] | C.-Y. Chen, Q. Huang, C.-c. Chao, and S. Lin, “Two low-complexity reliability-based message-passing algorithms for decoding non-binary LDPC codes,” IEEE Transactions on Communications, vol. 58, no. 11, pp. 3140-3147, 2010. |
| [73] | S. Aruna, and M. Anbuselvi, “FFT-SPA based non-binary LDPC decoder for IEEE 802.11n standard,” in International Conference on Communications and Signal Processing (ICCSP), 2013, pp. 566-569. |
| [74] | C.-L. Wang, Z. Li, and S. Yang, “A new min-sum based decoding algorithm for non-binary LDPC codes,” in International Conference on Computing, Networking and Communications (ICNC), 2012, pp. 476-480. |
| [75] | V. Savin, “Min-Max decoding for non binary LDPC codes,” in IEEE International Symposium on Information Theory (ISIT), 2008, pp. 960-964. |
| [76] | J. Wang, X. Liu, K. Chi, and X. Zhao, “Complex field network-coded cooperation based on multi-user detection in wireless networks,” Journal of Systems Engineering and Electronics, vol. 24, no. 2, pp. 215-221, 2013. |
| [77] | J. Lin, and Z. Yan, “A decoding algorithm with reduced complexity for non-binary LDPC codes over large fields,” in IEEE International Symposium on Circuits and Systems (ISCAS), 2013, pp. 1688-1691. |
| [78] | J. Li, K. Liu, S. Lin, and K. Abdel-Ghaffar, “A matrix-theoretic approach to the construction of non-binary quasi-cyclic LDPC codes,” IEEE Transactions on Communications, vol. 63, no. 4, pp. 1057-1068, 2015. |
| [79] | G. Garrammone, E. Paolini, B. Matuz, and G. Liva, “Non-binary LDPC erasure codes with separated low-degree variable nodes,” IEEE Transactions on Communications, vol. 63, no. 11, pp. 3937-3949, 2015. |
| [80] | L. Dolecek, D. Divsalar, Y. Sun, and B. Amiri, “Non-binary protograph-based LDPC codes: Enumerators, analysis, and designs,” IEEE Transactions on Information Theory, vol. 60, no. 7, pp. 3913-3941, 2014. |
| [81] | L. Song, Q. Huang, and Z. Wang, "Set min-sum decoding algorithm for non-binary LDPC codes." in IEEE International Symposium on Information Theory (ISIT), 2016, pp. 3008-3012. |
| [82] | T. Wu, H.-C. Yang, and J. Yan, "Modulation assisted preprocessing for non-binary LDPC decoding with extended min-sum algorithm." in IEEE Canadian Conference on Electrical and Computer Engineering (CCECE), 2016, pp. 1-4. |
| [83] | S. Yeo, and I.-C. Park, “Improved Hard-Reliability Based Majority-Logic Decoding for Non-Binary LDPC Codes,” IEEE Communications Letters, vol. 21, no. 2, pp. 230-233, 2017. |
| [84] | G. Liva, B. Matuz, E. Paolini, and M. F. Flanagan, "Non-binary LDPC codes for orthogonal modulations: Analysis and code design." in IEEE International Conference on Communications (ICC), 2017, pp. 1-6. |
| [85] | I. E. Bocharova, B. D. Kudryashov, and V. Skachek, "Performance of ML decoding for ensembles of binary and nonbinary regular LDPC codes of finite lengths." in IEEE International Symposium on Information Theory (ISIT), 2017, pp. 794-798. |
