Abstract:
An apparatus, computer software, and method for data detection in channels suffering from intersymbol interference comprising receiving a signal representative of a binary digit of data, computing a reliability score for that binary digit of data via windowed Chase equalization, and based on the reliability score, causing a signal to be output that the binary digit is a zero or a one.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims priority to and the benefit of the filing of U.S. Provisional Patent Application Ser. No. 60/896,083, entitled “List-Based Detection in Fading Channels with Long Intersymbol Interference”, filed on Mar. 21, 2007, and the specification and claims thereof are incorporated herein by reference. 
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
     Not Applicable. 
     INCORPORATION BY REFERENCE OF MATERIAL SUBMITTED ON A COMPACT DISC 
     Not Applicable. 
     COPYRIGHTED MATERIAL 
     Not Applicable. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention (Technical Field) 
     The present invention relates to methods, software, and apparatuses for improving data channels suffering from intersymbol interference (ISI). 
     2. Description of Related Art 
     Note that the following discussion refers to a number of publications by author(s) and year of publication, and that due to recent publication dates certain publications are not to be considered as prior art vis-à-vis the present invention. Discussion of such publications herein is given for more complete background and is not to be construed as an admission that such publications are prior art for patentability determination purposes. 
     It is well known that maximum likelihood sequence detection (MLSD) is an optimal equalization technique for intersymbol interference (ISI) channels in the sense that it minimizes the sequence error probability for equally likely input data sequences. G. D. Forney. Jr., “Maximum-likelihood sequence estimation of digital sequences in the presence of intersymbol interference,”  IEEE Trans. Inform. Theory,  vol. 18, pp. 363-378, May 1972. However, the number of states in the Viterbi algorithm (VA) while implementing MLSD grows exponentially with ISI length and the number of bits per constellation point. Other equalization techniques such as linear and decision feedback equalizers have also been thoroughly investigated in the literature. Although they provide low complexity approaches, their bit error rate (BER) performance may significantly fall short of MLSD&#39;s performance. J. G. Proakis,  Digital Communications,  4th ed. New York: McGraw-Hill, 2000. 
     In order to design reduced complexity MLSD for long ISI channels, many researchers have focused on channel shortening before using MLSD. For this purpose, both linear and decision feedback equalizers have been used to reduce ISI length before applying the MLSD algorithm. D. D. Falconer and F. R. Magee Jr., “Adaptive channel memory truncation for maximum likelihood sequence estimation”  Bell Syst. Tech. J.,  vol. 52, pp. 1541-1562, November 1973; W. U. Lee and F. S. Hill, “A maximum-likelihood sequence estimator with decision-feedback equalizer,”  IEEE Trans. Commun.,  vol. 25, pp. 971-979, September 1977; and N. Al-Dhahir and J. M. Cioffi, “Efficiently computed reduced-parameter input-aided MMSE equalizers for ML detection: A unified approach,”  IEEE Trans. Inform. Theory,  vol. 42, pp. 903-915, May 1996. However, perfect channel shortening is difficult and the BER performance degrades due to residual filter errors. Other complexity reduction approaches include a reduction in the number of surviving paths in VA, F. L. Vermeulen and M. E. Hellman, “Reduced-state Viterbi decoders for channels with intersymbol interference,”  Proc. IEEE ICC&#39; 1974, Minneapolis, 1974, reduced state sequence estimators for large signal constellation sizes, M. V. Eyuboglu, and S. U. Qureshi, “Reduced-state sequence estimation with set partitioning and decision feedback,”  IEEE Trans. Commun.,  vol. 36, pp. 13-20, January 1988, and delayed decision feedback sequence estimators for long ISI channels, A. Duel-Hallen, and C. Heegard, “Delayed decision-feedback sequence estimation,”  IEEE Trans. Commun.,  vol. 37, pp. 428-436, May 1989. However, none of the above sub-optimum techniques achieves close to MLSD performance without a significant increase in implementation complexity. Hence, for long ISI channels and large symbol alphabets, complexity and BER performance have been a matter of trade-off. 
     Recently, the inventors in H. Vikalo, B. Hassibi, and U. Mitra, “Sphere-constrained ML detection for frequency-selective channels,”  IEEE Trans. Commun.,  vol. 54, pp. 1179-1183, July 2006, extended the sphere decoder (SD) algorithm of U. Fincke and M. Pohst, “Improved methods for calculating vectors of short length in a lattice, including a complexity analysis,”  Math Comput.,  vol. 44, pp. 463-471, April 1985; R. Kannan, “Improved algorithms for integer programming and related lattice problems,”  Proc. ACM Symp. Theory of Comput.&#39;,  1983; and E. Viterbo and J. Boutros, “A universal lattice code decoder for fading channels,”  IEEE Trans. Inform. Theory,  vol. 45, pp. 1639-1642, July 1999, for frequency selective channels. The resulting algorithm is a hybrid of VA and SD. From the results on SD described in J. Jalden and B. Ottersten, “On the complexity of sphere decoding in digital communications,”  IEEE Trans. Signal Processing,  vol. 53, pp. 1474-1484, April 2005, it can be seen that the complexity of this algorithm is exponential in block length, and so this algorithm is suitable only for short data lengths. In S. Ohno and G. B. Giannakis, “ML sequence estimation for long ISI channels with controllable complexity,”  Proc. IEEE ICC&#39; 2004, Paris, 2004, a method called distributed zero padding (D-ZP) is shown to achieve a BER performance comparable to maximum likelihood (ML) detection for binary signaling. However, regular insertion of zeros during transmission compromises its effective data rate. A fast MLSD method that provides significantly low complexity at high signal-to-noise ratio (SNR) over vector ISI channels has also been recently described in J. Luo, “Fast maximum likelihood sequence detection over vector intersymbol interference channels,”  Proc. IEEE ICASSP&#39; 2007, Honolulu, 2007. 
     Existing methods of dealing with ISI do not offer near-optimal performance without significant complexity. The present invention, a list based data detection method, apparatus, and software for long intersymbol interference channels, is able to guarantee a specified level of near-optimal performance with low complexity. The invention first extracts bit reliabilities using a low complexity equalizer and then uses these reliabilities to generate lists of possible data vectors before making final bit decisions. The invention can ensure a specific bit error rate performance with respect to a maximum likelihood sequence detector. 
     List based techniques have also been considered by other researchers in various contexts. For example, a list-type generalization of the VA is proposed in T. Hashimoto, “A list-type reduced-constraint generalization of the Viterbi algorithm,”  IEEE Trans. Inform. Theory,  vol. 33, pp. 866-876, November 1987, where a number of survivors is selected from lists of candidates at each decoding step of the VA. In C. Kuhn and J. Hagenauer, “8-PSK turbo equalization with the list-sequential (LISS) algorithm,”  Proc. IEEE ISIT&#39; 2004, Chicago, 2004, a list-sequential equalizer, based on a modified stack algorithm, is discussed. This algorithm operates in the turbo equalization framework, and uses the information fed back from the channel decoder. However, the present invention focuses on an equalization algorithm without involving any channel decoder, and includes the following additional contributions. The invention uses a Chase-type algorithm, D. Chase, “A class of algorithms for decoding block codes with channel measurement information,”  IEEE Trans. Inform. Theory,  vol. 18, pp. 170-182, January 1972, for equalization of ISI channels. In earlier work, the Chase algorithm has been used to explore the soft decision decoding of block and turbo product codes. R. M. Pyndiah, “Near-optimum decoding of product codes: block turbo codes,”  IEEE Trans. Commun.,  vol. 46, pp. 1003-1010, August 1998; and X. Wu, H. R. Sadjadpour, and Z. Tian, “A new adaptive two-stage maximum-likelihood decoding algorithm for linear block codes,”  IEEE Trans. Commun.,  vol. 53, pp. 909-913, June 2005. It has also been used for multisymbol differential detection, W. Xiaofu and S. Songgeng, “Low complexity multisymbol differential detection of MDPSK over flat correlated Rayleigh fading channels,”  IEE Electronics Lett.,  vol. 34, pp. 2008-2009, October 1998, detection over multiple input multiple output channels, D. Waters and J. R. Barry, “The Chase family of detection algorithms for multiple-input multiple-output channels,”  Proc. IEEE GLOBECOM&#39; 2004, Dallas, 2004, and for multiuser detection in spread spectrum systems, Z. Qin and K. C. Teh, “Iterative reduced-complexity multiuser detection based on Chase decoding for synchronous turbo-coded CDMA system,”  IEEE J. Select. Areas Commun.,  vol. 24, pp. 200-208, January 2006. A direct application of the Chase algorithm, however, generates many test patterns, thereby increasing the complexity significantly. The invention uses the Chase method with a windowed technique resulting in significantly lower complexity. The invention also employs a threshold based list generation approach for implementing Chase. Finally, near-ML performance is obtained with significantly low complexity. 
     BRIEF SUMMARY OF THE INVENTION 
     The present invention is of an apparatus, computer software, and method for data detection in channels suffering from intersymbol interference, comprising: receiving a signal representative of a binary digit of data; computing a reliability score for that binary digit of data via windowed Chase equalization; and based on the reliability score, causing a signal to be output that the binary digit is a zero or a one. In the preferred embodiment, computing comprises employing a linear minimum mean squared error as a first stage of the windowed Chase equalization, more preferably also employing a windowed Chase algorithm as a second stage of the windowed Chase equalization, and most preferably wherein the first stage does not have to complete before initiation of the second stage. A decision feedback equalizer is employed as a first stage of the windowed Chase equalization, more preferably also employing a windowed Chase algorithm as a second stage of the windowed Chase equalization, and most preferably wherein the first stage does not have to complete before initiation of the second stage. 
     Objects, advantages and novel features, and further scope of applicability of the present invention will be set forth in part in the detailed description to follow, taken in conjunction with the accompanying drawings, and in part will become apparent to those skilled in the art upon examination of the following, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
       The accompanying drawings, which are incorporated into and form a part of the specification, illustrate one or more embodiments of the present invention and, together with the description, serve to explain the principles of the invention. The drawings are only for the purpose of illustrating one or more preferred embodiments of the invention and are not to be construed as limiting the invention. In the drawings: 
         FIG. 1  is a block diagram of the windowed Chase equalizer (WCE) apparatus, software, and method of the present invention; 
         FIG. 2  is a graph showing effects of MLSD-MF BER ratio η on percentage increase in list size; 
         FIG. 3  is a graph showing effects of threshold V th  on BER for channel C 1  with BPSK modulation; 
         FIG. 4  is a graph showing effects of threshold V th  on BER for channel C 2  with QPSK modulation; 
         FIG. 5  is a graph showing BER performance of WCE for channel C 1  with BPSK modulation; 
         FIG. 6  is a graph showing BER performance of WCE for channel C 2  with QPSK modulation; 
         FIG. 7  is a graph showing BER performance of WCE for channel C 3  with QPSK modulation; 
         FIG. 8  is a graph showing Effects of ε on the average list size per detected symbol for channel C 1 ; 
         FIG. 9  is a graph showing BER performance of WCE for channel C 1  (BPSK) with channel estimation; and 
         FIG. 10  is a graph showing effects of channel estimation error on the BER performance of WCE and MLSD at E b /N 0 =8.0 dB. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention is of a method (and concomitant software and apparatus) for obtaining near-optimal data detection performance in channels with long ISI. By combining a low complexity equalizer with a windowed list search, near-optimal performance is obtained with much lower complexity and delay than with a conventional Viterbi algorithm. 
     The present application will use the following notation standards in the specification and claims: Bold upper case (lower case) letters denote matrices (vectors). The notations (·) T , (·) H , (·) * , E[·], P[·], Re{·} and Im{·} denote transpose, Hermitian, conjugation, expectation, probability, real and imaginary parts respectively. A c  is the complement of A, ∥·∥ is the Euclidean norm, and 
               (         m           k         )               
