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.

Deep Learning Aided SCL Decoding of Polar Codes with Shifted-Pruning

Recently,a generalized successive cancellation list(SCL)decoder implemented with shiftedpruning(SP)scheme,namely the SCL-SP-ωdecoder,is presented for polar codes,which is able to shift the pruning window at mostωtimes during each SCL re-decoding attempt to prevent the correct path from being eliminated.The candidate positions for applying the SP scheme are selected by a shifting metric based on the probability that the elimination occurs.However,the number of exponential/logarithm operations involved in the SCL-SP-ωdecoder grows linearly with the number of information bits and list size,which leads to high computational complexity.In this paper,we present a detailed analysis of the SCL-SP-ωdecoder in terms of the decoding performance and complexity,which unveils that the choice of the shifting metric is essential for improving the decoding performance and reducing the re-decoding attempts simultaneously.Then,we introduce a simplified metric derived from the path metric(PM)domain,and a custom-tailored deep learning(DL)network is further designed to enhance the efficiency of the proposed simplified metric.The proposed metrics are both free of transcendental functions and hence,are more hardware-friendly than the existing metrics.Simulation results show that the proposed DL-aided metric provides the best error correction performance as comparison with the state of the art.

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.

List-Serial Pipelined Hardware Architecture for SCL Decoding of Polar Codes

For polar codes,the performance of successive cancellation list(SCL)decoding is capable of approaching that of maximum likelihood decoding.However,the existing hardware architectures for the SCL decoding suffer from high hardware complexity due to calculating L decoding paths simultaneously,which are unfriendly to the devices with limited logical resources,such as field programmable gate arrays(FPGAs).In this paper,we propose a list-serial pipelined hardware architecture with low complexity for the SCL decoding,where the serial calculation and the pipelined operation are elegantly combined to strike a balance between the complexity and the latency.Moreover,we employ only one successive cancellation(SC)decoder core without L×L crossbars,and reduce the number of inputs of the metric sorter from 2L to L+2.Finally,the FPGA implementations show that the hardware resource consumption is significantly reduced with negligible decoding performance loss.

A simplified decoding algorithm for multi-CRC polar codes

Polar codes represent one of the major breakthroughs in 5G standard,and have been proven to be able to achieve the symmetric capacity of binary-input discrete memoryless channels using the successive cancellation list(SCL)decoding algorithm.However,the SCL algorithm suffers from a large amount of memory overhead.This paper proposes an adaptive simplified decoding algorithm for multiple cyclic redundancy check(CRC)polar codes.Simulation results show that the proposed method can reduce the decoding complexity and memory space.It can also acquire the performance gain in the low signal to noise ratio region.

Erasure-Correction-Enhanced Iterative Decoding for LDPC-RS Product Codes

Low-density parity-check(LDPC)codes are widely used due to their significant errorcorrection capability and linear decoding complexity.However,it is not sufficient for LDPC codes to satisfy the ultra low bit error rate(BER)requirement of next-generation ultra-high-speed communications due to the error floor phenomenon.According to the residual error characteristics of LDPC codes,we consider using the high rate Reed-Solomon(RS)codes as the outer codes to construct LDPC-RS product codes to eliminate the error floor and propose the hybrid error-erasure-correction decoding algorithm for the outer code to exploit erasure-correction capability effectively.Furthermore,the overall performance of product codes is improved using iteration between outer and inner codes.Simulation results validate that BER of the product code with the proposed hybrid algorithm is lower than that of the product code with no erasure correction.Compared with other product codes using LDPC codes,the proposed LDPC-RS product code with the same code rate has much better performance and smaller rate loss attributed to the maximum distance separable(MDS)property and significant erasure-correction capability of RS codes.

Efficient Soft-Decision Maximum-Likelihood Decoding of BCH Code in the GNSS

