Printer Friendly

Turbo codes for pulse position modulation: applying BCJR algorithm on PPM signals.


Turbo encoding constitutes a very powerful forward error correcting technique that is capable of achieving very high performance gains over the Additive White Gaussian Noise (AWGN) channels. At the transmitter side, Recursive Systematic Convolutional (RSC) encoders are implemented along with interleavers that are deployed to provide the above encoders with different independent versions of the information bits. The encoded bits are then often punctured in order to improve the code rate. At the receiver side, demodulators that are capable of generating soft decisions about the received data are often implemented. The soft output of the demodulator is then passed to the turbo decoders that use this soft output as a metric to run an iterative decoding procedure. Usually, there are two turbo decoders that exchange the generated soft metrics between each other. This exchange of information is done in an iterative manner to achieve low bit error rates (BER). Finally, the BCJR algorithm (Bahl, Cocke, Jelinek, Raviv) is often implemented for generating soft outputs and decoding the applied convolutional codes [1], [2], [3], [4].

The turbo encoding/decoding strategy that is based on the above main building blocks was studied extensively in the wide literature of digital communications. Turbo codes were applied mainly with binary phase shift keying (BPSK) where the simple mapping and direct link between the binary 0's and 1's on one hand and the positive and negative signals on the other hand results in simple transceiver structures. Most of the research effort was steered in this direction and BPSK constituted, by far, the most conventional modulation scheme that was associated with turbo codes [5]-[7]. In this context, the research effort was directed towards soft-input soft-output iterative decoding algorithms for different types of turbo codes, such as block turbo codes BTC [8], [9]. Designing interleavers for Turbo Codes is also an important research direction in the field of turbo codes [10]-[12].

Recently, various contributions considered the problem of turbo encoding/decoding with QAM signals where different solutions showed how QAM signals can make use of turbo codes to improve the BER [13], [14]. These proposed solutions can be seen as extending the turbo coding techniques from the one-dimensional BPSK signal sets to the two-dimensional QAM constellations. Pursuing the research effort in this direction, we further present a simple and efficient solution for extending the principle of turbo encoding/decoding to the multidimensional PPM signal sets. Note that PPM is attracting a growing attention as a strong candidate modulation scheme for free-space optical (FSO) communications [15] and ultra-wideband (UWB) communications [16]. Given the very high temporal resolution resulting from the very large bandwidths occupied by optical and UWB signals, it is often much simpler to control the positions of the transmitted modulated signals rather than controlling their amplitudes and/or phases. Note that various contributions considered turbo codes with binary PPM in the context of UWB communications [17]-[20]. However, these proposed solutions are exclusive to two-dimensional binary PPM and cannot be extended to M-ary PPM. In fact, the two binary PPM signals [1 0] and [0 1] can be easily mapped to the +1 and -1 signals of the BPSK signal set by subtracting the value of the signal received in the first slot from that received in the second slot.

The major contribution of this paper consists of extending turbo codes to multi-dimensional PPM where we use the Log Likelihood Ratio LLR to carry on the soft demodulation. The paper goes through the proposed design by explaining the different components to be implemented at the transmitter and receiver sides. In other words, the turbo encoders are presented first and then the interleaver is introduced. After covering the encoding part, the PPM channel modulator is discussed. At the receiver side we have the PPM demodulator that generates soft outputs fed into the turbo decoders. Finally, we have the BCJR algorithm used to undergo the iterative turbo decoding. The results of the simulations are presented at the end of the paper.


As stated before, much research effort is done to maximize the benefits of turbo codes applied on BPSK signals. The advantages of working with BPSK signals can be summarized in these three point; 1) At the transmitter side the encoded bits directly map to BPSK signal, such that; binary zero is mapped to -1 and binary one is mapped to +1 or the other way around. 2) At receiver side a hard decision can be made simply based on the arithmetic sign of the received signal. 3) BCJR algorithm, which is based on the Log Likelihood Ratio, is highly adapted to the BPSK signals.

