Search

It is well known that tree-based theories can describe the properties of undirected clustered networks with extremely accurate results [S. Melnik, \textit{et al}. Phys. Rev. E 83, 036112 (2011)]. It is reasonable to suggest that a motif based theory would be superior to a tree one; since additional neighbour correlations are encapsulated in the motif structure. In this paper we examine bond percolation on random and real world networks using belief propagation in conjunction with edge-disjoint motif covers. We derive exact message passing expressions for cliques and chordless cycles of finite size. Our theoretical model gives good agreement with Monte Carlo simulation and offers a simple, yet substantial improvement on traditional message passing showing that this approach is suitable to study the properties of random and empirical networks., Comment: 14 pages, 7 figures

Low-density parity-check (LDPC) codes are widely used as error correction codes in new generation digital TV standards, such as the second generation of terrestrial digital video broadcasting standard (DVB-T2), Advanced Television Systems Committee (ATSC) 3.0, etc. The nonlinear belief propagation (BP) algorithm has excellent decoding performance for LDPC codes, but is often simplified in hardware implementations by linear min-sum (MS) algorithm due to its high complexity. This simplification also leads to over-estimation problems, which can be corrected by adding factors in conventional algorithms (e.g., normalized min-sum (NMS), offset min-sum (OMS), and variable scaling normalized min-sum (VMS) algorithms). However, the correction factors of these modified MS algorithms cannot adapt to different channels and modulations, and the performance needs further improvement. In this paper, the concepts of over-estimation value (OEV) and over-estimation rate (OER) are introduced to describe the over-estimation problem of the MS algorithm. Then, under the guidance of OEV and OER, a polygonal line min-sum (PMS) algorithm with correction factors adapted to different channels and modulations is proposed according to LLR distribution. Following the properties of OEV and OER, PMS algorithm is further simplified into Simplified PMS (SPMS) algorithm. LDPC codes from ATSC 3.0 are adopted in this paper to evaluate SPMS algorithm in comparison with the conventional algorithms. Extensive simulation results show that the SPMS algorithm for ATSC 3.0 LDPC decoder has at most 1.61dB, 0.24dB and 0.36dB gain over NMS, OMS and VMS algorithms respectively when frame error rate (FER) is at 10⁻⁴ level over additive white Gaussian noise (AWGN) channel with QPSK modulation. More importantly, the simulation results show that the SPMS algorithm can achieve much better performance than these modified MS algorithms over AWGN and Rayleigh channel with higher-order modulations or under limited maximum iteration number.

Simultaneous localization and mapping (SLAM) during communication is emerging. This technology promises to provide information on propagation environments and transceivers' location, thus creating several new services and applications for the Internet of Things and environment-aware communication. Using crowdsourcing data collected by multiple agents appears to be much potential for enhancing SLAM performance. However, the measurement uncertainties in practice and biased estimations from multiple agents may result in serious errors. This study develops a robust SLAM method with measurement plug-and-play and crowdsourcing mechanisms to address the above problems. First, we divide measurements into different categories according to their unknown biases and realize a measurement plug-and-play mechanism by extending the classic belief propagation (BP)-based SLAM method. The proposed mechanism can obtain the time-varying agent location, radio features, and corresponding measurement biases (such as clock bias, orientation bias, and received signal strength model parameters), with high accuracy and robustness in challenging scenarios without any prior information on anchors and agents. Next, we establish a probabilistic crowdsourcing-based SLAM mechanism, in which multiple agents cooperate to construct and refine the radio map in a decentralized manner. Our study presents the first BP-based crowdsourcing that resolves the "double count" and "data reliability" problems through the flexible application of probabilistic data association methods. Numerical results reveal that the crowdsourcing mechanism can further improve the accuracy of the mapping result, which, in turn, ensures the decimeter-level localization accuracy of each agent in a challenging propagation environment., Paper accepted for publication in IEEE Transactions on Wireless Communications

The integration of terrestrial and satellite communications (Satcom) is advocated for satisfying the challenging requirements of seamless, high-performance services. However, both the bandwidth and the power available are limited over satellite channels. In this paper, we propose index modulation (IM) and code-aided Satcom by conveying information by a pair of distinguishable constellation modes and their permutations. In order to combat both the linear and nonlinear distortionimposed by satellite channels, we conceive a factor graph (FG)-based iterative detection algorithm for Satcom relying on dualmode (DM) IM (Sat-DMIM). The correlation amongst Sat-DMIM symbols imposed by both the channel-induced dispersion and the mode-selection mapping is explicitly represented by the FGconstructed. Then the amalgamated belief propagation (BP) and mean field (MF) message passing algorithm is derived over this FG for detecting both the IM bits and the classic constellation mapping bits, while eliminating both the linear and nonlineardistortions. The complexity of the iterative detection algorithm is reduced by linearizing some high-order terms appearing in nonlinear distortion components using the a posteriori estimates of the Sat-DMIM symbols obtained from the previous iteration. Our simulation results demonstrate the power of the proposed amalgamated BP-MF-based and partial linearization approximation-based iterative detection algorithms.

This paper addresses the problem of multitarget tracking using a network of sensing agents with unknown positions. Agents have to both localize themselves in the sensor network and, at the same time, perform multitarget tracking in the presence of clutter and miss detection. These two problems are jointly resolved using a holistic and centralized approach where graph theory is used to describe the statistical relationships among agent states, target states, and observations. A scalable message passing scheme, based on the sum-product algorithm, enables to efficiently approximate the marginal posterior distributions of both agent and target states. The proposed method is general enough to accommodate a full multistatic network configuration, with multiple transmitters and receivers. Numerical simulations show superior performance of the proposed joint approach with respect to the case in which cooperative self-localization and multitarget tracking are performed separately, as the former manages to extract valuable information from targets. Lastly, data acquired in 2018 by the NATO Science and Technology Organization (STO) Centre for Maritime Research and Experimentation (CMRE) through a network of autonomous underwater vehicles demonstrates the effectiveness of the approach in a practical application., Comment: Submitted to IEEE Open Journal of Signal Processing

