{'fraction_non_alphanumeric': 0.0277414245821698, 'fraction_numerical': 0.009869545284041178, 'mean_word_length': 4.641187811530142, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Reconfigurable Structures for Direct Equalisation in Mobile Receivers

Any communication channel will usually distort the transmitted signal. This is especially true in the case of mobile systems, where multipath propagation causes the received signal to be seriously degraded. Over the years, many techniques have been proposed to combat channel effects. Two of the most popular are linear equalisation (LE) and decision feedback equalisation (DFE). These methods offer a good compromise between performance and computational complexity. LE and DFE are implemented using finite impulse response (FIR) filters whose frequency spectrum approximates the inverse of the channel spectrum plus noise. In mobile systems, the equaliser is made adaptable in order to be able to respond to the channel variations. Adaptability is achieved using adaptive FIR filters whose coefficients are iteratively updated. In principle, an infinite number of filter coefficients would be needed to achieve perfect channel inversion. In practice, the number of taps must be finite. Simulations show that, in realistic scenarios, making the equaliser longer than a certain (undetermined) number of taps will not yield any benefit. Moreover, computation and power will be wasted. In battery powered devices, like mobile terminals, it would be desirable to have the equaliser properly dimensioned. The equaliser's optimum length strongly depends on the particular scenario, and as channel conditions vary, this optimum is likely to vary. This thesis presents novel techniques to perform equaliser length adjustment. Methods for the LE and the DFE have been developed. Simulations in many different scenarios show that the proposed schemes optimise the number of taps to be used. Moreover, these techniques are able to detect changes in the channel and re-adjust the equaliser length appropriately.


SOURCE CODING / DECODING
In general, bandwidth is a limited resource whose usage can be optimised by properly designing some of the subsystems in Figure 1.1. This is especially true for the case of wireless systems where the same spectrum must be shared among many users and many different services.
One method to maximise bandwidth usage is to compact the information to be transmitted.
Source coding, i.e. compression, is one of the principal applications of information theory whose fundamentals results were stated by Shannon in his landmark paper [Shannon48].
Source compression can be achieved if some properties of the original message are exploited. A distinction must be made whether the source of information is a finite discrete source, such as the English alphabet, or is a natural source (typically continuous), such as speech. This distinction is fundamental as, depending on the type of source, different properties are exploited.
In the case of discrete sources, it is very often the case that the different symbols generated by the source do not have the same probability of occurrence. This fact can be effectively utilised by assigning short codes to the most frequent symbols and longer codes to less frequent ones, rather than assigning equal length codes to all symbols. Assuming that the source statistics are known (i.e. the probability of occurrence of each symbol), there are well defined procedures to assign different length codewords to each symbol in a way that reduces the average number of transmitted bits. These coding schemes, generally known as prefix coding, need to be uniquely decodable at the receiver, as otherwise ambiguity would appear with respect to the transmitted message. Huffman coding, a particular class of prefix coding, is the most popular algorithm for assigning codewords to symbols. The algorithm is optimum in the sense that the average number of binary digits required to represent the source symbols is minimum ( [Proakis95]), and is described in any of the communications textbooks mentioned at the beginning of this section. If the statistics of the source are not known a-priori, the Huffman algorithm cannot be used and other schemes must be employed. The most widely used technique in this situation is Lempel-Ziv coding which has the ability to adapt to the particular characteristics of the source. The algorithm works by parsing the source data stream into segments that are the shortest subsequences not encountered previously. Again, details of the algorithm can be found in any of the general references given.
If the input to the communication systems is a continuous waveform, typically speech, the signal must first be digitised. When a bandlimited continuous waveform is sampled at a sufficiently high rate (Nyquist sampling), the resulting samples perfectly represent the original signal and this can be reconstructed using a lowpass filter. Fundamental in the context of source coding is the fact that adjacent samples of a signal coming from a natural source will typically exhibit a high degree of correlation. Correlation is a sign of redundancy and in the case of continuous signals, the objective of the source coder is to remove this redundancy, transmitting only the essential information. Broadly speaking two different approaches are at hand to perform the process of redundancy removal in speech signals, namely, waveform coding and channel vocoding.
Waveform codes try to mimic as closely as possible the original speech signal. Examples of waveform coding are pulse code modulation (PCM) and adaptive differential pulse code modulation (ADPCM). PCM does not exploit signal redundancy and can only be regarded as a method of coding speech into a 64 kbit/s data stream. ADPCM does exploit the signal redundancy to compress the speech signal. ADPCM is based on the use of linear predictors.
A linear predictor can be thought of a filter whose output predicts the current input to the filter as a function of the past samples of the incoming signal. Logically, the prediction will not be perfect and by comparing the prediction with the current sample, an error signal can be formed. This error signal, whose variance is much smaller than that of the original samples, can be quantised and PCM encoded with fewer bits. At the receiver, the incoming error signal is used to correct the output of a predictor identical to that used in the transmitter, achieving in this way perfect reconstruction of the original signal. Given that the statistics of speech are non-stationary, the predictor coefficients vary with time, and need to be periodically transmitted so that reconstruction can take place at the receiver. Using ADPCM, a speech signal can be coded into a 32 kbit/s bit stream without any quality degradation with respect to the conventional PCM encoding.
Vocoding systems, on the other hand, assume that the signal (speech) being coded conforms to a certain model. The vocoder works by analysing a segment of speech in order to extract the parameters of the model corresponding to that particular segment. These parameters are then transmitted and the receiver uses them to synthesise the original speech segment. One of the most common vocoders in use is the linear predictive coder (LPC). LPC assumes that the speech generation mechanism can be modelled by an all-pole filter (vocal tract) excited by either white noise (unvoiced sounds) or frequency tones (voiced sounds). In this case, the LPC encoder estimates the filter coefficients for a short speech segment using linear prediction techniques. It also decides whether the sound is voiced or unvoiced. This information is then sent and at the other end, the receiver uses it to reconstruct the original speech. Rates as low as 4.8 Kbits/s can be achieved using LPC with an acceptable voice quality.
Nearly all current mobile standards such as GSM, IS-54 or IS-95 rely on some variant of LPC to compress speech. This is due to the necessity, in a mobile environment, of reducing as much as possible the transmitted bit rate. Detailed treatments of speech compression schemes can be found in Chapter 3 of [Steele99] and Chapter 7 of [Rappaport96]. A thorough treatment of adaptive linear prediction can be found in chapter 6 of [Haykin96].

CHANNEL CODING / DECODING
Channel coding, also known as error control coding, is the part of information theory that deals with the design of coding schemes which allow the receiver (i.e. the decoder) to detect and/or recover errors introduced by the transmission medium. The coding techniques briefly presented in the following paragraphs all have the common feature of adding some form of redundancy, i.e., extra bits, to the original message. The ratio between the number of input bits to the number of output (coded) bits is called the coding rate. In a way, channel coding acts in the opposite direction to source coding, where the purpose is to eliminate redundancy; however now the redundancy added has a very well defined structure in order to help in the control of errors.
It is important to recognise that adding bits to the original information sequence with the purpose of lowering the bit error rate has the effect of increasing the bandwidth needed to transmit the message. Alternatively, just the original bits could be sent, but with more signal power transmitted to overcome the channel impairments. This illustrates the classical tradeoff between signal power and transmission bandwidth when designing a system to achieve a given BER. In the context of mobile systems, both resources must be used carefully as spectrum is scarce and strictly limited and power should be kept as low as possible to reduce interference among different users and extend battery times.
Coding theory is a highly mathematical subject whose presentation falls out of the scope of this introductory chapter. Therefore the most important coding techniques will be just briefly described. The coding schemes covered are: linear block codes, cyclic codes, convolutional codes and compound codes.
An (n, k)-block code accepts k information bits and adds to them (n-k) redundant parity check bits producing a stream of n bits (coding rate = k/n). Depending on how many bits are included for parity, the decoder will be able to perform some checking procedures and to detect and/or correct one or more erroneous bits. A code is said to be linear if the modulo-2 addition of any two code words produces another code word belonging to the code. Code linearity simplifies the decoding process making it very efficient.
Cyclic codes are a particular subclass of linear block codes, which satisfy, apart from the linearity property, the cyclic property. The cyclic property states that any cyclic shift of a code word in the code is also a code word. When both properties are satisfied, the resulting code has a very well defined mathematical structure, whose properties simplifiy the encoding process and also allow the use of very efficient decoding schemes.
Next on the list are convolutional codes. These codes, unlike block codes, have as input a continuous (serial) stream of information bits and produce another continuous stream, typically at a higher rate, of coded bits. The input bits are fed into a shift register and the output bits are obtained from linear combinations (XOR) of the bits in the shift register. The span in bits of the shift register is termed the constraint length. From the encoding process just described, it is obvious that the generated code words are not independent of each other as is the case in block codes. The decoding of convolutional codes is normally performed using the Viterbi algorithm [Forney73]. This is a very efficient method of implementing a nearest neighbour decoding strategy (also known as maximum likelihood sequence estimation). A complete example illustrating the functioning of the Viterbi algorithm can be found in [Sklar01].
Compound, or concatenated, codes combine two or more coding schemes (component codes) such as the ones introduced in previous paragraphs. The resulting codes have large coding gains and error-correction capabilities of longer single codes. Moreover, their inner structure allows a relatively simple decoding. Among the different compound codes, Turbo-Codes ( [Berrou93]) have recently gained wide acceptance for achieving a performance close to the limit predicted by Shannon ([Shannon48]). A Turbo encoder is typically made of two convolutional encoders operating on two different interleaved versions of the same information sequence. At the receiver, the incoming bits are subject to a double decoding process by the decoders of the two component codes. These decoders rather than performing hard decisions as is the case of single codes, generate soft decisions and information is exchanged between them. Typically, this exchange of information between decoders is iterated several times, with each iteration producing more reliable solutions.
In a GSM speech frame (260 bits), bits are classified according to their importance in the speech quality. A 3-bit cyclic code is calculated for 50 of the 182 most significant bits.
These 182 bits are then encoded using a ½-convolutional encoder with a constraint length of 5. The remaining bits in the frame are left unprotected as they do not affect speech quality significantly. In data frames, all bits are coded using the same convolutional encoder as in the case of speech.
In UMTS, various coding schemes are supported. Depending on the type of service assigned to a particular link, convolutional encoding with coding rates of ½ or 1/3 and constraint length of 8 can be used. Support for Turbo-Codes with 1/3 coding rate and constraint length of 4 is also provided in the UMTS standard.

MODULATION
Modulation is the process of modifying one signal in sympathy with another ( [Glover98]). In the context of digital communications, an information signal is used to modify the characteristics of a carrier. In baseband systems, the carrier is a rectangular pulse train whereas in radio communications, where our interest is, the carrier is a sinusoid.
The three basic methods in RF modulation correspond to variations of one of the three parameters of a sinusoid, namely, amplitude, frequency and phase, giving rise to amplitude modulation (AM), frequency modulation (FM) and phase modulation (PM) respectively. In the case of digital modulation schemes, the number of levels of each of these parameters is discrete and finite and they are renamed as amplitude shift keying (ASK), frequency shift keying (FSK) and phase shift keying (PSK). FSK and PSK signals can be demodulated in a coherent or non-coherent way depending on whether the receiver has perfect knowledge of the phase of the transmitted signal. Coherent receivers achieve lower bit error rates but at the cost of increased hardware complexity, as they need to use some form of carrier synchronisation. The advantages and inconveniences of each type of modulation can be found in the communication textbooks mentioned above.
In most radio communication systems, spectrum is a rather scarce resource whose use must be optimised. One method to increase the spectral efficiency of the system is to use high order modulation schemes, where the carrier parameter being varied can take more than 2 values (usually a power of 2). The resulting modulation schemes, called multilevel ASK (MASK), FSK (MFSK) and PSK (MPSK), offer the possibility of transmitting more bits of information using the same channel bandwidth. The penalty paid is an increased bit error rate or a higher power transmission. Some important multilevel schemes are quaternary PSK (QPSK) and quadrature amplitude modulation (QAM). QAM is a multilevel scheme that combines amplitude and phase modulation providing as many levels as 1024 or 2048, achieving in this way a high spectral efficiency.
Gaussian minimum shift keying (GMSK) is a particularly important modulation format based on a form of QPSK (OQPSK) in which the information bits are first Gaussian-shaped before modulation. This shaping has the effect of avoiding the abrupt envelope variation which is present at the output of practical (i.e. filtered) OQPSK modulators. Changes in the envelope increase interference when the modulated signal is then amplified by a low noise amplifier (LNA) operated in the non-linear region, such as is the case in power restricted environments (satellites transponders, mobile handsets). As in some of the other schemes, GMSK modulated signals can be coherently or non-coherently detected.
Concluding this brief review of modulation methods it is important to mention a scheme that combines modulation and channel coding as a single process. Trellis coded modulation (TCM) is a technique that achieves coding gains of 3-6 dB without any bandwidth expansion. Details of TCM can be found in the general references given previously and in [Ungerboeck87].
GSM uses GMSK as its modulation scheme. This decision was made in light of the very low adjacent channel interference generated by this type of modulation which allow the use of amplifiers in the non-linear region (i.e. power efficient). In UMTS the selected modulation formats are OQPSK (offset quaternary phase shift keying) for the uplink and QPSK (quaternary phase shift keying) for the downlink. Notice that in the case of the downlink, envelope transitions of the output signals are of no importance because the base station can operate the LNAs in the linear region as there are no power constraints.

MULTIPLE ACCESS
Multiuser communication systems, such as mobile systems, allow a transmission medium to be shared among different users simultaneously. Clearly, there has to be some means of assigning transmission resources to users in a structured way, as otherwise mutual user interference would greatly impair communication. The technique employed to do this strongly affects the design of the rest of the network and many of its characteristics. The three most common methods to allow simultaneous use of the communication channel by different users are: frequency division multiple access (FDMA), time division multiple access (TDMA) and code division multiple access (CDMA). Each of them is now introduced.
In FDMA, each user is assigned a subband of the total frequency band. Guard bands are left between users in order to reduce mutual interference, as the filters separating users are nonideal. FDMA was the multiple access technique used in early (analogue) mobile systems.
TDMA allows a user to employ the entire available spectrum but only for a fraction (slot) of the total time. In analogy with FDMA, guard times are inserted between users to allow for the imperfections of the synchronisers. The standards GSM and IS-54 use a combination of TDMA with FDMA in which users are divided among carriers, and the users on each carrier are time multiplexed.
CDMA allows the utilisation of the whole spectrum all the time by any single user. Of the different types of CDMA, the one covered here is the direct sequence CDMA (DS-CDMA) which is the one selected by all forthcoming 3G systems. In DS-CDMA, each user is assigned a code. This code is used to multiply (spread) the user information stream.
Separation of users is achieved by the special properties of the codes. The most important is that all codes are orthogonal to each other. In this way, the transmission from a single user can be recovered by multiplying the incoming signal, which contains the signals from all users, by an in-phase replica of the code used at the transmitter. This will pull out the information from the desired user and cancel out the rest of signals.
It is not a coincidence that all 3G cellular standards currently being deployed, in Japan, US and Europe, have chosen CDMA as the multiple access technique. CDMA has proved to have certain advantages over FDMA and TDMA ( [Gilhousen91], [Lee91], [Pickholtz91] and [Jung93]) the most important being the increased system capacity it offers. This improvement is due to the total frequency re-use of CDMA systems, that is, the same frequencies can be used in all cells. It is important to mention that for this frequency re-use to be feasible, an accurate power-control mechanism must be employed, to ensure that transmitters far away from the base station are not shadowed by users close to the base station (near-far problem).
Recent advances in spatial signal processing and antenna technology ( [Winters98], [Kohno98]) have paved the way for a new method of multiple access called space division multiple access (SDMA). In this scheme, users are separated by virtue of their location.
Separation of users is achieved with the use of highly directive antennas which are able to track the position of receivers (smart antennas) and direct the beams in their directions. The UMTS standard gives the possibility of using this type of antenna at the base station with the goal of increasing the system capacity.

SYNCHRONISATION
Two sequences of events are said to be synchronised when the events in one sequence and the corresponding events in the other occur simultaneously. The process of making a situation synchronous and maintaining it in this condition is called synchronisation ([Haykin01]).
In general, three levels of synchronisation are required: • Phase synchronisation • Symbol synchronisation • Frame synchronisation Phase synchronisation only applies to receivers that make use of coherent demodulation. The basic device to perform this synchronisation is the phase locked loop (PLL), a device that generates a carrier whose phase difference in minimised with that of the incoming signal.
Detailed descriptions of PLL and its variants can be found in [Stremler90]. Increasingly, classical PLL circuits are being replaced by DSP systems that perform the synchronisation in the digital domain. This algorithmic approach formulates the carrier recovery process as a problem of maximum likelihood estimation of a parameter (i.e. the phase). Descriptions of these techniques can be found in Chapter 10 of [Sklar01] and Chapter 6 of [Haykin01].
Symbol synchronisation is the process of determining when a symbol starts and when it finishes or, in other words, at which point the modulation can change state. This knowledge is essential in order to determine the correct interval over which the received power must be integrated prior to making a symbol decision. There are two basic methods to achieve symbol synchronisation: open loop and closed loop. In open loop synchronisation, the receiver recovers a replica of the transmitter data clock using only the incoming signal. On the other hand, in closed loop systems the clock recovery is performed by comparative measurements of the incoming signal and the locally generated clock. Both methods are covered in detail in [Sklar01].
The last level of synchronisation, frame synchronisation, is required in any system in which information is grouped in blocks. As an example, in a system where users are timemultiplexed like GSM, boundaries between users must be known in order to route the information appropriately. In this case, notice that synchronisation is mainly a requirement for the transmitter who must send the symbols at very precise instants so that symbols reach the central node (where multiplexing takes place) at the appropriate time. Again, more information on this type of synchronisation can be found in Chapter 10 of [Sklar01]. The RF front end is in charge, among other things, of the conversion from RF frequency to an intermediate frequency or baseband. This down conversion process is illustrated in figure   1.2 by the multiplication of the incoming signal with a sinusoid whose frequency is the carrier frequency (mixing). There are other elements forming part of the RF front end whose purpose is to amplify the signal power while keeping as low as possible noise and interference. Extensive information on RF architectures and techniques can be found in [Smith86] and [Stremler90].
The matched filter is defined as follows ( [Glover98]): A filter which immediately precedes the decision circuit is said to be matched to a particular symbol pulse if it maximises the output SNR at the sampling instant when that pulse is present at the filter input. Typically the filter is matched to the transmitted symbol shape, which in turn has been generated by shaping an impulse with a pulse shaping filter. The function of the pulse shaping filter is to limit the required bandwidth to transmit the information. The most usual choice for matched filter and pulse shaping filter is the square root raised cosine filter (SRRC) whose combination forms a raised cosine filter. Matched filters are implemented as integrators (with an appropriate shaping) whose output is sampled at symbol rate.
In this previous definition of a matched filter, it is assumed that the channel is ideal in the sense that although it may introduce additive white Gaussian noise (AWGN), it does not induce any other type of interference. Under these conditions, the matched filter is the optimum detection structure. If the channel does introduce distortion, such as due to multipath propagation in wireless environments, the matched filter is no longer adequate. In this situation, the optimum receiver structure can be shown to consist of a matched filter followed by an infinite tap-delay line which weights the outputs of the matched filter ( [Gitlin92]). This infinite tap-delay line is what is normally called an equaliser. The reason why the equaliser appears in a dashed box in figure 1.2 is to denote that this subsystem is optional. As has been mentioned before, if there is no distortion, no equaliser is needed.
Obviously, when implementing the equaliser only a finite tap-delay line can be used. For the time being nothing else is said about the equaliser as equalisation methods are explained in detail in the next chapter.
As a last step in the demodulation phase, the symbol detector will map the soft output of the equaliser or matched filter to the nearest possible symbol.

Mobile channels
Most communication channels degrade the transmitted signal in one form or another. The most obvious type of degradation is AWGN, which is caused by the thermal motion of electrons present in all dissipative components such as resistors.
A simplified model for a wireless channel could be constructed assuming there are no interposing objects between transmitter and receiver. In this case, the only two effects to be taken into account would be the AWGN and the free space path loss. Such a model could be appropriate for a satellite link where a direct path, free of echoes, exists between transmitter and receiver.
In the case of mobile radio communications, the simple model described previously is not adequate, as transmission takes place near the ground. This implies that the propagation of the signal is subject to reflection, diffraction and scattering from objects in the environment where communication take place ( [Rappaport96]). Reflection results when the propagated wave hits objects whose dimensions are large when compared with its wavelength. This is the case when waves hit buildings, walls or the earth surface. Diffraction occurs when the transmitted signal encounters objects with sharp edges, giving rise to a bending of waves around the obstacle. The last effect, scattering, is due to the propagating wave encountering objects which are small in comparison with its wavelength. Trees, lamp posts and other small objects cause the transmitted wave to be scattered.
All these propagating mechanisms make the transmitted signal arrive at the receiver via multiple paths. This phenomenon is called multipath propagation. Moreover, as a mobile user or some of the objects in his surroundings move, the multipath profile changes, causing fluctuations in the received signal's amplitude or phase, giving rise to what is called multipath fading. The characterisation of both phenomena and their relation were first described in [Bello63].
Multipath propagation and fading pose important limitations on the transmission of information over the mobile channel. Both mechanisms are now described in some more detail. This discussion follows very closely the one presented in [Sklar97a] and [Sklar97b].
The most obvious way to characterise a communication channel is by its channel impulse response (CIR). In the power domain, the channel can be seen as a power delay profile showing the maximum excess delay, denoted by T m , between the first and last received components. This is shown on the left-hand side of figure 1.3.
The relation of T m to the symbol period, T s , is of fundamental importance as it largely determines the type of degradation introduced by the channel. When T m <T s , all the received multipath components arrive within the symbol period. In this case, the channel is said to be frequency non-selective. This condition means that there is no interference between successively transmitted symbols. Still, some degradation occurs as the different components may add up destructively and cause a drop in the received SNR. In order to compensate this effect, some form of diversity or channel coding should be used.
If T m >T s , neighbouring symbols interfere with each other causing intersymbol interference (ISI). This type of channel is frequency selective. Frequency selectivity can be reversed by the action of an equaliser whose operation is described in detail in the next chapter.
Taking the Fourier transform of the power delay profile, the channel can be described in the frequency domain. The resulting function, shown on the right-hand side of figure 1.3, represents the correlation between the channel's response to two sinusoids as a function of their frequency difference. The range of frequencies over which the channel passes all spectral components with the same gain and linear phase is termed the coherence bandwidth, denoted as f 0 . Defining the signal bandwidth, W, as the inverse of the symbol period, W=1/T s , the frequency selectivity of the channel can now be expressed in frequency domain terms. When f 0 >W, all the spectral components of the transmitted signal go undistorted through the channel and the channel is frequency non-selective. If on the other hand, f 0 <W, the channel will distort some of the frequency components of the signal making the channel frequency selective.
So far, the effects of multipath propagation have been described. These would apply to any wireless channel, mobile or fixed. In the specific case of a mobile channel, another effect, time variance, needs also to be considered.

Reconfigurable communication systems
The general area in which this research project started was reconfigurable signal processing for mobile terminals. The term "reconfiguration" involves two different concepts. The first one would refer to reconfiguration among different standards. The second one would deal with performance reconfiguration, that is, the adjustment of the parameters of a radio transceiver according to the specific conditions in which it is operating.
The diversity of mobile standards around the world makes the idea of inter-standard reconfiguration for mobile handsets attractive. Terminals able to function in different standards have already appeared in the market, an example being the dual band GSM phones which are able to work in the 900 MHz and 1.8 GHz (PCS system) bands. However, this can be regarded as a very limited form of standard reconfiguration, as in both systems the baseband processing is identical. Moreover, the band reconfigurability is achieved with the crude approach of duplicating the RF front end, one for each of the frequency bands.
Reconfiguration among completely different standards such as GSM, IS-95 or UMTS is far more problematic given the differences among the protocol stacks of these systems and the baseband functions performed on each of them. The approach of integrating a corresponding transceiver for each of the supported standards would invariably lead to bulky and heavy handsets, therefore a more elegant approach is needed.
A high degree of reconfiguration could be achieved with the concept of software radio The work on this thesis, focuses in the latter type of reconfiguration, performance reconfiguration, albeit in our case, the reconfiguration takes place at the receiver. A detailed explanation of the objectives of this work follows next.

Objectives of the thesis
The subject of this thesis is equalisation for mobile terminals. As has been mentioned in section 1. The above paragraph was written in the context of a proposed new type of mobile network based around the idea of infostations ( [Goodman97]). However, the problem it poses is equally challenging in the context of conventional cellular systems. The question can be generically stated as: How can the equaliser in a mobile handset be reconfigured in order to exploit the specific environmental conditions in which it is operating at one specific moment in time? The term "exploit" in this question can mean improvement in the performance of the equaliser (reduction of the BER) or reduction of the computational complexity which in turn implies a decrease in the power consumption. In our work, we focus on the latter objective, as power consumption is a scarce resource in any mobile handset. The specific type of reconfiguration studied is the variation of the length of the filters making up the equaliser.
To further reinforce the motivation and importance of this work, another very significant fragment from another paper, [Treichler96] pp. 73-75, is also reproduced: Although again in a different context (voiceband modems) from the one of our interest, this paragraph illustrates the importance and difficulty of properly adjusting the equaliser length.
A trivial approach would be to make the equaliser long enough to be able to compensate the worst scenario the mobile can encounter. However, in the context of mobile radio communications, where there is a great variety of possible channel profiles, this strategy is too pessimistic and, most of the time, would imply a great waste of resources. Moreover, in the thesis it will be shown that under certain conditions, short equalisers perform better than longer ones.
The objective of this thesis is to present dynamic and efficient techniques to adjust the equaliser length of a mobile handset according to the specific environmental conditions. The aim of these methods is to reduce the number of computations used in the equalisation process without introducing any performance degradation. The focus is on the two most common structures used for adaptive equalisation: linear equalisers (LE) and decision feedback equalisers (DFE).

Organisation of the thesis
Chapter 1 has introduced different general aspects of mobile systems such as the main elements of the transceivers, characteristics of mobile channels and a brief overview of the most popular cellular standards.
In chapter 2, a detailed description of equalisation is provided. The most common equalising structures are presented alongside with the adaptive algorithms used to adjust their coefficients. The chapter concludes by showing how equalisers can be used in different types of systems (TDMA and CDMA).
Chapter 3 describes the simulation environment implemented. Simulations results are presented for the algorithms and structures introduced in chapter 2.
In chapter 4, mean squared error (MSE) expressions are derived for two popular adaptive algorithms used to drive a linear equaliser. The derivations follow closely [Widrow76] and [Eleftheriou86] for the system identification case, but adapt the results to the system inversion problem.
The derived MSE expressions in chapter 4 provide the basis for the development of several algorithms controlling the length of a linear equaliser (LE). These algorithms are presented in chapter 5, including simulation results that verify their performance.
Chapter 6 extends the MSE expressions to the decision feedback equaliser (DFE) and discusses the importance of the length of the feedforward and feedback filters. Following this discussion, an algorithm is derived to control the length of the feedback filter.
In chapter 7, the performance of the length update algorithms for the LE and DFE is verified in a much more realistic environment using accurate mobile channel models.
Chapter 8 introduces some important aspects that need to be considered when implementing signal processing algorithms on real hardware. It then describes how the length update algorithms have been implemented on a commercial digital signal processor (DSP).
Simulation results obtained using the algorithms on the DSP are also shown.
In chapter 9, the main conclusions obtained from this project are stated alongside with some suggestions for further work.
The thesis finishes with a complete list of the bibliography used for this work.

Thesis notation
Given the large number of equations and mathematical formulas over the thesis, some notational conventions are now in place. Following the common notation found in the literature, scalars are denoted by lower case non-bold letters, vectors use lower-case bold letters and matrices are denoted by upper-case bold letters. If the dimensions of vectors and matrices are not specified it is assumed that they are arbitrary.

ADAPTIVE EQUALISERS: STRUCTURES, ALGORITHMS AND APPLICATIONS
This chapter presents a thorough coverage of equalisation techniques. In section 2.1, the concept of optimum filtering, also known as Wiener filtering, is introduced. This important topic forms the theoretical basis upon which the design of equalisers, and many other devices, is based. Section 2.2 covers the main equaliser structures used in digital communications. In the specific case of wireless applications, where the channel is unknown and/or time varying, the equaliser needs to be able to adjust and track the specific channel conditions, therefore its parameters need to be made adaptive. The most common algorithms to perform this filter adaptation are introduced in section 2.3. Finally, section 2.4 presents the role equalisers play in different types of receivers, in particular, TDMA and CDMA systems.

Wiener filter theory
The design of conventional digital filters is usually performed in the frequency domain.
Typically, filter specifications are given specifying which frequency bands should be present at the output of the filter. Then the designer uses one of the many techniques available to design the filter ( [Mitra01]) which ends up producing a set of time-domain coefficients giving the desired frequency response. An example of this type of procedure could be the design of a filter to eliminate the 50 Hz interference coming from the mains.
On the other hand, there are situations where the filter is required to minimise a certain error measure. In this case, the filter is normally designed using time-domain methods. The design of optimum filters falls into this latter category. A filter is said to be optimum in a given criterion, when the error between its output and a required output is minimised with respect to that particular criterion. The most generic configuration of the problem of optimum filter design is depicted in figure 2.1. The filter accepts as inputs an observed sequence, u(n), and a desired or required sequence, d(n). By desired sequence is meant the sequence that ideally should be produced at the filter output given the observed sequence. Instead the filter output is y(n). The difference between the desired output and the filter output is used to form an error signal, e(n)=d(n)-y(n), which gives an idea of how well the filter is performing. The task of the designer in this case is to design a filter which a minimises a particular function of the error, f(e).
A common choice for the error function is the mean squared error (MSE), defined as: where E denotes the statistical expectation operator and D is an integer accounting for the delay (in samples) of the filter. For simplicity and without loss of generality we assume from now that the delay is zero. Filters which minimise the MSE between its output and the required output are called Wiener filters.
The MSE can be expressed as a function of the filter weights: It is now possible to minimise the error function by deriving the MSE with respect to the filter weights and equating the resulting expression to zero: Solving this partial derivative equation and after some manipulations (see [Haykin96] or [Mulgrew98]), the following expression is found: where R is the autocorrelation matrix of the input vector, R=E[u(n)u(n) T The MSE level achieved when using this set of filter weights is called the minimum MSE (MMSE) and is given by: The MSE as a function of the filter weights can be represented as a multidimensional bowlshaped surface. The Wiener-Hopf equation computes the filter coefficients whose output MSE is the bottom (minimum) of this surface.
The Wiener-Hopf equation is a very general method for solving linear estimation problems and can be applied to many apparently different problems such as system identification, system inversion, linear prediction and interference cancellation (see introductory chapter in [Haykin96]).
Channel equalisation is a particular case of a more general problem known as system inversion, which is also found in other contexts, such as acoustic processing or control theory. Finally, it is also important to mention that, although the most common, the MSE is not the only criterion used in the design of optimum filters. In this chapter, some other criteria will also be applied and their pros and cons with respect to the MSE will be discussed.

Equaliser structures
The ultimate performance criterion in a digital communication system is the bit error rate (BER). However, due to its non-linearity, it is difficult to analyse a system on the basis of the BER, therefore alternative measures are needed. The most commonly used is the MSE just introduced. Over the years, different relations have been established between MSE level and BER, one of them being the Saltzberg bound ( [Saltzberg68], [Gitlin92]). The Saltzberg bound indicates that a decrease in the MSE level will usually, although not always, lead to a reduction in the BER. This allows us to work with the MSE as a performance metric with the reassurance that benefits observed from an MSE point of view will, most likely, imply reductions in the BER.
In this section, different equaliser structures are introduced whose purpose is the minimisation of the MSE although another criterion is also briefly covered (zero-forcing equalizers).
Most of the structures shown next are suitable for adaptive and non-adaptive implementation. In the non-adaptive case, the designer, with perfect knowledge of the channel, can calculate the optimum 2 equaliser a-priori as has been shown in the previous section by solving the Wiener-Hopf equation. When the equaliser is adaptive, algorithms like those presented in the next section are used to adjust the filter coefficients.
The information of this section has been extracted from [Proakis96], [Gitlin92], [Haykin01], [Benedetto99] and [Qureshi85]. This latter reference is particularly useful as it provides a comprehensive survey of all the classic equalisation methods. Chapters 7 and 8 in [Gitlin92] are also especially helpful on the topic of equalisation as they compile many of the ideas that appeared in the Bell Systems Technical Journal during the 70s and early 80s.   [Benedetto99] and [Qureshi85]. Here, only the final result is presented, which in the frequency domain is given by: where W(f) represents the equaliser response in the frequency domain, that is, the discretetime Fourier transform (DTFT) of the values obtained from solving the Wiener-Hopf equation. Note the important fact that, because the equaliser has an infinite number of taps, the frequency response is continuous. S(f) is the frequency response of the convolution of the pulse shaper, channel and matched filter, or equivalently, the DTFT of the samples entering the equaliser. N 0 is the power spectral density of the AWGN.
The DTFT of the equalised signal, Y(f), is then given by: (2.8) shows that, in the event of very low noise level (N 0 close to zero), Y(f)=1, which means that the system does not introduce any distortion. Notice that Y(f) represents the frequency transform of all the elements between the symbols source and the detector at the receiver. Y(f)=1 corresponds, in the time domain, to an impulse response function which is the unit operator for the convolution, indicating that what is sent, gets to the receiver undistorted.
The problem arises when N 0 is significant. In this case, Y(f)≠1, which in the time domain implies the presence of ISI terms in the detection process. This problem is especially important when the channel presents spectral nulls in the passband, a situation common in mobile radio channels. As it will be seen in later chapters, this strongly limits the action of the equaliser.
When the equaliser is limited to a finite number of taps, a performance degradation (increased MSE) occurs with respect to the infinite case. The amount of this degradation is difficult to quantify a-priori as it depends very much on the particular channel, equaliser length and noise level. In chapter 5, a detailed coverage of the effect the equaliser length has on the MSE performance will be presented.
For the sake of completeness, it will be mentioned that another popular criterion to design linear equalisers is known as the peak criterion ([Proakis96]). In this case, the equaliser is forced to produce zero-ISI samples at its output. For this reason, they are normally called zero-forcing equalisers. Their frequency response is given by: where S(f) is again the frequency domain expression for the convolution of the pulse shaper, channel and matched filter. When there is no noise, the MSE-LE and ZF-LE have the same expression as can be inferred from equations (2.7) and (2.9). However, when N 0 is significant, the resulting equaliser expressions are quite different as the ZF-LE does not take into account the noise level. Consequently, the ZF-LE may induce large noise enhancements while trying to cancel out all the ISI. In general, the MSE-LE offers better performance than the ZF-LE and is usually the preferred method to design equalisers.
The main advantages of linear equalisers are their simplicity, their tolerance to changing phase channels (going from minimum to maximum phase) and their immunity to decision errors. This last point will be better understood when the LE is compared with decision feedback equaliser (DFE). The main drawback of LE is its sensitivity to noise level which in some situations can make the equaliser completely useless.

Decision feedback equaliser
The idea of decision feedback equalisation (DFE) was introduced by Austin in 1967 ). The MSE design of DFEs was presented in [Salz73]. Some more properties, along with comparisons with maximum sequence likelihood receivers (see section 2.2.4), were presented in [Belfiore79]. The review provided by [Qureshi85] also covers the basics of DFE.
In order to understand the principle of DFE, it is first important to have an idea of a typical channel impulse response. Figure 2.4 presents a hypothetical impulse response of a communications channel when sampled at the symbol rate. Generally, the main pulse of energy, the one onto which detection is performed, gets to the receiver with a certain delay.
Due to the multipath effect, additional energy arrives before and after the main pulse causing precursor and postcursor ISI respectively. The idea behind DFE is that once a symbol has been detected, its postcursor interference can be perfectly cancelled, as the symbol is already known. The precursor ISI is handled with a conventional linear equaliser. Figure 2.5 shows the structure of a DFE. It has two FIR filters; one a feedforward filter (FFF) which acts as a LE, and the other a feedback filter (FBF) which performs postcursor cancellation. The inputs to the FFF are the samples coming out of the matched filter whereas the inputs to the FBF are the previously detected symbols.
It is important to recognise that the DFE is a non-linear structure because of the symbol detection used to form the inputs to the FBF. The MSE analysis of the DFE is difficult because of its non-linearity. However, the structure shown in figure 2.5 can be linearised by assuming that the decisions being made by the detector are correct 3 . This assumption allows the Wiener-Hopf equation to be applied in a similar way as for the LE. This derivation is rather long and not included here, but can be found in [Salz73] or [Gitlin92].
The greatest advantage of DFE over LE is the avoidance, in great measure, of any noise enhancement. This is explained by the observation that the FBF works on noise-free samples. As a consequence, the MMSE-DFE achieves a much lower value than the corresponding MMSE-LE when the channel is heavily distorted, i.e. has a spectral null, as it will not raise the noise floor when compensating spectral gaps.
In a real scenario not all symbols will be correctly detected. In this situation, the DFE inherits a new problem, namely, error propagation. When a symbol is wrongly detected it will also be fed back to the FBF producing a wrong cancellation tail. This, in turn, will reduce the noise margin for the detection of subsequent samples. Fortunately errorpropagation is not catastrophic ( [Benedetto99]) and although its effects tend to make the real DFE performance worse than predicted by the Wiener-Hopf equation, in most cases, its performance is still better than that of the LE. Still, it should be noted that there is no conclusive proof that the DFE will outperform the LE under any conditions. More will be said about error propagation in section 6.9.
The application of DFEs to multipath fading radio channels is treated in detail in [Foschini82].

Fractionally spaced equaliser
Fractionally spaced equalisation (FSE) is a modification applicable to any of the two structures introduced previously, LE and DFE, rather than a structure by itself. However, given its importance it is treated separately. It was first proposed in 1969 in an unpublished work by A. Gersho of Bell Labs ( [Benedetto99]) and later popularised by [Ungerboeck76] and [Gitlin81]. A more recent tutorial on FSE appeared in [Treichler96].  Before describing its benefits, there are two important points to note about the structure shown in figure 2.6. First, notice that although the sampling rate at the input of the equaliser is double the symbol rate, the equaliser output is sampled at symbol rate. In figures 2.3 and 2.5, the sampler before the detector was not shown as it was clear that the whole system was working at symbol rate. Now the sampler is made explicit in order to emphasise that the equaliser inputs and outputs are sampled at different rates.
The other important point to mention is that FSEs need more taps than symbol spaced equalisers to cover a certain time span. For example, if N taps are used in a conventional equaliser, 2N taps will be needed in a T/2-FSE covering the same time span. This has important consequences from a computational point of view, as FSEs tend to be much longer than symbol spaced equalisers.
FSEs offer two very important advantages, so important, that nearly all equalisers implemented in real communications receivers are fractionally spaced.
The first of these advantages is related to the bandwidth of the transmitted signal. In principle, given a particular bit rate, f 0 =1/T 0 , a signal with minimum bandwidth occupancy could be realised by transmitting sinc pulses (chapter 8 in [Glover98]). In this case, the signal bandwidth would be limited to 1/2T 0 . In practice, this is not possible, as it would require the use of ideal filters, which are not realisable, and an extremely precise sampler at the receiver. The alternative is to use filters (pulse shapers) that produce a bandwidth expansion (excess bandwidth) with respect to the minimum case. If these pulses are transmitted and they are sampled at the receiver symbol rate, aliasing will occur as the Nyquist sampling criterion is not satisfied because of the bandwidth expansion. This is the situation that takes place in a symbol-spaced equaliser. On the other hand, if samples are taken fast enough so as to satisfy the Nyquist sampling theorem, no aliasing results at the input of the equaliser, allowing the equaliser to modify independently any frequency band of the received signal. Fractionally spaced equalisers are designed so that the Nyquist sampling theorem is satisfied at their input. In this way, MSE levels lower than for equivalent symbolspaced equalisers are achieved.
The second important property of FSEs lies in their capability to correct timing phase without raising the noise floor. This compensates any delay (phase) distortion without noise enhancement and relaxes the synchronisation mechanisms at the receiver.
Both facts, avoidance of aliasing and compensation of delay distortion, make FSEs the preferred choice, rather than symbol spaced filters, to implement LEs or the FFF of DFEs.
Notice in this latter case that the FFF is the only filter in the DFE whose taps can be fractionally spaced. Given that the outputs of the DFE (inputs to the FBF) are generated at symbol rate, the FBF must also be symbol spaced.
Mathematical derivations proving the advantages of FSEs can be found [Ungerboeck76], [Gitlin81] and [Gitlin92]. A recent treatment on the optimum design of MSE-FSE-LE appeared in [Casas97].

Other multipath mitigation structures
Over the years, many different techniques to counteract the effects of the channel have appeared. Some of them are variations of the LE or DFE, while some others rely on completely different principles. Our work in later chapters is solely based on LE and DFE.
However, for the sake of completeness, a brief account of some of these other techniques is presented. The first methods described below, pre-equalisers and cancellers, are modifications of the DFE. The application of maximum likelihood sequence estimation as a method to compensate ISI is presented next. The last structure, the RAKE receiver, is mentioned briefly, as it will be covered in more detail in section 2.4.2. This section concludes with a quick list of and brief comments on some other methods that have recently appeared in the literature.

PRE-EQUALIZATION
Pre-equalisation, also known as Tomlinson-Harashima precoding, was simultaneously proposed by [Tomlinson71] and [Harashima72]. The main idea of this scheme is to move the feedback filter of a DFE to the transmitter side so that the symbols sent through the channel have their post cursor ISI already suppressed (i.e. pre-equalised). Given that the symbols are known at the transmitter, error propagation is avoided.
For this technique to work, the transmitter should have perfect knowledge of the channel impulse response, which limits its usage to systems whose CIR is fixed and known or to systems in which there is a feedback channel between transmitter and receiver. In this latter case, the receiver has the additional task of estimating the CIR.
The combination of Trellis coded modulation with pre-equalisation has been studied in [Forney91].

CANCELLERS
Cancellers are another extension to the DFE original structure proposed in [Gersho81]. The idea is to cancel the precursor ISI in addition to the postcursor ISI. To this end, the canceller is preceded by a conventional LE that provides tentative decisions about future samples whose ISI (precursor) is then subtracted from the symbol being detected. Cancellation of the postcursor ISI is achieved in a similar fashion to the DFE by feeding back the symbols already detected.

MLSE
Maximum likelihood sequence estimation is a rather general block technique which, given an observed sequence, selects the one which most likely has been transmitted. It has already been introduced in Chapter 1 as a method for decoding convolutionally encoded sequences.
The application of MLSE to the detection of symbols corrupted by a linear distortive channel was proposed in [Forney72]. Using the Viterbi algorithm ( [Forney73]) the complexity of this nearest neighbour detection can be shown to be L M where L is size of the alphabet and M the channel dispersion or channel memory.
The main drawback of this approach is that its computational complexity grows exponentially with the channel dispersion, therefore its use is only feasible in channels with a short impulse response.
The application of MLSE for ISI removal is often known as Viterbi equalisation and is the preferred equaliser structure in the GSM system. It is important to mention that the symbol rate in GSM is relatively low and the channel dispersion is limited to 4-6 symbol intervals.
This means that the Viterbi equaliser only has to perform the search and detection among 2 4 -2 6 possible sequences. Full explanation of the GSM Viterbi equaliser can be found in [Sklar97b]. The exponential dependence of the computational complexity on channel dispersion precludes this method from being used in very high bit rate systems where channel dispersion extends over many symbol periods. Concluding this quick review of different equalising structures, it must be mentioned that the combination of equalisation and diversity reception has also been covered by different authors, the main references being the thorough treatments given in [Balaban92a] and [Balaban92b]. In these papers, it is shown that this combination can lead to reductions of up to two orders of magnitude in the BER with respect to single branch receivers. In Unfortunately, in the context of mobile systems, use of diversity in the downlink is rather limited due to the reduced physical dimensions of mobile handsets.

Adaptive algorithms
Most of the structures described in the previous section can be used to mitigate the effects of known static channels. In that case, their parameters (i.e. filter taps) can be computed apriori. However, in most practical situations, certainly in the case of mobile radio systems, the channel is unknown and time varying. Under these conditions, the equaliser parameters must be adaptable and able to respond to the channel changes. This is the reason why equalising systems are typically implemented using adaptive filters, which can be defined as digital filters whose coefficients vary with time.
In order to drive the equaliser coefficients, an adaptive algorithm must be used. This section describes the most common algorithms to perform this task. These algorithms can be broadly divided into gradient methods and least squares methods. They are covered in sections 2.3.1 and 2.3.2 respectively. Section 2.3.3 introduces a particular low computational complexity least squares method.
Before each technique is presented in some detail, a few general comments must be made.
All the methods presented, have as an objective the computation of the Wiener-Hopf equation in a recursive way. This procedure has two important benefits. First, no knowledge of the channel is needed a-priori as the algorithms are able to learn from the observed data.
Second, a huge reduction in the computational complexity of the solution to the Wiener-Hopf equation is achieved when compared with the direct solution 5 of equation (2.5). These benefits, however, do not come for free. The penalty to pay is that the filter will have to undergo a convergence process before it achieves its near optimum values. Moreover, the steady-state filter values will not exactly coincide with those of the Wiener-Hopf solution as, in general, adaptive algorithms add some form of error (excess error). This will be covered in detail in chapter 4.
The presentation of the algorithms in the following subsections is done in the context of FIR filtering. As has already been mentioned, IIR filtering present some inconveniences that, at the moment, greatly limit their application in real systems. For tutorial review of adaptive IIR filtering see [Shynk89]. where adaptive filters with orders of a few thousands taps are not uncommon. In [Shynk92] a review of frequency domain techniques can be found.
The main reference for the information presented in next sections is the comprehensive textbook by Haykin ([Haykin96]), and also [Farhang-Boroujeny98] and [Mulgrew99].

Least mean squares algorithm and variants
The least mean squares (LMS) algorithm is the most widely used adaptive scheme due to its simplicity and robustness. It was originally proposed in [Widrow60] and since then a huge number of variants and applications have appeared in the technical literature.
The LMS algorithm is derived from a general technique known as steepest descent (SD), which is often used in optimisation problems. In section 2.1 it has already been stated that the MSE, as a function of the filter weights, has the shape of a multidimensional bowlshaped paraboloid with a single minimum. The SD algorithm finds the minimum MSE (MMSE) point by computing the gradient vector of the MSE, that is, the direction of maximum MSE increase, and then updating the coefficients one step in the opposite direction (maximum MSE decrease). By iterating this basic procedure, the filter weights will converge to the values producing the MMSE. The algorithm is given by the equations: In the above equations, ) n ( MSE ∇ denotes the gradient vector of the MSE, R is the autocorrelation matrix of input data, p is the cross-correlation vector between the desired and observed data and w is the filter weights vector. All these vectors have length equal to the filter order (N). The parameter µ is an arbitrary step size that defines the amount of correction applied to the filter weights. The derivation of equation (2.10) can be found in pp.
From a practical point of view, the SD algorithm has one important problem: typically, R and p are unknown in real situations, and therefore the exact gradient of equation (2.10) cannot be computed.
Fortunately, an estimation of the gradient vector can be computed from the available data.
This estimated gradient, where d(n) is the desired output value. We use a different notation for the filter weights used, ) n ( w , to emphasise that they are computed using an estimated (noisy) gradient.
Using this estimated gradient vector, rather than the exact one, in equation (2.11), gives rise to the LMS algorithm: Notice that the complexity of the algorithm given by equations (2.13) and (2.14) is only O(2N) where N is the order of the filter.
The general analysis of the LMS algorithm in stationary and non-stationary scenarios was presented in [Widrow76]. Other papers have presented additional analytic results for particular applications. In the case of equalisation, [Ungerboeck72] is particularly important as it analysed for the first time the transient behaviour of adaptive linear equalisers employing the LMS algorithm. [Gitlin79] analysed the behaviour of the LMS linear equaliser when the filter is implemented in finite-precision arithmetic.
Complete derivation for most of the analytical results for the LMS can be found in a unified way in chapter 9 of [Haykin96]. Additionally, in chapters 4 and 6 of this thesis, some of these results are re-derived for the specific case of equalisation. This last result about convergence has a special relevance for the case of equalisation. It can be proved ( [Gray72], [Ungerboeck72]) that, in the case of equalisation, ) (R χ is bounded by the maximum and minimum values of the channel power spectral density. This in turn implies that in channels presenting frequency selectivity, the equaliser may exhibit a slow convergence. This effect is very noticeable if the channel spectrum contains a null in the passband.
Also, notice the conflicting requirements for the selection of µ. If the step-size is large, convergence might be accelerated at the cost of a higher steady-state MSE. On the contrary, if µ is chosen to be small, the steady-state MSE will approach that of the Wiener solution but convergence time will be much longer. Often a compromise µ is chosen in the middle of the stability region, i.e.: 2 ) n ( 3 1 u = µ A step size is typically chosen with the help of computer simulations. Its value is also dependent on the non-stationarity of the channel as the step size, µ, needs to be large enough to allow an adequate channel tracking. In order to improve the performance of the LMS algorithm, a number of variants have appeared, improving some of its deficiencies. Two of them are explained below as they have been extensively used throughout this project; they are the normalised LMS (NLMS) and the variable step size LMS (VSLMS).
The NLMS algorithm differs from the conventional LMS in that the correction applied to the filter weights is normalised with respect to the power of the input vector. In this way, gradient noise amplification due to large input samples values is avoided. The algorithm is given by: to be stable (i.e. MSE convergent), the step size must satisfy the following relation: The main advantage of the NLMS is that by avoiding the gradient noise amplification, the algorithm has the potential to convergence faster. Simulation results in the next chapter confirm this fact. The major drawback is an increase in computational complexity to O(3N), and the need to perform a division. This latter point might be an issue in custom hardware structures.
The VSLMS algorithm, as its name suggests, dynamically varies the step-size in order to overcome the conflicts of a static step-size. Initially, µ has a large value (close to the upper stability limit), so that convergence is accelerated. As the filter converges toward its steady state, the value of µ is decreased in order to reduce the steady state MSE. Algorithms implementing this idea have appeared in [Kwong92], [Mathews93], [Aboulnasr97] and [Woo98]. The one implemented in our system is the algorithm in [Kwong92], which adds an extra equation to those given by the conventional LMS (equations 2.13 and 2.14). This additional equation is the step size update and is given by The parameter a is an exponential forgetting factor used to give more importance to recent data. The variable ρ is typically a very small positive value determined by the steady-state level required. In our work, their values have been determined by simulation.
Over the years, many other LMS variations have appeared in the literature. The sign-error-LMS algorithm introduced by ([Gersho84]) only uses the sign of the error to update the filter weights, that is, multiplication by either 1 or -1. Performance degradation can be observed in the sign-LMS algorithm when compared to the plain LMS. However it has the advantage of being implemented in a very efficient way on hardware. The self-orthogonalising-LMS algorithm proposed in [Gitlin77] pre-multiplies the weight correction term of the LMS algorithm (equation 2.14) by the inverse of R. This has the effect of whitening the input to the equaliser which in turn reduces its eigenvalue spread and accelerates its convergence.
The main drawback is its computational complexity, which grows quadratically with the filter length. In [Sari82], a variation of the self-orthogonalising-LMS is presented with reduced computational burden. Finally, several variants of the LMS algorithm ([Aboulnar99] and [Douglas97]) have appeared where only a subset of all the coefficients in the filter is updated.

RLS algorithm
The recursive least squares (RLS) algorithm overcomes most of the performance inconveniences of the LMS algorithm. In particular, it has a very rapid convergence rate as in approximately 2N iterations (N = filter length) finds the set of filter weights approaching the Wiener solution. Moreover, in the case of static channels, it achieves the Wiener solution without any excess error. Additionally, the convergence rate is independent of the eigenvalue spread of the input signal.
All these nice features are achieved by solving the Wiener-Hopf equation in a rather different form than the LMS algorithm. In order to explain the RLS algorithm, first the least squares principle will be introduced and then it will be explained how the algorithm can be made recursive. A thorough review of least squares techniques has recently appeared in [Glentis99].
Recall that LMS finds the MMSE solution by applying a gradient descent along the MSE surface using estimates of the required autocorrelation and cross-correlation functions. The is the temporal correlation matrix of the input data and z is the temporal cross-correlation between the input vector and the desired output. The optimum filter weights are given by: to the RLS algorithm is rather long and can be found in [Haykin96], [Mulgrew98] or . Here only the final form of the algorithm is shown.
Inversion of the input (2.24) correlation matrix The vector k(n), historically called the Kalman gain, represents the gain applied to the error signal, ) n ( ζ , to update the filter weights. P(n) is the inverse of the input correlation matrix, Its recursive computation appears in equation (2.24). The parameter λ is a forgetting factor that weights more importantly new data over older data 7 . If the channel is static then λ is set to 1. If the channel is time-varying, λ will have a value close to, but less than 1. It can be shown (pp. 563-564 in [Haykin96]) that when λ<1, the RLS algorithm no longer converges exactly to the Wiener solution since, as with the LMS algorithm, an excess error is introduced.
There are several methods to initialise the RLS algorithm. The procedure used in this thesis is called soft-constrained initialisation. This technique initialises the algorithm by setting The RLS algorithm represents a major reduction in complexity with respect to the original formulation of the least squares problem given by equation (2.19). However, from equations (2.21)-(2.24) it is found that its complexity 8 is still O(2N 2 ), far larger than that of the LMS, which is linear. In applications where the filter has a moderate to large number of taps, such a complexity order may become an issue, especially when the device has power consumption limitations (like a mobile handset). In the next section, a particular class of least squares algorithms is presented that reduces the computational complexity of the RLS algorithm.
Another general problem of the least square approach is that the recursive algorithms tend to present numerical stability problems when implemented on finite-precision arithmetic (especially fixed-point). Sources and solutions to RLS instability have been presented in [Bottomley89] and [Bottomley91].

Fast Kalman algorithms
The previous section showed that the RLS algorithm offers some performance advantages over the LMS algorithm at the expense of a significant increase in computational complexity. This last issue has motivated the search for variations of the least squares scheme with a reduced, preferably linear, computational complexity. The resulting algorithms are generally known as Fast Kalman algorithms. The first such technique found, At this point, it must be reinforced the fact that Fast Kalman and RLS schemes are all the same algorithm but using different formulations.
Fast Kalman algorithms inherit and exacerbate the stability problems of the RLS algorithm when implemented on finite precision arithmetic. The instability may appear in two forms [Moustakides89]. In the first one, explosive divergence, the Kalman gain suddenly becomes extremely large and so do the filter weights. In the second one, lock-up divergence, the Kalman gain tends to zero and the filter coefficients stop being updated. The simplest way to tackle instability is by periodically restarting the filter and algorithm. However, this approach will degrade the performance of the system due to the resets.
More elaborate approaches have appeared, and continue to appear, that algorithmically stabilise the Fast Kalman algorithm. Examples are [Cioffi84], [Botto89], [Moustakides89] and [Slock91]. The common approach in these techniques is to compute some of the variables in the algorithm in two different ways. In infinite precision arithmetic, both methods would produce the same result. In finite precision arithmetic, some discrepancy appears between the two results. This difference is then utilised to apply a correction term to particular variables.
In all these references, the adaptive filter is configured as a channel estimator and the reported results indicate that these approaches successfully prevent the algorithm instability.
In this project, the stabilised FAEST algorithm (SFAEST, [Moustakides89]) has been implemented and extensively tested for the case of channel equalisation. We have found that it works most of the times but occasionally goes unstable. Additionally, the algorithm parameters were difficult to tune to obtain satisfactory performance. Some simulation results with the SFAEST scheme will be shown in the next chapter.

Comparison of gradient and least squares techniques
Concluding this short introduction to adaptive algorithms, it is worth paying some attention at how gradient (LMS) and least squares (RLS) algorithms compare.
During the transient phase, the RLS algorithm clearly offers some advantages over the LMS algorithm, especially if the eigenvalue spread of the autocorrelation matrix is large. For the particular scenario of equalisation, this condition is likely to happen when the E/No is large and the channel is heavily frequency selective. If E/No is low, the spectral gaps of the channel will be less pronounced because of the large noise level, reducing in this way the eigenvalue spread.
Once the filter has converged, the filter will start to track the channel fluctuations. It is important to remark now that tracking is a steady-state phenomenon. Comparisons of the tracking capabilities of LMS and RLS are rather more involved than in the case of convergence and previous studies ( [Eweda94] and chapter 16 in [Haykin96]) have shown that the superiority of one or the other depends on the particular application.
In [Cioffi86] the tracking ability of both algorithms is analysed. It is concluded that in scenarios with large time variations (i.e. abrupt changes), the RLS algorithm has better tracking properties than the LMS. However, it mentions that for this to be true, the variations need to be much larger than those encountered in practical systems.
Also interesting is the work in [Rupp97b] where the LMS-DFE and RLS-DFE are compared in a mobile radio environment. The conclusion is that the LMS-DFE can track as well as the RLS-DFE, provided that the RLS algorithm was used during the training. This suggests a switching of algorithm between training and decision directed mode.
Finally, [Eleftheriou86] observed that if the adaptive filter is very long, the LMS step size will have to be very small to satisfy the stability criterion. This will limit the tracking ability of the LMS filter. Under these conditions, the RLS algorithm has better tracking capabilities. Surveys of equalisation methods and algorithms for TDMA systems can be found in [Proakis91] and [Tijdhof97].

Applications of equalisers to mobile radio systems
Not long ago, a new approach combining the two techniques just described appeared in the literature ( [Lo91], [Shukla91]). This technique, called channel-estimation-based equalisation, first estimates (and tracks) the channel and then, periodically, uses the channel estimate to compute the Wiener-Hopf equation in order to obtain the optimum equaliser settings. These optimum coefficients are then plugged into the equaliser that processes the incoming signal. The advantage this method offers is that, usually, the channel is easier to track than its inverse (direct equaliser).
Over the years many publications have appeared reporting results on equalisation for TDMA or similar systems. A brief account is provided next. In [Lo95] it is shown that the DFE can be used to reduce not only the multipath ISI, but also the effects of co-channel interference.
Similar results were also reported in [Niger91]. In [Lo99] the same topic, reduction of ISI and co-channel interference, is addressed but in this case using a blind (no training sequence)

CDMA systems
Spread spectrum systems have typically used the RAKE receiver to exploit diversity reception using the received signal through different paths ( [Turin80]). The effectiveness of the RAKE receiver depends on the properties of the sequence used to spread the original information signal. If the sequence is well designed, its autocorrelation function will be just an impulse located at zero delay. This means that the original signal, when correlated with any delayed version of itself will be zero.
This autocorrelation correlation property is exploited in the architecture of the RAKE receiver shown in figure 2.7. The RAKE works as follows: first, the path delays are estimated and the P strongest paths are selected (in the figure P=3). A correlator is then assigned to each of these paths. The function of each correlator is to multiply the incoming signal with the same spreading sequence used at the transmitter. The outputs of the correlators are delayed appropriately to synchronise them and then added up together.
Finally, symbol detection is performed. In order for the RAKE to be effective in a mobile scenario, the path delays must be tracked continuously to follow the variations in the channel profile. Using this method, the signal energy coming from the P strongest paths is independently received through different branches, called fingers, and coherently summed.  The RAKE structure just described ignores two effect caused by the multipath propagation.
First, multipath may induce interchip interference (ICI 9 ) degrading the codes' autocorrelation properties. Secondly, and also due to multipath, the orthogonality among different user codes is destroyed. This second phenomenon causes what is called multiple access interference (MAI). MAI is the responsible for the near-far effect (commented in chapter 1) making necessary the use of accurate power control schemes.
In an effort to relax the power control requirements and improve the system capacity, multiuser detectors have been introduced. Multiuser detectors exploit the structure of the inter-user interference in order to cancel it. [Lupas89] is regarded as the seminal publication proposing a receiver architecture to eliminate or reduce the effects of MAI. Since then, many different techniques have appeared on this topic. Concise introductions to this area generically called "multiuser detection" can be found in [Duel-Hallen95] and [Moshavi96].
A more comprehensive coverage appears in [Woodward98].
Many of the multiuser detection techniques published rely on the fact that the receiver has knowledge of all the user codes. This situation is reasonable on the base station side but it is certainly not realistic on a mobile terminal. For this reason, alternative structures have recently been researched for the downlink multiuser detection.
In [Madhow94] and [Abdulrahman94] it is shown how classical adaptive equalisation structures such as the LE or DFE, operating at chip level (rather than symbol), can be used to 9 ICI can be regarded as ISI at chip level reduce significantly the amount of MAI and also ICI. Moreover, they do so just having knowledge of the code of the user being detected. The main idea is to substitute the correlator in a typical receiver by an adaptive structure (LE or DFE) which, after training, will perform the correlation and multiuser interference removal in a single step. As in conventional equalisation this structure is designed to minimise the MSE between a received and a desired sequence.
This concept of chip level equalisation has been recently treated in [Grant99], [Petre00], [Hooli00] and [Wilson93]. Simulation results show that the performance of these structures is clearly superior to that offered by a conventional RAKE receiver.

Training aspects
Concluding this chapter, some attention is devoted to training aspects. Most commercial communication systems operating in unknown environments use some form of training to gain knowledge about the state of the channel. This is especially true in mobile and wireless environment where periodic training is needed in order for the receiver to be aware of the channel variations. Some specific training methods have been proposed such as in [Qureshi77] and references therein. However these methods were proposed in the context of wireline communications where a partial knowledge of the channel spectrum can be assumed. No such a-priori knowledge can be presupposed in wireless scenarios.
Obviously the transmission of a training sequence implies a reduction in the transmission bandwidth of information bits. This fact has spurred the investigation of blind equalisation methods whose origins can be traced back to the publication of [Godard80] where the most widely used blind algorithm, the constant modulus algorithm (CMA), was proposed. A short introduction to blind equalisation principles can be found in [Litwin99]. For a more detailed overview see chapter 18 in [Haykin96].
Recently, two references ( [Boss98], [Labat98]) have appeared studying the use of blind methods in wireless systems. In [Boss98] the feasibility of performing the channel estimation in the GSM system without using the training sequence is considered. In there, it is shown that the proposed blind channel estimation performs only 1.2-1.3 dB worse than the conventional Viterbi equaliser. Clearly, the gain in transmission bandwidth (22% more) would make up for the slight degradation in performance. However, it must be said that the amount of computation for the blind method was not addressed.
In [Labat98] a reconfigurable DFE structure is proposed that is able to adjust its coefficients without any form of training. Simulation results are presented in the context of wireless over-water channels showing that the equaliser does not suffer any performance degradation with respect to the trained counterpart and computational costs remains unaffected. In principle, it seems viable to apply the same structure to mobile scenarios.
Despite these promising results obtained using blind methods, all modern mobile standards, 2G and 3G, rely on some form of training to adapt the receiver to the channel in which they are operating.

BACKGROUND RESULTS
Nowadays, nearly all communications research relies on computer simulations in order to verify the performance of new systems in an efficient and cost effective way ( [Jeruchim92]).
The first objective of this chapter is to present an overview of the simulation environment developed to test the techniques described in later chapters. This rather generic and simple environment is not focused on a particular standard, but the techniques developed in chapters 5 and 6 are applicable to a wide variety of systems. The different channel models used in chapters 4, 5 and 6 are also described in detail here. Results presented in chapter 7, where the environment is configured according to UMTS-like specifications, use more complex system and channel models and will be described there.
The second objective of this chapter is to present some simulation results obtained using the algorithms and structures previously introduced, using the channel models introduced in this chapter. These simulations serve to contrast the theory previously presented with experimental evidence. The results also help us to take some decisions regarding which structures and algorithms to use as a foundation for further study.

Simulation tools
During the first stages of this project a dilemma was whether to use one of the commercial simulation tools (Cossap, SPW, Simulink, SystemView) or to implement a new simulation environment in a high level language such as C. Each option had its pros and cons.
Simulation packages are easy to use and offer a wide range of basic blocks making it easy to put together a whole system for simulation. On the other hand, simulations typically take longer to execute and eventually, C code needs to be written to implement "non-typical" signal processing operations. Implementing the whole environment in C from scratch is a fairly complex task but it gives complete freedom on how to assemble the system. In addition, simulations run considerably faster.
It was finally decided to implement a whole new environment in C, mainly because it was anticipated that many of the new techniques developed would need to be hand coded anyway and later integrated into the simulation tool. The C code was generated using the GNU C/C++ compiler for Solaris Sun workstations. The simulations were mainly run on a Pentium II-350MHz running Linux. Analysis of the results was done using Matlab 5.3.1.
Additionally, Matlab was used for some particular computational tasks such as the calculation of Wiener filters.

System description
The basic model used in the next three chapters is shown in figure 3.1. In the context of this thesis, the words bit and symbol will be used interchangeably as binary phase keying (BPSK) is used throughout the work. We recognise that many of today's mobile/wireless systems allow the use of higher order modulation schemes such as QPSK or QAM which provide superior spectral efficiency in terms of b/s/Hz when compared to plain BPSK.
However, the use of BPSK is justified on the basis that the novel techniques proposed in this work are independent of the modulation order utilised. Use of BPSK eased in great measure the implementation of the simulation environment and adaptive algorithms.
The generated symbols are drawn from a discrete uniform source where both symbols have equal probability of occurrence. The different channel models used are explained in detail in the next section. The noise components are samples of additive white Gaussian noise (AWGN). At the receiver, the equaliser is in charge of compensating for the channel effects in order to provide the threshold detector with better estimates than those coming out of the channel. This subsystem, the equaliser, is where the focus will be in all subsequent chapters in this thesis.  also be required to maximise the SNR at the decision instant. Additionally the receiver would need a subsystem, like a phase locked loop (PLL), to achieve carrier, or at least symbol, synchronisation. During this work, it is assumed that the receiver is appropriately synchronised, which by no means is a trivial task (see [Gitlin92] or [Sklar01]]). Another important subsystem not shown in figure 5.1 is a channel coding system. Nearly all communication systems incorporate nowadays some form of channel coding, ranging from simple parity tests to sophisticated turbo-codes. Channel coding is very effective in combating errors in AWGN channels, acting in a complementary way to equalisation whose primary goal is to remove the correlation introduced by the channel. Given that the equaliser acts as front end to the channel decoder, it is possible to study its performance independently of the decoding technique used. However, it must be emphasised that the BER curves shown in this and future chapters would be considerably improved by the action of the decoder.

