Home > Advanced Turbo Coding and Rate Matching

Advanced Turbo Coding and Rate Matching

NOTE: This section is Under-Edit if necessary: Construction began on May 16, 2014 and was finished on May 17, 2014.

Turbo Coded Signaling over a Coherent Memoryless Channel: Rate Matching and the Iterative Turbo Decoder 

by Darrell A. Nolta
May 5, 2014

The AdvDCSMT1DCSS (T1) Professional (T1 Version 2) system tool now offers the capability to model and simulate Rate Matching (RM) Punctured Turbo Coded Signaling over Memoryless Channel (MLC) with Additive White Gaussian Noise (AWGN). This feature is in addition to T1 V2's capability to model and simulate Turbo Coded (TC) and Punctured Turbo Coded (PTC) Signaling over MLC.

T1 V2 provides the option with this RM Signaling feature to use Multiple Iteration Soft Input/Soft Decision Output (SISO) TC Channel Decoding using a Punctured Turbo Decoding Algorithm where two SISO 'symbol-by-symbol' Maximum a Posteriori Probability (MAP) Algorithm component decoders (DEC1 & DEC2) are serial concatenated with a feedback loop.

In addition, T1 Professional provides the option with this RM Signaling feature to model and simulate a Non-Iterative (Single Iteration) SISO PTC Channel Decoding where DEC1 and DEC2 are serial concatenated without the feedback loop.

The Rate Matching Signaling requires that a parent Turbo Code is punctured so that the Punctured Turbo Code Rate is increased. One can achieve a Punctured Rate Rp of 1/2, 2/3, 3/4, 2/5, or 3/5 for a parent TC Rate of 1/3; Rp of 1/2, 2/3, 3/4, 2/5 or 3/5 for a parent TC Rate of 1/5; and Rp of 1/2, 2/3, 3/4, 2/5, or 3/5 for a parent TC Rate of 1/7.

The incorporation of the Rate Matching Punctured Turbo Coded M-ary Signaling over an AWGN MLC feature into T1 V2 supports M > 2 Modulation Schemes (M-PSK, M-PAM, M-QAM, & M-FSK where M = 4, 8, 16, 32, and 64). M-QAM (M-ary Quadrature Amplitude Modulation) Signaling using a Square (M = 4, 16, or 64) or Non-Square (M = 8, 16, 32 or 64) Signal Vector Space can be used with a Punctured Turbo Code.

For purposes of this paper, the 'impure' Gray coded Non-Square (NS) or Non-Rectangular (NR) 16-QAM was chosen for demonstrating this new T1 feature. Consult Figure 1 for a depiction of this NR 16-QAM constellation.

A Soft Bit Metric is used by the Punctured Turbo Decoder when an M > 2 Modulation Scheme is used for signaling over an AWGN Memoryless Channel. A Demodulation Constellation DeMapper will produce a Max-Log or Log-Sum Soft Bit Metric (User Specified).

The Turbo Encoding and Turbo Decoding algorithms development in T1 V2 was aided by the study of their description in a number of important works. Consult the References section at the end of this paper for some of these key works.

Consider the Rate Matching (RM) Punctured Turbo Decoding Algorithm Bit Error Rate (BER) or Bit Error Probability Pb performance simulation results that were produced by T1 V2 that are displayed below in Figure 2 and 3 BER plots for M = 16 Modulation Scheme (16-QAM).

Each figure's BER plot displays one or more curves where a curve is constructed from the set of simulated Pb values that correspond to a set of Eb/N0 values. Each curve displays the performance behavior of a Rate Matching Punctured Turbo Coding and Iterative Decoding system example that was used for a T1 V2 simulation. Each curve's behavior can be partitioned into Eb/N0 regions called 'waterfall', 'error-floor', and 'high' as ordered by increasing Eb/N0 and not in numerical value of Eb/N0. A particular Rate Matching Punctured Turbo Coding, Modulation Scheme, Channel, and Iterative Decoding system will dictate where the 'waterfall' region will reside in the Eb/N0 domain. Note that it appears that the reviewed published BER versus Eb/N0 plots do not display their curves' 'high' Eb/N0 behavior.

