A high‐performance belief propagation decoding algorithm for codes with short cycles

The simplicity of decoding is one of the most important characteristics of the low density parity check (LDPC) codes. Belief propagation (BP) decoding algorithm is a well‐known decoding algorithm for LDPC codes. Most LDPC codes with long lengths have short cycles in their Tanner graphs, which reduce the performance of the BP algorithm. In this paper, we present 2 methods to improve the BP decoding algorithm for LDPC codes. In these methods, the calculation of the variable nodes is controlled by using “multiplicative correction factor” and “additive correction factor.” These factors are obtained for 2 separate channels, namely additive white Gaussian noise (AWGN) and binary symmetric channel (BSC), as 2 functions of code and channel parameters. Moreover, we use the BP‐based method in the calculation of the check nodes, which reduces the required resources. Simulation results show the proposed algorithm has better performance and lower decoding error as compared to BP and similar methods like normalized‐BP and offset‐BP algorithms.     

Bounds on the performance of belief propagation decoding

We consider Gallager's (1963) soft-decoding (belief propagation) algorithm for decoding low-density parity-check (LDPC) codes, when applied to an arbitrary binary-input symmetric-output channel. By considering the expected values of the messages, we derive both lower and upper bounds on the performance of the algorithm. We also derive various properties of the decoding algorithm, such as a certain robustness to the details of the channel noise. Our results apply both to regular and irregular LDPC codes     

基于置信传播的视频运动目标检测

视频运动目标的检测是目标分类和行为理解等后续处理的基础。本文提出一种复杂背景条件下基于置信传播(BP)的视频运动目标检测算法。该算法依据视频背景的空间和时间相关性,分别定义了视频背景的空间和时间能量函数,完成视频运动目标的优化检测。利用置信传播算法在相邻像素之间的信息交换来实现能量最小化,不同背景条件下的实验结果验证了该算法的有效性和准确性。     

系统极化码的置信传播译码性能分析

置信传播( BP)算法可以为系统极化码提供软信息作为判决依据,也可以为系统极化码在级联迭代译码中提供交换软信息。在详细描述基于信道极化结构的置信传播算法基础上,比较了系统极化码在软信息判决方法和极化编码判决方法下错误率性能的差异。仿真结果表明,软信息判决方法可以提高系统极化码的误比特率,在高信噪比下误帧率方面也略有提高。     

Embedded trees: estimation of Gaussian Processes on graphs with cycles

Graphical models provide a powerful general framework for encoding the structure of large-scale estimation problems. However, the graphs describing typical real-world phenomena contain many cycles, making direct estimation procedures prohibitively costly. In this paper, we develop an iterative inference algorithm for general Gaussian graphical models. It operates by exactly solving a series of modified estimation problems on spanning trees embedded within the original cyclic graph. When these subproblems are suitably chosen, the algorithm converges to the correct conditional means. Moreover, and in contrast to many other iterative methods, the tree-based procedures we propose can also be used to calculate exact error variances. Although the conditional mean iteration is effective for quite densely connected graphical models, the error variance computation is most efficient for sparser graphs. In this context, we present a modeling example suggesting that very sparsely connected graphs with cycles may provide significant advantages relative to their tree-structured counterparts, thanks both to the expressive power of these models and to the efficient inference algorithms developed herein. The convergence properties of the proposed tree-based iterations are characterized both analytically and experimentally. In addition, by using the basic tree-based iteration to precondition the conjugate gradient method, we develop an alternative, accelerated iteration that is finitely convergent. Simulation results are presented that demonstrate this algorithm's effectiveness on several inference problems, including a prototype distributed sensing application.     

基于信念传播的分布式最大权匹配算法

针对目前已有的基于信念传播的分布式算法在处理一般图时会出现振荡与不确定现象,导致无法收敛或收敛至不正确解这些方面的不足,分析了其中的振荡现象并改进了相邻边交换消息的计算公式,以及对其中的不确定现象并提出了一种新的处理方法,以消除不确定性,从而形成了一种改进的基于信念传播的分布式最大权匹配算法。仿真结果表明,改进算法具有接近于最优解的良好性能。     

基于变量节点可靠度的洗牌置信传播算法

提出了一种新的低密度奇偶校验(Low-Density Parity-Check,LDPC)码串行译码策略.该方法基于原有的LDPC码串行译码策略,根据来自信道的初始消息的可靠度对变量节点或校验节点进行均匀分组.对所提方法的误码率与平均迭代次数进行了分析.仿真结果表明:该策略的性能比原来的LDPC码串行译码策略有很大提高.     

Variable-to-check residual belief propagation for LDPC codes

