Search

Joint probabilistic data association (JPDA) filter methods and multiple hypothesis tracking (MHT) methods are widely used for multitarget tracking (MTT). However, they are known to exhibit undesirable behavior in tracking scenarios with targets in close proximity: JPDA filter methods suffer from the track coalescence effect, i.e., the estimated tracks of targets in close proximity tend to merge and can become indistinguishable, while MHT methods suffer from an opposite effect known as track repulsion, i.e., the estimated tracks of targets in close proximity tend to repel each other in the sense that their separation is larger than the actual distance between the targets. In this paper, we review the JPDA filter and MHT methods and discuss the track coalescence and track repulsion effects. We also consider a more recent methodology for MTT that is based on the belief propagation (BP) algorithm. We argue that BP-based MTT does not exhibit track repulsion because it is not based on maximum a posteriori estimation, and that it exhibits significantly reduced track coalescence because certain properties of the BP messages related to data association encourage separation of target state estimates. Our theoretical arguments are confirmed by numerical results for four representative simulation scenarios.

Belief propagation is one of low latency decoding algorithms for polar codes but it requires relatively high decoding complexity due to its inherent iterative decoding nature. To remedy the problem, early stopping belief propagation algorithm was proposed. Unfortunately, it requires additional complexity to test stopping criterion at each end of decoder iterations. In this paper, we propose a low complexity early stopping belief propagation decoder for polar codes which requires lower complexities not only for stopping criterion test but also for decoding by reducing the number of message updates within the decoder without any performance loss.

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.

In this paper, an empirical study shows that positive tests containing multiple defectives are unlikely to provide effective messages in belief propagation (BP) for non-adaptive group testing. Thus, an objective function is proposed to measure the effectiveness of messages over edges, especially in the low-noise region. The maximization of the objective function allows us to optimize the pool size for BP. Simulation results show that the error performance of BP in the low-noise region is significantly improved by our pool size optimization.

The use of estimation techniques on stochastic models to solve control problems is an emerging paradigm that falls under the rubric of Active Inference (AI) and Control as Inference (CAI). In this work, we use probability propagation on factor graphs to show that various algorithms proposed in the literature can be seen as specific composition rules in a factor graph. We show how this unified approach, presented both in probability space and in log of the probability space, provides a very general framework that includes the Sum-product, the Max-product, Dynamic programming and mixed Reward/Entropy criteria-based algorithms. The framework also expands algorithmic design options that lead to new smoother or sharper policy distributions. We propose original recursions such as: a generalized Sum/Max-product algorithm, a Smooth Dynamic programming algorithm and a modified versions of the Reward/Entropy algorithm. The discussion is carried over with reference to a path planning problem where the recursions that arise from various cost functions, although they may appear similar in scope, bear noticeable differences. We provide a comprehensive table of composition rules and a comparison through simulations, first on a synthetic small grid with a single goal with obstacles, and then on a grid extrapolated from a real-world scene with multiple goals and a semantic map.

The growing number of Internet of Thing (IoT) and Ultra-Reliable Low Latency Communications (URLCC) use cases in next generation communication networks calls for the development of efficient Forward Error Correction (FEC) mechanisms. These use cases usually imply using short to mid-sized information blocks and requires low-complexity and/or fast decoding procedures. This paper investigates the joint learning of short to mid block-length coding schemes and associated Belief-Propagation (BP) like decoders using Machine Learning (ML) techniques. An interpretable auto-encoder (AE) architecture is proposed, ensuring scalability to block sizes currently challenging for ML-based linear block code design approaches. By optimizing a coding scheme w.r.t. the targeted decoder, the proposed system offers a good complexity/performance trade-off compared to various codes from literature with length up to 128 bits. [ABSTRACT FROM AUTHOR]

This article introduces a novel communication paradigm for the unsourced, uncoordinated Gaussian multiple access problem. The major components of the envisioned framework are as follows. The encoded bits of every message are partitioned into two groups. The first portion is transmitted using a compressive sensing scheme, whereas the second set of bits is conveyed using a multi-user coding scheme. The compressive sensing portion is key in sidestepping some of the challenges posed by the unsourced aspect of the problem. The information afforded by the compressive sensing is employed to create a sparse random multi-access graph conducive to joint decoding. This construction leverages the lessons learned from traditional IDMA into creating low-complexity schemes for the unsourced setting, while also accounting for inherent randomness. Under joint message-passing decoding, the proposed scheme offers good performance at a low computational complexity. Findings are supported by numerical simulations, and results are compared to existing alternatives. [ABSTRACT FROM AUTHOR]