Regression testing is required in each iteration of microservice systems. Regression testing selection, which reduces testing costs by selecting a subset from the original test cases, is one of the main techniques to optimize regression testing. Existing techniques mainly rely on the information retrieved from artifacts such as code files and system models. For microservice systems with service autonomy, development method diversity and a large amount of services, such artifacts are too difficultly obtained and costly processed to apply those approaches. This paper presents a regression testing selection approach called MRTS-BP, which needs the API gateway layer logs instead of code files and system models as inputs. By parsing the API gateway layer logs, our approach establishes the service dependency matrix, which in further is transformed into a directed graph with the services as nodes. Then, to find out which test cases are affected by service changes, an algorithm based on belief propagation is presented to compute the quantitative results of service-change propagation from the directed graph. Finally, the relationships between original test cases and service-change propagation results are established to select test cases with three strategies. To evaluate the efficiency of MRTS-BP, the empirical study based on four microservice systems is presented. A typical technique RTS-CFG is compared with MRTS-CFG and four experiments are setup to investigate four research questions. The results show that MRTS-BP can not only reduce the number of test cases by half compared with the retest-all strategy while ensuring the safety, but also save at least 20% testing time costs more than that of RTS-CFG. MRTS-BP is more practical than the techniques relying on the artifacts when the latter cannot be implemented due to the artifacts are difficult to obtain and process.

To provide massive connectivity in massive machine type communications (mMTC) for the Internet of Things (IoT) system, a novel grant free random access protocol, called multi-slot pilot allocation (MSPA) is proposed in this paper, where the user equipments (UEs) are permitted to jointly transmit randomly chosen pilot sequences along with their data packets over multi-slot to resolve intra-cell pilot collision. In addition, by utilizing the belief propagation tool for the MSPA protocol, the closed-form expressions to the access failure probability and system throughput in a finite length regime are derived, which are highly desired for practical-interest mMTC network. Further, a guideline for certain mMTC scenarios that target on urgent serving requirement UEs is also proposed to minimize the access latency and maximize the system throughput under diverse access failure probability constraints. Finally, the parametrical analysis for MSPA protocol is given by theoretical proof and simulation verification, which shed light on the advantages of our MSPA protocol over the existing protocols in terms of achieving high throughput and shortening the access latency.

In this paper, we design a kind of robust rateless multi-user code, which is called spatially coupled repeat-accumulate-repeat (SC-RA-R) code, for the interleave-division multiple-access (IDMA) system. The code is constructed by serially concatenating a fixed outer spatially coupled repeat-accumulate (SC-RA) code with an adjustable inner irregular repetition code. It achieves rateless property by simply adjusting the parameters of the inner repetition code. The IDMA system with the proposed SC-RA-R multi-user codes can adapt to varying channel qualities and varying number of users via rateless property while keeping encoder and decoder implementation unchanged. Analytical extrinsic information transfer (EXIT) functions are derived to determine belief propagation (BP) decoding thresholds of SC-RA-R codes on the IDMA system. The optimization expression is also given under the constraint that repeat parameters are monotonically non-decreasing with the sum rate decreasing. The numerical results show that the maximum achievable sum rates of the SC-RA-R codes can be close to the Shannon bound for arbitrary channel qualities. Besides, our proposed SC-RA-R codes have better BP thresholds and bit-error-rate (BER) performances than the conventional optimal parallel-concatenate codes (PCC) and the optimal partially repeated spatially coupled low-density parity-check (PR-SC-LDPC) codes on IDMA systems.

A novel rapid code acquisition scheme is proposed for low spreading factor satellite communication systems relying on message passing algorithms (MPA), where the acquisition of pseudonoise (PN) codes is converted to a sequence estimation problem. Due to the presence of data transitions in low spreading factor systems, conventional acquisition methods based on correlation would show poor capture performance. To overcome the impact of data transitions, this letter proposes a joint data chip and PN sequence estimation technique with the aid of factor graph and belief propagation (BP) algorithm. Meanwhile, in view of the short-term invariance of data chips, this letter models data chips as Markov chains to improve prior knowledge. Simulation results demonstrate that the proposed algorithm can save the mean acquisition time (MAT) about three orders of magnitude and improve the acquisition performance by 2 dB at 99% detection probability compared with serial search.

This correspondence discusses the estimation of direction-of-arrival (DOA) in a magnitude-aided antenna array (MA-AA), where magnitude-only radio frequency (RF) chains are introduced into the classical AA to acquire magnitude measurements. DOAs are initially estimated by the multiple signal classification (MUSIC) algorithm based on the complex-valued measurements from the conventional antennas. After griding the neighborhoods of these initial DOAs, the DOA estimation problem with the hybrid observations in MA-AA is converted as the recovery problem of sparse signals, which can be resolved by generalized approximate message passing (GAMP). Due to the “spatial leakage” effect, non-zero clusters appear around true DOAs. Their positions (i.e., non-zero supports) provide DOAs estimations. Moreover, DOAs and supports remain unchanged in several snapshots, then common supports are shared. Therefore, the cluster-sparse property of sparse signals is exploited by modeling a hidden Markov-tree (HMT) in the shared supports, on which belief propagation (BP) is executed to recover the binary probabilities of supports. Some unknown hyper-parameters in GAMP and BP are learned by expectation-maximization (EM). In comparison to existing estimators, EM-BP-GAMP shows advantages on DOA estimation, computational complexity, and DOA resolution. With the EM-BP-GAMP estimator, MA-AA is more energy-efficient than the classical AA. These advantages are successfully validated by experimental results.

Acquiring accurate channel state information and mitigating severe intersymbol interference are challenging for underwater acoustic communications with moving transceivers due to the rapid changes of the underwater acoustic channels. In this work, we address the issue using a superimposed training (ST) scheme with a powerful channel estimation method. Different from the conventional time-multiplexed training, training sequences with a small power are superimposed with symbol sequences. The training signals are transmitted over all time, leading to enhanced tracking capability to deal with time-varying channels at the cost of only a small power loss. To realize this, based on the belief propagation, we develop a message-passing-based bidirectional channel estimation (BCE) algorithm, where all messages are Gaussian, enabling efficient implementation. In particular, the channel correlations are fully exploited through a forward recursion and a backward recursion, thereby achieving accurate channel estimation. Moreover, the ST-based BCE is combined with channel equalization (in the frequency domain) and decoding, and they are performed jointly in an iterative manner to significantly enhance the overall system performance. Field experiments were carried out in Jiaozhou Bay in 2019, and the results verify the effectiveness of the proposed scheme and algorithm.