Channel models
One of the key elements of the system model described in the previous section is the channel profile used, especially as the objective of the whole model is to study the performance offered by various types of equaliser. As will be shown later in this chapter, the equaliser performance is greatly conditioned by the particular channel being compensated. Therefore in order to get a complete picture of the behaviour of a particular equaliser, it is necessary to check its performance with different classes of channels. In this and following chapters (except in chapter 7), four channel profiles have been thoroughly used. Each of these channels has different characteristics and introduces different levels of distortion. The first three channels are static while the last one is time varying and serves to study the tracking properties of the different algorithms and structures. These profiles have been selected to simulate the different scenarios, which at a given instant a mobile wireless receiver may have to confront.
As a last general comment on the channels used in this and forthcoming chapters, it is important to mention that although any physical channel has a continuous nature, the channel models used here are sampled versions of this continuous response. This is motivated by the fact that any modern wireless communications system is nowadays digital, and therefore all the continuous signals involved in the system can be modelled in a discrete manner ( [Bello63] and [Treichler96]). Obviously, the bit/symbol rate influences the number of samples required to model a given continuous response. For the work in chapters 4, 5 and 6, the bit/symbol rate is assumed to be normalised to one. Additionally, all the discrete channel impulse responses presented in the following subsections are normalised so that their total power is unity.

