Search

We consider the application of the factor graph framework for symbol detection on linear inter-symbol interference channels. Based on the Ungerboeck observation model, a detection algorithm with appealing complexity properties can be derived. However, since the underlying factor graph contains cycles, the sum-product algorithm (SPA) yields a suboptimal algorithm. In this paper, we develop and evaluate efficient strategies to improve the performance of the factor graph-based symbol detection by means of neural enhancement. In particular, we consider neural belief propagation and generalizations of the factor nodes as an effective way to mitigate the effect of cycles within the factor graph. By applying a generic preprocessor to the channel output, we propose a simple technique to vary the underlying factor graph in every SPA iteration. Using this dynamic factor graph transition, we intend to preserve the extrinsic nature of the SPA messages which is otherwise impaired due to cycles. Simulation results show that the proposed methods can massively improve the detection performance, even approaching the maximum a posteriori performance for various transmission scenarios, while preserving a complexity which is linear in both the block length and the channel memory. [ABSTRACT FROM AUTHOR]

We study the behavior of the belief-propagation (BP) algorithm affected by erroneous data exchange in a wireless sensor network (WSN). The WSN conducts a distributed multidimensional hypothesis test over binary random variables. The joint statistical behavior of the sensor observations is modeled by a Markov random field whose parameters are used to build the BP messages exchanged between the sensing nodes. Through linearization of the BP message-update rule, we analyze the behavior of the resulting erroneous decision variables and derive closed-form relationships that describe the impact of stochastic errors on the performance of the BP algorithm. We then develop a decentralized distributed optimization framework to enhance the system performance by mitigating the impact of errors via a distributed linear data-fusion scheme. Finally, we compare the results of the proposed analysis with the existing works and visualize, via computer simulations, the performance gain obtained by the proposed optimization. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel detector for single-channel long-haul coherent optical communications, termed stochastic digital backpropagation (SDBP), which takes into account noise from the optical amplifiers in addition to handling deterministic linear and nonlinear impairments. We discuss the design approach behind this detector, which is based on the maximum a posteriori (MAP) principle. As closed-form expressions of the MAP detector are not tractable for coherent optical transmission, we employ the framework of Bayesian graphical models, which allows a numerical evaluation of the proposed detector. Through simulations, we observe that by accounting for nonlinear signal—noise interactions, we achieve a significant improvement in system reach with SDBP over digital backpropagation (DBP) for systems with periodic inline optical dispersion compensation. In uncompensated links with high symbol rates, the performance difference in terms of system reach for SDBP over DBP is small. In the absence of noise, the proposed detector is equivalent to the well-known DBP detector. [ABSTRACT FROM PUBLISHER]

In this paper we provide necessary and sufficient conditions for constituent codes in (multiple) concatenated and graph-based coding schemes to achieve an asymptotically error-free iterative decoding fixed-point if the maximum possible a priori information is available. At least one constituent code in an iterative decoding scheme must satisfy these conditions in order to ensure an asymptotically vanishing bit error probability at the convergence point of the decoder. Our results are proved for arbitrary binary-input symmetric memoryless channels (BISMCs) and thus can be universally applied to many transmission scenarios. Specifically, using a factor graph framework, it is shown that non-inner codes in a serial concatenation or check nodes in generalized LDPC codes achieve perfect extrinsic information if and only if the minimum Hamming distance between codewords is two or greater. For inner codes in a serial concatenation, constituent codes in a parallel concatenation, or variable nodes in doubly-generalized LDPC codes the corresponding encoder condition for acquiring perfect extrinsic information is an infinite codeword weight for a weight-one input sequence. For this case we provide a general proof which holds for all linear encoders and BISMCs. We also show that these results can improve the performance of concatenated coding schemes. [ABSTRACT FROM PUBLISHER]