Reed–Muller (RM) codes are known for their good maximum likelihood (ML) performance in the short block-length regime. Despite being one of the oldest classes of channel codes, finding a low complexity soft-input decoding scheme is still an open problem. In this work, we present a versatile decoding architecture for RM codes based on their rich automorphism group. The decoding algorithm can be seen as a generalization of multiple-bases belief propagation (MBBP) and may use any polar or RM decoder as constituent decoders. We provide extensive error-rate performance simulations for successive cancellation (SC)-, SC-list (SCL)- and belief propagation (BP)-based constituent decoders. We furthermore compare our results to existing decoding schemes and report a near-ML performance for the RM(3,7)-code (e.g., 0.04 dB away from the ML bound at BLER of 10−3) at a competitive computational cost. Moreover, we provide some insights into the automorphism subgroups of RM codes and SC decoding and, thereby, prove the theoretical limitations of this method with respect to polar codes.

Belief propagation (BP) has attracted increasing attention due to its high parallelism. In this letter, a correction method is proposed to improve the block error rate (BLER) performance of the BP decoder for polar codes so that it is comparable to that of the successive cancellation list (SCL) decoder. Compared with BP flipping (BPF) decoding, the proposed decoder focuses on prior knowledge of the code bits in the factor graph. Two strategies have been proposed to construct the correction set. The simulation results show that the BPC decoder exhibits a BLER similar to that of BPF decoder while reducing the average latency and complexity by half. In addition, the BLER of the BPC decoder can approach that of the cyclic redundancy check (CRC)-aided SCL (CA-SCL) decoder in regions with low and medium signal-to-noise ratios (SNRs).

This paper focuses on the distributed static estimation problem and a Belief Propagation (BP) based estimation algorithm is proposed. We provide a complete analysis for convergence and accuracy of it. More precisely, we offer conditions under which the proposed distributed estimator is guaranteed to converge and we give concrete characterizations of its accuracy. Our results not only give a new algorithm with good performance but also provide a useful analysis framework to learn the properties of a distributed algorithm. It yields better theoretical understanding of the static distributed state estimator and may generate more applications in the future.

Molecular dynamics (MD) simulations provide a wealth of high-dimensional data at all-atom and femtosecond resolution but deciphering mechanistic information from this data is an ongoing challenge in physical chemistry and biophysics. Theoretically speaking, joint probabilities of the equilibrium distribution contain all thermodynamic information, but they prove increasingly difficult to compute and interpret as the dimensionality increases. Here, inspired by tools in probabilistic graphical modeling, we develop a factor graph trained through belief propagation that helps factorize the joint probability into an approximate tractable form that can be easily visualized and used. We validate the study through the analysis of the conformational dynamics of two small peptides with 5 and 9 residues. Our validations include testing the conditional dependency predictions through an intervention scheme inspired by Judea Pearl. Secondly we directly use the belief propagation based approximate probability distribution as a high-dimensional static bias for enhanced sampling, where we achieve spontaneous back-and-forth motion between metastable states that is up to 350 times faster than unbiased MD. We believe this work opens up useful ways to thinking about and dealing with high-dimensional molecular simulations.

In this paper, we propose a channel reliability compensation factor to enhance the performance of belief propagation polar decoders on flat Rayleigh fading channels with noisy channel estimates. By including the error variance of the channel estimate in the derivation of the channel intrinsic information, the formula for calculating the value of channel reliability compensation factor is provided. Simulation results show that a BP polar decoder with the proposed compensation factor achieves a gain of 1.5 dB at a BER of $$10^{-3}$$ compared to the one without using the compensation factor. This gain is obtained with no additional complexity.

The Low-Density Parity Check (LDPC) codes of Euclidean Geometry (EG) are encrypted and decrypted in numerous ways, namely Soft Bit Flipping (SBF), Sequential Peeling Decoder (SPD), Belief Propagation Decoder (BPD), Majority Logic Decoder/Detector (MLDD), and Parallel Peeling Decoder (PPD) decoding algorithms. These algorithms provide aextensive range of trade-offs between latency decoding, power consumption, hardware complexity-required resources, and error rate performance. Therefore, the problem is to communicate a sophisticated technique specifying the both soft and burst errors for effective information transmission. In this research, projected a technique named as Hybrid SBF (HSBF) decoder for EG-LDPC codes, which reduces the decoding complexity and maximizes the signal transmission and reception. In this paper, HSBF is also known as Self Reliability based Weighted Soft Bit Flipping (SRWSBF) Decoder. It is obvious from the outcomes that the proposed technique is better than the decoding algorithms SBF, MLDD, BPD, SPD and PPD. Using Xilinx synthesis and SPARTAN 3e, a simulation model is designed to investigate latency, hardware utilization and power consumption. Average latency of 16.65 percent is found to be reduced. It is observed that in considered synthesis parameters such as number of 4-input LUTs, number of slices, and number of bonded IOBs, excluding number of slice Flip-Flops, hardware utilization is minimized to an average of 4.25 percent. The number of slices Flip-Flops resource use in the proposed HSBF decoding algorithm is slightly higher than other decoding algorithms, i.e. 1.85%. It is noted that, over the decoding algorithms considered in this study, the proposed research study minimizes power consumption by an average of 41.68%. These algorithms are used in multimedia applications, processing systems for security and information.