Soft-decision decoding of BCH code in the global navigation satellite system( GNSS) is investigated in order to improve the performance of traditional hard-decision decoding. Using the nice structural properties of BCH code,a soft-decision decoding scheme is proposed. It is theoretically shown that the proposed scheme exactly performs maximum-likelihood( ML) decoding,which means the decoding performance is optimal. Moreover,an efficient implementation method of the proposed scheme is designed based on Viterbi algorithm. Simulation results show that the performance of the proposed soft-decision ML decoding scheme is significantly improved compared with the traditional hard-decision decoding method at the expense of moderate complexity increase.

JOINT ITERATIVE DECODING FOR SIMPLE-ENCODING SYSTEMATIC IRREGULAR-LDPC-BASED CODED COOPERATION IN NON-IDEAL RELAY CHANNEL

In this paper, a new kind of simple-encoding irregular systematic LDPC codes suitable for one-relay coded cooperation is designed, where the proposed joint iterative decoding is effectively performed in the destination which is in accordance with the corresponding joint Tanner graph characterizing two different component LDPC codes used by the source and relay in ideal and non-ideal relay cooperations. The theoretical analysis and simulations show that the coded cooperation scheme obviously outperforms the coded non-cooperation one under the same code rate and decoding complex. The significant performance improvement can be virtually credited to the additional mutual exchange of the extrinsic information resulted by the LDPC code employed by the source and its counterpart used by the relay in both ideal and non-ideal cooperations.

Weighted symbol-flipping decoding algorithm for nonbinary LDPC codes with flipping patterns

A novel low-complexity weighted symbol-flipping algorithm with flipping patterns to decode nonbinary low-density parity-check codes is proposed. The proposed decoding procedure updates the hard-decision received symbol vector iteratively in search of a valid codeword in the symbol vector space. Only one symbol is flipped in each iteration, and symbol flipping function, which is employed as the symbol flipping metric, combines the number of failed checks and the reliabilities of the received bits and calculated symbols. A scheme to avoid infinite loops and select one symbol to flip in high order Galois field search is also proposed. The design of flipping pattern＇s order and depth, which is dependent of the computational requirement and error performance, is also proposed and exemplified. Simulation results show that the algorithm achieves an appealing tradeoff between performance and computational requirement over relatively low Galois field for short to medium code length.

Accelerating BP-Based Iterative Low-Density Parity-Check Decoding by Modified Vertical and Horizontal Processes

Two modified BP algorithms related to vertical and horizontal processes are proposed to accelerate iterative low-density parity- check （LDPC） decoding over an additive white Gaussian noise （AWGN） channel, where the newly updated extrinsic information is immediately used in the current decoding round. Theoretical analysis and simulation results demonstrate that both the modified approaches provide significant performance improvements over the traditional BP algorithm with almost no additional decoding complexity. The proposed algorithm with modified horizontal process offers even better performance than another algorithm with the modified horizontal process. The two modified BP algorithms are very promising in practical communications since both can achieve an excellent trade-off between the performance and decoding complexity.

Iterative Decoding of Parallel Concatenated Block Codes and Coset Based MAP Decoding Algorithm for F24 Code

A multi dimensional concatenation scheme for block codes is introduced, in which information symbols are interleaved and re encoded for more than once. It provides a convenient platform to design high performance codes with flexible interleaver size. Coset based MAP soft in/soft out decoding algorithms are presented for the F24 code. Simulation results show that the proposed coding scheme can achieve high coding gain with flexible interleaver length and very low decoding complexity.

Jointly-check iterative decoding algorithm for quantum sparse graph codes

For quantum sparse graph codes with stabilizer formalism, the unavoidable girth-four cycles in their Tanner graphs greatly degrade the iterative decoding performance with standard belief-propagation （BP） algorithm. In this paper, we present a jointly-check iterative algorithm suitable for decoding quantum sparse graph codes efficiently. Numerical simulations show that this modified method outperforms standard BP algorithm with an obvious performance improvement.

