CAPACITY-MAXIMIZING RESOURCE ALLOCATION FOR DATA-AIDED TIMING AND CHANNEL ESTIMATION IN ULTRA-WIDEBAND RADIOSLin Wu and Zhi TianECE Department,Michigan Technological University,Houghton,MI49931,USAEmails:{liwu,ztian}@ABSTRACTThe overall system performance of data-aided ultra-wideband (UWB)communications relies critically on the accuracy of synchronization and channel estimation during the training phase.The total transmission resources should be properly allocated between training and information symbols in order to strike a desired balance between performance and informa-tion rate.To this end,this paper derives optimum transmission schemes that judiciously allocate the limited transmit power and pulse numbers for signal reception tasks performing opti-mal timing acquisition,channel estimation,as well as symbol detection.The resulting selection of transmitter parameters not only enables both the timing and channel estimators to attain the minimum mean-square estimation errors,but also maximizes the average system capacity.1.INTRODUCTIONUltra wide-band(UWB)technology has attracted great inter-est in both academia and industry for its promising future in short-range,high-data-rate indoor wireless communications. Conveying information over repeated ultra-short pulses,UWB signaling entails ample diversity inherent in its enormous band-width.In order to collect the diversity gain,an optimal corre-lation based receiver requires accurate timing-offset and chan-nel estimates,both of which are challenging to obtain due to the unique UWB transmission structure.In a data-aided mode,the generalized likelihood ratio test (GLRT)derived in[1]suggests that training symbols can be partitioned into two non-overlapping subsets to separately per-form channel estimation and timing acquisition without loss of optimality.To optimize the overall timing acquisition per-formance that is affected by both subsets,optimum training sequence(TS)design is investigated in[2]under the con-straints on total training resources(in terms of power and pilot symbol numbers).Under perfect timing,transmission resource allocation for channel estimation has been investi-gated using the pilot waveform assisted modulation(PWAM) framework[3].In this paper,we jointly consider the demands on transmission resources that are imposed from all three key elements in a UWB system:timing acquisition,channel esti-mation,and detection of information-bearing symbols.Based on the two-subset TS structure in[2],we use one of the sub-sets to perform PWAM-type channel estimation[3],yielding low-complexity yet near-optimum receiver design.Design tradeoffs reflect in the fact that more training symbols improve both timing-offset,channel,and symbol estimation,but also reduce transmission rate.To strike a desired performance-throughput tradeoff at the system level,we derive optimum energy and number allocation between training and informa-tion bearing symbols to jointly maximize the average system capacity,which is shown to be equivalent to minimizing the mean-square timing and channel estimation errors.Recogniz-ing the impact of nonlinear amplifiers on system implemen-tations,we also consider the optimum transmission resource allocation under a constant-envelope constraint.2.SYMSTEM MODELIn a UWB peer-to-peer communication system,every infor-mation symbol s(n)∈{±1}is conveyed over N f repeated pulses p(t),with one pulse per frame of frame duration T f. Each p(t)has unit energy and ultra-short duration T p(T p T f)at the nanosecond scale.During the training phase,each training symbol has energy E t,0spread over N f frames.The transmitted signal is u(t):=E t,0/N f∞k=0s(k)p s(t−kT s), where p s(t):=Nf−1j=0p(t−jT f−c j T c)is the transmit symbol-waveform of duration T s:=N f T f,and{c j}N f−1j=0is a pseudo-random time-hopping code with c j T c<T f,∀j.The signal u(t)passes through a L-path dense multipath channel with impulse response g(t):=L−1l=0αlδ(t−τl,0)[4], whereαl andτl,0denote the attenuation and delay of the l-th path,respectively.The overall channel is given by h(t):= (g∗p)(t)=L−1l=0αl p(t−τl,0)(with∗denoting convolution), and the composite received symbol-waveform is h s(t):=(g∗p s)(t)=Nf−1j=0h(t−jT f−c j T c).Denoting the receiver timing-offset asτ0,the received signal can be expressed asr(t)=E t,0N f∞k=0s(k)h s(t−nT s−τ0)+w t(t),(1)where w t(t)is a zero-mean Gaussian noise with PSDσ2w.We suppose h(t)andτ0remain invariant over a burst of duration NT s,but may change from burst to burst in a slow-varying channel.The timing-offsetτ0can be written asτ0:= n f T f+ ,where n f is an integer representing the frame-level acquisition error,and ∈[0,T f)denotes the small-scale tracking error.Mis-timing is confined to be within a symbol after energy detection,thus n f∈[0,N f−1].In every burst of N symbols,we use a total of N t training symbols to esti-mate both the acquisition error n f and the channel h(t),while«treating as an estimation error.Increasing N t ,or alterna-tively,the total training energy E t :=E t,0N t ,can improve theaccuracy of both channel and timing estimates ˆh (t )and ˆn f .While the resulting symbol detection performance improves,the information rate drops.To balance this paradox,we strive to judiciously assign energy E s and number N s of information symbols under the constraint of total energy E :=E t +E s and burst size N =N t +N s .The goal is to maximize the system capacity C given the fixed transmission resources per burst.3.TRANSMISSION RESOURCE ALLOCATION 3.1.Training Sequence Design and Timing Acquisition The training sequence (TS)pattern plays a critical role in de-veloping timing and channel estimators,and directly affects the estimation performance.Depending on whether two con-secutive symbols have the same or opposite signs,the N t training symbols can be grouped into two subsets,that is,S +:={s (n ):s (n )=s (n −1)}and S −:={s (n ):s (n )=−s (n −1)}.As observed in [1],the received signal result-ing from S +does not experience any symbol sign transition,therefore does not contain timing information,but is useful for channel estimation as if in a no-data-modulation mode.Tim-ing offset parameters can be extracted from the symbol tran-sition in S −,using the channel estimate obtained from S +.Such an observation is rigorized in [1]to suggest that estima-tion of channel amplitudes and timing errors can be carried out separately from the non-overlapping subsets S +and S −,without loss of optimality.Based on this separability property [1],it is convenient to place N +t symbols in S +at the first segment of TS fol-lowed by N −t =N t −N +t symbols in S −.With such a TS placement,a high-performance maximum-likelihood digital synchronizer can be constructed.Sampling at a low rate of one sample per symbol,an effective way to collect suf ficient multipath energy while bypassing the unknown channel h (t )is to select a noisy template p r (t ):=r (t ),t ∈[N f T f ,(N f +1)T f )as the receiver correlation template [2].The symbol-rate samples at the correlator output is thus given by y (n ):= (n +1)T s nT sr (t ) N f −1j =0p r (t −nT s −jT f )dt .Note that the noise-free version of p r (t )matches exactly to the unknown channel thanks to the TS structure;thus y (n )enjoys near-optimum en-ergy capture via maximum-ratio combining,without resorting to channel estimation.Due to mis-timing,each sample y (n )may contain two consecutive input symbols.Let us de fine amplitude A :=E t,0A and a tracking-induced energy lossfactor λh, :=(1/R h ) T f T f − h 2(t )dt ,where R h := T f 0h 2(t )dt is the total channel energy.Accordingly y (n )can be ex-pressed as [1]y (n )=A s (n ) 1−n f +λh, N f +s (n −1)n f +λh,N f+w t (n )(2)where the noise sample w t (n )is a Gaussian random variablewith zero mean and variance σ2t :=σ2w R h N f .Observe from (2)that nf :=n f +λh, represents the por-tion of signal waveform collected in the symbol-long correla-tion template due to mis-timing.Knowing {s (n ),y (n )},thisobservation can be exploited optimally to obtain the maxi-mum likelihood estimate (MLE)of the unknown n f [2],which approximates the true timing offset n f subject to a bounded timing ambiguity λh, ∈[0,1]caused by the unknown .The ML formulation in [2]achieves the Cramer-Rao lower bound CRB(n f ),which can be exploited to optimally allocate thesubset energies E +t :=N +t E t,0and E −t :=N −t E t,0.These results are summarized below [2]:Result 1(Training Resource Allocation and CRB)The MLEs of A and n f can be obtained from symbol-rate sam-ples {y (n )}.For a fixed total training energy E t ,the opti-mal energy allocation to minimize the CRB(n f )is given by (E +t )opt =E t (N f −2n f )/(2(N f −n f )),and the resultingCRB (n f )is upper bounded by CRB (n f )opt =N 2f σ2w /A 2.Having acquired ˆn f ,the frame-level residual timing er-ror ˜n f becomes ˜n f := ˆn f −n f N f ,where · represents the modulo operation with based N f .Recalling the de fini-tion ˆnf :=ˆn f +λh, ,and noting that ˆn f is an unbiased esti-mate,the mean-square estimation error (MSE)of ˜n f becomes σ2˜n f =σ2ˆn f :=E {|ˆnf −n f |2}=N f σ2w /(E t R h )+σ2.Note that σ2˜n f is inversely proportional to the total training energy E t and the energy capture index R h .In addition,an addi-tive noise floor σ2 arises from λh, ,whose mean ¯λh,and MSE σ2are both bounded in [0,1].The residual acquisi-tion error ˜n f will affect the ensuing channel estimation andsymbol detection quality,while its MSE σ2˜n f will be useful in transmission resource allocation:a comparatively smaller σ2˜n f suggests less resources to be allocated for synchroniza-tion purpose.3.2.Channel EstimationChannel estimation can be carried out during the first N +t symbol intervals,since the corresponding TS subset is equiv-alent to having no data modulation.Subject to the residual mis-timing ˜τ0:=˜n f N f + ,the effective symbol-long chan-nel h r (t )is related to h s (t )byh r (t )=h s (t −˜τ0+T s ),t ∈[0,˜τ0);h s (t −˜τ0),t ∈[˜τ0,T s ).(3)In fact,h r (t )is nothing but a circularly-shifted (by ˜τ0)ver-sion of h s (t )bounded within [0,T s ).The received signal in the n -th symbol interval is given by r n (t ):=r (t +nT s )=E t,0/N f h r (t )+w n (t ),where t ∈[0,T s ),and n ∈[0,N +t −1].The segments {r n (t )}can be summed up and scaled by µ:=N +t E t,0/N f to yield an unbiased least-square (LS)channel estimate of h r (t ):ˆhr (t ):=µ−1N +t−1n =0r n (t )=h r (t )+µ−1N +t−1n =0w n (t ).(4)It can be shown that this LS estimator achieves the estimationCRB lower bound [3].Let us de fine the residual channel es-timation error as ˜hr (t ):=ˆh r (t )−h r (t ).The MSE of ˜h r (t )is the same as the variance of ˆhr (t ),both of which can be deduced from (4)as σ2ˆh r=σ2˜hr:=E {˜h 2r (t )}=2N f σ2w /E t .¬3.3.System-Level Resource AllocationBoth the timing and channel estimation MSEs σ2˜n f and σ2˜h r decrease monotonically as the training energy E t increases.On the other hand,for fixed total energy per burst,the en-ergy of information symbols E s decreases as E t increases.To balance performance versus information rate,we seek optimal resource allocation between training and information symbols to jointly maximize the average system capacity C .The received information-conveying r (t )can be easily ob-tained by replacing E t,0,τ0,and w t (t )in (1)by E s,0:=E s /N s ,˜τ0,and w s (t ).Subject to ˜τ0,each T s -long segment of r (t ),denoted by r n (t ):=r (t +nT s ),t ∈[0,T s ),is given byr n (t )= E s,0N f (s (n )h s (t −˜τ0)+s (n −1)h s (t −˜τ0+T s ))+w n (t ).(5)Subject to imperfect channel estimation,an optimum correla-tor uses the T s -long channel estimate ˆhr (t )obtained in Sec-tion 3.2as the correlation template to yield decision statisticy s (n ):= Ts 0r n (t )ˆhr (t )dt for detecting s (n ).Similar to (2),y s (n )can be derived asy s (n )= E s,0N f R h s (n )(N f −˜n f )+s (n −1)˜nf +ζ(n ),(6)where ˜n f =˜nf +λh, is the residual acquisition error sub-ject to -induced ambiguity,and ζ(n )is the composite noise term resulting from not only the ambient noise,but also the random timing and channel estimation errors as well.De-noting the signal component of r n (t )as r ns (t ):=r n (t )−w n (t ),ζ(n )comprises the following three terms:ζ1(n ):= T s 0w n (t )h r (t )dt ,ζ2(n ):= T s0r ns (t )˜h r (t )dt ,and ζ3(n ):= T sw n (t )˜h r (t )dt .It is shown that these three terms can be approximated to be Gaussian random variables with zero mean [3],so is ζ(n ).All the contributing factors to ζ(n ),includingthe auto-or cross-correlations among w n (t ),h r (t ),˜hr (t ),are statistically known via σ2w ,R h ,σ2ˆh r ,subject to the impact of residual mis-timing.After some tedious derivations and de fin-ing N c :=T f /T c ,we reach the variance σ2ζof ζ(n )as (proof omitted for space limit):σ2ζ=σ2ζ1+σ2ζ2+σ2ζ3(7)=σ2w N f R h +σ2ˆh rN c +E s,0N 2fR h σ2ˆh rN 2f +2σ2˜n f −2(N f −1)¯λh,.To get the system capacity C ,let us exploit the effectiveSNR ρeff of each information symbol.We partition the dis-crete signal model in (6)into its signal component ˜s (n ):= E s,0/N f R h (N f −˜n f )s (n )and its noise component ˜w (n ):= E s,0/N f R h ˜n f s (n −1)+ζ(n ).The power of those two com-ponents are denoted by E ˜n f , |˜s (n )|2 and E ˜n f ,|˜w (n )|2respectively.Consequently,we obtain the effective SNR per information symbol as:ρeff :=E ˜n f , |˜s(n )|2 E ˜n f , {|˜w(n )|2}=E s R 2h σ2˜n f +σ2 +(N f −¯λh, )2E sR 2hσ2˜n f+σ2+¯λ2h,+N fN s σ2ζ.(8)To link the system capacity C with ρeff ,we treat theoverall UWB system,including the transmitter,the channel,the correlator,and the symbol detector,as a binary symmet-ric channel (BSC)with transition probability p =Q (√ρeff )1[3].Inspection on the mutual information of the BSC reveals that the average channel capacity isC =N sNE h {p log 2p +(1−p )log 2(1−p )+1}.(9)It is shown from (8)that when the channel coef ficients isperfectly estimated and timing is known,i.e.,ˆh(t )=h (t ),σ2˜n f =0,and λh, =0,the effective SNR becomes ρeff =E s R h /(N s σ2w ),which provides the upper bound for the effec-tive SNR.Its associated capacity C also gives an upper bound for the average capacity in the presence of imperfect channel and timing estimation.Having obtained the expression of C ,we can start deriving system-level resource allocation.Let us de fine an energy allo-cation factor β:=E s /E ∈(0,1),which leads to E t =(1−β)E .For convenience we also de fine the nominal transmit-SNRρ:=E /(Nσ2w )and the nominal receive-SNR ρr :=R h ρ,which simply scales ρby the energy capture R h .Putting all together,we express the effective SNR in (8)with respect to βas follows:ρeff (β)=N 2f (1−β)ρr N +AN 2f +2D (1−β)ρr N +N 2f N s βNρr +4N 2f (1−β)2ρ2r N 2+2N 2f N c N sβ(1−β)ρ2rN 2+B,(10)where the three constants A,B ,and D are de fined as A :=2σ2 +(N f −¯λh, )2,B :=2σ2 +¯λ2h, and D :=N 2f+2σ2 −2(N f −1)¯λh, ,respectively.Fixing N s and N ,the capacityC increases monotonously with ρeff ,therefore the optimal β∗that maximizes ρeff also maximizes C .When seeking a closed-form β∗,we find ∂ρeff /∂βto be a third-order poly-nomial in β.Solutions to β∗can be either obtained from the roots of ∂ρeff /∂β,or directly sought from (10)numerically.Proposition 1(Energy Allocation per Burst)For any given burst size N ,information symbol number N s ,and total energy E per burst,the energy allocation factor β∗maximizing the capacity C can be numerically solved by maximizing (10).Proposition 1implies that when the optimal β∗is selected,the SNRs for training and information symbols are generally not equal.Transmissions with uneven instantaneous power level may reduce the ef ficiency of nonlinear ampli fiers in sys-tem implementation.To avoid this problem,we consider a more practical situation where training and information sym-bols have the same energy per symbol,i.e.,E t,0=E s,0.In this case,we introduce a number allocation factor α:=N s /N ∈(0,1).Accordingly,the number of training symbols is N t =(1−β)N ,and the per-symbol energy is E t,0=E s,0=E /N .Similar to (10),the effective SNR in terms of αis given by ρeff (α)=N 2f (1−α)ρr N +A2f (1−α)ρr N +2f Nρr +2f(1−α)2ρ2r N2+2f c (1−α)ρ2r N+B .(11)1Q (x ):=(1/√2π) x exp(−y 2/2)dy .¬Therefore,the average capacity becomes a function of α,that is,C (α)=αE h [p (α)log 2p (α)+(1−p (α))log 2(1−p (α))+1],(12)where the transition probability is p (α):=Q (ρeff (α)).Substituting (11)into (12),we obtain the optimum α∗by max-imizing the average capacity C via numerical search.Proposition 2(Number Allocation per Burst)For any given burst size N and with equal per-symbol energy,the optimum number allocation factor α∗that maximizes the average ca-pacity C can be numerically obtained by maximizing (12).4.SIMULATIONSSimulation results are compared under both optimum resource allocation and non-optimal cases to validate our analyses and designs.In all test cases,the transmission parameters are se-lected as T p =T c =1ns ,T f =100ns ,N f =50and N =100,and the random channel parameters are generated according to [4],with Γ=30ns ,γ=5ns ,1/Λ=2ns and 1/λ=0.5ns .For energy allocation per burst,Figure 1(a-b)depict the effective SNR ρeff and the corresponding average capacity vs.N s /N ,for various βvalues.It is observed that the op-timum β∗offers the maximum effective SNR and system ca-pacity when N s is fixed.The results for β=0.5are very close to the best case especially at a low nominal SNR ρ,which provides a reasonable near-optimum parameter in the imple-mentation.For number allocation per burst under the equal-power constraint,Figure 2depicts the average system capacity over 500random channel realizations vs.the nominal SNR ρ,for various number allocation factors α.It has been con firmed by Figure 1that C increases monotonously as N s increases,for a fixed βwhen unequal power transmission is allowed.As a result,the optimum N ∗s should be N ∗s =N −3,where N t =3is the minimum number of training symbols needed for both timing and channel estimation,as can be deduced from the two-subset TS structure.Hence,we can get the maximumC (β∗)at N ∗s for reference.It is shown that the optimum num-ber allocation α∗using Proposition 2subject to equal-power transmission offers system capacity that is very close to themaximum C (β∗)at N ∗s .5.SUMMARYIn this paper,system-level resource allocation results are de-rived to facilitate transmitter design in trading off performance and information rate.Because of the use of near-optimum,low-complexity receiver design for timing,channel estima-tion,and symbol detection,our optimum allocation strategies not only attain the maximum system capacity,but also min-imize the mean-square channel and timing estimation errors,and thereby achieve the CRBs.6.REFERENCES[1]Z.Tian,and G.B.Giannakis,“Data-Aided ML TimingAcquisition in Ultra-Wideband Radios,”Proceedings of IEEE Symposium on Ultra-Wideband Syst.and Tech.(UWBST’2003),Reston,V A,November 16-19,2003.[2]Z.Tian,and G.B.Giannakis,“Training Sequence De-sign for Data-Aided Timing Acquisition in UWB Ra-dios,”to appear in Proc.Intl.Conf.on Communications (ICC),Paris,June 2004.[3]L.Yang,G.B.Giannakis,“Optimal Pilot WaveformAssisted Modulation for Ultra-Wideband Communica-tions,”Proc.of the 36th IEEE Asilomar Conf.on Sig-nals,Systems,and Computers ,Nov.3-6,2002.[4]H.Lee,B.Han,Y .Shin,and S.Im,“Multipath Char-acteristics of Impulse Radio Channels,”Proc.of VTC ,Tokyo,pp 2487-2491,Spring 2000.−−Ns/Nρe f f(d B )(a)Ns/Na v e r a g e c a p a c i t y (b)Fig.1.Energy allocation per burst using Proposition 1:(a)ρeff vs.N s /N (b)average capacity vs.N s /N .SNR (dB)a v e r a g e c a p a c i t y Fig.2.Number allocation per burst using Proposition 2¬。