The success of Multi-hypothesis tracking(MHT) lies in the use of multiple scans, which can often yield improved tracking performance over single scan based data association methods in radar-centric multi-target tracking(MTT) systems. However, with the increase of the number of targets associated with measurements, there is an exponentially increasing need for formulating potential hypotheses, of which the computational cost may be prohibitively expensive. In this paper, a multi-hypothesis fractional belief propagation (MHFBP) based data association algorithm is proposed by the use of a probabilistic graph model for both the previous trajectories and the current measurements. To achieve this idea, there are two main steps. First, the trajectory-related indicators associated state variables are created by making use of a convex fractional free energy (FFE)function. Second, the convex optimization algorithm is used for the objective function and the fractional belief propagation (FBP) is exploited to obtain the best marginal belief of measurement for target association. In this way, incorrect hypotheses with extremely low probability can be eliminated. Finally, the proposed method is applied to multiple scenarios for MTT by indoor radar system. From the results, we can observe that it provides higher tracking performance compared with the classical MHT, feature-aided MHT(FA-MHT) and MHT-belief propagation (MHT-BP). In addition, we see that the computational burden of the proposed method is reduced significantly to avoid the phenomenon of exponential growth with increasing the number of targets.

Belief propagation (BP)-based stereo matching has popular owing to its regularity and ability to yield promising results. Some commonly observed hardware-implementation challenges pertaining to the use of this algorithm are large memory requirements and trade-offs between speed and chip area, along with an increasing disparity range. The paper presents a hardware- and memory-efficient architecture for building a BP-based disparity estimation system capable of overcoming issues associated with large disparity ranges. The proposed architecture is memory-efficient owing to the regularity of its underlying algorithm. In addition, the improved hardware efficiency can be attributed to processing element modifications to demonstrate shareable characteristics. Results obtained in this study reveal a 67.8% reduction in required memory corresponding to a time–area term complexity of $O(L(logL)^{2})$ , where L denotes the disparity range. This result is in stark contrast to the $O(L^{2}logL)$ and $O(L^{2})$ complexities observed in extant studies. Compared to state-of-the-art implementations, the proposed architecture offers an 86.2% gate count reduction for message update units at a disparity range of 512. These results confirm the proposed architecture’s suitability for use in large disparity scenarios.

The state estimation algorithm estimates the values of the state variables based on the measurement model described as the system of equations. Prior to applying the state estimation algorithm, the existence and uniqueness of the solution of the underlying system of equations is determined through the observability analysis. If a unique solution does not exist, the observability analysis defines observable islands and further defines an additional set of equations (measurements) needed to determine a unique solution. For the first time, we utilise factor graphs and Gaussian belief propagation algorithm to define a novel observability analysis approach. The observable islands and placement of measurements to restore observability are identified by following the evolution of variances across the iterations of the Gaussian belief propagation algorithm over the factor graph. Due to sparsity of the underlying power network, the resulting method has the linear computational complexity (assuming a constant number of iterations) making it particularly suitable for solving large-scale systems. The method can be flexibly matched to distributed computational resources, allowing for determination of observable islands and observability restoration in a distributed fashion. Finally, we discuss performances of the proposed observability analysis using power systems whose size ranges between 1354 and 70000 buses., Comment: 9 pages, 9 figure, version of the journal paper submitted for publication

In this letter, a double polar code (D-Polar) for joint source and channel coding (JSCC) is proposed, in which the source compress is implemented by a polar code, the channel error correction is performed by a systematic polar code. Furthermore, a turbo-like belief propagation (TL-BP) decoder consisted of a channel BP decoder and a source BP decoder is proposed for joint source and channel decoding in the receiver. In this TL-BP decoder, the soft information is exchanged between the channel BP decoder and the source BP decoder so as to improve the efficiency of channel decoding in utilizing the source information residual in the compressed bits. Simulation results show that the performance of the proposed D-Polar JSCC scheme with TL-BP decoder is significantly improved compared with the existing source-channel joint polarization scheme.

In previous papers, decoding schemes which did not use machine learning considered additive white Gaussian noise or memoryless impulse noise. The decoding methods applying deep learning to reduce computational complexity and decoding latency didn’t consider the impulse noise. Here, we apply the Long Short-Term Memory (LSTM) neural network (NN) decoder for Polar codes under the Markov Gaussian memory impulse noise channel, and compare its bit error rate with the existing Polar code decoders like Successive Cancellation (SC), Belief Propagation (BP) and Successive Cancellation List (SCL). In the simulation results, we first find the optimal training SNR value 4.5 dB in the Markov Gaussian memory impulse noise channel for training the proposed LSTM based Polar code decoder. The optimal training SNR value is different from that 1.5 dB in the AWGN channel. The bit error rate of the propose LSTM based Polar code decoder is one third that of the previous non-deep-learning-based decoder SC/BP/SCL in Markov Gaussian memory impulse noise channels. The execution time of the proposed LSTM-based method is 5 ~ 12 times less and thus has much less decoding latency than that of SC/BP/SCL methods because the proposed LSTM-based method has inherent parallel structure and has one shot operation.

In the context of the non-Gaussian delay model, the fully distributed time synchronization approach based on Gaussian belief propagation will lead to the decline of synchronization accuracy. This paper proposes a distributed time synchronization algorithm based on sequential belief propagation (SBP-DTS), which assumes that the network delay is unknown. SBP-DTS first establishes a factor graph (FG) model for the time synchronization problem of wireless sensor networks (WSNs), and then uses sequential belief propagation (BP) algorithms to estimate node clock parameters under an unknown random delay model. At the same time, in order to reduce the amount of data exchanged between nodes during the execution of sequential belief propagation algorithm, the weighted expectation–maximization (EM) algorithm is used to reduce the number of Gaussian mixture components in the message. At last, the performance of SBP-DTS is evaluated under asymmetric Gaussian and exponential delay models.

For polar codes, the statistical breakdown of belief propagation (BP) decoding errors is firstly proposed by Sun et al. The errors are classified into three categories: unconverged errors, false converged errors and oscillation errors, which are corrected by three different post-processing methods. As for the BP List (BPL) decoding, we discover that one type of error can be transformed to another type by different factor graphs in the failed BP decoding. Besides, false converged error is usually easier to be detected and modified. Therefore, we only target false converged error to detect and correct. In this work, we propose a two-level detection rule for false converged errors and its corresponding post-processing algorithm to modify these errors in order to improve the performance of the BPL decoding. Numerical results show that the error-correction performance of the proposed decoder is more than 0.85dB better than that of the permuted BPL (PBPL) decoder with slight extra computation complexity at the frame error rate (FER) of $10^{-5}$ for 5G (1024,512) polar code.