Achieving reliable communications with low complexity is challenging for underwater acoustic communications with moving transceivers, where the time-varying channels need to be estimated and tracked accurately and data detection needs to be performed with low complexity. In this article, with the use of a superimposed training (ST) scheme, we address this challenge by developing a low-complexity channel estimation and tracking algorithm, which is then integrated with low-complexity data detection in the frequency domain. ST is used to acquire improved channel-tracking capability. Based on belief propagation, we design a message-passing-based low-complexity bidirectional channel estimation (LCE-MP) algorithm, where all computational intensive parts are handled by the fast Fourier transform (FFT) algorithm, thereby achieving very efficient implementation with logarithmic complexity. Specifically, a message-passing-based fast information collection algorithm is presented to acquire “local” channel estimates, followed by the fusion of local channel estimates to achieve a “global” estimate of the channel. It is shown that the computational complexity per channel tap is only in a logarithmic level for the channel estimation and tracking. Moreover, the ST-scheme-based LCE-MP algorithm is combined with FFT-based data detection and decoding, which are performed in an iterative manner. The overall complexity of channel estimation and data detection is in a logarithmic level, and the system delivers excellent performance thanks to the joint processing. Field experiments were carried out in Jiaozhou Bay in 2019, and the experimental results verify the effectiveness of the proposed technique. [ABSTRACT FROM AUTHOR]

This paper proposes a belief propagation (BP)-based algorithm for sequential detection and estimation of multipath component (MPC) parameters based on radio signals. Under dynamic channel conditions with moving transmitter/receiver, the number of MPCs, the MPC dispersion parameters, and the number of false alarm contributions are unknown and time-varying. We develop a Bayesian model for sequential detection and estimation of MPC dispersion parameters, and represent it by a factor graph enabling the use of BP for efficient computation of the marginal posterior distributions. At each time step, a snapshot-based parametric channel estimator provides parameter estimates of a set of MPCs which are used as noisy measurements by the proposed BP-based algorithm. It performs joint probabilistic data association, and estimation of the time-varying MPC parameters and the mean number of false alarm measurements, by means of the sum-product algorithm rules. The algorithm also exploits amplitude information enabling the reliable detection of “weak” MPCs with very low component signal-to-noise ratios (SNRs). The performance of the proposed algorithm compares well to state-of-the-art algorithms for high SNR MPCs, but it significantly outperforms them for medium or low SNR MPCs. Results using real radio measurements demonstrate the excellent performance of the proposed algorithm in realistic and challenging scenarios. [ABSTRACT FROM AUTHOR]

The striking growth of powerful computing resources allows time-efficient solution of computationally demanding problems. In particular, advances in high-performance computing have made stochastic approaches to real-world applications more practical. The belief propagation (BP) algorithm is a probabilistic method typically used in information theory and artificial intelligence. This article exploits the probabilistic message passing attribute of BP for solving stochastic linear systems that naturally arise from finite element formulation of stochastic partial differential equations (PDEs), establishing an explicit connection between the two fields for the first time. The accuracy of the algorithm is validated by comparison to the well-known Monte Carlo method. [ABSTRACT FROM AUTHOR]

This article investigates the performance of intelligent reflective surfaces (IRS)-aided physical layer network coding (PNC) in two-way relaying channels (TWRC). Specifically, IRS is used to eliminate carrier phase offset (CPO) at the relay node. To this end, the IRS reflectors’ phase shifts are optimized to align the received signals from two source nodes at the relay. This facilitates using a simple mapping function at the relay to map the superimposed signal to a network-coded signal. Two scenarios are considered, the first of which assumes that each source node is served by a separate IRS panel, while the second scenario considers the more challenging case where only one IRS panel is available for the two source nodes. In the latter case, the IRS panel is seen by both source nodes and its phase shifts are optimized to mitigate the CPO problem while maximizing the received signal amplitude at the relay. This optimization problem is formulated and solved over the complex circle manifold. Finally, we extend the IRS-assisted PNC system to include channel coding and higher modulation orders, for which a repeat accumulate (RA) channel-coded IRS-aided PNC scheme is proposed for general quadrature amplitude modulation (QAM) signals. A belief propagation (BP) based algorithm is designed to decode the network-coded sequences over a q-Ring using modular arithmetic. Our simulation results validate the theoretical error expressions derived for the two-IRS scenario as well as the efficacy of the proposed manifold optimization approach for the one-IRS scenario. The results also confirm the efficacy of the designed channel-coded IRS-aided PNC using high QAM modulation orders. [ABSTRACT FROM AUTHOR]