Channel model 1
Channel    The magnitude frequency response reveals some moderate attenuation (-5 dB) in the middle of the passband whereas the phase non-linearity implies that not all frequencies will be delayed uniformly. Intuitively it can be inferred that a longer equaliser than in the previous channel model will be required to equalise this channel impulse response. Lower graph: Phase response.

Channel model 3
The last static channel used regularly in this work, referred to as Channel model 3, is

Time varying channel
The time varying channel model used is largely based on the COST 207 -Typical Urban profile, which will be described in detail in chapter 7 where a more realistic environment has been implemented. For the time being, we just say that it is a multipath Rayleigh fading channel with 11 taps obtained from the sampling of a reduced 10 version of the COST207-TU profile at 3.48 Msamples/s. The resulting channel has a length of 11 taps. The carrier frequency was set to 2 GHz.

Background simulation results for LE
The next subsections present the performance of different adaptive algorithms (LMS, NLMS, VSLMS, RLS, SFAEST) when using a linear equaliser (LE) to compensate the channel models introduced in the previous section. The performance measures used are the bit error rate (BER) and the mean squared error (MSE). Although BER is the ultimate performance measure for a communication system, more emphasis is put on the second criterion, MSE, as this is analytically more tractable ( [Gitlin92]) and will be the basis for most of the work in later chapters. 10 The last path of the COST207-TU profile has been discarded as it enlarged the impulse response very significantly (and consequently the number of computations) while the results showed only small variations.
The results shown in the following subsection assume that the system operates permanently in training mode. This means that the adaptive algorithm can always make use of the correct symbol to perform the equaliser adaptation. In a practical system, it is obvious that at some point the receiver would be switched to a decision directed mode of operation. However, operating the system in a training mode is more appropriate when studying the theoretical properties of the different algorithms and structures. The number of samples required by the adaptive algorithm to make the equaliser converge gives an idea of the length of the training sequence to be used.
Another important parameter to be chosen is the equaliser length. This is the fundamental topic of this research project and is treated extensively in chapters 5 and 6. For the simulations presented in this chapter a rather common rule of thumb ([Treichler96]) has been used which, assuming the channel has N taps, makes the equaliser 2N+1 taps long in the case of linear equalisation.
This section concludes with a discussion of the effect that the decision delay has on the attained MSE level and the criteria used to select it.

