Bit Flipping Decoders for LDPC Codes: A Short Survey

Bit Flipping Decoders for LDPC Codes: A Short
Survey

Kurakula Madhukar
Department of Electrical, Electronics and Communication Engineering
GITAM Deemed to be University
Hyderabad, India.

Abstract— In the domain of wireless communication systems, Error Control Coding schemes are one of the widely relied upon or responsible methodology for securing the integrity and authenticity of the data transmission process. In the last decade, due to the advent of modern communication standards and their wide range of services, there has been a resurgence of interest and support in the research community towards the conception of efficient and versatile error control coding techniques. Recent developments in the wireless communication-based technologies have witnessed the pliable nature of low-density parity-check (LDPC) codes and their contributions which cannot be overstated. As of now, the decoding schemes based on LDPC codes have emerged as one of the most promising and efective coding scheme for addressing several key problems of reliable data communication. In this article, comprehensive overview on the on some well-known LDPC hard decision decoding algorithms is provided. In addition, simulations carried out on various LDPC decoding algorithms based on their performance is also presented. Finally, at the end of this review, the scope for future prospects are forecasted through discussions.
Keywords—LDPC; Hard Decision Decoding; Bit Flipping; Finite Geometry;
I. INTRODUCTION
Error Control Coding (ECC) is one of the most widely preferred methodology adopted by various communication and memory systems to minimize the likelihood of errors [1]. In general, many wireless communication-based applications strive to provide seamless high-quality service to its users by employing cost effective and much less computationally intensive methods [2, 3]. In literature, several techniques have been investigated towards the design and development of promising coding schemes which can lower the data transmission and reading errors [4, 5] since the inception of the information age [6]. Among various coding schemes, Low-Density Parity-Check (LDPC) codes are a special class of linear block codes which has become popular in recent years due to its versatile error correcting characteristics [7] and near Shannon limit performance. Originally, LDPC discovered by Gallager [8] was initially brought in as a generalized version for various applications by Mackay and his research team in [9, 10]. Since their reminiscence, LDPC codes are gaining traction as a popular choice of coding scheme in various wireless application areas [11]. Basically, according to their error correcting mechanisms, decoding algorithms for LDPC codes can be categorized into two main classes, i.e., soft-decision [12] and hard-decision [13] based approaches.
Among the hard decision algorithms, bit-flipping (BF) algorithms flip one or a group of bits based on the values of the flipping functions (FFs) computed in each iteration. The FF associated with a variable node (VN) is a reliability metric of the corresponding bit decision and depends on the binary-valued checksums of the VN’s connected check nodes (CNs). Although BF algorithms are much simpler than the SPA, their performance is far from optimal. To reduce the performance gap, many variants of Gallager’s BF algorithms have been proposed. Most of them tried to improve the VN’s reliability metric (the FF) and/or the method of selecting the flipped bits, achieving different degrees of bit error rate (BER) and convergence rate performance enhancements at the cost of higher complexity. Figure 1 illustrates the general classification of hard decision decoding approaches available for LDPC codes.

Figure 1: Classification of Hard-Decision Decoders

This manuscript attempts to give a short survey of some of the most used bit flipping algorithms and its variants. Section II describes the various famous bit flipping algorithms and their mathematical representations. In Section III, we give simulation results of the discussed algorithms for various LDPC codes.
II. BIT FLIPPING ALGORITHMS

A. Notations
We denote a regular binary LDPC code with Variable Node (VN) degree dv and Check Node (CN) degree dc by (ே୸௄)(ௗ𝑣୸ௗ𝑐). The code is the null space of ெ×ே parity check matrix ଋ=}ு𝑚𝑛~ . Let ଲbe a codeword and assume that Binary Phase Shift Keying (BPSK) modulation is used so that codeword ଲ=}௨ௌ୸௨்୸୅୸௨ே~ is mapped into a bipolar sequence ଵ=}௫ௌ୸௫்୸୅୸௫ே~ . This is sent through an Additive White Gaussian Noise (AWGN) channel with two-sided power spectral density of ேோ଻ଋ W/Hz. Let ଶ=}௬ௌ୸௬்୸୅୸௬ே~be the soft channel values obtained at the receiver’s coherent matched filer output. The sequence ଷ=}௭ௌ୸௭்୸୅୸௭ே~ is obtained by taking hard decision on the components of ଶ. Let ଲ̃=
IJERTV9IS110120 www.ijert.org
(This work is licensed under a Creative Commons Attribution 4.0 International License.)
Published by : International Journal of Engineering Research & Technology (IJERT)
http://www.ijert.org ISSN: 2278-0181
Vol. 9 Issue 11, November-2020

}̂௨ௌ୸௨்̂୸୅୸௨̂ே~be the decoded binary sequence. The syndrome vector ର=}௦ௌ୸௦்୸୅୸௦ଢ଼~ is computed by ର=ଲ̃ଋ𝑇(௠௢ௗଋ). Also, we denote the nth VN by ௩𝑛 and mth CN by ௖𝑚. Let ୾(௡) denote the set of indices of the neighboring CNs of ௩𝑛 and ୿(௠)denote the set of indices of the neighboring VNs of ௖𝑚.
B. Generic BF Decoding Algorithm
A BF decoding algorithm has four important parameters: ௟, the iteration number; ௟𝑚𝑎𝑥, the maximum iteration number; ா𝑛, the FF; and ୳, the index set of flipped bits (FB). The algorithm performs the computation of ா𝑛 and generating the FB set ୳.
The algorithm steps are given as follows:

