Optimization

A oupleofte hniquesforimproving theee tivenessoftheDTalgorithmare

des ribed inthe following.

Asstatedbefore,atraditional ompletionrepla ingtheunavailablemetri s

bynullvaluesworksonasubsetofpathsgivenbytheinterse tionofFSPsand

10

Forthe same reason,the redu ed- omplexity algorithmsbasedonstate redu tion[39℄

annotbesu essfullyapplied.

BSPs. While in the ase of the FT algorithm the interse tion oin ides with

theset of FSPs,inthe ase of theDT algorithm the interse tion ould result

almostempty,sin ethesets ofFSPsandBSPsarebuiltindependently ofea h

other. Thisissueisaddressed in[59℄,where the authorspropose a ompletion

onawindowofmultiple trellisse tions,thus implyingasigni ant in reasein

the omputational omplexity of the ompletion stage. We propose a simpler

solution allowing the ompletion stage to worknot on theinterse tion but on

theunionofthesetsofFSPsandBSPs,sothatallthemetri ssavedduringthe

re ursions an give a ontribution to thenalresult. The wayto do this

on-sists of repla ing the unavailable metri s in(2.21) byproper non-zero values.

For ea htime epo h

n

^,let

η _f,n

^{MINbethelowest metri saved duringtheforward}

re ursion,and let

η _b,n

^{MIN be thelowest metri saved during theba kward}

re ur-sion (expressions for forward and ba kward re ursions are provided in (2.17)

and (2.18),respe tively). Whena given state

σ n

^{doesnot belongto theset of}

FSPs at time epo h

n

^{, any non-zero value lower or equal to}

η _f,n

^{MIN ould be a}

reasonable hoi e for repla ing theunavailablemetri

η _f,n (σ _n )

^while

perform-ing the ompletion (2.21). Sin e we found, by means of extensive omputer

simulations, thatoverestimatingtheunavailablemetri sprovidesabetter

per-forman ethanunderestimatingthem,we hoosethelargestvalueintheallowed

range. Hen e, whenthe fa tor

η _f,n (σ _n )

^{in(2.21) isnot available, we repla eit}

by

η

^MIN

_f,n

^{.Similarly,when}

η _b,n+1 (σ _n+1 )

^{is notavailable, we repla eitby}

η

^MIN

_b,n+1

^.

Whenbothfa torsarenotavailable,we insteadignorethe ontribution ofthe

orresponding path.This solution, whi hwill bereferred to asnon-zero (NZ)

ompletion, ausesonlyaslightin reasein omputational omplexity[40℄,but

ensures a signi ant performan e improvement (see the simulation results in

Se tion 3.7).

A further optimization te hnique an be obtained byexploiting the

prob-abilisti meaningsof the statemetri s, provided in(2.19) and(2.20) and here

re alled:

η _f,n (σ n ) ∝ P (σ ⁿ |y ⁿ⁻¹ 0 )

η _b,n (σ _n ) ∝ p(y ^{N −1} n |σ n ) .

Inparti ular, (2.19)and (2.20) implythattheFSPsaresele ted basedonthe

MAP riterion, whilethe BSPsaresele tedbasedonthemaximum-likelihood

(ML) riterion.Thesedierent riteria, whi hresultequivalentonly whenthe

modulationsymbolsareequallylikelyandthere eiverdoesnotperform

itera-tivede oding,haveasigni antimpa tonthereliabilityofthesele tedpaths,

that is on the probability that su h paths in lude the orre t one [40℄. It is

intuitive to onje turethattheMAP approa h ismorereliable, andextensive

omputersimulations onrm this fa t. Asa onsequen e,theredu ed-sear h

forwardre ursionismorereliablethantheredu ed-sear hba kwardre ursion.

An ee tive solution for this asymmetry is presented in [40℄, with fo us on

the BCJR algorithm when employed for MAP symbol dete tion over

han-nels ae ted byinter-symbol interferen e (ISI),and onsists of modifyingthe

denition of the ba kward re ursion so that also the BSPs an be sele ted

basedon theMAP riterion. Sin ethis modi ationensures asigni ant

per-forman e improvement when ISI hannels are onsidered, it is interesting to

investigate the appli ability of thealgorithms in[40℄ to theproblem at hand.

Unfortunately, the re ursive denition of thestate

σ _n

^{implied by(1.5) makes}

the dire t appli ation of su h algorithms impossible. An alternative solution

for buildinga MAP-based setof BSPsisdes ribedinthefollowing.

Letustemporarilyassumetoknow,forea htimeepo h

n

^{andea hstate}

σ _n

^,

the a priori probability

P (σ _n )

^that

σ _n

^{is the orre t state, and let us dene}

themodied ba kward metri

η ˜ _b,n (σ _n )

^asfollows

˜

η _b,n (σ _n ) = η _b,n (σ _n )P (σ _n ) .

^(3.47)

Then, takinginto a ount (2.20), we an write

˜

η _b,n (σ _n ) ∝ p(y ^{N −1} n |σ n )P (σ _n ) = p(y ^{N −1} _n , σ _n ) ∝ P (σ n |y n ^{N −1} )

^(3.48)

showing that itis possible to build a MAP-based set of BSPs byworking on

the modied ba kward metri s

{˜ η _b,n }

^{instead of the lassi al ones}

{η b,n }

^{. In}

pra ti e, while performing the redu ed-sear h ba kward re ursion at a given

time epo h

n

^{,thealgorithm exe utesthe following steps:}

1. it extends the BSPs from time epo h

n + 1

^{to time epo h}

n

^{for the}

omputation ofthemetri s

{η b,n }

^;

2. it omputes the metri s

{˜ η _b,n }

^{by s aling the metri s}

{η b,n }

^{a ording}

to (3.47);

3. itin ludes thestates

σ _n

^withthebest

S

^{metri s}

{˜ η _b,n (σ _n )}

^{intheset of}

BSPs, saving the orrespondingmetri s;

4. its ales the saved metri s

{˜ η _b,n }

^{ba kto}

{η b,n }

^{a ordingto (3.47).}

We will refer to this algorithm asmodied double-trellis (MDT) algorithm. It

isworth notingthat, withrespe tto theDT algorithm,theforward re ursion

and the ompletion stage (either lassi al or non-zero) are exa tly the same.

Now, the point is how to ompute theterms

{P (σ n )}

^{required in(3.47). Due}

to there ursive denitionof thestate

σ _n

^{,they an be omputed asfollows}

P (σ n+1 ) = X

α n

X

σ n

T (α n , σ n , σ n+1 )P (σ n )P (α n )

^(3.49)

after initializing the values of

{P (σ 0 )}

^{a ording to the available}

informa-tion on the a tual rst state

¯ σ ₀

^{,as explained in thedis ussion related to the}

re ursion (2.17). In pra ti e, if we want to perform a MAP-based

redu ed-sear h ba kward re ursion, we have to perform the additional full-sear h

re- ursion(3.49)justforthe omputationoftheterms

{P (σ n )}

^{.Clearly,thelatter}

re ursionrepresentsthebottlene kofthemethodfroma omplexityviewpoint,

thus makingthe relevan eof theMDTalgorithm mainly theoreti al.

In on lusion, among the various redu ed-sear h algorithms des ribed so

far,thebest hoi eintermsofperforman e/ omplexitytradeoisexpe tedto

bethe DT-NZalgorithm.

Nel documento Advanced Modulation/Demodulation Schemes For Wireless Communications (pagine 130-133)