Reliability Analysis of the Joint LDPC Decoding Algorithms over the Multiple Access Channels
محورهای موضوعی : Communication Systems & Devices
1 - University of Tabriz
کلید واژه: Multi-Edge Type LDPC Codes, BER Performance, Joint SPA, Joint Channel Decoding Algorithm, Multiple Access Channel,
چکیده مقاله :
The joint Low Density Parity-Check (LDPC) decoding schemes iteratively decode the received data from multiple channels. Mostly, the available data in different channels are correlated and there is kind of dependency between the links or channels. In recent decades, the graph-based codes have been considered for the communication network scenarios. The performance of these codes is close to the existing theoretical bounds and their complexity is not high which cause the possibility of real world implementation and exploitation. The Multiple Access Channel (MAC) scenario with multiple senders which aim to send correlated data to a single receiver is considered. An analysis on the reliability of the Bit Error Rate (BER) performance of the Joint Sum-Product (JSP) decoding algorithm is presented for a two-link case, which can be extended to higher number of links. The effect of parameter variations on the BER performance is studied. These parameters include: the total number of iterations, the codeword length, the total number of rounds, and the coding rate in the JSP algorithm. An optimal value of the parameters is selected during the design procedure of a communication network by considering its limitations and complexity criterion. The JSP algorithm is a reliable scheme for jointly decoding of noisy binary data from different origins.
The joint Low Density Parity-Check (LDPC) decoding schemes iteratively decode the received data from multiple channels. Mostly, the available data in different channels are correlated and there is kind of dependency between the links or channels. In recent decades, the graph-based codes have been considered for the communication network scenarios. The performance of these codes is close to the existing theoretical bounds and their complexity is not high which cause the possibility of real world implementation and exploitation. The Multiple Access Channel (MAC) scenario with multiple senders which aim to send correlated data to a single receiver is considered. An analysis on the reliability of the Bit Error Rate (BER) performance of the Joint Sum-Product (JSP) decoding algorithm is presented for a two-link case, which can be extended to higher number of links. The effect of parameter variations on the BER performance is studied. These parameters include: the total number of iterations, the codeword length, the total number of rounds, and the coding rate in the JSP algorithm. An optimal value of the parameters is selected during the design procedure of a communication network by considering its limitations and complexity criterion. The JSP algorithm is a reliable scheme for jointly decoding of noisy binary data from different origins.
[1] E. C. Van Der Meulen, “The discrete memoryless channel with two senders and one receiver”, In Proc. IEEE Int. Symp. Information Theory (ISIT), September 1971, pp. 78.
[2] R. Ahlswede, “The capacity region of a channel with two senders and two receivers”, Annals of probability, Vol. 2, No. 5, 1974, pp. 805-814.
[3] A. Khandekar, “Graph-based codes and iterative decoding”, Ph.D. thesis, California Institute of Technology, USA, 2002.
[4] J. Scarlett, A. Martinez, and A. G. Fabregas, “Mismatched multi-letter successive decoding for the multiple-access channel”, IEEE Transactions on Information Theory, Vol. 64, No. 4, 2017, pp. 2253-2266.
[5] P. Li, X. Jian, F. Wang, S. Fu, and Z. Zhang, “Theoretical throughput analysis for massive random access with spatial successive decoding”, IEEE Transactions on Vehicular Technology, Vol. 69, No. 7, 2020, pp. 7998-8002.
[6] M. Nangir, R. Asvadi, J. Chen, M. Ahmadian-Attari, and T. Matsumoto, “Successive Wyner-Ziv Coding for the Binary CEO Problem under Logarithmic Loss”, IEEE Transactions on Communications, Vol. 67, No .11, 2019, pp. 7512-7525.
[7] M. Nangir, J. Pourrostam, J. M. Niya, and B. M. Tazehkand, “Comparison Between the Joint and Successive Decoding Schemes for the Binary CEO Problem”, In IEEE 28th Iranian Conference on Electrical Engineering (ICEE), August 2020, pp. 1-5.
[8] S. Papaharalabos and P. T. Mathiopoulos, “Simplified sum-product algorithm for decoding LDPC codes with optimal performance,” Electronics Letters, Vol. 45, No. 2, January 2009, pp. 116-117.
[9] M. Nangir, R. Asvadi, M. Ahmadian-Attari, and J. Chen, “Analysis and code design for the binary CEO problem under logarithmic loss”, IEEE Transactions on Communications, Vol. 66, No. 12, 2018, pp. 6003-6014.
[10] H. Khodaei Jooshin, and M. Nangir, “Reliability Analysis of the Sum-Product Decoding Algorithm for the PSK Modulation Scheme”, Journal of Information Systems and Telecommunication (JIST), Vol. 8, No. 3, 2020, pp. 167-174.
[11] A. El Gamal, and Y. H. Kim, Network information theory, Cambridge University Press, 2011.
[12] M. Nangir, R. Asvadi, M. Ahmadian-Attari, and J. Chen, “Successive Wyner-Ziv coding for the binary CEO problem under log-loss”, In IEEE 29th Biennial Symposium on Communications (BSC), Canada, 2018, pp. 1-5.
[13] Z. Goldfeld, and H. H. Permuter, “A Useful Analogy Between Wiretap and Gelfand-Pinsker Channels”, In IEEE International Symposium on Information Theory (ISIT), 2018, pp. 121-125.
[14] M. Nangir, R. Asvadi, M. Ahmadian-Attari, and J. Chen, ‘Binary CEO problem under log-loss with BSC test-channel model”, In IEEE 29th Biennial Symposium on Communications (BSC), 2018, pp. 1-5.
[15] F. Vatta, A. Soranzo, M. Comisso, G. Buttazzoni, and F. Babich, “Performance study of a class of irregular LDPC codes through low complexity bounds on their belief-propagation decoding thresholds”, In IEEE AEIT International Annual Conference, 2019, pp. 1-6.
[16] S. Jayasooriya, M. Shirvani moghaddam, L. Ong, G. Lechner, and S. J. Johnson, “A new density evolution approximation for LDPC and multi-edge type LDPC codes”, IEEE Transactions on Communications, Vol. 64, No. 10, 2016, pp. 4044-4056.
[17] S. Jeong, and J. Ha, “On the Design of Multi-Edge Type Low-Density Parity-Check Codes”, IEEE Transactions on Communications, Vol. 67, No. 10, 2019, pp. 6652-6667.
[18] J. Du, L. Zhou, L. Yang, S. Peng and J. Yuan, "A New LDPC Coded Scheme for Two-User Gaussian Multiple Access Channels," in IEEE Communications Letters, vol. 22, no. 1, pp. 21-24, Jan. 2018.
[19] S. Cammerer, X. Wang, Y. Ma and S. t. Brink, "Spatially Coupled LDPC Codes and the Multiple Access Channel," 2019 53rd Annual Conference on Information Sciences and Systems (CISS), 2019, pp. 1-6.
[20] M. B. Abdessalem, A. Zribi, T. Matsumoto and A. Bouallègue, "LDPC-based Joint Source-Channel-Network Coding for the Multiple Access Relay Channel," 2018 6th International Conference on Wireless Networks and Mobile Communications (WINCOM), 2018, pp. 1-6.
[21] B. K. Ng and C. Lam, "Joint Power and Modulation Optimization in Two-User Non-Orthogonal Multiple Access Channels: A Minimum Error Probability Approach," in IEEE Transactions on Vehicular Technology, vol. 67, no. 11, pp. 10693-10703, Nov. 2018.
[22] M. Ebada, S. Cammerer, A. Elkelesh, M. Geiselhart and S. t. Brink, "Iterative Detection and Decoding of Finite-Length Polar Codes in Gaussian Multiple Access Channels," 2020 54th Asilomar Conference on Signals, Systems, and Computers, 2020, pp. 683-688.
[23] Z. Sun, M. Shao, J. Chen, K. M. Wong, and X. Wu, “Achieving the rate-distortion bound with low-density generator matrix codes”, IEEE Transactions on Communications, Vol. 58, No. 6, 2010, pp. 1643-1653.
[24] T. Richardson, and R. Urbanke, Modern coding theory, Cambridge University Press, 2008.
[25] D. H. Schonberg, “Practical distributed source coding and its application to the compression of encrypted data”, Ph.D. thesis, University of California, Berkeley, USA, 2007.
Reliability Analysis of the Joint LDPC Decoding Algorithms over the Multiple Access Channels
Mahdi Nangir * Faculty of Electrical and Computer Engineering, University of Tabriz, Iran nangir@tabrizu.ac.ir
Received: 11/Jun/2021 Revised: 24/Nov/2021 Accepted: 13/Dec/2021 |
|
Abstract
The joint Low Density Parity-Check (LDPC) decoding schemes iteratively decode the received data from multiple channels. Mostly, the available data in different channels are correlated and there is kind of dependency between the links or channels. In recent decades, the graph-based codes have been considered for the communication network scenarios. The performance of these codes is close to the existing theoretical bounds and their complexity is not high which cause the possibility of real world implementation and exploitation. The Multiple Access Channel (MAC) scenario with multiple senders which aim to send correlated data to a single receiver is considered. An analysis on the reliability of the Bit Error Rate (BER) performance of the Joint Sum-Product (JSP) decoding algorithm is presented for a two-link case, which can be extended to higher number of links. The effect of parameter variations on the BER performance is studied. These parameters include: the total number of iterations, the codeword length, the total number of rounds, and the coding rate in the JSP algorithm. An optimal value of the parameters is selected during the design procedure of a communication network by considering its limitations and complexity criterion. The JSP algorithm is a reliable scheme for jointly decoding of noisy binary data from different origins.
Keywords: Multi-Edge Type LDPC Codes; BER Performance; Joint SPA; Joint Channel Decoding Algorithm; Multiple Access Channel.
1- Introduction
Recently, wireless sensor networks (WSN) and radio access networks (RAN) have many applications in telecommunication industry. In these networks, numerous amount of correlated data have been generated and shared to finally send to a central destination. The receiver aims to decode multiple correlated data coming from multiple links or channels. A proper model for describing this scenario is the multiple access channel (MAC) model [1] which its theoretical bounds is derived in [2].
The central receiver in a MAC requires to jointly decode received data and reconstruct them by exploiting the correlation and similarity between them. Joint decoding of the data by employing graph-based codes has acceptable complexity and close performance to the existing theoretical bounds. Due to these advantages, it is practical and can be implemented in real-world applications. These schemes iteratively reconstruct corrupted data [3].
The successive decoding schemes are another efficient methods to decode multiple correlated data [4-6]. The performance of successive and joint decoding schemes are compared in [7]. Joint decoding scheme has close performance to the theoretical bounds. The joint sum-product algorithm (SPA) is an extended version of SPA [8] which is used in joint decoding scenarios in multi-terminal source coding problems [9] and multi-link channels such as the MAC. In the joint SPA there are various parameters which affects the bit error rate (BER) performance of the algorithm which aims to decode correlated data. In this work, we investigate the performance of the joint SPA with respect to the variation of key parameters which plays important role in the decoding process. In general, increasing the value of parameters cause to improve performance along with to increase the complexity [10]. This trade-off motivate us to study and analysis the BER performance of the joint SPA by changing parameters which provides a useful view to design decoder and to select parameters properly.
Capacity concept in communication networks is an extension of the channel capacity of a point-to-point communication system proposed by Shannon in 1948 and it determines the maximum possible rate under an arbitrary small BER value [11]. Practical implementations with finite code lengths almost have a small gap between rate values and capacity to achieve small enough values of BER. The gap value is a good measure for comparison of different decoding algorithms and schemes.
The channel coding and source coding schemes and also their combinations are used in network scenarios such as the Wyner-Ziv problem [12], the Gelfand-Pinsker problem [13], and the CEO problem [14]. In this paper, we implement a joint SPA on the MAC and analysis its performance based on the variation of key parameters. This provides a reliability analysis for the algorithm over the MAC.
The joint SPA iteratively corrects errors which are occurred in the data by the noise of communication channel which is assumed to be an Additive White Gaussian Noise (AWGN) in our work. The LDPC codes is a strong and efficient group of error correction codes which can achieve the channel capacity and small BER values, when large enough code lengths are utilized [15]. In this work, we employ an extension of LDPC codes which are proper to network scenarios and called multi-edge type LDPC codes [16-17]. These graph-based codes are able to decode jointly and simultaneously the correlated data coming from separate links and channels.
A coding scheme is proposed for the two-user case of a Gaussian MAC based on LDPC codes [18]. Also, spatially coupled LDPC codes are utilized to multi-user detection over the MAC models to get advantages [19]. For the Multiple Access Relay Channels, a joint source-channel-network coding scheme is investigated in [20], which employs LDPC codes. A minimum error probability approach is studied in [21] to present a joint optimization method for two-user case in a non-orthogonal MAC. Besides the LDPC codes, other channel codes are employed for coding MACs. For instance, in [22] the polar codes which are strong channel codes are applied for the Gaussian MAC.
The purpose of a communication system and network designer in the practical implementation phase is to determine all parameters in the utilized algorithms. Our focus is on the key parameters of the joint decoding such as block length of codes, the total number of iterations and rounds in the joint SPA, and the coding rate. According to the criteria and expectations of the users with considering some aspects such as the complexity, one can choose the best possible value of the parameters by using our reported results and analyses. Throughout this paper, we present results based on a specific designed parity-check matrix H of a multi-edge type LDPC code, i.e. the reported results depend on the matrix H and its details. The performance of a reliable algorithm should not have tremendous variations by parameter changing. Finally, our presented results show that the joint SPA is a reliable algorithm for joint decoding of the MAC.
The main motivations of this research work can be listed as follows:
1- Graph-based codes are efficient tools in multi-user communication scenarios. Hence, we evaluate their performance in the MAC as an important case.
2- The SPA is generally for point-to-point communication, which is considered here for the case of multiple sender and encoder.
3- The BER performance of an efficient coding scheme should be reliable with respect to parameter variations, which is investigated in this paper.
The rest of this paper is organized as follows: In section II, the channel model and the joint decoding algorithm are proposed. Furthermore, the details of the joint SPA are provided in this section. Simulation results and discussions are presented in section III. Finally, section IV concludes this paper.
2- Problem Model and Decoding scheme
In this section, the problem model is provided and formulation of the joint SPA is given as an iterative message-passing algorithm as a joint decoding scheme. Prior to that we present the concept of the multi-edge type LDPC codes which the joint SPA is run by employing them.
2-1- MAC and its Limitations
The MAC is a many-to-one communication scenario which appears in real world applications such as the uplink transmission in wireless cellular and satellite communication systems. It also appears in computer networks when several information packets are sent to a single node via multiple links. A simple representation of the MAC is shown in Fig. 1, which N users aims to send their data to a single receiver.
Fig. 1: Multiple Access Communication Channel Model.
A single-letter characterization of the capacity region of the MAC with only two channels are as follows:
(1)
where, 
is the output of the encoder in the i-th channel. It is assumed that a message 
is encoded to. The codewords
and 
are the inputs of the MAC and its output is
. The probabilistic channel model is assumed to be
. The described model is depicted in the following figure.
Fig. 2: Two-link case MAC.
We consider the binary erasure MAC in our implementations [11], in which and are binary and the channel output 
is ternary. In this case, the capacity region is completely determined [11]. We have the following capacity region that is plotted in Fig. 3. Hence,
, we can write:
(2)
Fig. 3: The capacity region of the binary erasure MAC.
A joint decoding scheme such as the joint SPA wishes to recover the noisy corrupted data whit minimum possible BER and tolerable complexity.
2-2- Multi-Edge Type LDPC Codes
A conventional LDPC code consists of variable nodes and check nodes connected with each other with some edges that are in one-to-one correspondence with 1’s in the parity check matrix H. For an LDPC code, the number of 1’s are much less than the number of 0’s in H. As an extension of the classic LDPC codes, we have the multi-edge type LDPC codes in which there are a single group of the variable nodes and several groups of the check nodes connected with the variable nodes. There is no connection between groups of the check nodes. Thus, for an L-edge type LDPC code, we have L parity check matrix 
for
, each of which are related to a single LDPC code. They have shared variable nodes and separate check nodes. The total parity check matrix of the multi-edge type LDPC code are defined as follows:
(3)
For more illustration the Tanner graph representation of a two-edge type LDPC code is shown in Fig. 4. As it is seen, there are two types or two groups of the check nodes shown by squares, which are connected to the variable nodes shown by circles.
Fig. 4: Tanner graph of a two-edge type LDPC code.
The classical message passing algorithms for the channel decoding, e.g. the SPA, or for the source encoding, e.g. the Bias propagation consist of some iterations in which some messages are passed between the variable nodes and the check nodes of LDPC codes or LDGM 1 codes until reach to a stable condition. There exists a similar condition in the iterative joint decoding algorithms like the joint SPA in which some messages are passed between the variable nodes and a specific group of the check nodes in each round within a specific number of iterations. Therefore, by utilizing the multi-edge type LDPC codes, we are able to implement joint MAC decoding algorithms iteratively.
Similar to the SPA, short length for the girth of the LDPC codes cause some problems in the decoding procedure [24]. The minimum required girth of Tanner graph of the LDPC codes is 6 to perform well, which is satisfied in our implementations.
Generally, for an L-edge type LDPC code, we can consider L rate values. If we want to achieve small values of the BER, then all L rates must be located inside of the capacity region. This condition should be considered in the design procedure of the multi-edge type LDPC codes and it obviously affects rate and code lengths. For instance, in the case of the binary erasure MAC, rates of the channel must be satisfied the inequalities in (1).
In general, a multi-edge type LDPC code is an extension of the classical LDPC code. The difference between them is that by considering all groups of check nodes together, unlike classical LDPC codes, the number of check nodes in multi-type LDPC codes can be more than number of variable nodes. It should be noted that a single group of check nodes along with the variable nodes is a classical LDPC code and it is employed in each link or channel for accomplishing a complete channel coding procedure.
2-3- The Joint SPA
The joint SPA is a modified version of the SPA [10]. It is applicable to joint decoding scenarios while the SPA is for point-to-point communication scenarios.
For the sake of simplicity, we describe a joint SPA for a two-link case over a two-edge type LDPC code. This algorithm consists of 
rounds. For describing the decoding algorithm with more details, we use the following notations and assumptions:
- 
shows the LLR values passing from m-th edge and coming from (to) the i-th variable node in each iteration and each round and iteration of the algorithm.
- 
for 
shows the degree of the i-th variable node (j-th check node).
- 
shows the LLR values passing from m-th edge and coming from (to) the j-th check node in each iteration and each round of the algorithm.
- The total number of rounds is 
- The total number of iterations is 
- n is the codeword block length.
Clearly, the parity check matrix determines connections between the nodes and based on these connections LLR messages are passed between the check nodes and variable nodes.
First, the received syndromes are located in the check nodes of the two-edge type LDPC code. The first one is located in the type one check nodes and the second one is located in the type two check nodes, respectively. The proposed algorithm have rounds, where 
. Each round contains of 
iterations, where 
iterations are done in the first LDPC code and 
in the second one. Note that the information in the first and the second links are reconstructed in 
and 
iterations, respectively.
In the end of the algorithm, the reconstructed bit can be found in the variable nodes after a sufficient number of rounds.
At the beginning of the algorithm, the initial LLR values of the variable nodes are randomly determined. During iterations in each round, their values are changed and updated until reaching to the final iteration or the LLR values converge.
Encoding and Decoding Procedure:
Two information sequences are encoded by two LDPC codes with parity check matrices of 
and 
in the first and second links. Therefore, two LDPC codewords are sent to the receiver through a noisy channel which causes some errors in the bit streams.
In the receiver, a joint decoder receives the noisy codewords and calculate their syndromes at once. Then, these syndromes are employed to reconstruct information sequences of the links by the joint SPA.
By multiplying the information bit of length 
with the generator matrix 
with the size of
, a codeword 
is obtained, for i=1,2. is a valid codeword if and only if 
. These two codewords are sent via a noisy channel to the decoder side. Decoder receives 
, where 
is a random Bernoulli noise with parameter 
. Then, it calculates syndromes 
and starts to accomplish the joint SPA to recover LDPC codewords and information packets.
Without loss of generality, we suppose 
. Under this assumption, we expect that the codeword 
is decoded and appeared in the variable nodes after rounds. Similarly, that the codeword 
is decoded and appeared in the variable nodes after rounds and obviously we have 
.
Here, we present the update equations of the joint SPA. The initial values of LLRs are as follows:
(4)
where, 
is the bit value of the i-th variable node in the two-edge type LDPC code. Note that, 
is equal to
for the messages toward the type one check nodes; and it is 
for the messages toward the type two check nodes.
During an iteration, the LLR message that is sent from the i-th variable node to a check node using m-th edge is as follows:
(5)
for 
and
. In the first iteration, we set 
. In each iteration the LLR value of 
is allocated to the related 
based on the connections of the two-edge type LDPC code. These LLR values are used in the check node update equations and 
is the number of edge 2 connecting i-th variable node to the j-th check node through m-th edge from variable nodes side. The update equations engaged in the j-th check node of the two-edge type LDPC code are as follows:
(6)
where, 
and 
is bit value of the j-th check node. Note that it can belong to either 
or
. We set 
and continue the algorithm with update equations. Finally, after running a sufficient number of iterations, we can estimate the codewords and decide about the binary values of variable nodes based on the following rule:
(7)
Based on (7), we decode the codewords that have been sent from the different links of the MAC. Note that, this decoding is in the category of the error correction algorithms.
3- Implementation Results and Analyses
In this section, we present implementation results which reports the performance of the algorithm for different values of the important parameters. As it is known, the BER value can represent the efficiency and power of a scheme in channel decoding scenarios. All reported BER values are obtained by averaging over 50 tests when random binary information sources are generated.
We focus on some key parameters which play important role in the decoding procedure. They include: the number of iterations in the algorithm, the number of rounds in the algorithm, the code length, and the coding rate. We compare the results in various cases and present the BER performance versus different values of the signal to noise ratio. We compute the BER in our implementation results using the following formula:
(8)
after rounds when is decoded. Similarly, is decoded after rounds and BER is equal to:
(9)
In (8) and (9), 
is expectation, 
shows the Hamming distance between two binary sequences, and 
is obtained from (7). We define
(10)
In what follows, the simulation and implementation results are reported which shows the BER performance of a MAC scenario with binary sources which is equipped with the joint SPA for jointly decoding of noisy information sources employing a two-edge type LDPC code. Generally, we know that the BER value decreases by increasing the signal to noise ratio.
In Fig. 5, it is shown that the BER performance of the algorithm improves by increasing the number of maximum number of iterations in the SPA in each round. Note that we have used a same parity-check matrix H with the rate of 1. The code length is considered to be 104 and the total number of rounds is 25. Increasing the number of iterations cause to increase the accuracy of the convergence in the joint SPA similar to the conventional SPA.
Furthermore, it is seen that by increasing the total number of iterations more and more, the BER performance does not improve significantly. Therefore, the sensitivity of the joint SPA over a MAC with respect to the total number of iterations is high for small number of iterations and vice versa.
Fig. 5: The BER performance of the joint SPA for the MAC for different number of iterations.
In fig 6, we propose the BER performance of the joint SPA with respect to the variation of the codeword length n. The total number of iterations is 100. The total number of rounds is assumed to be 25 and for simplicity we consider rate is equal to be 1 in this implementation. As it is seen, increasing codeword length cause to reduce the BER value. This observation exactly happens in the point-to-point channel coding scenarios in telecommunication. It should be noted that the complexity increases with growing the codeword length n.
A communication system designer can choose appropriate and reliable parameters of the message-passing algorithms and establish a trade-off between the acceptable BER performance and the complexity. Acceptable performance and complexity strongly depend on the application and the communication scenario. We accept complexity increasing in some real world applications that high security or high reliability is required. In some other applications, we can employ not so large codeword lengths.
We defined the total number of rounds which is shown by r. As it is depicted in Fig. 7, by increasing the total number of rounds, the BER performance of the algorithm improves. This is somehow predictable, because by increasing the total number of rounds the accuracy of the convergence in a message-passing algorithm, such as the joint SPA, increases for a fixed number of iterations and fixed codeword length and rate. Simulation results that are presented in Fig. 7 are obtained for 100 number of iterations. Furthermore, the codeword length is 104 and the rate is equal to be 1. The comparison will be simplified when all parameters except one of them are fixed.
Fig. 6: The BER performance of the joint SPA for the MAC for different code lengths (n).
The running time of an algorithm is another factor which should be considered. The running time increases by growing the total number of iterations and rounds in the joint SPA.
Fig. 7: The BER performance of the joint SPA for the MAC for different number of rounds (r).
Finally, we show the BER performance of the joint SPA with respect to variation of rate values in Fig. 8. We defined the rate as the ratio of the total number of check nodes to the total number of variable nodes in a multi-edge type LDPC code. In this case, n is equal to 104, the total number of iterations is 100, and r is equal to 25.
Based on the results presented in Fig. 8, the BER performance of the joint SPA improves by increasing the value of the rate, i.e. by growing the total number of check nodes when the total number of variable nodes is assumed to be fixed.
Fig. 8: The BER performance of the joint SPA for the MAC for different values of rate.
In message-passing algorithms over the graph-based codes, the number of check nodes shows the independent linear equations should be satisfied on the set of variable nodes. Thus, it is concluded that by growing the number of check nodes, the number of conditions over the variable nodes that should be satisfied increases and this cause to reach more accuracy of convergence in the algorithm. In other words, by increasing the total number of check nodes, we achieve low BER values.
Based on the results which are presented in this section can report the BER value of the joint SPA for some other values of the key parameters by using linear interpolation technique. The obtained results from the linear interpolation are not exact, but they can provide a good view about the performance of the message-passing algorithm. Estimation of the performance in these message-passing algorithms can be done with an arbitrary precision by finding more BER curves versus the signal to noise ratio for various parameters.
4- Conclusions
In this paper, a new scheme for the MAC decoding presented. Graph-based codes are employed to design the joint SPA for reconstructing binary data which are encoded by using multi-edge type LDPC codes. The performance of the proposed scheme is evaluated form the BER point of view. As a communication system designer, we analysis the reliability of the joint SPA with respect to some key parameters including the total number of iterations, the codeword length, the total number of rounds, and the coding rate. We present the BER values of the joint decoding versus different values of the signal to noise ratio. These results helps a system designer to choose appropriate values of the parameters according to the desirable complexity-performance trade-off.
Appendix
The degree distribution of the parity-check matrices are given here. These degree distributions are utilized in the simulations and implementations of the section 3. As it is known, for a single degree distribution, there is not a unique parity-check matrix and there a lot. We construct matrices by utilizing the progressive edge growth method with some approximations. We employ the degree distributions reported in [25].
We employ the following degree distribution for the coding rate of 0.3:
and
We employ the following degree distribution for the coding rate of 0.4:
and
We employ the following degree distribution for the coding rate of 0.5:
and
We employ the following degree distribution for the coding rate of 0.6:
and
References
[1] E. C. Van Der Meulen, “The discrete memoryless channel with two senders and one receiver”, In Proc. IEEE Int. Symp. Information Theory (ISIT), September 1971, pp. 78.
[2] R. Ahlswede, “The capacity region of a channel with two senders and two receivers”, Annals of probability, Vol. 2, No. 5, 1974, pp. 805-814.
[3] A. Khandekar, “Graph-based codes and iterative decoding”, Ph.D. thesis, California Institute of Technology, USA, 2002.
[4] J. Scarlett, A. Martinez, and A. G. Fabregas, “Mismatched multi-letter successive decoding for the multiple-access channel”, IEEE Transactions on Information Theory, Vol. 64, No. 4, 2017, pp. 2253-2266.
[5] P. Li, X. Jian, F. Wang, S. Fu, and Z. Zhang, “Theoretical throughput analysis for massive random access with spatial successive decoding”, IEEE Transactions on Vehicular Technology, Vol. 69, No. 7, 2020, pp. 7998-8002.
[6] M. Nangir, R. Asvadi, J. Chen, M. Ahmadian-Attari, and T. Matsumoto, “Successive Wyner-Ziv Coding for the Binary CEO Problem under Logarithmic Loss”, IEEE Transactions on Communications, Vol. 67, No .11, 2019, pp. 7512-7525.
[7] M. Nangir, J. Pourrostam, J. M. Niya, and B. M. Tazehkand, “Comparison Between the Joint and Successive Decoding Schemes for the Binary CEO Problem”, In IEEE 28th Iranian Conference on Electrical Engineering (ICEE), August 2020, pp. 1-5.
[8] S. Papaharalabos and P. T. Mathiopoulos, “Simplified sum-product algorithm for decoding LDPC codes with optimal performance,” Electronics Letters, Vol. 45, No. 2, January 2009, pp. 116-117.
[9] M. Nangir, R. Asvadi, M. Ahmadian-Attari, and J. Chen, “Analysis and code design for the binary CEO problem under logarithmic loss”, IEEE Transactions on Communications, Vol. 66, No. 12, 2018, pp. 6003-6014.
[10] H. Khodaei Jooshin, and M. Nangir, “Reliability Analysis of the Sum-Product Decoding Algorithm for the PSK Modulation Scheme”, Journal of Information Systems and Telecommunication (JIST), Vol. 8, No. 3, 2020, pp. 167-174.
[11] A. El Gamal, and Y. H. Kim, Network information theory, Cambridge University Press, 2011.
[12] M. Nangir, R. Asvadi, M. Ahmadian-Attari, and J. Chen, “Successive Wyner-Ziv coding for the binary CEO problem under log-loss”, In IEEE 29th Biennial Symposium on Communications (BSC), Canada, 2018, pp. 1-5.
[13] Z. Goldfeld, and H. H. Permuter, “A Useful Analogy Between Wiretap and Gelfand-Pinsker Channels”, In IEEE International Symposium on Information Theory (ISIT), 2018, pp. 121-125.
[14] M. Nangir, R. Asvadi, M. Ahmadian-Attari, and J. Chen, ‘Binary CEO problem under log-loss with BSC test-channel model”, In IEEE 29th Biennial Symposium on Communications (BSC), 2018, pp. 1-5.
[15] F. Vatta, A. Soranzo, M. Comisso, G. Buttazzoni, and F. Babich, “Performance study of a class of irregular LDPC codes through low complexity bounds on their belief-propagation decoding thresholds”, In IEEE AEIT International Annual Conference, 2019, pp. 1-6.
[16] S. Jayasooriya, M. Shirvani moghaddam, L. Ong, G. Lechner, and S. J. Johnson, “A new density evolution approximation for LDPC and multi-edge type LDPC codes”, IEEE Transactions on Communications, Vol. 64, No. 10, 2016, pp. 4044-4056.
[17] S. Jeong, and J. Ha, “On the Design of Multi-Edge Type Low-Density Parity-Check Codes”, IEEE Transactions on Communications, Vol. 67, No. 10, 2019, pp. 6652-6667.
[18] J. Du, L. Zhou, L. Yang, S. Peng and J. Yuan, "A New LDPC Coded Scheme for Two-User Gaussian Multiple Access Channels," in IEEE Communications Letters, vol. 22, no. 1, pp. 21-24, Jan. 2018.
[19] S. Cammerer, X. Wang, Y. Ma and S. t. Brink, "Spatially Coupled LDPC Codes and the Multiple Access Channel," 2019 53rd Annual Conference on Information Sciences and Systems (CISS), 2019, pp. 1-6.
[20] M. B. Abdessalem, A. Zribi, T. Matsumoto and A. Bouallègue, "LDPC-based Joint Source-Channel-Network Coding for the Multiple Access Relay Channel," 2018 6th International Conference on Wireless Networks and Mobile Communications (WINCOM), 2018, pp. 1-6.
[21] B. K. Ng and C. Lam, "Joint Power and Modulation Optimization in Two-User Non-Orthogonal Multiple Access Channels: A Minimum Error Probability Approach," in IEEE Transactions on Vehicular Technology, vol. 67, no. 11, pp. 10693-10703, Nov. 2018.
[22] M. Ebada, S. Cammerer, A. Elkelesh, M. Geiselhart and S. t. Brink, "Iterative Detection and Decoding of Finite-Length Polar Codes in Gaussian Multiple Access Channels," 2020 54th Asilomar Conference on Signals, Systems, and Computers, 2020, pp. 683-688.
[23] Z. Sun, M. Shao, J. Chen, K. M. Wong, and X. Wu, “Achieving the rate-distortion bound with low-density generator matrix codes”, IEEE Transactions on Communications, Vol. 58, No. 6, 2010, pp. 1643-1653.
[24] T. Richardson, and R. Urbanke, Modern coding theory, Cambridge University Press, 2008.
[25] D. H. Schonberg, “Practical distributed source coding and its application to the compression of encrypted data”, Ph.D. thesis, University of California, Berkeley, USA, 2007.
Mahdi Nangir received the B.Sc degree with first rank in Electrical Engineering from University of Tabriz and M.Sc. degree in Communication System Engineering from Sharif University of Technology, Tehran, Iran, in 2010 and 2012, respectively. He received the Ph.D. degree from K. N. Toosi University of Technology, Tehran, Iran, in 2018. He was a finalist of the Mathematics Olympiad and owner of bronze medal in 2005 from Young Scholar Club. He received high ranks in Iranian National Electrical Engineering Student Olympiads of 2009 and 2010. In 2017, he joined McMaster University, Hamilton, Ontario, Canada as a research visiting student. He is now an assistant professor in Faculty of Electrical and Computer Engineering, University of Tabriz, Tabriz, Iran. His research interests include coding and information theory, distributed source coding, data compression algorithms and optimization.
[1] Low Density Generator Matrix (LDGM) codes are the dual codes of the LDPC codes that are proper to the source coding scenarios in communication [23].
[2] From check nodes side.
