Improved Segmented Belief Propagation List Decoding for Polar Codes with Bit-Flipping

Belief propagation list(BPL) decoding for polar codes has attracted more attention due to its inherent parallel nature. However, a large gap still exists with CRC-aided SCL(CA-SCL) decoding.In this work, an improved segmented belief propagation list decoding based on bit flipping(SBPL-BF) is proposed. On the one hand, the proposed algorithm makes use of the cooperative characteristic in BPL decoding such that the codeword is decoded in different BP decoders. Based on this characteristic, the unreliable bits for flipping could be split into multiple subblocks and could be flipped in different decoders simultaneously. On the other hand, a more flexible and effective processing strategy for the priori information of the unfrozen bits that do not need to be flipped is designed to improve the decoding convergence. In addition, this is the first proposal in BPL decoding which jointly optimizes the bit flipping of the information bits and the code bits. In particular, for bit flipping of the code bits, a H-matrix aided bit-flipping algorithm is designed to enhance the accuracy in identifying erroneous code bits. The simulation results show that the proposed algorithm significantly improves the errorcorrection performance of BPL decoding for medium and long codes. It is more than 0.25 d B better than the state-of-the-art BPL decoding at a block error rate(BLER) of 10^(-5), and outperforms CA-SCL decoding in the low signal-to-noise(SNR) region for(1024, 0.5)polar codes.

Belief Propagation List Decoding for Polar Codes:Performance Analysis and Software Implementation on GPU

Belief propagation(BP)decoding outputs soft information and can be naturally used in iterative receivers.BP list(BPL)decoding provides comparable error-correction performance to the successive cancellation list(SCL)decoding.In this paper,we firstly introduce an enhanced code construction scheme for BPL decoding to improve its errorcorrection capability.Then,a GPU-based BPL decoder with adoption of the new code construction is presented.Finally,the proposed BPL decoder is tested on NVIDIA RTX3070 and GTX1060.Experimental results show that the presented BPL decoder with early termination criterion achieves above 1 Gbps throughput on RTX3070 for the code(1024,512)with 32 lists under good channel conditions.

Parity-check and G-matrix based intelligent early stopping criterion for belief propagation decoder for polar codes

The error correction performance of Belief Propagation(BP)decoding for polar codes is satisfactory compared with the Successive Cancellation(SC)decoding.Nevertheless,it has to complete a fixed number of iterations,which results in high computational complexity.This necessitates an intelligent identification of successful BP decoding for early termination of the decoding process to avoid unnecessary iterations and minimize the computational complexity of BP decoding.This paper proposes a hybrid technique that combines the“paritycheck”with the“G-matrix”to reduce the computational complexity of BP decoder for polar codes.The proposed hybrid technique takes advantage of the parity-check to intelligently identify the valid codeword at an early stage and terminate the BP decoding process,which minimizes the overhead of the G-matrix and reduces the computational complexity of BP decoding.We explore a detailed mechanism incorporating the parity bits as outer code and prove that the proposed hybrid technique minimizes the computational complexity while preserving the BP error correction performance.Moreover,mathematical formulation for the proposed hybrid technique that minimizes the computation cost of the G-matrix is elaborated.The performance of the proposed hybrid technique is validated by comparing it with the state-of-the-art early stopping criteria for BP decoding.Simulation results show that the proposed hybrid technique reduces the iterations by about 90%of BP decoding in a high Signal-to-Noise Ratio(SNR)(i.e.,3.5~4 dB),and approaches the error correction performance of G-matrix and conventional BP decoder for polar codes.

Link prediction in complex networks via modularity-based belief propagation

Link prediction aims at detecting missing, spurious or evolving links in a network, based on the topological information and/or nodes＇ attributes of the network. Under the assumption that the likelihood of the existence of a link between two nodes can be captured by nodes＇ similarity, several methods have been proposed to compute similarity directly or indirectly, with information on node degree. However, correctly predicting links is also crucial in revealing the link formation mechanisms and thus in providing more accurate modeling for networks. We here propose a novel method to predict links by incorporating stochastic-block-model link generating mechanisms with node degree. The proposed method first recov- ers the underlying block structure of a network by modularity-based belief propagation, and based on the recovered block structural information it models the link likelihood between two nodes to match the degree sequence of the network. Experiments on a set of real-world networks and synthetic networks generated by stochastic block model show that our proposed method is effective in detecting missing, spurious or evolving links of networks that can be well modeled by a stochastic block model. This approach efficiently complements the toolbox for complex network analysis, offering a novel tool to model links in stochastic block model networks that are fundamental in the modeling of real world complex networks.

Low-loss belief propagation decoder with Tanner graph in quantum error-correction codes

