Novel modified min-sum decoding algorithm for low-density parity-check codes

The problem of improving the performance of min-sum decoding of low-density parity-check(LDPC)codes is considered in this paper.Based on rain-sum algorithm,a novel modified min-sum decoding algorithm for LDPC codes is proposed.The proposed algorithm modifies the variable node message in the iteration process by averaging the new message and previous message if their signs are different.Compared with the standard min-sum algorithm,the modification is achieved with only a small increase in complexity,but significantly improves decoding performance for both regular and irregular LDPC codes.Simulation results show that the performance of our modified decoding algorithm is very close to that of the standard sum-produet algorithm for moderate length LDPC codes.     

Modified time-domain algorithm for decoding Reed-Solomon codes

A technique for reducing the number of inversions in the time-domain decoding algorithm based on an algebraic decoder (Blahut's decoder) is introduced. It is proved that the modified algorithm is equivalent to the original one. The modified algorithm can be used in the universal Reed-Solomon decoder to decrease complexity     

Two-dimensional correction for min-sum decoding of irregular LDPC codes

Two-dimensional (2-D) correction schemes are proposed to improve the performance of conventional min-sum (MS) decoding of irregular low density parity check codes. An iterative procedure based on parallel differential optimization is presented to obtain the optimal 2-D factors. Both density evolution analysis and simulation show that the proposed method provides a comparable performance as belief propagation (BP) decoding while requiring less complexity. Interestingly, the new method exhibits a lower error floor than that of BP decoding. With respect to conventional MS and 1-D normalized MS decodings, the 2-D normalized MS offers a better performance. The 2-D offset MS decoding exhibits a similar behavior.     

On implementation of min-sum algorithm and its modifications for decoding low-density Parity-check (LDPC) codes

The effects of clipping and quantization on the performance of the min-sum algorithm for the decoding of low-density parity-check (LDPC) codes at short and intermediate block lengths are studied. It is shown that in many cases, only four quantization bits suffice to obtain close to ideal performance over a wide range of signal-to-noise ratios. Moreover, we propose modifications to the min-sum algorithm that improve the performance by a few tenths of a decibel with just a small increase in decoding complexity. A quantized version of these modified algorithms is also studied. It is shown that, when optimized, modified quantized min-sum algorithms perform very close to, and in some cases even slightly outperform, the ideal belief-propagation algorithm at observed error rates.     

MLC闪存的最小和译码算法研究

随着多级单元(Multi-Level Cell,MLC)闪存存储密度的增加,单元间干扰(Cell-toCell Interference,CCI)成为影响NAND闪存可靠性的主要噪声。针对这种情况,在深入分析MLC闪存信道模型和CCI噪声模型的基础上,利用MLC阈值电压的均匀感知策略获取闪存页中每比特的对数似然比(Log-Likelihood Ratio,LLR)信息,提出了一种MLC型NAND闪存的最小和译码算法。仿真结果表明,在MLC闪存信道下,该方法既可保证闪存单元可靠性,又具有较短闪存单元的读取时间,从而实现了译码复杂度和性能间的良好折衷。     

一种改进的无线光通信LDPC码译码算法

针对无线光通信中低密度奇偶校验码(LDPC)置信传播(BP)译码算法复杂度高及置信度振荡造成译码错误等缺点,基于对数BP算法提出了一种改进的译码算法。改进的译码算法在校验节点运算时,判断输入到校验节点消息的最小值与某个门限的大小,根据比较结果,分别用消息最小值或若干个最小值进行运算,在损失很少性能的情况下降低了运算复杂度;同时在比特节点采用振荡抵消处理运算,提高了算法的性能增益。最后在对数正态分布湍流信道模型下,分别对比特充分交织和交织深度为16的情况进行了仿真实验。仿真结果表明,改进的译码算法与BP算法相比,大幅度降低了计算复杂度,而且译码性能有一定的优势,收敛速度损失很少;而相对于最小和算法,改进的算法虽然译码复杂度有所增加,但误码率性能有明显的优势,并且收敛速度也优于最小和算法。因此,改进的译码算法是无线光通信中LDPC码译码算法复杂度和性能之间一个较好的折中处理方案。     

CS-FSCL decoding algorithm of polar codes based on critical sets

In order to reduce the number of redundant candidate codewords generated by the fast successive cancellation list (FSCL) decoding algorithm for polar codes, a simplified FSCL decoding algorithm based on critical sets (CS-FSCL) of polar codes is proposed. The algorithm utilizes the number of information bits belonging to the CS in the special nodes, such as Rate-1 node, repetition (REP) node and single-parity-check (SPC) node, to constrain the number of the path splitting and avoid the generation of unnecessary candidate codewords, and thus the latency and computational complexity are reduced. Besides, the algorithm only flips the bits corresponding to the smaller log-likelihood ratio (LLR) values to generate the sub-maximum likelihood (sub-ML) decoding codewords and ensure the decoding performance. Simulation results show that for polar codes with the code length of 1 024, the code rates of 1/4, 1/2 and 3/4, the proposed CS-FSCL algorithm, compared with the conventional FSCL decoding algorithm, can achieve the same decoding performance, but reduce the latency and computational complexity at different list sizes. Specifically, under the list size of L=8, the code rates of R=1/2 and R=1/4, the latency is reduced by 33% and 13% and the computational complexity is reduced by 55% and 50%, respectively.     

Adaptive offset min-sum algorithm for low-density parity check codes

An improvement is presented to the offset min-sum decoding algorithm for low-density parity check codes. The proposed algorithm introduces a more efficient adjustment for check-node update computation in view of different minimum values. According to the optimal correction factor of normalized min-sum algorithm, we can determine the adaptive offset item. The improved algorithm achieves a noticeable performance gain with only a modest increase in computation complexity.     

Modified minimum-weight decoding for Reed-Solomon codes

The authors describe an improvement to the minimum-weight decoding (MWD) algorithm for Reed-Solomon (RS) codes. The modification improves the probability of the MWD algorithm `trapping' the error pattern by squaring each of the terms in the received codeword resulting in a transformation which changes the order of the symbols while maintaining the cyclic properties of the codeword. The results of computer simulations are presented which show that the modified decoder provides an improvement in error performance of ~1 dB over the conventional technique with no increase in decoder complexity. The results show that the modified technique achieves an error performance close to that of maximum-likelihood algorithms with ~1/6 the complexity     

Simplified SCL decoding algorithm of polar codes based on critical sets

In order to reduce the high complexity of the successive cancellation list (SCL) algorithm for polar codes, a simplified SCL decoding algorithm based on critical sets (CS-SCL decoding algorithm) is proposed. The algorithm firstly constructs the critical sets according to the channel characteristics of the polar codes as well as comprehensively considering both the minimum Hamming weight (MHW) of the information bits and the channel reliability. The information bits within the critical sets and the path splitting are still performed by the SCL decoding algorithm while the information bits outside the critical sets are directly performed by the hard decision. Thus, the number of path ordering, copying, and deleting can be reduced during decoding. Furthermore, the computational complexity of the SCL decoding can also be reduced. Simulation results demonstrate that the decoding complexity of the proposed CS-SCL decoding algorithm, compared with the conventional SCL decoding algorithm, is reduced by at least 70%, while compared with the simplified SCL (PS-SS-SCL) algorithm which constructs the critical set with the first and second information bits of the Rate-1 nodes, its decoding complexity can also be reduced. Moreover, the loss of the error correction performance for the proposed CS-SCL decoding algorithm is minor. Therefore, the proposed CS-SCL algorithm is effective and can provide a reasonable tradeoff between the decoding performance and complexity for the decoding algorithm of polar codes.     

极化码的多比特译码算法研究

针对极化码的连续消除列表（successive cancellation list,SCL）译码算法的高时延问题,提出了基于对数似然比的多比特SCL（multi-bit SCL,MSCL）译码算法,可以在一个判决时刻同时译出多个码字比特,在不损失译码性能的前提下,将译码时延由3N-2个时钟降为4N/M-2个时钟,相比于现有的多比特SCL译码算法,MSCL译码算法具有更低的路径度量值计算复杂度。为了降低循环冗余校验（cyclical redundancy check, CRC）辅助的SCL（CRC aided SCL,CA-SCL）译码算法的译码时延以及存储空间,提出了分段CRC辅助的MSCL（segmented CRC-aided MSCL,SCA-MSCL）译码算法,并提出了分段信息码字长度修正算法,来保证在信息位索引集A不变的前提下,实现每一分段结尾处对应的信息位索引能够被M整除。SCA-MSCL算法可以借助多个CRC判决来尽可能早地输出译码码字,从而减少译码器的存储空间以及译码时延。     

Dual-CRC polar codes and dual-SCFlip decoding algorithm for cell search in 5G system

Polar codes become the coding scheme for control channels of enhanced mobile broadband (eMBB) scenarios in the fifth generation (5G) communication system due to their excellent decoding performance. For the cell search procedure in 5G system, some common information bits ( CIBs) are transmitted in consecutive synchronization signal blocks ( SSBs). In this paper, a dual-cyclic redundancy check ( dual-CRC) aided encoding scheme is proposed, and the corresponding dual-successive cancellation flip ( dual-SCFlip) algorithm is given to further improve the performance of polar codes in the low signal-to-noise ratio ( SNR) environment. In dual-CRC aided encoding structure, the information bits of polar codes in different transmission blocks add cyclic redundancy check (CRC) sequences respectively according to CIBs and different information bits (DIBs). The structure enlarges the size of CIBs to improve the block error ratio ( BLER) performance of the system. The dual-SCFlip decoder can perform bit flip immediately once CIBs is decoded completely, and then decode DIBs or terminate decoding in advance according to the CRC result, which reduces the delay of decoding and mitigates the error propagation effect. Simulation results show that the dual-CRC aided encoding scheme and dual-SCFlip decoder have significant performance improvement compared to other existing schemes with low SNR.     

Fast decoding algorithm for RS codes

The singularity of the syndrome matrix is used to determine the error locations. After each error location has been ascertained, the syndrome values are calculated by an iteration method and the orders of the syndrome matrix are reduced by one. With the syndrome values of iteration, the error values are easily evaluated     

An improved AS-SCLF decoding algorithm of polar codes based on the assigned set

An improved successive cancellation list bit-flip based on assigned set (AS-SCLF) decoding algorithm is proposed to solve the problems that the successive decoding of the successive cancellation (SC) decoder has error propagation and the path extension of the successive cancellation list (SCL) decoder has the decision errors in the traditional cyclic redundancy check aided successive cancellation list (CA-SCL) decoding algorithm. The proposed algorithm constructs the AS firstly. The construction criterion is to use the Gaussian approximation principle to estimate the reliabilities of the polar subchannel and the error probabilities of the bits under SC decoding, and the normalized beliefs of the bits in actual decoding are obtained through the path metric under CA-SCL decoding, thus the error bits containing the SC state are identified and sorted in ascending order of the reliability. Then the SCLF decoding is performed. When the CA-SCL decoding fails for the first time, the decision results on the path of the SC state in the AS are exchanged. The simulation results show that compared with the CA-SCL decoding algorithm, the SCLF decoding algorithm based on the critical set and the decision post-processing decoding algorithm, the improved AS-SCLF decoding algorithm can improve the gain of about 0.29 dB, 0.22 dB and 0.1 dB respectively at the block error rate (BLER) of 10-4 and reduce the number of decoding at the low signal-to-noise ratio (SNR), thus the computational complexity is also reduced.     

Efficient algorithm for decoding layered space-time codes

Layered space-time codes have been designed to exploit the capacity advantage of multiple antenna systems in Rayleigh fading environments. A new efficient decoding algorithm based on QR decomposition is presented, which requires only a fraction of the computational effort compared with the standard decoding algorithm requiring the multiple calculation of the pseudo inverse of the channel matrix     

Improved Log-MAP decoding algorithm for turbo-like codes

In this letter, a new method for decoding turbo-like codes is proposed to simplify the hardware implementation of Log-MAP algorithm. In our method, the multivariable Jacobian logarithm in Log-MAP algorithm is actually concatenated by recursive 1D Jacobian logarithm units. Two new approximations of Log-MAP algorithm based on these 1D units are then presented, which have good approximated accuracy and is simple for hardware implementation. We further suggest a novel decoding scheme that its complexity is near the Max-Log-MAP while the performance is close to the Log-MAP algorithm.     

A decoding algorithm for finite-geometry LDPC codes

In this paper, we develop a new low-complexity algorithm to decode low-density parity-check (LDPC) codes. The developments are oriented specifically toward low-cost, yet effective, decoding of (high-rate) finite-geometry (FG) LDPC codes. The decoding procedure updates iteratively the hard-decision received vector in search of a valid codeword in the vector space. Only one bit is changed in each iteration, and the bit-selection criterion combines the number of failed checks and the reliability of the received bits. Prior knowledge of the signal amplitude and noise power is not required. An optional mechanism to avoid infinite loops in the search is also proposed. Our studies show that the algorithm achieves an appealing tradeoff between performance and complexity for FG-LDPC codes.     

Investigation into decoding algorithm for turbo codes

An investigation into the turbo decoder is presented. It was carried out to determine whether the decoded bit sequence constitutes a (at least) local maximum in the likelihood between possible codewords in the composite code trellis. The answer was obtained experimentally using a modified iterative turbo decoder. Results show that the turbo decoder does not necessarily lead to a maximum likelihood sequence estimator being realised for the composite code. Moreover, finding a closer code in a Euclidean distance sense only degrades the bit error rate of the system     

Turbo码的Taylor-Log_MAP译码算法

以Turbo码基本理论和算法为基础,依据无线信息传输的实际要求和Taylor级数的基本原理,提出了一种Turbo码的Taylor-Log-MAP高效译码算法。该算法对基本的Log-MAP算法中K运算利用Taylor级数进行展开,针对实际的信道需求对展开式进行截断,实现了Turbo码的最佳译码。与传统的对数域最大后验概率译码算法相比,该算法基本保持了优良的译码性能,同时避免了复杂的对数运算,减小了运算量。仿真结果表明,与现有的RS码性能相比,使用Turbo码可以获取5 dB的信噪比增益。     

量子稳定子码的概率译码

为了提高量子稳定子码的译码速率,提出了一种基于校验矩阵的量子概率译码算法。通过选择具有最小量子权重的算子作为差错算子来减少译码出错概率,通过预先构造量子标准阵列来缩短译码时间。与已有的量子最大似然译码算法相比,该算法对简并码和非简并码采用统一的译码方式,从而提高了简并码的译码可靠性。此外,算法不需要预先寻找差错算子对应的向量空间的基,因此算法复杂度更小。