denotes m!/[(m−k)!k!].
 
     A discrete-time complex baseband system is considered. The k-th received sample y k  is given by 
                     y   k     =         ∑     i   =   0       L   -   1       ⁢           ⁢       h   i     ⁢     x     k   -   i           +     n   k               (   1   )               
where L is the ISI length, h i  is the i-th channel coefficient, and n k  denotes complex additive white Gaussian noise (AWGN) with zero mean and variance σ 2 . The i-th complex M-ary symbol x i  is obtained from a symbol mapper as x i =F(d i ), where d i =[d im , d im+1 , . . . , d (i+1)m−1 ] T  denotes a group of information bits, and m=log 2 M is the number of bits per constellation point. Consider both fixed ISI channel and randomly varying complex Gaussian ISI channels where the coefficients change from one data packet to the next.
 
     Considering a received signal vector of length N samples, one can rewrite (1) in vector form as
 
 y   k   =X   k   h+n   k    (2)
 
where y k =[y k , . . . , y k−N+1 ] T , n k =[n k , . . . , n k−N+1 ] T , h=[h 0 , . . . , h L−1 ] T , and X k  is an N×L data matrix whose i-th row is given by [x k−i , x k−i−1 , . . . , x k−i−L+1 ] for 0≦i≦N−1. If N p  denotes the total number of transmitted symbols in a data packet then setting k=N p +L−2 and N=N p +L−1 makes the vector y k  cover the entire data packet.
 
     It is well known that MLSD minimizes the metric ∥y N     p     +L−2 −X N     p     +L−2 h∥ 2  and results in a tree search with M N     p    paths. An efficient approach is to use VA with M L−1  states, which is too complex for long ISI channels and large symbol alphabets. 
     Next is described the windowed Chase equalization (WCE) that will eventually lead to the strategy of the invention to ensure a specified BER performance with respect to MLSD. The WCE belongs to the tree search (rather than the trellis search) category of MLSD with three modifications. 
     First, many of the less likely paths in tree search are eliminated by using a sub-optimum low complexity equalizer. Second, the exponential complexity increase in data length is overcome by using a windowed search instead of a one-shot full search over the entire data length. This approach has been exploited in the Pseudo-ML algorithm presented in H. R. Sadjadpour and C. L. Weber, “Pseudo-maximum-likelihood data estimation algorithm and its application over band-limited channels,” IEEE Trans. Commun., vol. 49, pp. 120-129, January 2001. Finally, the search is at the bit level rather than at the symbol level. 
     The proposed WCE is a two stage algorithm consisting of a linear minimum mean squared error (MMSE) equalizer as the first stage followed by the Chase algorithm. Other equalizers, such as the decision feedback equalizer (DFE), can also be used as the first stage. The second stage does not have to wait for completion of the first stage. At time l, the inputs to the MMSE equalizer is the vector y l =[y l , . . . , y l−K+1 ] T , where K is the MMSE filter length. This is shown in  FIG. 1 , which can be implemented in hardware (e.g., application specific integrated circuit, digital signal processor, field programmable gate array, or like hardware) or computer-readable software (including firmware) embodied on a physical medium and operating on hardware. Denoting the MMSE filter coefficient vector as g=[g 0 , . . . , g K−1 ] T , the optimal filter coefficient vector is given by g=R −1 p, where R=E[y l y l   H ], and p=E[x l−L+1   * y l ]. The MMSE output at time l is z l−L+1 =g H y l , which is used to obtain reliability of the m bits d (l−L+1)m , . . . , d (l−L+2)m−1  corresponding to symbol x l−L+1 . So, at time l, reliabilities of all bits up to d (l−L+2)m−1  are available. The reliability of a bit d i  is measured by the log-likelihood ratio, log(P(d i =1|z(l−L+1))/P(d i =0|z(l−L+1))), (l−L+1)m≦i≦(l−L+2)m−1. In the present case case, it is represented by the location of z l−L+1  on the complex signal space with respect to the decision line for the bit. For binary phase-shift keying (BPSK) in AWGN, Re{z l−L+1 } gives the reliability and the imaginary line becomes the decision line. For quadrature phase-shift keying (QPSK) with constellation points (1+j)/√{square root over (2)}, (−1+j)/√{square root over (2)}, (−1−j)/√{square root over (2)}, (1−j)/√{square root over (2)} representing bit pairs ( 0 , 0 ), ( 0 , 1 ), ( 1 , 1 ), and ( 1 , 0 ) respectively, Im{z l−L+1 } and Re{z l−L+1 } give the reliabilities of the first and the second bit respectively. For other signal constellations, the bit reliability expression can take different forms. R. D. Maddock and A. H. Banihashemi, “Reliability-based coded modulation with low-density parity-check codes,” IEEE Trans. Commun., vol. 54, pp. 403-406, March 2006. By using bit reliabilities, i.e., by using soft information from the MMSE filter output, the invention is able to improve the detector&#39;s performance significantly. 
     Once the reliabilities of all bits up to d (l−L+2)m−1  are available, the second stage, i.e., the Chase algorithm begins. At time l, a time window of length mW bits is considered over bits d (l−2L+3)m−1 , . . . , d (l−2L−W+3)m . Let Γ be the set of all bits in the window whose reliability magnitudes are below a certain threshold V th  and let γ be the cardinality of Γ. The choice of V th  will be discussed next. If any of the bits forming symbol x l−2L−W+3  is in Γ, then the Chase algorithm generates a list of 2 γ  candidate test vectors, where the k-th candidate vector is a hypothetical sequence of mW bits {circumflex over (d)} (k) =[{circumflex over (d)} (l−2L+3)m−1   (k) , . . . , {circumflex over (d)} (l−2L−W+3)m   (k) ] T . The first candidate vector is obtained by taking hard decisions of reliability values of mW bits. The subsequent hypothetical sequences (candidates in the list) are obtained by varying the bits in Γ, while keeping the other bits same as in the first candidate vector. Note that if none of the bits in x l−2L−W+3  is in Γ then the list is restricted to only the first candidate vector. Let S denote the list size. When γ is large, a performance complexity tradeoff can be obtained by considering the most important error patterns in the Chase algorithm so that S&lt;2 γ . For each test vector {circumflex over (d)} (k) , the hypothetical symbol vector {circumflex over (x)} (k) =[{circumflex over (x)} l−2L+2   (k) , . . . , {circumflex over (x)} l−2L−W+3   (k) ] T  is created using the symbol mapper. Then a final decision on the (l−2L−W+3)-th symbol is {circumflex over (x)} l−2L−W+3 ={circumflex over (x)} l−2L−W+3   (η) , where 
                     η   =         arg   ⁢           ⁢   max     k     ⁢     p   ⁡     (         y   1     |       x   ^       l   -   L   +   1         ,   …   ⁢           ,       x   ^       l   -     2   ⁢   L     +   3       ,       x   ^       (   k   )       ,       x   ^       l   -     2   ⁢   L     -   w   +   2       ,   …   ⁢           ,       x   ^       l   -     3   ⁢   L     -   W   +   4         )           ,           (   3   )               
