This invention relates to wireless communication, and especially to physical layer equalization in wireless systems.

Modern wireless standards attempt to address a number of requirements, (i) The system should offer high data rate services. These are important to operators since the revenue per bit for data services is dropping due to competitive forces, which in turn requires the cost to deliver each bit to drop and the total number of bits that can be consumed to rise in order that operators can run a profitable service with opportunity for revenue growth. For most applications, a user has a better experience when using higher data rate services, so these are highly desirable which in turn affects the competitiveness of an operator.

(ii) The system should make efficient use of the available spectrum. Only the range of carrier frequencies from a few hundred megahertz up to a few gigahertz has good propagation characteristics, that is to say a good chance of transmitting and recovering data over hundreds of metres at reasonable power levels in reasonable sized equipment, so that operators must pay considerably for a bandwidth of several megahertz in this range.

(iii) The quality of connection should be maintained. In order to reduce the instances of dropped calls, lack of signal, poor data rates etc. the systems need to compensate for user mobility, for example in a vehicle, signal distortion in an urban environment (e.g. reflections off tall buildings) and patches of bad reception.

(iv) For most portable devices, battery consumption of wireless components is important.

Each generation of wireless standards and products aims to address these requirements better than previous generations. The technology that allows this to be possible is primarily the increasingly sophisticated signal processing techniques to meet (or attempt to meet) these requirements. The physical layer

(PHY) of the protocol stack subjects signals to many stages of mathematical processing prior to transmission, and even more on reception.

Whereas radio and antenna designs have changed little in the last 10 years, Moore's Law (the doubling of gate count on a silicon device approximately every

2 years) has allowed the digital part of a wireless physical layer to increase in complexity to a considerable extent. High speed Fourier Transforms and other operations that were not feasible in real time only a few years ago can now be created using only minimal cost of silicon.

The downside of this revolution is the cost of development of these increasingly complex PHYs - many tens or even hundreds of man years is typical for a new standard, which means that instead of approaching each new generation from first principles, developers borrow many techniques from previous generations. This can lead to sub-optimal designs from a performance perspective, although it facilitates rapid time to market.

A number of techniques are applicable to many wireless standards. One such technique is the use of multiple antennas to improve the probability of correct reception. For example most modern wireless standards support the option of receive diversity. The goal of receive diversity is to obtain uncorrelated noisy samples of the same signal at the receiver. Obtaining the samples is simple using multiple antennas. However, the uncorrelated condition is extremely difficult. The white noise seen is uncorrelated, but the channel seen at each antenna is generally correlated. The rule of thumb in designing these systems is to space the antennas apart by half the wavelength of the carrier. However, in derivation of this rule of thumb, the multiple paths the signal takes to get to the receiver are assumed to arrive at any direction at the receiver. That is to say, the angle of arrivals of each path is uniformly distributed from 0 to 360 degrees. This is impractical for most environments, with most of the energy arriving from a narrow direction. This breaks the desired uncorrelated nature of the channels observed per antenna and sometimes results in channels which do not differ significantly.

Transmit diversity is the idea of transmitting the signal from multiple antennas, to obtain similar gains to receive diversity. If the signal from each transmit antenna can be separated at the receiver, the transmit diversity can be viewed as introducing more samples of the same signal, which can increase the capacity of the system substantially. However, both of these techniques require careful system design and close examination of the assumption of uncorrelated channels.

All digital wireless systems use some form of forward error correction so that occasional bit errors can be corrected (instead of a whole burst being discarded). Of particular relevance is turbo coding which is used in third generation (3G), WiMAX, long term evolution (LTE) and other standards. Turbo encoding at transmit is straightforward - parity bits based on the most recent k data (systematic) bits are added to transmitted bit stream. Repeating the process but with interleaved data adds to the error correcting abilities of the code. Turbo decoding at the receive end is substantially more processor-intensive, but otherwise straightforward. A soft demapper prior to a Turbo decoder converts analogue-like symbol plus a measure of confidence in these symbols into likelihood ratios for the Turbo decoder. For orthogonal frequency division multiplexing (OFDM) referred to below, confidence values can be derived from the channel estimate: the greater the fading at a given frequency the less confidence there is in the equalised symbol. For single carrier systems confidence values per symbol are not computable. For example, in single carrier systems using minimum mean squared error (MMSE) frequency domain equalization described below, the fading at each frequency is corrected in such a way that the time domain signal now has the same confidence values for all symbols. However of relevance to the present invention is that any confidence values computed by additional time domain processing can be used in a beneficial way by the soft demapper and Turbo decoder combination. One system that is employed in standards like Wireless LAN (IEEE

802.1 1), WiMAX (IEEE 802.16), and multiband UWB (IEEE 802.15.3a) is orthogonal frequency division multiplexing (OFDM) in which symbols, s, are modulated into frequency bins, known as subcarriers, and a set of N subcarriers is then transformed to the time domain. Figure 1 shows an example of one frequency/time schedule used in an OFDM system. The signal is divided into a number of subcarriers of different frequencies and lasts for a defined time, for example for 10 ms. A number of different users may be assigned to different subcarriers and/or time slots in the frame, and one time slot, may be used for the scheduling 1 , for example for assigning time/frequency blocks to different users or, in the case of SC-FDMA, for pilots that may be inserted in order to ascertain the transmission characteristics of the channel. The subcarriers may be changed in order to suit the reception of the signal. For example, one or more subcarriers 2 may not be used if the reception is too poor due to fading or to multipath. The scheduling of the subcarriers and time slots will need to be changed periodically in order to adapt it to changing circumstances as the location of the receiver changes. This will depend on how quickly the circumstances change, but it may be as often as once for each time/frequency block (e.g. 10 ms).