ா௡ =−୰|௬௡|− ∑ ௪𝑚𝑛(ଊ−ଋ௦௠) ௠ஊ୾(௡) (4)
where ௪𝑚𝑛 = ଦଢଧ ஘and ୰ >ଉ.஘௬𝑛 ′𝑛 ′ 𝜖୿(𝑚)ொ𝑛
G. Gradient Descent Bit Flipping (GDBF) For Gradient Descent BF (GDBF) [17], the FF is
ா௡ =−௬(ଊ−ଋ̃௨௡)− ∑ (ଊ−ଋ௦௠)௡௠ஊ୾(௡) (5)

An FF is also called as cost function or inversion function. It helps to take a tentative decision on VN. Given FF values and FB rules, we select a set of VNs and flip the corresponding bits whose FF values exceed a threshold.
C. Gallager Decoding
Gallager proposed a simple bit flipping algorithm [8] whose FF is given as (1)
ா௡=− ∑ (ଊ−ଋ௦௠) ௠ஊ୾(௡)
D. Weighted Bit Flipping (WBF)
For Weighted Bit Flipping (WBF) decoding [14], the FF is
ா௡ =− ∑ ௪𝑚𝑛(ଊ−ଋ௦௠) ௠ஊ୾(௡) (2)
where ௪𝑚𝑛 = ଦଢଧ ஘.஘௬𝑛 ′𝑛 ′ 𝜖୿(𝑚)
E. Modified Weighted Bit Flipping (MWBF) For Modified WBF (MWBF) [15], the FF is
ா௡ =−୰|௬௡|− ∑ ௪𝑚𝑛(ଊ−ଋ௦௠) ௠ஊ୾(௡) (3)

where ௪𝑚𝑛= ଦଢଧ ஘and ୰>ଉ.
஘௬𝑛′
𝑛′𝜖୿(𝑚)
F. Improved Modified Weighted Bit Flipping (IMWBF)
For Improved MWBF (IMWBF) [16], the FF is