These three points prompted us to introduce additional layers to the already existing design in order to extend turbo codes to multidimensional PPM. At the transmitter side we have a simple modulator that generates M-ary PPM signals. At the receiver side the demodulation of the received signal is achieved through a PPM signal demodulator that generates soft BPSK-like signal that can undergo turbo decoding as suggested in past research papers. This paper aims at abstracting the modulation/demodulation layer from other layers; turbo encoding, interleaving, turbo decoding, etc. As such, further optimization of the proposed design can be accomplished by simply improving the demodulator at the receiver side keeping all other components intact.

In this section, we go through the proposed design in a sequential manner. At the transmitter side turbo encoders are introduced first. At the encoding stage, the crucial role of the inter-leaver is highlighted. Data encoding is followed by pulse position channel modulation. At the receiver side, before going through the traditional turbo decoding process using the BCJR algorithm, pulse position demodulation comes into play to generate the desired BPSK-like soft decision.

2.1 Turbo Encoders

Turbo codes are generated using two convolutional encoders that are IIR (infinite impulse response) Finite State Sequential Machines (FSSM). These two encoders are known as recursive systematic convolutional (RSC) encoders that are concatenated in parallel. They receive the same input message however in different order and generate the corresponding parity bits. As such, each input message bit is encoded twice, which results in a code rate of 1/3. However, we puncture the two parity bits to improve the code rate from 1/3 to 1/2. For even position message bits, the parity bits from encoder I are taken. On the other hand, for odd position message bits, the parity bits from encoder II are taken. Note that we should not puncture the systematic bits because it results in BER performance loss [1] [2]. Therefore, upon puncturing we end up with a code rate of 1/2. The trellis encoders used make the source model a discrete hidden Markov source. The joint probability of the symbol sequences is given by,

p(x) = p([X.sub.1]). [[PI].sub.(j=2[right arrow]n)] [P.sub.j]([X.sub.j]/[X.sub.j-1]), (1)

X = [X.sup.n.sub.1] = {[X.sub.1], [X.sub.2], ..., [X.sub.n]}, where the source transition probabilities are

[P.sub.j]([X.sub.j]/[X.sub.j-1]) = p([X.sub.j-1], [X.sub.j])/p([X.sub.j-1]) (2)


As state before, the reordering of input message before entering the second RSC encoder is significant. The process of reordering or interleaving input message renders the two parity streams from encoder I and encoder II sufficiently independent, which enhances the performance of the iterative decoding at the receiver side. The degree of independence is strongly associated with the type of interleaver used. In this paper, we used 10 by 10 block interleavers that are simply matrix structures. In this matrix structure data are input along the rows and read along the columns [1] [2]. A 6 by 6 block interleaver, for example, can use a 6x6 matrix as shown below. The data bits will be read from the entries as (1, 7, 13, 19, 25, 31, 2, 8, 14, 20, 26, 32, 3, 9, 15, 21, 27, 33, 4, 10, 16, 22, 28, 34, 5, 11, 17, 23, 29, 35, 6, 12, 18, 24, 30, 36). Note that block interleavers do not have to be square matrices.


The turbo encoding process, interleaving of input message and parity bit puncturing are depicted in Fig. 1.

2.2 Pulse Position Modulation

After we generate the parity bits we have the channel modulation part. In the case of BPSK signals we have no problem because zeros are mapped to '-1' and ones are mapped to However, given that PPM is attracting a growing attention for the reasons briefly mentioned in the introduction, we propose modulating the encoded data into PPM symbols and not simply sending them through the communication channel as BPSK signals.

Pulse position modulation is based on sending N message bits by transmitting a single pulse in one of the M = [2.sup.N] possible M-ary PPM symbol slots. As such, we should adopt a strategy to map the encoded bits to PPM symbols. A similar effort is done in [13], where the encoded bits are mapped to gray-coded QAM signals. In other words, the encoded bits specify the coordinates of the QAM-symbol generated on the gray code QAM map shown in Fig. 2. The puncturing process yields two bits, a systematic bit and a parity bit, at every time instant. Therefore, two time instants are required to indicate both the abscissa and the ordinate on the mentioned map.


