Decision Feedback Filter Device in the Frequency Domain

1. Field of the Invention

The invention relates to a decision feedback device for the filtering of a digital signal, working in the frequency domain. The invention can be applied, for example to the cancellation of echoes generated by multipath propagation during the RF transmission of a digital signal in particular.

2. Description of the Related Art

A major problem in terrestrial transmission systems is that of signal distortion due to the phenomenon of multipath propagation. The reflection of a transmitted signal on dwellings, relief features or various layers of the atmosphere gives rise to the reception of several signals or echoes instead of only one signal. The undesirable echoes received are generally out of phase and time-lagged, and have amplitudes that are attenuated as compared with the origin signal (all in a manner that is variable in time, depending on the path followed). Since these phenomena depend, as far as their variation is concerned, chiefly on weather phenomena, they change slowly for a fixed reception system.

In digital transmission, the echoes received induce a distortion of the received symbols. This distortion results in a phenomenon of overlapping of the symbols, also called intersymbol interference. In order to ensure high quality reception, the resulting intersymbol interference must be eliminated or substantially reduced.

The pulse response of a multipath channel extends over a typical time interval of some tens of microseconds. This interval, which is a function of the frequency used, corresponds typically to a few hundreds of successive symbols in digital television broadcasting systems. One of the symbols received (see FIG. 2) corresponds to a symbol (x(n)) that is actually transmitted at the beginning, and the other symbols (x(n+i), x(n-j)) are parasitic symbols (or echoes) resulting from the multipath propagation. One processing approach involves the use of high-order digital filters, i.e. a large number of corrective coefficients, at reception, in order to eliminate the parasitic symbols (and produce, through a decision device, a sequence of decisions actually corresponding to the transmitted data).

The sampled pulse response of a multipath channel can be put in the following form:

with K as an index that is a integer ranging from 1 to p in considering p paths, .alpha..sub.k and t.sub.k being the effective gain and temporal delay respectively of the kth path, (t) being transmitted pulse. The gains are generally complex. The time delays t.sub.k are positive (echoes known as postcursor echoes) or negative (echoes known as precursor echoes). In practice the precursor echoes are temporally very close to the signal relating to the main path (typically at a temporal distance of less than 1 microsecond) whereas the postcursor echoes are fairly spread out temporally (being typically received with a time lag of 0 to 40 microseconds).

As we have seen, the phenomenon of multipath propagation changes over time, and it is therefore necessary to adapt the filtering coefficients temporally. Filters known as adaptive filters are used to this end. These adaptive filters, according to their principle, comprise a variable coefficient filter and a computation device providing these coefficients to the filter as a function, firstly, of the sequences of symbols received and produced by the filter, and, secondly, of the sequences of corresponding decisions. The coefficient adaptation devices are physically uncoupled for high sampling rates (for example rates of over one megahertz). The adapting of the coefficients is usually done in a digital signal processor or DSP, and the filter is normally made on a VLSI (Very Large Scale Integration) circuit. An approach of this type is described, for example, in the document EP-A-0 641 102. The temporal type processing is conventionally carried out therein symbol by symbol.

In terms of adaptation of coefficients, a known approach lies in the use of adaptation techniques known as techniques of adaptation on the basis of blocks of symbols: the coefficients are prepared out of blocks of symbols. Thus, a faster convergence is obtained than in the case of step-by-step algorithms. Fast linear filters are then used to carry out time domain filtering, symbol by symbol, or frequency domain filtering by blocks of symbols. A linear filtering of this kind, performed in the frequency domain, makes it possible, as compared time domain filtering, to reduce the number of computations through the replacement of a temporal convolution by a frequency multiplication. An approach of this kind, for example, is described in the article "On The Convergence Properties Of Partitioned Block Frequency Domain Adaptive Filter (PBFDAF)" in Torres L., Masgrau E., Lagunas M. A. (eds), Signal Processing V: Theories and Applications; Proceedings of EUSIPCO--90, Fifth European Signal Processing Conference, Barcelona, Sep. 18-21, 1990, Vol.1, Sep. 18, 1990, pages 201-204.