At the receiver, the received time domain signal is transformed to the frequency domain. If the system is designed correctly (which is assumed to be the case), each frequency bin experiences flat fading. That is to say, the data in each bin is multiplied by a complex number, a, dependent on the channel transfer function. It can be shown that a represents the channel transfer function at the frequency in which the bin is located. In addition, additive white complex Gaussian noise is present in each bin, represented by n. The received signal for a given bin can therefore be written as

r = as +n

The channel estimation can be performed by the introduction of pilots, which are known values in pre-defined bins. Therefore, the fading in that bin can be calculated simply by comparing the received amplitude and phase of the pilots with the transmitted amplitude and phase. Correcting this fading is known as equalization, i.e. equalization is the restoring of the data waveform to its transmitted state by removing the effects of the channel transfer function. In the expression above for the received signal, a can easily be estimated by dividing r by s, which is known assuming this corresponds to a pilot.

The two most common forms of equalizers in OFDM are the zero forcing (ZF) and minimum mean square error (MMSE) equalizers. The ZF equalizer simply multiplies each received bin by the inverse of the estimated channel fading. That is, the equalized symbol estimate can be calculated to be

, 1 1 1 1

s _E0 =—r =—as -\— n = s -i— n

a a a a

It is clear form the above expression that this equalizer recovers the data symbol s perfectly if and only if n is zero, i.e. no noise is present. If there is noise, the noise power is amplified by I/or ² . This is known as noise amplification. Therefore, if the channel transfer contains nulls (very low a values), the noise power can be amplified significantly.

The MMSE equalizer aims to combat the noise amplification present in ZF equalizers. Instead of multiplying each frequency bin by the inverse of the fading as in the ZF case, each bin is multiplied by

_*

a

aa + σ ^Δ

where σ ¹ is the noise power (variance of the Gaussian distribution which represents the noise process). This avoids severe noise amplification when a is small, but does not recover s perfectly as shown below.

Even though 5 is not recovered perfectly, in the average case, the equalized noise power is the minimum possible for a given channel noise power. This is how the equalizer was designed, to achieve the minimum mean square error at the output of equalization. MMSE is the most common equalizer for modern OFDM systems.

Figure 2 is a schematic view of a single carrier-frequency division multiple access wireless transmission scheme. In this system, the original time- domain signal s is converted to the frequency domain by means of a digital

Fourier transform 20 so that the signal is split into a number of subcarriers 22 after which pilots 24 from the frequency/time schedule 26 are inserted into the different frequency bins. The signal is then converted back to the time domain by means of an inverse Fourier transform 28 and a cyclic prefix is added at 29. The cyclic prefix is a repeated section of the end of the symbol added at the beginning.

The signal is then transmitted from the transmitter antenna 30 to the receiver antenna 32. After the cyclic prefix has been removed by the receiver at 33, the signal is again converted to the frequency domain by means of a Fourier transform device 34 so that the pilots can be extracted in order to determine the channel response, and sent to a frequency-domain equalizer 36 (e.g. MMSE), following which the signal is sent to an inverse Fourier transform device 38 to put it in the time domain. After the inverse Fourier transforming the signal, it can be processed. by means of decoders 40 etc in known manner.

In OFDM systems, one symbol is transmitted per frequency bin. Single carrier systems differ from this in that each and every bin contains an equal portion of each and every symbol. This can be viewed as spreading the data across every frequency bin. The main reason to do this is to reduce the peak to average power ratio (PAPR) of the time domain output at the transmitter. In

OFDM, the time domain signal is the sum of multiple frequencies (one for each bin) with different phases. These add together constructively and destructively in the time domain and can produce high peaks with the result that the PAPR may be in the order of 13dB, although this may differ for other systems. However, it is the average signal power that affects the probability of successful reception.

Systems that have a higher PAPR require the RF power amplifier to operate with sufficient 'headroom' to cope with the peaks. These power amplifiers therefore consume more energy which is clearly undesirable in mobile products due to the reduction in battery life, and is one of the reasons that OFDM-based Mobile

WiMAX (802.16e) is unappealing for small devices like cell phones.

However, for the single carrier case, the data is defined in the time domain and therefore tends to have significantly lower peak to average power, for example in the order of 4dB to 6dB depending on the constellation size of the system, which means that the power amplifier can operate at a lower level. In addition, unlike early single carrier systems, the received symbols can still be equalized in the frequency domain (as with OFDM).