Channel model 1
The   In the next two figures, 3.10 and 3.11, the MSE curves are again shown, but in this case the equaliser is being updated with the NLMS algorithm. Similar conclusions to those drawn for the LMS step size apply also to the NLMS step size ( μ ). There is some improvement in the rate of convergence with respect to the LMS. This improvement is more evident when comparing small values of µ and μ .     The RLS results are shown in figure 3.13. In this particular case the forgetting factor ( λ ) was set to 1 as the channel is static. In this case (static environment), the SS-MSE attained by the RLS algorithm would correspond to the Wiener-Hopf solution, that is, the lowest minimum mean squared error (MMSE). Particularly important to notice is the extremely fast convergence rate when E/No is large.
In figure 3.14, the learning rate is shown for the SFAEST algorithm for the three different E/No values. As has already been discussed in section 2.3.3, the settings of the SFAEST parameters strongly affect its performance and stability. In particular we have found that decreasing the value of µ improves its convergence but increases the chances of the algorithm going unstable. For these particular simulations the chosen settings were: λ =1 (static environment), ρ=1 and µ =10. This value of µ tends to slow down slightly the MSE convergence but it has proved satisfactory to keep the algorithm indefinitely stable without the need of reset mechanisms.
In order to get an idea of the complexity associated with each algorithm,    Given that the channel is static, the BER is directly related to the convergence time. Notice that this particular channel allows the LMS-type algorithms to use small step sizes without enlarging significantly the convergence time. Consequently, they are also able to get very close to the optimum solution. Looking at the BER curves in figure 3.16 and focusing on the very low E/No levels (0 to 10 dB), no differences can be appreciated among the different algorithms. This is because, as theory predicts, in low SNRs, gradient and least-squares algorithms present similar convergence rates ( [Haykin96]). As the E/No increases, RLS tends to achieve a lower BER for the same SNR. In theory SFAEST should achieve the same BER levels as RLS but due to the choice of its parameters, its convergence is somewhat compromised in favour of stability. NLMS and VSLMS slightly outperform the conventional LMS due to their faster convergence.            It is an engineering decision to evaluate whether the reduction in BER offered by the RLS makes up for the huge increase in computational complexity of this algorithm. Obviously, in situations where power/computations is not a concern, the RLS would typically be the preferred option. In power restricted systems, the SFAEST could very well be a good alternative if the application requires a very low probability of error.

Channel model 3
Simulation     In figure 3.29, a moderate improvement in convergence and SS-MSE of the NLMS ( μ =0.1) with respect to the LMS ( µ =0.01) can be observed. However, the problem is that the appropriateness of μ clearly depends on the E/No level. Notice in figure 3.28 that when E/No=5 dB, the step size offering the best performance is μ =0.01 where as for E/No=25 dB is μ =0.1. Again, if this algorithm is to be used in a variety of E/No scenarios, a compromise μ needs to be chosen.
In figure 3.30, the main advantage offered by the VSLMS is again observed. That is, the same set of parameters is able to operate very satisfactorily with regard to convergence time and attained SS-MSE level irrespective of the E/No level. The superiority of the least squares algorithms over the gradient ones, when operating in channels with large spectral variations, is clearly seen in figures 3.31 and 3.32. Notice that both RLS and SFAEST converge much faster and achieve an SS-MSE nearly one dB lower that that of the LMStype algorithms.    The measured BER curves shown in figure 3.34 reveal the extremely poor characteristics of this channel; even at an E/No of 25 dB, the BER does not even get to 10 -2 . Obviously, for a system to operate in this channel it would require the use of some other countermeasures to enhance the BER such as error coding or some form of diversity.
Notice in this figure that the curves corresponding to the RLS and SFAEST overlap and therefore cannot be distinguished. At a large E/No, these two algorithms offer a reduction of nearly 2.5 dB in the required E/No to achieve a given probability of error with respect to the gradient algorithms.

Effect of the decision delay in the LE
One of the parameters to select when implementing an equalisation system is the delay between the sample being detected and the sample being transmitted. There are not many references on how to select this parameter because, even when the channel is known, there are no definite rules to set the delay optimally 11 . [Qureshi73] proposed performing an exhaustive search to determine the optimum delay in the context of gradient type algorithms.
A similar scheme proposed by [Mueller75], termed cyclic equalisation, implements in an efficient way this exhaustive testing of all delays by using rotations of a cyclic training sequence whose length equals the filter length. In [Manolakis83] an algorithm is presented to determine the optimum delay. This algorithm however, given its complexity, is not suitable for real-time implementation. In [RUPP], some simulation results using different choices for the delay are presented in the particular context of mobile systems but no conclusions are drawn on how to select it. Notice that in a time-varying channel, the problem becomes more complex because the optimum delay may vary as the channel changes.
In the context of this work, we have resorted to simulation to set the delay for the different channels. What this graph shows is that a wrong choice of the delay may cause a significant loss of performance. In figure 3.47 the same information is shown but now for Channel model 3. In this case, the equaliser length was set to 11 taps. This channel is less sensitive to the delay than Channel model 2 but notice again that the equaliser becomes more sensitive to the delay at large E/No, although now in a much less pronounced way. What is also clear from both graphs is that the delay should be set so that the main paths of the channel are captured, i.e.
the decision on a sample is made after most of the energy corresponding to that sample has arrived.  In the simulations in this and later chapters, the delay has been set so that the dominant path of the equaliser lies roughly in the middle of the tap delay line (TDL). This has proved to be a convenient strategy when the channel is time varying and the dominant paths of the channel may change. When this happens, the dominant equaliser tap will also vary its position but will still be far away from the extremes of the TDL where, in some cases, performance is severely degraded as has been shown in the previous graphs. Varying the decision delay during operation has not been considered, as this would require some form of resynchronisation mechanism, which would further complicate the design of the receiver.
In real channels, it is not possible to know what will be the position of the main channel taps.
However, there are channel profiles available such as the COST207 models, which can serve as a guideline to help in deciding an appropriate value for the decision delay.

Background simulation results for DFE
In this section the performance of the DFE is analysed using the same channel models as for the LE although now only Channel models 2 and 3 and the Time varying model are tested.
The feedforward filter (FFF) has arbitrarily 12 been set to 6 taps whereas the feedback filter As a last general comment on these simulations it must be said that, as in the LE simulations, the DFE is assumed to operate all the time in training mode. In the case of DFE, this must be born in mind when drawing conclusions from the results, as in a practical system (decision directed), performance will be worse due to error propagation. MSE is now about 1-2 dB lower than the equivalent LE simulation. The fact that the DFE has fewer taps than the LE used previously allows the algorithm to use larger step sizes like µ =0.03. As before, the ideal step size to use is very much influenced by the E/No level at which the receiver is operating.  These comments for the LMS algorithm apply also to the simulation results obtained when using the NLMS, VSLMS and RLS algorithms, whose results are presented in figures 3.50 to 3.53. A 1-2 dB MSE reduction is observed with respect to the LE. The convergence time seems to be independent of the equalisation structure used.    The BER curves corresponding to all the simulated algorithms are presented in figure 3.54.

Channel model 2
The main conclusion that can be drawn is that in this particular channel the use of a DFE does not significantly improve the BER with respect to the LE. Moreover, error propagation may significantly decrease the BER with respect to the curves shown in 3.54. In order to get a quantitative idea of the degradation caused by error propagation, see pp. 624-625 in [Proakis95].  Notice that because of the large eigenvalue spread of the channel, the algorithm takes a long time to achieve full convergence, but now the SS-MSE is much lower than in the LE case.
Again, it can be observed when using the DFE structure that the NLMS algorithm converges much faster than the plain LMS.       In figure 3.60 the MSE curves corresponding to the RLS algorithm are presented.
Convergence time is clearly superior to any of the gradient schemes previously shown. Since the channel is static, the forgetting factor can be set to one and therefore the equaliser weights converge to the Wiener-Hopf solution as there is no excess mean squared error.
Although         The BER confirms the superiority of the DFE over the LE by reducing the probability of BER up to two orders of magnitude with respect to a LE operating at the same E/No level. There is one point to clarify regarding figure 3.69 if its results are compared with the ones obtained for the static Channel model 2. It may seem that the BER for the time-varying channel is lower than that of the static model whose profile is very similar. It should be recalled that the BER computed for the time-varying profile excludes the initial 50,000 iterations, as the objective is to measure the tracking capabilities of the different algorithms.
In the static profiles, the BER is computed using also the initial 50,000 iterations where most of the errors take place, raising in this way the BER.

Effect of the decision delay in the DFE
As in linear equalisation, a given decision delay must be chosen between the sample being detected and the currently transmitted symbol. Unlike in the LE situation, for the DFE there are some precise rules on how to select the delay in order to attain the lowest MSE level. In [Al-Dhahair96] and [Voois96] it is shown how in minimum phase channels, the optimum delay is given by N f -1, where N f is the length of the feedforward filter. When the channel is not minimum phase, as is often the case, an exhaustive search for the optimum delay must be performed.
[Al-Dhahair96] shows a computationally efficient way of performing this exhaustive search of the optimum delay. This method is feasible in static or quasi-static environments, but in the case of time-varying channels, where the optimum delay is likely to vary very often, the complexity of this process will become prohibitive.
In the simulations shown so far and the ones to be presented in future chapters, the decision delay has been set to N f -1. This choice is based on the fact that although the channel may not be minimum phase, the main paths will still be located at the beginning of the channel impulse response (see COST207 models in pp. 728 [Steele99]). This implies that the channel will be close to minimum phase and the chosen decision delay will also be close to its optimum value.

Conclusions from the background results
The objective of the simulations presented in this chapter was to give a general idea of the performance of the different algorithms and structures in different scenarios. For detailed comparisons and analysis, the reader is referred to the references given in this and the previous chapter.
Some conclusions can be drawn from these results. Regarding the algorithms, the RLS has proven to be superior to the gradient algorithms when operating in high E/No conditions. However, this performance benefit comes at the cost of a much larger computational complexity, especially when the equaliser has many taps. Within the gradient schemes, the enhanced LMS versions, namely, NLMS and VSLMS, have been shown to offer some significant advantages with respect to the plain LMS algorithm with a modest increase in complexity. The VSLMS algorithm, in certain scenarios, has been found not to converge as quickly as the NLMS algorithm with an appropriate step size. Still it provides a very important advantage over the NLMS and LMS algorithms, which is the ability to work very well independently of the E/No level. This is a very important property if the receiver must operate under different levels of noise or interference.
In terms of complexity, between the RLS and gradient algorithms lies the SFAEST algorithm, which in the simulations presented, has been shown to offer a performance similar to the RLS algorithm but with a much lower computational complexity. However, it must be mentioned, that in some other simulations not shown here, the SFAEST has proved to be an algorithm difficult to tune. If its parameters are not chosen properly, it is likely that the algorithm will become unstable during execution. Additionally, it is important to realise that the simulations were executed using double precision floating point arithmetic. If fixedpoint arithmetic is used, as is typically done in mobile terminals, instability problems will become more severe.
For the reasons mentioned above, the algorithms used in the rest of this work are: • The LMS algorithm, as it is the most common adaptive scheme.
• The VSLMS algorithm, because it has proved to be a robust and enhanced version of the LMS algorithm with a minimal increase in complexity. • The RLS algorithm, given its excellent convergence and tracking properties independently of the channel characteristics.
Concerning the equalising structures, both LE and DFE are widely used in commercial systems and therefore it is worth examining the potential reconfigurability of the two structures.

MSE ANALYSIS OF LINEAR EQUALISERS
The most common measure of the performance of a communication system is typically the BER. However, designing or analysing a system is often difficult to do by trying to minimise the BER, basically because it is a non-linear parameter. Alternative measures need to be found. In the case of adaptive filters, as mentioned in chapter 2, the mean squared error (MSE) is the usual cost function to be optimised. MSE analysis of many different adaptive filter algorithms has been addressed by several authors in the past, two of the most important studies being [Widrow76] and [Eleftheriou86].
[Widrow76] presents a steady state MSE expression when using the LMS to drive an FIR adaptive filter in a time varying scenario. In [Eleftheriou86] the counterpart RLS MSE equation is derived.
Both studies (and many others) configure the adaptive filter as an estimator of an unknown and time varying channel. In this chapter, derivations of expressions for the MSE are presented when the FIR adaptive filter is configured as a channel inverter (i.e. linear equaliser). Channel equalisation is a harder problem to analyse than channel estimation due to the correlation of the input data at the input of the adaptive filter. By no means do we claim that the analysis presented herein is completely accurate. As will be seen, numerous approximations and assumptions need to be made. Nonetheless, the resulting expressions are valuable because they show the different parameters influencing the steady state MSE and, in particular, the effect of the equaliser length. The derivations presented here follow closely those in [Widrow76] and [Eleftheriou86], but some key observations allow the results to be applied to the equalisation scenario. The first section of this chapter introduces the system model used for the analysis.  The communication channel is modelled as an N-tap FIR filter, ) n ( c , whose coefficients represent the different multipath components arriving at the receiver. In realistic scenarios the channel coefficients vary with time. In the particular case of wireless mobile channels, the variations of the coefficient amplitudes follow a Rayleigh or Rice distribution [Rappaport96]. The linear equaliser consists of an M-tap FIR filter, ) n ( w , followed by a threshold detector that produces an estimate, ) n ( d , of the original transmitted symbol.

Analytical system model for LE
In a real implementation of a digital transceiver, a pulse shaping filter would be included in the transmitter in order to limit the bandwidth of the signal. At the receiver, a filter matched to the transmit filter would maximise the signal to noise ratio at the sampling instant. In order to simplify the analysis, both filters are assumed to be included in the channel , that is, the channel represents the convolution of the transmitter filter, the physical channel and the matched filter.

Equalisation vs channel estimation
As has been mentioned in the introduction, the analysis of adaptive algorithms is usually done for the case of channel estimators. It is important to point out what are the differences that make channel estimation a simpler situation. Fig. 4.2 shows the structure of a channel estimator. IIR filters have some inconveniences that make their use rather limited (see [Shynk89]).
Perfect equalisation is generally not achievable with an FIR finite length equaliser and therefore the minimum MSE is affected, not only by the noise level, but also by the residual ISI left in the samples.

LE model assumptions
The simple, albeit realistic, model described in section 4.1 still poses some difficulties to the derivation of expressions describing the MSE performance achieved by the equaliser. Some hypotheses need to be established to facilitate this analysis; in particular, four assumptions are stated concerning: • Channel model • Channel power response • Optimum equaliser behaviour • Independence assumption The following subsections describe and justify each of these important assumptions.

Channel model
Realistic channel models such as the ones based on Rayleigh or Rice processes complicate the analysis to the point of making it impossible, therefore a more tractable model is needed.
A commonly used channel model ( [Eweda94]) is the one based on a first order Markov model described recursively by the equation: The vector c(n) corresponds to the channel coefficients. The vector q(n), called the process

Channel power response
It is assumed that the channel has unit power response therefore the channel coefficients, ) n ( c i , always satisfy: The normalised power response of the channel implies that the received signal power, 2 u σ , is constant and equal to 2 d σ + 2 v σ . Although (4.2) may seem a very restrictive constraint, it is usually satisfied in real systems by means of the power control mechanisms established between the transmitter and the receiver. Power control mechanisms are normally implemented in cellular systems to control interference among nearby users. In the case of CDMA systems, this problem is normally known as the near-far effect.

Optimum equaliser behaviour
Recall from section 2.2.1 that given a static channel impulse response, c, it is possible to compute the optimum MSE linear equaliser w by solving the Wiener-Hopf equation.
Alternatively, the optimum equaliser can also be approximated using one of the recursive algorithms available that minimise the MSE. In many realistic scenarios like those found in nearly all wireless systems (cellular, fixed wireless or WLANs), the channel impulse response will be time varying, and in the particular context of this chapter, its time evolution follows (4.1). As a consequence, the optimum linear equaliser, w(n), will also vary with time. This optimum equaliser produces at each instant the minimum error, e o (n): It is assumed that the fluctuations of the optimum equaliser follow: where p(n) is an M-tap vector with every p i (n) having zero mean and power 2 p σ . This assumption is used in [Rupp97b] for the analysis of equalisers in flat Rayleigh channels.
In our context, it is further assumed that p(n) and q(n) are related by: where 2 x denotes the 2-norm of x and the symbol ≈ is used to denote similar magnitude. In fact during the derivation the symbol ≈ will be further approximated as an equality symbol assuming both quantities have the same magnitude. Equation (4.5) is equivalent to saying that large changes in the channel will produce large changes in the optimum equaliser and small channel changes will barely perturb the optimum equaliser settings. It is important to note that q(n) and p(n), albeit having equal power, have different lengths (N and M respectively). This allows the equaliser in the model to have a different number of taps (typically more) from the channel filter. Some simulation results are now presented that justify the use of (4.5) but also show the limitations of this model.
Fifty consecutive samples of different channels, whose initial static profiles were described in section 3.3, were generated using (4.1). For each channel sample, the optimum equaliser was computed and the norm of the two update vectors (q(n) and p(n)) was calculated.      For most of the time 14 , the channel behaviour in a realistic wireless scenario will be closer to profiles 1 and 2 (figures 3.2 and 3.4) than to profile 3 making equation (4.5) a sensible approximation. Note also that if a system is known to operate permanently in channels like Channel model 3, linear equalisation is not an adequate technique to mitigate distortion as LE cannot compensate for spectral nulls.
14 As can be inferred from the channel profiles in the COST207 models from the ITU-T.

Independence assumption
The independence assumption is an hypothesis often used in adaptive signal processing to facilitate mathematical derivations that otherwise would be extremely complicated or impossible. It states that the current inputs to the adaptive algorithm, u(n) and d(n), are independent of the past sets of inputs: u(n-1), u(n-2), u(n-3), … and d(n-1), d(n-2), d(n-3),… .The degree of accuracy of this assumption depends very much on the application of the adaptive filter. For example, in the case of spatial beamformers, the assumption models reality very well as successive input vectors correspond to distinct snapshots of data acquired at different instants. In the context of temporal filters such as equalisers or channel estimators, it is easy to see that the inputs to the filter (samples in the tap delay line) at successive instants are dependent on each other. The input vector at time n is a shifted version of the one at time n-1 so u(n) and u(n-1) have M-1 terms in common.
In spite of this dependence, previous analysis of channel estimators and other systems based on adaptive filters using the independence assumption matches accurately with the experimental results. The reason for this apparent contradiction is that the independence assumption is only used at certain points in the development where there is no other way to progress in the analysis. However, if the analysis can continue without making use of the independence assumption, the data dependence is preserved. It turns out that this strategy retains most of the influence of the dependence of the successive input vectors, making the analysis fairly accurate when confronted with the measured results. A detailed explanation of the independence assumption can be found in [Widrow76] and [Mazo79].

Steady state LMS-MSE analysis for the LE
In this section a detailed analysis of a recursive linear equaliser using the least mean square The derivation of an MSE expression starts by stating the LMS equations: ŵ (n) is defined as the estimated equaliser coefficients while w(n) is used to denote the optimum equaliser value at instant n. From these two definitions it is possible now to define the error vector as: Using the definition of the error vector, (4.6) can be rewritten as is the minimum error signal, produced when the equaliser uses the optimum coefficients. Recalling the definition of the mean squared error introduced in previous chapters, MSE(n)=E[|e(n)| 2 ], it is possible now to reformulate this definition using (4.9): (4.10) The first term in (4.10) corresponds to the minimum mean squared error, MMSE(n), which, in the case of equalisation, varies with time as the channel varies. The last term in (4.10) will cancel out as a result of the orthogonality between the input vector and the minimum error signal ( [Haykin96]). Therefore the MSE evolution can be expressed as the sum of two components. One is due to the MMSE and the other due to what is usually called the excess mean squared error (EMSE): The MMSE(n) solely depends on the channel conditions and on the number of taps of the equaliser. The second term, the EMSE(n), is directly related to the algorithm being used, in this case the LMS. As the equaliser coefficients converge, the amount of EMSE reduces.
However in the case of the LMS algorithm it will not disappear completely even when the equaliser has fully converged.
Making use of the independence assumption it is possible to refine the expression for the EMSE: where R(n) and K(n) are the autocorrelation matrices of the input (u(n)) and error (t(n)) vectors respectively, and Tr[X] denotes the trace of matrix X. Equation (4.12) will be useful at a later point in this derivation.
Using (4.9) it is possible to write the equaliser coefficients update (4.7) in another form: Subtracting w(n+1) from both sides of (4.13) and using the definitions of (4.4) and (4.8) the following expression is obtained: (4.14) All the common factors are now grouped together, resulting in: where I M denotes the MxM identity matrix. The assumption made in channel estimation Haykin96]) is also assumed here: it is supposed that under the realistic assumption of µ (step size) being small, . This assumption is called the Direct Averaging approximation. This approximation allows us to write (4.15) as: In contrast with channel estimation, now the autocorrelation matrix of the input data is time varying, hence its time dependence.
Defining K(n) as the autocorrelation matrix of the error vector ) n ( t , it can be shown from (4.16): To simplify the mathematical treatment, the 4 th term in (4.18) is discarded. This simplification is justified because the 2 µ factor makes this term small compared with all the other terms containing K(n). In the steady state it is reasonable to assume that . Taking all of this into account and rearranging, (4.18) becomes: Taking now the trace of both sides of (4.19): Now use is made of two results from matrix theory [Noble88]: where A and B are product compatible matrices. Recognising that according to (4.12) Tr[R(n)K(n)] corresponds to the EMSE(n) and making use of the above two algebraic results, equation (4.20) becomes: In order to move forward in the derivation, the matrices R(n) and P must be carefully examined in order to compute their traces. The starting point is the definition of R(n): The form of the matrix R(n) in (4.22) is fairly different from the one that would arise in the channel estimation scenario. There R(n) would have a diagonal form as the inputs to the adaptive filter would be uncorrelated. It is also important to point out that if the channel was static R(n) would have Toeplitz structure 15 and the analysis would be much simpler. In general, this is not true if the channel is time varying.
Given that solely the trace of R(n) is needed, only the diagonal elements need to be calculated: 15 A matrix is said to be Toeplitz when all its Northwest to Southeast diagonals have a constant value.
In (4.23) advantage is taken of using the independence and zero mean of the data symbols to set to zero the expectation of the product of different symbols and also with the noise samples. Now the assumption of a unitary normalised channel power response is used. This assumption corresponds to the following expression: so that (4.23) becomes: Using (4.25) it is easy to observe now that It is important to stress that (4.25) and, indeed, the whole derivation from this point forward are possible due to the assumption of the normalised channel power response, otherwise it would not be possible to find a closed expression for the trace of R(n).
A similar procedure is followed for the matrix P: Given that all p i (n) have zero mean and variance 2 p σ , computing the trace of P is straightforward: It is known from equation (4.5) (assumption 1) that ) L therefore (4.28) can also be written as: Using (4.26) and (4.29) it is now possible to rewrite (4.21) as: Finally, recognising that MSE(n)=MMSE(n)+EMSE(n), the final MSE expression for the LMS equaliser operating in the steady state can be found: Equation (4.31) is the equaliser counterpart to the channel estimation equation in [Widrow76]. It can be observed that it has three terms. The first one corresponds to the MMSE, the middle term is due to the noise level and equaliser imperfection and the final term corresponds to the error due to tracking. From the form of (4.31) it can be easily seen that the predicted MSE will be a replica of the MMSE multiplied by a factor greater than one , with the added constant µ σ 2 N 2 q . Logically, the MSE(n) will always be larger than the MMSE(n).
Although From equation (4.31) it is possible to compute the optimum step size that minimises the MSE: The dynamic nature of the step size is apparent from (4.32). In practical situations, the instantaneous MMSE is not known but it would be possible to use one of the variable step size LMS algorithms available, such as [Kwong92], to perform the step adaptation.