Nevertheless this filtering structure does not make it possible, with an accessible degree of complexity, to obtain sufficient correction in the case of the long echoes, in particular when the temporal spread of the echoes exceeds about a hundred symbols.

A more advantageous way to improve the correction of the intersymbol interference is to use an adaptive filter called decision feedback adaptive filter, working in the time domain. A filter of this kind, illustrated schematically in FIG. 1, is constituted by two temporal filters, a forward filter FF and a feedback filter FB, each receiving different series of symbols at input. The input of the forward filter FF receives symbols {x(n)} produced by the sampling of the received signals, and the input of the feedback filter receives decisions {d(n)}, produced by a decision device C, from the symbols {y(n)} produced after filtering by the forward filter FF. The symbols {y(n)} are the outputs of the total filter.

The outputs y(n) have the form:

where

with i varying from 0 to M-1, represents the symbols produced by the forward filter FF, which comprises M weighting coefficients, and where

with j varying from 1 to N, represents the symbols produced by the feedback filter FB from the decisions d(n-1)=f(y(n-1)) with d(n-N)=f(y(n-N)), with F as a decision function. The filter FB comprises N weighting coefficients b.sub.j.

The operations for filtering the postcursor symbols x(n-j) and the precursor symbols x(n+i) are thus decorrelated. The filter FF is used for the correction of the intersymbol interference induced by the precursor symbols. The feedback filter FB is used for the correction of the intersymbol interference induced by the postcursor symbols.

Since the input/output data from the feedback filter FB come from a decision device, only the outputs y(n) are noise-sensitive. The decision feedback filters are thus less sensitive than the linear filters without looping in the presence of noise.

As the parasitic symbols appear chiefly in the postcursor part, the number M of corrective coefficients a.sub.i of the forward filter FF is much smaller than number N of corrective coefficients b.sub.j of the feedback filter FB. Typically these numbers are about M=30 to 60 coefficients for the forward filter FF and N=250 to 500 coefficients for the feedback filter FB.

A number N of coefficients such as this makes it difficult to integrate both the filters into a common integrated circuit. It is possible, if necessary, to reduce the number of coefficients for the feedback filter FB by using delay lines to shift groups of mainly active coefficients to the estimated positions of the echoes. However, this approach cannot easily be implemented in practice, as the circuit is overloaded with logic operations. Another approach lies in the use of a reduced number of coefficients in the feedback filter. The disadvantage of this kind of alternative approach is that the correction of the intersymbol interference is thereby less efficient.

In view of the above, it is a goal of the invention to implement an improved method of filtering, in which it is possible to correct the intersymbol interference without any reduction in the number of corrective coefficients, while at the same time reducing the complexity of the filters.

The approach suggested by the invention is that of implementing a frequency domain decision feedback filtering operation. This provides the benefit of the low complexity that characterizes frequency domain filtering (the symbols being processed in blocks of symbols) and, at the same time, gives advantages in terms of correction of the intersymbol interference from the decision feedback filtering operation. In term of complexity, the frequency domain filtering enables a significant reduction in the number of operators needed as compared with time domain processing, thus making it easier to set up the filter in a VLSI circuit.

Thus, the invention proposes a decision feedback filter device comprising a forward filter and a feedback filter for the production, from input symbols and output symbols, of the corresponding decisions, the forward filter receiving the input symbols at input, and the feedback filter receiving the decisions at input, characterized in that the forward filter carries out a frequency domain filtering of blocks of M input symbols, and in that the feedback filter carries out a frequency domain filtering of blocks of L decisions, with L being lower than M.

Other particular features and advantages shall appear from the following description, in conjunction with the appended drawings, of which:

FIG. 1, already described, provides a schematic view of a time domain filtering device with decision feedback,

FIG. 2 represents the phenomenon of multipath propagation and the correction made by a time domain filtering device with decision feedback,

FIG. 3 illustrates the phenomenon of multipath propagation and the correction made by a filtering device according to the invention,