A similar yet a simpler approach is proposed to undergo pulse position modulation. Upon puncturing, the two encoded bits are capable of uniquely specifying, as shown in Table 1, four channel slots, which results in having 4-ary PPM symbols.

In case of having non-punctured three encoded bits, the symbols generated are 8-ary PPM symbols as shown in Table 2. Note that for the two mentioned cases, the PPM symbols are generated at every time instance. In other words, each PPM symbol corresponds to one systematic or message bit. Therefore, the modulation can take place every n time instants resulting in [2.sup.2n]-ary and [2.sup.3n]-ary PPM symbols for punctured and non-punctured turbo encoded bits, respectively.

2.3 Pulse Position Demodulation

Turbo decoding at the receiver side, as shown in Fig. 3, requires that the channel demodulator generate soft decision about the transmitted data. The paper proposes a pulse position demodulation strategy based on two important facts: 1) State transitions on the trellis diagram are based on the message bits entering the turbo encoders. In other words, the iterative turbo decoding, irrespective of the decoding algorithm used (whether BCJR algorithm or Soft Output Viterbi Algorithm (SOVA) or any other algorithm), cannot be operated directly on the received PPM symbols. 2) BCJR algorithm is highly compatible with polar bits, because it is based on the log likelihood ratio.


Based on the mentioned reasons, a soft demodulation technique is proposed, which is based on evaluating the LLR of the transmitted data. Similar technique is used in [13] to generate soft decision for gray-coded QAM symbols.

The paper presents the demodulation equation for the 4-PPM received symbol. However, the equation extends to M-ary pulse position modulation. Note that M-ary PPM symbols have a pulse in one of the M slots.

The PPM symbols are transmitted over AWGN channel. Therefore, if the transmitted value is x then,


where z is the received value and [E.sub.b]/[[sigma].sup.2]/2 is the signal to noise ratio SNR.

Denote by [z.sub.i] the received value in the ith slot of the PPM signal. Moreover, the demodulation of a 4-PPM symbol must evaluate two LLR's for [b.sub.1] and [b.sub.0] (recall Table 1.). Table 3 illustrates the stated ideas. Accordingly,


Moreover, the log likelihood ratio of the encoded bit is as follows,


Applying Bayes' Theorem gives,


Note that equation is (6) is valid because the PPM symbols are equiprobable.

(4) and (6) result in,

LLR ([b.sub.i]) =


Note that equation (7) has a positive value if [b.sub.i] is more likely to be equal to 1 and a negative value otherwise. Moreover, the magnitude of the calculated value represents the degree of confidence of the likely bit value. The calculated quantity, therefore, specifies the bit metrics of the transmitted data. As a result, the LLR values generated by the demodulator can pass to the turbo decoders that can deal with them as if they were BPSK signals.

The complexity of the above equation is high. For this reason, MAX Log Likelihood ratio can be used instead [20]. This method approximates (7) by considering


We can easily extend the soft demodulation technique to M-ary PPM symbols. For instance, if we do not puncture the encoded data, as discussed in subsection 2.2, we end up having three bits for each systematic bit. These three bits result in 8-ary PPM symbols. Therefore, at the receiver side the demodulator generates soft decisions based on Table 4. Accordingly,


As in equation (4), each pulse slot of the 8-PPM signal is independent of the remaining slots.

The same soft demodulation technique can be extended for M-ary PPM symbols.

2.4 Turbo Decoders & BCJR Algorithm

