IEEE Transactions on Information Theory

A low-weight trellis-based iterative soft-decision decoding algorithm for binary linear block codes

Takuya Koumoto, T. Takata, Tadao Kasami, Shu Hwa Lin

Published Mar 1, 1999• 13 citations

Abstract

This paper presents a new low-weight trellis-based soft-decision iterative decoding algorithm for binary linear block codes. The algorithm is devised based on a set of optimality conditions and the generation of a sequence of candidate codewords for an optimality test. The initial candidate codeword is generated by a simple decoding method. The subsequent candidate codewords, if needed, are generated by a chain of low-weight trellis searches, one at a time. Each search is conducted through a low-weight trellis diagram centered around the latest candidate codeword and results in an improvement over the previous candidate codewords that have been already tested. This improvement is then used as the next candidate codeword for a test of optimality. The decoding iteration stops whenever a candidate codeword is found to satisfy a sufficient condition on optimality or the latest low-weight trellis search results in a repetition of a previously generated candidate codeword. A divide-and-conquer technique is also presented for codes that are not spanned by their minimum-weight codewords. The proposed decoding algorithm has been applied to some well-known codes of lengths 48, 64, and 128. Simulation results show that the proposed algorithm achieves either practically optimal error performance for the example codes of length 48 and 64 or near optimal error performance for the (128, 29, 32) RM code with a significant reduction in computational decoding complexity.

DOI: 10.1109/18.749023

Related papers

An Iterative Soft-Decision Decoding Algorithm

Shu Wen Lin, Takuya Koumoto, Toyoo Takata +1 more

This paper presents a new minimum-weight trellis-based soft-decision iterative decoding algorithm for binary linear block codes. Simulation results for the RM(64,22), EBCH(64,24), RM(64,42) and EBCH(64,45) codes show that the proposed decoding algorithm achieves practically (or near) optimal error performance with significant reduction in decoding computational complexity. The average number of search iterations is also small even for low signal-to-noise ratio.

Jul 10, 19967 citations

A low-weight trellis based decoding algorithm for binary linear block codes with application to generalized irregular low-density codes

Telex M. N. Ngatched, Fambirai Takawira

In this paper, reduced-complexity trellis-based soft-input soft-output (SISO) decoding of linear block codes is considered. A new low-weight subtrellis based SISO decoding algorithm for linear block code to achieve near optimal error performance with a significant reduction in decoding complexity is presented. The proposed scheme is suitable for iterative decoding of linear block codes when used as component codes in compound or concatenated coding schemes. It has the following important features. An initial candidate codeword is first generated by a simple decoding method that guarantees a successful decoding. A low-weight subtrellis diagram centered around the candidate codeword is constructed. The maximum a posteriori probability (MAP) algorithm is then applied to the subtrellis. The generated extrinsic information is then used as a priori information to improve the generation of a candidate codeword for the next stage of iteration. Simulation results in the case of the newly introduced generalized irregular low-density (GILD) codes indicate that the proposed algorithm achieves practically optimal performance with a significant reduction in decoding complexity.

GlobecomFeb 22, 20050 citations

Study on Iterative Soft-Decision Decoding Algorithms for Binary Linear Block Codes

卓也甲本

For iterative soft-decision decoding algorithms for binary linear block codes, error performance and computational complexity are very important factors.In this thesis, suÆcient conditions of the optimality of decoded codeword and a suÆcient condition which is used for ruling-out some useless iterations of bounded distance decoding which reduces the computational complexity of iterative soft-decision decoding algorithms are shown.New iterative soft-decision decoding algorithms which uses the suÆcient conditions of the optimality of decoded codeword to achievegood error performance with small computational complexity are also shown.First, the suÆcient conditions are derived based on: (1) partial knowledge of the distance pro le of the code, and (2) previously generated candidate codewords.When the numberof previously generated candidate codewords is greater than 1, the conditions presented here are less stringent than those derived by Taipale and Pursley [4] and Kaneko et.al.[5].The condition based on three previously generated candidate codewords is the rst such s u Æ c i e n t condition that has ever been derived.It is shown by computer simulation that these suÆcient condions reduce the computational complexity of iterative decoding algorithms without degradation of error performance.Second, a suÆcient condition to rule-out some useless test error patterns is derived.In an iterative decoding algorithm, such as Chase Type-II decoding algorithm[2] and its improved versions, candidate codewords for a received vector are generated