FIG. 4 gives a schematic view of a filtering device according to the invention,

FIG. 5 gives a schematic view of a first filter of the device of FIG. 4,

FIG. 6 gives a schematic view of a second filter of the device of FIG. 4,

FIG. 7 shows a frequency domain adaptive filtering device,

FIG. 8 represents an adaptive filtering device that comprises a coefficient computation device made with a decision feedback filter of the invention,

FIG. 9 provides a schematic view of an algorithm for updating the coefficients of a computation device.

FIGS. 1 and 2 illustrate time domain decision feedback filtering.

A goal of the invention is to transpose the decision feedback filtering from the time domain into the frequency domain, the symbols being processed in blocks of symbols, and the filtering in the direct and feedback filters being done in the frequency domain.

Let it be assumed that the symbols are assembled in blocks of M symbols x(n) to x(n+M-1), these blocks being filtered simultaneously in order to produce output blocks y(n) to y(n+M-1). The relationship (1) defined here above is no longer applicable. Indeed, to compute y(n+1), it is necessary to have d(n). This entails the assumption that y(n) is known. It is thus not possible to produce y(n) and y(n+1) simultaneously. In other words, the transposition of the decision feedback filtering into the frequency domain is no trivial matter.

To solve this problem, the invention proposes to modify the above relationship (1) and to use the following relationship (2):

with

i varying from 0 to M-1,

j varying from 1 to N, t and L being integers.

Taking L>1, and assuming that the decisions prior to d(n) are known, it is possible to compute the outputs y(n) to y(n+L) simultaneously. It is therefore possible to compute the decisions d(n) to d(n+L). From these decisions, it is then possible to compute the outputs y(n+L+1) to y(n+2L) and so on and so forth.

By choosing L such that M=P*L with P as an integer, and N such as N=D*M, with D as an integer, the processing of a block (x(n) . . . x(n+M-1)) can be done in P successive stages.

The outputs y(n) are produced from three components (see FIG. 3):

with

i varying from 0 to M-1,

j2 varying from 1 to M (feedback sub-filter FB.sup.1),

j2 varying from M+1 to N (feedback sub-filter FB.sup.2),

As compared with FIG. 2, FIG. 3 shows a shift in the feedback filtering (formed by the two sub-filters FB.sup.1 and FB.sup.2 in the postcursive part). In other words, the decisions are provided to the feedback filter with a lag of L time intervals with respect to the taking of the decision. The forward filter is itself shifted. In practice, t.gtoreq..multidot.L is chosen, in order to filter the symbols x(n-1) with x(n-L) in the forward filter FF. Furthermore, the forward filter FF will include, in practice, a greater number M' of coefficients, such that N+M'-1-t is equal to N+M-1, so that for a given application (i.e. for a given number of postcursor symbols) the filtering of the postcursive part covers all the postcursive components.

The relationship (3) can be put in matrix form, the indices indicating the dimensions of the vectors and the exponent T signifying the transposed matrix:

with

and for j from 0 to M-1:

with

Having thus reformulated the time domain decision feedback filtering so that the symbols can be processed in blocks of symbols, the invention proposes to transpose this filtering to the frequency domain.

FIG. 4 illustrates a filter according to the invention.

The filter receives successive symbols x(n) at input.

By series/parallel conversion 10, the symbols are assembled in blocks x.sup.M (n) of M successive samples (x(n) . . . x(n-M+1)), k representing the rank of the block.

These blocks go through a 2M order forward filter FF 1 (corresponding to the transposition of an M order time domain filter into the frequency domain). In the example shown, this filter FF has the standard structure of a frequency domain fast linear filter. For example, a partitioning of the input will be used according to the so-called overlap-save technique with an overlap rate of 50%. After a discrete Fourier transform 11 has been performed on the input blocks, they are multiplied in a multiplexer 12 by a block A.sub.2M (k) of 2M weighting coefficients. Then, by reverse Fourier transform 13, a block z.sub.M (n) of M symbols is produced at output of the filter FF.