Figure 2 displays the BER versus signal-to-noise ratio (SNR) Eb/N0 for RM Punctured Turbo Coded Non-Square [Non-Rectangular (NR)] 16-QAM signaling for one, three, and four iterations Max-Log-MAP RM Punctured Turbo Decoding algorithm. Figure 3 contrasts the BER for Max-Log-MAP Turbo decoding for one, three, and four iterations for the RM Punctured Turbo Coded NR 16-QAM signaling.

Note that BER results are based on the use of an Equal Probable Independent and Identically Distributed (IID) Source.

For Rate Matching Punctured Convolutional Coded NR 16-QAM Signaling, an Odenwalder [Best (Optimal)] convolutional code is used, i.e., Parent Code Rate = 1/3, Constraint Length K = 4.

For Punctured Turbo Coded 16-QAM Signaling, a Turbo Code Rate (r) = 1/3, K = 4 using an r = 1/2, K = 4 Optimum-weight Spectrum Recursive Systematic Convolutional (RSC) code is used along with a 6144-Bit QPP Interleaver.

For RM PTC NR 16-QAM signaling, the Turbo Code's r = 1/2, K = 4 RSC code was chosen because it is an Optimum-weight Spectrum RSC code and its corresponding Iterative Turbo Channel Decoder's complexity of 8 trellis states for each MAP algorithm decoder (DEC1 & DEC2)] facilitates a reasonable simulation time for demonstration purposes. For the Turbo Encoder's interleaving algorithm, the 6144-Bit Quadratic Permutation Polynomial (QPP) [f(x) = 263x + 480x2] was chosen because it is a Long Term Evolution (LTE) mobile communications interleaving algorithm candidate.

To evaluate this new T1 Professional feature of Rate Matching Punctured Turbo Coded Signaling and Iterative Turbo Channel Decoding, the modulation type M-QAM was chosen because it allows for the use of interesting signal vector spaces (constellations), i.e., Non-Square distribution of signal vectors in M-QAM 2-D signal space. The use of this constellation will result in a reduced Peak Channel Symbol Signal-to-Noise Ratio (SNR) during signaling. The 'impure' Gray Coded Non-Square (NS) 16-QAM was chosen for testing this new T1 feature.

The Non-Square constellation [or Non-Rectangular (NR)] is constructed by modifying the Square constellation by relocating each quadrant's two signal vectors (innermost and corner) to specific available locations [signal vector position near the in-phase (I) axis & signal vector position next to the quadrature-phase (Q) axis]. Each corner signal vector is rotated to the first available location that is adjacent to the in-phase (I) axis. Each innermost signal vector is moved up (Quadrant I & II) or down (Quadrant III & IV) to the first available location adjacent to the quadrature (Q) axis. And each signal vector's Bit-to-M-ary Channel Input Symbol assignment is based upon a Gray Code scheme. The 2-D positions of the signal vectors of this NR 16-QAM constellation are depicted in Figure 1.

For Punctured Convolutional or Punctured Turbo Coded 16-QAM signaling, the Puncturing process involves the punctured of one parity code bit per branch over a Puncturing Period of two branches that will result in a Punctured Turbo Code Rate of 1/2.

Note that the notation of a RSC code's Generator sequence polynomial's binary representation is right justified octal in this paper.

For the Rate Matching PCC or Rate Matching PTC simulations, the Non-Square (Non-Rectangular) 16-QAM Demodulation Constellation DeMapper is used to produce Max-Log Bit Metrics.

There are many important conclusions that can be drawn from the below displayed Iterative Turbo Code (ITC) Decoding simulated BER results. It appears that T1 is correctly modeling and simulating Rate Matching Punctured Turbo Coded Signaling over an AWGN Memoryless Channel with ITC Decoding.

Now, let us look at the Rate Matching Punctured Turbo Coded Signaling BER results as shown in Figure 2. One can clearly see the dramatic reduction in BER in the low SNR region ('waterfall') for RM PTC NR 16-QAM Signaling with Max-Log-MAP ITC Decoding (three & four Iterations) as compared to the UnCoded or RM PCC 16-QAM Signaling with VA Decoding. For the case of three iterations, we are able to achieve a BER of ~4.6x10-5 at SNR of 6.5 dB. For the case of four iterations, we are able to achieve a BER of ~7.4x10-5 at SNR of 5.6 dB.