Validation of the LMS equations
The objective of this section is to present simulation results that validate equations      There is another peculiar phenomenon worth mentioning: observe for example in Fig. 4.9, the E/No=25dB curve, how at some instants (at 2,500 or 24,000 samples), the simulated MSE using the LMS algorithm seems to operate below the MMSE level. This paradox is a consequence of the inability of the adaptive algorithm to track such rapid changes in the environment, so the simulated curve is a "low pass" version of the predicted and MMSE

Channel model 2
The channel model 2 is illustrated in the time and frequency domains in figures 3.4 and 3.5.
As mentioned before, the initial profile of Channel model 2 corresponds to a snapshot of an urban mobile channel sampled at 3.84 Msamples/s. Its spectral characteristics makes it a relatively good channel because although there is significant fading in the middle of the passband, it is not a complete spectral null. The equaliser used in this case had 23 taps and the delay was set to 8 samples. Different delays were tested. As long as the delay was greater than 4 samples it did not influence significantly the MSE results.
Notice in this case that the MSE curves (figures 4.13 to 4.16) converge much more slowly than with the previous channel model, especially at high E/No ratios. This is due to the greater distortion introduced now by the channel, which provokes a moderately high eigenvalue spread of the autocorrelation matrix of the input data.    Notice that in the four pictures the different MSE curves tend to increase. The process noise vector (p(n)) added to the channel coefficients at every iteration worsens the fairly good initial channel profile. This fact, although it is observable at any E/No level, is much more noticeable at high E/No, where the residual error is mainly due to the equaliser imperfection.
In order to evaluate the agreement between the predicted and simulated MSE, the curves need to be examined in the steady state, that is, in the region covering the last iterations

