Method and apparatus for computing prefilter coefficients

[0002] This invention relates in general to digital communication systems that include a digital prefilter in conjunction with a Decision Feedback Sequence Estimation (DFSE) equalizer, and more particularly, to a system and method for computing the coefficients of such a prefilter.

[0003] Digital wireless communication systems require equalization to compensate for intersymbol interference (ISI) resulting from time dispersion or delay spread in the channel. Typically, a non-linear equalizer, such as a Maximum Likelihood Sequence Estimation (MLSE) equalizer, is used to provide coherent demodulation, and thus, compensation for ISI, in such digital wireless communication systems. However, while a MLSE equalizer performs adequately, it is complex to implement.

[0004] Other equalizers have also been used to provide compensation for ISI. For example, a Decision Feedback Sequence Estimation (DFSE) equalizer has been used in place of the MLSE equalizer. While the complexity of implementing the DFSE equalizer can be substantially lower than the complexity of implementing the MLSE equalizer, the DFSE equalizer alone provides suboptimal results compared to the MLSE equalizer.

[0005] A finite impulse response (FIR) prefilter may be used with the DFSE equalizer to improve performance. The impulse response of the prefilter is determined by coefficients that are calculated by complex mathematical equations. While a DFSE equalizer with a prefilter can perform very close to the MLSE equalizer, the complexity of the mathematical equations to determine the coefficients of the prefilter can offset the complexity savings afforded by the DFSE equalizer.

[0006] In some communication systems the receiver operates on a burst-by-burst basis, i.e. the receiver first collects a burst of received samples, and then starts processing this collected burst. In this type of system, the receiver typically equalizes part of the burst “forward in time” and it equalizes the other part of the burst “backward in time.” Two different prefilters must then be used, one for forward equalization and one for backward equalization. Multiple prefilters along with the corresponding impulse response calculations reduce the complexity savings afforded by the DFSE equalizer.

[0007] The DFSE equalizer will now be explained. The DFSE equalizer can be best explained as an approximation of a well-known MLSE equalizer. The MLSE equalizer considers various hypotheses for the transmitted symbol sequence, and with a model of the dispersive channel, determines which hypothesis best fits the received samples. This is efficiently realized using the Viberbi algorithm. This equalization technique is well known to those skilled in the art, and can be found in J. C. Proakis, Digital Communication, McGraw-Hill (1989).

[0008] The conventional MLSE equalizer can be explained by a simple example. Suppose the transmitter transmits a symbol stream s(n), which takes on values “+1” or “−1” corresponding to bit values 0 or 1 respectively. This stream is modulated using binary-shift keying (BPSK). At the receiver, the received signal is filtered, amplified, and mixed down using I and Q carriers, then sampled once every symbol period (T), giving a received signal stream r(n). In this example, an intervening channel consists of three rays, a main ray and two echoes, where the first echo arrives T second later, and the second echo arrives 2T seconds later. The received signal at baseband can then be modeled as:

[0009] r(n)=c₀s(n)+c₁s(n−1)+c₂s(n−2)+η(n)  (1)

[0010] where c₀, c₁and c₂are complex channel tap values, and η(n) is additive noise or interference.

[0011] In the MLSE equalizer, at iteration n, there are four different previous “states” (0, 1, 2, and 3), corresponding to the four possible values for the two most recent previous symbols:

[0012] 1. (s(n−1)=−1, s(n−2)=−1)⇄Previous State=0

[0013] 2. (s(n−1)=−1, s(n−2)=+1)⇄Previous State=1

[0014] 3. (s(n−1)=+1, s(n−2)=−1)⇄Previous State=2

[0015] 4. (s(n−1)=+1, s(n−2)=+1)⇄Previous State=3.

[0016] Associated with each previous state there is an accumulated metric, accumulated from previous iterations, giving rise to accumulated metrics:

[0017] (A₀(n−1), A₁(n−1), A₂(n−1), A₃(n−1)).

