International Workshop on Signal Design and its Applications in Communications

Sum-product decoding of convolutional codes

Toshiyuki Shohon, Yuuichi Ogawa, Haruo Ogiwara

Published Oct 1, 2009• 5 citations

Abstract

This article proposes two methods to improve the sum-product soft-in/soft-out decoding performance of convolutional codes. The first method is to transform a parity check equation in such a way as to remove cycles of length four in a Tanner graph of a convolutional code, and performs sum-product algorithm (SPA) with the transformed parity check equation. This method improves the performance of (7,5)8convolutional code (CC1). However, for (45,73)8convolutional code (CC2), the method does not effect. The second proposed method is to use a higher order parity check equation in comparison with a normal parity check equation for SPA decoding. This method improves the performance for both convolutional codes (CC1, CC2). The performance is close to that by BCJR algorithm and it is less complex than BCJR algorithm.

DOI: 10.1109/iwsda.2009.5346439

Related papers

Sum-product decoding of BCH codes

Haruo Ogiwara, Kyouhei Shimamura, Toshiyuki Shohon

This paper proposes methods to improve soft-input and soft-output decoding performance of BCH codes by sum-product algorithm (SPA). A method to remove cycles of length four (RmFC) in the Tanner graph has been proposed. However, the RmFC can not realize good decoding performance for BCH codes which have more than one error correcting capability. To overcome this problem, this paper proposes two methods. One is to use a parity check matrix of the echelon canonical form as the starting check matrix of RmFC. The other is to use a parity check matrix that is concatenation (ConC) of multiple parity check matrices. For BCH(31,11,11) code, SPA with ConC realizes Eb/N03.8dB better than the original SPA, and 3.1dB better than the SPA with only RmFC at bit error rate 10−5. The decoding complexity is 0.08 times of that of Chase-2 decoding.

International Symposium on Turbo Codes and Iterative Information ProcessingSep 1, 20082 citations

Sum-Product Decoding of BCH Codes

Haruo Ogiwara, K. SHIMAMURA, Toshiyuki Shohon

This paper proposes methods to improve soft-input and soft-output decoding performance of BCH codes by sum-product algorithm (SPA). A method to remove cycles of length four (RmFC) in the Tanner graph has been proposed. However, the RmFC can not realize good decoding performance for BCH codes which have more than one error correcting capability. To overcome this problem, this paper proposes two methods. One is to use a parity check matrix of the echelon canonical form as the starting check matrix of RmFC. The other is to use a parity check matrix that is concatenation (ConC) of multiple parity check matrices. For BCH(31,11,11) code, SPA with ConC realizes Eb/No 3.7dB better at bit error rate 10-5 than the original SPA, and 3.1dB better than the SPA with only RmFC.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesOct 1, 20083 citations

An efficient decoding algorithm for cycle-free convolutional codes and its applications

Jing Li, Krishna R. Narayanan, C.N. Georghlades

This paper proposes an efficient graph-based sum-product algorithm for decoding 1/(1+D/sup n/) code, whose Tanner (1981) graph is cycle-free. A rigorous proof is given which shows the proposed algorithm is equivalent to the MAP decoding implementing the BCJR algorithm, but with a lower complexity magnitude. The paper presents an explicit example which confirms the claim that the sum-product algorithm is optimal on cycle-free graphs. A parallel realization is then discussed and shown to resemble low density parity check (LDPC) decoding. The paper further proposes a min-sum algorithm which is equivalent to the max-log-MAP algorithm. Prospective applications which can take advantage of the proposed decoding algorithms are discussed and simulations are provided.

GlobecomNov 13, 200211 citations

Modified sum-product algorithms for decoding low-density parity-check codes

Stylianos Papaharalabos, P. Sweeney, B.G. Evans +4 more

The authors deal with the sum–product algorithm (SPA) based on the hyperbolic tangent (tanh) rule when it is applied for decoding low-density parity-check (LDPC) codes. Motivated by the finding that, because of the large number of multiplications required by the algorithm, an overflow in the decoder may occur, two novel modifications of the tanh function (and its inverse) are proposed. By means of computer simulations, both methods are evaluated using random-based LDPC codes with binary phase shift keying (BPSK) signals transmitted over the additive white Gaussian noise (AWGN) channel. It is shown that the proposed modifications improve the bit error rate (BER) performance up to 1 dB with respect to the conventional SPA. These results have also shown that the error floor is removed at BER lower than 10−6. Furthermore, two novel approximations are presented to reduce the computational complexity of the tanh function (and its inverse), based on either a piecewise linear function or a quantisation table. It is shown that the proposed approximations can slightly improve the BER performance (up to 0.13 dB) in the former case, whereas small BER performance degradation is observed (<0.25 dB) in the latter case. In both cases, however, the decoding complexity is reduced significantly.

IET CommunicationsJun 1, 200734 citations

An improved low-complexity sum-product decoding algorithm for low-density parity-check codes

Michaelraj Kingston Roberts, Ramesh Jayabalan

In this paper, an improved low-complexity sum-product decoding algorithm is presented for low-density parity-check (LDPC) codes. In the proposed algorithm, reduction in computational complexity is achieved by utilizing fast Fourier transform (FFT) with time shift in the check node process. The improvement in the decoding performance is achieved by utilizing an optimized integer constant in the variable node process. Simulation results show that the proposed algorithm achieves an overall coding gain improvement ranging from 0.04 to 0.46 dB. Moreover, when compared with the sum-product algorithm (SPA), the proposed decoding algorithm can achieve a reduction of 42%–67% of the total number of arithmetic operations required for the decoding process.

Frontiers of Information Technology & Electronic EngineeringJun 1, 201512 citations

An improved implementation of sum-product algorithm for LDPC decoder

Zhou Wang, Bin Wu, Tianchun Ye

An improved decoding algorithm for low-density parity-check (LDPC) codes is presented. By taking advantages of the first-term Taylor’s series multiple expansion to approximate the correction term of the Jacobian logarithm used in LLR-SPA (log-likelihood ratio sum-product algorithm), we propose an algorithm which significantly simplifies the check node update computation of the optimal LLR-SPA. Besides, the parameter δ is introduced to determine suitable expansion points. The simulation result shows that the proposed method with ten expansion points when δ is set to 0.01 has almost identical performance compared with ideal SPA algorithm and outperforms both the min-sum algorithm (MS), the offset min-sum algorithm (OMS) and the normalised min-sum algorithm (NMS). The architecture of proposed method is also presented for implementation, which has reduced computational complexity and is feasible for hardware implementation.

IEICE Electronics ExpressJan 1, 20193 citations