The outputs y(n) are computed as a function of the output symbols from the filter FF and of decisions d(n) produced by a decision device DO from the preceding outputs, these decisions having been filtered by a 2N order frequency domain feedback filter FB (corresponding to the transposition of a time domain N order filter into the frequency domain). This feedback filter consists of two frequency domain sub-filters FB.sup.1 and FB.sup.2, illustrated respectively in FIGS. 5 and 6.

From these symbols and decisions d(n), an addition 14 enables the production, in the time domain, of the outputs y(n) corresponding to the input symbols x(n).

The outputs y(n) are therefore obtained by the addition of three components.

A first component of the relationship (3) is produced by the forward filter FF. These are output samples z(n) of this filter contained in the block z.sub.M (k).

A second component u.sup.1 (n) is produced by the sub-filter FB.sup.1 which corresponds to the 2M first coefficients of the filter FB.

A third component u.sup.2 (n) is produced by the sub-filter FB.sup.2 which corresponds to 2(N-M) last coefficients of the filter FB.

As we have seen, the difficulty to be resolved is that of obtaining, for each block of outputs, decisions needed for the computation of the outputs, these decisions corresponding to outputs of the same block.

It is assumed that the decisions corresponding to the last outputs produced are known.

The blocks of output symbols z.sub.M (k) are partitioned into sub-blocks of a size L with L as an integer such that L=M/P, with P as an integer.

From the sub-block corresponding to the L first output symbols of FF, the L corresponding outputs are produced by time domain summation (see relationship (3)). From these outputs, a block of L corresponding decisions is produced in a decision device DO.

These decisions are thus processed in the sub-filter FB.sup.1 corresponding to a frequency domain linear filter (through the use for example of the overlap-save technique with an overlap rate of 50%).

The sub-filter FB.sup.1 (FIG. 5) constitutes, by means of P shift circuits such as 15, P successive blocks of 2L symbols (P*L=M) after discrete Fourier transform 16 of the blocks of L decisions. The circuits 15 give, at output, blocks that are lagged with respect to one another by a time interval corresponding to L decisions. P multipliers 17 compute the products of the symbols of the P blocks by corresponding weighting coefficients that are assembled in blocks of 2L coefficients (B.sub.2L.sup.11 (n), . . . B.sub.2L.sup.1P (n)). The multipliers give, at output, P blocks of 2L symbols which are then summed up in parallel in an adder 18 whose output gives 2L symbols. These 26 symbols enable the production, by a reverse discrete Fourier transform, of a block of L symbols u.sup.1 (n) in the time domain.

It is then possible to produce the L following outputs by the addition 14 in the time domain. Through the renewal of this operation P times, all the outputs (and consequently the decisions) corresponding to the M output symbols of the forward filter are produced successively. In one example, the sub-filter FB.sup.1 (just like the sub-filter FB.sup.2) is of the type described in the patent application FR-A-2 702 612. The sub-filter FB1, or the filter FB as a whole, therefore works at a frequency that is p times higher than that of the forward filter FF.

The sub-filter FB.sup.2 (FIG. 6) corresponding to the N-M last coefficients of time domain feedback filtering has a structure comparable to that of the sub-filter FB.sup.1. Just like the first sub-filter, it produces blocks of L symbols u.sup.2 (n) added, in the time domain, with the sub-blocks of L output symbols of the forward filter to produce corresponding outputs. For a block of M output symbols of the forward filter FF and, unlike the first sub-filter, these symbols u.sup.2 (n) are produced from decisions corresponding to the previous block of symbols of the forward filter FF. In other words, it is used in a manner similar to a feedback filter of a time domain decision feedback filter. The blocks of L decisions received from the decision device are grouped together in a step 20 in groups of M by parallel/parallel conversion. The sub-filter FB.sup.2, by means of shift circuits such as 21, constitutes (J-1) successive blocks of 2M symbols (with J such that J*M=N) after Fourier transform 22 of the blocks of M decisions. The delay circuits 21 provide blocks at output that are lagged with respect to one another by a time interval corresponding to M decisions. J-1 multipliers 23 take the products of the symbols of the blocks by corresponding weighting coefficients grouped together in blocks of 2M coefficients (B.sub.2M.sup.2 (k), . . . ,B.sub.2M.sup.J (k)). The multipliers 23 give, at output, J-1 blocks of 2M symbols which are then summed up in parallel in an adder 24 whose output gives 2M symbols. These symbols enable the production, by reverse discrete Fourier transform 25 and parallel/parallel conversion 26, of P blocks of L symbols u.sup.2 (n) in the time domain. These blocks u.sup.2 (n) are used to compute the outputs corresponding to the output symbols from the forward filter of the block following the one from which they have been produced.

