New Controlled State-Expansion Sequence Estimation for TCM

New Controlled State-Expansion Sequence Estimation for TCM

* Niranjan. B. S. , **Vanaja Shivakumar

*Dept. of Electronics and Communication Engg., BMSCE, Bangalore, India

** Department of Electronics and Communication Engg., Bangalore, India

Abstract

We developed a new decoding strategy, namely, Controlled State-Expansion Sequence Estimation (CSESE) for Trellis Coded Modulation (TCM) schemes. TCM is a power efficient and bandwidth efficient coded modulation scheme [14,15], finds many advanced communication applications. Invention of TCM schemes initiated the era of development of bandwidth efficient coded modulation schemes. There is renewed interest for the invention of robust and efficient decoding strategies as well. The optimum decoding strategy for TCM schemes in the presence of Additive White Gaussian Noise (AWGN) is the Maximum Likelihood Sequence Estimation (MLSE)[12,14,15,18]. For the implementation of MLSE Soft output Viterbi algorithm is used. The complexity requirement of MLSE prohibits its use for bandlimited ISI channels practically. Later developments in the research arena emphasized on the development of sub-optimum decoding strategies for TCM schemes [1,17,21,22,25].

The new strategy we have developed, namely CSESE, is a controlled state-expansion sequence estimation approach emphasized on expansion of states of the trellis structure being processed, based on the decision parameters of the algorithm. Simulation results depicts that it is a faster approach. The number of states processed during each iteration varies with some of the coefficients which define the optimality of the algorithm.

1. Introduction

   Over the decades, advancement in digital communication technology and ever increasing demand for faster and reliable data transmission stimulated the research for newer inventions. Trellis Coded Modulation (TCM) is an integrated coded modulation approach for high rate digital data transmission. Invention of TCM schemes motivated the researchers for the development of

   Reduced State Sequence Estimation (RSSE) is one of the sub-optimum approaches for TCM schemes, provides symmetric distribution of states for the reduced trellis structures [20,21]. It finds many wireless communication applications.

   The new decoding strategy given in this paper, namely, Controlled-State Expansion Sequence Estimation (CSESE), is an integrated approach for TCM schemes transmission over bandlimited ISI channels. It comprises an algorithm for controlled-state expansion integrated with the MLSE implemented through soft output Viterbi algorithm. During each symbol interval, the CSESE determines the number of states to be processed in the next iteration, as a function of the expansion parameter defined in the algorithm. The algorithm provides faster decoding performance compared to RSSE[20,21] considered as conventional approach (c_RSSE).

   This paper is organized as follows: In Section 2, general structure of TCM encoder/modulator has been explained and the optimum MLSE is explained. In the section 3, a brief description of finite state machine model of band-limited ISI channel and the conventional Reduced-State Sequence Estimation (RSSE) are given. The Section 4 explains CSESE. Computer simulation results and conclusions are given in section 5. Next Section contains the acknowledgment and, in the following section references are listed.

2. TCM Encoder

   The general structure of TCM encoder/modulator employs redundant nonbinary modulation. It comprises a finite state convolutional encoder of rate m~ / m~ 1which governs the selection

   of modulation signals. When m -bits are to be transmitted per encoder/modulator operation, m~ m bits are encoded by the convolutional encoder. The encoded m~ 1 bits select one of the

   new bandwidth efficient coded modulation schemes

   subsets of M -ary signal set where M

   2m 1 .

   and decoding strategies accordingly. Maximum Likelihood Sequence Estimation is the optimum decoding strategy for TCM schemes. But the higher computational complexity of MLSE prohibits its use in practice. Later developments in the research emphasize on the development of reduced complexity suboptimum decoding strategies.

   Remaining m m~ uncoded bits select one of 2m m~ signals of a subset for transmission. Trellis coded bits of size m 1 are mapped into one of the symbols of M-ary signal constellation by the

   mapping function

   g1 X n , n

   where

   X n is m-bits

   L

   u

   n i 1

   pi an i

   represents ISI cancellation by linear

   information transmitted and n is encoder state.

   If the transmitted symbols are corrupted by AWGN samples, MLSE becomes the optimum solution. MLSE processes the noisy symbol sequence received

   equalization and { pi } are the tap gains of the Linear Time Invariant filter [18].

   :

   Convolutional encoder

   rate- m' m' 1

   m bits input

   xn m'

   n

   g1 xn ,

   Mapping

   m' 1

   an

   P1 +

   an L

   +

   +

   PL

   un +

   rn

   Figure 1. Discrete Time Finite State Machine Model of the Transmission System wn

   iteratively. The MLSE traces the encoder trellis to find the minimum

   metric path for Likelihood symbol sequence estimation. The path metric M n (..an ) computation at each node of the trellis during the discrete time interval n is given by

   In RSSE, for the assumed channel memory length L, ISI-code trellis complexity is reduced by truncating the channel memory length L to J. Likelihood sequence estimation performs the metric computation as given by

   M (..a ) M

   (..a ) r a 2

   (1)

   L J 2

   n n n 1 n 1 n n

   Mn (..an )

   min Mn 1 (..an 1 ) zn

   pn i an i pi an i an

   (4)

   where {rn} is the noisy received symbol given by

   { n 1} n

   i J 1 i 1

   {rn}

   {an}

   {wn}

   (2)

   where the second term in the metric computation provides ISI cancellation due to

   where{wn } is AWGN samples, and M n 1 (..an 1 ) is

   the metric computed during the interval n-1.