The increasing data traffic rate of wireless communication systems forces the development of new technologies mandatory. Providing high data rate, extremely low latency and improvement on quality of service are the main subjects of next generation 5G wireless communication systems which will be in the people's life in the years of 2020. As the newest and first mathematically proven forward error correction code, polar code is one of the best candidates among error correction methods that can be employed for 5G wireless networks. The aim of this tutorial is to show that belief propagation decoding of polar codes can be a promising forward error correction technique in upcoming 5G frameworks. First, we survey the novel approaches to the belief propagation based decoding of polar codes and continue with the studies about the simplification of these decoders. Moreover, early detection and termination methods and concept of scheduling are going to be presented throughout themanuscript. Finally, polar construction algorithms, error types in belief propagation based decoders and hardware implementations are going to be mentioned. Overall, this tutorial proves that the BP based decoding of polar codes has a great potential to be a part of communication standards.

For the scenarios with high throughput requirements, the belief propagation (BP) decoding is one of the most promising decoding strategies for polar codes. By pruning the redundant variable nodes (VNs) and check nodes (CNs) in the original factor graph, the graph is condensed to a sparse bipartite graph that is similar to the graph for low-density parity-check (LDPC) codes. In this paper, we introduce the bit flipping scheme into the LDPC-like BP (L-BP) decoding and propose two methods to identify the error-prone VNs. By additional decoding attempts, the L-BP flip (L-BPF) decoding improves the error-correction performance with a similar average complexity for high Eb/N0 values. The simulation results show that the L-BPF decoding achieves 0.25 dB gain compared with the L-BP decoding. Finally, a parallel decoder with the proposed L-BPF algorithm for an (256,128) polar code is implemented using 65nm CMOS technology, and it delivers a throughput of 1877.3 Mbps.

The recent development of deep learning methods provides a new approach to optimize the belief propagation (BP) decoding of linear codes. However, the limitation of existing works is that the scale of neural networks increases rapidly with the codelength, thus they can only support short to moderate codelengths. From the point view of practicality, we propose a high-performance neural min-sum (MS) decoding method that makes full use of the lifting structure of protograph low-density parity-check (LDPC) codes. By this means, the size of the parameter array of each layer in the neural decoder only equals the number of edge-types for arbitrary codelengths. In particular, for protograph LDPC codes, the proposed neural MS decoder is constructed in a special way such that identical parameters are shared by a bundle of edges derived from the same edge-type. To reduce the complexity and overcome the vanishing gradient problem in training the proposed neural MS decoder, an iteration-by-iteration (i.e., layer-by-layer in neural networks) greedy training method is proposed. With this, the proposed neural MS decoder tends to be optimized with faster convergence, which is aligned with the early termination mechanism widely used in practice. To further enhance the generalization ability of the proposed neural MS decoder, a codelength/rate compatible training method is proposed, which randomly selects samples from a set of codes lifted from the same base code. As a theoretical performance evaluation tool, a trajectory-based extrinsic information transfer (T-EXIT) chart is developed for various decoders. Both T-EXIT and simulation results show that the optimized MS decoding can provide faster convergence and up to 1dB gain compared with the plain MS decoding and its variants with only slightly increased complexity. In addition, it can even outperform the sum-product algorithm for some short codes., To appear in the IEEE JSAC Series on Machine Learning in Communications and Networks

International audience; This paper describes a practical Slepian-Wolf source coding scheme based on Low Density Parity Check (LDPC) codes. It considers the realistic setup where the parameters of the statistical model between the source and the side information are unknown. A novel Self-Corrected Belief-Propagation (SC-BP) algorithm is proposed in order to make the coding scheme robust to incorrect model parameters by introducing some memory inside the LDPC decoder. A Two Dimensional Density Evolution (2D-DE) analysis is then developed to predict the theoretical performance of the SC-BP decoder. Both the 2D-DE analysis and Monte-Carlo simulations confirm the robustness of the SC-BP decoder. The proposed solution allows for an important complexity reduction and shows a performance very close to existing methods which jointly estimate the model parameters and the source sequence.

A novel cooperative spectrum sensing algorithm intended for robust sensing in the presence of Byzantine attacks was formulated for relay-based cognitive radio networks, with the computation distributed among the relay nodes. The development of this algorithm improves the viability of the application of decentralised CRNs to sensing, which in turn increases the number of use cases for the technology. The proposed algorithm, which performs probabilistic inference using belief propagation, learns from historical sensing results to provide an estimate of the primary user (PU) state. The algorithm was found to reduce the impact of malicious users significantly in comparison to the majority decision rule even in cases where the majority of users were malicious. Furthermore, the algorithm’s PU state estimations converged quickly. Characteristic of a distributed algorithm, the performance of the algorithm was sensitive to the measurement quality of the relay nodes responsible for computation.

In this paper, we propose a design technique for the construction of variable-regular time-invariant spatially-coupled low-density parity-check (SC-LDPC) codes with small constraint length and low error floor. The proposed technique reduces the error floor by imposing simple constraints on the short cycles in the code’s Tanner graph, which in turn, result in the elimination of the most dominant trapping sets of the code. In some cases, we also derive lower bounds on the syndrome former memory for satisfying such constraints. The designed codes are superior to the state-of-the-art in terms of error floor performance and/or decoding complexity and latency.