But what is most interesting about these BER versus SNR plotted results is that one can see the BER instability in ITC Decoding (i.e., as the Eb/N0 increases and exceeds the BER minimum's Eb/N0, the BER increases) for the three and four iterations BER curves. This instability effect is an observed simulation result and not an analytical derived determination. Claude Berrou et al. in his 1993 and 1996 papers ([1], page 1069 & [8], page 1270) discloses the existence of this instability. Patrick Robertson in his 1994 paper ([2], page 1302) acknowledges the stability issue but counters the need for Berrou's correction factors. And Shu Lin and Daniel J. Costello, Jr. in their 2004 book ([14], page 839) discuss the similarity between Iterative Decoding and Negative Feedback in a control system and the possibility of divergence after converging to the correct decision or 'oscillate' between the correct and incorrect decision. This instability effect is real and may be related to the extrinsic information exchange that involves the feedback from DEC2 to DEC1.

Also, we can observe the effect of the number of iterations of the iterative decoding on BER performance in the Figure 2 BER plot. This effect belongs to the subject of the process of convergence in a suboptimal iterative decoder. One could actually cause a deterioration in BER performance when the number of iterations used exceed the number of iterations required for convergence of the decoding process., i.e., achieve the optimal (minimum) number of Information Bit Errors. It appears that one can 'over-iterate' and, thus, cause a decoding failure. This convergence decoding failure is dependent on the value of SNR that exists during the signaling process.

Note that the transmission of an Information Bit Stream involves the Turbo encoding process that divides the Information (Data) Bit Stream into a set of blocks where a block size matches the size of the Turbo Encoder Interleaver.

Thus, determination of convergence involves one block (block convergence) and then a set of blocks (global convergence).

One can clearly observe this BER instability in the ITC Decoding of RM PTC NR 16-QAM Signaling BER results as shown in Figure 3. It is interesting that the BER deterioration is worst for the four iterations curve as compared to the three iterations curve.

This BER instability and 'over-iterate' revelations illustrates the valuable utility of T1 Professional.

T1 Professional (T1 V2) now offers the Turbo Channel Coding and Turbo Channel Decoding (Iterative & Non-Iterative; based on the 'Symbol-by-Symbol' MAP algorithm) for IID and Markov Information Sources feature to the User. One can choose to puncture the Turbo Code. M-ary Signaling over an AWGN Memoryless Channel can be used where a Binary Modulation Scheme or an M > 2 Modulation Scheme (M-PSK, M-PAM, M-QAM or M-FSK) can be selected. And the User can choose the Rate Matching Punctured Turbo Coded Signaling with Iterative or Non-Iterative Turbo Decoding feature. The User via T1 V2 can get experience with these algorithms as applied to Iterative Decoding in simulated digital communication systems for Spacecraft and Mobile Communications Turbo Coding applications.

Figure 1. 'Impure Gray Coded Non-Square 16-QAM Signal Vector Space (constellation).

Figure 2. Bit Error Probability for UnCoded, Rate Matching (RM) Punctured 
          Convolutional Coded (PCC), and RM Punctured Turbo Coded (PTC) 'Impure'
          Gray Coded Non-Rectangular (NR) 16-QAM Signaling over a Coherent 
          Memoryless Channel with Additive White Gaussian Noise (AWGN):

          Equal probable Independent and Identical Distributed (IID) Source for 
          10 Million, 1 Million, and 1,001,472 Information Bits for UnCoded, RM PCC, 
          & RM PTC Gray Coded NR 16-QAM Signaling respectively over a Vector Channel;

          Parent Code Rate = 1/3, K = 4, (7,5,6,7) a Non-Recursive Convolutional Code 
          and Viterbi Algorithm Decoder using a Path Memory Length of 48 bits and 
          a squared Euclidean distance Branch Metric;

          Punctured Code (Rp = 2/4) derived from this 1/3 rate parent code for 
          Puncturing Period of 2 using the Puncturing Matrix P = [[1,0],[1,1],[0,1]];

          Rate (r) = 1/3, K = 4 Parent Turbo Code based on a r = 1/2, K = 4 (G0 = 13 
          octal, G1 = 17 octal) Recursive Systematic Convolutional component code 
          (Optimum-weight Spectrum) and a 6144-Bit QPP Turbo Encoder Interleaver;

          Punctured Turbo Code Rate = 1/2 for Puncturing Period of 2 and 
          Puncturing Matrix P = [[1,1],[1,0],[0,1]];

          'Impure' Gray Code NR 16-QAM Demodulation Constellation DeMapper Algorithm: 
          Max-Log Bit Metrics; and

          Max-Log-MAP Iterative Turbo Decoder using Systematic Channel Output as 
          input to both component decoders and Decoder Information Bit Decision is 
          based on the Sum of both decoders' log-likelihood ratios (L-values) 
          and for One Iteration, Three Iterations, and Four Iterations.

Figure 3. Bit Error Probability for Rate Matching (RM) Punctured Turbo Coded (PTC)
          'Impure' Gray Coded Non-Rectangular (NR) 16-QAM Signaling over a Coherent 
          Memoryless Channel with Additive White Gaussian Noise (AWGN):

          Equal probable Independent and Identical Distributed (IID) Source for 
          1,001,472 Information Bits for RM PTC 'Impure' Gray Coded NR 16-QAM 
          Signaling over a Vector Channel;

          Rate (r) = 1/3, K = 4 Parent Turbo Code based on a r = 1/2, K = 4 (G0 = 13 
          octal, G1 = 17 octal) Recursive Systematic Convolutional component code 
          (Optimum-weight Spectrum) and a 6144-Bit QPP Turbo Encoder Interleaver;

          Punctured Turbo Code Rate = 1/2 for Puncturing Period of 2 and 
          Puncturing Matrix P = [[1,1],[1,0],[0,1]];

          'Impure' Gray Code NR 16-QAM Demodulation Constellation DeMapper Algorithm: 
          Max-Log Bit Metrics; and

          Max-Log-MAP Iterative Turbo Decoder using Systematic Channel Output as 
          input to both component decoders and Decoder Information Bit Decision is 
          based on the Sum of both decoders' log-likelihood ratios (L-values) 
          and for One Iteration, Three Iterations, and Four Iterations.
References (Turbo Coding & Binary Modulation):

[1] Claude Berrou, Alain Glavieux, and Punya Thitimajshima, "Near Shannon Limit Error-Correcting Coding: Turbo -Codes (1)," in Proc., 1993 IEEE International Conference on Communications (Geneva, Switzerland), pp. 1064-1070, May 1993.

[2] Patrick Robertson, "Illuminating the Structure of Code and Decoder of Parallel Concatenated Recursive Systematic (Turbo) Codes," in Proc., IEEE Globecom Conference (San Francisco, CA), pp. 1296-1303, December 1994.

[3] D. Divsalar and F. Pollara, "Turbo Codes for PCS Applications," in Proc. IEEE ICC'95, Seattle, WA pp. 54-59, June 1995.

[4] Patrick Robertson, Emmanuelle Villebrun, and Peter Hoeher, "A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domain," in Proc. IEEE ICC'95, Seattle, WA, pp. 1009-1013, June 1995.

[5] Sergio Benedetto and Guido Montorsi, "Unveiling Turbo Codes: Some Results on Parallel Concatenated Coding Schemes," IEEE Transactions on Information Theory, Vol. 42, No. 2, pp. 409-428, March 1996.

[6] Joachim Hagenauer, Elke Offer, and Lutz Papke, "Iterative Decoding of Binary Block and Convolutional Codes," IEEE Transactions on Information Theory, Vol. 42, No. 2, pp. 429-445, March 1996.

[7] Sergio Benedetto and Guido Montorsi, "Design of Parallel Concatenated Convolutional Codes," IEEE Transactions on Communications, Vol. 44, No. 5, pp. 591-600, May 1996.

[8] Claude Berrou and Alain Glavieux, "Near Optimum Error Correcting Coding and Decoding: Turbo Codes," IEEE Transactions on Communications, Vol. 44, No. 10, pp. 1261-1271, October 1996.

[9] Lance C. Perez, Jan Seghers, and Daniel J. Costello, Jr., "A Distance Spectrum Interpretation of Turbo Codes," IEEE Transactions on Information Theory, Vol. 42, No. 6, pp. 1698-1709, November 1996.

[10] A.J Viterbi, A.M. Viterbi, and N.T. Sindhushayana, "Interleaved concatenated codes: New perspective on approaching the Shannon limit," in Proc., Natl. Acad. Sci. USA, Vol. 94, pp. 9525-9531, September 1997.

[11] Sergio Benedetto, Roberto Garello, and Guido Montorsi, "A Search for Good Convolutional Codes to be Used in the Construction of Turbo Codes," IEEE Transactions on Communications, Vol. 46, No. 9, pp. 1101-1105, September 1998.

[12] Omer F. Acikel and William E. Ryan, " Punctured Turbo-Codes for BPSK/QPSK Channels," IEEE Transactions on Communications, Vol. 47, No. 9, pp. 1315-1323, September 1999.

[13] Roberto Garello, Paola Pierleoni, and Sergio Benedetto, "Computing the Free Distance of Turbo Codes and Serially Concatenated Codes with Interleavers: Algorithms and Applications," IEEE Journal on Selected Areas in Communications, Vol. 19, No. 5, pp. 800-812, May 2001.

[14] Shu Lin and Daniel J. Costello, Jr., Error Control Coding: fundamentals and applications, Second Edition, Pearson Prentice Hall, Upper Saddle River, New Jersey, 2004.

[15] Jing Sun and Oscar Y. Takeshita, "Interleavers for Turbo Codes Using Permutation Polynomials over Integer Rings," IEEE Transactions on Information Theory, Vol. 51, No. 1, pp. 101-119, January 2005.

[16] Oscar Y. Takeshita, "On Maximum Contention-Free Interleavers and Permutation Polynomials over Integer Rings," IEEE Transactions on Information Theory, Vol. 52, No. 3, pp. 1249-1253, March 2006.

[17] Guang-Chong Zhu, and Fady Alajaji, "Joint Source-Channel Turbo Coding for Binary Markov Sources," IEEE Transactions on Wireless Communications, Vol. 5, No. 5, pp. 1065-1075, May 2006.

[18] Oscar Y. Takeshita, "Permutation Polynomial Interleavers: An Algebraic-Geometric Perspective," IEEE Transactions on Information Theory, Vol. 53, No. 6, pp. 2116-2132, June 2007.

[19] Yang Sun and Joseph R. Cavallaro, "Efficient hardware implementation of a highly-parallel 3GPP LTE/LTE-advance turbo decoder," INTEGRATION, the VLSI journal, Vol. 44, pp. 305-315, 2011.

References (Turbo Coding & M > 2 Modulation):

[20] Stephane Le Goff, Alain Glavieux, and Claude Berrou, "Turbo-Codes and High Spectral Efficiency Modulation," in Proc. of 1994 IEEE International Conference on Communications (New Orleans, LA), ICC '94, pp. 645-649, May 1994.

[23] Patrick Robertson and Thomas Worz, "A Novel Bandwidth Efficient Coding Scheme Employing Turbo Codes," in Proc. of 1996 IEEE International Conference on Communications (Dallas, TX), ICC '96, pp. 962-967, June 1996.

[24] Filippo Tosato and Paola Bisaglia, "Simplified Soft-Output Demapper for Binary Interleaved COFDM with Application to HIPERLAN/2," HP Technical Report HPL-2001-246, October 10, 2001; or in Proc. IEEE International Conference on Communications, 2002, ICC 2002, Vol. 2, pp. 664-668, 2002.

[25] Ramesh Pyndiah, Annie Picart, and Alain Glavieus, "Performance of Block Turbo Coded 16-QAM and 64-QAM Modulations," in Proc. of IEEE GLOBECOM '95, pp. 1039-1043, November 1995.

[26] Ramesh Pynadiah, Alain Glavieus, Annie Picart, and Sylvie Jacq, "Near Optimum Decoding of Product Codes," in Proc. of IEEE GLOBECOM '94, pp. 339-343, November - December 1994.

[27] Ephraim Zehavi, "8-PSK Trellis Codes for a Rayleigh Channel", IEEE Transactions on Communications, Vol. 40, No. 5, pp. 873-884, May 1992.

[28] Lifang Li, Dariush Divsalar, and Samuel Dolinar, "Iterative Demodulation, Demapping, and Decoding of Coded Non-Square QAM," IEEE Transactions on Communications, Vol. 53, No. 1, pp. 16-19, January 2005.

[29] Keunhyung Lee, Donghoon Kang, Hyobae Park, and Wangrok Oh, "Joint Encoding and Modulation Scheme for Binary Turbo Code and 16-QAM," The 6th International Conference on Information Technology and Applications (ICITA 2009), pp. 307-310, 2009.

      

BUY T1 Version 2 (ADVDCSMT1DCSS Professional software system tool)NOW.