H. Flipped Bit Selection Rules
For all the above algorithms, only the bits related to VN having the largest ா𝑛 value is (are) flipped in each iteration. Thus, the FB set is
(6)
୳={௡஘௡=௔௥௚ଦଚ଱ ா௜|
௜
The simplest FB selection rule for flipping multiple bits to increase the convergence is
୳={௡஘ா௡≥୳| (7)
where ୳ is the threshold obtained from simulations. The optimal value of the threshold is derived by Gallager in [8].
III. SIMULATION RESULTS

In this section, we will see the performance of the decoding algorithms discussed in the previous section for Euclidean geometry (EG) based LDPC codes, a class of finite geometry (FG) LDPC codes [14]. The code considered in our simulations is a (ଊଉଋଌ୸ଐ଑ଊ)(ଌଋ୸ଌଋ)EG-LDPC code whose code rate is
0.763 with a very high node degree.

Figure 2: BER performance of several bit flipping decoders for (1023,781) EG-LDPC code.

Figure 2 shows the Bit Error Rate (BER) performance of Gallager decoder (BF), WBF, IMWBF and GDBF respectively for a (1023,781) EG-LDPC code. Since MWBF and IMWBF are almost similar, BER performance of MWBF is not shown. From
IJERTV9IS110120 www.ijert.org

(This work is licensed under a Creative Commons Attribution 4.0 International License.)
Published by : International Journal of Engineering Research & Technology (IJERT)
http://www.ijert.org ISSN: 2278-0181
Vol. 9 Issue 11, November-2020

our simulations we have found that the value ୰ for IMWBF is
0.2. At a BER of 10-3 we can see that IMWBF stands more than
0.5 dB better when compared to BF, WBF and GDBF. The numbers in the legends of the Figure 2 represent the maximum number of iterations ௟𝑚𝑎𝑥.
IV. CONCLUSIONS AND FUTURE WORK
For the past few decades, the development of error control coding techniques based on LDPC decoding algorithms has emerged as an active area of research and source of inspiration for several outstanding researchers worldwide. In this short survey paper, we surveyed the commonly used Bit flipping decoders for LDPC codes summarizing their mathematical representations and demonstrated their performance for finite geometry based LDPC code. The future work would consist of doing more literature survey and actually working towards their real time implementations.
REFERENCES
[1] Huang L, Zhang H, Li R, Ge Y, Wang J, “AI coding: learning to construct error correction codes,” IEEE Transactions on Communications, Vol. 68, no.1, pp. 26-39, Nov 2019.
[2] Xing Z, Liu K, Liu Y, “Low-complexity companding function design for PAPR reduction in OFDM systems,” IET Communications, Vol.14, no.10, pp.1581–1587, 2020.
[3] Arum SC, Grace D, Mitchell PD, “A review of wireless communication using high-altitude platforms for extended coverage and capacity,” Computer Communications, 2020.
[4] Babar Z, Chandra D, Nguyen HV, Botsinis P, Alanis D, Ng SX, Hanzo L, “Duality of quantum and classical error correction codes: design principles and examples,” IEEE Communications Surveys & Tutorials, Vol 21, no.1, pp.970–1010, 2019.

[5] Egilmez ZBK, Xiang L, Maunder RG, Hanzo L, “The development, operation and performance of the 5G polar codes,” IEEE Communication Surveys & Tutorials, Vol 22, no.1, pp.96–122, 2019.
[6] Shannon C.E, “A mathematical theory of communication,” ACM SIGMOBILE mobile computing and communications review, Vol 5, no.1, 2001.
[7] Abdessalem MB, Zribi A, Matsumoto T, Dupraz E, Bouallègue A, “LDPC-based joint source channel coding and decoding strategies for single relay cooperative communications,” Physical Communication, Vol 38, 2020.
[8] Gallager RG, “Low-density parity-check codes,” IRE Transactions on Information Theory, Vol 8, no.1, pp.21–28, 1962.
[9] Mackay DJC,“Good error correcting codes based on very sparse matrices,” IEEE Transactions on Information Theory, Vol 45, no.2, pp.399–431, 1999.
[10] Davey MC, MacKay D,“Low-density parity check codes over GF(q)” IEEE Communication Letters, Vol 2, no.6, pp.165–167, 1998.
[11] Richardson TJ, Urbanke RL, “The Renaissance of Gallager’s low-density parity-check codes,” IEEE Communications Magazine, Vol 41, no.8, pp.126–131, 2003.
[12] Roberts MK, Mohanram SS, Shanmugasundaram N, “An improved low complex ofset min-sum based decoding algorithm for LDPC codes,” Mobile Network Applications, Vol 24, no.6, pp.1848–1852, 2019.
[13] Chen Y, Cui H, Lin J, Wang Z, “Fine-grained bit-fipping decoding for LDPC codes,” IEEE Transactions on Circuits and Systems II: Express Briefs, Vol 67, no.5, pp.896–900, 2020.
[14] Y. Kou, S. Lin, and M. Fossorier, “Low density parity check codes based on finite geometries: a rediscovery and more,” IEEE Trans. Inf. Theory,
vol. 47, pp.2711-2736, Nov. 2001.

[15] J. Zhang and M. Fossorier, “A modified weighted bit-flipping decoding of low-density parity-check codes,” IEEE Commun. Lett., vol. 8, no. 3, pp. 165-167, Mar. 2004.
[16] M. Jiang, C. Zhao, Z. Shi, and Y. Chen, “An improvement on the modified weighted bit flipping decoding algorithm for LDPC codes,” IEEE Commun. Lett., vol. 9, no. 9, pp. 814-816, Sep. 2005.
[17] T. Wadayama et al., “Gradient descent bit flipping algorithms for decoding LDPC codes,” IEEE Trans. Commun., vol. 58, no. 6, pp. 16101614, Jun. 2010.
IJERTV9IS110120 www.ijert.org
(This work is licensed under a Creative Commons Attribution 4.0 International License.)