Construction of LDPC Codes for the Layered Decoding Algorithm

Abstract： 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,

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.

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.

Efficient Information Set Decoding Based on Genetic Algorithms

In this paper, we describe a hard-decision decoding technique based on Genetic Algorithms (HDGA), which is applicable to the general case of error correcting codes where the only known structure is given by the generating matrix G. Then we present a new soft-decision decoding based on HDGA and the Chase algorithm (SDGA). The performance of some binary and non-binary Linear Block Codes are given for HDGA and SDGA over Gaussian and Rayleigh channels. The performances show that the HDGA decoder has the same performances as the Berlekamp-Massey Algorithm (BMA) in various transmission channels. On the other hand, the performances of SDGA are equivalent to soft-decision decoding using Chase algorithm and BMA (Chase-BMA). The complexity of decoders proposed is also discussed and compared to those of other decoders.

An MMSE Decoding Algorithm without Matrix Inversion in QSTBC

The matrix inversion operation is needed in the MMSE decoding algorithm of orthogonal space-time block coding （OSTBC） proposed by Papadias and Foschini. In this paper, an minimum mean square error （MMSE） decoding algorithm without matrix inversion is proposed, by which the computational complexity can be reduced directly but the decoding performance is not affected.

Bidirectional Viterbi Decoding Algorithm for OvTDM

Overlapped time domain multiplexing(OvTDM)is an innovative encoding scheme that can obtain high spectral efficiency.However,the intentional inter-symbol interference(ISI)caused by OvTDM will make the decoding process more complex.The computational complexity of maximum likelihood sequence detection increases exponentially with the growth of spectral efficiency in OvTDM.As a consequence of high complexity,the decoding effort for a given spectral efficiency may occasionally exceed the physical limitations of the decoder,leading inevitably to buffer overflows and information erasures.In this paper,we propose a bidirectional Viterbi algorithm(BVA)based on the bidirectional sequence decoding for OvTDM.With the BVA,the decoding operation starts simultaneously from the both ends of the corresponding trellis and stops at the middle of trellis.The simulation results show that compared with Viterbi algorithm(VA),the decoding time of BVA can be reduced by about half.And the memory space of two decoders in BVA are about half of that in VA,which means that the BVA has lower memory requirements for decoder.And the decoding performance of BVA is almost the same as VA.

Noncoherent Unitary Space-Time Codes： Constellation Design and Decoding Algorithm

Two novel schemes of unitary space-time constellations generation based on zero vectors adding are proposed for the multiple-antenna communication system. In the first scheme, T2 zero row vectors are added into conventional unitary matrices directly, and the number of new unitary matrices obtained by different positions of the added zero vectors in T symbol duration is [T / T2 ] times larger than that of conventional unitary matrices. In the second scheme, one part of the required constellations is created by the first scheme and the other part is obtained by the conventional design. This means that more information bits can be transmitted by the new constellations. According to their special construction, two corresponding decoding algorithms are proposed with low complexity in flat fading channel, respectively. At the same time, the probability of miss detection is deduced for the decoding algorithms. Performance analysis and simulation results show that the proposed constellations outperform the conventional constellations and the proposed decoding algorithms are efficient and simple.

An FPGA-based LDPC decoder with optimized scale factor of NMS decoding algorithm

Considering that the hardware implementation of the normalized minimum sum(NMS)decoding algorithm for low-density parity-check(LDPC)code is difficult due to the uncertainty of scale factor,an NMS decoding algorithm with variable scale factor is proposed for the near-earth space LDPC codes(8177,7154)in the consultative committee for space data systems(CCSDS)standard.The shift characteristics of field programmable gate array(FPGA)is used to optimize the quantization data of check nodes,and finally the function of LDPC decoder is realized.The simulation and experimental results show that the designed FPGA-based LDPC decoder adopts the scaling factor in the NMS decoding algorithm to improve the decoding performance,simplify the hardware structure,accelerate the convergence speed and improve the error correction ability.

Optimal M-BCJR Turbo Decoding: The Z-MAP Algorithm