The filter thus described has the advantages, in terms of complexity, of frequency type applications and the advantages, in terms of performance, of decision feedback filtering.

To correct the intersymbol interference induced by the reception of echoes, as the input symbols (x(n)) are accompanied by precursor echoes x(n+j) and postcursor echoes x(n-j), the forward filter FF performs a filtering on the precursor echoes and on near postcursor echoes, and the feedback filter FB performs a filtering on the decisions produced from the postcursor echoes, these decisions being provided to the feedback filter with a delay of L time intervals, a time interval being the period of time between two successive symbols. Preferably, the forward filter carries out a filtering operation on the postcursor echoes whose corresponding decisions are not filtered by the feedback filter so that all the postcursor and precursor echoes are taken comprehensively into account by the total filter.

As has been seen, the weighting coefficients A.sub.2M B.sub.2L B.sub.2M are preferably variable in time so as to adapt the response of the filter to the variants of the transmission channel. In practice, the computation of the coefficients is uncoupled from the filtering itself. Since this computation generally requires a large number of operations, it is done most of the time on a deferred time basis by a digital signal processor (DSP) type of computation device.

In specific terms, an adaptive filter schematically takes the form shown in FIG. 7. The input symbols {x(n)} received are processed by a filter F for the production in real time, using weighting coefficients (referenced a.sub.i and b.sub.j), of the corresponding outputs and decisions. The filter F will, for example, be a filter shown in FIG. 4. The weighting coefficients are produced by a computation element OC. From input symbols, it produces the corresponding outputs and decisions by means of a preliminary filter FP. These outputs and decisions are then used by a computation filter FC to produce the weighting coefficients which are given to the filter F.

It is quite possible to use different types of filters to make the filters F and FP. In practice, this is often the case. Since the filter F is used in real time, it is indispensable that its processing speed should be compatible with the symbol frequency. As far as the filter FP of the computation device is concerned, this constraint is not present. It is therefore possible to make a filter FP that has high precision, without being concerned about the time needed to produce the outputs and decisions, provided that the transmission channel is stationary for the period of computation of the coefficients. It is possible for example, for the filter FP, to use a frequency domain filter, a time domain filter or a decision feedback filter.

One way of making the computation device OC is to use a time domain decision feedback filter as shown in FIG. 8.

A standard algorithm for the adaptation of coefficients in the time domain, working step by step, is that of the least mean squares algorithm which can be put in the form:

with

and .mu..sup.a and .mu..sup.b being constants (representing a convergence pitch for the forward filter and the feedback filter).

LMS type filters are already known in the frequency domain (see for example E. R. Ferrara, "Frequency-Domain Adaptive Filtering", C. F. N. Cowan and P. M. Grant, ed. Adaptive Filters, Englewood Cliffs, Prentice Hall, 1985, Chapter 6, pp. 145-1479). One approach to the computation of the coefficients is to use a time domain decision feedback filter FP, working step by step, store the outputs and decisions produced and set up an LMS type frequency domain computation algorithm FC (in fact the computation algorithm then consists of two LMS type algorithms for the respective production of the coefficients of the forward filter and of the feedback filter).