[0018] There are also four current states corresponding to four possible values for the 2-tuple [s(n), s(n−1)]. Each possible paring of a previous state with a current state corresponds to a hypothetical 3-tuple sequence [s_h(n), s_h(n−1), s_h(n−2)]. For each of these hypotheses, there is a corresponding hypothesized received signal value at time n:

[0019] r_h(n)=c₀s_h(n)+c₁s_h(n−1)+c₂s_h(n−2).  (2)

[0020] Furthermore, for each of these hypothesis, there is a corresponding “branch” metric given by: $\begin{array}{cc}{M}_h\left(n\right)={\left|r\left(n\right)-r_h\left(n\right)\right|}^2& \left(3\right)\\ ={\left|r\left(n\right)-\sum _{k=0}^2{c}_k{s}_h\left(n-k\right)\right|}^2.& \left(4\right)\end{array}$

[0021] In this example, there are eight possible hypothetical sequences, corresponding to eight different pairings of a previous state and a current state.

[0022] In an MLSE equalizer for each “n”, eight branch metrics must be computed according to equation (4). There is one branch metric corresponding to each possible value of the 3-tuple [s_h(n), s_h(n−1), s_h(n−2)]. Since each element of this 3-tuple has two possible values, there are 8=2³possible 3-tuples.

[0023] The DFSE equalizer can be best explained by continuing the above example with three channel taps (c₀, c₁, c₂). In a DFSE equalizer, the three channel taps are usually divided into two parts: an MLSE part consisting of the first few-taps (e.g. c₀and c₁), and a DFE part consisting of the other trailing taps (e.g. c₂). Next, a trellis corresponding only to the MLSE taps (in this example the state will have just one element) is constructed. The branch metric of the DFSE equalizer at time n is:

[0024] dM_h(n)=|r(n)−c₀s_h(n)−c₁s_h(n−1)−c₂{overscore (s)}(n−2)|²  (5)

[0025] where [s_h(n), s_h(n−1)] come from the hypothesized paring of the previous state and the current state, but {overscore (s)}(n−2) denotes the decided symbol obtained from the path history of the previously hypothesized state.

[0026] Comparing the branch metric of the DFSE (equation (5)) to the branch metric of the MLSE (equation (4)), the MLSE equalizer at time n hypothesizes all possible values of the 3-tuple [s_h(n), s_h(n−1), s_h(n−2)], while the DFSE equalizer. at time n only hypothesizes all the possible values of the 2-tuple [s_h(n), s_h(n−1)]. Hence, the MLSE equalizer computes eight-branch metrics for each n, while the DFSE equalizer computes only four-branch metrics for each n. The DFSE equalizer is approximately one half the complexity of the MLSE equalizer in this example. Correspondingly, the performance of the DFSE equalizer is also less than the MLSE equalizer.

[0027] In this example, for the performance of the DFSE equalizer to be close to the performance of the MLSE equalizer, it is desirable to make |c₂|²as small as possible. If c₂=0, then the DFSE equalizer is equivalent to the MLSE equalizer. More generally, if the intervening channel has coefficients ${\left\{c_i\right\}}_{i=0}^{L_c-1},$