Channel model 3
The last channel covered in this section corresponds to Channel model 3, described by    There is another factor contributing to the mismatch between the predicted and simulated results. As has been stated before, the prediction equation assumes steady state operation. In heavily distorting channels such as this one, the LMS algorithm takes a long time to converge (see section 2.3.1). The next two figures show the same simulation scenario but with different simulation lengths.   The RLS algorithm is defined by the following equations: In these equations λ is the forgetting factor of the algorithm, k(n) is the so-called Kalman gain and ) n ( ξ is the error signal 16 . The matrix P(n) is the inverse of the correlation matrix of the input data ) n ( Φ which is defined as: It can easily be shown that Using (4.34) and (4.38) the weights' update can be rewritten as: The minimum instantaneous error, denoted by ) n ( e o , is defined as the error produced when using the optimum equaliser settings: Substituting the above definition into (4.39) the following expression is obtained: Now w(n) is subtracted from both sides of (4.41) and use is made of equation (4.5) from the optimum equaliser assumption: As in the LMS derivation, the error vector ) n ( t is defined as: Using (4.43) and rearranging terms (4.42) becomes The analysis done so far is independent of whether the adaptive filter is a channel estimator or a channel equaliser. In order to further develop (4.44), ) n ( 1 − Φ must be computed, and this step is where our analysis differs from that in [Eleftheriou86] and [Haykin96]. Assuming it can be written: Note that now, in the equalisation case, the autocorrelation matrix is time dependent, making the analysis more complex. As in the LMS analysis, the structure of the autocorrelation matrix needs to be examined in detail; in fact in deeper detail as now all its elements are needed, as opposed to the LMS case where only the diagonal elements were required. The objective is to find a recursion for the evolution of the autocorrelation matrix in order to compute the summation appearing in (4.45).
The definition of the autocorrelation matrix of the input data, R(n), is given by (4.22). From the assumption of the normalised power response and using the same analysis as in the LMS case (equation (4.22) ), the diagonal elements of R(n) are given by: holds for all i, j, so only half of the elements need to be computed. The elements of the upper triangular submatrix are given by: In order to derive (4.48) and (4.49), use is made of the independence between the channel coefficients, the independence of sample to sample process noise vector coefficients, and also the independence between the channel and the process noise vector. Noting the relation between (4.46) and (4.48) and between (4.47) and (4.49) it is possible to define the autocorrelation matrix in a recursive manner: This recursion allows the summation in (4.45) to be expressed in a different way: Now the different R(i) terms are expanded using (4.50): Notice that all the summing terms in (4.52) are expressed as a function of R(0). In order to obtain a close expression for this summation it is more convenient to express the terms in the "opposite" direction, that is as a function of R(n). This can be done by expressing R(n) as a function of R(n+1) in (4.50). The resulting expression is: The above expression corresponds to the sum of two arithmetic progressions, one The second term matrix has non-zero elements in the main diagonal and they are given by whereas the diagonal elements of the first matrix are given by Under plausible conditions, the elements of the second term matrix in (4.54) will be at least an order of magnitude smaller than those in the first term. By "plausible conditions" is meant that the forgetting factor is chosen correspondingly (roughly within an order of magnitude of its optimum value) given a determined value of channel change, 2 q σ .
An example of non-plausible choice of forgetting factor would be, for example, λ =0.9999 (very long memory) for a channel change rate 2 q σ =10 -4 (very fast changing). In this situation the magnitude of the second term of (4.54) is comparable to the first term.
The inverse of ) n ( Φ is easily calculated if the second term in (4.54) is discarded: Notice that now, unlike the channel estimation scenario, (4.55) depends on a time varying autocorrelation matrix. Substituting (4.55) into (4.44) and assuming that the following expression is obtained: Rearranging (4.56): The derivation now follows a similar course to the LMS one in section 4.4.1. The autocorrelation of the error vector is computed: In the steady state it is reasonable to assume ) 1 n ( ) n ( − ≅ K K , so (4.58) becomes: Now using the common approximation 1 for , and multiplying both sides of (4.59) by R(n): Finally the trace is taken of both sides of (4.60) in order to obtain the EMSE(n) (see equation (4.12) ): The computation of the two traces is straightforward, M ] [ Tr M = I and , so (4.61) becomes: Finally, using (4.5), it is possible to write , so the final expression for the RLS MSE is given by: The resulting MSE expression has three terms. The first one corresponds to the instantaneous MMSE level. The second and third terms constitute the excess mean squared error of the RLS algorithm and they appear as a result of using a forgetting factor smaller than one. The optimum forgetting factor can be obtained by differentiating (4.63) with respect to λ and equating the result to zero: Note by looking at the magnitude of the variables in (4.64) that opt λ will always be less than, but very close to, 1. In particular notice that the larger 2 q σ is, the smaller opt λ becomes.
As in the LMS case, the optimum parameter of the algorithm, in this case the forgetting factor, is time varying. Although some variable forgetting factor algorithms have appeared in the literature, their complexity is significantly higher than that of RLS (of the order of O (M 3 ) where M is the filter length), therefore these algorithms are not widely used.

Validation of the RLS equations
Some simulation results are now presented to show the validity of equations (4.63) and (4.64). As with the LMS analysis, the equations have been tested using the models described in chapter 3. recalled that if the channel is stationary, the RLS algorithm does not introduce any excess mean squared error (EMSE) and therefore is capable of achieving the minimum mean squared error. When the channel is nearly stationary ( 2 q σ =10 -6 or 2 q σ =10 -7 ) the forgetting factor will be extremely close to 1 and the RLS is able to achieve near MMSE performance.
On the other hand, in rapidly varying channels, the forgetting factor will take a smaller value     good agreement between the predicted and measured MSE, the difference between the two being within 1.5 dB (in most cases much less than that). However, it can be seen also that at higher E/No the prediction becomes less accurate. There is an explanation for this inaccuracy. As has been stated before, in stationary environments the RLS algorithm is able to attain the MMSE level.    In the derivation of equation (4.63) some simplifications have been made, therefore the final expressions cannot be 100% accurate. In particular, the inaccuracies affect the EMSE terms of (4.63). In near static scenarios the adaptive filter is able to operate at the MMSE level or very close to it, thus under these conditions the MMSE level serves as a good indicator of the performance the equaliser will achieve. In particular, notice that if 2 q σ is very small (near static channel), then the forgetting factor should be adequately set very close to one otherwise the EMSE terms in (4.63) will become significant and will distort the prediction because the filter is able to operate at the MMSE level. Thus the mismatch between    it is important to notice that slightly smaller and bigger values than the optimum perform worse than the optimum, thus this 3-D bowl shape can be inferred. The values λ =0.98 and λ =0.999 were also simulated, however their MSE curves were much worse than the ones shown and displaying them made it impossible to distinguish the rest of curves which are closer to the optimum value.

Limitations of the LMS/RLS MSE equations
Over

Transient considerations
The focus of this chapter has been so far on the steady state behaviour of the MSE. This is justified because in typical links, the transient phase is just an extremely small part of the total transmission time.
Some attention is now given to the MSE convergence stage of a linear equaliser for the sake of completeness, and also because some of the techniques presented in following chapters are also applicable to the transient stage. The convergence of the LMS and RLS algorithms differ radically from each other as described briefly next.

LMS transient
The transient MSE for the LMS algorithm has been extensively studied since the first published works in equalisation ( [Ungerboeck72], [Gitlin79]). These papers present the convergence analysis for static channels, and a recursion describing the transient MSE evolution is obtained.
The basic approach to obtain this expression consists of diagonalizing the autocorrelation matrix of the input data, R, using the Unitary Similarity Transformation ( [Noble88]). The mean squared error can thus be expressed in terms of the eigenvalues and eigenvectors of R and, from the connection between eigenvalue structure and channel spectrum, some bounds to the convergence time can be established for particular channel characteristics. The final recursive expression for the MSE evolution during the transient stage is given by: where M is the equaliser length, µ is the step size, MMSE is the minimum mean squared

RLS transient
The RLS transient performance is easier to analyse given the extremely good convergence properties of least squares algorithms. In stationary environments, the MSE convergence of the RLS is given by [Haykin96]: Convergence is achieved in about 2M iterations, where M is the order of the equaliser.
As in the LMS case, the channel is considered to be near stationary during the first steps of the convergence process. Clearly for any reasonable value of 2 q σ the channel does not vary significantly in 2M iterations, so equation (4.66) can be assumed to be true also for dynamic channels.

Conclusions on the derived MSE equations
This fairly long chapter has presented the derivations of steady state MSE expressions for a linear equaliser using the LMS and RLS algorithms. Simulation results show that in normal channel conditions, they model very accurately the true MSE performance. The resulting equations have the same structure as their channel estimation counterparts but with two significant differences, namely, the variation of the MMSE level with time and the dependence on the equaliser length (which in general will be different from the channel length). Given their importance both equations are shown again here: The key point to be appreciated with respect to the equaliser length is that increasing the equaliser length will not always result in a reduction in the overall MSE level. Increasing the number of taps of the equaliser will result in a reduction of the MMSE level but will also imply an increase in the EMSE level that may be greater than the MMSE reduction. This should be taken into account when choosing the equaliser length. Additionally, the filter order directly influences the complexity of the equalisation process, so the equaliser length can serve as a "tuner" to trade performance with complexity (i.e. power consumption).
In the next chapter, a thorough study of the equaliser length is presented along with techniques to adjust it in an efficient manner.

Equaliser length selection problem
Given a known channel impulse response with N taps and a given E/No level, there are no rules predicting how many taps will be needed to achieve an irreducible MMSE level. One possible solution to this problem is to set the equaliser length, M, to a very large number of taps, typically several times N. This approach presents two problems. First, in many cases the equaliser will be overdimensioned as a much shorter equaliser would achieve an almost identical MMSE level. The computational waste provoked by system overdimensioning might be a concern in systems with restricted power consumption such as mobile terminals.
Second, although increasing the equaliser length will never result in an increase in the   So far it has been assumed that channels were static and known. In practical scenarios, such as mobile or wireless systems, the channel will be unknown and probably time varying, therefore the number of taps the equaliser cannot be determined a-priori and can also vary with time as conditions in the environment change.    This fact has been the main motivation of the study of reconfigurable equalisation structures; to help in better tracking of channel conditions and to avoid unnecessary waste of computational power.  Later on it will be shown that combining this structure with the algorithm presented in the next subsection only requires one extra adder.

Segmented FIR filters for linear equalisation
Any other properties the original equaliser may have, such as linearity, are preserved when it is converted into a segmented structure. Basically what this new structure allows is to "monitor" how the filtering operation is progressing.

Structure update algorithm
The segmented equaliser structure introduced in the previous section does not offer any significant benefit over the conventional linear equaliser unless there is some means to modify the equaliser length dynamically. The structure depicted in figure 5.8 has the potential to increase or decrease the number of taps used in the equalisation process, however there is still the question of what criterion to follow in order to reconfigure the filter in an efficient manner. This algorithm should have two qualities: • It should only use the information available to the equaliser subsystem, that is, no external information should be required (such as noise level, Doppler spread).
• It should be easy to compute. There is no point in using criteria that require lot of computations, as then the benefits of reducing the number of taps might be lost.
The criterion proposed here, termed accumulated squared error (ASE), is given by: Notice that the ASE(n) has exactly the same definition as the least squares criterion from which the RLS algorithm is derived. It has been decided to refer to it with a different name because its use is rather different from that in the least squares algorithms. Note that the ASE(n) and MSE(n), assuming ergodicity and reasonably large n, are related by: Looking again at figure 5.8, it is clear that a distinctive ASE i (n) value can be computed for every segment, using the different error signal e i (n) available at every segment's output. In this way the measures ASE 0 (n), ASE 1 (n),…ASE K-1 (n) are obtained.
It is now possible to state an algorithm that dynamically updates the length of the equaliser.
Suppose that at any given moment an equaliser made of K segments of P taps/segment is only using the first L segments with L ≤ K, the rest of the segments (K-L) have their taps set to zero and they are not being updated. At every iteration, the ASE L (n) and ASE L-1 (n) are being computed and the following decision algorithm is executed: There are three possible outcomes when algorithm 5.1 is executed. If the comparison in (5.5) is true, the equaliser will be expanded by P taps. If the comparison in (5.6) holds true then the equaliser will be reduced by P taps. If none of the comparisons hold true, the equaliser will be left as it is. Provided that dw up α < α , both comparisons cannot be true at the same time (expansion and contraction).
This algorithm can be translated into plain words as: If an equaliser with L segments performs significantly better than one with L-1 segments then add another segment. If an equaliser with L segments performs similarly to one with L-1 segments remove the last segment. This simple heuristic limits the number of segments to those that really make a significant contribution in the equalisation process. Notice that algorithm 1 satisfies the qualities sought: it only relies on information available to the equalising subsystem (only uses the different e i (n)), and its computational complexity is low, requiring only four products and four additions per iteration. Also important is the fact that with the given algorithm only the performance of the last two segments is monitored, therefore only one extra adder is required.

Parameter selection
Combining the segmented FIR structure and the basic length control algorithm requires four parameters to be determined, namely, K (maximum number of segments), P (taps per segment), up α and dw α . The maximum number of taps of the equaliser, M, is given by KP.
At this point attention is only given to the qualities and relations of each of the parameters.
Simulation results with variations of the parameters will be presented later on.
The parameter K determines, jointly with P, the maximum number of taps of the equaliser.
For a given value of P, K defines the amount of equalisation the system can potentially perform. K´s choice will be mainly conditioned by the computational/power resources available. The parameter P is more interesting from a system point of view as it provides the degree of "equalisation granularity" of a segment. By equalisation granularity is meant the amount of reduction in MSE level a segment can achieve. This concept is better explained  On the other hand small P values mean that the contribution of each segment to the MSE performance is not very big and therefore the equaliser can be adjusted more precisely (fine granularity). When P=KP → K=1, this corresponds to an equaliser with just one segment, i.e. a conventional linear equaliser. If P=1 → K=KP, each tap contribution is assessed individually and there are as many segments as taps.
The two other parameters to be specified are up α and dw α and their values should be set in accordance with the chosen value of P. The effects of modifying up α and dw α are best understood by looking at equations (5.5) and (5.6) in algorithm 1. If up α is set to 1 it can be seen from (5.5) that even the slightest reduction in ASE level will provoke the equaliser to expand by one segment. Typically up α will be set to values less than 1 so that the equaliser only expands when the ASE improvement is significant. As an example, up α =0.9 means that the equaliser will expand only if the difference in the MSE (ASE) reduction between the last two segments is greater than 10%.
The parameter dw α controls the sensitivity of the equaliser to reduce its length. This is useful to prevent the equaliser from being kept unnecessarily long if channel conditions change.
Usually dw α will have a value very close to one. In this way it is detected when the last segment has started increasing the MSE level and the equaliser is shrunk. Lower values of dw α will increase the tendency of the equaliser to contract.
When the values of up α and dw α are very close to each other the equaliser length will tend to oscillate. The further apart up α and dw α are, the less likely is the equaliser will change its length. Notice though, that length oscillation does not cause any significant trouble. An exception to this occurs when the RLS algorithm is being used, an issue treated in the next section.
Finally it is worth noting that up α and dw α have to be set jointly with P (taps per segment).
As has been mentioned, when the segment length is short, the effect of adding or removing a segment will be far less significant than when a long segment length is used, therefore

Variable length LE enhancements
The basic structure update algorithm described in section 5.2.2 works well in channels whose conditions are fairly stable during operation. By stable is meant that in spite of the time varying nature of the channel, the variations are approximately of constant magnitude.
However this structure may have trouble reconfiguring when there are sudden changes after prolonged intervals of stationarity. The algorithm needs a minor modification in order to be able to cope with these situations. This modification is presented in section 1.3.1.
Additionally the variable length LE may have some stability problems if the RLS algorithm is used to drive the filter coefficients, so a method of stabilisation when using the RLS algorithm is introduced in 1.3.2. Finally some attention is paid to the choice of the delay in the detection process in the segmented equaliser.

Robust variable length linear equalisation
Simulations using the basic algorithm reveal that algorithm 1 loses efficiency in detecting channel changes after long periods of operation. This problem arises because with algorithm 5.1, the measured ASE weights equally all the information from the start of operation.
When dealing with time-varying channels it is better to stress the information obtained from recent data as the scenario may have changed and old data may not be very relevant to the current situation. Similarly to the exponentially weighted RLS algorithm, a forgetting factor, denoted as β, is introduced in the ASE measurement. This makes the equaliser much more robust to large and irregular channel changes.
Algorithm 5.1 can be modified with the inclusion of the forgetting factor to obtain the algorithm shown below.  This modification represents a modest increase in computational complexity with respect to the basic algorithm as it only requires 2 additional products per iteration. The total complexity of algorithm 2 consists of 6 products and 4 additions per iteration.

Stabilisation of the RLS variable length LE
As has been described in chapter 2, least squares algorithms are much more prone to suffer stability problems than gradient type algorithms (like LMS). RLS is no exception and it was found that its use in conjunction with the variable length structure occasionally led to severe stability problems. In order to understand where the instability comes from some insight into the algorithm is needed. For convenience the RLS algorithm is repeated here: (5.14) The . In plain words, the inverse of a truncated matrix is not simply the truncation of the inverse. This fact completely invalidates (5.14) making the filter go unstable whenever the equaliser contracts.
There seems to be only one solution in order to solve this problem: restart the filter every time it is contracted. This may seem a very drastic solution, however, given the extremely good convergence properties of the RLS algorithm, the restart does not affect the MSE performance greatly, provided the number of resets is not too large.
The other possibility occurs when the equaliser is expanded. In this case and using the same notation as in the paragraph above, M 2 >M 1 . When this happens, the M 1 xM 1 correlation is expanded in the following way into the expanded correlation matrix It has not been possible to find this result in the matrix theory literature (which may exist in a different form), however its validity has been verified using the Symbolic Computation Toolbox of Matlab. Using this result, when the equaliser is expanded, the new P(n) (after expansion) can be directly and easily calculated from the old P(n) (before expansion), therefore equation (5.14) can be kept consistent by simply "zero padding" P(n) with the appropriate number of zeros whenever the filter length is increased.
The RLS stabilisation procedure can be summarised as: "Restart the adaptive filter when the number of taps is reduced. Do nothing when it is increased". Of course it is advisable to minimise the number of contractions. Simulation results shown later prove the efficacy of this method.

Decision delay in segmented equalisers
The last theoretical topic related to segmented equalisation requiring some attention is the choice of the decision delay. Decision delay in conventional equalisers has been covered in section 3.4.5 and the main conclusion extracted is the lack of techniques to optimise the choice of the decision instant other than performing an exhaustive search. Simulations with typical wireless channels show that the MSE performance is quite insensitive to the delay if this is bigger than a small number of taps.
There are two important points concerning the delay to be aware of when using the segmented structure. First, the initial number of taps of the equaliser has to be greater than the delay (also applies for conventional equalisers). This means that the number of active segments at any given instant has to be large enough to include the delay. This is obvious as otherwise the equaliser would not be able to capture the peak of signal energy of the reference tap.
The second important issue is concerned with the way taps/segments are added and subtracted from the equaliser. According to the techniques presented in 5.2, taps are always added/subtracted at the end (tail) of the equaliser. In principle it would be possible to arbitrarily add/subtract taps at either end (head or tail), however this poses the problem that when taps are added/subtracted at the head of the equaliser, the decision delay should also be modified by an equal number of taps. Changes in the decision delay implies the need for some form of resynchronisation of the bit stream making the system more complex. An alternative solution would be to add some zeroed segments before the first active segment.
These zeroed coefficients would initially be used only to introduce an "artificial" delay in the received bit stream, acting as simple buffers. If the equaliser needs to be expanded then some of these segments might be switched on and start contributing to the equalising process. Similarly, if the equaliser has to be shortened, the first segment can be switched off (zeroed) again. With this method the delay does not need to be changed if taps are added or removed from the head of the equaliser as it is already taken into account by the zeroed coefficients. This technique is useful to keep the reference tap in the centre of the equaliser even when the number of taps changes.
In the context of wireless and mobile systems, the reference tap does not need to be centred as channels tend to be minimum or near minimum phase, i.e. the strongest components arrive first. Consequently, segments/taps are only added at the tail of the equaliser, making unnecessary the technique described in the previous paragraph.       taps.

Simulation results of the variable length LE
Most of the comments for figures 5.9 and 5.10 also apply to figures 5.11 and 5.12 corresponding to an E/No level of 15 dB. Nonetheless, notice how in this scenario figure   5.11 shows that the 24 tap fixed equaliser achieves the same performance level as the 18 tap.
Notice also that the variable length equaliser with up α =0.8 achieves the same MSE level as the longest fixed equaliser. As up α is reduced, performance degrades because the equaliser is not sufficiently expanded. As in the E/No=25 dB case, the average length can be computed from the total number of products. Repeating the procedure described previously it is found that M av =17.9 taps. Adding further taps will not help in reducing the MSE level in a significant way and will increase the computational burden of the equalisation process.
This ability to predict the useful number of taps of the equaliser does not come for free, as the price to be paid is an increase of 4 products and 2 additions per iteration. However the potential savings obtained from using an equaliser with the optimum number of taps clearly outweighs this modest increase in the computational complexity. Moreover the problem of a rise in the MSE level due to the EMSE generated by the LMS algorithm is also avoided.
The same results are now presented but using the RLS algorithm. The system parameters are the same as in the LMS simulations. The RLS forgetting factor, given that the channel is static, was fixed to 1.      The variable equaliser with up α =0.8 uses less than a third of the products required for the 24 tap equaliser and less than a half with respect to the 18 tap filter.
Using the same channel profile the effect of the segment length has also been studied. The     In general, using large segment lengths will produce a coarser approximation to the optimum number of taps than short segment lengths. This is simply due to the larger differences between the last two segments. In theory this would push for the use of short segment lengths, however short segment lengths have also a drawback which can be clearly appreciated in figure 5.24. Notice how where 1-tap segments have been used the MSE, remain very high for all values of up α , even for up α =0.8. The reason for this phenomenon is that the very small differences in performance between two successive segments (in this case, just 1 tap) constrain the equaliser from expanding as the proposed algorithm (algorithm 5.1) considers that the performance limit has been reached. This can also be inferred from Extensive simulations using different segment lengths with a variety of channels have shown that segment lengths of 3 or 4 taps provide good performance and easiness of adjustment of the system parameters. Segment lengths greater than 4 make the equaliser length changes too steep and inherently inaccurate to find the right number of taps. Segment lengths of 1 or 2 taps need very big values for up α and are difficult to adjust. In light of these results, for the rest of the simulations presented in this chapter the segment length has been fixed to 3 taps.

Channel model 3 (Static)
The next channel profile tested is channel model 3 whose characteristics are shown in         A recurring effect that can be observed when comparing the resulting M av values for the LMS and RLS algorithms is that normally, when using the RLS algorithm, the equaliser tends to grow more than when the LMS is used. Again this is due to the ability of the RLS to avoid any EMSE. In connection with this, and contrary to the LMS case, when using the RLS algorithm, increasing the equaliser length always decreases the MSE level. However after a certain number of taps, the reduction becomes minimal. Therefore it is possible, or even advisable, to use a lower up α such as 0.6 to avoid this slight over-expansion of the equaliser with respect to the optimum number of taps when using the RLS algorithm.

Channel model 3 (Dynamic)
The simulation results presented so far were based on static channel models. This section and the next two show results obtained by operating the variable length equaliser in dynamic environments.
In this particular section, the time varying nature  taps. The length progression is shown in figure 5.34 and it can be clearly seen that the variable length equaliser tends to increase its order up to nearly 14 taps. That is, the variable length equaliser is able to infer that the channel conditions are becoming favourable and increase the equaliser length to further reduce the MSE level.  For the RLS algorithm, similar results were found. The only difference is that, as in the case of the static channels, the achieved length with the RLS algorithm was slightly longer than the LMS values presented above.  At this point, it is important to clarify a particular aspect of the performance measure used in these simulations. So far the quantity measured has been the MSE. Initially the same quantity was used in this particular scenario however a "visualisation" problem arises due to the different MSE levels involved in the same graph.

Variable E/No profile
In particular, when the E/No level is 5 dB, the MSE curve attains its maximum value, which is much bigger than the minimum value achieved when E/No=25 dB. The problem comes from the fact that the MSE is recorded continually from the start of the simulation. Once the MSE has gone through its maximum value (E/No=5 dB) it is impossible to appreciate the subsequent part of the MSE as the largest values dominate from that point onwards the rest of the curve.
In order to solve this problem the recorded MSE is a windowed version of the original MSE, i.e., only the values inside the window corresponding to the most recent data are taken into account in the MSE computation. This has the effect of "forgetting" old data and the resulting MSE curve reflects more accurately what it is happening in the system. The window length clearly affects the shape of the resulting MSE curve. Large windows will tend to present smoother MSE curves than short windows.
For the simulations presented here, and after several trials, the window length has been chosen to be of 2,000 samples.     Logically, increasing the value for up α lowers the MSE, however notice that the curve corresponding to up α =0.6 presents a fairly degraded aspect, clearly much worse than the equivalent curve using the LMS algorithm. In section 5.2.3 it was mentioned that the nearer up α and dw α are, the more prone the equaliser is to length oscillation.
If the LMS algorithm is used, length oscillation does not cause any trouble at all. On the other hand, when using the RLS algorithm, and according to the stabilisation procedure described in section 5.3.2, the RLS algorithm is re-initialised every time the equaliser contracts. Therefore, if the length is oscillating often, the equaliser is continually being restarted, causing an increase in the MSE level. In order to alleviate this problem, dw α was set to 1.0 (instead of the 0.99 used so far) and, as can be observed in figure 5.41, the problem was not completely solved. The MSE curve corresponding to up α =0.8 is not shown in figure  5.41 as its performance was far worse than the one corresponding to up α =0.6 due to an even higher restart rate. Figure       The second profile used also starts using channel model 1 but then switches to Channel model 3, which could simulate a strong sudden shadowing by a nearby object. Towards the end, the channel goes back to Channel model 2.
For all simulations in this section, the length was set to 180,000 bits, with the switching instants fixed at 60,000 bits (1 st change) and 120,000 bits (2 nd change). The E/No has been set to 35 dB. Note that this value of E/No is higher than in previous simulations. This value has been used in order to "isolate" the behaviour of the equaliser in front of a channel profile change as it has been seen that the E/No level also influences the response of the variable length equaliser. In this set of simulations the MSE has also been windowed as otherwise the whole curve would be dominated by the largest MSE level achieved.

Joint VSLMS and variable length equalisation
The simulations presented so far have concentrated on the most common algorithms, LMS and RLS. Now some attention is given to a "flavour" of the LMS algorithm, the variable step size LMS (VSLMS), whose characteristics are well complemented by that of the variable length equaliser.
The properties of the VSLMS algorithm have been described in section 2.3.1. It has been shown in previous studies ( [Kwong92], [Mathews93]) and also in some of the simulations in chapter 3, that the possibility of dynamically changing the step size can potentially provide a faster convergence time and a smaller steady state error when compared with the conventional LMS algorithm. It has also been pointed out in the background chapter that all the algorithms of the LMS family (including the VSLMS) have the same constraint regarding the maximum value the step size can take in order to have stability guaranteed. For convenience the condition is rewritten here: As can be seen, the maximum step size bears a direct relation to the equaliser length. The variable length equaliser, with its ability to reduce its number of taps, allows the step size to achieve higher values which may potentially improve the convergence of the equaliser.  Obviously this computation needs to be done only once and may serve for the iteration of both algorithms.

Restriction of the equaliser expansion
This chapter presented techniques to minimise the MSE level while also optimising the number of computations to be performed. In theory the MSE level should be kept as low as possible, but in practice the system may get to an MSE level where any further reduction will not improve the BER of the system. Therefore it might be useful to set a lower bound,   multiplicative factor on its r.h.s. . Therefore, it is reasonable to assume that by shortening the filter, the convergence will take place more rapidly. Simulation results in the two mentioned references confirm this assumption.

Transient of the variable length equaliser
The main drawback of the scheme just described is that the time to switch on the rest of elements of the equaliser must be known a-priori. In the context that work is described, telephone lines, this is a reasonable pre-requisite as, although the channel is unknown, average channel models can be used to calculate this switching instant. In the case of wireless mobile systems, this is certainly not the case as the channel impulse response cannot be accurately predicted beforehand.
In our simulations, the convergence time of the VL LE depended strongly on the parameter up α . When up α is small (0.2-0.4), convergence is typically worse than that of a fixed length equaliser with a number of taps equal to the final length achieved by the VL LE. This is not surprising as when using small up α performance is compromised in order to keep the computational complexity low. If up α is made larger (0.6-0.8), the VL LE converges as quickly as a fixed length equaliser.

RECONFIGURATION
In chapter 3 it has been shown that linear equalisers do not perform well when the channel to be equalised is heavily distorted. In these situations, DFE has been shown to work isome concluding remarks about the variable length FBF DFE are given.

Analytical system model for DFE
The generic model used for the MSE performance analysis is shown in figure 6.1. As in the case of LE, we assume this system model is in a fully digitised form. In chapter 2 the phenomenon of error propagation in DFE has been briefly discussed. From figure 6.1 it is clear that any erroneous decision made by the threshold detector will also affect posterior decisions. This fact complicates very much the treatment of the DFE.

Analysis of the DFE taking into account error propagation has been presented in
[Dutweiler74], [Altekar93] and [Smee98]. In these references, the performance is analysed from the point of view of BER. On the contrary, in the work presented here, our objective function is the MSE. This measure, as has been shown in the previous chapter, can serve as an indicator to efficiently reconfigure the equaliser. However, in order to make the DFE-MSE analysis feasible it is necessary to assume correct past decisions. This assumption lets us re-draw figure 6.1 as the linearised system shown in figure 6.2.

DFE model assumptions
All the assumptions stated in 4.3 for the linear equalisation study can also be applied without any change to the case of the DFE model. Notice that assumptions 4.3.1 (channel model) and 4.3.2 (channel power response) refer to the channel characteristics, and therefore they are independent of the structure of the receiver. The independence assumption will also be used at some points of the LMS-MSE derivation.  As has been already explained in section 4.3.3, the accuracy of this assumption depends on the spectral properties of the input data autocorrelation matrix. If this matrix has a small eigenvalue spread, which happens when the channel spectra is flat or the SNR low, the assumption is very accurate. On the contrary, when the channel spectrum contains nulls or the SNR is very high, the assumption becomes a loose approximation.

LMS-DFE analysis
The MSE LMS analysis for the case of the DFE follows exactly the same path as the LE derivation and therefore only the different parts will be covered now in detail.
The LMS algorithm for the case of the DFE is given by: These equations are identical to those given by (4.6) and (4.7) except that now u(n) and ) n ( w have a different structure. The DFE input vector, u(n), is given by: where r(n) is the vector formed by N f consecutive channel samples stored in the FFF and d(n) is made of the last N b detected symbols. The equaliser coefficient vector, ) n ( w , can also be split as: represents the N f feedforward and N b feedback taps respectively. The MSE derivation now follows exactly the same path as the one for the LE given by equations (4.8) to (4.21) with the resulting expression being: Equation (6.5) albeit identical in form to (4.21) presents some important differences as the structure of R(n) and P is not the same in the DFE and in the LE. We now examine in detail the characteristics of both matrices in order to obtain the final expression for the DFE-EMSE.
The autocorrelation matrix of the input data is defined as:

R(n)=E[u(n)u T (n)]=E[[r(n) d(n)][r(n) d(n)] T ] (6.6)
Expanding the vectors y(n) and d(n) we obtain: where F(n) is an N f xN f matrix given by F(n)=E[r(n)r(n) T ], V(n) is an N f xN b matrix given by  Given that only the trace of R(n) is needed, only the diagonal elements in R(n) are of concern here. Recalling the assumption of a unitary normalised channel impulse response, it is straightforward to compute the diagonal correlation coefficients given by With (6.11), (6.13) and (6.14), a closed-form expression can be written for the EMSE of the LMS-DFE:

V(n)=E[r(n)d(n) T ] and D is an N b xN b diagonal matrix given by D=E[d(n)d(n)
The overall MSE, which the sum of the MMSE and EMSE, is given by: Equation (6.16) is the expression for the steady-state MSE for a DFE when using the LMS algorithm to update the equaliser settings. The first term on the r.h.s. of (6.15) corresponds to the minimum mean squared error, the second term is due to the noise misadjustment of the FFF, the third term results from the misadjustment of FBF and the last term results from the tracking misadjustment. Notice that the derived expression shows that the FBF does not produce any noise enhancement as the EMSE introduced by the FBF does not depend on 2 v σ . This is one of the main advantages of the DFE over LE ( [Qureshi85]).
It is also intuitively satisfying to check that when N b =0, the resulting expression reduces to equation (4.31) corresponding to the MSE for the LE. Equation (6.16) shows that the EMSE depends on several variables that can be set by the designer, namely, N f , N b and µ.
The value for µ needs to be chosen as a compromise between steady state accuracy and tracking capability. The lengths of the FFF and FBF also need careful consideration and will be discussed extensively later on in the chapter. Nonetheless, it can be anticipated from equation (6.16) that making the filters too long may end up increasing the overall MSE due to an increase in the misadjustment. In the next section, simulation results are presented showing the accuracy of equation (6.16).

Validation of the LMS-DFE equation
The simulations in this section use the same channel models and simulation conditions as in the LE case. The Markov variations of the channel impulse response (CIR) imply that any of the coefficients in the CIR may become the dominant path. In order to achieve an acceptable performance, the FFF must be able to gather the main peak of energy, that is, the FFF span must be long enough to include the dominant path. Therefore, and for the case of the Markov channel, the FFF must have at least the same number of taps as the CIR. For the simulations presented next, the FFF length has been set to N+1 (N= number of channel taps) and the FBF to N-1 taps. In practical channels, the energy is always concentrated at the beginning of the CIR, and consequently the FFF can be much shorter than the CIR length. DFE performance in realistic radio environments is covered in chapter 7.

Channel model 1
Channel model 1, already described in chapter 3, can be considered as a very well behaved channel introducing a modest amount of distortion. The DFE used in these simulations consisted of 3 forward taps and 1 feedback tap. The step size was set to the rather large value of 0.025 to accelerate convergence.      In figures 6.11 and 6.12 the accuracy of equation (6.16) is verified when using different number of taps in the FFF and the FBF. One comment is needed on the results shown in figure 6.11. This figure compares the predicted with the simulated MSE for different values of N f . As was explained at the beginning of this section, the length of the FFF needs to be at least as long as the CIR in order to guarantee that the FFF is able to capture the dominant path. For this channel model (N=11) and using a 6-tap FFF, this condition is not met and in some simulations where the main path in the channel moved beyond the 6 th tap in the CIR, a huge increase in the MSE level appeared.
In order to make a fair comparison, these simulations have been removed from the ensemble averaging process for any of the N f values. The results presented in figure 6.11 show that adding taps to the FFF tends to reduce the MSE but a point is reached where the MSE reduction becomes very small. Eventually, as in the LE case and for the same reasons, after a certain number of taps making the FFF any longer will start increasing the MSE. The important fact to appreciate in figure 6.11 is that equation (6.10) successfully predicts the impact the FFF length has on the overall MSE.
In figure 6.12 the effect of the FBF length is studied. Some known results regarding the DFE-MMSE are discussed in section 6.8; one of them is particularly relevant to the results shown in figure 6.12 and is therefore anticipated now: assuming a decision delay D=N f -1 the combined channel-FFF impulse response will have N-1 postcursors. Therefore, any FBF longer than N-1 taps will not improve the MSE in any way. This can be clearly seen in figure 6.12. Knowing that the channel has 11 taps (N=11), we can predict that there will not be any improvement when using more than 10 taps in FBF.  The curve for N b =5 taps is clearly worse than for the other N b values as some of the postcursors are not cancelled. However the curves for 10, 15 and 20 feedback taps offer very similar performance as there are only 10 postcursors to cancel. In fact, although barely distinguishable in the graph, the MSE for N b =10 is lower than for N b =15 which in turn is lower than N b =20. This indicates the correctness of the 3 rd term in equation (6.16) and proves the hypothesis that using too many taps in the feedback filter not only wastes computations but also increases the MSE level. Finally, the effect of varying the step size has also been studied. Figure 6.13 shows the simulated and predicted MSE curves for two different values of µ when E/No=15dB and 2 q σ =10 -4 . Again the prediction agrees very accurately with the experimental results. It is interesting to verify that reducing the step size produces an increase in the MSE: although the smaller step size reduces the misdjustment errors of the FFF and FBF, it increases the tracking misadjustment producing an overall larger MSE.

Channel model 3
As has already been said (chapter 3), Channel model 3 is a fairly pessimistic scenario due to the existence of a null in the passband. Figure 6.6 shows that the hypothesis about the optimum equaliser variations holds only in a rather loose way, therefore it is expected that the predictions made by equation (6.16) are not as exact as in the other channel models, especially at high E/No levels. range. For the high E/No case, the discrepancy becomes more noticeable. However, the predicted MSE is far more accurate than simply using the MMSE as an approximation of the real MSE performance. The same applies for the slowly varying channel ( 2 q σ =10 -6 ). In fact, at a high E/No, the differences between the prediction and the measurements become quite large. Notice however that the E/No=25dB curve in figure 6.15 has not yet reached the steady state after 30,000 samples. If the simulation is allowed to run for a larger number of samples, the measured MSE will tend to get closer to the predicted value although a gap between the two will still exist. The reason for such a slow convergence is to be sought in the dependence of the LMS transient on the channel spectrum (see chapter 2). Both the inband null and the large E/No contribute to the poor power spectral characteristics of this particular scenario. The source of the prediction inaccuracy is to be attributed to the incomplete satisfaction of the optimum equaliser variations hypothesis (see figure (6.6)).

Decision delay effect on the LMS-DFE
While studying the LMS-DFE, an interesting novel result has been found concerning the choice of decision delay. This topic has already been considered in section 3.5.4. There, it was mentioned that some specific techniques exist ( [Voois96], [Al-Dhahair96]) in order to choose the decision delay that minimises the attainable MMSE. These methods, although optimum from an MSE point of view, do not take into account the characteristics of the algorithm used to perform the filter adaptation.
In the particular case of the LMS algorithm, as has been mentioned in section 2.3.1, the convergence of the algorithm is sensitive to the eigenvalue spread of the input autocorrelation matrix, is, the longer it takes the algorithm to converge.
We have found that, in a typical channel, ) (R χ strongly depends on the decision delay, D. By typical channel we understand one whose impulse response contains a clear peak of energy followed and preceded by other pulses of smaller amplitude (multipaths).
The relation between D and ) (R χ arises from the way the decision delay affects R 19 , whose structure is shown in equations (6.7) and (6.8). In these equations, it can be seen that R is It is also important to look at how the decision delay affects the MMSE. This information is shown in figure 6.17 and reveals that the minimum MMSE is achieved by choosing D=4.
Also fundamental is the fact that when D> c ∆ +N f -1 the MMSE attained becomes extremely large. This is not surprising as with this choice of delay, the main peak of energy falls out of the span of the FFF and is therefore not captured. Consequently, the rule to minimise the 19 For simplicity, in this section the channel is assumed to be static, hence, R will also be static.
eigenvalue spread while at the same obtaining a sensible MMSE can be simplified to just set the delay to D= c ∆ +N f -1, in this example, D=5.   It is seen in figure 6.18 that D=5 is the one with the fastest rate of convergence as could be already inferred from its low eigenvalue spread in figure 6.16. The curve for D=4 is the one achieving the lowest MSE as already predicted by the results in figure 6.17. Notice however, that this slight improvement in MSE with respect to D=4 comes at the prize of a significantly longer convergence time. Even more revealing is the curve for D=3. If the simulation is let run for long enough, this curve will end up converging very near the curve corresponding to D=5. Note in figure 6.17 that D=3 and D=5 have almost identical MMSE. However, and due to its large ) (R χ , the MSE convergence for D=3 is extremely slow. Obviously, this choice of delay should be avoided.

RLS-DFE analysis
The RLS equations for a DFE have exactly the same form as the corresponding LE equations given by (4.33)-(4.36). These equations are repeated here for convenience: represent the N f feedforward and N b feedback taps respectively.
The (N f +N b ) vector k(n) is the Kalman gain applied to each of the equaliser coefficients. The is defined as the inverse of the input temporal correlation matrix: In the previous definition, λ, is the forgetting factor used to improve the tracking of the algorithm.
As in the LMS case, the MSE derivation for a DFE using the RLS algorithm follows very closely its LE counterpart. In fact, the derivation presented in section 4.6, taking into account the definitions of (6.21) and (6.22), applies also for the DFE up to equation (4.44), restated here: Recall from the LE derivation that t(n) is the error vector given by Similarly to the previous section for the LMS, it is now important to examine the structure of the temporal correlation matrix ) n ( Φ . We start with an assumption already made in the RLS-LE analysis, that is: where R(n) denotes the ensemble correlation matrix. Therefore, from (6.25) it can be written: . The structure of the ensemble input correlation matrix is given by equation (6.7), and, in a more detailed form, by equation (6.8). Notice however, that now we are interested in computing not only R(n) but also ) n ( Φ . Equation (6.25) can be expressed as: In order to proceed further it is necessary to establish the relation between R(n) and R(n+1).
As shown in equation (6.7), R(n) is composed of four submatrices: F(n), V(n), V(n) T and D.
The submatrix F(n)=E[r(n)r(n) T ] corresponds to the correlation of the inputs to the FFF, so clearly the relation of F(n) and F(n+1) can be determined using equations (4.48), (4.49) and (4.50) corresponding to the LE. Therefore it can be written: where I Nf is the N f xN f identity matrix.
The entries of V(n) are just entries of the channel impulse response (see equation (6.8)), therefore, V(n) and V(n+1) are related directly by the channel process noise vector q(n) as follows: [ ] When n is large, we can assume that: as the entries in the submatrices ∆ ∆ ∆ ∆ V (n) and ∆ ∆ ∆ ∆ V (n) T have zero mean and will tend to cancel when n is large. Equation (6.31) can also be expressed "backwards" as: Using equation (6.33) and the approximation of equation (6.32), ) n ( Φ can be expressed as: Rearranging (6.34): The summation terms within brackets in equation (6.35) can be recognised as the sums of two geometric series allowing the previous equation to be written in a compact way: Recall that in chapter 4, during the development of an steady state MSE expression for the RLS-LE, a similar expression to (6.36) was also derived (see equation (4.54)). There, it was justifiable to ignore the second term in the expression for ) n ( Φ because, under normal conditions, it was very small when compared to the first term. The same reasoning is now applied to equation (6.36). Assuming the forgetting factor (λ) is chosen consistently with the magnitude of the channel variations ( 2 q σ ), the second term in (6.36) will be one order of magnitude smaller than the first term. In order to ease the analysis it is assumed that the temporal correlation matrix is given by: Given that our main interest is in the inverse of ) n ( Φ , we write: We are now in a position to continue the analysis from equation (6.24) making use of (6.38): As in the LMS derivation we assume that ) . This further simplifies the previous equation: The derivation follows now exactly the same steps as those given for the RLS-LE in equations (4.57) to (4.61) and a very similar expression is found for the RLS-DFE EMSE: The trace of I Nf+Nb is obviously N f +N b . Substituting both traces in equation (6.41), the EMSE is obtained: It is only left to express the second term on the r.h.s. of (6.43) as a function of the channel parameters (N and 2 q σ ) by means of the assumption expressed in section 6.2 which is restated here: Finally, using (6.44) and adding the MMSE term we obtain the formula for the steady state MSE for a DFE using the RLS algorithm: Some comments are now in order regarding equation (6.45). First of all notice that there are four terms: the first one corresponds to the MMSE, the other three terms correspond to the EMSE due to the use of a forgetting factor less than one (2 nd term), and the channel variations (3 rd and 4 th terms). If we set λ=1, which would correspond to a situation where the channel is static and therefore 2 q σ =0, the last three terms of (6.45) will cancel and the steady state MSE will be equal to the MMSE. This agrees with the RLS theory presented in chapter 2 which states that in an stationary environment, the least squares solution will converge to the optimum Wiener solution. It also reassuring to check that when the FBF is suppressed (i.e. N b =0), the resulting expression is the same as equation (4.63) derived for the RLS-LE.
As in the LMS, it should also be noticed that the FBF does not produce any noise enhancement as there are not any terms containing 2 v σ proportional to N b .
In the next section, simulation results are presented to give an idea of the accuracy of equation (6.45).

Validation of the RLS-DFE equation
The simulation results use the same channel models and simulation conditions as in previous sections. As in the DFE-LMS, the FFF length has been set to N+1 where N is the channel length. The number of feedback taps has been set to N-1. RLS-DFE performance in practical scenarios is deferred until chapter 7. 6.7.1 Channel model 1 MSE curves for Channel model 1 are shown in figures 6.19 and 6.20 for 2 q σ =10 -4 and 2 q σ =10 -6 respectively. In general, and for this particular channel, good agreement exists between the predicted and measured MSE. However, notice that in scenarios subject to fast variations ( figure 6.19), the predicted MSE tend to be larger than the simulated MSE. This tendency is more accentuated as the E/No gets larger, but over a reasonable range of E/No, such as from 5 to 25 dB, the maximum divergence between prediction and simulation is only   Again, some discrepancy (still within a dB) between the predicted and simulated MSE is found in a large E/No scenario with rapid channel variations. Notice however, that unlike the previous channel model, the predicted MSE is much closer to the real performance than the plain MMSE. This indicates that in this particular scenario the EMSE components predicted in equation (6.45) are significant, about 5-6 dB over the MMSE and therefore their effects should be taken into account.
When this channel varies slowly, as happened also in Channel model 1, the true MSE performance and also its predicted level, approach the MMSE. The difference between the predicted and simulated MSE is about 1-1.5 dB. So, for example, it can be inferred from the predicted MSE curves that there is a significant improvement when the equaliser is expanded from 6 to 12 taps. On the other hand, it can also be deduced that extending the equaliser to 18 taps will only reduce the MSE level by a small amount.
Both conjectures are seen to be true by examining the simulated results.    In figure (6.24) the effect of the FBF length is studied under the same conditions as described for figure (6.23). As in the FBF length study for the same channel model when using the LMS algorithm, it can be seen that, when the number of taps in the FBF exceeds N-1 (N= channel length), there is not any reduction in the MSE level. Although there is a gap of about 1 dB between the predicted and simulated MSE, it is clear that equation (6.45) already confirms this phenomenon. Overall, a good agreement is observed between predictions and simulations.

Conclusions on the derived MSE equations
So far, this chapter has been devoted to finding and validating expressions for the steadystate MSE of a DFE when using the LMS (equation (6.16)) and RLS (equation (6.45)) algorithms to perform the coefficients update. Given their importance, these expressions are re-stated next:

RLS-MSE
It might be argued that both expressions are useless in practical scenarios as some of the parameters in them will not be known a-priori. σ ), three parameters can be used to adjust the performance of the equaliser, namely: N f , N b and the algorithm parameter ( µ or λ ). In mobile radio systems, where the environment is subject to a wide range of potential variations, these parameters will rarely be optimum all the time. Therefore, it would be desirable to adjust them accordingly in response to changes in the environment.
As has been said in section 4.10, adaptive algorithms with time varying parameters have already been studied in the past. On the other hand, and as in linear equalisation, dynamic variations of the FFF and FBF lengths have received no attention at all 20 . Our interest for the rest of this chapter is to investigate in detail how N f and N b influence the MSE performance in a DFE and also to study the potential reconfiguration of the filters' length to better withstand changes in the environment. 20 To the best of author's knowledge.