In this work, we consider the decoding of short sparse graph-based channel codes via reinforcement learning (RL). Specifically, we focus on low-density parity-check (LDPC) codes, which for example have been standardized in the context of 5G cellular communication systems due to their excellent error correcting performance. LDPC codes are typically decoded via belief propagation on the corresponding bipartite (Tanner) graph of the code via flooding, i.e., all check and variable nodes in the Tanner graph are updated at once. We model the node-wise sequential LDPC scheduling scheme as a Markov decision process (MDP), and obtain optimized check node (CN) scheduling policies via RL to improve sequential decoding performance as compared to flooding. In each RL step, an agent decides which CN to schedule next by observing a reward associated with each choice. Repeated scheduling enables the agent to discover the optimized CN scheduling policy which is later incorporated in our RL-based sequential LDPC decoder. In order to reduce RL complexity, we propose a novel graph-induced CN clustering approach to partition the state space of the MDP in such a way that dependencies between clusters are minimized. Compared to standard decoding approaches from the literature, some of our proposed RL schemes not only improve the decoding performance, but also reduce the decoding complexity dramatically once the scheduling policy is learned. By concatenating an outer Hamming code with an inner LDPC code which is decoded based on our learned policy, we demonstrate significant improvements in the decoding performance compared to other LDPC decoding policies.

Linear nested codes, where two or more sub-codes are nested in a global code, have been proposed as candidates for reliable multi-terminal communication. In this paper, we consider nested array-based spatially coupled low-density parity-check (SC-LDPC) codes and propose a line-counting based optimization scheme for minimizing the number of dominant absorbing sets in order to improve its performance in the high signal-to-noise ratio regime. Since the parity-check matrices of different nested sub-codes partially overlap, the optimization of one nested sub-code imposes constraints on the optimization of the other sub-codes. To tackle these constraints, a multi-step optimization process is applied first to one of the nested codes, then sequential optimization of the remaining nested codes is carried out based on the constraints imposed by the previously optimized sub-codes. Results show that the order of optimization has a significant impact on the number of dominant absorbing sets in the Tanner graph of the code, resulting in a tradeoff between the performance of a nested code structure and its optimization sequence: the code which is optimized without constraints has fewer harmful structures than the code which is optimized with constraints. We also show that for certain code parameters, dominant absorbing sets in the Tanner graphs of all nested codes are completely removed using our proposed optimization strategy., Accepted for publication in IEEE Transactions on Communications

Tracking an unknown number of targets based on multipath measurements provided by an over-the-horizon radar (OTHR) network with a statistical ionospheric model is complicated, which requires solving four subproblems: Target detection, target tracking, multipath data association, and ionospheric heights identification. A joint solution is desired since the four subproblems are highly correlated, but suffering from the intractable inference problem of high-dimensional latent variables. In this article, a unified message passing (MP) approach, combining belief propagation (BP) and mean-field (MF) approximation, is developed for simplifying the intractable inference. Based upon the factor graph corresponding to a factorization of the joint probability density function (PDF) of the latent variables and a choice for a separation of this factorization into BP region and MF region, the posterior PDFs of target kinematic state and ionospheric heights, are approximated by MF due to its simple MP update rules for conjugate-exponential models. The posterior PDFs of target visibility state and multipath data association which contains one-to-one frame (hard) constraints (i.e., at each time, a measurement is either originated from one target via a particular path or it is clutter, and each target generates at most one measurement under a particular path) are approximated by BP. Finally, the approximated posterior PDFs are updated iteratively in a closed-loop manner, which is effective for dealing with the coupling issue among latent variables. Meanwhile, the proposed approach has the measurement-level fusion architecture due to the direct processing of the raw multipath measurements from an OTHR network, which is beneficial to improving tracking fusion performance. Its performance is demonstrated on a simulated OTHR network multitarget tracking scenario.

Sensor registration is an important problem that must be considered when attempting to perform any kind of data fusion in multimodal, multisensor target tracking. In this multiple target tracking (MTT) application, any inaccuracies in the registration can lead to false tracks being created, and tracks of true targets being stopped prematurely. This article introduces a method for simultaneously tracking multiple targets in a surveillance region and estimating appropriate sensor registration parameters so that sensor fusion can be performed accurately. The proposed method is based around particle belief propagation (BP), a recent but highly efficient framework for tracking multiple targets. The proposed method also uses a hierarchical model which allows for multiple processes to be linked and interact with one another. We present a comprehensive set of simulations and results using differing, asynchronous sensor setups, and compare with a random finite set (RFS) approach, namely the sequential Monte Carlo (SMC)-probability hypothesis density (PHD) filter. The results show the proposed method is 17% more accurate than the RFS approach on average.

The Belief Propagation (BP) algorithm has the advantages of high-speed decoding and low latency. To improve the block error rate (BLER) performance of the BP-based algorithm, the BP flipping algorithm was proposed. However, the BP flipping algorithm attempts numerous useless flippings for improving the BLER performance. To reduce the number of decoding attempts needed without any loss of BLER performance, in this paper a metric is presented to evaluate the likelihood that the bits would correct the BP flipping decoding. Based on this, a BP-Step-Flipping (BPSF) algorithm is proposed which only traces the unreliable bits in the flip set (FS) to flip and skips over the reliable ones. In addition, a threshold β is applied when the magnitude of the log–likelihood ratio (LLR) is small, and an enhanced BPSF (EBPSF) algorithm is presented to lower the BLER. With the same FS, the proposed algorithm can reduce the average number of iterations efficiently. Numerical results show the average number of iterations for EBPSF-1 decreases by 77.5% when N = 256, compared with the BP bit-flip-1 (BPF-1) algorithm at Eb/N0 = 1.5 dB.

Polar codes have been officially selected as the channel coding in 5G standard. To meet the requirements of enhanced mobile broadband (eMBB), most published polar decoder chips aim to improve throughput rate and error-correction performance. However, to meet with the requirements of another two 5G new radio (NR) application scenarios, ultra-reliable low-latency communications (URLLC), and massive machine-type communications (mMTC), the design features of low latency and energy efficiency are also desirable. In this article, we present a 7.8-13.6 pJ/b ultra-low latency and energy-efficient polar decoder fabricated in 40nm CMOS technology. By adopting the decoding algorithm of recurrent neural network-assisted belief propagation (RNN-BP), the learned scaling parameters can improve the convergence rate by 8 times with reasonable hardware and memory overhead. Then, by taking advantage of BP’s regular structure, we propose a fully-reconfigurable RNN-BP decoder architecture to support multiple code lengths with negligible hardware complexity. It contributes to 2- $8\times $ improved hardware utilization rate while providing a flexible adjustment between throughput and error-correction performance. At the architectural level, two optimization techniques for the design of the processing element (PE) are proposed to jointly reduce the chip’s area and power by 73% and 67%, respectively. From the measurement results, our reconfigurable RNN-BP polar decoder chip has $2.3\times $ , $2.3\times $ , and $10.0\times $ enhancement over prior designs in terms of latency, throughput rate, and energy efficiency. Consequently, our reconfigurable design has great potential to meet various 5G NR applications.