[0028] then the DFSE equalizer partitions these L_ccoefficients into two parts: the MLSE part consisting of the leading L_MLSEcoefficients (i.e. $\left(i.e.{\left\{c_i\right\}}_{i=0}^{L_{\mathrm{MLSE}}-1}\right),$

[0029] and the DFE part consisting of the trailing coefficients (i.e. $\left(i.e.{\left\{c_i\right\}}_{i=L_{\mathrm{MLSE}}}^{L_c-1}\right).$

[0030] The resulting branch metric for time n for the DFSE equalizer is: $\begin{array}{cc}d{M}_h\left(n\right)={\left|r\left(n\right)-\sum _{k=0}^{L_{\mathrm{MLSE}}-1}{c}_k{s}_h\left(n-k\right)-\sum _{k=L_{\mathrm{MLSE}}}^{L_c-1}{c}_k{\stackrel{\_}{s}}_h\left(n-k\right)\right|}^2.& \left(6\right)\end{array}$

[0031] Since only ${\left\{c_i\right\}}_{i=0}^{L_{\mathrm{MLSE}}-1}$

[0032] are hypothesized, the number of possible branch metrics that need to be computed for each n is only 2^Lfor the DFSE equalizer but 2^Lfor the MLSE equalizer.

[0033] In a typical implementation of the DFSE equalizer, the received signal, r(n), is first passed through a FIR prefilter having an impulse response ${\left\{f\left(n\right)\right\}}_{n=0}^{L_f-1}.$

[0034] A composite baseband channel which is the channel now seen by the DFSE equalizer is expressed as g(n)=c(n)*f(n). A signal r′(n) representing the received signal after passing through the prefilter can be expressed in terms of the transmitted symbols, s(n)′s, according to: $\begin{array}{cc}{r}^{\prime }\left(n\right)=\sum _{k=0}^{L_h-1}s\left(n-k\right)g\left(k\right)+v\left(n\right),& \left(7\right)\end{array}$

[0035] where v(n)=w₁(n)*f(n). The DFSE equalizer then operates on r′(n), and the intervening channel seen by the DFSE equalizer is now ${\left\{g\left(n\right)\right\}}_{n=0}^{L_h-1}.$

[0036] The goal in computing the prefilter f(n) is to get a composite channel, g(k)′s, such that the trailing taps $({\left\{g\left(n\right)\right\}}_{n=L_{\mathrm{MLSE}}}^{L_h-1}$

[0037] are the trailing taps of g(k)) are as small as possible. For the DFSE to perform well, it is also desirable that |F(ω)| (i.e. the magnitude of the Fourier transform of the prefilter f(n)) be constant for all frequencies ω (i.e. we would like |F(ω)|≈1 for all ω).

[0038] One method for computing the impulse response of the prefilter f(n) for the DFSE is disclosed by S. Ariyavisitakul, J. H. Winters, N. R. Sollenberger, Joint Equalization and Interference Suppression for High Data Rate Wireless Systems, Proceedings of IEEE Vehicular Technology Conference, Houston, 1999. The method involves solving a system of L_flinear equations (where L_fis the length of the FIR prefilter f(n)). Solving this system of equations requires approximately 2×L_f³operations. For each burst of the received samples, the coefficients for two such prefilters need to be computed (one for equalizing “forward in time” and another for equalizing “backward in time”). In summary, this method requires approximately 4×L_f³operations.

[0039] Accordingly, there is a need for a receiver system and method that provides a low complexity mechanism for computing the impulse response (i.e. coefficients) of the prefilter used in the DFSE equalizer. There is a further need for such a receiver system and method that avoids performing two prefilter computations per burst (one computation for the “forward equalization”, and one computation for the “backward equalization”).

[0040] The present inventions meets these needs by providing a receiver system having a prefilter and a DFSE equalizer in which the impulse response of the prefilter is computed relatively easily. A channel estimate is determined in response to signals received by the receiver system. The channel estimate may include a forward channel estimate and a backward channel estimate. Roots of a z-transform of the forward channel estimate and roots of a z-transform of the backward channel estimate are determined. Those roots of the z-transform of the forward channel estimate having a magnitude greater than one are used to form a z-transform of a forward impulse response of the prefilter while those roots of the z-transform of the backward channel estimate having a magnitude greater than one are used to form a z-transform of a backward impulse response of the prefilter. Forward prefilter coefficients for the prefilter are computed based on the z-transform of the forward impulse response of the prefilter and backward prefilter coefficients for the prefilter are computed based on the z-transform of the backward impulse response of the prefilter. A forward impulse response of a forward composite channel are computed based on the forward prefilter coefficients while a backward impulse response of a backward composite channel are computed based on the backward prefilter coefficients.

[0041] According to a first aspect of the present invention, a method of computing a prefilter comprises estimating a channel estimate of a signal received by a receiver. Roots of a z-transform of the channel estimate are determined. A z-transform of an impulse response of the prefilter is formed based on the roots of the z-transform of the channel estimate. Prefilter coefficients of the prefilter are computed based on the z-transform of the impulse response of the prefilter.

[0042] According to another aspect of the present invention, a method of computing a prefilter comprises estimating a forward channel estimate and a backward channel estimate of a signal received by a receiver. Roots of a z-transform of the forward channel estimate are determined. Roots of a z-transform of the backward channel estimate are determined. A z-transform of a forward impulse response of the prefilter is formed based on the roots of the z-transform of the forward channel estimate. A z-transform of a backward impulse response of the prefilter is formed based on the roots of the z-transform of the backward channel estimate. Forward prefilter coefficients of the prefilter are formed based on the z-transform of the forward impulse response of the prefilter. Backward prefilter coefficients of the prefilter are computed based on the z-transform of the backward impulse response of said prefilter.

[0043] According to yet another aspect of the present invention, a method of computing a prefilter comprises estimating a channel estimate of a signal received by a receiver. Roots of a z-transform of the channel estimate are determined. A z-transform of a forward impulse response of the prefilter is formed based on the roots of the z-transform of the channel estimate having a magnitude greater than one. A z-transform of a backward impulse response of the prefilter is formed based on the roots of the z-transform of the channel estimate having a magnitude less than or equal to one. Forward prefilter coefficients of the prefilter are computed based on the z-transform of the forward impulse response of the prefilter. Backward prefilter coefficients of the prefilter are computed based on the z-transform of the backward impulse response of the prefilter.

[0044] The present invention provides a low complexity mechanism for computing the impulse response (i.e. coefficients) of the prefilter used in the DFSE equalizer. The receiver and method for computing the impulse response of the prefilter avoids the need to perform two prefilter computations per burst (one computation for the “forward equalization”, and one computation for the “backward equalization”). Other features and advantages of the invention will be apparent from the following description, the accompanying drawings and the appended claims.

[0045] FIG. 1 illustrates a wireless communication system according to the present invention;

[0046] FIG. 2 illustrates a GSM burst structure used with the wireless communication system of FIG. 1;

[0047] FIG. 3 illustrates a baseband processor of the wireless communication system of FIG. 1;

[0048] FIG. 4 illustrates a composite channel model in a forward direction of a DFSE Equalizer of the baseband processor of FIG. 3;

[0049] FIG. 5 illustrates a composite channel model in a backward direction of the DFSE Equalizer of the baseband processor of FIG. 3;

[0050] FIG. 6 is a flowchart illustrating the computation of prefilter coefficients in the forward and backward directions for a prefilter of the baseband processor of FIG. 3 according to a first aspect of the present invention; and

[0051] FIG. 7 is a flowchart illustrating the computation of prefilter coefficients in the forward and backward directions for the prefilter of the baseband processor of FIG. 3 according to a second aspect of the present invention.

[0052] The present invention is a method for computing the impulse response of a prefilter in a digital communication receiver, which requires smaller amount of computations than that required by the conventional method. This invention can be used in receivers of any radio communication systems, such as the Global System for Mobile Communication (GSM) or the Enhanced Data rates for Global Evolution (EDGE), to improve the performance of equalization at baseband. For illustrative purposes, the following description is directed to the GSM systems and to a communication receiver that uses a DFSE equalizer. However, it will be appreciated by those skilled in the art that the invention is not so limited and applies to other systems, such as IS-136, and to receivers with other types of equalizers as well.

[0053] Referring to FIG. 1, a block diagram of a hardware implementation of a radio communication system 90 is illustrated. The radio communication system 90 comprises a line 99, a digital symbol generator 100, a digital transmitter 101, a transmitting antenna 102, a receiving antenna 103, a radio unit 104, an analog-to-digital (AND) converter 105 and a baseband processor 106. Voice or data information to be transmitted is delivered on line 99 to the digital symbol generator 100. The symbol generator 100 develops transmitted symbols s(n) based on the received information signal from line 99. The transmitted symbols s(n) are then supplied to the digital transmitter 101. The transmitter 101 transmits radio signals containing information about s(n) via the transmitting antenna 102 through a channel medium 92. The radio signals are received by the receiving antenna 103 of the radio unit 104. The radio unit 104 filters and amplifies the received signals and converts them to a suitable form for processing. The received signals may be represented as analog samples that are provided to the A/D converter 105, whose outputs are digital samples suitable for processing by the baseband processor 106. The baseband processor 106 processes the digital samples from the A/D converter 105 and produces estimated symbols ŝ(n). The transmitter 101, the channel 92, the radio unit 104, and the A/D converter 105 will be referred to as a transmission function 107 hereinafter. The baseband processor 106 along with the receiving antenna 103, the radio unit 104 and the AND converter 105 form a receiver.

[0054] In most communication systems, the transmitted symbols s(n) are grouped into blocks or bursts, each containing many unknown symbols and a few known symbols. Specifically, in the GSM systems, each burst consists of 148 symbols, with each symbol containing one bit of information. As shown in FIG. 2, each burst has time duration of 577 μsec and contains a training sequence of 26 symbols and 3 tail symbols at either end of the burst. The tail symbols are both known a priori at the receiver. Each burst carries 58 data symbols at either side of the training sequence. The goal of an equalizer in a receiver is to detect these data symbols with as low error rate as possible. To obtain a good initial start, an equalizer typically starts detection from the data symbols right beside the training sequence and going towards each end of the burst. In other words, an equalizer would typically be detecting the 58 data symbols on the left side of the training symbols in the backward direction and then detecting the 58 data symbols on the right side in the forward direction. Hereinafter, we will refer to the concatenation of the 3 tails symbols on the left side, the first 58 data symbols from the left side, and the 26 training symbols as the first half burst. Similarly, the concatenation of the 26 training symbols, the second 58 data symbols from the left side, and the 3 tails symbols on the right side as the second half burst.

[0055] Referring now to FIG. 3, a detailed block diagram of the baseband processor 106 is illustrated. The baseband processor 106 comprises a synchronizer 108, a channel estimator 109, a prefilter coefficient generator 110, a prefilter 113 and a DFSE equalizer 114. The digital samples from the transmission function 107 are transmitted to the synchronizer 108 and the channel estimators 109. The synchronizer 108 is configured to identify the position of the training sequence, and thus the relative positions of the data symbols, of each burst contained in the received samples. The synchronizer 108 produces bursts of symbols in the format depicted in FIG. 2.

[0056] The channel estimator 109 is configured to model the digital symbols from the transmission function 107 in conjunction with the synchronizer 108 as a linear filter with a finite impulse response. The channel estimator 109 develops a channel estimate c(n) of the impulse response of such a filter. The prefilter coefficient generator 110 receives the channel estimate c(n) and computes impulse responses of a desired prefilter and the impulse responses of corresponding composite channels, which will be defined later. The prefilter 113 receives bursts of symbols from the synchronization block 108 and performs linear filtering on the bursts based on the impulse responses received by the prefilter coefficient generator 110. The output of the prefilter 113 is transmitted to the DFSE equalizer 114. The DFSE equalizer detects the transmitted data symbols contained in each burst from the prefilter 113, based on the impulse responses of the composite channels received from the prefilter coefficient generator 110.

[0057] As described above, in a communication system like the GSM system where the training symbols are located in the middle of a burst, the data symbols in each half burst are typically detected by the DFSE equalizer 114 in either the forward direction or the backward direction. Forward and backward equalization will be described based on the models illustrated in FIGS. 4 and 5, respectively. It will be appreciated by those skilled in the art that the block diagrams illustrated in FIGS. 4 and 5 are for illustrative purposes only and do not necessarily represent the components illustrated in FIG. 3 per se.

[0058] Referring now to FIG. 4, a forward equalization model 200 is represented by a forward linear filter 115, an adder 116, a forward prefilter 113A and a forward DFSE equalizer 114A. Similarly, referring now to FIG. 5, a backward equalization model 300 is represented by a backward linear filter 120, the adder 116, a backward prefilter 113B and a backward DFSE equalizer 114B. When performing equalization in the forward direction as illustrated in FIG. 4, the transmission function 107 in conjunction with the synchronizer 108 can be modeled by the linear filter 115 with a finite impulse response c_forward(n), (followed by an addition of a white noise signal w₁(n) via the adder 116. Similarly, when performing equalization in the backward direction as illustrated in FIG. 5, the combination of the transmission function 107 and the synchronization block 108 can be modeled by the linear filter 120 with impulse response c_backward(n) followed by an addition of a white noise signal w₂(n) via the adder 116.

[0059] The corresponding inputs to the forward linear filter 115 and to the backward linear filter 120 are denoted by s_forward(n) and s_backward(n), respectively, which are derived from the transmitted symbols s(n). The finite impulse response c_forward(n) of the linear filter 115, hereinafter referred to as the forward channel response, is equal to the channel estimate c(n) generated by the channel estimator 109. The finite impulse response c_backward(n) of the linear prefilter 120, hereinafter referred to as the backward channel response, is related to the forward channel response c_forward(n) by changing the order of time indices. More precisely, let c_forward(n), n=0,1,2, . . . L−1, denote the impulse response in the forward direction, where L denotes the length of the impulse response. The backward channel response is then represented by:

[0060] c_backward(n)=c_forward(L−1−n).  (10)

[0061] In other words, the first tap of the backward channel response is equal to the last tap of the forward channel response, the second tap of the backward channel response is equal to the second to last tap of the forward channel response, and so on.

[0062] The operations performed on the first half burst and the second half burst by the prefilter 113 in FIG. 3 are separated into the backward prefilter 113A in FIG. 5 and the forward prefilter 113B in FIG. 4, respectively. It will be appreciated by those skilled in the art that the forward and backward prefilters 113A, 113B are actually the same prefilter with different impulse responses. Specifically, the impulse response of the forward prefilter 113A is f_forward(n) and the impulse response of the backward prefilter 113B is f_backward(n). Both f_forward(n) and f_backward(n) are generated by the prefilter coefficient generator 110, and together establish the output of the prefilter coefficient generator 110 in FIG. 3 received by the prefilter 113.

[0063] Similarly, the operations performed on the first half burst and the second half burst by the DFSE equalizer 114 in FIG. 3 are modeled by the backward DFSE equalizer 114B in FIG. 5 and the forward DFSE equalizer 114A in FIG. 4. Two different impulse responses, g_forward(n) and g_backward(n), are needed for the forward DFSE equalizer 114A and the backward DFSE equalizer 114B. The forward impulse response g_forward(n) is equal to the convolution of c_forward(n) and f_forward(n), while the backward impulse response g_backward(n) is equal to the convolution of c_backward(n) and f_backward(n). Both g_forward(n) and g_backward(n) are generated by the prefilter coefficient generator 110, and together they establish the output of the prefilter coefficient generator 110 in FIG. 3 received by the DFSE equalizer 114.

[0064] Referring to FIG. 4, the effective channel model from the perspective of the forward DFSE equalizer 114A is the composite channel 119, which has the impulse response g_forward(n). Similarly, referring to FIG. 5, the effective channel model from the perspective of the backward DFSE equalizer 114B is the composite channel 123, which has the impulse response g_backward(n).

[0065] Implementing the prefilter coefficient generator 110 in FIG. 3 will now be described. It is desirable to compute f_forward(n) so as to maximize $\begin{array}{cc}\sum _{k=0}^{L_{\mathrm{MLSE}}}{\left|g_{\mathrm{forward}}\left(k\right)\right|}^2& \left(11\right)\end{array}$

[0066] and to compute f_backward(n) so as to maximize $\begin{array}{cc}\sum _{k=0}^{L_{\mathrm{MLSE}}}{\left|g_{\mathrm{backward}}\left(k\right)\right|}^2.& \left(12\right)\end{array}$

[0067] Equations 11 and 12 are constrained as both f_forward(n) and f_backward(n) have constant magnitudes in their corresponding Fourier transforms, where L_MLSEis the number of MLSE taps. The reason for the constant magnitudes is that the prefilters 113A and 113B would have otherwise colored the frequency spectrum of the additive noise w₁(n) and w₂(n), which often has an adverse effect on the performance of the equalizer. It has been shown that the solution to the maximization problem described in equations 11 or 12, is to make the composite channel g_forward(n), and respectively g_backward(n) to be a minimum-phase impulse response, i.e. all the roots of the z-transform $\begin{array}{cc}{G}_{\mathrm{forward}}\left(z\right)=\sum _{n=0}^{L-1}{g}_{\mathrm{forward}}\left(n\right)z^{-n}& \left(13\right)\end{array}$

[0068] of g_forward(n), and respectively $\begin{array}{cc}{G}_{\mathrm{backward}}\left(z\right)=\sum _{n=0}^{L-1}{g}_{\mathrm{backward}}\left(n\right)z^{-n}& \left(14\right)\end{array}$

[0069] of g_backward(n), must have magnitudes less than or equal to one. See A. V. Oppenheim and R. W. Schafer, Discrete-Time Signal Processing, McGraw-Hill, 1989.

[0070] In accordance with one aspect of the present invention, a flow chart is shown in FIG. 6 summarizing the steps involved in computing f_forward(n) and f_backward(n) that lead to minimum-phase impulse response of the composite channel g_forward(n) and g_backward(n). The steps involved in computing f_forward(n) will be described first, and the corresponding steps involved in computing f_backward(n) follows in a similar manner. In block 124, the roots, denoted by ${\left\{z_n^{\mathrm{forward}}\right\}}_{n=1}^{L-1},$

[0071] of the z-transform of the forward channel estimate c_forward(n) are computed as follows: $\begin{array}{cc}{C}_{\mathrm{forward}}\left(z\right)=\sum _{k=0}^{L-1}{c}_{\mathrm{forward}}\left(n\right)z^{-n}.& \left(15\right)\end{array}$

[0072] It will be appreciated by those skilled in the art that there are many well-known numerical methods for solving the roots of equation 15, such as the Newton-Raphson method and the Laguerre's method. In fact, when the number of taps L of the channel estimate c_forward(n) is less than or equal to 5, there exist closed-form expressions for the roots of equation 15 in terms of the forward channel estimate c_forward(n). In block 125, the subset Q_outof all the roots in {z_n^forward}_n=1^L−1which have magnitudes greater than one is determined. This step can be accomplished by checking whether the quantity z_n^forward·(z_n^forward)* is greater than one for each n=1,2, . . . , L−1, where denotes the complex conjugate. In block 126, the z-transform F_forward(z) of the forward impulse response f_forward(n) of the forward prefilter 113A is calculated using the following formula: $\begin{array}{cc}{F}_{\mathrm{forward}}\left(z\right)=\frac{\prod _{z_i\in Q_{\mathrm{out}}}\left(1-z_i^{•}z\right)}{\prod _{z_i\in Q_{\mathrm{out}}}\left(-z_i+z\right)}.& \left(16\right)\end{array}$

[0073] In block 127, the forward impulse response or forward prefilter coefficients f_forward(n) from the z-transform F_forward(z) described in equation 16 is calculated. It will be appreciated by those skilled in the art that various methods may be used to find the impulse response of a digital signal from its z-transform, such as the long division of the polynomial of z in the numerator of equation 16 by the polynomial of z in the denominator of equation 16. See J. G. Proakis and D. G. Manolakis, Introduction to Digital Signal Processing, McGraw-Hill, 1988. In block 128 the composite forward channel g_forward(n) is calculated by simply performing the convolution of f_forward(n) and c_forward(n).

[0074] To obtain the backward impulse response or backward prefilter coefficients f_backward(n) of the backward channel estimate, the steps denoted by blocks 124, 125, 126, 127 and 128 are repeated using c_backward(n) defined in equation 10 instead of c_forward(n). The corresponding steps for computing f_backward(n) are re-labeled and denoted as blocks 129, 130, 131, 132 and 133, respectively, in FIG. 6. For example, similar to block 124, in block 129 the roots of the z-transform of the backward channel estimate c_backward(n) are computed by: $\begin{array}{cc}{C}_{\mathrm{backward}}\left(z\right)=\sum _{k=0}^{L-1}{c}_{\mathrm{backward}}\left(n\right)z^{-n}.& \left(17\right)\end{array}$

[0075] The signals resulting from block 128 and block 133 form part of the output of the prefilter coefficient generator 110 in FIG. 3 that is transmitted to the DFSE equalizer 114. The signals resulting from block 127 and block 132 form part of the output of the prefilter coefficient generator 110 in FIG. 3 that is transmitted to the prefilter 113.

[0076] Referring to FIG. 7, another aspect of the present invention is illustrated. It is noted that the roots of equation 17 are simply the reciprocals of the roots of equation 15. Further, only the roots of equation 15, but not those of equation 17, are computed in the process of generating both f_forward(n) and f_backward(n) Since the bulk of the computational complexity in the previous method lies in the blocks 124 and 129, the method illustrated in FIG. 7 effectively reduces the computational complexity of the prefilter coefficient generator 110 by a factor of two. Similar to the previous method, in block 134 the roots of the z-transform C_forward(z) described in equation 15 are computed. The steps in blocks 135, 136, 137 and 138 are equivalent to the steps in blocks 125, 126, 127 and 128, respectively, for determining the forward impulse response f_forward(n) and the composite forward channel g_forward(n).

[0077] Blocks 139, 140, 141 and 142 illustrate the steps for computing the backward impulse response f_backward(n) of the backward prefilter and the composite backward channel g_backward(n) of the backward composite channel. In block 139, the subset Q_inof all the roots in ${\left\{z_n^{\mathrm{forward}}\right\}}_{n=1}^{L-1}$

[0078] which have magnitude less than or equal to one are determined. This step can be accomplished by putting the rest of the roots in ${\left\{z_n^{\mathrm{forward}}\right\}}_{n=1}^{L-1}$

[0079] that are not in the subset Q_outcomputed in block 135. In block 140, the z-transform F_backward(z) of the backward impulse response f_backward(n) of the backward prefilter is computed according to the following formula: $\begin{array}{cc}{F}_{\mathrm{backward}}\left(z\right)=\frac{\prod _{z_i\in Q_{\mathrm{in}}}\left(-z_i^{•}+z\right)}{\prod _{z_i\in Q_{\mathrm{in}}}\left(1-z_{i}z\right)}.& \left(18\right)\end{array}$

[0080] In block 141, the backward impulse response f_backward(n) from the z-transform F_backward(z) described in equation 18 is computed in the same manner as described above with respect to block 127. In block 142, the composite channel g_backward(n) is computed by performing the convolution of f_backward(n) and c_backward(n). The signals resulting from block 142 form part of the output of the prefilter coefficient generator 110 in FIG. 3 that is transmitted to the DFSE equalizer 114. The signals resulting from block 141 form part of the output of the prefilter coefficient generator 110 in FIG. 3 that is transmitted to the prefilter 113. The forward impulse response of the prefilter 113 and the forward composite channel may be computed by finding the roots of the z-transform of the forward channel estimate that are greater than one and using the remaining roots to compute the backward impulse of the prefilter 113 and the backward composite channel.

[0081] Having described the invention in detail and by reference to preferred embodiments thereof, it will be apparent that modifications and variations are possible without departing from the scope of the invention defined in the appended claims.