The most important thing in any communication system is reliable transmission of data. To transmit the data through noisy channel, a redundancy is added before transmission which is known as channel coding. This transmitted data is decoded at the receiver with the help of soft decision decoding or hard decision decoding. Soft decision decoding can be classified as reliability based and code structure based decoding. Reliability in coding theory implies the probability of decoding the bit correctly. Most reliable bits give correct decoding output while less reliable bits are more prone to create errors. Iterative decoder accepts soft inputs-including a priori values-and delivers soft outputs that can he split into: the soft channel and a priori inputs, and the extrinsic value. The extrinsic value is used as an a priori value for the next iteration. The commonly used iterative decoder is sum product belief propagation algorithm. We are extending this analysis to the min-sum algorithm for polar codes. Using polar codes, the sum-product and min-sum algorithms are compared and simulation results are demonstrated.
The most important thing in any communication system is reliable transmission of data. To transmit the data through noisy channel, a redundancy is added before transmission which is known as channel coding. This transmitted data is decoded at the receiver with the help of soft decision decoding or hard decision decoding. Soft decision decoding can be classified as reliability based and code structure based decoding. Reliability in coding theory implies the probability of decoding the bit correctly. Most reliable bits give correct decoding output while less reliable bits are more prone to create errors. Iterative decoder accepts soft inputs-including a priori values-and delivers soft outputs that can he split into: the soft channel and a priori inputs, and the extrinsic value. The extrinsic value is used as an a priori value for the next iteration. The commonly used iterative decoder is sum product belief propagation algorithm. We are extending this analysis to the min-sum algorithm for polar codes. Using polar codes, the sum-product and min-sum algorithms are compared and simulation results are demonstrated.
Error correctiong codes (ECC) are widly used in applications to correct errors in data transmission over unreliable or noisy communication channels. Recently, two kinds of promising codes attracted lots of research interest because they provide excellent error correction performance. One is non-binary LDPC codes, and the other is polar codes. This dissertation focuses on efficient decoding algorithms and decoder design for thesetwo types of codes.Non-binary low-density parity-check (LDPC) codes have some advantages over their binary counterparts, but unfortunately their decoding complexity is a significant challenge. The iterative hard- and soft-reliability based majority-logic decoding algorithms are attractive for non-binary LDPC codes, since they involve only finite field additions and multiplications as well as integer operations and hence have significantly lower complexity than other algorithms. We propose two improvements to the majority-logic decoding algorithms. Instead of the accumulation of reliability information in the ex-isting majority-logic decoding algorithms, our first improvement is a new reliability information update. The new update not only results in better error performance and fewer iterations on average, but also further reduces computational complexity. Since existing majority-logic decoding algorithms tend to have a high error floor for codes whose parity check matrices have low column weights, our second improvement is a re-selection scheme, which leads to much lower error floors, at the expense of more finite field operations and integer operations, by identifying periodic points, re-selectingintermediate hard decisions, and changing reliability information.Polar codes are of great interests because they provably achieve the symmetric capacity of discrete memoryless channels with arbitrary input alphabet sizes an explicit construction. Most existing decoding algorithms of polar codes are based on bit-wise hard or soft decisions. We propose symbol-decision successive cancellation (SC) and successive cancellation list (SCL) decoders for polar codes, which use symbol-wise hard or soft decisions for higher throughput or better error performance. Then wepropose to use a recursive channel combination to calculate symbol-wise channel transition probabilities, which lead to symbol decisions. Our proposed recursive channel combination has lower complexity than simply combining bit-wise channel transition probabilities. The similarity between our proposed method and Arıkan's channel transformations also helps to share hardware resources between calculating bit- and symbol-wise channel transition probabilities. To reduce the complexity of the list pruning, atwo-stage list pruning network is proposed to provide a trade-off between the error performance and the complexity of the symbol-decision SCL decoder. Since memory is a significant part of SCL decoders, we also propose a pre-computation memory-saving technique to reduce memory requirement of an SCL decoder.To reduce the complexity of the recursive channel combination further, we propose an approximate ML (AML) decoding unit for SCL decoders. In particular, we investigate the distribution of frozen bits of polar codes designed for both the binary erasure and additive white Gaussian noise channels, and take advantage of the distribution to reduce the complexity of the AML decoding unit, improving the throughput-area efficiency of SCL decoders.Furthermore, to adapt to variable throughput or latency requirements which exist widely in current communication applications, a multi-mode SCL decoder with variable list sizes and parallelism is proposed. If high throughput or small latency is required, the decoder decodes multiple received words in parallel with a small list size. However, if error performance is of higher priority, the multi-mode decoder switches to a serialmode with a bigger list size. Therefore, the multi-mode SCL decoder provides a flexible tradeoff between latency, throughput and error performance at the expense of small overhead.
In this work, reliability based decoding is combined with belief propagation (BP) decoding for low-density parity check (LDPC) codes. At each iteration, the soft output values delivered by the BP algorithm are used as reliability values to perform reduced complexity soft decision decoding of the code considered. This approach allows to bridge the error performance gap between BP decoding which remains suboptimum, and maximum likelihood decoding (MLD) which is too complex to be implemented for the codes considered. A stopping criterion which reduces the average number of iterations at the expense of very little performance degradation is also proposed for this combined decoding approach. Simulations results for several Gallager LDPC codes and different set cyclic (DSC) codes of hundreds of information bits are given and elaborated.
In this paper, two iterative message passing algorithms based on belief propagation proposed for the decoding of any binary linear block code are compared. The innovation of these algorithms lies in the fact that the structure of the graph of the parity check matrix is adaptively modified to render it suitable to belief propagation decoding. The modification is done such that the least reliable bits received from the channel are leaves of the graph. These algorithms perform favorably when compared with existing hard and iterative soft decision decoding algorithms in terms of error rate while maintaining a complexity polynomial in block length. It was found that while these two algorithms are conceptually similar, their performance in terms of word error rate (as a function of signal-to-noise ratio), decoding time (average number of iterations) and the updated bit reliabilities are very different
We present novel decoding schemes for hard and soft decision decoding of block codes using the minimal weight codewords of the dual code. The decoding schemes will be described for cyclic codes where polynomials can be used, however, the modification for non-cyclic codes is possible and straight forward. The hard decision decoding calculates syndrome polynomials which are the product of the received polynomial with dual codewords. Proper cyclic shifts of these syndrome polynomials are obtained and the non-zero positions are counted componentwise for these shifts. The values of this counting are a reliability measure and can be used for locating the error and also the non-error positions. This reliability measure is the basis for various variants of hard decision decoding algorithms. Decoding schemes with iterative error reduction are possible as well as information set decoding using the inherent reliability information of the measure even if there is no reliability information from the channel. Further, we will show how reliability information from the channel can be included in order to obtain soft decision decoding schemes. We derive the relation between bit flipping, believe propagation, and majority logic decoding to the novel schemes. As examples to illustrate the functioning we use BCH and Reed-Muller codes as examples for binary codes, and RS codes for non-binary codes. Besides the Plotkin construction we recall a known result that Reed-Muller codes punctured by one position are cyclic and thus, are equivalent to special cases of BCH codes. Simulation results for hard and soft decision decoding will be given for several examples and compared with results from literature. Finally, we analyze the soft decision decoding of the Plotkin construction and derive that one of the two codes uses a 3 dB better channel (also known as channel polarization).
In this paper, reliability based decoding is combined with belief propagation (BP) decoding for low-density parity check (LDPC) codes. At each iteration, the soft output values delivered by the BP algorithm are used as reliability values to perform reduced complexity soft decision decoding of the code considered. This approach allows to bridge the error performance gap between belief propagation decoding which remains suboptimum, and maximum likelihood decoding which is too complex to be implemented for the codes considered. Trade-offs between decoding complexity and error performance are also investigated. In particular, a stopping criterion which reduces the average number of iterations at the expense of very little performance degradation is proposed for this combined decoding approach. Simulation results for several Gallager (1963, 1968) LDPC codes and different set cyclic codes of hundreds of information bits are given and elaborated.
Channel coding technique is a fundamental building block in any modern communication system to realize reliable, fast, and secure data transmission. At the same time, it is a challenging and crucial task, as the data transmission happens in a channel where noise, fading, and other impairments are present. The Low-Density Parity-Check (LDPC) codes give substantial results close to the Shannon limit when the complexity and processing delay time are unlimited. In this paper, the performance of the LDPC decoding with four algorithms was investigated. The investigated four algorithms were Belief Propagation (BP), Layered Belief Propagation (LBP), Normalized min-sum (NMS), and Offset min-sum (OMS). These algorithms were examined for code rates ranging from 1/3 to 9/10 and message block lengths (64, 512, 1024, and 5120) bits. The simulation results revealed the flexibility of these decoders in supporting these code rates and block lengths, which enables their usage in a wide range of applications and scenarios for fifth-generation (5G) wireless communication. In addition, the effect of the maximum number of decoding iterations on the error correction performance was investigated, and a gain of 5.6 dB can be obtained by using 32 decoding iterations at BER=2*10-3 instead of one decoding iteration. The results showed that the decoders performed better for longer message blocks than for short message blocks, and less power was required for transmitting longer messages. Finally, the comparison results of their performance in terms of bit error rate (BER) under the same conditions showed a gain of 0.8 dB using LBP at BER= 10-5 compared with the NMS decoding algorithm.