Integrated Joint Source-Channel Symbol-by-Symbol Decoding of Variable-Length Codes Using 3-D MAP Sequence Estimation

Most of multimedia schemes employ variable-length codes （VLCs） like Huffman code as core components in obtaining high compression rates. However VLC methods are very sensitive to channel noise. The goal of this paper is to salvage as many data from the damaged packets as possible for higher audiovisual quality. This paper proposes an integrated joint source-channel decoder （I-JSCD） at a symbol-level using three-dimensional （3-D） trellis representation for first-order Markov sources encoded with VLC source code and convolutional channel code. This method combines source code and channel code state-spaces and bit-lengths to construct a two-dimensional （2-D） state-space, and then develops a 3-D trellis and a maximum a-posterior （MAP） algorithm to estimate the source sequence symbol by symbol. Experiment results demonstrate that our method results in significant improvement in decoding performance, it can salvage at least half of （50%） data in any channel error rate, and can provide additional error resilience to VLC stream like image, audio, video stream over high error rate links.

Quaternion Integers Based Higher Length Cyclic Codes and Their Decoding Algorithm

The decoding algorithm for the correction of errors of arbitrary Mannheim weight has discussed for Lattice constellations and codes from quadratic number fields.Following these lines,the decoding algorithms for the correction of errors of n=p−12 length cyclic codes(C)over quaternion integers of Quaternion Mannheim(QM)weight one up to two coordinates have considered.In continuation,the case of cyclic codes of lengths n=p−12 and 2n−1=p−2 has studied to improve the error correction efficiency.In this study,we present the decoding of cyclic codes of length n=ϕ(p)=p−1 and length 2n−1=2ϕ(p)−1=2p−3(where p is prime integer andϕis Euler phi function)over Hamilton Quaternion integers of Quaternion Mannheim weight for the correction of errors.Furthermore,the error correction capability and code rate tradeoff of these codes are also discussed.Thus,an increase in the length of the cyclic code is achieved along with its better code rate and an adequate error correction capability.

Research on encoding and decoding of non-binary polar codes over GF(2m)

Binary Polar Codes (BPCs) have advantages of high-efficiency and capacity-achieving but suffer from large latency due to the Successive-Cancellation List (SCL) decoding. Non-Binary Polar Codes (NBPCs) have been investigated to obtain the performance gains and reduce latency under the implementation of parallel architectures for multi-bit decoding. However, most of the existing works only focus on the Reed-Solomon matrix-based NBPCs and the probability domain-based non-binary polar decoding, which lack flexible structure and have a large computation amount in the decoding process, while little attention has been paid to general non-binary kernel-based NBPCs and Log-Likelihood Ratio (LLR) based decoding methods. In this paper, we consider a scheme of NBPCs with a general structure over GF(2m). Specifically, we pursue a detailed Monte-Carlo simulation implementation to determine the construction for proposed NBPCs. For non-binary polar decoding, an SCL decoding based on LLRs is proposed for NBPCs, which can be implemented with non-binary kernels of arbitrary size. Moreover, we propose a Perfect Polarization-Based SCL (PPB-SCL) algorithm based on LLRs to reduce decoding complexity by deriving a new update function of path metric for NBPCs and eliminating the path splitting process at perfect polarized (i.e., highly reliable) positions. Simulation results show that the bit error rate of the proposed NBPCs significantly outperforms that of BPCs. In addition, the proposed PPB-SCL decoding obtains about a 40% complexity reduction of SCL decoding for NBPCs.

An Iterative Decoding Scheme for Davey-MacKay Construction

In the Davey-MacKay(DM) construction,the inner decoder treats unknown transmitted bits as random independent substitution errors. It limits the synchronization capability of the inner decoder, and thus weakens the error-correcting capability of the DM construction.In order to improve the performance of the DM construction, an iterative decoding scheme is proposed, which iteratively utilizes the more accurate estimates of transmitted codewords. In the proposed scheme, the estimated average bit error rates and the estimated low-density parity-check(LDPC) codewords from the outer decoder are fed back into the inner decoder to update the synchronization process. Simulation results show that the proposed iterative decoding scheme significantly outperforms the traditional DM construction.