y l  is a vector of length N=W+L−1 and p(·) denotes probability density function (pdf). The symbols {circumflex over (x)} l−L+1 , . . . , {circumflex over (x)} l−2L+3  are obtained by taking hard decisions of the reliability values of the MMSE filter output. The symbols {circumflex over (x)} l−2L−W+2 , . . . , {circumflex over (x)} l−3L−W+4  are already detected symbols. It is clear that, due to AWGN, the above pdf maximization becomes minimization of ∥y l −{circumflex over (X)} l   (k) h∥ 2  over all S hypotheses, where {circumflex over (X)} l   (k)  is a matrix as defined in (2) with elements {circumflex over (x)} l−L+1 , . . . , {circumflex over (x)} l−2L+3 , {circumflex over (x)} l−2L+2   (k) , . . . , {circumflex over (x)} l−2L−W+3   (k) , {circumflex over (x)} l−2L−W+2 , . . . , {circumflex over (x)} l−3L−W+4 . Thus a decision delay of (W+2L−3) symbols occurs. In our numerical study, W=L is used resulting in a decision delay of 3L−3 symbols. Note that in VA, a typical decision delay of about 4L to 5L is used based on experience. G. L. Stuber, Principles of Mobile Communication, Kluwer Academic Publishers, 1996.
 
     Next consider BPSK or QPSK modulation. The probability of an error e in bit d i  can be written as 
                     P   b     =         ∑   1       k   =   0       ⁢       P   ⁡     (       e   |     d   i       =   k     )       ⁢     P   ⁡     (       d   i     =   k     )                   (   4   )               