The probabilistic forecasting method described in this study is devised to leverage spatial and temporal dependency of urban traffic networks, in order to provide predictions accurate at short term and meaningful for a horizon of up to several hours. By design, it can deal with missing data, both for training and running the model. It is able to forecast the state of the entire network in one pass, with an execution time that scales linearly with the size of the network. The method consists in learning a sparse Gaussian copula of traffic variables, compatible with the Gaussian belief propagation algorithm. The model is trained automatically from an historical dataset through an iterative proportional scaling procedure, that is well suited to compatibility constraints induced by Gaussian belief propagation. Results of tests performed on two urban datasets show a very good ability to predict flow variables and reasonably good performances on speed variables. Some understanding of the observed performances is given by a careful analysis of the model, making it to some degree possible to disentangle modeling bias from the intrinsic noise of the traffic phenomena and its measurement process. [ABSTRACT FROM AUTHOR]

This letter incorporates the adaptive kernel Kalman filter (AKKF) into the belief propagation (BP) algorithm for Multi-target tracking (MTT) in single-sensor systems. The algorithm is capable of tracking an unknown and time-varying number of targets, in the presence of false alarms, clutter and measurement-to-target association uncertainty. Experiment results reveal that the proposed method has a favourable tracking performance using the generalized optimal sub-patten assignment (GOSAP) metrics at substantially less computation cost than the particle filter (PF) based Multi-target tracking (MTT) BP algorithm. [ABSTRACT FROM AUTHOR]

As an algorithmic framework, message passing is extremely powerful and has wide applications in the context of different disciplines including communications, coding theory, statistics, signal processing, artificial intelligence and combinatorial optimization. In this paper, we investigate the performance of a message-passing algorithm called min-sum belief propagation (BP) for the vertex-disjoint shortest $k$ -path problem ($k$ -VDSP) on weighted directed graphs, and derive the iterative message-passing update rules. As the main result of this paper, we prove that for a weighted directed graph $G$ of order $n$ , BP algorithm converges to the unique optimal solution of $k$ -VDSP on $G$ within $O(n^{2}w_{max})$ iterations, provided that the weight $w_{e}$ is nonnegative integral for each arc $e\in E(G)$ , where $w_{max}=\max \{w_{e}: e\in E(G)\}$. To the best of our knowledge, this is the first instance where BP algorithm is proved correct for NP-hard problems. Additionally, we establish the extensions of $k$ -VDSP to the case of multiple sources or sinks. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of learning a tree graph structure that represents the statistical data dependency among nodes for a set of data samples generated by nodes, which provides the basic structure to perform a probabilistic inference task. Inference in the data graph includes marginal inference and maximum a posteriori (MAP) estimation, and belief propagation (BP) is a commonly used algorithm to compute the marginal distribution of nodes via message-passing, incurring non-negligible amount of communication cost. We inevitably have the trade-off between the inference accuracy and the message-passing cost because the learned structure of data dependency and physical connectivity graph are often highly different. In this paper, we formalize this trade-off in an optimization problem which outputs the data dependency graph that jointly considers learning accuracy and message-passing costs. We focus on two popular implementations of BP, ASYNC-BP and SYNC-BP, which have different message-passing mechanisms and cost structures. In ASYNC-BP, we propose a polynomial-time learning algorithm that is optimal, motivated by finding a maximum weight spanning tree of a complete graph. In SYNC-BP, we prove the NP-hardness of the problem and propose a greedy heuristic. For both BP implementations, we quantify how the error probability that the learned cost-efficient data graph differs from the ideal one decays as the number of data samples grows, using the large deviation principle, which provides a guideline on how many samples are necessary to obtain a certain trade-off. We validate our theoretical findings through extensive simulations, which confirms that it has a good match. [ABSTRACT FROM AUTHOR]

In this paper, we investigate a joint device activity detection (DAD), channel estimation (CE), and data decoding (DD) algorithm for multiple-input multiple-output (MIMO) massive unsourced random access (URA). Different from the state-of-the-art slotted transmission scheme, the data in the proposed framework is split into only two parts. A portion of the data is coded by compressed sensing (CS) and the rest is low-density-parity-check (LDPC) coded. In addition to being part of the data, information bits in the CS phase also undertake the task of interleaving pattern design and CE. The principle of interleave-division multiple access (IDMA) is exploited to reduce the interference among devices in the LDPC phase. Based on the belief propagation (BP) algorithm, a low-complexity iterative message passing (MP) algorithm is utilized to decode the data embedded in these two phases separately. Moreover, combined with successive interference cancellation (SIC), the proposed joint DAD-CE-DD algorithm is performed to further improve performance by utilizing the belief of each other. Additionally, based on the energy detection (ED) and sliding window protocol (SWP), we develop a collision resolution protocol to handle the codeword collision, a common issue in the URA system. In addition to the complexity reduction, the proposed algorithm exhibits a substantial performance enhancement compared to the state-of-the-art in terms of efficiency and accuracy. [ABSTRACT FROM AUTHOR]