3. Bandlimited ISI Channel and FSM

   In a band-limited digital communication system, intersymbol interference (ISI) is the primary obstacle to high speed data transmission. For practical implementations the ISI intervals are

   previous symbols transmission not represented by the truncated combined states of reduced state trellis structure.

   Reduced State Trellis Structure is also obtained by grouping the states of super-trellis by implementing set-partitioning concept [20,21]. Resulting structure has the metric computation of the form

   limited. Accordingly, the TCM encoder and the ISI channel can be viewed as a combined finite-state machine (FSM), and, hence can be represented by the combined ISI-Code trellis called super-trellis

   M n (..an )

   (5)

   min

   { n 1}} n

   M n 1 (..an 1 ) zn

   L

   i J 1

   pn i an i

   2

   p0 an

   whose states are given by the product of encoder states and the ISI states[13,18,20]. The receiver performs Maximum-Likelihood Sequence Estimation of the noisy symbol sequence received by processing the super-trellis. The SOVA searches for a minimum cost path in the super- trellis. The path metric computation is given by

   L 2

   M (..a ) min M (..a ) r p a p a (3)

   where second term in the ISI cancellation eliminates the ISI due to symbols not represented by the RSSE trellis.

4. Controlled State-Expansion Sequence Estimation

   The new CSESE is a fast subopimum decoding strategy for TCM schemes in the ISI environment.

   n n {

   n 1} n

   n 1 n 1 n

   i n i 0 n

   i 1

   The CSESE is an integrated approach for Likelihood sequence estimation of TCM signals corrupted by

   where n is the state of super trellis and L is the finite ISI channel memory length assumed. The term

   the channel ISI and AWGN. It provides variable computational complexity for the algorithm. The metric computation is given by

   Mn (..an )

   min

   { n 1} n

   Mn 1(..an 1) zn

   L'

   i J 1

   pn ian i

   J1 2

   piani an

   i 1

   (6)

   noted that better performance is obtained for x3, with a degradation of 0.2 dB over c_PDFD.

   The simulation results depict that the error

   where L' and J ' are varied index parameters of CSESE. During each symbol interval, CSESE performs Likelihood Sequence Estimation and find the best- survivor node. Accordingly, the number of states- expansion for the next interval is determined. The decision parameter of the algorithm determines the nodes of combined ISI-code trellis to be expanded in the succeeding interval. The CSESE strategy reduces the computational complexity of the decoder by reducing the number of nodes expanded. The technique does not require additional storage and, the only overhead introduced is the decision parameter estimation. The error performance of CSESE has been evaluated for 4-state 16-QAM

   performance characteristics obtained with the CSESE strategy is close to the performance obtained by c-PDFD, with 15 to 20 percent of reduced in execution time. The performance is a function of optimality of controlled state-expansion. The technique can be extended to complex trellis structures.

   .

   Transmision on Bandlimited ISI Channel

   TCM scheme for a specific ISI channel simulated. The simplest case of c_RSSE that is Parallel Decision Feedback Decoding as the conventional approach (c_PDFD) has been simulated for comparison.

5. Results and Discussions