The PPM demodulator, as explained in the previous subsection, calculates bit metrics using the Log Likelihood Ratio. In the case of BPSK signals, the received data is directly fed into the turbo decoders. Turbo decoding involves communicating soft decisions between the two decoders present. In other words, decoder I receives the message bits and the corresponding parity bits (generated by the encoder I) and generates an extrinsic information about the systematic bits. The extrinsic information is then passed to decoder II after being interleaved. Decoder II uses this interleaved extrinsic information as a priori information together with the systematic information and the corresponding parity bits (generated by the encoder II) to generate its own extrinsic information [1]-[3]. This extrinsic information is then de-interleaved and passed back to decoder I. This process constitutes one iteration. However, when using a soft output demodulator before starting turbo decoding, as it is the case here in this paper, the decoder I has a priori information about the transmitted data during the first turbo decoding cycle. Therefore, we can consider that PPM demodulation itself constitutes an iteration that generates bit metrics fed into turbo decoder I.

The process of decoding can undergo several iterations. Each additional iteration improves the BER until a certain limit is reached. After this limit further iterations will not introduce much improvement in BER; thus, a hard decision is made and decoding terminates. As we said before, the decoding algorithm is known as the BCJR algorithm [1]. Note that the BCJR decoders will deal with the soft output of the PPM symbol demodulator as if they were BPSK symbols transmitted through AWGN channel. Such an approach does not give optimal results, because the iterative BCJR decoding algorithm is used to generate bit metric for BPSK symbols.

In BPSK modulation only the extrinsic information is communicated between the two turbo decoders. However, when using PPM signals both the systematic information and the extrinsic information must be exchanged between the two decoders. This is because both the parity bit and the systematic bit are used to specify the pulse position.


Figures 4, 5, 6, and 7 show the Matlab simulation results for BPSK, QAM, 4-PPM, and 8-PPM signals, respectively. They show the Bit Error Rate with respect to the Signal to Noise Ratios that are in dB. The figures show that the turbo codes are improving the BER; however, there is limit after which further iterations become useless. Another important observation is that the first turbo decoding iteration improves the BER more for PPM symbols, however, further decoding iterations applied on PPM symbols result in insignificant improvement. In other words, the waterfall region in both figures 6 and 7 is steeper (from the first iteration) than that of figures 4 and 5. Moreover, if we compare figures 6 and 7 it may seem that not puncturing the transmitted data is giving better results.





However, the power of the pulse in the 8-PPM symbols of the nonpunctured bits is the same as that of 4PPM symbol. If we are to make a more realistic comparison, we should consider the energy of the transmitted pulse for the 8-PPM symbol 1.5 times that of 4PPM symbol. This is because 3 bits are mapped to 8-PPM symbols and not 2 bits as it is the case for 4-PPM symbols. This gives an additional 1.76 dB for the SNR of the 8-PPM symbols, which is a great improvement especially in the waterfall region of the BER curve. In other words, for a BER of 10-2 5.2 dB of SNR is required for the first decoding iteration of soft demodulated 4-PPM symbols. On the other hand, for the same BER 5.6-1.76 = 3.84 dB of SNR is required for the first decoding iteration of soft demodulated 8-PPM symbols.


We investigated the BER improvement achieved when applying turbo codes on PPM signals. We have shown how pulse position modulation of turbo encoded bits is achieved. Moreover, the paper proposed a PPM demodulator technique that is capable of making a soft decision about the received bits. The soft decision is then passed to the turbo decoders that run the BCJR algorithm to do an iterative decoding of the received data. The results obtained illustrate the efficiency of the proposed design. However, we can see that only the first iterations are capable of improving the BER; further iterations do not improve much. Further improvements can be made in two fields: 1) the iterative turbo decoding algorithm can be modified to adjust with the soft demodulation technique proposed, 2) improving the soft demodulation technique to improve the performance of the turbo BCJR decoders.


[1.] J. C. Moreira and P. G. Farrell (2006). Essentials of Error-Control Coding. London: John Wiley & Sons Ltd.

[2.] P. Sweeney (2002). Error Control Coding: From Theory to Practice. London: John Wiley & Sons Ltd.