The use of an algorithm FC made according to one improvement of the invention enables a considerable reduction in the complexity of the computation device OC. Indeed, it is then possible to obtain a frequency domain adaptation of the coefficients, the computation device then comprising a filter FP made in accordance with FIG. 4 and a computation filter FC made in accordance with FIG. 9 using a new formulation of the matching algorithms so that:

and

It is possible, in the adaptive part, to choose to work on blocks of N symbols. In other words, the adaptation of the coefficients in the filter F is delayed by N time intervals (a time interval corresponding to the time gap between two successive symbols). In practice, it is even possible to delay the adaptation of the coefficients in the filter F by several blocks of N symbols if the environment is assumed to be stationary for some milliseconds (this corresponds in standard applications to some tens of blocks of N symbols).

A description shall now be given of the computation algorithm FC shown in FIG. 9. To facilitate understanding by the reader, a mathematically formalistic approach will be used. Specifically, this algorithm will typically be made in the form of a digital signal processor (or DSP).

The symbols x(n), y(n) and d(n) are assembled in series/parallel converters 27-29 in blocks x.sub.M (k)=(x(kN+M-t) . . . x(kN+M-t+N-1)), y.sub.N (k)=y(kN-L) . . . y(kN-L+N-1)) and d.sub.N (k)=(d(kN-L) . . . d(kN-L+N-1)) of N successive symbols and decisions. From the blocks y.sub.N (k) and d.sub.N (k), a summator 30 is used to produce an block of errors e.sub.N (k)=d.sub.N (k)-y.sub.N (k).

Using the k.sup.th blocks x.sub.N (k) and d.sub.N (k), concatenation devices 31-32 are used to produce blocks of 2N elements by concatenation with the (k-1)th corresponding blocks, the block e.sub.N (k) for its part being complemented by N zeros in a concatenation device 33.

A passage into the frequency domain is then got by discrete Fourier transforms 34-36. Thus, matrices X.sub.2N (k), D.sub.2N (k) and E.sub.2N (k) are produced such that:

O.sub.N and I.sub.N being respectively the N-dimensioned identically zero square matrix and identity matrix; : signifying a concatenation by juxtaposition; diag signifying the diagonal matrix; and FFT signifying the discrete Fourier transform operation.

It will be noted that the matrices are in practice blocks of 2N elements represented mathematically, with a view to concision, by diagonal matrices with a dimension 2N.

Then, in the recursive filters 37 and 38, there are produced matrices with a dimension 2N, referenced M.sub.2N.sup.A (k) and M.sub.2N.sup.B (k) such that:

with

1.sub.2N being a vector with a dimension 2N having all its elements at 1 to obtain a result vector, .lambda. being a neglect factor less than 1, H signifying the transpose and diagP.sub.1.sup.-x (k) signifying the constitution of a diagonal matrix whose non-zero terms are the inverse values (whence the exponent -) of the components of the vector X.sub.1 (k), . . . , X.sub.2 N(k), and similarly for diagP.sub.1 -d(k) with the vector D.sub.1 (k), . . . , D.sub.2N (k).

By using two multipliers 39, 40, the following matrices are then produced:

and

The diagonal matrices M.sub.2N.sup.AX (k) and M.sub.2N.sup.BD (k) are then transposed into the time domain by reverse discrete Fourier transform operations 41, 42.

Then, in the concatenation devices 43, 44, the 2N-M last elements of the block M.sub.2N.sup.AX (k) and the N last elements of M.sub.2N.sup.BD (k) are cancelled. This mathematically consists of the computation Q.sup.M.M.sub.2N.sup.AX (k) and Q.sup.N M.sub.2N.sup.BD (k), with: ##EQU1##

The blocks are then transposed at 45, 46 into the frequency domain by discrete Fourier transform.

In order to produce A.sub.2N (k+1) and B.sub.2N (k+1), it is enough to use two adders 47, 48 and two delay circuits 49, 50 so that the following computation is done:

Specifically, two blocks of 2N elements are produced (these blocks being formed by diagonal elements of the matrices A.sub.2N (k+1) and B.sub.2N (k+1)).