Quantum error-correction codes are immeasurable resources for quantum computing and quantum communication.However,the existing decoders are generally incapable of checking node duplication of belief propagation(BP)on quantum low-density parity check(QLDPC)codes.Based on the probability theory in the machine learning,mathematical statistics and topological structure,a GF(4)(the Galois field is abbreviated as GF)augmented model BP decoder with Tanner graph is designed.The problem of repeated check nodes can be solved by this decoder.In simulation,when the random perturbation strength p=0.0115-0.0116 and number of attempts N=60-70,the highest decoding efficiency of the augmented model BP decoder is obtained,and the low-loss frame error rate(FER)decreases to 7.1975×10^(-5).Hence,we design a novel augmented model decoder to compare the relationship between GF(2)and GF(4)for quantum code[[450,200]]on the depolarization channel.It can be verified that the proposed decoder provides the widely application range,and the decoding performance is better in QLDPC codes.

A Multi-Vehicle Cooperative Localization Method Based on Belief Propagation in Satellite Denied Environment

The global navigation satellite system(GNSS)is currently being used extensively in the navigation system of vehicles.However,the GNSS signal will be faded or blocked in complex road environments,which will lead to a decrease in positioning accuracy.Owing to the higher-precision synchronization provided in the sixth generation(6G)network,the errors of ranging-based positioning technologies can be effectively reduced.At the same time,the use of terahertz in 6G allows excellent resolution of range and angle,which offers unique opportunities for multi-vehicle cooperative localization in a GNSS denied environment.This paper introduces a multi-vehicle cooperative localization method.In the proposed method,the location estimations of vehicles are derived by utilizing inertial measurement and then corrected by exchanging the beliefs with adjacent vehicles and roadside units.The multi-vehicle cooperative localization problem is represented using a factor graph.An iterative algorithm based on belief propagation is applied to perform the inference over the factor graph.The results demonstrate that our proposed method can offer a considerable capability enhancement on localization accuracy.

A Survey on Belief Propagation Decoding of Polar Codes

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 the manuscript.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.

Iterative Receiver for Orthogonal Time Frequency Space with Index Modulation via Structured Prior-Based Hybrid Belief and Expectation Propagation

Orthogonal Time Frequency Space(OTFS)signaling with index modulation(IM)is a promising transmission scheme characterized by high transmission efficiency for high mobility scenarios.In this paper,we study the receiver for coded OTFS-IM system.First,we construct the corresponding factor graph,on which the structured prior incorporating activation pattern constraint and channel coding is devised.Then we develop a iterative receiver via structured prior-based hybrid belief propagation(BP)and expectation propagation(EP)algorithm,named as StrBP-EP,for the coded OTFS-IM system.To reduce the computational complexity of discrete distribution introduced by structured prior,Gaussian approximation conducted by EP is adopted.To further reduce the complexity,we derive two variations of the proposed algorithm by using some approximations.Simulation results validate the superior performance of the proposed algorithm.

Image Segmentation via Mean Shift and Loopy Belief Propagation

This paper presents a novel approach that can quickly and effectively partition images based on fully exploiting the spatially coherent property. We propose an algorithm named iterative loopy belief propagation（iLBP） to integrate the homogenous regions and prove its convergence. The image is first segmented by mean shift（MS） algorithm to form over-segmented regions that preserve the desirable edges and spatially coherent parts. The segmented regions are then represented by region adjacent graph（RAG） . Motivated by k-means algorithm,the iLBP algorithm is applied to perform the minimization of the cost function to integrate the over-segmented parts to get the final segmentation result. The image clustering based on the segmented regions instead of the image pixels reduces the number of basic image entities and enhances the image segmentation quality. Comparing the segmentation result with some existing algorithms,the proposed algorithm shows a better performance based on the evaluation criteria of entropy especially on complex scene images.

Loopy belief propagation based data association for extended target tracking

The data association problem of multiple extended target tracking is very challenging because each target may generate multiple measurements.Recently,the belief propagation based multiple target tracking algorithms with high efficiency have been a research focus.Different from the belief propagation based Extended Target tracking based on Belief Propagation(ET-BP)algorithm proposed in our previous work,a new graphical model formulation of data association for multiple extended target tracking is proposed in this paper.The proposed formulation can be solved by the Loopy Belief Propagation(LBP)algorithm.Furthermore,the simplified measurement set in the ET-BP algorithm is modified to improve tracking accuracy.Finally,experiment results show that the proposed algorithm has better performance than the ET-BP and joint probabilistic data association based on the simplified measurement set algorithms in terms of accuracy and efficiency.Additionally,the convergence of the proposed algorithm is verified in the simulations.