Variable-to-check residual belief propagation for LDPC decoding for faster convergence, better error performance and lower complexity is proposed. It is similar to residual belief propagation (RBP) that was recently applied to LDPC decoding by Vila Casado et al. because it is also a dynamic scheduling belief propagation using residuals, but it is different because the residuals are computed from a variable-tocheck message. Simulation shows that it outperforms with only a maximum of eight iterations by about 0.3 dB compared with RBP at an FER of 10²⁴.     

对数似然比置信传播算法的改进

改进对数似然比置信传播(LLR BP)算法,以提高其对低密度奇偶校验(LDPC)码的译码性能。在变量节点间加入信道响应相关性,并在算法中预设迭代次数,以使变量节点间传递的外部信息达到平衡,降低外部信息震荡现象,并保障译码不会因所需迭代次数过大而终止。改进型LLR BP算法可降低误码率,并在信噪比(SNR)较小时降低译码迭代次数。     

Iterative reliability-based decoding of linear block codes with adaptive belief propagation

In this letter, an iterative decoding algorithm for linear block codes combining reliability-based decoding with adaptive belief propagation decoding is proposed. At each iteration, the soft output values delivered by the adaptive belief propagation algorithm are used as reliability values to perform reduced order reliability-based decoding of the code considered. This approach allows to bridge the gap between the error performance achieved by the lower order reliability-based decoding algorithms which remain sub-optimum, and the maximum likelihood decoding, which is too complex to be implemented for most codes employed in practice. Simulations results for various linear block codes are given and elaborated.     

Nonparametric belief propagation for self-localization of sensor networks

Automatic self-localization is a critical need for the effective use of ad hoc sensor networks in military or civilian applications. In general, self-localization involves the combination of absolute location information (e.g., from a global positioning system) with relative calibration information (e.g., distance measurements between sensors) over regions of the network. Furthermore, it is generally desirable to distribute the computational burden across the network and minimize the amount of intersensor communication. We demonstrate that the information used for sensor localization is fundamentally local with regard to the network topology and use this observation to reformulate the problem within a graphical model framework. We then present and demonstrate the utility of nonparametric belief propagation (NBP), a recent generalization of particle filtering, for both estimating sensor locations and representing location uncertainties. NBP has the advantage that it is easily implemented in a distributed fashion, admits a wide variety of statistical models, and can represent multimodal uncertainty. Using simulations of small to moderately sized sensor networks, we show that NBP may be made robust to outlier measurement errors by a simple model augmentation, and that judicious message construction can result in better estimates. Furthermore, we provide an analysis of NBP's communications requirements, showing that typically only a few messages per sensor are required, and that even low bit-rate approximations of these messages can be used with little or no performance impact.     

Constructing free-energy approximations and generalized belief propagation algorithms

Important inference problems in statistical physics, computer vision, error-correcting coding theory, and artificial intelligence can all be reformulated as the computation of marginal probabilities on factor graphs. The belief propagation (BP) algorithm is an efficient way to solve these problems that is exact when the factor graph is a tree, but only approximate when the factor graph has cycles. We show that BP fixed points correspond to the stationary points of the Bethe approximation of the free energy for a factor graph. We explain how to obtain region-based free energy approximations that improve the Bethe approximation, and corresponding generalized belief propagation (GBP) algorithms. We emphasize the conditions a free energy approximation must satisfy in order to be a "valid" or "maxent-normal" approximation. We describe the relationship between four different methods that can be used to generate valid approximations: the "Bethe method", the "junction graph method", the "cluster variation method", and the "region graph method". Finally, we explain how to tell whether a region-based approximation, and its corresponding GBP algorithm, is likely to be accurate, and describe empirical results showing that GBP can significantly outperform BP.     

Bilateral exchange of soft-information for iterative reliability-based decoding with adaptive belief propagation

For linear block codes without a sparse graph representation, there exists an iterative decoding algorithm which combines the traditional reliability-based decoding (RBD) with adaptive belief propagation (ABP) to achieve a good tradeoff between the error performance and decoding complexity. However, in the original design of the iterative scheme, only a one-way flow of soft-information from the ABP-part to the RBD-part is available, hence limiting the performance of iterative processing. In this study, several low-complexity schemes are presented for the RBD-part to produce desirable soft-outputs such that decoded results can be bilaterally exchanged between both of the RBD and ABP parts. Simulation results also verify the superiority of the proposed idea over the conventional design.     

Iterative decoding of one-step majority logic deductible codesbased on belief propagation