Despite the great promises that the resistive random access memory (ReRAM) has shown as the next generation of non-volatile memory technology, its crossbar array structure leads to a severe sneak path interference to the signal read back from the memory cell. In this paper, we first propose a novel belief propagation (BP) based detector for the sneak path interference in ReRAM. Based on the conditions for a sneak path to occur and the dependence of the states of the memory cells that are involved in the sneak path, a Tanner graph for the ReRAM channel is constructed, inside which specific messages are updated iteratively to get a better estimation of the sneak path affected cells. We further combine the graph of the designed BP detector with that of the BP decoder of the polar codes to form a joint detector and decoder. Tailored for the joint detector and decoder over the ReRAM channel, effective polar codes are constructed using the genetic algorithm. Simulation results show that the BP detector can effectively detect the cells affected by the sneak path, and the proposed polar codes and the joint detector and decoder can significantly improve the error rate performance of ReRAM. [ABSTRACT FROM AUTHOR]

In order to reduce the decoding latency, a new early stopping criterion is proposed for belief propagation (BP) decoding. A kind of special processing elements (PEs) of BP decoder called frozen and information PE (FIPE) is selected to predict whether decoding is successful or not. Statistics indicate that FIPE can be considered reliable when the frozen bit is decoded successfully. The proposed criterion is based on the fact that the number of reliable FIPE increase along with iterations and the variation trend is approximate to the ratio of correct information bits. In the term of hardware complexity, the proposed method has a linear correlation with the number of FIPE. This criterion consumes only ‘xor’ and ‘or’ gates to check stopping condition. Simulation results show that the proposed criterion achieves lower latency than Worst Information Bits (WIB) and Frozen Bit Error Rate (FBER) without BLER degradation compared with fixed and G-matrix. Compared with WIB, FBER, Best Frozen Bits (BFB) criterion, the proposed criterion has the lowest hardware complexity. [ABSTRACT FROM AUTHOR]

A novel fault-tolerant computation technique based on array Belief Propagation (BP)-decodable XOR (BP-XOR) codes is proposed for distributed matrix-matrix multiplication. The proposed scheme is shown to be configurable and suited for modern hierarchical compute architectures such as Graphical Processing Units (GPUs) equipped with multiple nodes, whereby each has many small independent processing units with increased core-to-core communications. The proposed scheme is shown to outperform a few of the well–known earlier strategies in terms of total end-to-end execution time while in presence of slow nodes, called stragglers. This performance advantage is due to the careful design of array codes which distributes the encoding operation over the cluster (slave) nodes at the expense of increased master-slave communication. An interesting trade-off between end-to-end latency and total communication cost is precisely described. In addition, to be able to address an identified problem of scaling stragglers, an asymptotic version of array BP-XOR codes based on projection geometry is proposed at the expense of some computation overhead. A thorough latency analysis is conducted for all schemes to demonstrate that the proposed scheme achieves order-optimal computation in both the sublinear as well as the linear regimes in the size of the computed product from an end-to-end delay perspective. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The low-density parity-check (LDPC) code is chosen to be a channel coding scheme for ultra-reliable and low-latency communications (URLLC) in 5G. However, short LDPC compromises the belief propagation (BP) decoder because of the stopping set (SS) in the decoding graph. We propose to perform different node operations according to the SS. A dynamic SS selection according to the received sequence is further applied. In the length 308 5G LDPC, our decoders outperform prior work, improving BP and collaborative BP at block error probability (BLER) of $3 \times 10^{-5}$ by around 0.176 and 0.092 dB respectively, with almost the same number of iterations. [ABSTRACT FROM AUTHOR]

Reasonable resource management scheme is the premise to ensure system reliability and practicability of vehicle-to-vehicle (V2V) communications network. In this paper, spectrum resource allocation and power control scheme is studied. Firstly, the problem of resource block (RB) sharing is considered. Assuming that each V2V link occupies at most one resource block while multiple links can share the same RB. In this work, a factor graph model is proposed corresponding to the RB allocation problem through function mapping. Therefore, the RB allocation problem is equivalent to studying the message update and belief inference problem on the factor graph model. We propose a Belief Propagation based on Real-time Update of Messages (BPRUM) algorithm, in which the message of each node is calculated based on the new messages of other nodes rather than the messages calculated in the last iteration. Secondly, after the RB allocation is completed, a power control scheme under the maximum power limit is proposed by utilizing the Lagrange dual decomposition. And the total throughput of the system is maximized by using the proposed power control scheme. Simulation results show that the resource allocation and power control scheme can achieve a significant increment in spectrum utilization and throughput of the V2V communications network.