The most common technique for equalization of these systems is MMSE, as described above for the OFDM case. In fact, the process is exactly the same, except that the equalized data is transformed back to the time domain after equalization.

The difference between the receiver for OFDM and single carrier with frequency domain equalization systems is the despreading of the values in the frequency bins in the single carrier case. In OFDM, the equalized symbols have been corrected and fed to the error correcting decoding block. Each symbol contains noise which may vary in power from one frequency bin to the next, but is white. White noise is essential for correct decision making. In simple terms, it means that high noise samples may occur, but the surrounding noise samples are not related to this high peak and can be small. This is the basis for which soft decision error correcting codes work.

However, for single carrier systems, the noise in each frequency bin is combined. Hence, each symbol has noise of the same power (average of the power in every bin), but this is no longer white. The coloured noise profile is equivalent to the profile of the equalizer. This leads to significant problems in the decision making. This problem is shown graphically in figures 3a to 3f. Figure 3a is a typical channel response of an LTE vehicular model. As can be seen a null occurs at about 1 1.5 MHz where the transmitted amplitude is reduced by approximately 24dB. Figure 3b shows the channel response of figure 3a (solid line) together with the transfer function for a ZF equalizer (dashed line) which essentially mirrors the channel response of the channel with a peak of about 24dB at the frequency where the channel shows a null value so that the frequency response of the combined channel and equalizer is flat as shown in figure 3d (solid line). This clearly corresponds to a single sharp peak forming the impulse response in the time domain as shown in figure 3e, which is what is desired. An

MMSE equalizer, on the other hand, has a transfer function that is shown in figure 3c with the dashed line which generally mirrors the channel response of the channel, but with a peak at the 1 1.5MHz null of only about 12dB. This means that the combined channel and equalizer frequency response is as shown in figure 3d with the dashed line, and shows a dip of HdB at the 1 1.5MHz null The impulse response of the MMSE equalizer is shown in figure 3f The coloured nature of the noise means that if a high peak occurs, this affects surrounding samples So, instead of isolated peaks of noise which affect only one symbol and are therefore relatively easy to correct, significant bursts of noise may corrupt multiple consecutive bits. Interleaving combats this effect to some extent, but for large block codes, such as turbo coding, interleaving is impractical In addition, due to the non-perfect recovery of the transmitted data, inter symbol interference (ISI) occurs as can be seen by the two side lobes 1 and 2 on either side of the main peak in figure 3f

In addition, the fact that MMSE does not recover the frequency bin data perfectly, the channel is not fully equalized. Inter symbol interference (ISI) components exist, even after equalization

According to one aspect, the present invention provides a receiver for a single earner, frequency division multiple access wireless transmission scheme, which composes

(a) a frequency domain equalizer that introduces inter-symbol interference into the received signal (for example an MMSE equalizer),

(b) a transformation device for transforming the equalized signal from the equalizer to the time domain, and

(c) a plurality of decision feedback equalizers, each decision feedback equalizer composing a feedforward filter that is operable to receive the time domain signal output by the transformation device and to whiten noise in the signal, a decision device that is operable to determine output symbols from the output of the feedforward filter, and a feedback filter that is operable to receive previous symbol estimates from the decision device and to subtract them from the output of the feedforward filter to reduce inter-symbol interference; and

(d) a combiner for combining the outputs of the decision feedback equalizers; wherein different decision feedback equalizers are arranged to receive signals from the transformation device in different temporal orders and/or with different time delays in order to reduce error propagation from the decision feedback equalizers in the output of the receiver.

The invention also provides a method of operating such a receiver.

A decision feedback equalizer (DFE) is a nonlinear equalizer that uses previous detector decisions to eliminate the ISI on pulses that are currently being demodulated. If the values of the symbols previously detected are known, then

ISI contributed by those symbols can be cancelled at the output of the feedforward filter by subtracting past symbol values with appropriate weighting.

The use of decision feedback equalizers, however, has the problem of error propagation. That is to say, if an error is made in the decision process, this error is fed back and used for all subsequent decisions, which leads to significant error components in the subsequent decisions and will generally corrupt the system. According to the present invention, the DFE operates on a block of data and is applied to reordered data. In other words, the DFE is applied not only on the symbols in the order they are modulated, i.e. 1, 2, 3, N, but on a different ordering of the data. By doing this and combining the results it is possible to avoid error propagation. For example, if an incorrect decision occurs early in the DFE operation, the error propagates. If the index corresponding to that incorrect decision was processed at a later point, the error propagation will affect fewer subsequent symbols or might even not occur due to the previous correct decisions made. In general, error propagations occur with relatively low probability.

Therefore, by performing the DFE on multiple sets of differently ordered data, the probability that error propagation occurs in the majority of reorderings of the data is highly unlikely.