We consider the problem of joint channel estimation and data decoding in uplink massive multiple input multiple output systems with low resolution analog-to-digital converters (ADCs) at the base station. The nonlinearities introduced by the ADCs make the problem challenging: in particular, the existing linear detectors perform poorly. Also, the channel coding used in commercial wireless systems necessitates soft symbol detection to obtain satisfactory performance. In this paper, we present a low-complexity variational Bayesian (VB) inference procedure to jointly solve the (possibly correlated) channel estimation and soft symbol decoding problem. We present the approach in progressively more complex scenarios, including the case where even the channel statistics are not available at the receiver. Finally, we combine our proposed VB procedure with a belief propagation (BP) based channel decoder, which further enhances the performance without any additional complexity. We numerically evaluate the bit error rate (BER) and the normalized mean squared error (NMSE) in the channel estimates obtained by our algorithm as a function of various system parameters, and benchmark the performance against genie-aided and state-of-the-art receivers. The results show that VB procedure is a promising technique for the design of low-complexity advanced receivers in low resolution ADC based systems.

Non-orthogonal multiple access (NOMA) on shared resources has been identified as a promising technology in 5G to improve resource efficiency and support massive access in all kinds of transmission modes. Power domain and code domain NOMA have been extensively studied and evaluated in both literatures and 3GPP standardization, especially for the uplink where large number of users would like to send their messages to the base station. Though different in the transmitter side design, power domain NOMA and code domain NOMA share the same need of the advanced multi-user detection (MUD) design at the receiver side. Various multi-user detection algorithms have been proposed, balancing performance and complexity in different ways, which is important for the implementation of NOMA in practical networks. In this paper, we introduce a unified variational inference (VI) perspective on various universal NOMA MUD algorithms such as belief propagation (BP), expectation propagation (EP), vector EP (VEP), approximate message passing (AMP) and vector AMP (VAMP), demonstrating how they could be derived from and adapted to each other within the VI framework. Moreover, we unveil and prove that conventional elementary signal estimator (ESE) and linear minimum mean square error (LMMSE) receivers are special cases of EP and VEP, respectively, thus bridging the gap between classic linear receivers and message passing based nonlinear receivers. Such a unified perspective would not only help the design and adaptation of NOMA receivers, but also open a door for the systematic design of joint active user detection and multi-user decoding for sporadic grant-free transmission.

Belief propagation (BP) decoding has natural advantages in throughput for polar codes to meet high-speed and low-latency requirements. The soft outputs of BP decoding can be utilized further for joint detection and decoding in the baseband communication system. However, its error-correction performance is not comparable with the successive cancellation list (SCL) decoding. Belief propagation flip (BPF) decoding is recently proposed to improve the error-correction performance of BP decoding and indicates the potential to compete with SCL decoding. In this paper, we propose an advanced BPF (A-BPF) scheme that reduces the decoding latency with the help of one critical bit and improves the error-correction performance by the proposed joint detection criterion. To improve area efficiency in the hardware level, an optimized sorting network is proposed and applied for the A-BPF decoder. The decoder is implemented on 65 nm CMOS technology for length-1024 and rate-1/2 polar codes, and the results show that the proposed decoder can achieve a close frame error rate performance to the SCL decoder with four lists and deliver a throughput of 5.17 Gb/s at $E_{b}/N_{0}=4.0$ dB.

Worries about the increasing number of Sybils in online social networks (OSNs) are amplified by a range of security issues; thus, Sybil detection has become an urgent real-world problem. Lightweight and limited data-friendly, LBP (Loopy Belief Propagation)-based Sybil-detection methods on the social graph are extensively adopted. However, existing LBP-based methods that do not utilize node attributes often assume a global or predefined homophily strength of edges in the social graph, while different user’s discrimination and preferences may vary, resulting in local homogeneity differences. Another issue is that the existing message-passing paradigm uses the same edge potential when propagating belief to both sides of a directed edge, which does not agree with the trust interaction in one-way social relationships. To bridge these gaps, we present SybilHP, a Sybil-detection method optimized for directed social networks with adaptive homophily prediction. Specifically, we incorporate an iteratively updated edge homophily estimation into the belief propagation to better adapt to the personal preferences of real-world social network users. Moreover, we endow message passing on edges with directionality by a direction-sensitive potential function design. As a result, SybilHP can better capture the local homophily and direction pattern in real-world social networks. Experiments show that SybilHP works with high detection accuracy on synthesized and real-world social graphs. Compared with various state-of-the-art graph-based methods on a large-scale Twitter dataset, SybilHP substantially outperforms existing methods.

This paper proposes a centralized MTT method based on a state-of-the-art multi-sensor labeled multi-Bernoulli (LMB) filter in underwater multi-static networks with autonomous underwater vehicles (AUVs). The LMB filter can accurately extract the number of targets and trajectories from measurements affected by noise, missed detections, false alarms and port–starboard ambiguity. However, its complexity increases as the number of sensors increases. In addition, due to the time-varying underwater environment, AUV detection probabilities are time-varying, and their mismatches often lead to poor MTT performance. Consequently, we detail a robust multi-sensor LMB filter that estimates detection probabilities and multi-target states simultaneously in real time. Moreover, we derive an effective approximate form of the multi-sensor LMB filter using Kullback–Leibler divergence and develop an efficient belief propagation (BP) implementation of the multi-sensor LMB filter. Our method scales linearly with the number of AUVs, providing good scalability and low computational complexity. The proposed method demonstrates superior performance in underwater multi-AUV network MTT simulations.

