Comments on “A New Parity-Check Stopping Criterion for Turbo Decoding”

Yuejun Wei, Yuhang Yang, Lili Wei, , and Wen Chen, Manuscript received March 16, 2012. The associate editor coordinating the review of this letter and approving it for publication was A. Burr.The authors are with the Department of Electronic Engineering, Shanghai Jiao Tong University, Shanghai, 200240, China (e-mail: {yjwei; yhyang; liliwei; wenchen}@sjtu.edu.cn).This work is supported by the National 973 Project 2012CB316106, 2009CB824904, and by NSF China 60972031 and 61161130529.

Abstract

A parity-check stopping (PCS) criterion for turbo decoding is proposed in [1], which shows its priority compared with the stopping criteria of Sign Change Ratio (SCR), Sign Difference Ratio (SDR), Cross Entropy (CE) and improved CE-based (Yu) method. But another well-known simple stopping criterion named Hard-Decision-Aided (HDA) criterion has not been compared in [1]. In this letter, through analysis we show that using max-log-MAP algorithm, PCS is equivalent to HDA; while simulations demonstrate that using log-MAP algorithm, PCS has nearly the same performance as HDA.

Index Terms:

Parity-check criterion (PCS), hard-decision-aided (HDA), block error rate (BLER), iteration number.

I Introduction

A parity-check stopping (PCS) scheme for iterative turbo decoding is proposed in [1], where each soft-input and soft-output (SISO) decoder outputs both the estimated systematic bits and parity bits. The systematic bits from one SISO decoder are interleaved and encoded with the constituent encoder, then the parity bits from the encoder are compared with the parity bits from another SISO decoder. If the two sets of parity bits are matched bit by bit, the iterative decoding stops. From the simulation results, the PCS has a smaller average number of iterations compared with the stopping criteria of sign change ratio (SCR), sign difference ratio (SDR), cross entropy (CE) and an improved CE-based (Yu) methods.

Another well-known stopping criterion named hard-decision-aided (HDA) has been proposed in [2], which compares decisions from the same SISO on successive full-iterations. An improved HDA (IHDA) was proposed in [3] which requires less storage than HDA with similar performance in terms of bit error rate (BER) and average number of iterations. A general HDA approach was first introduced in [4]. This HDA approach compares hard decisions of the systematic bits between SISO1 and SISO2, and can stop the iterative decoding after either SISO, which is currently the best HDA approach. Analysis and simulation results in [5] show that the general HDA has very good performance with enhanced max-log-MAP algorithm (i.e., with scaled extrinsic information feedback).

However, the PCS criterion in [1] has not been compared with the HDA criterion. In this paper, we analyze and compare between PCS and the general HDA criteria, under both max-log-MAP and log-MAP algorithms. We show that, using max-log-MAP algorithm, the PCS criterion is equivalent to the HDA criterion; while using log-MAP algorithm, simulations demonstrate that both criteria have almost the same performance in terms of average number of iterations and block error rate (BLER).

Refer to caption — Figure 1: Turbo decoding of the systematic bits and the parity bits.

II Comparison Between PCS and HDA Criteria

In the PCS scheme, each SISO decoder outputs log-likelihood ratio (LLR) (as shown in Fig. 1) of the systematic bits $s_{k}$ and the parity bits $p_{k}$ , which can be expressed as follows,

$\displaystyle{L}(s_{k})$	$\displaystyle=$	$\displaystyle\ln\left(\sum_{s^{\prime},s,s_{k}=1}{\alpha_{k-1}(s^{\prime})\gamma_{k}(s^{\prime},s)\beta_{k}(s)}\right)$
		$\displaystyle-\ln\left(\sum_{s^{\prime},s,s_{k}=-1}{\alpha_{k-1}(s^{\prime})\gamma_{k}(s^{\prime},s)\beta_{k}(s)}\right),$
