 Open Access
 Total Downloads : 552
 Authors : Niranjan. B. S. , Vanaja Shivakumar
 Paper ID : IJERTV1IS5048
 Volume & Issue : Volume 01, Issue 05 (July 2012)
 Published (First Online): 02082012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
New Controlled StateExpansion 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 StateExpansion 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 suboptimum decoding strategies for TCM schemes [1,17,21,22,25].
The new strategy we have developed, namely CSESE, is a controlled stateexpansion 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.

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 suboptimum 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, ControlledState Expansion Sequence Estimation (CSESE), is an integrated approach for TCM schemes transmission over bandlimited ISI channels. It comprises an algorithm for controlledstate 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 bandlimited ISI channel and the conventional ReducedState 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.

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 Mary signal constellation by the
mapping function
g1 X n , n
where
X n is mbits
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, ISIcode 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 n1.

Bandlimited ISI Channel and FSM
In a bandlimited 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 supertrellis by implementing setpartitioning 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 finitestate machine (FSM), and, hence can be represented by the combined ISICode trellis called supertrellis
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 MaximumLikelihood Sequence Estimation of the noisy symbol sequence received by processing the supertrellis. 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.

Controlled StateExpansion 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 ISIcode 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 4state 16QAM
performance characteristics obtained with the CSESE strategy is close to the performance obtained by cPDFD, with 15 to 20 percent of reduced in execution time. The performance is a function of optimality of controlled stateexpansion. 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.

Results and Discussions
The CSESE performance is evaluated for 4state 16QAM 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 8QAM is evaluated and considered for comparison, and, ISI free performance for 4state 16QAM 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 cPDFD 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 cPDFD performance with a small amount of performance degradation. The degradation of about 0.5db at an error rate of 104 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 
101
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
102
103
104
Error Event Probability
101
Transmission on Bandlimited ISI Channel p0=0.7071 p1=0.7071
decision parameter: x2 = noise variance
CSESE.for.4state.16QAM.TCM: for x2
10
5
CSESE.for.4state.16QAM.TCM:for x1
c_PDFD.for.4state.16QAM.TCM CSESE.for.4state.16QAM.TCM:forx3
102
13 14 15 16 17 18
SNR in dB
Figure 4. Error Event Vs SNR for different decision parameters
103
104
105
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 BlockIterative 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. 223236, 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. 833855, June 1994 [6]. Biglieri. E., HighLevel Modulation and Coding for Nonlinear Satellite Channels, IEEE Trans. Commun., Vol. COM32, 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 bandlimited Digital Channels, IEEE Trans Inform. Theory, vol. 34, pp 803.809, July 1988.
[9]. Biglieri E. and Mclane P.J., Uniform Distance and ErrorProbability Properties of TCM Schemes, IEEE Trans.
Commn.,
Vol. 39, No.1 pp. 4152, Jan. 1991.
[10]. Calderbank A.R. and Mazo J.E., A New Description of Trellis Codes, IEEE Trans. Inform. Theory, Vol. IT30, pp. 784 791, Nov. 1984. [11]. Divsalar D. and Simon M. K., Trellis – Coded Modulationfor 48009600 bits/s Transmission over a Fading Mobile atellite Channel, IEEE, J. Select., Area Commn. Vol. SAC5, pp.162
175,
Feb 1987
[12]. Forney G.D., Jr., Maximumlikelihood Sequence Estimation of Digital Sequences in the Presence of IntersymbolInterference,
IEEE rans.Inform. Theory, Vol. IT18, pp. 363378,May 1972. [13]. Forney G.D., Jr., Gallager R.G., Lang G.R., Longstaff F.M. and Qureshi S.U.H., Efficient Modulation for Bandlimited Channels, IEEE J. selected Areas Commun., Vol. SAC2, pp. 632647, Sept. 1984.
[14]. Gottfried Ungerboeck, TrellisCoded Modulation with Redundant Signal Sets part1: Introduction, IEEE communications magazine, Feb. 1987vol.25, No. 2 [15]. Gottfried Ungerboeck, TrellisCoded Modulation with Redundant Signal Sets part1I: State of the art, IEEE communications magazine, Feb. 1987vol.25, No. 2 [16]. Hallen A.D. and Heegard. C., Delayed Decision Feedback SequenceEstimation, IEEE, Trans. on Comunn.,Vol.37, p 428436 May 1989.
[17]. Jon Feldman , Ibrahim AbousFaycal, Matteo Frigo, A Fast MaximumLikelihood Decoder for Convolutional Codes, Email: jonfeld@theory.1cs, mit.edu. [18]. John G. Proakis,Digital Communications, Third Edition, McGRAWHILL 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 TrellisEncoded 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 onchip 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 TrellisBased 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