As industrial plants increase the number of wirelessly connected sensors for fault detection, a key problem is to identify and obtain data from the sensors. Due to the large number of sensors, random access protocols exploiting non-orthogonal multiple access (NOMA) are a natural approach. In this paper, we develop new algorithms based on approximate message passing for sensor identification and channel estimation accounting for correlation in the activity probability of each sensor and observations of physical variables (e.g., temperature) by the access point. These algorithms form the basis for data decoding, while also identifying faulty machines and estimating local values of the temperature, which can lead to a reduction in the amount of data required to be transmitted. Numerical results show that for an expected activity probability of 0.35, our algorithms improve the normalized mean-square error of the channel estimate by up to 5dB and reduce the rate of sensor identification errors by a factor of four.

An efficient channel assignment plays an important role in mitigating co-channel interference in ultra-dense wireless networks. A simple solution is to separate interfering network nodes into orthogonal channels to reduce the interference among them. However, determining the optimal channel assignment is considered to be a non-linear problem, which may also be associated with practical implementation issues such as high computational complexity and control signaling issues. In an effort to cope with these challenging issues, we propose a distributed channel assignment algorithm that efficiently finds the optimal channel configuration by utilizing the concept of belief propagation. Based on a message-passing framework, the proposed distributed channel assignment algorithm maximizes the overall sum rate of the ultra-dense network with a low computational load for each network node. In addition, we design a network protocol and frame format to implement the proposed message-passing framework to real-world wireless networks. The main advantage of the proposed approach is that network nodes autonomously determine the optimal channel assignment and rapidly adapt to dynamic changes of the network. Simulation results confirm that the proposed distributed channel assignment algorithm outperforms conventional algorithms in terms of various network performance aspects, such as the sum rate, scalability, latency, and user mobility.

Distinguishing obstacles from ground is an essential step for common perception tasks such as object detection-and-tracking or occupancy grid maps. Typical approaches rely on plane fitting or local geometric features, but their performance is reduced in situations with sloped terrain or sparse data. Some works address these issues using Markov Random Fields and Belief Propagation, but these rely on local geometric features uniquely. This article presents a strategy for ground segmentation in LiDAR point clouds composed by two main steps: (i) First, an initial classification is performed dividing the points in small groups and analyzing geometric features between them. (ii) Then, this initial classification is used to model the surrounding ground height as a Markov Random Field, which is solved using the Loopy Belief Propagation algorithm. Points are finally classified comparing their height with the estimated ground height map. On one hand, using an initial estimation to model the Markov Random Field provides a better description of the scene than local geometric features commonly used alone. On the other hand, using a graph-based approach with message passing achieves better results than simpler filtering or enhancement techniques, since data propagation compensates sparse distributions of LiDAR point clouds. Experiments are conducted with two different sources of information: nuScenes’s public dataset and an autonomous vehicle prototype. The estimation results are analyzed with respect to other methods, showing a good performance in a variety of situations.

Probabilistic graphical models (PGMs) are powerful tools for solving systems of complex relationships over a variety of probability distributions. However, while tree-structured PGMs always result in efficient and exact solutions, inference on graph (or loopy) structured PGMs is not guaranteed to discover the optimal solutions. It is in principle possible to convert loopy PGMs to an equivalent tree structure, but this is usually impractical for interesting problems due to exponential blow-up. To address this, we developed the “purge-and-merge” algorithm. This algorithm iteratively nudges a malleable graph structure towards a tree structure by selectively merging factors. The merging process is designed to avoid exponential blow-up by way of sparse structures from which redundancy is purged as the algorithm progresses. We set up tasks to test the algorithm on constraint-satisfaction puzzles such as Sudoku, Fill-a-pix, and Kakuro, and it outperformed other PGM-based approaches reported in the literature. While the tasks we set focussed on the binary logic of CSP, we believe the purge-and-merge algorithm could be extended to general PGM inference.

Serial decoding algorithms of low-density parity-check (LDPC) code converge efficiently with low errors. Previously, a serial decoding algorithm, named a shuffled belief-propagation (SBP), was applied in turbo equalization of bit-patterned magnetic recording (BPMR) systems. With the SBP algorithm, an LDPC decoder converged twice as fast as one using conventional BP algorithms. We further improved the convergence speed of SBP by updating the messages in an adaptive order, which played a flexible role throughout decoding. We proposed two adaptive-serial algorithms for LDPC codes in turbo equalization. One updated the messages using the extrinsic loglikelihood ratio (LLR) and the result of the parity-check equation checking. The second contained an additional rule that tracked the LLR sign changes in each iteration. Both algorithms converged faster and with lower bit error rates (BERs) than the SBP and previous adaptive-serial algorithms in a BPMR system with media noise. [ABSTRACT FROM AUTHOR]