Assuming bits  0  and  1  to be equally likely and P(e|d i =K) to be same for k=0 and 1, we can write P b =P(e|d i =0). Let V be the random variable denoting the reliability of bit d i  at the output of the MMSE filter. Let E[V|d i =0]=μ 0  and E[V|d i =1]=μ 1 . Without loss in generally, assume μ 1 &gt;μ 0 . Let us define μ=(μ 0 +μ 1 )/2, so μ forms the decision boundary and μ 0 =−μ 1 , which implies μ=0. Then P b  can be written as
 
 P   b   =P ( e|d   i =0,  V≧V   th ) P ( V≧V   th   |d   i =0)
 
+ P ( e|d   i =0,  V&lt;V   th ) P ( V&lt;V   th   |d   i =0)   (5)
 
     Denote P(V≧V th |d i =0) as P δ . If V≧V th  the algorithm makes a hard decision on the reliability value and this decision is final. Therefore, P(e|d i =0, V≧V th )=1, which implies that the first term on the right hand side of (5) is 
               P   δ     =       ∫     V   th     ∞     ⁢       p   ⁡     (       v   |     d   i       =   0     )       ⁢       ⅆ   v     .               
Approximate p(v|d i =0) to be Gaussian, H. V. Poor and S. Verdu, “Probability of error in MMSE multiuser detection,” IEEE Trans. Inform. Theory, vol. 43, pp. 858-871, May 1997; and K. R. Narayanan, X. Wang and G. Yue “Estimating the PDF of the SIC-MMSE equalizer output and its applications in designing LDPC codes with turbo equalization,” IEEE Trans. Wireless Commun., vol. 4, pp. 278-287, January 2005, with variance σ 0   2 . One then obtains
 
                 P   δ     =     Q   ⁡     (         V   th     +          μ   0              σ   0       )         ,         