[3.] G. Colavolpe, G. Ferrari, and R. Raheli, "Extrinsic Info in Iterative Decoding: A Unified View," IEEE Trans. Commun., vol. 49, no. 12, pp. 2088-2094, December 2001.

[4.] H. R. Sadjadpour, "Maximum A Posteriori Decoding Algorithms for Turbo Codes," Proceedings of SPIE, vol. 4045, pp. 73-83, July 2000.

[5.] B. Unal, "Performance of Turbo-Codes in Time-Synchronous BPSK/CDMA Systems and Rayleigh Fading Channels," Vehicular Technology Conference, i999. VTC i999-Fall. IEEE VTS 50th, vol. 3, pp. 1575-1579, 1999.

[6.] O. Acikel, and W. Ryan, "Punctured turbo-codes for BPSKQPSK channels," IEEE Trans. Commun., vol. 47, no. 9, pp. 1315-1323, September 1999.

[7.] C. Kojima, and T. Saba, "Improvement of BPSK space-time turbo code with full antenna diversity," IEEE International Conference, Commun., vol. 3, pp. 1625-1629, 2002.

[8.] M. Lalam, K. Amis, D. Leroux, D. Feng, and J. Yuan, "An improved iterative decoding algorithm for block turbo codes," IEEE International Symposium, Information Theory, pp. 2403-2407, July 2006.

[9.] S. Dave, K. Junghwan, and S. Kwatra, "An efficient decoding algorithm for block turbo codes," IEEE Trans. Commun., vol. 49, no. 1, pp. 41-46, January 2001.

[10.] W. Feng, J. Yuan, and B. Vucetic, "A code-matched interleaver design for turbo codes," IEEE Trans. Commun., vol. 50, no. 6, pp. 926-937, June 2002.

[11.] F. Daneshgaran, and M. Mondin, "Design of Inter-leaver for Turbo Codes: Iterative Interleaver Growth Algorithms of Polynomial Complexity," IEEE Trans. Information Theory, vol. 45, no. 6, 1845-1859, September 1999.

[12.] J. Sun, and O. Takeshita, "Design of interleavers for turbo codes: iterative interleaver growth algorithms of polynomial complexity," IEEE Trans. Information Theory, vol. 51, no. 1, 101-119, January 2005.

[13.] K. Kim, K. Hyun, C. W. Yu, Y. O. Park, D. Yoon, and S. K. Park, "General Log-Likelihood Ratio Expression and Its Implementation Algorithm for Gray-Coded QAM Signals," ETRI journal, vol. 28, no. 3, pp. 291 300, June 2006.

[14.] S. Oh, A. Fayziyev, J. Cha, and J. Ha, "A New Efficient 16-QAM Mapping Approach for Iterative Receiver using Turbo Codes over SISO Channel," Proc. i0th International Conference On Advanced Communication Technology, ICACT2008, pp. 421-423, February 2008.

[15.] K. Kiasaleh, "Performance of APD-Based, PPM Free-Space Optical Communication Systems in Atmospheric Turbulence," IEEE Trans. Commun., vol. 53, no. 9, 1455-1461, September 2005.

[16.] B. Ho, and N. Beaulieu, "Precise Bit Error Rate of TH PPM UWB Systems in the presence of Multiple Access Interference," IEEE Conf UWB and tech., pp. 106-110, November 2003.

[17.] J. Park, and J. Kim, "Performance of double-binary turbo coded TH-PPM UWB systems with multiple receive antennas," Advanced Comm. Tech. International Conference, pp. 1687-1690, February 2009.

[18.] E. Kim, and J. Kim, "Performance Analysis of UWB Systems with Non-Binary Turbo Code in Multi-User Environments," Advanced Comm. Tech. iith International Conference, pp. 1954-1958, February 2009.

[19.] E. Kim, and J. Kim, "Iterative Decoding for Space Time Block coded PPM-TH UWB Systems," IEEE International Symposium on Industrial Electronics, pp. 795-799, July 2009