DFE MMSE results
The Lastly, p denotes the cross-correlation between the current sample being detected, d(n), and the input vector u(n). The solution given by w opt will produce the minimum mean squared error (MMSE) between the output of the equaliser and the detected symbol. Notice that in equation (6.46), a determined decision delay D, is implicitly assumed. In [Voois96] it is shown that under the assumption that the FBF is made sufficiently long, the optimum delay from an MSE point of view, approaches D=N f -1. Later on in this chapter the issue of delay choice is covered in greater detail.
The combined FFF (feedforward filter) and CIR (channel impulse response), z, is given by: where * denotes the linear discrete convolution. Notice that z will have N f +N-1 taps. Figure   6.27 shows a generic FFF-CIR combined response. In the figure it can be seen that the precursor ISI is very much reduced by the action of the FFF. The FBF will take care of suppressing the postcursor components. The FFF settings are set so that a compromise is reached between the levels of ISI pre and filtered noise. ISI post is completely eliminated provided the FBF has enough taps. Given the finite length of the channel and FFF and having set the delay to N f -1, it is easy to see that there are N-1 postcursor samples (see figure 6.27). An FBF longer than N-1 taps will not decrease the MMSE level any further.
The length of the FFF depends very much on the position of the main peak of energy within the CIR. In practical applications, the strongest paths are usually concentrated at the beginning of the CIR and therefore a short FFF is enough to capture most of the energy ([Ariyavisitakul97]) and significantly reduce the amount of ISI pre without excessive noise enhancement.
The following set of graphs (6.28 to 6.31) shows the dependence of the MMSE level on the number of taps in the FFF and FBF. The results shown in figures 6.28 and 6.29 correspond to a DFE equalising Channel model 2 for E/No=5 dB and E/No=25 dB respectively. The delay in both cases was set to N f -1=5. In both cases, a FFF of 5-6 taps is enough to achieve the minimum attainable MSE level. Regarding the FBF length clear differences can be appreciated. While for E/No=5 dB, 3 taps is enough to approach the minimum possible MMSE, for E/No=10 dB the FBF needs to be expanded up to 10 taps. Notice that for this particular channel, and as has been explained in a paragraph above, the longest the FBF needs to be is 10 taps as this is the number of postcursors in the FFF-CIR combined response.
Attention is now turned to figures 6.30 and 6.31 where the same data is presented but now equalising Channel model 3. As before, a FFF 5-6 taps long is enough to cancel out most of the precursor ISI. As for the FBF, 4 taps are required to cancel out all the postcursors.
What can be inferred from these simple examples and has been covered in previous studies ([Ariyavisitakul97]) is that the FFF will typically be short, just long enough to capture the main peak of energy of the received signal whereas the FBF length depends very much on the particular CIR. If the CIR is very long, many taps will be needed to reduce the postcursor interference. On the other hand, if the CIR is short, only a few FBF taps are required.    In order to get an idea of the variety of possible channels found in a mobile system, it is useful to look at the COST207 channel models (pp. 728 in [Steele99]) developed during the GSM study phase. The delay spread of these models varies between 0.5 µ s in rural areas up to 20 µ s in hilly terrain.
The number of taps required to cancel out all the postcursor interference will obviously depend on the signalling rate, however it should be clear that the spread of ISI post is very variable. This suggests that in a DFE, the FBF is more suitable for reconfiguration given its potentially wide range of taps whereas a short fixed-length FFF is able to cope with most of the practical scenarios.

Motivations for a DFE with variable length FBF
Given that the required number of feedback taps to cancel out all the ISI post is deemed to be N-1, and that N depends very much on the particular environment, we could design a "worstscenario" DFE with enough taps in the FBF so as to cancel the longest possible channel.
This approach presents three problems. The most obvious and important inconvenience is the waste of resources this method implies, as in many situations the equaliser will be oversized.
The second problem arises from the use of adaptive algorithms such as the LMS and RLS to perform the coefficient update. These algorithms do not produce the exact optimum solution but instead, as is seen in equation (6.16) and (6.45), they introduce an excess mean squared error (EMSE). The FBF taps beyond N-1, which in theory should be zero, will not be zero in practice due to the use of a step size greater than zero (LMS) or a forgetting factor smaller than one (RLS). These excess taps introduce a third source of ISI, which we call Excess ISI energy and is given by: Erroneous symbols in the FBF reduce the noise margin for future decisions, increasing in this way the probability of error. The classic paper of [Duttweiler74] shows that in high E/No, the error probability is multiplied by at most a factor of 2 Nb relative to the error probability in the absence of decisions errors. In [Gitlin92] an intuitive explanation of this result is presented on the basis of the following three facts: 1. All errors are cleansed from the FBF when N b consecutive corrections are made.
2. The probability of making an error is no bigger than ½.
3. Let K denote the number of symbols needed to make N b correct decisions (K= error propagation length). Since a single error produces on average K/2 errors, the average error rates is (K/2)P 0 where P 0 is the probability of making an error when all the symbols in the FBF are correct.
It is clear that if the FBF is unnecessarily long (i.e. longer than N-1 taps), the potential error propagation will also be increased.  From previous paragraphs, it seems desirable to be able to adjust the length of the feedback section depending on the instantaneous channel characteristics. This would help to avoid the unnecessary update of taps (reduction in computational complexity), eliminate the ISI excess component and reduce the potential error propagation.

FBF length update algorithm
The algorithm controlling the length of the FBF filter, as in the case of the linear equaliser length update, should have two properties: first, it should only use information which is available at the receivers and secondly, it should be computationally simple. The solution we propose is to use the following test iteratively to control the length of the FBF: and if (6.55) The heuristic of the algorithm is very simple: if the power of the last active tap in the FBF is significant with respect to the MSE level, an extra tap is added. If the power of the last two taps in the FBF is significantly smaller than the MSE level, the last tap in the FBF is switched off.
The idea of the algorithm is to detect the length of the CIR-FFF combined response and adjust the FBF length appropriately. The parameter χ acts like a "tuner" to control whether a tap power is significant or not. If χ is very small, for example χ =0.001, the algorithm tends to enlarge the FBF so as to cancel all postcursors of the CIR-FFF response. When χ is large, for example χ =0.1, the algorithm considers the small components of the CIR-FFF response as noise and therefore the FBF is kept short. The algorithm is based on using the last two It is important to recognise that the algorithm always uses one more tap than those considered as "true cancelling" taps. This additional coefficient serves as a watchdog to detect when the CIR is getting longer. When this happens, this last tap will start to have some significant value with respect to the MSE and an extra tap is added.
The problem with the test/algorithm given by equations (6.54) and (6.55) is that the true ensemble values of the FBF taps will not be available in practice. However, assuming ergodicity of the tap values, the ensemble averages can be substituted by time averages.
Given that the environment is likely to change, the time averages are performed over a time When n=kW (k is an integer): The algorithm given by (6.57)-(6.60) is the temporal and windowed version of the one given by equations (6.54) and (6.55). Notice that divisions are avoided in the algorithm by making the comparisons of the accumulated tap power with a scaled version of the MSE (scaled by W). The length of the window, W, will depend on the type of environment in which the receiver has to operate. In the context of mobile systems where variations may take place in a very rapid and sudden way, it is advisable to use short windows. In the simulations presented in the next section, W was set to 150 samples.
As a final point, notice that the computational complexity of the algorithm given by equations (6.57)-(6.60) is very low. Only (6.57) and (6.58) are computed for each symbol and each of them only performs one multiplication and one addition.

Simulations using a FBF with variable length
In this section, results obtained when using the FBF length update algorithm are presented.
First, the algorithm is used to predict the adequate number of feedback taps to be used in a static unknown environment. In subsection 6.11.2 the behaviour of the algorithm is verified when there are sudden changes in the channel impulse response. Finally, in subsection 6.11.3 the response of the algorithm to sudden jumps on the signal level is investigated.

Static channels
The aim of this set of simulations was to check whether the algorithm was able to correctly estimate the right number of feedback taps to be used when confronted with an unknown static channel.
The simulations have been performed using the same channel models used previously. In Note also that when χ has a small value such as χ=0.001, the FBF length presents some oscillations. These fluctuations are due to the high sensitivity of the algorithm when χ is so small. Finally, notice also that in this case, χ=0.001, for both E/No levels the FBF length is on average slightly greater than two taps (around 2.3 for E/No=5dB). This is again due to the high sensitivity of the algorithm, which sometimes considers the noise in the last tap as a true postcursor and therefore increases the length. This effect is more obvious for the low         When χ takes a small value, the algorithm sets the FBF length to an average of around 5.5 taps. This slight increase with respect to the optimum length is due to the high sensitivity of the algorithm, which is accentuated by the resulting large steady state MSE level when equalising this particular channel with a very low E/No. When E/No=25 dB (figure 6.41), any χ value makes the FBF enlarge up to five taps. Notice that the larger χ is, the longer it takes the FBF to achieve the definitive length. This illustrates the fact that the choice of χ influences both the length attained and the amount of time required to get to that length.
From the results presented in this subsection, it can be concluded that the FBF length update algorithm is able to predict, with very good accuracy, the number of taps to be used in an unknown environment.

Abrupt changes in the channel profile
In this section, the behaviour of the FBF length update algorithm is investigated when confronting sudden changes in the channel impulse response. It is with this type of scenario that the technique has proven to be most useful, as the FBF is able to adjust its length The results are compared with those obtained using a fixed 11-tap feedback filter in terms of performance and number of computations. The simulation length was set to 180,000 samples with the abrupt changes taken place at iterations 60,000 and 120,000. As in previous sections dealing with abrupt changes and given its wide variance, the MSE is windowed over a temporal length of 2,000 samples. In all situations the FFF filter has been set at 6 taps and remains fixed during all simulations. It is crucial to notice that the performance when the system confronts Channel model 1 is the same for all equalisers. In particular, the 11-tap fixed equaliser does not perform any better than any of the variable length ones, which during this interval are reduced to just two FBF taps. This is the main benefit of the FBF length update algorithm: the potential savings in computation when the channel spread is short. The same conclusions as for the 5 dB situation can be drawn.        In figure 6.50, when E/No=5 dB, it can be seen that when χ=0.001, the FBF length update algorithm recognises this change to a channel profile with a shorter delay spread and starts to decrease the FBF length. It should be noted however, that the FBF reduction takes place very slowly. This is because the steady state MSE when equalising Channel model 2 is fairly large, a condition accentuated by the low E/No in this particular case. This extremely large MSE (notice in the graph the MSE level is about -1.5 dB) slows down the length adjustment process.
The curve for χ=0.1 in figure 6.50 shows another interesting property of the algorithm. After the transition to Channel model 3, the FBF grows. This may seem inconsistent with the fact that the channel delay spread is getting shorter. The explanation is that, although the new channel is shorter, its postcursor components are now stronger and so the FBF expands (compare power profiles for Channel models 2 and 3 in chapter 3). Additionally the use of the VSLMS algorithm, which tends to reduce the step size in the steady state phase, helps in keeping the ISI excess (equation 6.53) to an insignificant level.
From both profiles of abrupt channel changes it can be inferred that the algorithm given by equations (6.57)-(6.60) is able to determine which is the most appropriate number of taps to be used in the FBF according to the instantaneous channel profile.

FBF length update algorithm: final remarks
In order to conclude the study of the DFE and more in particular of the FBF length update algorithm, some of its potential problems are considered.
Given that the FFF remains fixed, the dimensions of Γ Γ Γ Γ (n) will not change. However the FBF length changes will affect Λ Λ Λ Λ (n), Λ Λ Λ Λ T (n) and I. The key point is to analyse the contents of Λ Λ Λ Λ (n) which in this case, (6,11)-DFE and Channel model 2, would be: 23 Notice that the notation used for the submatrices of Φ Φ Φ Φ (n) is the same as the one used for the submatrices of R(n) but in this case, the averages are temporal. Suppose that now the channel abruptly changes to Channel model 1 (2 taps). When this happens, and due to the effect of the forgetting factor, many of the entries of Λ Λ Λ Λ (n) will quickly tend to zero and eventually Λ Λ Λ Λ (n) will become: Remember from the previous chapter that the source of the instability was in the update of the inverse of the correlation matrix, P(n). If the FBF reduced from to 11 taps to 2 taps, the correlation matrix, Φ Φ Φ Φ (n), will now have dimension 8x8. However, when this happens and unlike in the LE situation, the inverse of the new correlation matrix, P 8x8 (n), can be extracted from the inverse of the higher order matrix P 17x17 (n) because, due to the new zero columns and rows: This implies that when changing the FBF length, the only thing to be done is to re-size the vectors and matrices involved in the RLS algorithm. Notice that in this example and in order to simplify the presentation it has been assumed that the FBF shrank from 11 to 2 taps in one step. Using the proposed length update algorithm, this reduction will take place tap by tap, with a transient stage between reductions that would allow the correspondent column and row of Φ Φ Φ Φ (n) to converge to zero.
When the FBF is expanded, as the LE case, there are no stability problems and only re-sizing of the appropriate vectors and matrices is required.

Sparse channel impulse responses
The algorithm has been shown to work on the basis of using a dummy tap (the last one) to detect when the channel grows. This mechanism works well when the channel expands in continuous way. To be more accurate, when the combined CIR-FFF evolves in a way such that it does not contain "holes".
If the channel is sparse, these holes are likely to appear and this is worth taking into account.
Consider a situation where, due to changes in the CIR, the combined CIR-FFF response varies from figure 6.60 to figure 6.61:  In these figures, the tap with highest magnitude corresponds to the detected sample, the previous samples are the precursor ISI while the posterior samples correspond to the postcursor ISI components. If the FBF length update algorithm is used when operating in the channel of figure 6.60, the FBF will be set to 4 taps (3 cancelling taps plus the detection tap).
Suppose that the channel suddenly changes to the one in figure 6.61 where some sparse components appear towards the end of the CIR-FFF response. In this scenario, the FBF length update algorithm will not be able to expand the FBF to cancel the new postcursors.
The reason is that the detection tap, which will be monitoring the sample number 10 in figure 6.61, will not register any increase in its power and will prevent the FBF from expanding. Notice that in order to get a sparse tap (one with zero magnitude) in the CIR-FFF combined response, there must be a hole of N f samples in the CIR response, assuming that the magnitude of the FFF coefficients are all greater than zero (albeit arbitrarily small).
Sparse channels do occur in practice. In the COST207 channel specifications there is a particular model corresponding to hilly terrain with a gap in the CIR of about 10 µ s (pp. 628 in [Steele99]). One possible solution to allow the FBF length update algorithm to detect these sparse components would be to enlarge the FBF periodically up to its maximum length. From there, the algorithm would shrink the FBF down to the point where the last components, sparse or continuous, are located.
Exploitation of sparsity in adaptive filtering is a current topic of research, see for example [Martin01a], [Martin01b] and [Berberidis00].