where Q(·) is the Gaussian tail probability. Evaluation of the second term of (5) is difficult. However, one is mostly interested near the ML region. Hence one preferably proceeds as follows.
 
     For a large window size, if a tree search is performed over all possible bit sequences for bits in Γ and Γ c , then ML BER performance, P ML , i.e., P(e|d i =0)□P ML , is obtained. This is also true for asymptotically large V th , i.e., when V th →∞, one can write
 
 P ( e|d   i =0,  V&lt;V   th )□ P   ML    (6)
 
     Even for moderate V th  so that P δ ≦P ML , the probability that an erroneous bit is picked for Γ c  is less than P ML . Thus although an exhaustive search over all bits in Γ and Γ c  is not done, the use of good quality fixed bits in Γ c  during search over bits in Γ makes (6) a good approximation. One can thus write from (5)
 
 P   b   ≈P   δ +(1− P   δ ) P   ML    (7)
 
     Note that when V th  is large, the algorithm performs a tree search for almost all bits and hence P b ≈P ML . This agrees with (7) since P δ →0 as V th  gets larger. When V th  is very small so that P δ &gt;&gt;P ML , (6) becomes less applicable since tree search is almost absent and P b ≈P δ  due to MMSE. One is typically not interested in this region. Numerical results below demonstrate that (7) provides accurate results ( FIG. 1 ). 
     Equation (7) provides one a rule to select V th . Suppose, one wants P b  of WCE to be within a fraction ε of P ML . From (7) one gets
 
(1−ε) P   ML   =P   δ +(1− P   δ ) P   ML ,   (8)
 
and hence
 
                     P   δ     =       ɛ   ⁢           ⁢     P   ML         1   -     P   ML                 (   9   )               
resulting in
 
                     V   th     =       -          μ   0            +       σ   0     ⁢       Q     -   1       ⁡     (       ɛ   ⁢           ⁢     P   ML         1   -     P   ML         )                   (   10   )               
No existing equalizer can provide such a strategy to obtain P b  within a desired fraction of P ML . Note that for P ML &lt;&lt;1, one can approximately replace 1−P ML  by 1.
 
     In computing V th  using (10), three parameters, μ 0 , σ 0  and P ML  are needed. The parameters μ 0  and σ 0  are obtained from the MMSE filter coefficients. K. R. Narayanan, supra. For example, μ i , i=0,1, can be obtained as Re{g H p/x l−L+1   * }, depending on the corresponding data bit being a 0 or a 1 respectively. For BPSK, σ 0   2 =μ 0 −μ 0   2  and for QPSK σ 0   2 =μ 0 /√{square root over (2)}−μ 0   2 . Finding P ML  is not straightforward. One can use P ML  values obtained through numerical simulations for studying the behavior of WCE. However, in a practical use of the algorithm, one has to find P ML  on-line. This can be taken care of by using tight upper or lower bounds. G. D. Forney. Jr., “Lower bounds on error probability in the presence of large intersymbol interference,”  IEEE Trans. Commun.,  vol. 20, pp. 76-77, February 1972; S. Verdu, “Maximum likelihood sequence detection for intersymbol interference channels: a new upper bound on error probability,”  IEEE Trans. Inform. Theory,  vol. 33, pp. 62-68, January 1987; and W. H. Sheen and G. L. Stuber, “MLSE equalization and decoding for multipath-fading channels,”  IEEE Trans. Commun.,  vol. 39, pp. 1455-1464, October 1991. In the present invention, it is preferred to use a matched filter (MF) bound given by
 
 P   MF   =Q (√{square root over (2γ)})   (11)
 
for fixed ISI channel, where γ is the average received SNR. J. E. Mazo, “Exact matched filter bound for two-beam Rayleigh fading,”  IEEE Trans. Commun.,  vol. 39, pp. 1027-1030, July 1991. In practice, a receiver may or may not achieve the MF bound. However, one does not need to know the exact value of P ML  if P ML  is used.
 
     Suppose one changes the design requirement slightly so that one now wants P b  of WCE to be worse than P ML  at most by a fraction ε of P MF  instead of P ML . From (8), one gets
 
 P   ML   +εP   MF   =P   δ +(1− P   δ ) P   ML ,   (12)
 
which gives
 
                     P   δ     =       ɛ   ⁢           ⁢     P   MF         1   -     P   ML                 (   13   )               
Since in the region of interest, P ML &lt;&lt;1, we get P δ ≈εP MF /(1−P MF )≈εP MF . Hence, one can choose V th  as
 
                     V   th     ≈       -          μ   0            +       σ   0     ⁢       Q     -   1       ⁡     (       ɛ   ⁢           ⁢     P   MF         1   -     P   MF         )           ≈       -          μ   0            +       σ   0     ⁢       Q     -   1       ⁡     (     ɛ   ⁢           ⁢     P   MF       )                   (   14   )               
There is a penalty on the computational side due to this simplification and will be discussed in the complexity analysis later.
 
     When the ISI changes from packet to packet, the error probability P b  is to be averaged over random channel realizations to get an average error probability  P   b . For large V th  and large window size, the ML performance  P   ML  is obtained, where  P   ML  now represents average over the fading channels. Hence the average error probability  P   b  is obtained from (7) asymptotically as
 
   P     b   □  P     δ +(1−   P     δ )   P     ML    (15)
 
where
 
                         P   _     ⁢             δ     =     E   ⁡     [     Q   ⁡     (         V   th     +          μ   0              σ   0       )       ]               (   16   )                 FIG. 4  shows that (15) provides very good results where  P   ML  is obtained through simulations. Instead of  P   ML , one can use the MF bound  P   MF  for the fading channels and obtain an approximate lower bound as
 
   P     b   ≧  P     δ +(1−   P     67 )   P     MF    (17)
 
where  P   MF  is the matched filter bound which is obtained by averaging (11) over all possible channel realizations. For BPSK and QPSK, closed form expressions for  P   MF  is derived in F. Ling, “Matched filter-bound for time-discrete multipath Rayleigh fading channels,”  IEEE Trans. Commun.,  vol. 43, pp. 710-713, March 1995. This can also be obtained from maximal ratio combiner (MRC) for independent fading paths, M. K. Simon and M. S. Alouini,  Digital Communication over fading channels,  John Wiley &amp; Sons, Inc., 2000, by calculating the symbol error probability given by
 
                     P     s   ,   MRC       =       1   π     ⁢       ∫   0         (     M   -   1     )     ⁢   π     M       ⁢       ∏     l   =   0       L   -   1       ⁢           ⁢         (     1   +         γ   l     ⁢       sin   2     ⁡     (     π   M     )             sin   2     ⁢   θ         )       -   1       ⁢     ⅆ           ⁢   θ                     (   18   )               