$\displaystyle{L}(p_{k})$	$\displaystyle=$	$\displaystyle\ln\left(\sum_{s^{\prime},s,p_{k}=1}{\alpha_{k-1}(s^{\prime})\gamma_{k}(s^{\prime},s)\beta_{k}(s)}\right)$	(1)
		$\displaystyle-\ln\left(\sum_{s^{\prime},s,p_{k}=-1}{\alpha_{k-1}(s^{\prime})\gamma_{k}(s^{\prime},s)\beta_{k}(s)}\right),$	(1)

where $\alpha$ , $\beta$ and $\gamma$ denote the forward recursive, backward recursive and branch transition probabilities, respectively. For max-log-MAP decoding, we can rewrite (II) as:

$\displaystyle{L}(s_{k})$	$\displaystyle=$	$\displaystyle\max_{s^{\prime},s,s_{k}=1}{A_{k-1}(s^{\prime})\Gamma_{k}(s^{\prime},s)B_{k}(s)}$
		$\displaystyle-\max_{s^{\prime},s,s_{k}=-1}{A_{k-1}(s^{\prime})\Gamma_{k}(s^{\prime},s)B_{k}(s)},$
$\displaystyle{L}(p_{k})$	$\displaystyle=$	$\displaystyle\max_{s^{\prime},s,p_{k}=1}{A_{k-1}(s^{\prime})\Gamma_{k}(s^{\prime},s)B_{k}(s)}$	(2)
		$\displaystyle-\max_{s^{\prime},s,p_{k}=-1}{A_{k-1}(s^{\prime})\Gamma_{k}(s^{\prime},s)B_{k}(s)},$	(2)

where $A$ , $B$ and $\Gamma$ are logarithms of $\alpha$ , $\beta$ and $\gamma$ , respectively. Then the hard decisions (HD) of $s_{k}$ and $p_{k}$ are based on the sign of $L(s_{k})$ and $L(p_{k})$ respectively:

	$\displaystyle\hat{s}_{k}=1,\;\mbox{if}\,\,L(s_{k})>0;\;\mbox{else}\,\,\hat{s}_{k}=0,$
	$\displaystyle\hat{p}_{k}=1,\;\mbox{if}\,\,L(p_{k})>0;\;\mbox{else}\,\,\hat{p}_{k}=0.$		(3)

II-A Max-log-MAP

It has been proved in [6] that, the max-log-MAP algorithm is equivalent to the soft-output Viterbi algorithm (SOVA), and the max-log-MAP algorithm makes the same hard decisions as the Viterbi algorithm (assuming no tied path metrics). In the decoding process, the max-log-MAP looks at two paths per step in the trellis, the best with bit zero and the best with bit one, and outputs the difference of the log-likelihoods of the two paths.

From step to step, one of these paths may change, but one will always be the maximum-likelihood (ML) path. That means, for the max-log-MAP decoding, the hard decision of the output always comes from the ML path because the ML path always has the largest path metrics (again, assuming no tied path metrics). From (1) and (2), we can see that, the decoding processes are quite similar for the systematic bits and parity bits. The difference is the path set of bit zero and the path set of one. However, in max-log-MAP decoding, the output of hard decision bits always come from the ML path, which is valid for both systematic bits and parity bits. Since there is only one ML path in the trellis (without considering the situation of equal path metrics), $\hat{s}_{k}$ and $\hat{p}_{k}$ must come from the same path in the trellis. In the PCS scheme, there are two parity-check flags to stop the iteration, as shown in Fig. 2:

(a)

$\hat{S}_{1}$ of the $i$ -th iteration is interleaved and encoded with the 2nd recursive systematic convolutional encoder (RSC2), and then compared with $\hat{P}_{2}$ . If the two sequences are totally matched, the iteration is terminated.
(b)

$\hat{S}_{2}$ of the $i$ -th iteration is de-interleaved and encoded with RSC1, and then compared with $\hat{P}_{1}$ . If the two sequences are totally matched, the iteration is terminated.

The process of (a) and (b) are similar. For convenience, we take (a) at $i$ -th iteration as an example to explain the equivalence between the PCS and the HDA criteria. As described in the above, for SISO2 decoder, the systematic bits $\hat{S}_{2}$ and the parity bits $\hat{P}_{2}$ are in the same ML path in the encoding trellis. So it is easy to deduce that $\hat{P}_{2}$ is also the encoded result of $\hat{S}_{2}$ , with the encoder of RSC2. As we know, the RSC encoding is a one-to-one mapping process (assuming a rate 1/2 RSC code), which means that one information sequence can only give rise to one unique parity sequence, and one parity sequence can only arise from one unique information sequence. So if $\hat{P}^{\prime}_{2}$ is the same as $\hat{P}_{2}$ , $\hat{S}^{\prime}_{1}$ must be the same as $\hat{S}_{2}$ . On the other hand, if $\hat{S}^{\prime}_{1}$ is the same as $\hat{S}_{2}$ , after encoding with RSC2, they must get the same parity bits. So the PCS criterion is equivalent to comparing $\hat{S}^{\prime}_{1}$ and $\hat{S}_{2}$ , which is actually the HDA criterion shown in Fig. 3. Similar to the proof of (a), it’s easy to prove that (b) is also equivalent to the HDA criterion.

II-B Log-MAP

Unlike the max-log-MAP and SOVA algorithms which only look at two paths per step, the log-MAP algorithm always takes all paths into calculation, but splits them into two sets (s=1, s=0), which may change from step to step. The information bits output from the log-MAP decoder do not certainly constitute a whole path in the trellis. Thus we cannot get a certain relationship between the systematic bits and parity bits output from a log-MAP decoder. This means that $\hat{P}_{1}$ and $\hat{P}_{2}$ are not certainly the encoding results of $\hat{S}_{1}$ and $\hat{S}_{2}$ respectively. However, since log-MAP algorithm and max-log-MAP with a proper scaling factor on the extrinsic information have similar performance [4, 7], we expect that using log-MAP decoding, the PCS has similar performance with HDA in most scenarios in terms of average iteration number and block error rate. We will perform simulations to compare the two criteria using both max-log-MAP and log-MAP in the next section.

III Simulation Results

Simulation studies are performed with the rate 1/3 turbo code in Universal Mobile Terrestrial Systems (UMTS) [8] in additive white Gaussian noise (AWGN) channel with binary phase shift keying (BPSK) modulation. The cyclic redundancy check (CRC) stopping scheme with 24-bit CRC is simulated as the baseline, in which the CRC is checked using the hard decisions of systematic bits after each SISO decoder. The maximum number of decoding iterations is set to 8 for all simulation cases.

Due to the simplification and approximation in calculating LLRs, the max-log-MAP is suboptimal and yields an inferior soft output than the log-MAP algorithm. However, the quality of the max-log-MAP algorithm can be improved by using an extrinsic information feedback, referred to as enhanced max-log-MAP in [4], and s-max-log-MAP in [7]. With a proper scaling factor, e.g. $0.75$ , the performance of s-max-log-MAP algorithm is quite close to log-MAP algorithm. In this simulation, we use the max-log-MAP with an extrinsic scaling factor of $0.75$ and the standard log-MAP algorithms. Of course, the extrinsic information is not scaled for making the decisions.

The path ambiguity (tied path metrics) problem was analyzed in [9, 10], and it may affect the BER and BLER performance of HDA early-stopped turbo decoding with finite quantization, especially with coarser quantization. When a soft output is equal to zero, which means that there is a “tie” for the best bit decision at that time, then the hard decision on this bit is ambiguous and can be either ‘1’ or ‘0’. In this letter, we do not permit early stopping on the current half-iteration if there exists any soft output for hard decision that is exactly zero, which is the same as the solution proposed in [9, 10].

The simulation results are shown in Fig. 4 - Fig. 7. From the simulation results, we can see that, for both information length of 990 and 5000, the PCS criterion has the same performance as HDA criterion in terms of block error rate and average number of iterations for max-log-MAP algorithm. With log-MAP decoding, two criteria also have nearly the same performance. Comparing with the CRC stopping criterion, both PCS and HDA criteria have the same block error rate but need more average number of iterations. Since the HDA criterion only need to compare the information bits, it does not need to check with the parity bits or re-encode the systematic bits, therefore HDA is simpler than PCS.