Realistic simulation environment
In chapters 5 and 6, novel techniques have been presented to adjust dynamically the number of taps in different types of equalisers. There, the simulation environment used was a rather simple one as the main objective was to highlight how the algorithms worked and the potential benefits of adjusting the equaliser length. It is however mandatory to verify that these algorithms and structures are also able to perform satisfactorily in a realistic mobile scenario.
As explained in chapter 2, equalisation is, or can be, applied in one form or another in nearly all cellular standards. Consequently, the simulation environment designed for this set of simulations is not specifically targeted to any particular standard although some of its parameters are taken from the UMTS (W-CDMA) specification ( [3GPP00] Generated symbols are then BPSK modulated and subsequently band limited with a square root raised cosine filter (SRRC) with a roll-off factor of 0.22. The carrier frequency used for transmission is 2 GHz which is the frequency band selected for most 3G standards world wide. At the receiver, another SRRC filter is used to perform matched filtering on the incoming signal. The equaliser will reduce the effects of multipath propagation and will present "cleaner" samples to the threshold detector. In a practical system, error correction coding/decoding would also form part of the transceiver chain. However, in the context of this work, the focus lies only on the equalisation subsystem.
In order to get an idea of how the equaliser performs in real conditions, it is fundamental to use a channel that accurately models the physical channels encountered in practical mobile scenarios. For this purpose, a Rayleigh fading generator has been implemented ([Proakis95, pp 45-46, 767]).
In order to construct a Rayleigh process, two coloured Gaussian processes need to be generated. Here "coloured" means that the originally white Gaussian processes are filtered with a filter whose bandpass spectrum is given by the Doppler spectrum at a particular centre frequency and mobile speed. Two methods are available to generate such processes. The most obvious technique consists of filtering samples of white noise with a filter whose spectrum equals the Doppler spectrum ( [Laurenson94]). This method presents the drawback that, given the sharp spectrum generated by the Doppler phenomenon, the filters are also required to have very sharp stopbands, which in turn implies using many coefficients.
The alternative method used in this work, known as the Sum of Sines or Jakes model  The figure above shows how the two independent coloured Gaussian processes, µ 0 and µ 1, are obtained using the Sum of Sines model. The outcomes from these processes are then summed in quadrature and the norm taken. The resulting output is a sample of a Rayleigh variable whose fading rate is given by the chosen Doppler spread.
The fading process described in previous paragraphs may apply to all or some of the paths in a multipath profile. In this chapter, extensive use has been made of the COST 207 Typical Urban profile depicted in figure 7.3 [Steele99]. The model specifies that, in this particular case, all six paths are subject to Rayleigh fading. It is therefore necessary to maintain an independent Rayleigh fading generator for each of the paths.

Variable length LE in realistic scenarios
In this section, the behaviour of the variable LE in realistic conditions is presented. Results are compared in terms of performance and computational complexity with those obtained using fixed length LE. In all the simulations presented in this and forthcoming sections, the variable step size LMS (VSLMS) algorithm has been used to drive the filter coefficients.
This algorithm has proven to be very robust in a wide variety of scenarios.

Effect of the equaliser length on a mobile channel
In chapter 5 the effect of the equaliser length has been studied for some static channels. In this section, a similar study has been conducted, using the reduced COST207-TU channel described before under different levels of Doppler spread.
The steady state MSE levels, measured after 100,000 iterations, are shown in figures 7.4 and 7.5 for two different E/No levels and different equaliser lengths. The decision delay was set to 8 samples, therefore the equaliser lengths were chosen to be longer than 8 taps as otherwise the LE would not be able to capture the main peak of energy.
There are a few points worth noting in these graphs. First, the steady state MSE for the different equaliser lengths are now much larger than when dealing with a static channel with similar characteristics. As an example, compare figures 7.4 and 7.5 with the curves in figure   5.3 corresponding to Channel model 2 being equalised using the LMS algorithm 24 . The MSE 24 Remember that Channel model 2 was a "frozen" version of the COST207-TU profile used in this chapter.
is larger due to two factors. First, channel variation introduces tracking misadjustment.
Second, these variations may turn a fairly good channel into a very bad one with larger steady state MSE. Nonetheless, the important point to be noticed in these graphs is that again      3 taps per segment, up α =0.6, dw α =0.9 and β=0.999. The initial number of taps was set to 9, since the decision delay was chosen to be 8. The MSE is seen to converge to around -3 dB which is the lowest MSE achieved by any of the fixed length equalisers. In figure 7.7 the length evolution of the equaliser is shown. The equaliser length can be seen to remain always between 12-13 taps, avoiding the MSE increase that would result if a longer equaliser was used.
In figures 7.8 and 7.9 the same results are presented but now for E/No=25 dB, using the same parameters as before for the length update algorithm. Notice in figure 7.9 that now the length update algorithm is able to recognise the better conditions of the link and expand the equaliser up to around 20 taps which is the optimum value for fd=200Hz and fd=400Hz. For       In order to get an idea of how the variable length equalisers perform with respect to a classical equaliser some simulations need also to be run using a fixed length equaliser. The choice of the equaliser length is rather arbitrary and in this case, the common rule of thumb of making the equaliser 2N+1 taps long (N=channel length) has been used. Knowing that the channel is 11 taps long, the equaliser length was set to 23 taps.  The one with up α =0.6, dw α =0.9 offers a reduction of up to 30% in the number of operations with respect to the fixed equaliser, although in this case some performance degradation is observed. The savings of the variable length structure come from the fact that it is able to reduce its length when E/No is low.
It is worth stressing one point of this previous set of simulations: when choosing the length of the fixed equaliser, although using a rule of thumb, some knowledge has been assumed about the channel length. When using the variable length LE no such assumption needs to be made as the equaliser will adapt to an adequate length. Also, notice that the potential savings offered by the variable length LE depend strongly on the specific channel conditions.
Nonetheless, the variable LE has been shown to work satisfactorily in many different scenarios.

Abrupt channel change
The next realistic scenario tested resembles that of section 5.4.5 in that there is also an abrupt change in the channel profile, but now the channel is also subject to Doppler spread.
The simulation starts using the reduced COST207-TU channel model and after 100,000 iterations, it suddenly changes to a static single path channel. After another 100,000 iterations, the channel changes back to its original model.  respectively. These have been obtained when using a fixed equaliser whose length is again selected to be 23 taps. This type of abrupt channel change is common in mobile scenarios, as a consequence of a handover from one base station to another or a sudden change in the environment such as entering/exiting a building. Note the significant drop in the MSE after the first abrupt change as a result of the system operating in a far more favourable channel. It is also worth appreciating that the higher Doppler of the channel in figure 7.17 causes larger MSE fluctuations than in the results shown in figure 7. 16 Also important is to highlight that when E/No=5 dB, the algorithm correctly recognises that there is no improvement in expanding the equaliser and therefore is kept at 11-12 taps.
Turning now attention to the case of f d =200 Hz (figure 7.23), it is very clear that the equaliser changes length far more often than when fd=10 Hz. This is perfectly logical as the faster channel changes make the optimum number of taps more likely to vary. In the case of a large Doppler effect, the equaliser tends to be kept slightly shorter than when the Doppler spread is low. This could also be seen in figure 7.5, when fixed equalisers of different lengths were tested under various levels of Doppler spread.       It is worth noting once more that, in a practical system, the equaliser would be followed by Once more, it is worth emphasising that the profiles used for these simulations are not tailored specially to favour the variable length structures. The nice property of the VL LE is its ability to adjust the number of taps to those that are significant to the equalisation process.

Variable length FBF-DFE in realistic scenarios
This section uses simulation results to examine the performance of a DFE with a variable length FBF (referred to as VL FBF DFE) when operating in a realistic scenario. Its results are compared with those obtained using a DFE with a fixed length FBF.

Effect of the FBF length in a realistic scenario
In the last chapter, some simulation results were presented showing the effect the FBF length has on the MSE level when operating in a static channel. Now the study is repeated but with the additional feature that the channel is subject to Doppler spread. For the simulations in this and future sections, the FFF length has been set to 6 taps, as making the FFF longer will not reduce the MSE (see Chapter 6). The delay has been set to 5 samples (N f -1

Abrupt channel change
To conclude this set of simulations, the behaviour VL FBF DFE in response to a realistic abrupt change in the channel profile has been checked. The sudden channel change is exactly the same as the one used in section 7.2.3, namely, starting with the reduced COST207-TU channel and changing, after 100,000 iteration, to a static single path model. After another 100,000 bits, the channel changes back to its initial profile. The scenario has been verified in two different Doppler conditions, f d =10 Hz and f d =200 Hz.  In order to be able to compare of the performance the VL FBF DFE with that of a conventional DFE, some simulations have been run using a fixed length (     In theory, and to a certain extent in practice, convergence time could be improved by further reducing χ. However, in this realistic scenario, this has proved to be a difficult adjustment to do as using a very small χ tends to affect the performance in low E/No (the FBF expands to its maximum value). Therefore, a compromise value for χ must be determined, which in this case, we have found by simulation to be between 0.0075 and 0.01. An alternative solution to this convergence problem would be to initialise the FBF to its maximum length and let the algorithm controlling the FBF length reduce it appropriately.

RECONFIGURABLE EQUALISERS
Nowadays, most terminal handsets use fixed-point arithmetic to perform the different signal processing operations. The reason for this choice is that fixed-point devices (DSP, FPGA, ASIC), when compared with their floating-point counterparts, offer important reductions in power consumption, which in turn translates into extended battery times. It is therefore important when designing algorithms to be used in the handset side to verify that they work under fixed-point constraints.
The main objective of this chapter is to show that the length update algorithms for the LE and DFE presented in previous chapters also work when they are implemented on a fixedpoint device. To verify this, the algorithms and simulation environment have been implemented on a Texas Instruments TMS320C5402 DSP. This particular DSP is widely used in many commercial handsets to perform the baseband processing. In a way this chapter complements the results presented in chapter 7. In there, we proved that the algorithms work under realistic physical conditions. Here we show that the algorithms perform well when implemented on a widely used commercial device.
In section 8.1 some background information is provided regarding fixed-point arithmetic and the problem it causes. Section 8.2 briefly comments on the different types of devices suitable to implement signal processing operations, namely ASIC, FPGA and DSP. Section 8.3 presents the development environment and processor used to implement the fixed-point version of the algorithms. It also shows and comments on the fixed-point assembly code generated to implement the length update algorithm for the LE and DFE. In section 8.4 simulation results are shown that prove the robustness of the algorithms to fixed-point inaccuracies. The chapter ends by summarising the main conclusions to be extracted from this implementation.

Fixed-point vs floating-point arithmetic 26
The mathematical descriptions of signal processing functions such as the adaptive filtering and length update algorithms presented in previous chapters implicitly make use of infinite numerical precision. However any algorithm implemented on a digital processor can only utilise a finite number of bits to represent the different variables. This transformation from infinite to finite arithmetic, called quantisation, may influence significantly the performance of an algorithm. A clear example of this is the SFAEST algorithm (and other Fast Kalman algorithms) where finite precision effects cause severe instability problems (see chapter 2).
Another example is the design of digital filters whose poles are very close to the unit circle.
In this case, the quantisation error may move the poles outside the unit circle making the filter unstable.
There are two basic formats to represent numbers with a finite number of bits: floating-point and fixed-point. We will refer to the number of bits, typically 16 or 32, used to represent a number as a word. In floating-point representations, the binary point that separates the integer and fractional parts may vary its position within the word. In contrast, in fixed-point representation, the binary point is constantly fixed at the same position within the word. The use of finite length arithmetic significantly influences the performance of adaptive algorithms such as LMS and RLS with the introduction of new error terms (chapter 17 in [Haykin96]). These factors can be seen as new forms of excess mean squared error (EMSE).
Consequently, their influence must be taken into account when choosing algorithm parameters such as step size in the case of LMS and the forgetting factor for the RLS.
Additionally, undesired behaviour like gain stalling or explosive divergence may appear and therefore mechanisms to minimise their effects must be used. An example of one of these mechanisms is the leakage technique introduced in [Gitlin82] to make the LMS more robust when implemented on finite precision. Thus, it is very important to verify the performance of any signal processing algorithm when implemented on finite length arithmetic, especially 27 The dynamic range of a numeric system is defined as the ratio between the largest and smallest magnitudes that can be represented.
if the target device uses fixed-point arithmetic. This will be the objective of sections 8.3 and 8.4, but first a brief survey of the available technologies to implement signal processing systems is given in the next section.

Technologies for signal processing implementation
One of the most critical decisions when designing a signal processing system is deciding which semiconductor technology to use for its implementation. Nowadays the choice is typically one of the following: • Digital signal processor (DSP) • Application specific integrated circuit (ASIC) • Field programmable gate array (FPGA) The first two types of device have been the classical technologies used to implement signal processing functions whereas the FPGA is a relatively new type of device whose characteristics offer a compromise between the other two ( [Tessier01]). Each of these technologies is now briefly discussed.
DSPs are microprocessors specifically targeted for signal processing operations. They usually have two separate buses and memory spaces, one for data and one for instructions Their main advantage is flexibility as they can be programmed to do any task. The fact that the functionality of the DSP is mainly determined by the software running on top of it, means that modifying its function is just a matter of loading a new program on the DSP, easing in this way the maintainability of the system.
On the other hand, their major drawback is the lack of specialisation, which implies that they are not optimised for any particular DSP operation. This sets upper bounds to the performance of DSPs for certain operations.
The classic alternative to DSP implementation consists of using ASICs. As the name implies, an ASIC is a device designed to perform a very specific function. Its main advantage is the superior computational performance when compared to a DSP.
Additionally, the fact that the ASIC contains just the elements needed may help in reducing the chip count of a system and, consequently, board area ( [Ackenhusen99]). An important consequence of this reduction in the number of components is a reduction in the power consumption ( [Tessier01]). The main drawback of ASIC technology is the long design cycle required to implement an algorithm on custom silicon ( [Ackenhusen99]). This, coupled with its lack of flexibility, makes the time to market of ASIC based products considerably longer than in the case of software based systems such as DSPs.
Over recent years, considerable attention has been given to the signal processing capabilities of FPGAs 28 ( [Tessier01]). An FPGA is a device containing a matrix of equal combinatorial FPGAs offer levels of performance similar to those of ASICs as they are specifically configured to perform a specific task. On the other hand, the fact that their functionality can be altered, just by loading a new configuration sequence, confers them a high degree of flexibility.
Use of FPGAs for high performance signal processing applications has already been reported by many authors. In [Srikanteswara00], a single user (i.e. terminal) CDMA receiver was designed around the Xilinx XC4028EX. The tasks of the FPGA included equalisation and despreading using an adaptive filter whose coefficients were updated with the LMS algorithm. Thanks to the reconfiguration capability of the FPGA, parameters such as 28 FPGA is a name coined by one particular manufacturer (Xilinx), nevertheless, it is often used to denote reconfigurable logic devices in general.
adaptive algorithm, step-size, filter length and spreading code could be arbitrarily selected.
Efficient techniques to implement adaptive filters on FPGA can be found in [Allaire97]. Figure 8.1 shows the trade-offs between performance and flexibility of the different technologies. It is unlikely, at least for the foreseeable future, that a single technology can be used to implement all the signal processing functions of a radio communications receiver.
Instead, combinations of the three types of device are used ( [Rabaey98]). In the context of CDMA receivers, the baseband processing at symbol level, such as source and channel coding or encryption, is typically performed on a DSP, whereas chip level processing such as de/spreading or multiplexing is implemented using either ASICs or FPGAs ( [Tessier01]).
Nonetheless, the trend is to move more and more of the processing onto the DSP and some

DSP environment and implementation
In this section details of the implementation of the length update algorithms for the LE and The generic procedure to implement a signal processing algorithm on the board is as follows: first the algorithm is coded in either C or Assembly. After compilation, the binary generated code is downloaded (via parallel port) to the memory on the DSP board, when execution can begin. During run time, several methods are available to monitor the execution of the program, for example, real-time graphics monitoring some particular parameter can be obtained. Once the program has finished, control returns to the development environment on the host computer.

Implementation of variable length equalisers with fixed-point arithmetic
In order to verify the performance of the length update algorithms for the LE and DFE on a fixed-point device, the simulation environment described in chapter 3 was implemented on the DSK in C language. The LMS algorithm has been used for all the simulations presented in this chapter. In theory, in order to avoid the undesired effects fixed-point arithmetic has on the LMS algorithm (see section 8.1), some changes to the algorithm would need to be included (such as the variation described in [Gitlin82]). However theory predicts that these effects, in the case of the LMS algorithm, only become significant after the algorithm has been operating for a long time. In this chapter, and in fact in the whole project, simulation lengths have been kept relatively short and therefore the plain version of the LMS can be used even when implemented in fixed-point arithmetic.
There is one important point to mention regarding the development of C programs for a fixed-point device. In theory, only fixed-point variables could be used. However in the environment used in this project, the use of floating-point variables was allowed provided a certain library was included. This library has the task of making the conversion floatingpoint to fixed-point arithmetic whenever one of these variables is used. This greatly eases the development of fixed-point applications, but at the cost of producing very inefficient code [Kuo01]. This inefficiency is caused by the numerous calls to functions in that library to make the conversions. Nonetheless, this method for fixed-point development is useful to verify the correct functioning of an algorithm in this type of arithmetic.
The resulting fixed-point assembly code of the length update algorithms for the LE and DFE is presented below. The algorithms were implemented in C using floating-point variables.
Consequently this code cannot be regarded as very efficient but it serves the purpose of validating the algorithms under fixed-point arithmetic.
Some comments about this code are now in place. Each line in the assembly listings has one assembly instruction and a number between bars (|xxx|). This number corresponds to the C source line from which that assembly instruction has been generated. Obviously, one line of C source generates many more lines of assembly code. Also included in the listings below, are comments (in capital letters) relating groups of assembly instructions with the equations of algorithms 5.2 (variable length LE) and 6.1 (DFE with variable length FBF).
Finally notice in the assembly code the presence of many lines like this: These instructions are those calling routines to perform operations with floating-point quantities (in this particular case, a subtraction). In an efficient implementation, none of these calls would appear.

Simulation results for variable length equalisers using fixed-point arithmetic
In this section, simulation results obtained using the DSK are presented. In particular, the aim of the results shown next is to verify the correct functioning of the algorithms controlling the equaliser length when implemented on a fixed-point device. These results have been obtained when using the length update routines presented in the previous sections and using the LMS algorithm to drive the equaliser coefficients. it was shown that the length update algorithm (algorithm 5.2) was able to predict this optimum number of taps, but in that case double precision arithmetic was used. When the channel changes to the single path profile, which in theory would require no equalisation at all, the length update algorithm shrinks the equaliser to 6-7 taps.  Recall that the decision delay was set to 5 taps so the equaliser will never reduce below this number of taps. When E/No=5 dB, the length update algorithm detects the large noise level and only expands the equaliser up to 12 taps when operating in Channel model 2. The important point, once again, is that even when implemented on fixed-point arithmetic, the variable length LE is able to select dynamically the adequate number of taps to be used in the equaliser.
The next series of graphs show the results obtained when using the fixed-point versions of the algorithm controlling the FBF length in a DFE. The FBF had an initial and minimum length of 2 taps and the parameter χ was set to 0.01. The length of the FFF was fixed to 6 taps. In these fixed-point simulations, the FBF is expanded to 11 taps for E/No=25 dB and 9 taps for E/No=5 dB, which in both cases is very close to the ideal FBF length, 10 taps.
Comparing these results with those obtained using double-precision arithmetic (section 6.11.1), it is noticeable that the fixed-point results using χ=0.01 are very similar to those obtained when using χ=0.001 with double-precision arithmetic (figures 6.33 and 6.34).  From figures 8.5 and 8.6, it is clear that the algorithm is able to "guess" how many taps must be used in each case without any a-priori knowledge of the environment.

Implementation conclusions
This chapter has served various purposes. First, it has briefly considered some important issues, such as quantisation, that must be taken into account when implementing an algorithm on real hardware. Secondly a quick review of semiconductor technologies suitable to implement signal processing functions has been presented. Finally, fixed-point versions of the length update algorithms for the LE and DFE have been presented and tested in order to verify their correct functioning on a commercial DSP device. Simulation results have shown that variable length equalisers continue to perform very well when implemented with fixedpoint arithmetic.

WORK
The final chapter in this thesis summarises the work done in this research project. Some suggestions for further research are also presented.

Conclusions
Our work has focused on possible forms of reconfiguration for adaptive equalisers, in particular linear equalisers (LEs) and decision feedback equalisers (DFEs), in the context of downlink mobile communications. These forms of equalisation have traditionally been used in TDMA mobile systems but recently their effectiveness in CDMA receivers has also been proved. Therefore, the results achieved are relevant to nearly any modern mobile standard.
LEs and DFEs are implemented using digital filters with a finite number of taps. The main question this work addresses is: "How long, in taps, should the equaliser in a mobile receiver be?". Even in the general context of digital communications, this apparently simple question has not found a definitive answer in the last 37 years since the adaptive equaliser was invented back in 1965. In the specific case of mobile handsets, and given that the equaliser length is directly related to power consumption, this issue becomes very relevant.
Our objective in this project has been the development of techniques to adjust, according to the channel conditions, the number of taps used in the equalising filters.
To that end, we have confirmed that the appropriate equaliser length, as was already known, depends strongly on the particular scenario in which the receiver is operating. Namely, it depends on the specific channel impulse response and noise/interference level. The adaptive algorithm (LMS and RLS have been considered) used to perform the equaliser coefficients adaptation has also been found to influence the length to be used.
In order to verify these dependencies, steady-state mean squared error ( From the point of view of our work, it is important to observe how the equaliser length is related to each of these components. It is known from theory that adding taps to the equaliser will always provoke a reduction in MMSE level. However, it has been found by simulation that after a certain number of taps, the MMSE reduction is completely insignificant. On the other hand, the addition of taps will cause a reduction of the EMSE initially but a point is reached where the addition of more taps will cause the EMSE to start increasing. The tap whose addition does not reduce the MMSE any further and the tap whose addition causes the EMSE to start increasing are generally the same. If the equaliser is lengthened beyond this tap, the MSE increases and computations are wasted. One of our aims in this project has been to find a method to set the equaliser length at or near that critical number of taps. A novel filtering structure that splits an N-tap FIR filter into K segments of P taps/segment (N=KP) has been introduced. This structure allows us to monitor how successive segments contribute to the reduction in MSE at the output of the equaliser. An algorithm has been devised that controls the number of segments to be used at each instant depending on the channel conditions. This combination of segmented structure and supervisory algorithm is what we call a variable length linear equaliser (VL LE). The VL LE, in combination with LMS or RLS, has been tested in a wide range of different scenarios offering in all of them a very satisfactory performance. That is, the VL LE is able to estimate correctly the optimum number of segments (hence, taps) to be used in the equalisation according to the channel conditions.
As with the LE, a similar procedure has been followed with the DFE to assess its reconfiguration potential. First, the MSE expressions have been expanded to include the effects of the feedback filter, then the influence of the lengths of the FFF and FBF on the derived expressions have been analysed.
In the case of the DFE, some previous research had shown that the FFF, which is in charge of compensating the pre-cursor interference, can be kept fairly short. This is due to the fact that, normally, a mobile channel is composed of a few strong paths arriving first, being followed by a variable (potentially very large) number of weaker paths causing post-cursor interference. The FFF must take care of collecting most of the received energy in the strong paths while the FBF is in charge of cancelling the post-cursor interference. Given that the FFF is short, i.e. computationally inexpensive, our efforts have centred on the length adjustment of the FBF whose length can vary considerably depending on the specific environment in which is operating.
An algorithm has been presented to perform the FBF length adjustment. This algorithm works on a tap by tap basis and therefore does not require any special structure. The combination of the DFE with the algorithm controlling the length of the FBF is what we have called a variable length FBF DFE (VL FBF DFE).
The VL FBF DFE has also been tested on a wide variety of different situations and it has always adjusted the FBF length appropriately. Nevertheless, there is a situation where the proposed procedure might fail, the case of sparse channels. An additional strategy has been proposed in order to cope with this particular scenario.
As a side result, an interesting relation between decision delay and rate of convergence in the LMS-DFE has been found. A rule has been derived on how to chose the decision delay in order to minimise the convergence time of the LMS-DFE.

Further Work
There are quite a few ways to take the work presented in this thesis one step further. The four we believe are more interesting are explained next.

COMBINATION OF VARIABLE LENGTH LE/DFE WITH ITERATIVE DECODING
The first extension concerns the combination of the work presented in this thesis with modern channel decoding techniques such as turbo-decoding.
Turbo-codes can be decoded using iterative techniques, where at each iteration, a more reliable estimate is produced. In general, error control techniques perform well in uncorrelated channels, i.e. AWGN, whereas they are not adequate for linear distorting channels. Equalisers, on the other hand, work the other way round. They are effective in combating linear channel distortion but there is nothing they can do against AWGN. This complementary action of equalisation and decoding can be better exploited when both subsystems can be adjusted dynamically. This would be the case of a receiver combining the use of iterative turbo decoding (adjustable number of iterations) and the variable length equalisers presented (adjustable number of taps). In a system like this, a certain amount of computational power could be jointly assigned to the equalisation-decoding process. The specific amount of computation spent on each of the sub-processes would depend on the particular channel characteristics and would be able to change as channel conditions varies.
This method ensures that each type of channel is tackled with the most effective countermeasure.

DIVERSITY
The second area for further work is the application of the principles of variable length equalisation to systems with spatial diversity. Advances in antenna technology start to make feasible the implementation of more than one antenna on a mobile handset.
In principle, and assuming that each diversity branch is connected to an independent equaliser, the techniques presented in this thesis could be applied to each individual branch.
If the channel is subject to long fades, the different equalisers will have different lengths as all of them will see "different" channels (independently fading). Another interesting possibility to explore would be techniques that, given a fixed number of taps, distribute them optimally, and probably unevenly, among the different branches.

PERFORMANCE OF VARIABLE LENGTH STRUCTURES ON CDMA
A more straightforward and interesting task would be to test the variable length equaliser performance on a fully implemented CDMA environment. More specifically, it would be interesting to see how the variable length structure responds to variations in the number of users (interferers).

IMPLEMENTATION OF VARIABLE LENGTH EQUALISERS ON FPGA
The last area we propose for further work would cover the implementation aspects of variable length equalisers. In particular, the implementation of reconfigurable equalisers on reconfigurable logic devices such as FPGAs seems an attractive option worth considering in detail.