In large multi-user multi-input multi-output systems, the computational cost and circuit scale of base stations (BSs) are effectively reduced using two-stage signal processing consisting of a slow varying outer beamformer (OBF) based on long-term channel statistics and group-specific multi-user detection for instantaneous channel variations. However, the dimensionality reduction of the group-specific beam-domain channel based on the OBF causes significant performance degradation in the subsequent spatial-filtering detection. To compensate for this drawback, this paper introduces a novel layered belief propagation (BP) detector with a concatenated structure of beam- and antenna-domain BP layers for post-stage OBF processing. The proposed detector is designed for improving the convergence of iterative detection by suppressing intra- and inter-group interference in stages. The layered structure provides the advantages of both beam and antenna domains while maintaining low signal-processing complexity. Numerical results show the validity of our proposed method in terms of the bit error rate performance in both the uncoded and coded cases and the computational complexity. [ABSTRACT FROM AUTHOR]

We study the stability of low-density parity-check codes under blockwise or bitwise maximum a posteriori decoding, where transmission takes place over a binary-input memoryless output-symmetric channel. Our study stems from the consideration of constructing universal capacity-achieving codes under low-complexity decoding algorithms, where universality refers to the fact that we are considering a family of channels with equal capacity. Consider, e.g., the right-regular sequence by Shokrollahi and the heavy-tail Poisson sequence by Luby et al. Both sequences are provably capacity-achieving under belief propagation decoding when transmission takes place over the binary erasure channel. In this paper we show that many existing capacity-achieving sequences of low-density parity-check codes are not universal under belief propagation decoding. We reveal that the key to showing this non-universality result is determined by the stability of the underlying codes. More concretely, for an ordered and complete channel family and a sequence of low-density parity-check code ensembles, we determine a stability threshold associated with them, which gives rise to a sufficient condition under which the sequence is not universal under belief propagation decoding. Moreover, we show that the same stability threshold applies to blockwise or bitwise maximum a posteriori decoding as well. We demonstrate how the stability threshold can determine an upper bound on the corresponding blockwise or bitwise maximum a posteriori threshold, revealing the operational significance of the stability threshold. [ABSTRACT FROM AUTHOR]

Wireless distributed cache system (WDCS) is a promising technique to offload traffic and improve energy efficiency in content-centric networks. In this paper, the content sharing problem is considered by minimizing the average energy consumption for content caching and delivering in device-to-device (D2D) enabled cellular networks. The problem is formulated as a joint optimization problem of multiple interactive variables, which is NP-hard. In order to solve this problem, we first decompose the original problem into three subproblems, which are content helper (CH) selection, content caching, and content delivering. Specifically, in CH selection, we propose a PageRank based distributed algorithm to estimate the centrality of mobile users (MUs) by jointly analyzing their social relationships and channel conditions. Based on the selected CHs, the content caching and content delivering are formulated into two weighted matching problems. Two belief propagation (BP) based distributed algorithms are then proposed by considering content popularity and channel states to solve the aforementioned problems. Furthermore, based on the correlation of the three subproblems, a heuristic-based alternating iterative optimization method (HAIOM) is proposed to improve the average energy consumption performance of the content delivering of the WDCS. Simulation results show that by jointly optimizing the CH selection, content caching, and content delivering, the proposed scheme is capable of reducing the average energy consumption and the average content delivery delay, as well as of increasing the caching hit ratio.

Compared with successive cancellation list (SCL) decoders, belief propagation (BP)-based decoders suffer performance loss in middle-and high-signal-to-noise ratio (SNR) regions. By analyzing the behavior of the incorrect decoding results of the bit-flipping BP decoder with a critical set of order ω (BFBP-CSω), we found that undetected errors mainly contribute to the error floor. Based on this observation, we proposed a belief propagation decoder with multiple bit-flipping sets (BFSs) and stopping criteria (BP-MF-MC) in this work. We use multiple stopping criteria to identify undetected errors and a small BFS to find an additional estimated codeword given by the bit-flipping BP (BFBP) function. For uncorrected errors, we use multiple BFSs to find estimated codewords with the BFBP function. Furthermore, we propose a method to dynamically generate a BFS based on the submatrix check. This method can remove unnecessary bit-flipping positions and increase the order of the critical set. Then, the best codeword is selected from all estimated codewords according to the maximum likelihood principle. Numerical results show that BP-MF-MC performs similarly to the cyclic redundancy check-aided SCL (CA-SCL) decoder with list size 16 and is slightly worse than CA-SCL with list size 32.