Clock synchronization has become an indispensable requirement in wireless sensor networks due to its central importance in vital network operations such as data fusion and duty cycling, and has attracted considerable research interest recently. Assuming exponentially distributed random delays in a two-way message exchange mechanism, this work proposes a network-wide clock synchronization algorithm using a factor graph representation of the network. Message passing using the max-product algorithm is adopted to derive the update rules for the proposed iterative procedure. A closed form solution is obtained for each node's belief about its clock offset at each iteration. Simulation results show that the application of the proposed message passing-based network-wide clock synchronization algorithm provides convergent estimates for both regular cycle-free and random topologies. Moreover, the mean square error (MSE) performance of the proposed algorithm is also compared with the Cramer-Rao bound (CRB) for small example networks, which further highlights the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

A large number of stochastic networks including loss networks and certain queueing networks have product-form steady-state probabilities. However, for most practical networks, evaluating the system performance is a difficult task due to the presence of a normalization constant. We propose a new framework based on probabilistic graphical models to tackle this task. Specifically, we use factor graphs to model the stationary distribution of a network. For networks with arbitrary topology, we can apply efficient message-passing algorithms like the sum-product algorithm to compute the exact or approximate marginal distributions of all state variables and related performance measures such as blocking probabilities. Through extensive numerical experiments, we show that the sum-product algorithm returns very accurate blocking probabilities and greatly outperforms the reduced load approximation for loss networks with a variety of topologies. The factor graph model also provides a promising approach for analyzing product-form queueing networks. [ABSTRACT FROM AUTHOR]

This paper presents the systolic array implementation of a real-time symbol-optimum multiuser detection (MUD) algorithm for a direct-sequence code-division multiple-access system by truncating the backward recursions in the generalized forward/backward schedule. Simulation results show that the real-time algorithm provides negligible performance loss compared to the original symbol-optimum detection algorithm. The systolic array implementation is derived in this paper through the factor graph language of the real-time algorithm in order to exploit the suitability of the algorithm for parallel signal processing. [ABSTRACT FROM AUTHOR]

The performance of the generalized belief propagation algorithm to compute the noiseless capacity and mutual information rates of finite-size two-dimensional and three-dimensional run-length limited constraints is investigated. In both cases, the problem is reduced to estimating the partition function of graphical models with cycles. The partition function is then estimated using the region-based free energy approximation technique. For each constraint, a method is proposed to choose the basic regions and to construct the region graph which provides the graphical framework to run the generalized belief propagation algorithm. Simulation results for the noiseless capacity of different constraints as a function of the size of the channel are reported. In the cases that tight lower and upper bounds on the Shannon capacity exist, convergence to the Shannon capacity is discussed. For noisy constrained channels, simulation results are reported for mutual information rates as a function of signal-to-noise ratio. [ABSTRACT FROM AUTHOR]

It is shown that a large class of communication systems which admit a sum-product algorithm (SPA) based receiver also admit a corresponding linear-programming (LP) based receiver. The two receivers have a relationship defined by the local structure of the underlying graphical model, and are inhibited by the same phenomenon, which we call pseudoconfigurations. This concept is a generalization of the concept of pseudocodewords for linear codes. It is proved that the LP receiver has the `maximum likelihood certificate' property, and that the receiver output is the lowest cost pseudoconfiguration. Equivalence of graph-cover pseudoconfigurations and linear-programming pseudoconfigurations is also proved. A concept of system pseudodistance is defined which generalizes the existing concept of pseudodistance for binary and nonbinary linear codes. It is demonstrated how the LP design technique may be applied to the problem of joint equalization and decoding of coded transmissions over a frequency selective channel, and a simulation-based analysis of the error events of the resulting LP receiver is also provided. For this particular application, the proposed LP receiver is shown to be competitive with other receivers, and to be capable of outperforming turbo equalization in bit and frame error rate performance. [ABSTRACT FROM PUBLISHER]

Belief propagation, via a novel reinterpretation of the Bethe free energy's pseudo-dual, is shown to be related to a novel relaxation of maximum likelihood detection via a constrained optimization. The conventional maximum likelihood detection falls out for a zero constraint, and belief propagation's fixed points are obtained for other constraint values. [ABSTRACT FROM PUBLISHER]