The receiver may include one or more interleavers located between the transformation device and the DFEs in order to reorder the data symbols that are operated on in the blocks of data. The interleavers may be arranged to reorder the data into any desired order. For example one block may be operated on by a DFE in one order, e.g. the order in which the symbols are received, while another block may be operated on in the reverse order. Alternatively, because the blocks are operated on cyclically, the interleavers may be arranged to cause the DFEs to operate on the blocks at different starting points in the blocks whether the DFEs operate on the blocks in forward or reverse order. However, while it is possible to arrange the interleavers so that the DFEs operate on the symbols in the blocks in any order, there will normally be no advantage in using a complicated order, and sufficiently good results may be obtained simply by one DFE operating on the symbols in the forward direction (in which case no interleaver need be present) and another DFE operating on the symbols in the reverse order.

Because the performance of a DFE is highly dependent on the availability of past decisions, it is possible for a DFE to assign a confidence level to any decision, which is dependent on the number of previous decisions that have been made. Thus, the DFE may start on the first symbol of a block with a very low confidence level, and the confidence level may rise with (but not necessarily in proportion to) the number of past decisions made. Thus, it is possible for the receiver to weight the proportion of its output from one DFE and correspondingly weight the proportion of its output from the other DFE(s) as it operates on symbols of a block.

Although the present invention has been referred to as a receiver, it will be appreciated that the device, whether it be a cellular telephone, base station or other equipment, will normally include a transmitter as well as a receiver.

One form of receiver according to the present invention will now be described by way of example with reference to the accompanying drawings, in which: Figure 1 shows schematically one example of a frequency/time matrix employed in a conventional OFDM wireless transmission allocating different users to different subcarriers and time slots;

Figure 2 is a schematic view of a single carrier-frequency division multiple access wireless transmission scheme;

Figure 3a shows part of the frequency response of a typical channel used for an OFDM transmission system;

Figure 3b is a transfer function of a ZF equalizer for the frequency response shown in figure 3a;

Figure 3c is a transfer function of an MMSE equalizer for the frequency response shown in figure 3a;

Figure 3d is the frequency response of a combined channel and equalizer for the case of both a ZF equalizer and an MMSE equalizer for the frequency response shown in figure 3a;

Figure 3e shows the impulse response of the ZF equalizer of frequency response shown in figure 3c;

Figure 3f shows the impulse response of the MMSE equalizer of frequency response shown in figure 3c;

Figure 4 is a schematic view of a receiver according to the invention; Figure 5 is a schematic view of part of the receiver of figure 4 indicating the signal at various points along the receiver;

Figure 6 shows the confidence levels for the outputs of a pair of decision feedback equalizers;

Figure 7 is a representation of the input to the Cholesky decomposition for calculating the filter coefficients of the decision feedback equalizers; and

Figure 8 shows the order of operation of the fast Cholesky factorization for the filter coefficients of the decision feedback equalizers. Referring to figure 4, a receiver for a single carrier, frequency division multiple access (SC-FDMA) wireless transmission system comprises a conventional digital Fourier transform device (not shown) that receives the transmitted signals that are in the time domain and transforms them into a series of subcarriers 50 in the frequency domain. The subcarriers are input into a frequency domain equalizer, in this case a MMSE equalizer, 52 which equalizes the different frequencies. In addition, the subcarriers are sent in parallel to a channel estimator 53 which extracts the pilots from the received signal and calculates the transfer function α for each of the frequency bins which is sent to the MMSE equalizer. The subcarriers 54 from the MMSE equalizer are then input into an inverse digital Fourier transform device 56 in order to regenerate the time domain signal.

The time domain signal is then fed into a number of DFEs 59 via a number of interleavers 58 which reorder the symbols in the blocks of data appropriately. Any reordering of the data symbols can be represented as the product of a permutation matrix Il times the original data vector d. Hence, the permutation matrices defined for the m ^th direction is Il _m . As shown, the data sent to the first DFE via an interleaver 68 having a permutation matrix FI). However, it is often the case that this data is not reordered but simply sent in the order received, so that the permutation matrix would simply be the unit matrix.

Each DFE 59 comprises a feedforward filter 60 that receives the time domain symbols appropriately reordered by the interleaver 58 and passes it to a decision device 62. The feedforward filter 60 may be implemented as a FIR filter having filter coefficients that may be the time domain inverse of the MMSE equalizer 52 and so whitens the noise at the input to the decision device (i.e. makes it additive white Gaussian noise (AWGN)) but may introduce additional inter-symbol interference. The output from the decision device 62 is then fed back to its input by means of feedback filter 66 and subtracted from the output of the feedforward filter 60. The significant inter symbol interference introduced needs to be cancelled and the feedback filter does this prior to the decision device making a decision. In other words, the feedback filter examines the previous symbol estimates, and from this calculates the inter symbol interference expected. The ISI from the output of the feedforward filter can then be removed prior to making a decision.

The DFEs employed herein are different from most conventional DFEs in that the output from the DFE is taken from the input to the decision device 62 (i.e. from the subtractor 64) which means that the output is a soft symbol estimate in which the value of an output symbol estimate may vary continuously with the input symbols over a range between two values. This is different from conventional

DFEs whose output is taken from the output of the decision device 62 and which generate hard symbol estimates in which the estimate has only one of a number of values.

The soft symbol estimates, prior to making a decision, are output from the DFEs and fed to deinteleavers 68 which reorder the signal into the order output by the inverse digital Fourier transform device 56 and pass it to a combiner 70 before being passed to an error correcting block 72 and then output.

The DFEs each operate on a block of data. Therefore, the filter coefficients should be allowed to vary depending on the current symbol to achieve optimum performance. Unfortunately, the general case of reordering by any pattern requires the calculation of new feedforward and feedback matrices, which each require a Cholesky factorization, as described below. The Cholesky factorization is performed by a Cholesky factorization calculator 74 which typically forms part of the channel estimator 53 (although may be separate if desired) and sends values of the filter coefficients to the feedforward filter 60 and the feedback filter 66 of each DFE.

The mathematics involved in the calculation is represented by matrices and vectors, where the goal is to estimate the vector d, which is the data vector. In the drawings and in the following explanation:

r is the received vector (in the frequency domain) α is the channel fading vector

n is the vector of noise samples with variance σ ²

H is a diagonal matrix with the vector α on the main diagonal

W is the DFT matrix, with W ^w representing the hermitian transpose (conjugate transpose) which is equivalent to the IDFT matrix.

d _est is the estimated data, which is the input to the decision device.

e is the error vector, i.e. the difference between the ISI cancelled signal and the transmitted data d^— d.

B is the upper triangular matrix with zero diagonal with each row defining the feedback filter coefficients for that symbol.

F is the upper triangular matrix with each row defining the feedforward filter coefficients for that symbol.

E _s is the energy per symbol.

G _MMSE represents the diagonal matrix with the equalizer coefficients. In matrix terms, this can be represented as E _S H ^H (σ ² I _N + HH ^H ) ^~ '

R _xy is the correlation between two vectors x and y, i.e. R _xy = E(Xy^] .

Figure 5 is a block diagram showing the same units as figure 4 but in which only one DFE is shown for the sake of clarity, and in which mathematical formulae are indicated for the signals passing through the devices.

The primary condition imposed on the system is that the noise into the decision device is white. The error at the input into the decision device (assuming correct past decisions, which represents the operating point of the system) can be written as

e = <L es,l - d

= FW"G _WyM5£ r - Bd - d

= FW ^w G _WW5£ r - (B + I _w )d The orthogonality principle states that the minimum error vector is orthogonal to and uncorrelated to the received vector. That is, the system can compensate for all error within the space spanned by the received vector. The resultant error is therefore out of the space spanned by the received vector. Therefore,

£{er"} = O _N

= FW"G _MMSE R _rr - (B ₊ I^)R-,

=> FW"G _MMS£ R _rr = (B + I _Λ )R _dr

But the received vector in the frequency domain can be written as

r = HWd +n

This is, the transmitted data, d, is passed through the Fourier transform block W, which is transmitted in the channel with frequency domain fading specified by H and with AWGN, n.

Therefore,

R _rr = HWR _dd W " H" +R _nn

R _dr = R _dd W " H " + R _dn

The noise and data are uncorrelated, so therefore the second term on the right hand side of the second equation (1) is zero. Also, R _d d is simply a diagonal matrix with constant entries on the diagonal corresponding to the energy per symbol, E _s . This means the expression for the received vector correlation can be written as

R _rr = ^HH " + R _nn

^~ *-* MMSE ^u s ⁿ

where the expression for G _MMSE has been used to simplify notation.

The expressions for the two correlations can be substituted into the orthogonality expression to examine the relationship between F and B. FW"G _MW5£ R _rr = (B + I _w )R _dr

™ ^H G _MMSE ^G _MM sεE _s n ^H = (B + 1 _N )(E _S W"H ^H )

F^W'Η") = (B + I.X^WH" )

F = B + I _Λ

As expected, the feedforward and feedback filters are identical, except for the diagonal, which comprises ones for the feedforward case and zeros for the feedback filter. Thus, it can be seen that for the DFE structure, the optimum frequency domain linear equalizer is the MMSE.

Substituting the relationship between feedforward and feedback into the expression for the error gives: e = FWG^r - (B ₊ IJd

= F(WG^r - d)

For white noise, R _ee must be a diagonal matrix. To force diagonality, it is necessary to calculate R _ee

R _ee = E{F(XV ^H G _MMSE r - d)(W"G _MMSE r - d)" F ^H }

= FTF" where the matrix T has been introduced for notational convenience and can be calculated to be

T = E ₃ I _N - E ₅ W" H ^H (E _S HH ^H + σ ² I _N )E _s Finally, using the Woodbury identity the matrix T can be written as:

T = (E;' + σ ^~2 W"H"HW) ^~ ' (2)

This gives the final expression for the noise correlation at the input to the decision device to be

R _ce = F(£;' + CT- ² W ⁷ V HW) ^{- 1} F" Again, white noise is desired at the input to the decision device, so this is a diagonal matrix. The feedforward matrix is also upper triangular. Hence, if the Cholesky factorization of T is taken as

U" ΛU = E ^~χ + σ ² W"H"HW where U is an upper triangular matrix with ones on the diagonal and Λ some diagonal matrix. Substituting into the expression for R _ee , and letting F=U,

R. = FU ^" -' ¹ ΛA ^" -' ¹ UU ^" ^"FF"

= UU ^-1 A ^-1 U-^U"

= A ^"1

The noise has now been forced to be white at the input to the decision device. The variance for each symbol at the input to the device is given by the inverse of the appropriate diagonal entry in Λ. These values can also be input to the error correcting process, e.g. a turbo decoder.

In summary, to obtain white noise of variance Λ ^"1 at the input to the decision device, the feedforward and feedback matrices are defined as

F - U

B = U -I ₇ , where U is calculated from

U"ΛU = E; ¹ + σ ^"2 W"H"HW It should be noted that despite the matrix formulation, the feedforward and feedback structures can be designed as finite impulse response (FIR) filters with varying tap coefficients, that is, FIR filters with N taps for systems without any optimisations.

The outputs of the DFEs are then sent to the combiner. Figure 6 shows the confidence levels of the outputs of a pair of DFEs in which the input data is ordered according to the invention so that the confidence in the output data sent to the turbo decoder is increased. Figure 6 shows the confidence of the outputs for

DFEs in which the first DFE (DFE 1) receives the symbols in the order in which they were output by the inverse discrete Fourier transform 56 while the second DFE (DFE 2) receives symbols of each block in time-reversed order so that, for DFE 2 the DFE starts to operate on (say) symbol No 100 and works down to the first symbol of the block.

At the start of the block, since there have been no previous symbols, the ISI contributed by previous symbols cannot be cancelled out by the feedback filter and so the confidence in the output is small or zero. "Confidence" as used here is the amount of ISI that has been cancelled out by correct past decisions of the DFE. Thus, for DFE 1, as time passes and the number of symbols that have been decoded increases, the amount of uncancelled ISI decreases (curve a) and the confidence in the output (curve b) increases until it reaches its maximum at the end of the block. Similarly, for DFE 2, where the order in which the symbols are operated on by the DFE has been reversed, the confidence in the output (curve b) increases as the number of symbols operated on increases which means that the confidence is high for the first symbol in the block and decreases toward the end of the block.

Also shown for DFE 2 is an error c that has occurred in the processing, for example due to noise. Since the DFE depends on previously detected values, this error will be propagated, and curve d shows the effect of an incorrect value that decays with time.

The outputs of both the DFEs are combined by the combiner 70. As the confidence in correct detection of the symbol increases with the symbol number in DFE 1 but decreases with symbol number in DFE 2, the contribution due to each DFE in the output may be weighted so that, in this case, the contribution due to DFE 1 increases with symbol number and that of DFE 2 decreases.

Various different techniques for combining the data are possible, but maximal ratio combining is used here, but this should not rule out the application of other combining techniques. Maximal ratio combining (MRC) is the optimum linear diversity combining technique for signals of the form r_ = h d + n _n where m denotes the m ^xh diversity branch, h _m the flat fading present on that branch, d the data symbol and n _m the Gaussian noise. The MRC combiner output is given as

m

The output for the k ^th symbol of a block for the m ^lh DFE branch can be written as lk m

rk » = ^d k +

λk.m where rtk, _m represents the white noise component of unit variance and λ^ _m the k ^th element of the matrix Λ for the rn ordering. This is somewhat different from the standard expression for MRC whose data is scaled with unit variance noise compared to unit variance data with scaled noise. However, the problem can be reformulated to scale the data relative to the noise variance. That is

The MRC combiner output can therefore be shown to be

where the fact that λ _{k m} is real has been used. This estimate is then sent to the constellation demapping function which calculates Log-Likelihood Ratios (LLRs) for the error decoding. The noise variance is still not constant for each symbol so the error decoding processing favours some bits more strongly than others. Again, this is extremely useful for the turbo decoder. The noise variance (inverse of the confidence level) for the k ^lh symbol estimate can be shown to be

A full Cholesky factorization is computationally intensive. We therefore wish to minimise the number of factorisations required for the set of reorderings.

In order to reduce the number of computations required, a permutation matrix for the interleavers is proposed which allows the re-use of the results of a

Cholesky factorization. The two directional DFE with data ordering of 1, 2, 3, TV and N, /V-I, N-2, , 1 corresponds to setting the first permutation matrix to the identity matrix and the second permutation matrix to the anti-diagonal matrix J _N , which is a matrix with ones on the anti-diagonal (diagonal running from top right corner to bottom left corner. That is II, = I _N and U ₂ = J^ . The first reordering results in the Cholesky factorization

UfA ₁ U ₁ = £; ¹ + σ ^"2 πfW ^// H ^w HWπ,

= E —,/ + σ --U ^ι rH _N πVfrH"iΕLτ H ^H iWNl _N

The second reordering requires the Cholesky factorization of

UfA ₂ U ₂ = £;' + σ ^~2 j£W"H"HWJ _w By noting that J " W " WJ _N = I _N and that J^ = J^ , the equation can be rewritten as:

UfA ^l ₇ 2U" ₇ = r' + σ ^"! j!!W ^/f H"HWJ _J

= £;'J^W ^W WJ _Λ . + _σ - ² j£\V"H"HWJ _yv

= J^W ^// E;'l _Λ ,WJ _;V + σ- ² J^W ^w H ^w HWJ _Λ ,

= J _Λ , W" (£; ¹ I _Λ , + σ- ² H ^H H)WJ _Λ , where the terms within the brackets on the right hand side of the expression combine to a diagonal matrix. However, a circulant matrix can be diagonalised by the DFT matrix and vice versa. Hence, the term

W ^// (£;'l, + σ ^"3 H"H)W - UfA ₁ U, is a circulant matrix, which will be referred to below as C. The circulant matrix is a special case of Toeplitz matrix, which belongs to a class of matrices which are known as persymmetric and satisfy the condition A = JA ^r J . Therefore,

= UfΛfu;

This implies that

u ₂ =u;.

Thus, for the reordering which reverses the order in which the symbols are detected the complex conjugate of the ordering of the non-reversed case can be used. Accordingly, only one Cholesky factorization is required for these two orderings. Further orderings can be derived that can re-use Cholesky factorizations. However, although the gains seen from doing more than two orderings are present, they are of lesser significance than those seen from just two orderings and the additional computations needed for additional DFE branches.

Typically, a Cholesky factorization requires in the order of TV ³ multiplications. That is, the number of multiplications required to solve the expression is proportional to N ³ , where N is the number of subcarriers used, and therefore for high data rates, can be very large. In addition, if the channel changes, the factorization is required again. For mobile channels with the data rates of interest in LTE this computational burden is extremely large, even for base stations. For example a block of JV=I 2 symbols would require nearly 2000 multiplications per block. For the high data rates of interest, N can be considerably larger (for example 10.5 Mb s ^"1 which requires 100 subcarriers or more, or 30.44 Mb s ^"1 which requires 300 subcarriers or more), which results in an unfeasible computational load and prohibits the use of the DFE receiver for these data rates.

However, the computational burden of performing the Cholesky factorization may be reduced by means of a novel fast Cholesky factorization (FCF) employed according to the invention, in this case specifically designed for the problem of factorizing

W ^H (£;'!„ + σ ² H ^H H)W = UfA ₁ U ₁

As mentioned above, the matrix that is required to be factorized is a circulant matrix, which is a special form of Toeplitz. Toeplitz matrices have low displacement rank. Let the Toeplitz matrix to be factorized be represented by the C and let Z represent the lower shift matrix (ones on the first subdiagonal and zeros elsewhere). The displacement rank of a circulant matrix is 2, i.e. the rank of C - T ₁ CL" is 2. This means that the resulting matrix has a single column which contains more that one non-zero entry. All the other columns have a single nonzero entries in the first row. The function can therefore be written as:

with U ₁ = [Z ₀ t _x ^■■■ V ₁ ]/ V^ (4)

where t _n indicates the n ^th value of the first row of the matrix C. The square root at the end of the vector is only a normalising factor.

A'

We next assume let C = V ^H \3 = ^] ufu _A . , where u^ is the k ^th row of the

A = I

upper triangular matrix U. The displacement rank expression can therefore be written as

The last row vector u^ has a single non-zero entry in the last place. Thus, Zu" = v" = 0 . Subtracting uf'u, from both sides of the expression for the expanded displacement rank expression v" , V ₄₊₁

vf v,

where the identity Zu^ = v" = 0 has been used in the last line in order to get the summation ranges constant for all summations. This expression can therefore be evaluated for every k separately and gives what is known as the downdating problem

This downdating does not necessarily take into account the fact that the leading k entries of V _k are zero. In fact, it lacks the zero location properties that defines the triangular factorization. To force these properties, the hyperbolic rotation matrix Φ(p), may be introduced which may be set equal to

Φ(p) = ¹ - P

- p i

Note, that for any ^P≤ K,

which can be substituted into the downdating expression to obtain •*+i

which can finally be simplified to the solution

We now have an expression to obtain the k+l iteration vector pair from the k iteration vector pair. We also have control to force the zero locations (the reason the hyperbolic rotation matrix was introduced). That is, the parameter p is chosen such that the first column of

where γ is some complex scalar value.

The p which satisfies on the k ^th iteration can be calculated to be

This downdating rotation may, if desired, be improved for stability and minimising the number of multiplications required.

The order of multiplications per iteration is of the order of iV and there are N iterations. Hence, the order of multiplications for the algorithm has been reduced from N ³ to TV ² . Typically, for a case where there are 128 subcarriers (i.e. N= 128), this will correspond to a reduction from approximately two million multiplications to 16,000 multiplications.

This fast Cholesky factorization is applicable not only to receivers having a plurality of DFEs arranged according to the invention as described above, but is applicable to receivers having any arrangement of DFEs or having only a single DFE. Thus, according to another aspect, the invention provides a receiver for a single carrier frequency division multiple access wireless transmission scheme, which includes at least one decision feedback equalizer comprising a feedforward filter that is operable to receive a time domain signal, a decision device that is operable to determine output symbols from the output of the feedforward filter, and a feedback filter that is operable to receive previous symbol estimates from the decision device and to subtract them from the output of the feedforward filter to reduce inter-symbol interference;

the feedforward and feedback filters each having filter coefficients forming an upper triangular matrix U having rows uι _< , where the first row is given by:

in which /„ represents the nth value of the time domain residual defined as

W ⁷⁷ ^g(E ₅ -' + a- ² H"H), where N is the total number of values in the first row, and

the following rows have been generated by applying the formula: in which Z is the lower shift matrix, \ _k initialised as

V ₁ = [O I ₁ ^■■■ V, ] / ^ .,

and Φ(p) is a hyperbolic rotation matrix given by the equation

1 - p

Φ(Λ> =

- P 1 in which the value of p is given by p =— .

u _k (k)

Calculation of the feedforward and feedback filter coefficients for each single carrier symbol may be performed by the following algorithm as shown in figure 7. Again, the problem is to calculate

UfA ₁ U ₁ = W"(£;'l _Λ , + σ ^~2 H"H)W = C

The Fast Cholesky algorithm only operates on one column of the resulting matrix (due to the circulant structure). However, it was discovered that the resulting vector contains a large number of zeros around the central area of the column. This is due to the delay spread of the channel being much less than the length of the symbol (N).

By examining the downdating algorithm, p tends to zero for these values.

It can therefore be approximated that the hyperbolic rotation matrix tends to the

Identity matrix and the downdating in the central iterations corresponds to a down shift of the previous iterations vectors. Near the end of the vector, p begins to grow from zero and hence the downdating process involves rotations where

Φ(P)≠I _W .

An implementation parameter L which is typically significantly lower than

N, may be introduced which defines the number of iterations used to approximate the full Cholesky factorization. This involves removing values from the column vector used to initialise the downdating. That is, the downdating process is initialised with the vectors

^U l ⁼ Uo ^l ^{' " l} L!2-2 ^. ' 2-1 *N-L/2-l ^N-L/2 ^{' "} ^V-l J ' λ/'θ

V ₁ = [0 J, ^•■■ t _{L 2} _ ₂ t _{i n} _ _χ t _Λ r-i _{/ 2} - _l IN-L I I ' " ^ _V - _I - _T ΛT _O where t _n indicates the « ^th value of the first row of the matrix C, which can be calculated very quickly using an inverse fast Fourier transform (IFFT) on the diagonal of the matrix E ^~X \ _N + σ ^'2 H ^w H . Also, with an application specific IFFT algorithm, the calculation of the discarded values could be avoided. When the downdating process is complete, the resulting set of feedforward and feedback filter taps are indicated by the vector u _/ . The one to one relationship between symbol k and coefficient set / no longer exists, but can simply allocated using the mapping

£ = 1,2,3,. - ., £/2 => / =1,2,3,...,1/2

k = LI2,LI2 + \,...,N-LI2 - \,N -LI2 => I =LI l k = N- LI 2,N- LI2 + \,....,N => I =LI2,LI2 + 1,...,L

This parameter L can be defined by the user to remove redundant calculations and even to cut out non-zero values. In the case where the choice of L is picked too small to assume only zero values are discarded, the system still defines a feedforward and feedback filter pair which whitens the noise to some non-optimum point (whitens the noise somewhat, but not fully). This reduces the order of multiplications needed from N ² to L ² , which is a significant saving. A good compromise between the quality of the DFE and the number of computations required to generate the filter coefficients may be obtained by setting L to be not more than N/4. For example, the number of subcarriers TV will typically be about 128 as mentioned above and L may be in the region of 16 or 32, which will reduce the number of computations yet further from approximately 16,000 to about 256 or 1000 depending on the value of L. This also allows an implementation aware structure which can be adapted for any system, even battery operated mobile equipment in time varying environments.

The final FCF block diagram is given in Figure 8 which is conducted in the Cholesky factorization calculator 74 of figure 4. The input to the IFFT 80 is the first row of the N x N matrix T defined by equation 2, and the output is sent to block 81 where the middle values, from LIl to N-LIl are set to zero to give the values U| and V| from equations 3 to 5 above, and m is extracted and outputed.

The values of u and v are sent to blocks 82, 83 and 84 which perform the operation of equation 6 to generate the next value of u^ and vι _< , the last value of v being discarded . The above receiver structure can easily be extended to multiple antenna systems, i.e. systems with receive diversity.

In the description of the multi-directional DFE it was described how the output of the DFEs with different ordering can be combined. For the case of receive diversity, the number of DFE branches can be scaled by the number of receive antennas, and the branches all combined similarly to the single antenna case.

The extension of the algorithm to multiple transmit antennas is straightforward, with the reformulation of the problem dependent of the MIMO scheme used, e.g. space time coding, transmit diversity, etc.