where γ l =α l mE b /N 0 , E b  is the average bit energy, N 0  is noise power spectral density and α l  is the average power for the l-th channel coefficient. The bit error probability for MRC can then obtained by P b,MRC =1−(1−P s,MRC ) 1/m . For Gray codes, P b,MRC ≈P s,MRC /m.
 
     There are K/m complex multiplications per bit and (K−1)/m additions per bit in implementing the MMSE stage. The complexity of the Chase stage depends on the list size. Assuming independent bit errors, the average list size  S  in a window can be approximated as 
                       ∑   m       k   =   1       ⁢         ∑     m   ⁡     (     W   -   1     )           i   =   0       ⁢       (         m           k         )     ⁢     (           m   ⁡     (     W   -   1     )               i         )     ⁢     2     k   +   i       ⁢         P   Γ     k   +   i       ⁡     (     1   -     P   Γ       )           m   ⁢           ⁢   W     -   k   -   i                   (   19   )               
This can be simplified as
 
                       S   _     =         (     1   +     P   Γ       )       m   ⁢           ⁢   W       ⁢     (     1   -       (       1   -     P   Γ         1   +     P   Γ         )     m       )         ,           (   20   )               
where P Γ  is the probability that a bit belongs to Γ. It is given by
 
 P   Γ   =Q ((|μ 0   |−V   th )/σ 0 )− P   δ   (21)
 
which becomes
 
                     P   Γ     =       Q   ⁡     (         2   ⁢          μ   0              σ   0       -       Q     -   1       ⁡     (       ɛ   ⁢           ⁢     P   ML         1   -     P   ML         )         )       -       ɛ   ⁢           ⁢     P   ML         1   -     P   ML                   (   22   )                         ⁢           ⁢           ⁢             ⁢     =       Q   ⁡     (         2   ⁢          μ   0              σ   0       -       Q     -   1       ⁡     (       ɛ   ⁢           ⁢   η   ⁢           ⁢     P   MF         1   -     η   ⁢           ⁢     P   MF           )         )       -       ɛ   ⁢           ⁢   η   ⁢           ⁢     P   MF         1   -     η   ⁢           ⁢     P   MF                       (   23   )               
where P ML =ηP MF , η≧1, and we call η the MLSD-MF BER ratio. Using (20) and (22) one can find out the average list size for any given deviation ε from ML BER.
 
     When P MF  is used instead of P ML  to calculate V th  as in (14), the average list size becomes 
                           S   _     ⁢             MF     =         (     1   +     P     Γ   ,   MF         )       m   ⁢           ⁢   W       ⁢     (     1   -       (       1   -     P     Γ   ,   MF           1   +     P     Γ   ,   MF           )     m       )         ,           (   24   )               where                             P     Γ   ,   MF       =       Q   ⁡     (         2   ⁢          μ   0              σ   0       -       Q     -   1       ⁡     (       ɛ   ⁢           ⁢     P   MF         1   -     P   MF         )         )       -       ɛ   ⁢           ⁢     P   MF         1   -     P   MF                   (   25   )               
The fractional increase in average list size due to this simplification is the MF use penalty, (  S   MF −  S )/  S , given by
 
                         (       1   +     P     Γ   ,   MF           1   +     P   Γ         )       m   ⁢           ⁢   W       ⁢     (     1   -       (       1   -     P     Γ   ,   MF           1   +     P   MF         )     m       )     ⁢       (     1   -       (       1   -     P   Γ         1   +     P   Γ         )     m       )       -   1         -   1           (   26   )               