Sequential stratified sampling belief propagation for multiple targets tracking

Rather than the difficulties of highly non-linear and non-Gaussian observation process and the state distribution in single target tracking, the presence of a large, varying number of targets and their interactions place more challenge on visual tracking. To overcome these difficulties, we formulate multiple targets tracking problem in a dynamic Markov network which consists of three coupled Markov random fields that model the following： a field for joint state of multi-target, one binary process for existence of individual target, and another binary process for occlusion of dual adjacent targets. By introducing two robust functions, we eliminate the two binary processes, and then apply a novel version of belief propagation called sequential stratified sampling belief propagation algorithm to obtain the maximum a posteriori （MAP） estimation in the dynamic Markov network, By using stratified sampler, we incorporate bottom-up information provided by a learned detector （e.g. SVM classifier） and belief information for the messages updating. Other low-level visual cues （e.g. color and shape） can be easily incorporated in our multi-target tracking model to obtain better tracking results. Experimental results suggest that our method is comparable to the state-of-the-art multiple targets tracking methods in several test cases.

Online belief propagation algorithm for probabilistic latent semantic analysis

Probabilistic latent semantic analysis （PLSA） is a topic model for text documents, which has been widely used in text mining, computer vision, computational biology and so on. For batch PLSA inference algorithms, the required memory size grows linearly with the data size, and handling massive data streams is very difficult. To process big data streams, we propose an online belief propagation （OBP） algorithm based on the improved factor graph representation for PLSA. The factor graph of PLSA facilitates the classic belief propagation （BP） algorithm. Furthermore, OBP splits the data stream into a set of small segments, and uses the estimated parameters of previous segments to calculate the gradient descent of the current segment. Because OBP removes each segment from memory after processing, it is memoryefficient for big data streams. We examine the performance of OBP on four document data sets, and demonstrate that OBP is competitive in both speed and accuracy for online ex- pectation maximization （OEM） in PLSA, and can also give a more accurate topic evolution. Experiments on massive data streams from Baidu further confirm the effectiveness of the OBP algorithm.

Non-parametric belief propagation for mobile mapping sensor fusion

Many different forms of sensor fusion have been proposed each with its own niche.We propose a method of fusing multiple different sensor types.Our approach is built on the discrete belief propagation to fuse photogrammetry with GPS to generate three-dimensional(3D)point clouds.We propose using a non-parametric belief propagation similar to Sudderth et al’s work to fuse different sensors.This technique allows continuous variables to be used,is trivially parallel making it suitable for modern many-core processors,and easily accommodates varying types and combinations of sensors.By defining the relationships between common sensors,a graph containing sensor readings can be automatically generated from sensor data without knowing a priori the availability or reliability of the sensors.This allows the use of unreliable sensors which firstly,may start and stop providing data at any time and secondly,the integration of new sensor types simply by defining their relationship with existing sensors.These features allow a flexible framework to be developed which is suitable for many tasks.Using an abstract algorithm,we can instead focus on the relationships between sensors.Where possible we use the existing relationships between sensors rather than developing new ones.These relationships are used in a belief propagation algorithm to calculate the marginal probabilities of the network.In this paper,we present the initial results from this technique and the intended course for future work.

Multiuser detection algorithm based on belief propagation in multiple-input multiple-output systems

In MIMO (multiple-input, multiple-output) systems, signals from differenttransmitting antennas interfere at each receiving antenna and multiuser detection (MUD)algorithms may be adopted to improve the system performance. This paper proposes anovel multiuser detection algorithm in MIMO systems based on the idea of 'beliefpropagation' which has achieved great accomplishment in decoding of low-densityparity-check codes. The proposed algorithm has a low computation complexityproportional to the square of transmitting/receiving antenna number. Simulation resultsshow that under low signal-to-noise ratio (SNR) circumstances, the proposed algorithmoutperforms the traditional linear minimum mean square error (MMSE) detector while itencounters a 'floor' of bit error rate under high SNR circumstances. So the proposedalgorithm is applicable to MIMO systems with channel coding and decoding. Although inthis paper the proposed algorithm is derived in MIMO systems, obviously it can be appliedto ordinary code-division multiple access (CDMA) systems.

Achieving Differential Privacy of Genomic Data Releasing via Belief Propagation