Construction of LDPC Codes for the Layered Decoding Algorithm

The layered decoding algorithm has been widely used in the implementation of Low Density Parity Check (LDPC) decoders, due to its high convergence speed. However, the pipeline operation of the layered decoder may introduce memory access conflicts, which heavily deteriorates the decoder throughput. To essentially deal with the issue of memory access conflicts, we propose a construction algorithm of LDPC codes, to which a constraint condition is added in the Progressive Edge-Growth (PEG) algorithm. The constraint condition can guarantee that for our constructed LDPC codes, the sets of all the variable nodes connected to the consecutive layers do not share any common variable node, which can avoid the memory access conflicts. Simulation results show that the performance of our constructed LDPC codes is close to the several other LDPC codes adopted in wireless standards. Moreover, compared with the decoder for IEEE 802. 16e LDPC codes, the throughput of our LDPC decoder has large improvement, while the chip resource consumption is unchanged. Thus, our constructed LDPC codes can be adopted in the high-speed transmission.

NEW ITERATIVE SUPER-TRELLIS DECODING WITH SOURCE A PRIORI INFORMATION FOR VLCS WITH TURBO CODES

A novel Joint Source and Channel Decoding (JSCD) scheme for Variable Length Codes (VLCs) concatenated with turbo codes utilizing a new super-trellis decoding algorithm is presented in this letter. The basic idea of our decoding algorithm is that source a priori information with the form of bit transition probabilities corresponding to the VLC tree can be derived directly from sub-state transitions in new composite-state represented super-trellis. A Maximum Likelihood (ML) decoding algorithm for VLC sequence estimations based on the proposed super-trellis is also described. Simu-lation results show that the new iterative decoding scheme can obtain obvious encoding gain especially for Reversible Variable Length Codes (RVLCs),when compared with the classical separated turbo decoding and the previous joint decoding not considering source statistical characteristics.

Novel joint encoding/decoding algorithms of fountain codes for underwater acoustic communication

Fountain codes are considered to be a promising coding technique in underwater acoustic communication（UAC） which is challenged with the unique propagation features of the underwater acoustic channel and the harsh marine environment. And Luby transform（LT） codes are the first codes fully realizing the digital fountain concept. However, in conventional LT encoding/decoding algorithms, due to the imperfect coverage（IC） of input symbols and short cycles in the generator matrix, stopping sets would occur and terminate the decoding. Thus, the recovery probability is reduced,high coding overhead is required and decoding delay is increased.These issues would be disadvantages while applying LT codes in underwater acoustic communication. Aimed at solving those issues, novel encoding/decoding algorithms are proposed. First,a doping and non-uniform selecting（DNS） encoding algorithm is proposed to solve the IC and the generation of short cycles problems. And this can reduce the probability of stopping sets occur during decoding. Second, a hybrid on the fly Gaussian elimination and belief propagation（OFG-BP） decoding algorithm is designed to reduce the decoding delay and efficiently utilize the information of stopping sets. Comparisons via Monte Carlo simulation confirm that the proposed schemes could achieve better overall decoding performances in comparison with conventional schemes.

Turbo Decoding中BCJR算法的应用及改进

并行级连卷积码 (Turbo Codes)是近年来在编码理论上的一个重大突破 ,其性能与信道容量极限的差距可小于 1d B,有着极其广阔的应用前景 ,而其独特的迭代译码方法更成了编码界和通信界讨论的热点。讨论了 Turbo Codes的编译码原理及 BCJR算法 ,比较了 SOVA,M- BCJR及T- BJCR等几种简化译码算法的性能 ,并对后两者的工程应用进行了探讨。