The belief propagation (BP) decoding of polar codes provides better bit error rate (BER) and packet error rate (PER) performance than the successive cancelation (SC) decoding. It has been reported in the literature that the graph of BP decoding of polar codes can be permuted to provide even better decoding performance. In this paper, we theoretically prove that all permutations of the graph are equivalent in terms of the polar encoding. For BP decoding, it is shown that permutations of the layers of the graph also permute the bit channels. A principle which protects the weakest information bit channel is provided in the paper. Two parallel BP decoders, one employing the standard graph and the other selected based on the selection principle, are also proposed to work together. The simulation results show that when the total number of iterations is fixed, the proposed BP decoding can have the same performance as the existing permutation scheme while provides a higher throughput.

The location-based social network (LBSN) contains a large amount of user check-in data informations, in order to better improve the recommendation performance and avoid the impact of user check-in data sparsity. It is proposed to mine the time-category informations in the user's check-in data to carry out network modeling; by using the belief propagation algorithm on the time-category Markov network to obtain the user's social influence set. Calculating the similarity and familiarity of the social users in the collection, linearly integrate the unified social influence factors and geographical location influences, to recommend locations. Experimental analysis in the Foursquare dataset, compared with other algorithms, the recommendation algorithm performance of combining social influence and geographic location based on belief propagation has improved.

This paper studies the convergence properties of the well-known message-passing algorithm for convex optimisation. Under the assumption of pairwise separability and scaled diagonal dominance, asymptotic convergence is established and a simple bound for the convergence rate is provided for message-passing. In comparison with previous results, our results do not require the given convex program to have known convex pairwise components and that our bound for the convergence rate is tighter and simpler. When specialised to quadratic optimisation, we generalise known results by providing a very simple bound for the convergence rate. [ABSTRACT FROM AUTHOR]

It has been shown that direct target localization in distributed multiple input multiple output (MIMO) radar can outperform indirect localization significantly, but conventional direct localization methods suffer from both high computational complexity and high communication cost. In this work, we address the issues by designing an efficient factor graph based message passing approach to direct localization, which greatly reduces the computational complexity and communication cost. First, a factor graph representation for the problem of direct localization is developed, which, however, involves difficult local functions. Inspired by expectation propagation (EP), we design an iterative method to solve the problem, where both EP and belief propagation (BP) are used to make message passing in the factor graph tractable, leading to a low complexity message passing iterative method. We show that the message passing based method are very suitable for decentralized processing and can be employed in distributed radars with different configurations. Extensive comparisons with state-of-the-art indirect and direct methods are provided, which show that the proposed method can achieve similar performance to the exhaustive search-based direct localization methods while with much lower computational complexity and communication cost, and it outperforms significantly indirect localization methods at low signal to noise ratios. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This paper presents a new approach to accurately and efficiently identifying a large number of wireless devices blindly installed to known three-dimensional installation/fitting points, based on received signal strengths (RSSs) between the devices. The approach is non-trivial because of the factorial, mapping nature of the considered problem, the multiplicative ranging errors of the RSS measurements (with standard deviation of 5–7 dB), and the requirement of high mapping accuracy in many internet-of-things (IoT) applications, e.g., industrial IoT and aircraft. The consideration of a structured environment where the set of candidate node positions is known beforehand shifts the problem of interest from a pure position estimation problem to a position assignment problem. The key idea of the proposed approach is that we interpret the position mapping problem with a probabilistic graphical model, where the factorial nature of mapping (more specifically, the mutual exclusiveness of devices at every installation point) is fully captured. A max-product belief propagation is designed against the probabilistic graph, to estimate the max-marginal position distribution of each device. The Kuhn-Munkres algorithm is applied to preserve the mutual exclusiveness of devices throughout the belief propagation and to decide device locations based on the estimated position distributions. Large-scale simulations and field tests are carried out, showing that the new approach achieves close-to-100% accuracy in simulations with hundreds of blindfolded devices under RSS measurement errors with standard deviation of 5–7 dB. Our approach also achieves 100% accuracy in all field trials with 76 devices inside the cabin of a Fokker 100 airplane, dramatically outperforming baseline techniques. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 70 000 buses. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Belief propagation (BP) decoding of low-density parity-check (LDPC) codes with various dynamic decoding schedules have been proposed to improve the efficiency of the conventional flooding schedule. As the ultimate goal of an ideal LDPC code decoder is to have correct bit decisions, a dynamic decoding schedule should be variable node (VN)-centric and be able to find the VNs with probable incorrect decisions and having a good chance to be corrected if chosen for update. We propose a novel and effective metric called conditional innovation (CI) which serves this design goal well. To make the most of dynamic scheduling which produces high-reliability bit decisions, we limit our search for the candidate VNs to those related to the latest updated nodes only. Based on the CI metric and the new search guideline separately or in combination, we develop several highly efficient decoding schedules. To reduce decoding latency, we introduce multi-edge updating versions which offer extra latency-performance tradeoffs. Numerical results show that both single-edge and multi-edge algorithms provide better decoding performance against most dynamic schedules and the CI-based algorithms are particularly impressive at the first few decoding iterations. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We study multi-marginal optimal transport problems from a probabilistic graphical model perspective. We point out an elegant connection between the two when the underlying cost for optimal transport allows a graph structure. In particular, an entropy regularized multi-marginal optimal transport is equivalent to a Bayesian marginal inference problem for probabilistic graphical models with the additional requirement that some of the marginal distributions are specified. This relation on the one hand extends the optimal transport as well as the probabilistic graphical model theories, and on the other hand leads to fast algorithms for multi-marginal optimal transport by leveraging the well-developed algorithms in Bayesian inference. Several numerical examples are provided to highlight the results. [ABSTRACT FROM AUTHOR]