Privacy preserving data releasing is an important problem for reconciling data openness with individual privacy. The state-of-the-art approach for privacy preserving data release is differential privacy, which offers powerful privacy guarantee without confining assumptions about the background knowledge about attackers. For genomic data with huge-dimensional attributes, however, current approaches based on differential privacy are not effective to handle. Specifically, amount of noise is required to be injected to genomic data with tens of million of SNPs （Single Nucleotide Polymorphisms）, which would significantly degrade the utility of released data. To address this problem, this paper proposes a differential privacy guaranteed genomic data releasing method. Through executing belief propagation on factor graph, our method can factorize the distribution of sensitive genomic data into a set of local distributions. After injecting differential-privacy noise to these local distributions, synthetic sensitive data can be obtained by sampling on noise distribution. Synthetic sensitive data and factor graph can be further used to construct approximate distribution of non-sensitive data. Finally, non-sensitive genomic data is sampled from the approximate distribution to construct a synthetic genomic dataset.

A Denoiser for Correlated Noise Channel Decoding: Gated-Neural Network

This letter proposes a sliced-gated-convolutional neural network with belief propagation(SGCNN-BP) architecture for decoding long codes under correlated noise. The basic idea of SGCNNBP is using Neural Networks(NN) to transform the correlated noise into white noise, setting up the optimal condition for a standard BP decoder that takes the output from the NN. A gate-controlled neuron is used to regulate information flow and an optional operation—slicing is adopted to reduce parameters and lower training complexity. Simulation results show that SGCNN-BP has much better performance(with the largest gap being 5dB improvement) than a single BP decoder and achieves a nearly 1dB improvement compared to Fully Convolutional Networks(FCN).

Current-Aided Multiple-AUV Cooperative Localization and Target Tracking in Anchor-Free Environments

In anchor-free environments,where no devices with known positions are available,the error growth of autonomous underwater vehicle(AUV)localization and target tracking is unbounded due to the lack of references and the accumulated errors in inertial measurements.This paper aims to improve the localization and tracking accuracy by involving current information as extra references.We first integrate current measurements and maps with belief propagation and design a distributed current-aided message-passing scheme that theoretically solves the localization and tracking problems.Based on this scheme,we propose particle-based cooperative localization and target tracking algorithms,named CaCL and CaTT,respectively.In AUV localization,CaCL uses the current measurements to correct the predicted and transmitted position information and alleviates the impact of the accumulated errors in inertial measurements.With target tracking,the current maps are applied in CaTT to modify the position prediction of the target which is calculated through historical estimates.The effectiveness and robustness of the proposed methods are validated through various simulations by comparisons with alternative methods under different trajectories and current conditions.

Joint Multi-User Detection with Weighting Factors for Unsourced Multiple Access

Multi-user detection techniques are currently being studied as highly promising technologies for improving the performance of unsourced multiple access systems. In this paper, we propose joint multi-user detection schemes with weighting factors for unsourced multiple access. First, we introduce bidirectional weighting factors in the extrinsic information passing process between the multi-user detector based on belief propagation (BP) and the LDPC decoder. Second, we incorporate bidirectional weighting factors in the message passing process between the MAC nodes and the user variable nodes in BP- based multi-user detector. The proposed schemes select the optimal weighting factors through simulations. The simulation results demonstrate that the proposed schemes exhibit significant performance improvements in terms of block error rate (BLER) compared to traditional schemes. .

Improved Reduced Latency Soft-Cancellation Algorithm for Polar Decoding

Soft-cancellation(SCAN) is a soft output iterative algorithm widely used in polar decoding. This algorithm has better decoding performance than reduced latency soft-cancellation(RLSC) algorithm, which can effectively reduce the decoding delay of SCAN algorithm by 50% but has obvious performance loss. A modified reduced latency soft-cancellation(MRLSC) algorithm is presented in the paper. Compared with RLSC algorithm, LLR information storage required in MRLSC algorithm can be reduced by about 50%, and better decoding performance can be achieved with only a small increase in decoding delay. The simulation results show that MRLSC algorithm can achieve a maximum block error rate(BLER) performance gain of about 0.4 dB compared with RLSC algorithm when code length is 2048. At the same time, compared with the performance of several other algorithms under(1024, 512) polar codes, the results show that the throughput of proposed MRLSC algorithm has the advantage at the low and medium signal-to-noise ratio(SNR) and better BLER performance at the high SNR.

CLOUD IMAGE DETECTION BASED ON MARKOV RANDOM FIELD

In order to overcome the disadvantages of low accuracy rate, high complexity and poor robustness to image noise in many traditional algorithms of cloud image detection, this paper proposed a novel algorithm on the basis of Markov Random Field (MRF) modeling. This paper first defined algorithm model and derived the core factors affecting the performance of the algorithm, and then, the solving of this algorithm was obtained by the use of Belief Propagation (BP) algorithm and Iterated Conditional Modes (ICM) algorithm. Finally, experiments indicate that this algorithm for the cloud image detection has higher average accuracy rate which is about 98.76% and the average result can also reach 96.92% for different type of image noise.