To make the comparisons above as easy as possible, the 24 bits of overhead required for implementing the CRC stopping rule were just considered part of the information payload. Properly accounting for the reduction in code rate with the 24-bit CRC present requires that the simulation results with CRC stopping be shifted to the right by 10*log10(k/(k-24)) dB, where k is the nominal information block length without the 24-bit CRC. This means that the results for k=990 should be shifted right by about 0.11 dB, and the results for k=5000 should be shifted right by about 0.02 dB. With these shifts included, it can be seen that CRC stopping actually performs worse than the other stopping schemes. However, as shown in [5, 9, 10], the performance for the HDA and PCS schemes may start to degrade at lower block error rates with log-MAP decoding.

IV Conclusions

In this letter, we analyze and compare the PCS with the HDA stopping criteria. Through analysis we show that using max-log-MAP decoding, the two criteria are equivalent; using log-MAP decoding, simulations demonstrate that they have nearly the same performance in terms of average iteration number and block error rate. Since the HDA criterion only compares the systematic bits from two constitute decoders, which does not need to check with the parity bits and re-encode the systematic bits, it is simpler than the PCS criterion.

V Acknowledgement

The authors would like to thank the anonymous reviewers for their valuable comments and suggestions.

References

[1] Z. Wu, M. Peng, and W. Wang, “A New Parity-Check Stopping Criterion for Turbo Decoding,” IEEE Commun. Lett., vol. 12, no. 4, pp. 304-306, Apr. 2008.
[2] R. Y. Shao, M. Fossorier, and S. Lin, “Two Simple Stopping Criteria for Iterative Decoding”, Proceedings of the 1998 International Symposium on Information Theory, MIT, Cambridge, MA, USA, pp. 279, Aug. 1998.
[3] T. Ngatched and F. Takawira, “Simple stopping criterion for turbo decoding,” Electron. Lett., vol. 37, pp. 1350-351, Oct. 2001.
[4] K. Gracie, S. Crozier, and A. Hunt, “Performance of a Low-Complexity Turbo Decoder with a Simple Early Stopping Criterion Implemented on a SHARC Processor,” Proceedings of the 6th International Mobile Satellite Conference (IMSC ’99), Ottawa, Ontario, Canada, pp. 281-286, Jun. 1999.
[5] K. Gracie, S. Crozier, and P. Guinand, “Performance of an MLSE-based Early Stopping Technique for Turbo Codes”, Proceedings of the 60th IEEE Vehicular Technology Conference 2004 - Fall (VTC 2004 - Fall), Los Angeles, California, USA, Sept. 2004.
[6] M. P. C. Fossorier, F. Burkert, S. Lin and J. Hagenauer, “On the Equivalence Between SOVA and Max-Log-MAP Decodings,” IEEE Commun. Lett., vol. 2, no. 5, May 1998.
[7] J. Vogt and A. Finger, “Improving the max-log-MAP turbo decoder,” Electron. Lett., vol. 36, no. 23, pp. 1937-1939, Aug. 2000.
[8] 3GPP TS 25.212 v8.5.0, “Channel coding and multiplexing,” Mar. 2009.
[9] K. Gracie, A. Hunt, S. Crozier and P. Guinand, “MLSE-Based Early Stopping for Turbo Codes - Finite Quantization Effects”, Proceedings of the 2005 Canadian Workshop on Information Theory (CWIT 2005), Montr al, Quebec, Canada, Jun. 2005.
[10] K. Gracie, A. Hunt, and S. Crozier, “Performance of Turbo Codes using MLSE-Based Early Stopping and Path Ambiguity Checking for Inputs Quantized to 4 Bits”, 4th International Symposium on Turbo Codes & Related Topics, Munich, Germany, Apr. 2006.