Mar 24, 19991 citation

On iterative soft-decision decoding of linear binary block codes and product codes

R. Lucas, Martin Bossert, Markus Breitbach

Iterative decoding methods have gained interest, initiated by the results of the so-called "turbo" codes. The theoretical description of this decoding, however, seems to be difficult. Therefore, we study the iterative decoding of block codes. First, we discuss the iterative decoding algorithms developed by Gallager (1962), Battail et al. (1979), and Hagenauer et al. (1996). Based on their results, we propose a decoding algorithm which only uses parity check vectors of minimum weight. We give the relation of this iterative decoding to one-step majority-logic decoding, and interpret it as gradient optimization. It is shown that the used parity check set defines the region where the iterative decoding decides on a particular codeword. We make plausible that, in almost all cases, the iterative decoding converges to a codeword after some iterations. We derive a computationally efficient implementation using the minimal trellis representing the used parity check set. Simulations illustrate that our algorithm gives results close to soft decision maximum likelihood (SDML) decoding for many code classes like BCH codes. Reed-Muller codes, quadratic residue codes, double circulant codes, and cyclic finite geometry codes. We also present simulation results for product codes and parallel concatenated codes based on block codes.

IEEE Journal on Selected Areas in CommunicationsJan 1, 1998100 citations

An efficient information set algorithm for soft-decision decoding of linear block codes

Dulte José de Barros, B.G. Dorsch

This paper presents an approach to soft-decision decoding for a (n, k) binary linear block code. This approach achieves near-optimal to optimal performance for any signal-to-noise ratio value. The proposed decoding is based on the reordering of the received symbols according to their reliability measure and can be applied to any binary linear code. The basic idea is to generate a sequence of codewords such that there will be a high probability that the next codeword is closer to the received vector. In this algorithm the information provided by the soft-decisions is used to generate information sets utilized in decoding. A fast procedure checks whether a given set of k positions is an information set. A sequence of codewords is reconstructed using a sequence of information sets. Each codeword reconstructed is compared with the received word and the closest one is selected. Hence, the decoding algorithm is an iterative procedure designed to enhance the performance of the usual soft-decision decoding, since with each iteration of the procedure, real vectors successively closer to the received vector are examined. A high performance stop rule is utilized to reduce the number of generated information sets, stopping the decoding process when a codeword is closest to the received sequence.

IEEE International Symposium on Information Theory (ISIT)Nov 22, 20021 citation

Soft-decision decoding using punctured codes

Ilya I. Dumer

Let a q-ary linear (n,k)-code be used over a memoryless channel. We design a soft-decision decoding algorithm that tries to locate a few most probable error patterns on a shorter length s /spl isin/ [k,n]. First, we take s cyclically consecutive positions starting from any initial point. Then we cut the subinterval of length s into two parts and examine T most plausible error patterns on either part. To obtain codewords of a punctured (s,k)-code, we try to match the syndromes of both parts. Finally, the designed codewords of an (s,k)-code are re-encoded to find the most probable codeword on the full length n. For any long linear code, the decoding error probability of this algorithm can be made arbitrarily close to the probability of its maximum-likelihood (ML) decoding given sufficiently large T. By optimizing s, we prove that this near-ML decoding can be achieved by using only T/spl ap/q/sup (n-k)k/(n+k)/ error patterns. For most long linear codes, this optimization also gives about T re-encoded codewords. As a result, we obtain the lowest complexity order of q/sup (n-k)k/(n+k)/ known to date for near-ML decoding. For codes of rate 1/2, the new bound grows as a cubic root of the general trellis complexity q/sup min{n-k,k}/. For short blocks of length 63, the algorithm reduces the complexity of the trellis design by a few decimal orders.

IEEE Transactions on Information TheoryJan 1, 200116 citations