The CSESE performance is evaluated for 4-state 16-QAM TCM scheme in the ISI environment, in the presence of AWGN. The results are compared with the error performance obtained for c_PDFD. Error performance of uncoded 8-QAM is evaluated and considered for comparison, and, ISI free performance for 4-state 16-QAM TCM scheme evaluated through MLSE has also been considered.

The Figure 2 depicts the error performance

1.4

normalized time of execution

1.2

1.0

0.8

0.6

0.4

p0=0.7071 p1=0.7071

decision parameter: x2 = noise variance

for transmission over bandlimited ISI channel characterized by the impulse response coefficients p0=0.707 and p1=0.707. The decision parameter x2 is assumed as AWGN variance V. The curve No.2 from right represents the error event probability Vs SNR for CSESE. The curve No.3 represents the error event probability Vs SNR for the c-PDFD approach and the curve No.4 shows the error performance for ISI free condition. It is observed that CSESE performance is close to that of c-PDFD performance with a small amount of performance degradation. The degradation of about 0.5db at an error rate of 10-4 is observed. The curve 1, from right to left shows the error performance of 8- QAM uncoded scheme.

The reduced execution time of CSESE is shown in the Figure 3. It is noted from the Figure 3 that for the decision parameter x1, CSESE execution is about 20% faster than c_PDFD execution. The Table 1 shows the total number of states expansions reduced. The number of states biased from expansion increases at high SNR, and, varies as a function of the decision parameter.

The Figure 4 shows the error performance of CSESE for the decision parameters x1,x2 and x3. It is

0.2 normalized.execution.time.for.c_PDFD

normalized.execution.time.for.CSESE

0.0

13 14 15 16 17 18 19

SNR in dB

Figure 2. Error Event Probability Vs SNR for channel: p0=0.707,p1=0.707,

for decision parameter x2=0.5*noise variance

SNR in dB	No. of State	Discarded from expansion
	for Decision Parameters x1,x2,x3 in terms of Noise variance V x2=V x1 =0.5V x3=0.1V
17	13	3	1
16	34	8	1
15	100	25	1
14	229	45	1
13	434	112	4

10-1

Transmission on Bandlimited ISI Channel p0=.7071 p1=.7071

decision factors: x1=0.5 * noise variance

x2= noise variance x3=0.1 * noise variance

Error Event Probability

10-2

10-3

10-4

Error Event Probability

10-1

Transmission on Bandlimited ISI Channel p0=0.7071 p1=0.7071

decision parameter: x2 = noise variance

CSESE.for.4-state.16-QAM.TCM: for x2

10

-5

CSESE.for.4-state.16-QAM.TCM:for x1

c_PDFD.for.4-state.16-QAM.TCM CSESE.for.4-state.16-QAM.TCM:forx3

10-2

13 14 15 16 17 18

SNR in dB

Figure 4. Error Event Vs SNR for different decision parameters

10-3

10-4

10-5

CSESE.for.4_state.16_QAM.TCM.scheme ISI.free.performance.for.4_state.16_QAM.TCM c_PDFD.for.4_state.16_QAM.TCM.scheme uncoded.8QAM

TABLE 1

NUMBER OF STATES NOT EXPANDED

ACKNOWLEDGMENT

The authors would like to thank the reviewers of this paper. Also the authors would like to thank Mrs. Shivakumarappa Bandakkala for the extended help

REFERENCE

10 11 12 13 14 15 16 17 18 19

SNR in dB

Figure 3. Normalized Time Vs SNR

[1]. And Gregory W. Wagnall, A class of Block-Iterative Equalizer for Intersymbol Interference Channels: Fixed Channel Results, IEEE Transaction on communications, vol. 49, No. 11, July 2001. [2].Belfiore C. A., and Park J.H., Jr., Decision Feedback Equalization Proc. IEEE Tran. on commn., Vol. 67, pp 1143- 1156, Aug. 1979.

[3]. Benedetto S., Marson M. A., Albertengo G. and Giachin E., Combined Coding and Modulation: Theory and Applications,

IEEE Trans. Inform Theory, vol. 34, pp. 223-236, Mar. 1988. [4]. Benedetto S., Mondin M. and Montorsi G. Mallard L., Geometrically Uniform Multidimensional PSK Trellis Codes, Electron. Lettrs., Vol. 28, no. 4, pp. 1286- 1288, July

1992.