In this paper, we propose a novel idea for improvement performances of the leader M-BCJR algorithm functioning in low complexity. The basic idea consists to localize error instant possibility, and then increase the complexity around this moment. We also propose an easy and important idea for early localisation of erroneous moments. We call this new algorithm Z-MAP. The simulations show that the improvement of performances is significant. The performances of Z-MAP turbo decoding are so close to full MAP-BCJR performances. Furthermore, the complexity is the same that of the M-BCJR. So, Z-MAP is an optimal version of M-BCJR algorithm.

Low complexity joint source-channel decoding for transmission of wavelet compressed images

To utilize residual redundancy to reduce the error induced by fading channels and decrease the complexity of the field model to describe the probability structure for residual redundancy, a simplified statistical model for residual redundancy and a low complexity joint source-channel decoding（JSCD） algorithm are proposed. The complicated residual redundancy in wavelet compressed images is decomposed into several independent 1-D probability check equations composed of Markov chains and it is regarded as a natural channel code with a structure similar to the low density parity check （LDPC） code. A parallel sum-product （SP） and iterative JSCD algorithm is proposed. Simulation results show that the proposed JSCD algorithm can make full use of residual redundancy in different directions to correct errors and improve the peak signal noise ratio （PSNR） of the reconstructed image and reduce the complexity and delay of JSCD. The performance of JSCD is more robust than the traditional separated encoding system with arithmetic coding in the same data rate.

AN IMPROVED SOVA-BASED DECODING SCHEME FOR TURBO-STCM

Parallel concatenated spa ce time trellis code modulation, called Turbo STCM, can efficiently increase the coding gains of the space time codes. However, the complexity of the iterat iv e decoding restricts its application. This paper introduces a lower complex deco ding algorithm based on soft output Viterbi algorithm (SOVA) for Turbo STCM. S imulational results show that the new SOVA algorithm for the Turbo STCM outperf orms the original space time trellis code (STTC) by 4~6 dB. At the same time, compared with the Max Log MAP (maximum a posteriori) algorithm, the new scheme requires a lower complexity and approaches the performance of Turbo STCM decod ing w ith Max Log MAP.

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.

A Decoding Method Based on RNN for OvTDM

Overlapped X domain multiplexing(Ov XDM) is a promising encoding technique to obtain high spectral efficiency by utilizing Inter-Symbol Interference(ISI). However, the computational complexity of Maximum Likelihood Sequence Detection(MLSD) increases exponentially with the growth of spectral efficiency in Ov XDM, which is unbearable for practical implementations. This paper proposes an Ov TDM decoding method based on Recurrent Neural Network(RNN) to realize fast decoding of Ov TDM system, which has lower decoding complexity than the traditional fast decoding method. The paper derives the mathematical model of the Ov TDM decoder based on RNN and constructs the decoder model. And we compare the performance of the proposed decoding method with the MLSD algorithm and the Fano algorithm. It’s verified that the proposed decoding method exhibits a higher performance than the traditional fast decoding algorithm, especially for the scenarios of a high overlapped multiplexing coefficient.

Low-Complexity Detection and Decoding Scheme for LDPC-Coded MLC NAND Flash Memory

With the development of manufacture technology, the multi-level cell(MLC)technique dramatically increases the storage density of NAND flash memory. As the result,cell-to-cell interference(CCI) becomes more serious and hence causes an increase in the raw bit error rate of data stored in the cells.Recently, low-density parity-check(LDPC)codes have appeared to be a promising solution to combat the interference of MLC NAND flash memory. However, the decoding complexity of the sum-product algorithm(SPA) is extremely high. In this paper, to improve the accuracy of the log likelihood ratio(LLR) information of each bit in each NAND flash memory cell, we adopt a non-uniform detection(N-UD) which uses the average maximum mutual information to determine the value of the soft-decision reference voltages.Furthermore, with an aim to reduce the decoding complexity and improve the decoding performance, we propose a modified soft reliabilitybased iterative majority-logic decoding(MSRBI-MLGD) algorithm, which uses a non-uniform quantizer based on power function to decode LDPC codes. Simulation results show that our design can offer a desirable trade-off between the performance and complexity for high-column-weight LDPC-coded MLC NAND flash memory.

JOINT SOURCE-CHANNEL DECODING OF HUFFMAN CODES WITH LDPC CODES

In this paper, we present a Joint Source-Channel Decoding algorithm (JSCD) for Low-Density Parity Check (LDPC) codes by modifying the Sum-Product Algorithm (SPA) to account for the source redun-dancy, which results from the neighbouring Huffman coded bits. Simulations demonstrate that in the presence of source redundancy, the proposed algorithm gives better performance than the Separate Source and Channel Decoding algorithm (SSCD).

ON THE DECODING OF ALGEBRAIC GEOMETRIC CODES BASED ON FIA

Suppose C is an irreducible algebraic curve of genus g, C*(D,G) is an algebraic geometric code with designed minimum distance d* = deg(G)-2g + 2. In this paper, a decoding algorithm based on Fundamental Iterative Algorithm(FIA) is presented, also its reasonableness is proved. In fact, our decoding algorithm is a modification of the algorithm proposed by G. L. Fend and T. R. N. Rao(1993) and can correct any received words with errors not more than (d*-1)/2, whereas the complexity is only about one half as much as Feng and Rao’s. The procedure can be implemented easily by hardware or software.

A reordered first fit algorithm based novel storage scheme for parallel turbo decoder

In this paper we discuss a novel storage scheme for simultaneous memory access in parallel turbo decoder. The new scheme employs vertex coloring in graph theory. Compared to a similar method that also uses unnatural order in storage, our scheme requires 25 more memory blocks but allows a simpler configuration for variable sizes of code lengths that can be implemented on-chip. Experiment shows that for a moderate to high decoding throughput （40-100 Mbps）, the hardware cost is still affordable for 3GPP＇s （3rd generation partnership project） interleaver.

A Novel Decoder Based on Parallel Genetic Algorithms for Linear Block Codes

Genetic algorithms offer very good performances for solving large optimization problems, especially in the domain of error-correcting codes. However, they have a major drawback related to the time complexity and memory occupation when running on a uniprocessor computer. This paper proposes a parallel decoder for linear block codes, using parallel genetic algorithms (PGA). The good performance and time complexity are confirmed by theoretical study and by simulations on BCH(63,30,14) codes over both AWGN and flat Rayleigh fading channels. The simulation results show that the coding gain between parallel and single genetic algorithm is about 0.7 dB at BER = 10﹣5 with only 4 processors.

Serial Genetic Algorithm Decoder for Low Density Parity Check Codes

Genetic algorithms are successfully used for decoding some classes of error correcting codes, and offer very good performances for solving large optimization problems. This article proposes a new decoder based on Serial Genetic Algorithm Decoder (SGAD) for decoding Low Density Parity Check (LDPC) codes. The results show that the proposed algorithm gives large gains over sum-product decoder, which proves its efficiency.

PRECODING AND DECODING DESIGN FOR TWO-WAY MIMO AF MULTIPLE-RELAY SYSTEM

In this paper, a joint precoding and decoding design scheme is proposed for two-way Multiple-Input Multiple-Output (MIMO) multiple-relay system. The precoding and decoding matrices are jointly optimized based on Minimum Mean-Square-Error (MMSE) criteria under transmit power constraints. The optimization problem is solved by using a convergent iterative algorithm which in-cludes four sub-problems. It is shown that due to the difficulty of the block diagonal nature of the relay precoding matrix, sub-problem two cannot be solved with existing methods. It is then solved by converting sub-problem two into a convex optimization problem and a simplified method is proposed to reduce the computational complexity. Simulation results show that the proposed scheme can achieve lower Bit Error Rate (BER) and larger sum rate than other schemes. Furthermore, the BER and the sum rate performance can be improved by increasing the number of antennas for the same number of relays or increasing the number of relays for the same number of antennas.