Previously, the belief propagation (BP) algorithm has received a lot of attention in the coding community, mostly due to its near-optimum decoding for low-density parity check (LDPC) codes and its connection to turbo decoding. In this paper, we investigate the performance achieved by the BP algorithm for decoding one-step majority logic decodable (OSMLD) codes. The BP algorithm is expressed in terms of likelihood ratios rather than probabilities, as conventionally presented. The proposed algorithm fits better the decoding of OSMLD codes with respect to its numerical stability due to the fact that the weights of their check sums are often much higher than that of the corresponding LDPC codes. Although it has been believed that OSMLD codes are far inferior to LDPC codes, we show that for medium code lengths (say between 200-1000 bits), the BP decoding of OSMLD codes can significantly outperform BP decoding of their equivalent LDPC codes. The reasons for this behavior are elaborated     

Turbo decoding of product codes using adaptive belief propagation

The adaptive belief propagation (ABP) algorithm was recently proposed by Jiang and Narayanan for the soft decoding of Reed-Solomon (RS) codes. In this paper, simplified versions of this algorithm are investigated for the turbo decoding of product codes. The complexity of the turbo-oriented adaptive belief propagation (TAB) algorithm is significantly reduced by moving the matrix adaptation step outside of the belief propagation iteration loop. A reduced-complexity version of the TAB algorithm that offers a trade-off between performance and complexity is also proposed. Simulation results for the turbo decoding of product codes show that belief propagation based on adaptive parity check matrices is a practical alternative to the currently very popular Chase-Pyndiah algorithm.     

Variable non-uniform quantized belief propagation algorithm for LDPC decoding

Non-uniform quantization for messages in Low-Density Parity-Check（LDPC）decoding can reduce implementation complexity and mitigate performance loss.But the distribution of messages varies in the iterative decoding.This letter proposes a variable non-uniform quantized Belief Propagation（BP）algorithm.The BP decoding is analyzed by density evolution with Gaussian approximation.Since the probability density of messages can be well approximated by Gaussian distribution,by the unbiased estimation of variance,the distribution of messages can be tracked during the iteration.Thus the non-uniform quantization scheme can be optimized to minimize the distortion.Simulation results show that the variable non-uniform quantization scheme can achieve better error rate performance and faster decoding convergence than the conventional non-uniform quantization and uniform quantization schemes.     

Reduced complexity iterative decoding of low-density parity checkcodes based on belief propagation

Two simplified versions of the belief propagation algorithm for fast iterative decoding of low-density parity check codes on the additive white Gaussian noise channel are proposed. Both versions are implemented with real additions only, which greatly simplifies the decoding complexity of belief propagation in which products of probabilities have to be computed. Also, these two algorithms do not require any knowledge about the channel characteristics. Both algorithms yield a good performance-complexity trade-off and can be efficiently implemented in software as well as in hardware, with possibly quantized received values     

An analysis of belief propagation on the turbo decoding graph withGaussian densities

Motivated by its success in decoding turbo codes, we provide an analysis of the belief propagation algorithm on the turbo decoding graph with Gaussian densities. In this context, we are able to show that, under certain conditions, the algorithm converges and that-somewhat surprisingly-though the density generated by belief propagation may differ significantly from the desired posterior density, the means of these two densities coincide. Since computation of posterior distributions is tractable when densities are Gaussian, use of belief propagation in such a setting may appear unwarranted. Indeed, our primary motivation for studying belief propagation in this context stems from a desire to enhance our understanding of the algorithm's dynamics in a non-Gaussian setting, and to gain insights into its excellent performance in turbo codes. Nevertheless, even when the densities are Gaussian, belief propagation may sometimes provide a more efficient alternative to traditional inference methods     

LDPC码的交替迭代分层置信传播译码

低密度奇偶校验码(LDPC)通过迭代译码算法进行译码,例如置信传播算法(belief-propagation)便是其中一种译码方式。标准BP算法是并行译码,在更新所有校验节点及比特节点过程中,使用上一次迭代的更新信息。为了提高一定迭代次数下的收敛速度,在研究不同算法的基础上,如Layered BP算法(LBP)和Shuffled BP算法(SBP),通过改变节点的更新顺序,提出了改进的shuffled迭代译码算法。相对于普通的SBP算法,文章所提改进型SBP算法是传统置信传播收敛速度的两倍,并且在保持性能的同时降低复杂度。最后给出了CMMB标准下LDPC码的仿真结果。     

一种结合比特翻转的自适应置信传播算法

提出了一种结合比特翻转的自适应置信传播迭代译码新算法,称之为"BP 比特翻转"算法.首先详细描述了新算法的整个流程,然后在相同仿真条件下比较了传统"BP"和"BP 比特翻转"两者的性能和平均迭代次数,发现新算法要优于传统的"BP"算法,特别是在最大迭代次数较小时,优势就会显得更加突出.