We consider near maximum-likelihood (ML) decoding of short linear block codes. In particular, we propose a novel decoding approach based on neural belief propagation (NBP) decoding recently introduced by Nachmani et al. in which we allow a different parity-check matrix in each iteration of the algorithm. The key idea is to consider NBP decoding over an overcomplete parity-check matrix and use the weights of NBP as a measure of the importance of the check nodes (CNs) to decoding. The unimportant CNs are then pruned. In contrast to NBP, which performs decoding on a given fixed parity-check matrix, the proposed pruning-based neural belief propagation (PB-NBP) typically results in a different parity-check matrix in each iteration. For a given complexity in terms of CN evaluations, we show that PB-NBP yields significant performance improvements with respect to NBP. We apply the proposed decoder to the decoding of a Reed-Muller code, a short low-density parity-check (LDPC) code, and a polar code. PB-NBP outperforms NBP decoding over an overcomplete parity-check matrix by 0.27–0.31 dB while reducing the number of required CN evaluations by up to 97%. For the LDPC code, PB-NBP outperforms conventional belief propagation with the same number of CN evaluations by 0.52 dB. We further extend the pruning concept to offset min-sum decoding and introduce a pruning-based neural offset min-sum (PB-NOMS) decoder, for which we jointly optimize the offsets and the quantization of the messages and offsets. We demonstrate performance 0.5 dB from ML decoding with 5-bit quantization for the Reed-Muller code. [ABSTRACT FROM AUTHOR]

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 article, 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 trade-off 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The bit-flip method has been successfully applied to the successive cancellation (SC) decoder to improve the block error rate (BLER) performance for polar codes in the finite code length region. However, due to the sequential decoding, the SC decoder inherently suffers from longer decoding latency than that of the belief propagation (BP) decoder with efficient early stopping criterion. It is natural to ask how to perform bit-flip in a polar BP decoder. In this paper, bit-flip is introduced into the BP decoder for polar codes. The idea of critical set (CS), that is, originally proposed by Zhang et al. for identifying unreliable bits in a SC bit-flip decoder, is extended to the BP decoder here. After revealing the relationship between CS and the incorrect BP decoding results, critical set with order ω (CS-ω) is constructed to identify unreliable bit decisions in polar BP decoding. The simulation results demonstrate that compared with the conventional BP decoder, the BLER of the proposed bit-flip decoder can achieve significant signal-to-noise ratio (SNR) gain which is comparable to that of a cyclic redundancy check-aided SC list decoder with a moderate list size. In addition, the decoding latency of the proposed BP bit-flip decoder is only slightly higher than that of the conventional BP decoder in the medium and high SNR regions.

Polar codes have become the channel coding scheme for control channel of enhanced mobile broadband in the fifth generation (5G) communication systems. Belief propagation (BP) decoding of polar codes has the advantage of low decoding latency and high parallelism but suffers from high complexity. In this paper, a low complexity BP decoder is proposed for polar codes. We reduce the computational complexity by two steps. First, the cyclic redundancy check is concatenated to the decoder in order to decrease the number iterations of the BP algorithm. Then, a threshold is proposed based on Gaussian approximation to save the computational complexity of BP nodes. If the log-likelihood ratio of a node in the tanner graph is larger than the threshold, this node is no longer updated during the rest of the decoding process. The simulation results show that the proposed scheme has a similar block error rate performance with the original BP decoder, while the computational complexity is reduced significantly.