[5]. Benedetto S., Mondin M.and Montorsi G., Performance Evaluation of Trellis Coded Modulation Schemes, IEEE Proc., Vol. 82, pp. 833-855, June 1994

[6]. Biglieri. E., High-Level Modulation and Coding for Nonlinear Satellite Channels, IEEE Trans. Commun., Vol. COM-32, pp. 616- 626, May 1984

[7].Biglieri E., Divsalar D., McLane P.J. and SimonM.K,

Introduction to Trellis Coded Modulation with Applications, New York: MacMillan, 1991

[8]. Biglieri E. and Elia M., Multidimensional [1]. Albert M Chan. Modulation and Coding for band-limited Digital Channels, IEEE Trans Inform. Theory, vol. 34, pp 803-

.809, July 1988.

[9]. Biglieri E. and Mclane P.J., Uniform Distance and Error

Probability Properties of TCM Schemes, IEEE Trans.

Commn.,

Vol. 39, No.1 pp. 41-52, Jan. 1991.

[10]. Calderbank A.R. and Mazo J.E., A New Description of Trellis Codes, IEEE Trans. Inform. Theory, Vol. IT-30, pp. 784- 791, Nov. 1984.

[11]. Divsalar D. and Simon M. K., Trellis – Coded Modulation

for 4800-9600 bits/s Transmission over a Fading Mobile atellite Channel, IEEE, J. Select., Area Commn. Vol. SAC-5, pp.162-

175,

Feb 1987

[12]. Forney G.D., Jr., Maximum-likelihood Sequence Estimation of Digital Sequences in the Presence of Intersymbol

Interference,

IEEE rans.Inform. Theory, Vol. IT-18, pp. 363-378,May 1972. [13]. Forney G.D., Jr., Gallager R.G., Lang G.R., Longstaff F.M. and Qureshi S.U.H., Efficient Modulation for Band-limited Channels, IEEE J. selected Areas Commun., Vol. SAC-2, pp. 632-647, Sept. 1984.

[14]. Gottfried Ungerboeck, Trellis-Coded Modulation with Redundant Signal Sets part1: Introduction, IEEE communications magazine, Feb. 1987-vol.25, No. 2

[15]. Gottfried Ungerboeck, Trellis-Coded Modulation with Redundant Signal Sets part1I: State of the art, IEEE communications magazine, Feb. 1987-vol.25, No. 2

[16]. Hallen A.D. and Heegard. C., Delayed Decision Feedback Sequence

Estimation, IEEE, Trans. on Comunn.,Vol.37, p 428-436 May 1989.

[17]. Jon Feldman , Ibrahim Abous-Faycal, Matteo Frigo, A Fast Maximum-Likelihood Decoder for Convolutional Codes, Email: jonfeld@theory.1cs, mit.edu.

[18]. John G. Proakis,Digital Communications, Third Edition, McGRAW-HILL International Editions.

[19] Laura Ekroot and sam Dolinar, A* Decoding of Block Codes,

IEEE Transaction on communications, vol.44 No. 9, SEPT 1996

[20]. Pierre R. Chevillat and Evangelos Elefthrious, Decoding of Trellis-Encoded Signals in the presence of Intersymbol Interference and Noise, IEEE Transaction on communications, vol 37. No.7, July 1989

[21]. M. Vedat Eyboglu and Shahid U. H. Qureshi, Reduced State Sequence Estimation for Coded Modulation on Inter symbol Interference Channels, IEEE Journal on Selected Area in communications, Vol. 7, No. 6, Aug 1989.

[22] Daneshgaran.F,Mondi.M Simplified Viterbi decoding of geometrically uniform TCM codes, IEEE Transactions on Communications,Vol. 44, Issue 8, Aug 1996 Page930 937

[23]Multilevel Flash Memory on-chip Error Correction Based on Trellis Coded Modulation, Fei Sun, Siddharth

[24] Maunder, R.G.; Kliewer, J.; Ng, S.X.; Wang, J.; Yang, L.-L.; Hanzo,L. Joint Iterative Decoding of Trellis-Based VQ and TCM, IEEE Transactions on Wireless Communications, Volume 6, Issue 4,

April 2007 Page(s):1327 1336

[25]. Runsheng He, J. R. Cruz and Hongxin Song , A Reduced- State Sequence Estimation Technique and Its Applications, IEEE Transactions on Magnetics, vol. 35, No. 5, Sept. 1999