Thanks to its superior features of fast read/write speed and low power consumption, spin-torque transfer magnetic random access memory (STT-MRAM) has become a promising non-volatile memory (NVM) technology that is suitable for many applications. However, the reliability of STT-MRAM is seriously affected by the variation of the memory fabrication process and the working temperature, and the later will lead to an unknown offset of the channel. Hence, there is a pressing need to develop more effective error correction coding techniques to tackle these imperfections and improve the reliability of STT-MRAM. In this work, we propose, for the first time, the application of deep-learning (DL)-based algorithms and techniques to improve the decoding performance of linear block codes with short codeword lengths for STT-MRAM. We formulate the belief propagation (BP) decoding of linear block code as a neural network (NN) and propose a novel neural normalized-offset reliability-based min-sum (RB-MS) (NNORB-MS) decoding algorithm. We successfully apply our proposed decoding algorithm to the STT-MRAM channel through channel symmetrization to overcome the channel asymmetry. We also propose an NN-based soft information generation method (SIGM) to take into account the unknown offset of the channel. Simulation results demonstrate that our proposed NNORB-MS decoding algorithm can achieve significant performance gain over both the hard-decision decoding (HDD) and the regular RB-MS decoding algorithm, for cases without and with the unknown channel offset. Moreover, the decoder structure and time complexity of the NNORB-MS algorithm remain similar to those of the regular RB-MS algorithm.

Known for their capacity-achieving abilities and low complexity for both encoding and decoding, polar codes have been selected as the control channel coding scheme for 5G communications. To satisfy the needs of high throughput and low latency, belief propagation (BP) is chosen as the decoding algorithm. However, it suffers from worse error performance than that of cyclic redundancy check (CRC)-aided successive cancellation list (CA-SCL). Recently, convolutional neural network-aided bit-flipping (CNN-BF) is applied to BP decoding, which can accurately identify the erroneous bits to achieve a better error rate and lower decoding latency than prior critical-set bit-flipping (CS-BF) mechanism. However, successive BF, having better error correction capability, has not been explored in CNN-BF since the more complicated flipping strategy is out of the scope of supervised learning. In this work, by using imitation learning, a convolutional neural network-aided tree-based multiple-bits BF (CNN-Tree-MBF) mechanism is proposed to explore the benefits of multiple-bits BF. With the CRC information as additional input data, the proposed CNN-BF model can further reduce 5 flipping attempts. Besides, a tree-based flipping strategy is proposed to avoid useless flipping attempts caused by wrongly flipped bits. From the simulation results, our approach can outperform CS-BF and reduce flipping attempts by 89% when code length is 64, code rate is 0.5 and SNR is 1 dB. It also achieves a comparable block error rate (BLER) as CA-SCL.

In this article we propose a technique for polar codes (PC) construction for any code length. By default, PC construction is limited to code length proportional to the power of two. To construction the code length arbitrary, puncturing, shortening and extension techniques must be applied. However, performance is degraded with the use of these techniques. Other ways to design polar codes with arbitrary code length but which have encoding and decoding with higher complexity such as multi-kernel, concatenated codes and specific constructions for belief propagation (BP) or successive cancellation list (SCL) decoding. The polarization theory is generalized for non-uniform channels (NUC) and with this approach we can construction rate-compatible PC and variable code length. We developed an implementation algorithm based on the of PC construction by Gaussian approximation (NUPGA). In a scenario where the transmission is over an additive white Gaussian noise (AWGN) channel and under successive cancellation (SC) decoding, the PC construction of arbitrary code length can be implemented with NUPGA. With NUPGA we re-polarize the projected synthetic channels by choosing more efficiently the positions of the information bits. In addition, we present a generalization of the Gaussian approximation (GA) for the polarization and re-polarization processes and an extension technique for PC. The PC construction based on NUPGA present better performance than the existing techniques as shown in the simulations of this work.

In this paper, we extend the bilinear generalized approximate message passing (BiG-AMP) approach, originally proposed for high-dimensional generalized bilinear regression, to the multi-layer case for the handling of cascaded problem such as matrix-factorization problem arising in relay communication among others. Assuming statistically independent matrix entries with known priors, the new algorithm called ML-BiGAMP could approximate the general sum-product loopy belief propagation (LBP) in the high-dimensional limit enjoying a substantial reduction in computational complexity. We demonstrate that, in large system limit, the asymptotic MSE performance of ML-BiGAMP could be fully characterized via a set of simple one-dimensional equations termed state evolution (SE). We establish that the asymptotic MSE predicted by ML-BiGAMP' SE matches perfectly the exact MMSE predicted by the replica method, which is well known to be Bayes-optimal but infeasible in practice. This consistency indicates that the ML-BiGAMP may still retain the same Bayes-optimal performance as the MMSE estimator in high-dimensional applications, although ML-BiGAMP's computational burden is far lower. As an illustrative example of the general ML-BiGAMP, we provide a detector design that could estimate the channel fading and the data symbols jointly with high precision for the two-hop amplify-and-forward relay communication systems., Comment: 61 pages, 16 figures. This paper has been accepted by IEEE Transaction on Signal Processing

Recently, Graph Convolutional Network(GCN) methods for skeleton-based action recognition have achieved great success due to their ability to preserve structural information of the skeleton. However, these methods abandon the structural information in the classification stage by employing traditional fully-connected layers and softmax classifier, leading to sub-optimal performance. In this work, a novel Graph Convolutional Networks-Hidden conditional Random Field (GCN-HCRF) model is proposed to solve this problem. The proposed method combines GCN with HCRF to retain the human skeleton structure information even during the classification stage. Our model is trained end-to-end by utilizing the message passing from the belief propagation algorithm on the human structure graph. To further capture spatial and temporal information, we propose a multi-stream framework which takes the relative coordinate of the joints and bone direction as two static feature streams, and the temporal displacements between two consecutive frames as the dynamic feature stream. Experimental results on three challenging benchmarks (NTU RGB+D, N-UCLA, SYSU) show the superior performance of the proposed model over state-of-the-art models.