[20.] K. Cho and D. Yoon, "On the General BER Expression of One- and Two-Dimensional Amplitude Modulations," IEEE Trans. Commun., vol. 50, no. 7, pp. 1074-1080, July 2002.

Serj Haddad and Chadi Abou-Rjeily

Lebanese American University

PO. Box, 36, Byblos, Lebanon,
Table 1. 4-ary PPM symbol

[b.sub.1][b.sub.0]       PPM symbol

00                          0001
01                          0010
10                          0100
11                          1000

Table 2. 8-ary PPM symbols

[b.sub.2][b.sub.1][b.sub.0]       PPM symbol

000                                00000001
001                                00000010
010                                00000100
011                                00001000
100                                00010000
101                                00100000
110                                01000000
111                                10000000

Table 3.

       Encoded    Possible
       bit (bi)   transmitted
                  4-ppm symbol (A)

                  [A.sub.3]   [A.sub.2]

i=0    0          0           0
                  0           1

       1          0           0
                  1           0

i=i    0          0           0
                  0           0

       1          0           1
                  1           0

       Encoded    Possible                     Received
       bit (bi)   transmitted                   values
                  4-ppm symbol (A)                (z)

                  [A.sub.1]   [A.sub.0]

i=0    0          0           1           [z.sub.3] [z.sub.2]
                  0           0           [z.sub.1] [z.sub.0]

       1          1           0           [z.sub.3] [z.sub.2]
                  0           0           [z.sub.1] [z.sub.0]

i=i    0          0           1           [z.sub.3] [z.sub.2]
                  1           0           [z.sub.1] [z.sub.0]

       1          0           0           [z.sub.3] [z.sub.2]
                  0           0           [z.sub.1] [z.sub.0]

Table 4.

      Encoded   Possible transmitted 8-ppm symbol (A)
      bit (bj
                [A.sub.7]   [A.sub.6]   [A.sub.5]   [A.sub.4]

i=0      0      0               0           0           0
                0               0           0           0
                0               0           0           0
                0               0           0           0

         1      0               0           0           1
                0               0           1           0
                0               1           0           0
                1               0           0           0

i=i      0      0               0           0           0
                0               0           0           0
                0               0           0           1
                0               0           1           0

         1      0               0           0           0
                0               0           0           0
                0               1           0           0
                1               0           0           0

i=2      0      0               0           0           0
                0               0           0           0
                0               0           0           1
                0               1           0           0

         1      0               0           0           0
                0               0           0           0
                0               0           1           0
                1               0           0           0

      Possible transmitted 8-ppm symbol (A)            Received
                                                      values (z)
      [A.sub.3]   [A.sub.2]   [A.sub.1]   [A.sub.0]

i=0       0           0           0           1        Z.sub.7]
          0           0           1           0        Z.sub.6]
          0           1           0           0        Z.sub.4]
          1           0           0           0        Z.sub.4]
          0           0           0           0        Z.sub.2]
          0           0           0           0        Z.sub.1]
          0           0           0           0        Z.sub.0]
          0           0           0           0

i=i       0           0           0           1
          0           0           1           0
          0           0           0           0
          0           0           0           0

          0           1           0           0
          1           0           0           0
          0           0           0           0
          0           0           0           0

i=2       0           0           0           1
          0           1           0           0
          0           0           0           0
          0           0           0           0

          0           0           1           0
          1           0           0           0
          0           0           0           0
          0           0           0           0
COPYRIGHT 2012 The Society of Digital Information and Wireless Communications
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2012 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Haddad, Serj; Abou-Rjeily, Chadi
Publication:International Journal of New Computer Architectures and Their Applications
Date:Apr 1, 2012
Previous Article:Timeliness measurement model: a mathematical approach for measuring the timeliness of handheld application usage.
Next Article:Continuous functioning of soft system bus based centralized persistent computing system.

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters