Two adaptive algorithms are commonly in use, the LMS and RLS Algorithms123 and these are described in Appendix I.

The least mean square (LMS) algorithm (and the closely related normalised least mean squares (NLMS) algorithm) is a stochastic gradient algorithm which has only one parameter, the step size y. The LMS algorithm is computationally simple but its convergence rate is slow and highly dependent on the properties of the input signal, more specifically on the eigenvalue ratio of the autocorrelation matrix. When many elements of the input signal are unknown, for example the channel in a mobile communications system, it is difficult to choose y. The algorithm is numerically <BR> <BR> <BR> stable, but an inappropriate choice of y can cause instability. In high noise conditions, the eigenvalue ratio of the autocorrelation matrix is low and this can help with convergence.

The recursive least squares (RLS) algorithm is computationally much more complex, but has much faster convergence than the LMS algorithm. It has two parameters, the forgetting factor X and the initial diagonal matrix term b. The forgetting factor is set appropriate to the rate of change of the autocorrelation of the input signal. The diagonal term has little effect on the algorithm once converged, but does affect the size of internal variables within the algorithm during initial convergence. The RLS algorithm is usually considered converged within a number of iterations equal to twice the filter length, which is generally much faster than the LMS algorithm. The RLS

algorithm can become numerically unstable when the autocorrelation matrix of the input signal is close to being a singular matrix.

There are a few much less common adaptive filter algorithms and the use of these algorithms has been found desirable. The fast a-posteriori error sequential technique (FAEST) 5, algorithm and its stabilised version the SFAEST7, which are also described in Appendix I, have a convergence rate close to the RLS algorithm but complexity close to the LMS algorithm. They do however impose an additional constraint: the input signal must have a shift invariant property. The shift invariant property simply means that the input signal must be the same as the input signal on the previous iteration shifted on by one sample, with only one new sample. This property is not satisfied by the conventional architecture for a minimum mean square error (MMSE) receiver for a DS-CDMA system8. The numerical stability of the FAEST algorithms is not as well understood as for LMS and RLS, but in practice the SFAEST algorithm seems to remain stable for a sufficiently long period of time for the purpose proposed here. The Fast Newton algorithm (see Appendix I) is an algorithm which can simplify the calculation of any of the above adaptive filter algorithms if the input signal can be modelled as an autoregressive filter with order less than is assumed by the above filters.

The conventional architecture for the uplink and downlink of a DS-CDMA system with an adaptive filter receiver is shown in Figure 1. In this architecture, the training of an adaptive FIR filter 1 of length N+P-1 chips (N being the number of chips per data bit and P the total number of chips in the code) is done at the bit rate, using an adaption error found by the algorithm to be the difference between data from a particular user and a sampled estimate of the data from the output of the filter 1, i. e. the filter has an effective training path ETP. The contents

of the filter 1 change completely from one iteration thereof to the next. This means that convergence is slow and it is not possible to use the FAEST or SFAEST algorithm because the shift invariance property is not satisfied. With the LMS algorithm, convergence is too slow and the time taken to reconverge when a user switches on or off is far too slow.

This architecture does work reasonably well with the RLS algorithm, although convergence is still not very rapid and the computational complexity is very high.

Summary of the Invention It is one aim of the present invention to provide a DS-CDMA receiver using an adaptive filter in which the convergence is rapid. It is another aim of the invention to allow the use of the less common adaptive algorithms which has not hitherto been possible.

The present invention provides a direct sequence code division multiple access (DS-CDMA) receiver comprising an adaptive filter controlled by an adaptive algorithm for filtering data which has been multiplied by a spreading code and filtered by a channel filter, the adaptive filter having a length appropriate to model the inverse of the channel filter, and a multiuser detector operating on the output of the adaptive filter.

The algorithm is preferably either trained using the spread-multiplied signal of a desired user only, or from a composite signal which is the sum of the spread-multiplied signals of more than one, for example all, transmitting users. This means that the adaptive filter will be trained by new information at the chip rate of the code.

In a particular embodiment of the invention the fixed multiuser detector is of the minimum mean squared error (MMSE) type, but it may alternatively be of the zero forcing (decorrelating), Volterra, Radial Basis function, cancellation, near optimum or other decoding types.

The algorithm can for example comprise the least mean squares (LMS) or recursive least squares (RLS) algorithm. However, because the adaptive filter of the invention satisfies the shift invariance property, the algorithm may alternatively comprise the fast a-posterion error sequential technique (FAEST) algorithm, the stabilised FAEST (SFAEST) algorithm, and the above algorithms or others may be used in combination with the Fast Newton algorithm.

Brief Description of the Drawings In order that the present invention may be more readily understood, reference will now be made, by way of example only, to the accompanying drawings, in which:- Figure 1 shows the conventional DS-CDMA architecture already discussed; Figure 2 shows DS-CDMA architecture according to an embodiment of the invention; Figures 3,4 and 5 are graphs of simulation results, showing respectively the comparative convergence of the architectures of Figures 1 and 2, the relative convergence rates of different algorithms using the architecture of Figure 2, and the bit error ratio (BER) results for the architecture of Figure 2; Figure 6 schematically shows a DS-CDMA system with no channel model; Figures 7 and 8 are graphs showing signal to noise performance of a Wiener filter calculated for 7 chip and 31 chip Gold codes respectively; Figures 9 and 10 are graphs showing bit error rate (BER) perfomance of the Wiener filter calculated for 7 chip and 31 chip Gold codes respectively;

Figure 11 is a graph showing convergence properties of the LMS and RLS adaptive filters; Figure 12 is a graph showing BER performance of the LMS and RMS algoritms after 1000 iterations allowed for convergence, compared with the Wiener optimal and a matched filter with no MAI; Figures 13 and 14 are graphs plotting BER against number of active users in an AWGN channel and a stationary multipath channel respectively, all users being equal power and the spreading code length being 7; Figure 15 schematically shows the construction of a received signal Y (n); Figures 16 a) to d) schematically show the structures of a matched filter, a parallel canceller using matched filters, a Wiener filter and a parallel canceller using Wiener filters respectively; Figure 17 is a graph showing the BER performance of the filters shown in Figures 16 a) to d); and Figures 18 a) to d) are graphs plotting simulated BER averaged over all users against number of users for four differnt signal to additive Gaussian noise ratios, with 60,000 data bits per user and a sequence length of 64.

Deatiled Description of the Preferred Embodiments Figure 2 shows DS-CDMA transmitter and receiver architecture comprising spreading means 2 respectively operated by each user in which a data signal from the user is multiplied by one of a set of spreading codes uniquely allocated to the respective user. The data is supplied to the spreading means at its bit rate and the code is input at its chip rate, there being N code chips for each data bit.

The spread-multiplied data is summed at 4 and filtered in a finite impulse response (FIR) channel filter 6 of length P chips, the output of which is transmitted, with incidental Gaussian noise, to a receiver comprising an adaptive FIR filter 8, also of length P chips.

An adaptive algorithm 10 controls and trains the adaptive filter 8. The algorithm 10 basically finds an error signal which is the difference between (a) either the spread-multiplied data from the desired user only or the composite spread-multiplied signal, and (b) the output of the adaptive filter 8. The choice of training data in (a) can either be preset or switchable. The effective training paths ETP for the adaptive filter, representing this operation of the algorithm are shown in Figure 2.

The adaptive filter 8 acts similarly to (but not exactly the same as) a conventional equaliser. As previously stated, training can be on the desired user's signal only, or on the composite chip rate signal. The filter 8 has less taps than the adaptive filter 1 in the conventional architecture and is trained at the chip rate, which means much faster convergence. The adaptive filter 8 also satisfies the shift invariance property required for the FAEST and SFAEST algorithm and this allows LMS complexity levels with RLS convergence rates. A fixed multiuser detector 14 is precalculated and stored at the receiver and is based on knowledge obtained about the number of users in the system and their spreading codes. This detector 14 can be of the MMSE type9 (used in the comparisons here) or it can be of a different type, for example zero forcing or decorrelating10 Voterra1l Radial Basis functionll. cancellation basedl3, 14 or near optimum decoding based on Viterbi decoding".

Summary of Multiuser Detection Techniques The conventional single user detector or spreading

code matched filter calculates the correlation between the received signal and the spreading code (or the spreading code convolved with the channel impulse response in a multipath channel) over the data bit period. The multiple access interference (MAI) impacts the ability to recover the desired transmissions with this receiver and is more pronounced for high power interfering users.

The matched filter is the optimum detector in AWGN but the MAI cross-correlation terms are not Gaussian unless there are many active users. In this situation the optimal detector is not the conventional matched filter but rather a form of multi-user detector.

The detector that yields the most likely transmitted sequence maximizes the probability that it was transmitted.

When all possible transmitted sequences are equally probable, this is the maximum likelihood sequence estimator (MLSE). When implemented with a Viterbi algorithm the complexity is exponential in the number of users. The MLSE must also estimate the received amplitudes and phases but it lowers the mobile user transmitter power control accuracy requirement. Despite the performance and capacity gains over conventional detection, the MLSE is not a practical solution.

Here the zero forcing or decorrelating detector implements an inverse of the received signal autocorrelation matrix (neglecting the noise) such that the output is completely free of multiple access interference. The decorrelating detector was initially proposed in the late 1970s and it provides substantial performance/capacity gains over the conventional detector and does not need to know in advance the received signal amplitudes, avoiding sensitivity to estimation error. It has computational complexity significantly lower than MLSE. Another desirable feature is that it corresponds to the MLSE when the user energies are unknown. A disadvantage of this detector is that it causes

noise enhancement i. e. the power associated with the noise term at the output of the decorrelating detector is always greater or equal to the noise term at the output of the conventional detector. A more significant disadvantage of the decorrelating detector is that the computations needed to invert the matrix are considerable.

A possibly superior linear receiver structure is to build an adaptive filter that minimises (at its output) the error power. This implements a partial or modified inverse of the autocorrelation matrix, dependent on the level of background noise, to balance the desire to decouple the users for MAI reduction while not enhancing the background noise. Again this receiver structure implements a matrix inversion operation and here we can apply the recursive adaptive filter techniques. This detector differs from the decorrelating detector in that it takes the noise terms into account to minimise the noise enhancement. Thus if noise is low the minimum mean squared error (MMSE) receiver approaches the decorrelating detector and achieves close to optimum performance. On the other hand, if the multiple access interference is small compared to the noise, then the matched filter detector solution is approached. This is exactly analogous to the MMSE linear equalizer used to combat inter-symbol interference. Unlike the decorrelating detector, it requires estimation of the received amplitudes but its complexity is independent of number of active users and explicit knowledge of the CDMA spreading sequences is not required for an adaptive implementation.

Other researchers have investigated radial basis function (which in its complete implementation is similar to MLSE, various simplifications have been suggested) and Volterra nonlinear approaches (where the received signal is passed through a power series nonlinear expansion before applying a linear filter eg. decorrelating or MMSE). Note that if a MMSE error type fixed multiuser detector is used, the overall impulse response of the adaptive filter followed

by the fixed detector is not exactly the same as for the conventional architecture even when both systems are fully converged. This will give different bit error ratio (BER) results even when both the adaptive filters in the two receivers are fully converged. Note also that the adaptive filter 8 has an extremely low signal to noise ratio at its output as the processing gain has not been applied at this stage. This leads to a low eigenvalue spread which can help the convergence and stability of some adaptive algorithms but others exhibit instability in the extremely high noise conditions Possible multiuser detectors are discussed in more detail in Appendix II.

The output from the detector 14 is down-sampled to the bit rate at the synchronous points to give the required estimate of the user's data signal.

Simulation Results All simulation results presented below are for 16 chip spreading codes (i. e. P=16) and a six tap stationary channel. Firstly we show that the new architecture has far faster or convergence than the conventional one. Figure 3 shows convergence curves for the conventional architecture of Figure 1 and the new architecture of Figure 2. The new architecture is much faster than the conventional one, mostly because it is trained at the chip rate instead of the bit rate but also because the eigenvalue ratio of the autocorrelation is reduced in high noise.

The graph of Figure 3 shows ensemble averaged squared error at the output of the adaptive filter in both architectures plotted against time measured in chips, for the single user case. Both curves use the LMS algorithm with the value of y individually optimised for each. The use of chip rate training instead of bit rate training,

increases the convergence by a factor of 16, but in fact the convergence is more than 16 times faster because high noise reduces the eigenvalue ratio in the autocorrelation. The new algorithm converges to a MMSE 16 times higher than the conventional architecture, but this loss will be largely regained through the fixed multiuser detector.

Figure 4 shows the relative convergence rates of some different adaptive filter algorithms using the architecture of Figure 2. The use of the SFAEST algorithm is only possible in the new architecture, as the conventional one does not satisfy the shift invariance property.

Relatively speaking, the LMS algorithm is very slow. <BR> <BR> <BR> <P>It can be made faster by increasing the value of y but when this value is increased too far, the LMS algorithm does not converge to the MMSE error floor (misadjustment error). The RLS is fast, but at the price of high computational com- plexity. The SFAEST algorithm is as quick as the RLS algorithm if it is initialised appropriately.

Figure 5 shows BER results for the new architecture after allowing 160 chips (only 10 databits) for convergence of the adaptive filter.

With only 160 databits for convergence, the LMS algorithm is not fully converged when the training period ends and this results in a slightly poorer performance than is obtainable with the conventional architecture. The RLS and SFAEST give similar results.

The architecture of the receiver of the invention is much faster converging and tracking than the conventional architecture with only a small loss in BER performance for a stationary channel. In a time varying channel, average BER will be better for the new architecture because of reduced tracking errors. The fast adaptive algorithms (FAEST, SFAEST, preferably in combination with Fast Newton)

allow the new architecture to achieve good convergence without the computational complexity of the RLS algorithm.

The receiver of the invention could be integrated in a"hard-wired"form or could be made capable of being updated by using reconfigurable or replaceable firmware.

APPENDIX I Summaries of Adaptive Algorithms Least mean square algorithm From the stochastic gradient approach [1] one obtains the well known least mean squares (LMS) algorithm which was first introduced in 1960 by Widrow and Hoff [2]. This algorithm is uncomplicated and yields acceptable performance in most cases. The LMS technique is probably the most frequently used adaptive algorithm in current communication system. It is derived by applying the method of steepest descent minimisation to the Wiener-Hopf equations which define the optimum Wiener filter and one obtains a simple recursive scheme of the form [3] {old}#{learning}{new}{new}= (1) tapweightsrateinformation}{apweights where the new information consists of the product of the filter input vector and the error signal, i. e. the difference between the desired filter output and the actual output of the filter. Essentially one can express the LMS algorithm (and many other adaptive algorithms) by means of three expressions [1]: <BR> <BR> <BR> Filter output: y =w(x()(2)<BR> <BR> <BR> <BR> <BR> Adaption error: e (t) = d (t)-y (t) (3<BR> <BR> <BR> <BR> <BR> Tap weight update: w (-l) = w (t) uxlt) (4) where x is the filter input vector, WT the transposed tap <BR> <BR> <BR> weight vector, d represents the desired filter output and y is the learning rate (step size parameter).

Several modifications have been made to improve the LMS algorithm, the most important one resulted in the normalised LMS (NLMS [4]) which normalises the adaption error e using instantaneous estimates of the input vector power ||x||2. Doing so largely improves the algorithm's stability characteristics and allows faster convergence. The LMS algorithm is computationally simple but its convergence

Appendix I rate is slow and highly dependent on the properties of the input signal, more specifically on the eigenvalue ratio of the autocorrelation matrix. When many elements of the input signal are unknown, for example the channel in a mobile communications system, it is difficult to choose. The algorithm is numerically stable, but an inappropriate choice of ß can cause instability. In high noise conditions, the eigenvalue ratio of the autocorrelation matrix is low and this can help with convergence. Other versions of the LMS such as leaky, signed and quantised LMS [3] were developed but only the NLMS achieved sufficient stability at acceptable performance and is therefore considered as a candidate for application in advanced multiuser detection.

To illustrate the improved performance of the normalised LMS as compared to the standard LMS we will present the performance of both the LMS and NLMS later in this document report.

Recursive least square algorithm The most popular least-square (LS) technique is is probably the recursive least squares (RLS) algorithm. The RLS algorithm is computationally much more complex, but has much faster convergence than the LMS algorithm. It has two parameters, the forgetting factor X and the initialisation factor 6 for the diagonal matrix P (0), see Equations below.

The forgetting factor is set appropriate to the rate of change of the autocorrelation of the input signal. The diagonal term has little effect on the algorithm once converged, but does effect the size of internal variables within the algorithm during initial convergence. The RLS algorithm is usually considered converged within a number of iterations equal to twice the filter length, which is generally much faster than the LMS algorithm. The RLS algorithm can become numerically unstable when the autocorrelation matrix of the input signal is close to being a singular matrix.

Appendix I We can summarise the standard RLS algorithm as follows [1]: INITIALISATION P (p) b-lI w (0) = 0 SUBSEQUENT ITERATIONS P(i-l)x(t)<BR> <BR> °"A-x(i)P-l)x(:)" e(t) = d(t) - wNT(t-1)xN(t) (6) w(=w(f-l)-g(;)e(:)(-) P(t)= 1/# (P(t-1) - g(t)xT(t)P(t-1)) (8) The vector g (t) is known as the gain vector of the algorithm, P (t) represents the inverse of the correlation matrix which can be computed in a recursive manner by means of the matrix inversion lemma. The variable e denotes the a-priori error of the filter estimation and the filter weights are again represented by the vector w.

Fast a-posteriori error sequential technique (FAEST) The fast a-posteriori error sequential technique (FAEST) has first been reported by Carayannis et. al [5] in the context of least-square (LS) filtering. Compared to standard LS algorithms the FAEST uses a different approach for calculating the Kalman gain vector based on the a-posteriori error formulation rather than the a-priori error formulation as used in fast Kalman algorithms [6].

Assuming the shift invariance property of the input signal and introducing a slightly modified version of the Kalman gain, the FAEST algorithm manages to perform a direct updating of the Kalman gain without invoking matrix-vector multiplications.

The Kalman gain update according to the FAEST algorithm is summarised in the Table 1.

Appendix I Table 1: The FAEST algorithm. I Tirne update of vain vector | ultipLIcatlons § D ! vlslons s , v a'v (t-1) xv (t-1) rtß , v \ J C, vltì (<) =A (<-l)-M. (t) 2- 7 I % u=ii) _','N (tl aG ! : (-I) ! 1 I 1 4^y, v (t) a., v (t (t) wv (t-1)-iv vu n r 1 (t) = O ~, a vttw a. v (t- avv eiN, V t) et'rt_, y<<t) z i_ I : Yt-et l. N=i e' (t)- v 1 : V v i-v,, t t) a°V (tzar (t-1) _-e v l). (t) ="W., V--i (I 0. 1 bN (tj=bv (t_1_uWVj v j- ) Toai number of muitip'ucanons a. nd divisions j 5-Y-11 j 5

It is well known that the FAEST algorithm suffers from sever stability problems and we will therefore not describe this algorithm in more detail but focus on its stabilised version, the SFAEST. For more information about FAEST please refer to [5].

Stabilised FAEST The stabilised version of the FAEST algorithm has been derived by [7] and is presented in Table 3. For easier reading of the equations building the stabilised FAEST (SFAEST) algorithm, we will first list all variables occurring and explain their meaning with a few words, see Table 2.

Appendix I Table 2: Variable definitions of the SFAEST algorithm. Variable Name l-Definition x (t) Filter input at time t y (t) Filter output, y (t) = 0 # t < 0 x, v (i) Input vector [z (t) x (t-N + 1) KalmangainvectorgN(t)Dual a, v (t) Forward predictor coefficients predictorcoefficientsbN(t)Backward hiv (t) Filter coefficients filtererroreN(t)A-priori A-posteriori filter error ers (t), ex (t) Forward predictor error and its corrected version e (t) e#N (t) Backward predictor error and its corrected version o Forward orediction error power #°N (t) Backward prediction error power γN+1(t)0#γN(t)#1γN(t), (t) #N(t),#N(t) Difference of errors and the corrected error difference exp. forgetting factor 0 < A < 1 Table 3 shows the successive steps of the SFAEST algorithm and also evaluates the complexity in terms of multiplications and divisions required.

Appendix I Table 3: Tasks of SFAEST in order of computations and number of required MUL/DIV operations Tasks of SFAEST DIV Available at time t: gN(taN(t-1),bN(t-1),xN(t-1)1), 1),αfN(t-1),αbN(t-1)γN(t- New Information: x(t),y(t) Computation of the residuals and corrections: A-priori forward/backward errors (residuals): 1) =x(t)-aN(t-1)TxN(t-1)N-(t) 2) ebN (t) = N)-bN(t-1)TxN(t)N-- Normalisation parameters: Normalisationparameters: αfN(t-1) =-γN(t-1)413)γN+1(t) #αfN(t-1)(efN(t))21)+γN(t efN(t) =1+γN+1(t)ebN(t)(gNN(t-1)+-aN(t-1)N)314)#N(t) γαfN+1(t) 1 -andγN(t)--15)γN(t)= #N(t)1-gTN(t)xN(t) -1)=#-NγN(t-1)aNN(t-1)2-6)kN(t Difference of errors: l l 7) ebN(t)+kN(t-1)efN(t)+#αbN(t-1)gNN(t-1)= Difference of errors of corrected filters 1+#(1-γN(t))+#k2y(T-1))411)(1-γN(t Corrected a-priori forward/backward errors: =efN(t)-(1-γN(t-1)kN(t-1)##N(t)3-9)#fN(t) 10) #αfN(t-1)+γN(t-1)(#fN(t))23-= 11) #bN(t) = ebN(t) -(1 γN(t))##N(t) - 12) #αbN(t-1)+γN(t)(#bN(t))23-= Time update of the dual Kalman gain gN(t): Extended Kalman gain vector: = =--N+1113)gN+1(t) 1)]#αfN(t-1)[-aN(t-1)][gN(t- Forwardfilter: =aN(t-1)-γN(t-1)(efN(t)+kN(t-1)##N(t))gN(t-1)N+4-14)aN(t) Dual Kalman gain: [gN(t)] [-bN(t 1)] gN+1(t)-gN+1N=1(t)N-15)= 0 1 Backward filter: 16) bN(t-1)-#N(t)(ebN(t)+##N(t))gN(t)N+3-= Time update of the filter hN (t): 18) eN(t) = y(t) - hTN(t)xN(t) N - 19) #N(t) 1-γN(t)eN(t) 20) h(t-1)-#N(t)gN(t)N-= Total number of multiplications and divisions: 8N + 36

Appendix I Initialisation, stabilisation and optimisation issues related to the SFAEST The value of the forgetting factor X largely depends on the rate by which the input signal changes and defines the memory length of the algorithm. The eigenvalue spread of the weighted input covalence matrix given by plays an important part in determining X. A suitable value could for example be X = 0.98 but the type of the input signal needs to be considered and it is most likely that changing between static and dynamic users and static and dynamic channels will require different values forX.

The choice for the variable p is not straight forward and no direct rule for calculating an appropriate value exists. In [7] it is mentioned that a initialisation can be done by means of an estimate such as This could however not be confirmed by simu-ations carried out in the course of this work. Usually a value of p = 1 has been chosen but an adaptive estimation of p during operation of the algorithm might prove advantageous. The most crucial parameters were found to be the forward/backward error powers. Initialisation has been done by means of the following rules: <BR> <BR> <BR> <BR> µ#N(11)αfN(0)= <BR> <BR> <BR> abv (0) (12)<BR> <BR> <BR> <BR> <BR> As can be seen both error powers depend on the value y and hence this parameter needs to be initialised with care. A <BR> <BR> <BR> typical, stable range for g was found to be between 10 < y < 100. From a stability point of view it is advantageous to <BR> <BR> <BR> monitor the evolution of the variable-y, (t). To prevent divergence of the algorithm, this variable should be restricted to values between 0 and 1. A recommended rule [7]

-Appendix I to assure convergence is to reinitialise the algorithm when the condition ( >M (13) becomes true, where v is a small constant. This precaution will also take care of the case where the gain tends towards zero, hence y-"0.

Fast Newton transversal filter The Fast Newton algorithm is an algorithm which can simplify the calculation of any of the above adaptive filter algorithms if the input signal can be modelled as an autoregressive filter with order less than is assumed by the above filters. Fast Newton transversal filters originate from the area of speech enhancement and echo cancellation.

Their main feature is a fast calculation of the gain vector as required in many LS adaptive algorithms.

The stabilised fast Newton transversal filter (SFNTF) is essentially a computational accelerator for any least square (LS) algorithm. Operating as a"higher-level" adaptive predictor it can use any LS algorithm as a subroutine within its own algorithm. However, the order of this LS filter can be chosen to be smaller than the actual filter order of the SFNTF algorithm. A sophisticated predictor part then extrapolates the remaining filter coefficients to gain the complete set of filter coefficients as required according to the definition of the SFNTF length.

It is this feature that should make the SFNTF a potentially attractive adaptive algorithm for many application and the usefulness of SFNTFs for advanced MUD receivers shall be examined in the future. As far as this report is concerned, we will however restrict ourselves to the description of the algorithm only.

To discuss the details of the SFNTF we will again list all variables as present in the algorithm with some words of Appendix I explanation about the meaning of the variables. Table 4 lists these definitions.

Table 4: Variable definitions of the SFNTF algorithm. DefinitionVariableName x (t) Filter input at time t y(t) y(t)=0#t<0output, vector[x(t),...,x(t-N+1]xN(t)Input g. v (t) | Dual Kalman gain vector of order V vectorstocomputegN(t)inversionqN(t),qN+1(t)temporary 2 and 3. sP+1,uP+1 temporary vectors to compute giv (t) a, v (t) Forward predictor coefficients bN (t) j Backward predictor coefficients h. v (t) i RN covariancematrixsample thatrNVector builds endoftabie.see filtererroreN(t)A-priori A-posteriori filter error ej, (t), eiv (t) | Forward predictor error and its corrected version# predictorerroranditscorrectedver-e°N(t),e°N(t)Backward sion a (t) Forward prediction error power aV (t) Backward prediction error powerr γN+1(t)0γN(t)#1γN(t), #N(t) (t) Difference of errors and the corrected error dif- ference factor0###1exp.forgetting

We can now describe the SFNTF with all its equations.

For easier reading of the following equations, we first define two new vectors s and u:

Comparing these definitions with Equation 4, we notice the similarity with the updating part Axe. WhileX represents the forgetting factor similar to µ, the second factor of Equations 14 and 15 are normalised error signals

Appendix I and the third factor, containing the vectors a and b, are similar to the input vector x of Equation 4. Note however that this is only a basic attempt to explain the nature of the vectors s and u and not a completely valid comparison- in particular with respect to the third factor. The vectors a and b represent the forward and backward predictor coefficients of the FNTF, respectively, and are computed by means of the sample covariance matrix Rp by and Their corresponding predictor error powers can then be defined as x0(t)-[x1(t)...xP(t)]aP(t)(18)αfP(t)= and c(t)=.=-P)-[)...(t-F-l)]bp(t)(19) As we notice from the definitions above, the SFNTF operates two separate predictor branches and by enabling or disabling those branches we can create three different versions of the algorithm: Version 1: Using forward and backward predictors (not recommended) Available values at time t: gN(t - 1) and γN,P(t - 1) From SFAEST algorithm: SP+i (t), ep (t), upTi (t°) and ep (t°

Appendix I Verson 2: Using only forward predictors Available at time t: qN(t gN(t-1)1), From SFAEST efP(t),sP+1(t0),efP(t0),gP(t0),γP(t0)SP+1(t), Version 3: Using only backward predictors Available at time t: qN(t - 1),gN(t - 1) From SFAEST algorithm: uP+1(t0),ebP(t0),gP(t0),γP(t0)ebP(t), Time update of the filter h, (t): Available at time t: hv (t-l), xxv (t-l) New information: x y (t) <BR> <BR> <BR> <BR> <BR> <BR> ev ()=!/M-h(<-l)v(t-1)(32)<BR> <BR> <BR> <BR> <BR> <BR> eiv(t)<BR> (33)#N(t)= <BR> <BR> γN,P(t)<BR> <BR> <BR> <BR> <BR> hN(t) = hN(t - 1) - #N(t)gN(t) (34) Predictor version 1 is more likely to diverge due to the fact that the calculation of γ is not realised as a finite sum. Versions 2 and 3 include only a finite sum of Appendix I

P + 1 values in the computation ofy.

As the algorithm of Table 5 is rather complex and difficult to overview, we also include Table 6 which displays the variable occurences in the different equations of Table 5 and states which variables are required for updating other variables.

1Note: The definitions of differ between FAEST and FNTF! Appendix I Table 5: Tasks of SFNTF with SFAEST in order of computation and number of required MUL/DIV operations SFNTE with DIVMUL Available at time t: 1),aP(t-1),bP(t-1),hN,t-1,xP(t-1),gP(t- 1),αfP(t-1),αbP(t-1)γP(t- New Information: x (t), y (t) Computation of the residuals and corrections: A-priori forward/backward errors (residuals) 1) efP(t) -aP(t-1)HxP(t-1)P-x(t) 2) ebP(t) -N)-bP(t-1)HxP(t)P-x(t Normalisation parameters #αfP(t-1) =γP(t-1)413)γP+1(t) 1)+γP(t-1)(efP(t))2#αfP(t- efP(t) =14)#P(t) -1)+aP(t-1)P)31γP+1(t)ebP(t)(gPP(t =andγP(t)=5)γP(t) #P -11-gHP(t)xP(t) 6) kP(t - 1) =#-P γP(t -1)1)aPP(t 2 - Difference of errors: ebP(t)+kP(t-1)efP(t)+#αbP(t-1)gPP(t-1)#P(t)= Difference of errors of corrected filters 4 Corrected a-priori forward/backward errors =efP(t)-(1-γP(t-1))kP(t-1)##P(t)3-9)#fP(5) 10) =#αfP(t-1)+γP(t-1)(#fP(t))23-(f) =ebP(t)-(1-γP(t))##P(t)2-11)#bP(t) =#αbP(t-1)+γP(t)(#bP(t))23-12)αbP(t) Time update of the dual Kalman gain gp (t): Extended Kalman gain vector: 0 1 13) gP+I,t = # - # P + 1 1 1)][gP(t- 1)[-aP(t-1)]- Forward filter: 14) aP(t-1)-γP(t-1)(efP(t)+kP(t-1)##P(t))gP(t-1)P+4-= Dual Kalman gain: -1)][gP(t)][-bP(t gP+1,t-gP+1P+1,tP-15)= 0 1 Backward fiiter: 16) bP(t-1)-γP(t)(ebP(t)+##P(t))gP(t)P+= Computation of dual Kalman gain for SFNTF: description17)see of Version and3)22) Time update of the SFAEST filter hp (t): (not required for SFNTF) 18a) ep (t) = y (t)-hpH (t) xp (t) P 19a) γP(t)eP(t)1-= 20a) hp (t) = hp (t - 1) - #P(t)gP(t) P - Time update of the SFNTF filter hN,t: 18b) e, V (t) = y (t) - hHN,t-1xN,t-1 N - 19b) #N(t) = eN(t)/γN(t)1 - 20b) hN,t = hN. c-i"EN (t) gvt lV _ Total number of multiplications and divisions: 8P + 2N + 39 Equation in Variables as function of t / (t-1) Table 3 x(t) x(t-P) xP wP wP+1 aP bP eJP ebP αfP αbP γP γP+1 #P kP #P 1) # -/# -/# #/- 2) # #/- -/# #/- 3) #/- -/# -/# #/- 4) -/# -/# #/- #/- -/# #/- #/- 5) #/- #/- #/- 6) -/# -/# -/# 7) -/# #/- 0/- -/# -/# #/- 8)#/# -/# #/- 9) #/- -/# -/# 10) #/# -/# 11) #/- #/- 12) #/# #/- 13) -/# #/- -/# -/# 14) -/# #/# #/- -/# -/# 15) #/- #/- -/# 16) #/- #/# #/- #/- # of variables 1 1 1 1 1 1 1 1 1 1/2 1 2 1 1 1 1 required Legend: # = variabie being updated<BR> # = value of vriable required<BR> - = value not required<BR> */* = describes the time step t/t - 1 of variables.<BR> <P>Example: #/# for bP in Equation 16) denotes bP(t) will be updated and bP(t-1) is required.

APPENDIX II Multiuser detectors for CDMA THE MMSE RECEIVER Consider the direct sequence spread spectrum system shown in Fig. 6.

In it we have M (m = 1 to M) users, each transmitting a PN code of length N chips (n = 1 to N). We assume that all the users are both data bit and chip synchronous and that the data modulation Dm and the codes Cmn take the values ~1. The signal at the input to the receiver at chip n is therefore:- W (r) is the noise sample at chip n. Wiener filter theory [1], [15] states that the optimal set of weights for an FIR filter hoDt is given by:- <BR> <BR> <BR> <BR> <BR> hopt= I-<BR> (2) #yy is the autocorrelation matrix of the input signal and for a stationary input:- y(n)y(n-N)y2(n)y(n)y(n-1) y(n)y(n-N+1)y(n)y(n-1)y2(n) y(n)y(n-N+2)y(n)y(n-2)y(n)y(n-1) #yy= E # . # . . . y (n) y (n-N) y (n) y (n-N + 1) y (n) j where E [x] denotes the expected value of x. We are interested in the FIR filter when it contains no data transitions, ie when it only has one data bit from each user in it. Assuming that the data modulation on each code is independent, ie E (DaDb)=0, A#B by direct substitution of equation {1} into equation {3} or analogy with the spatial radar case [16], [17] it can be shown that #yy=Q#QT + {4} The matrix 0 has dimension NxM and has the codes as its columns, ie:-

C31.CM1C11C21 C32.CM2C12C22 C13 C23 C33 . CM3 C1N C2N C3N . CMN Appendix 1 : QT denotes the transpose of matrix Q. The matrix A has dimensions MxM and has Pm at position m along its leading iiagonal and is zero elsewhere. Pm is the power at the receiver of user m. For the rest of the section we shall assume Pm = 1 for all m, ie perfect power control with the power of each user normalised to 1. The crJ term term the noise term assuming the noise power is #2 and the noise is uncorrelated.

The vector 0, is given by:- y(n) y(n-1) y(n-2) #xy={5}]] y(n-N) x (n) is the desired response. We are only interested in the response when the FIR filter contains the chips from one data bit, ie when n = 0 and at that point the desired response is the data bit for the desired code. Assuming the desired code is m = 1 then x (n) = D1. Substituting this and equation {1} into equation {5} and assuming the the data symbols are uncorrelated yields:- Cil C12 C13 CRIN Thus the vector 0 is the desired code. From equations {1}, {3} and {6}, and under the assumptions that we have stated, the optimum mean squared error performance is only dependent on the code set chosen. The minimum mean squared error at the FIR filter output is given by:-

Appendix II min = M]-, 0 We can define the output signal to noise ratio for the filter as:- <BR> <BR> <BR> <BR> <BR> <BR> S P1<BR> # #(dB) = 10log10# #<BR> <BR> <BR> N out # Assuming that the channel bandwidth in Hz is equal to the chip rate in chips per second then we can use the energy per <BR> <BR> <BR> bit Eb divided by the noise power spectral density No as a processing gain independent measure of the signal to noise ratio at the input to our FIR filter. In our case:- Eb 1 = N0 N#² Figs. 7, 8, 9 and 10 show the theoretical and simulated performance of the Wiener filter calculated as above for a set of 7 and 31 chip Gold codes. Fig. 7 shows the theoretical and simulated performance of the 7 chip Gold codes in terms of the output signal to noise ratio from the Wiener filter. Fig. 7. shows that the performance of the optimal filter with 4 users is practically the same as the performance of a matched filter with no MAI. Looking at the data, at 10 dB output signal to noise ratio, the difference between the 4 user curve and the matched filter curve is around 0.3 dB. From Fig. 7, to have 7 users in a system with a processing gain of 7 we must have <BR> <BR> <BR> an increase of around 1.8 dB in Eb/No to achieve the same performance as a matched filter with no MAI. These figures are again measured with 10 dB as the required output signal to noise ratio.

Fig. 8 shows theoretical and simulated performance of the 31 chip Gold codes in terms of the output signal to noise ratio from the Wiener filter. With 16 users, we require around <BR> <BR> <BR> a 0.1 dB increase in Eb/No over the matched filter with no MAI. This is better than the 4 user, 7 chip case, partly because 4/7 is greater than 16/31. When there are 31 users in <BR> <BR> <BR> a 31 chip system, the required increase in Eb/No is 1 dB over the matched filter with no MAI. It would appear that the 31

Appendix II chip system enjoys some inherent advantage over the 7 chip system, probably due to the greater degree of statistical orthogonality between the 31 chip codes when compared with the 7 chip case. However, other factors such as the choice of the desired user or the choice of the code sets cannot be ruled out.

Figs. 9 and 10 show the simulated bit error rate (BER) performance of the 7 and 31 chip codes. These graphs show similar results to Figs. 7 and 8 in terms of the increase in <BR> <BR> <BR> Eb/No required to accommodate more users. A good approximation to Figs. 9 and 10 can be derived from Figs. 7 and 8 assuming that because of the central limit theorem the noise output from the Wiener filters is Gaussian.

Adaptive filter receivers In most cases the DS-CDMA channel is non-stationary and as we have already stated the MAI will vary with the birth and death of signals. Therefore the FIR filter used in our receiver has to be a time varying approximation to the Wiener filter calculated using an adaptive algorithm. We will consider the properties of the two most popular adaptive algorithms, least mean squares (LMS) and recursive least squares (RLS) [1]. We shall use the 7 chip Gold code case as our example, as the 31 chip case would involve considerable extra computation. Fig. 11 shows the convergence properties of the LMS algorithm with two different values of the adaption parameter y. The graphs show the feedback error ensemble <BR> <BR> <BR> summed over 100 independent trials. With y = 0.007 the algorithm converges to 20% of its initial value within <BR> <BR> <BR> approximately 20 data bits, but with y = 0.0007 convergence takes around 100 data bits. In a DS-CDMA cellular system, where the channel varies relatively quickly with respect to the data rate of a single user, this slow convergence will not be acceptable. Fig. 12 shows the BER performance of the LMS <BR> <BR> <BR> algorithm after convergence with the same values of F as for<BR> <BR> <BR> <BR> <BR> <BR> Fig. 11. It shows that the smaller value of y produces a good approximation to the Wiener filter, but the performance of the

Appendix II LMS algorithm with the larger value of y is around 2 dB worse in terms of the required signal to noise ratio for a bit error <BR> <BR> <BR> rate of 10-3. Thus it is difficult to find a value of y which will provide a fast enough convergence without introducing a large residual error into the performance of the filter, even for the 7 chip case. The convergence time will be greater if the codes are longer. If we consider a DS-CDMA cellular system with imperfect power control and a multipath channel, then the eigenvalue spread of the input signal will be increased. This will also have an adverse effect on the convergence time of the LMS algorithm. More evidence of this is contained in [18].

Thus the LMS algorithm is unsuitable for this application.

Also shown in Fig 11 is the convergence of an RLS algorithm <BR> <BR> <BR> with X = 1 and the diagonal elements of the autocorrelation matrix initially set to 0.001. This shows typical behaviour for an RLS algorithm, rapid convergence by 2N. The RLS curve in Fig. 12 shows that the RLS algorithm does not add any significant residual error to the Wiener filter solution. Thus the RLS algorithm is potentially more suited to a DSCDMA cellular system.

Discussion In this section we shall look at the assumptions made in the derivation of the filters and look at applying this type of receiver to a cellular system.

We have assumed that all the channels are data bit and chip synchronous. If the channels are not chip synchronous, provided the receiver samples the desired channel synchronously, any change is likely to be beneficial as the effective MAI will be reduced. If the channels are not data bit synchronous however, the effect is greatly dethmental.

With transitions of the interfering channels occurring in the middle of the desired channel data bits, each interfering channel requires two eigenvectors in the O matrix. Thus performance is reduced and the system breaks down when the number of users exceeds 0.5N instead of N for the data bit synchronous case. An interesting case is when the data bits

Appendix II are almost synchronous, for example as synchronous as the transmission delays in the system will allow. In this case, it may be possible to ensure that any transition occurs a small number of chips (compared with N) from the beginning or end of the desired user's data bit. In this case the detrimental effect may not be so great, although this hypothesis remains unproven. We have also assumed perfect power control. There is some evidence that this type of adaptive filter structure is tolerant to variations in the power of the received codes [19]. The last assumption we made is that the data bits are uncorrelated. Provided that the signals are independently generated, idle channels are suppressed and that care is taken over the content and timing of control information, this should be a reasonable assumption.

If we are to apply this receiver structure to a cellular DS-CDMA system we need to take into account the non-stationary multipath channel and the birth and death of users. To take into account the multipath channel, we can use the technique in [20], replacing the impulse response of the spreading process C. with B=, where B is the convolution of the impulse response of the channel with the impulse response of the spreading process and repeat the analysis. This paper already describes the theoretical optimal with multipath evaluated for all users of the system simultaneously. The non-stationary elements of the channel can be taken into account by blocks of training data with or without decision feedback in between. The birth and death of signals problem will be greatly alleviated if all users are constrained to switch on and off only immediately proceeding a training block. The convergence and tracking properties of the adaptive algorithm and speed at which the channel varies will determine the length and frequency of the training blocks. However, by employing the RLS algorithm (or the covariance form of the least squares algorithm on training blocks [1]), the ratio of training data to information carrying data can be kept reasonable.

Appendix II Some desirable properties of this receiver are that it does not require to know the desired or the interferers spreading codes, provided the training data is known and its adaptive nature will allow it to reduce the effect of strong interferers from neighbouring cells and local narrow band interference.

Conclusions We have shown that an FIR filter can be used to separate a desired signal from MAI in a DS-CDMA system with only a small degradation in Gaussian noise performance. These filters can be approximated by trained adaptive filters. These sub-optimal filters may make practical receivers for a DS-CDMA cellular system.

THE DECORRELATING RECEIVER The decorrelating detector is similar to the MMSE detector except that the noise term is not taken into account ie. the second term in equation {4} above is neglected in the formulae for 0.

RADIAL BASIS FUNCTION RECEIVERS Introduction: In many DS-CDMA communications systems there are three sources of distortion when the signal arrives at the receiver, structured multiple access interference (MAI) from other users in the system, Gaussian noise which can often be extended to include unstructured interference and time dispersion due to multipath propagation. The simplest DS-CDMA receiver structures are based on matched filters for a non-dispersive channel and RAKE receivers for multipath channels. The MAI performance of matched filter/RAKE receivers can be enhanced by applying cancellation at the expense of increased receiver complexity [12]. Many proposed receiver structures are based on linear equaliser structures. Examples include decorrelating receivers which are based on the zero-forcing equaliser and those based on the MMSE equaliser [21]. We shall compare the above receiver structures with the RBF receiver. This nonlinear receiver minimises the

Appendix II probability of error when deciding on a data bit. It has already been shown that an RBF equaliser has superior performance to a linear equaliser in multipath channels for conventional minimum bandwidth signalling [22] and that an RBF filter has superior performance to a MMSE filter in a non-dispersive CDMA system [23]. We shall show that the RBF based receivers have the ability to considerably increase the capacity of a DS-CDMA system when compared with other receiver structures.

AWGN channel system model : To enable us to compare the wide variety of receivers discussed above we shall first consider an additive white Gaussian noise channel. Our system will consist of U independent users each transmitting a DS-CDMA signal which is chip and bit synchronous and with all users transmitting equal power normalised to 1. The data bit transmitted by user u during bit time k will be denoted by <BR> <BR> <BR> D" (k) and the spreading code for user u by Cu<. We will use n to denote the chip number within the code which is an integer <BR> <BR> <BR> between 0 and (N-1) where N is the spreading sequence length (processing gain). The spreading codes used throughout are 7 chips long and randomly generated. Without loss of generality we can assume that the desired user is user 0. The channel <BR> <BR> <BR> <BR> model will be a simple additive white Gaussian noise (AWGN) model with the noise time series denoted by G (kN + i). Thus the chip rate signal arriving at the receiver, denoted Y (kN<BR> <BR> <BR> <BR> <BR> <BR> + i), will be:- at the point where data bit k chip i is received. In the AWGN case there is no need to consider i outside the range 0 : 5i<N as outside this time the signal will contain no useful information relating to data bit k.

AWGN channel receiver structures: We shall consider three main receiver structures, matched filtering, the MMSE receiver and the RBF receiver. In all cases we shall assume that the codes and the signal powers are known at the receiver. In the

Appendix II non-dispersive case the matched filter receiver is given by <BR> <BR> <BR> an N tap FIR filter whose co-efficients Hi are the spreading code for the desired receiver i.e.

HiMF=C0,i The MMSE receiver is also an N tap FIR filter, but the co-efficients of this filter are given (in vector form) by [24] :- MMSE j is the autocorrelation matrix of the cyclostationary input <BR> <BR> signal with dimensions NxN. is the cross correlation vector. The RBF receiver is a nonlinear filter whose estimate of the data output is given by:- where y (k) denotes the input vector consisting of the N chip<BR> spaced input samples at data bit time k and _ are the centres. The centres are the noise free input vectors for all possible input data bit combinations. There are therefore n = 2U centres. #.# denotes the length of the enclosed vector (Euclidean norm). zizis the standard deviation of the noise. w is the value of Do associated with centre c.. In our simulations we shall assume that the centres and weights are known at the receiver. For all three receiver cases we shall also consider supplementing the receiver with a single stage of parallel cancellation similar to [12].

AWGN channel simulation results : The receiver structures above were simulated using Monte-Carlo simulation. The graphs show the log,, of the BER averaged over all active users in the system plotted against the number of active users. Fig.

13 shows results for Eb/No = 9 dB. These figures show that the performance of matched filtering becomes poor as the MAI (the number of active users) increases. The number of active users which gives an acceptable BER for a matched filter receiver improves considerably with the addition of cancellation, as Appendix II

this filter is clearly interference limited. The MMSE receiver performs better than both the matched filter and the matched filter with cancellation. It too improves with the addition of cancellation, although the improvement is not as great as adding cancellation to a matched filter. The RBF receiver is considerably better than both the matched filter and the MMSE receiver, with or without cancellation. However, the RBF receiver is not improved by the addition of cancellation. This is because in this scenario the RBF is the maximum likelihood receiver and therefore cancellation cannot improve its performance.

Multipath channel system model: We shall now consider a stationary multipath channel model. The channel we shall consider has impulse response:- M (z) = 0.3482 + 0.8704z-1 + 0.3482z-2 All signals are assumed to pass through the same channel, as would be the case in the downlink of a mobile radio system. The received signal at the time data bit k, chip i is received by the direct path and therefore becomes:- Note that if i-x is negative then the Du (k) Cu,i-x is replaced by D. (k-1) Cu,N+i-x and if i or i-x is greater than N (if we extend the receiver filter length beyond N) then Du (k) Cu x is<BR> replaced by DU (k+1) (k+l) This is a direct illustration of ISI caused by the multipath channel.

Multipath channel receiver structures: We shall base all our new receiver structures on a new set of input signal samples y (kN+i) where the range of i is extended to 0i<N+2 to capture all the signal energy that originated from data bit k. This combined with the multipath channel will result in ISI from both the preceding and following data bit. The equivalent of the matched filter for a multipath channel is an FIR filter

Appendix II with N+2 taps where the taps are given by:- HRAKE=c0*M The * represents convolution and C0 and M represent the spreading code of user 0 and impulse response of the channel respectively. The MMSE receiver coefficients are given by the same equation as before, however, the elements of the <BR> <BR> <BR> ( (N+2) x (N+2)) autocorrelation matrix (t) and the (N+2) cross correlation vector must be calculated according to the derivation of the MMSE receiver taking into account the multipath. The RBF receiver equation is also essentially unchanged, except now the input and centre vectors are of length N+2 and the number of centres is now 23 as all possible combinations of the previous, current and next data bit must be considered. This number of centres increases rapidly with the number of active users U and the computational load will rapidly become impractical.

Multipath channel simulation results: Graphs for the BER performance of the receiver structures described in the <BR> <BR> <BR> previous section are shown in Fig. 14 for b/No = 9 dB. These graphs show similar trends to the nondispersive case. The RAKE receiver rapidly breaks down as the MAI interference increases because the interfering users are not taken account of at all in the RAKE receiver and are therefore treated as unstructured noise. The MMSE receiver does considerably better than the RAKE receiver. The RBF receiver performs better than either the RAKE receiver or the MMSE receiver. However, it does involve a considerable increase in computational complexity.

The RBF results are truncated at 5 users because the calculation of 6 users would require evaluating the Euclidean distance from 218 centres for every data bit sent.

Discussion and Conclusions: We have shown that an RBF receiver has greatly improved performance over the more conventional matched filter and MMSE based receiver structures. This performance increase is apparent in both AWGN and multipath channels. However the computational complexity

Appendix II and the number of variable parameters in a non-stationary environment presently make the RBF filter receiver impractical for mobile radio applications.

NEAR OPTIMUM RECEIVERS Near Optimum receivers use similar methods to the Radial Basis Function receiver, usually with simplifications to the Radial Basis Function by dropping the exponential term and simplifying the Euclidean difference expression. These receivers can be implemented at the chip level or the bit level (after preprocessing) and often involve the Viterbi forward programming algorithm to search for the optimum centre (path in the Viterbi algorithm).

CANCELLATION BASED RECEIVERS The optimal receiver for a direct sequence code division multiple access (DS-CDMA) system is the maximum likelihood sequence estimator [25] [14] which is effectively an RBF receiver with infinite memory. However, this receiver's complexity rises exponentially with the number of users and is therefore impractical. At the other end of the complexity scale, a matched filter is commonly used as the receiver in a DS-CDMA system. A matched filter is the optimal receiver only in additive white Gaussian noise (AWGN) and has very poor performance when the level of multiple access interference (MAI) from other users in the system is high.

Between these two extremes a range of sub-optimal receiver structures have been proposed. The majority of these can be split into two types. Cancellation structures are typically based on matched filtering followed by subtraction of the matched filter output from a delayed version of the input signal [12] [26] [27]. Equaliser structures use a linear or decision feedback FIR filter with the co-efficients optimised according to varying criterion such as minimum mean square error (MMSE) or zero-forcing [18] [20] [28]. A comprehensive review of this area and a reference list can be found in [21].

Appendix II In this section the performance of a Wiener filter receiver is compared with that of a simple parallel canceller.

The combination of the two techniques is also examined.

System description The system to be considered consists of U independent equal power users transmitting both data bit and chip synchronously as shown in Fig. 15. The data bit transmitted by user u at bit time k will be denoted by Da (k) and the spreading code for user u will be denoted by Cru. n denotes the chip within the code which is an integer between 0 and (N-1) and N is the spreading sequence length (processing gain). The spreading codes used as an example throughout this paper are 64 chips long and randomly generated. Orthogonal (Walsh) or semi-orthogonal (Gold) codes would give better performance, but would require longer simulation times to give meaningful BER results. In many communications systems the channel will destroy the orthogonality property of orthogonal codes anyway. Throughout this paper the chip and data values will be normalised to 1. Without loss of generality we can assume that the desired user is user 0. The channel under consideration will be a simple AWGN channel with the noise denoted by G (kN+n) having variance cr. Thus the chip rate signal arriving at the receiver, denoted Y (kN+n), will be:- Receiver structures and theoretical performance The four receiver structures shown in Fig. 16 will be examined, Receiver structure a) is the simple matched filter case. The receiver consists of an N tap FIR filter whose co-efficients hrl are a scaled version of the desired user's code, ie:- <BR> <BR> <BR> COn<BR> <BR> N The matched filter treats the MAI as noise and therefore, if the signal power of each user is one and the codes are random, the central limit theorem allows us to approximate the BER for

Appendix II this receiver as:- where erfc () is the complimentary error function.

Receiver structure b) is a simple parallel canceller using matched filters to despread each interfering signal and reconstruct a replica which is subtracted from an appropriately delayed input signal, cancelling much of the interference. The remaining signal is then despread using a matched filter to the desired user. The reconstruction of the signal assumes that the power of the signal is known exactly.

Therefore an interfering signal which is is received with the correct sign will be cancelled exactly and an interfering signal received incorrectly will have its amplitude doubled (power quadrupled). A lower bound on the BER for this structure is given by:- This equation is only a lower bound for two reasons. Firstly the noise samples for each matched filter in the cancellation stage are the same, whereas the above equation assumes they are independent samples. Secondly, after cancellation the combined interference plus noise distribution of the remaining signal is a poor approximation to Gaussian because it consists of the Gaussian noise and a limited number of enlarged interferering signals which will be a poor approximation to a Gaussian distribution.

Receiver structure c) is the Wiener, Levinson or MMSE producing filter [15] [1]. It is also an N tap FIR filter, but the co-efficients of this filter are given (in vector form) by [24]:- h=#yy-1#yx where Appendix II

The T superscript denotes a matrix transpose. is the autocorrelation matrix of the input signal with dimensions NxN, given by:- #2I#yy=QQT+ The matrix 0 has dimensions Nx U and has the codes as its columns, # is the NXN ldentlty matrix. b is the cross correlation vector:- C0.2#C0,N-1]T#yx=[C0.0,C0.1, The MMSE is given by:- MMSE=1-hT#yx and the BER performance (derivation A) is:- hr EERviener * : (h T TY ;') 2 (3) - (hyx) + (.,. 0) hyx-1. 0 + MMSE To obtain average BER performance, this equation must be averaged over all the users in the system to crive Receiver structure d) is a parallel canceller using Wiener filters for the initial estimate of the interferers data bits. By analogy with equation 2, a lower bound on the BER performance of this structure is given by:- N BER= erfc < (J2+ BERwiener (4 0) (U Results All simulated results in this section are for 60,000 data bits, with the BER averaged over all users. Graphs show the average BER for all users in the system plotted against number of users. The sequence length is 64. The signal to Gaussian noise ratio is exoressed as:- N- Eb/No =<BR> 2#²<BR> <BR> <BR> <BR> <BR> Fig. 17 shows a comparison between the theoretical results derived in above and simulation results. The results show that equations (1) and (3) give good and unbiased

Appendix II estimates of the simulated results for the matched filter and Wiener filter respectively. The deviation of the simulated results for the matched filter from equation (1) with a low number of users is caused by the interference distribution only being approximately Gaussian and the limited number of simulated points. Equations (2) and (4) however only give an approximation to the actual performance of the two cancellation receivers. This estimate is biased towards a lower BER for reasons that were discussed above.

Fig. 18 shows simulated results for a range of signal to noise ratios. These results show that a matched filter is only a good receiver structure when Gaussian noise is the dominant source of interference. This only applies when there are very few interfering users and the signal to noise ratio is low.

A single stage of parallel cancellation based on matched filters performs better than a matched filter except at extremely high levels of interference, where the BER is too low for most communications systems anyway. The improvement <BR> <BR> <BR> is fairly significant, with Eb/N 9 dB, the cancellation receiver can support three times as many users as the matched filter if the required BER is 10-2.

The Wiener filter will always perform better than the matched filter. The only case where the performance of these two receiver systems is the same is when there is no MAI interference and the Wiener filter becomes a scaled version of the matched filter. The Wiener filter also performs significantly better than the matched filter based <BR> <BR> <BR> cancellation receiver. With Eb/No = 9 dB and a required BER of<BR> <BR> <BR> <BR> 10-2, the Wiener filter will allow approximately six times as many users as a matched filter and twice as many as the matched filter based cancellation receiver. The computational complexity of the Wiener filter receiver is identical to the matched filter receiver, and significantly less than the matched filter based cancellation receiver. This assumes that the Wiener co-efficients are calculated in advance.

Appendix II The Wiener filter based cancellation receiver gives the best performance of all. It will allow approximately seven <BR> <BR> <BR> times the number of users if Eb/No = 9 dB and the required BER<BR> <BR> <BR> <BR> is lu-', compared with the matched filter receiver.

Note that in all cases there is a significant variation in performance between users. For example, using the Wiener <BR> <BR> <BR> filter receiver with 48 users and Eb/No = 9 dB, the average BER is 0.00940 but the user with the best spreading sequence experiences a BER of 0.001167 and the user with the worst spreading sequence experiences a BER of 0.038092. This variation is due to the cross correlation properties of the code set and will also apply to an orthogonal code set which has lost its orthogonality due to a multipath channel.

Discussion and Conclusions In this paper we have shown that cancellation and Wiener filtering both perform much better in MAI than a simple DMF.

Wiener filters in particular offer a large increase in the number of users that can be accommodated. The two ideas can be successfully combined and provide a better performance than either on its own.

There is a cost to pay for improved performance. The cancellation receiver introduces a delay of one data bit and requires a substantial increase in either computation or hardware. Both the Wiener filter and the cancellation receiver require knowledge of the number and spreading sequences of the interfering users at the receiver, and the Wiener filter also requires a priori knowledge of the signal to noise ratio. If the signal to noise ratio is very high, calculation of the inverse of the autocorrelation matrix for the Wiener filter can be difficult as it becomes close to singular. In a computer network application the calculation of the Wiener filter in advance may be feasible, but in a mobile communications application the signal to noise ratio and the number of users varies rapidly with time. However, a good approximation to the Wiener filter can often be obtained using

Appendix II an adaptive algorithm.

Derivation A To calculate the BER for the Wiener filter we require to find a relationship between the MMSE and the variance at the output of the filter.

MMSE=E[(D0(k)-#)2]=E[D02(k)]-(2.0)E[D0(k)#]+E[#2] where E [] denotes the expected value and x denotes the filter output. Do (k) takes the values 1, therefore:- MMSE=1-(2.0hT#yx+E[#2][A.1] The variance of the filter output is given by:- <BR> <BR> <BR> var (#)=E[(#-#)2]=E[#2]-(2.0) E []-E [.]<BR> <BR> <BR> <BR> where x denotes E [x]. var (. =(hT#yx)2-(2.0)(hT#yx)2+E[#2] [A. 2] Subtracting [A. 1] from [A. 2] and rearranging gives:- var(#)=-(hT#yx)2+(2.0)hT#yx-1.0+MMSE Therefore, assuming the output of the Wiener filter has a Gaussian distribution, the BER is given by:- (D, _, 2 h) T BERWiener = e4) y') rfc = e rfc-T VOLTERRA RECEIVER The Volterra receiver is made up by a power series expansion of the received signal followed by a linear filter such as MMSE where the Volterra expanded signal v is used instead of the original received signal y. For a DS-CDMA system with received input signal y (kN+n), the output of the third order Volterra expansion is given by:- where the h co-efficients are estimated using a linear technique such as MMSE with the autocorrelation and crosscorrelation matrices replaced with the autocorrelation and crosscorrelation matrices of the power series expanded matrices.

References [1] S. Haykin, Adaptive Filter Theory. New Jersey: Prentice Hall, 3rd ed., 1996.

[2] B. Widrow and M. E. Hoff,"Adaptive switching circuits," IRE WESCON Conv. Rec., vol. 4, pp. 96-104,1960.

[3] N. Kalouptsidis and S. Theodoridis, Adaptive System Identification and Signal Processing Algorithms. New York: Prentice Hall, 1993.

[4] J. I. Nagumo and A. Noda,"A learning method for system identification,"IEEE Transactions on Automated Control, vol.

AC-12, pp. 282-287,1967.

[5] D. G. M. G. Carayannis and N. Kalouptsidis,"A Fast Sequential Algorithm for Least-Squares Filtering and Prediction,"IEEE Transactions on Communications, vol.

ASSP-31, pp. 1394-1402, November 1983.

[6] M. S. Grewal and A. P. Andrews, Kalman Filtering. New York: Prentice Hall, 1993.

[7] G. V. Moustakides,"Correcting the instability due to finite precision of the fast Kalman Identification Algorithms,"Signal Processing, Elsevier Science Publishers, vol. 18, pp. 33-42,1989.

[8] D. G. M. Cruickshank,"Suppression of Multiple Access Interference in a DS-CDMA System using Wiener Filtering and Parallel Cancellation,"IEE Proceedings (Communications), 143, 4, pp. 226-230 (Aug 1996).

[9] T. Kawahara and T. Matsumoto,"Joint Decorrelating Multiuser Detection and Channel Estimation in Asynchronous CDMA Mobile Communications Channels,"IEEE Transactions on Vehicular Technology, 44,3, pp. 506-515 (August 1998).

[10] R. Tanner and D. G. M. Cruickshank,"Volterra Based Receivers for DS-CDMA,"8th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications PIMRC'97, 3, pp. 1166-1170, Helsinki (September 1997).

[11] R. Tanner and D. G. M. Cruickshank,"RBF Based Receivers for DS-CDMA with reduced complexity,"IEEE Fifth International Symposium on Spread Spectrum Techniques and Applications, ISSSTA'98,2, pp. 647-651, Sun City, South Africa (September 1998).

[12] R. S. Mowbray, R. D. Pringle, and P. M. Grant,"Increased CDMA System Capacity through Adapative Co-channel Interference Regeneration and Cancellation,"IEE Proceedings, 139, Part I, No. 5, pp. 515-524 (October 1992).

[13] I. W. Band and D. G. M. Cruickshank,"Improving the Capacity of DS-CDMA Systems Using Convolutional Coding and Interference Cancellation,"IEE Proceedings (Communications), 145,3, pp. 186-190 (June 1998).

[14] S. Verdu,"Minimum Probability of Error for Asynchronous Gaussian Multiple-Access Channels,"IEEE Transactions on Information Theory, 32, pp 85-96 (January 1986).

[15] P. M. Grant, C. F. N Cowan, J. H. Dripps, and B. Mulgrew, Analogue and digital signal processing & coding, Chartwell-Bratt, Bromley, Kent (1989). ISBN 0-86238-206-8.

[16] B. D. Van Veen and K. M. Buckley,"Beamforming: A Versatile approach to Spatial Filtering, Magazine, pp. 4-24 (April 1988).

[17] R. Monzingo and T. Miller, Introduction to Adaptive Arrays, Wiley and Sons, New York (1980).

[18] M. Abdulrahman, A. U. H. Sheikh, and D. D. Falconer,

"DFE Convergence for Interference Cancellation in Spread<BR> <BR> <BR> <BR> <BR> Spectrum Multiple Access Systems,"Vehicular Technology Conference fVTC;, pp. 807-810 (May 1993).

[19] P. N. Monogioudis, R. Tafazolli, and B. G. Evans, "Performance of adaptive nonlinear NEFAR CDMA receiver architecture,"Electronics Letters, 30,3 (February 1994).

[20] A. Klein and P. W. Baier,"Simultaneous Cancellation of Cross Interference and ISI in CDMA Mobile Radio <BR> <BR> <BR> <BR> Communications,"3rd IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), pp. 118-122 (October 1992).

[21] R. Kohno, P. B. Rapajic, and B. S. Vucetic,"An Overview of Adaptive Techniques for Interference Minimisation in CDMA <BR> <BR> <BR> Systems,"Wireless Personal Communications, 1,1, pp. 3-21 (1994). <BR> <BR> <BR> <BR> <BR> <BR> <BR> <P>[22] P. M. Grant and B. Mulgrew,"Nonlinear Adaptive Filters: Design and Application, of the 5th IFAC Symposium on Adaptive Systems in Control and Signal Processing, pp.

31-42 (June 1995). ISBN 963 311 344 X.

[23] U. Mitra and H. V. Poor,"Neural Network Techniques for Adaptive Multiuser Demodulation, Journal on Selected Areas in Communications, 12,9, pp. 1460-1470 (December 1994).

[24] D. G. M. Cruickshank,"Optimal and Adaptive FIR Filter <BR> <BR> <BR> Receivers for DS-CDMA,"Personal, Indoor and Mobile Radio Communications PIMRC'94, pp. 1339-1343 (September 1994).

[25] A. J. Viterbi,"Very Low Rate Convolutional Codes for Maximum Theoretical Performance of Spread Spectrum <BR> <BR> <BR> Multiple-Access Channels,"IEEE Journal on Selected Areas in Communications, 8,4, pp. 641-649 (May 1990).

[26] R. Kohno, H. Imai, M. Hatori, and S. Pasupathy,"An

Adaptive Canceller of Cochannel Interference for Spread-Spectrum Multiple-Access Communication Networks in a Power Line,"IEEE Journal on Selected Areas in Communications, 8,4, pp. 69 1-699 (May 1990).

[27] M. Ewerbring, B. Gudmundson, G. Larsson, and P. Teder, "CDMA with Interference Cancellation: A Technique for High Capacity Wireless Systems,"International Conference on<BR> Communications (ICC'93), 3, pp. 1901-1906 (May 1993).

[28] P. Jung, J. Blanz, M. Nasshan, and P. W. Baier, "Simulation of the Uplink of DS-CDMA Mobile Radio Systems with Coherent Receiver Antenna Diversity,"Wireless Personal Communications, 1,1, pp. 61-89 (1994).