This penalty (in percentage) is shown in  FIG. 2  for a 7-tap fading channel with equal power coefficients (channel C 2  described in section VI) using QPSK modulation and ε=0.05. Consider P MF =0.015 and 2.1×10 −6 , representing low and high SNR cases respectively. The P ML  values are hypothetically calculated using P ML =ηP MF  for various values of η to see how a mismatch between P ML  and P MF  affects complexity in terms of  S . It is clear from the figure that at high SNR, even η=10 increases complexity by less than 4%. At low SNR, complexity can increase as high as 25% for η=10, mostly due to ignoring the 1−P ML  factor in (13). Also note that for this hypothetical case, P ML =0.15, which is too pessimistic for practical applications. For fading channels, the average list size  S  should be computed by averaging over random channel realizations.
 
     Assuming all x k h i  are pre-computed and stored, the average number of complex multiplications, additions and min operations are  S (W+L−1)/m,  S (W(L+1)+L 2 −2)/m and 1/m respectively. In contrast, the MLSD requires M L /m multiplications, LM L /m additions and M L−1 /m min operations. As an example, consider QPSK modulation with W=L=7, and SNR=12 dB. Let ε be 0.05 so that one gets a BER of 1.10×10 −3  instead of P ML =1.05×10 −3  of MLSD ( FIG. 7 ). From simulations, one obtains by averaging over random channels,  S =45 and thus the average number of multiplications is about 308 per bit for WCE. In contrast, the number of multiplications for MLSD is about 8192. The complexity reduction benefits will be more for higher values of L. For example, for L=11 , we get from simulations,  S =928 and the number of multiplications becomes about 9.8×10 3 , while that of MLSD is about 2.1×10 6 . 
     Both BPSK and QPSK modulations are considered. For BPSK, the fixed ISI Proakis A[2] channel with length L=11 is taken. The impulse response of this channel is given by [0.04−0.05 0.07−0.21 −0.5 0.72 0.36 0 0.21.0.03 0.07]. Call this the C 1  channel. For QPSK modulation, two block fading channels C 2  and C 3  with ISI length L=7 are considered. The channel C 2  is a complex Gaussian channel with zero mean and identical power coefficients. The third channel C 3  is also complex Gaussian with an exponential decay power profile. Data packets have N p =256 symbols, K=31 and W=L are chosen for WCE. The MLSD simulation results are obtained by using VA over the whole data packet. 
       FIG. 3  shows the effect of threshold level on the BER performance for channel C 1  with BPSK. Note that when V th =0, the BER performance of WCE is same as the MMSE equalizer while P b ≈P ML  for large V th . The figure shows that the analysis (7) agrees well with simulation. A similar study is shown for QPSK modulation in  FIG. 4 . Also note that the analysis results in  FIG. 4  are actually semi-analytical in nature since  P   δ  and  P   ML  values used in (15) are obtained through simulations. 
       FIGS. 5 ,  6  and  7  show BER performance for channels C 1  (BPSK), C 2  (QPSK) and C 3  (QPSK) respectively. One obtains close to MLSD performance using V th  from (10) and (14), for fixed and block fading channels respectively, with ε=0.05. 
       FIG. 8  shows the effects of ε on the average list size per detected symbol for channel C 1  (BPSK). We observe that for exact ML performance (ε=0) the list size is  S =2048 for 8.0 dB giving P ML =1.91×10 −4 . However, if one relaxes the requirement by 1 percent and target for a BER of 1.93×10 −4  then  S □1.6. This can hugely benefit system design for low complexity yet near-optimal detection in long ISI channels. 
       FIG. 9  shows the BER performance for channel C 1  with BPSK modulation. The channel is estimated using training symbols. Data packets in this case consist of 200 symbols of data and 56 symbols of training. The channel coefficients are estimated using the least squares estimator, S. M. Kay,  Fundamentals of Statistical Signal Processing Estimation Theory,  New Jersey: Prentice Hall Signal Processing Series, 1993, and then the noise variance is estimated using the already estimated channel coefficients. We show two sets of results for the unknown channel. In the first case, only the training symbols are used for channel estimation and this estimate is used for MMSE equalizer coefficient calculation and in WCE detection. In the second case, the training symbols are used for MMSE equalizer coefficient calculations, but once the MMSE equalized detected data are available, the whole detected data packet is used for estimating the channel coefficients again. This new set of estimated channel coefficients is used for WCE computations. The second approach provides BER improvement at the cost of additional computations and delay. Also shown is the effect of channel estimation on MLSD, which uses only the training data for channel estimation. This performance is similar to WCE that uses only the training data for channel estimation. The WCE can provide improved performance using MMSE detected data along with training data, since the MMSE equalizer is a part of WCE anyway. This is an additional benefit of WCE. 
       FIG. 10  shows the effects of channel estimation error on WCE. The estimation error is modeled as a Gaussian random variable, i.e., ĥ i =h i +w i  for i=0, . . . , L−1, where w i  is a Gaussian random variable with zero mean and variance equal to σ w   2 . The x-axis is the estimation error-to-signal ratio (ESR) defined as σ w   2 /E b . D. Gu and C. Leung, “Performance analysis of transmit diversity scheme with imperfect channel estimation,”  Electron. Lett.,  vol. 39, pp. 402-403, February 2003. The BER performance is plotted for E b /N 0  equal to 8.0 dB for channel C 1  with BPSK modulation, where the true ML BER is 1.91×10 −4 . The initial erroneous channel is used to estimate the MMSE filter coefficients. The MMSE equalizer is next used to detect data over the whole packet. The whole detected data is then used to re-estimate the channel and this new channel estimate is used for both WCE and MLSD. The effect of estimation error is negligible at an ESR of −50 dB. However, at higher ESR, the performance degrades significantly. It can be seen that the performance of MLSD with estimation error is similar to that of WCE at low ESR, while degrades at high ESR. For this example, WCE is more robust to channel estimation errors. 
     Although the invention has been described in detail with particular reference to these preferred embodiments, other embodiments can achieve the same results. Variations and modifications of the present invention will be obvious to those skilled in the art and it is intended to cover in the appended claims all such modifications and equivalents. The entire disclosures of all references, applications, patents, and publications cited above are hereby incorporated by reference.