Method for intersymbol interference compensation

[0002] This application claims priority of Provisional Application Ser. No. 60/176162 which was filed on Jan. 14, 2000.

[0003] This invention relates to methods for intersymbol interference compensation in data communications and data storage systems with the objective of improving the reliability of data recovery.

[0004] Intersymbol interference (ISI) is found in many communications and recording systems. In order to reduce the frequency spectrum of a modulated signal, ISI may be introduced deliberately at the modulator. An example of modulation schemes that introduce ISI is Gaussian minimum shift keying (GMSK) described in the article: “GMSK Modulation for Digital Mobile Radio Telephony,” by K. Murota and K. Hirade, IEEE Transactions on Communications, vol. COM-29, pp. 1044-1050, July 1981. Filtering at the transmitter to control the signal spectrum can extend the basic modulation pulse beyond one signaling interval, thus introducing ISI. The communications medium is another potential source of ISI. In digital subscriber line (DSL) systems, which support high-rate data transmissions in addition to voice traffic, the severe line attenuation and delay variation with frequency of the telephone lines have been found to cause significant ISI in the received signal, as described in the book: Understanding Digital Subscriber Line Technology, by T. Starr et al., Prentice Hall, 1999, pp. 183-186. In mobile communications, ISI associated with multipath fading occurs when the direct-path signal combines with the reflected and delayed signals to form a composite signal at the receiver, as described in the book: Mobile Communications Engineering: Theory and Applications, Second Edition, by W. Lee, McGraw-Hill, 1998, pp. 442-445.

[0005] In reading data from a magnetic recording medium, a phenomenon referred to as bit crowding may occur if the bit packing density is high, as described in the book: Electronics Engineers' Handbook, Fourth Edition, by D. Christiansen, McGraw-Hill, 1997, pp. 27.49-27.54. Bit crowding leads to ISI since a read head, which is a transducer configured to provide an output in response to a change in the polarity of the magnetization pattern, has a limited bandwidth. The transducer output is a pulse whose width is inversely proportional to the transducer's bandwidth. When the bit packing density of the recording is sufficiently high, the response pulse will be become wide enough to have non-zero amplitude in the adjacent bit periods, resulting in ISI. There are precursor and postcursor ISI. Precursor ISI is caused by leading undershoots in the transducer response resulting from stray magnetic fields at the edges of the inductive read heads. Postcursor ISI is caused by trailing undershoots in the transducer response.

[0006] Modern high-end disk drive systems employ the partial response maximum likelihood (PRML) technology to achieve better performance. In this scheme a certain amount of ISI is deliberately introduced into the recorded signal in order to reduce constraints on the bandwidth of the electronic circuitry. During data recovery, the ISI is usually removed using a maximum likelihood detection scheme such as the Viterbi algorithm. A popular choice of partial response is the class IV partial response (PR4) characterized by the transfer function 1−D², where D represents a symbol delay, i.e., the current output is equal to the current input minus the input two symbol periods ago.

[0007] The block diagrams of a data communications system and a data storage system presented in FIGS. 1 and 2, respectively, will be used to define the problem to be solved. In FIG. 1, data source 102 provides a data sequence {u_j}, which is advantageously processed by encoder 104 to provide an encoded sequence {v_k}. The data sequence is usually a binary digital stream but it could also have elements taken from an M-ary alphabet consisting of M values, where M is an integer. Likewise, the elements of the encoded sequence could be binary or M-ary. The term “symbol” will be used to refer to a binary or M-ary element taken from an alphabet of a set of predetermined values. For is example, a binary alphabet has two symbols, which may be 0 and 1, while an octal alphabet has eight symbols, which may be −7, −5, −3, −1, 1, 3, 5, and 7. Thus, a data sequence is made up of data symbols and an encoded sequence is made up of encoded symbols. With reference to FIGS. 1 and 2, the indices j and k may be different since the encoded sequence may have a length different from that of the data sequence. For example, if the encoder is a rate 1/2 error-correction encoder, then the encoded sequence is twice as long as the data sequence. Examples where the encoded sequence is the same length as the data sequence include: (i) the encoder is simply a one-to-one mapper such as mapping “0” to “−1” and “1” to “+1”, as in antipodal signaling; and (ii) the encoder is a binary, rate 1/n error-correction encoder followed by a mapping of n bits to a symbol chosen from an alphabet of size 2ⁿ. With reference to FIG. 1, the encoded sequence is supplied to modulator 122, which converts the discrete-time sequence {v_k} into a continuous-time modulated signal. The modulated signal is filtered, up-converted to a higher frequency, and amplified by transmitter 124 for transmission over communications medium 126. The transmitted signal is received by receiver 128, which usually performs the functions of amplification using a low-noise amplifier, down-conversion to a lower frequency, and filtering to reject out-of-band noise. The receiver output is sampled and digitized using analog-to-digital (A/D) converter 130 to provide a digitized signal, which is advantageously processed by matched filter 132. In this exemplary arrangement, matched filter 132 is a digital filter. In implementations where matched filter 132 is an analog filter, the positions of A/D converter 130 and matched filter 132 shown in FIG. 1 are interchanged. Communications channel 120 comprises modulator 122, transmitter 124, communications medium 126, receiver 128, A/D converter 130, and matched filter 132. The channel output sequence {r_k} is the output of matched filter 132. Each element of the channel output sequence is represented by a digital word made up of a number of bits dependent on the implementation. The term “sample” will be used to refer to a quantity that is not taken from an alphabet. Thus, the number of possible values assumed by a sample is not predetermined but dependent in part on the length of the digital word representing the sample. With this convention, r_kis a channel output sample and the channel output sequence {r_k} is a collection of channel output samples arranged chronologically. In general, the channel generates one or more channel output samples r_kin response to an encoded symbol v_kpresented to the channel input. To simplify the discussion, the indices of the encoded sequence {v_k} and the channel output sequence {r_k} are shown in FIG. 1 to be identical to signify that there is one channel output sample for each channel input symbol. The use of the same indices for these two sequences in FIG. 1 should be considered exemplary rather than restrictive. The channel output sequence is supplied to data estimator 106 to recover the data sequence. The output of data estimator 106 is an estimated data sequence {û_j}, which is composed of estimated data symbols. The estimated data sequence is supplied to data sink 108.

[0008] FIG. 2, which is a block diagram of a data storage system, shows the encoded sequence being supplied to modulator 222, which converts the discrete-time sequence {v_k} into a continuous-time modulated signal. The modulated signal is supplied to data recorder 224, which writes the modulated signal onto recording medium 226, which can represent a magnetic tape or disk. Data reader 228 reads recording medium 226 to provide an analog signal, which is sampled and digitized using A/D converter 230. Recording channel 220 comprises modulator 222, data recorder 224, recording medium 226, data reader 228, and A/D converter 230.

[0009] FIGS. 1 and 2 use the same reference numerals for data source 102, encoder 104, data estimator 106, and data sink 108 to show the similarities between the data communications and data storage problems to be solved. Such a convention in notation should be considered exemplary rather than restrictive. FIG. 3 shows a block diagram that could represent either a data communications or a data storage system. Channel 300 could be communications channel 120 or recording channel 220.

[0010] The intersymbol interference found in a channel output sample is usually made up of precursor and postcursor portions. The precursor ISI is defined as the interference on the current sample from the future symbols while postcursor ISI is the interference from the past symbols. The channel output sample for the k'th symbol interval, in response to the application of the encoded sequence {v_k} to the channel input, may be represented as $\begin{array}{cc}{r}_k=\sum _{i=-L_1}^{-1}{h}_i{v}_{k-i}+h_0{v}_k+\sum _{i=1}^{L_2}{h}_i{v}_{k-i}+n_k& \left(1\right)\end{array}$

[0011] where h_i, i=−L₁, . . . ,0,L₂are the coefficients the channel impulse response (CIR) and n_kis a noise term. In general, these quantities are complex, having real and imaginary parts. The quantity h₀is the channel gain on the desired symbol and the quantities h_i, i≠0, are the gains of the ISI components. The term “ISI profile” will be used to mean a set of channel gain coefficients such as {h_i}. The first term on the right-hand side of the above equation is the precursor ISI, which has a span of L₁symbols, the second term is the desired signal, and the third is the postcursor ISI, which has a span of L₂symbols. It can be seen from the above equation that, depending on the CIR and the encoded symbols, the ISI can result in a reduction of the signal amplitude, leading to degradation in the reliability with which data can be recovered. For example, if the CIR parameters are L₁=L₂=1, h₋₁=h₁=0.5, and h₀=1, and the encoded sequence is such that v_k−1=v_k+1=−1, v_k=1, then from equation (1), r_k=n_k, which contains no desired signal component.

[0012] The problem to be solved is to estimate the data sequence {u_j} based on having observed the channel output sequence {r_k}, which contains ISI. I will review the prior art on solving the problem of data recovery in the face of ISI and discuss areas where improvements may be desirable.

[0013] It is well known to those skilled in the art that the optimum estimator, in terms of providing the lowest probability of estimation error in the presence of additive white Gaussian noise (AWGN), is the maximum likelihood sequence estimator (MLSE). The Viterbi algorithm (VA) has been demonstrated to be an efficient implementation of MLSE in the article: “Maximum-Likelihood Sequence Estimation of Digital Sequence in the Presence of Intersymbol Interference,” by G. D. Forney, Jr., IEEE Transactions on Information Theory, vol. IT-18, pp. 363-378, May 1972. In MLSE, the channel is modeled as a linear transversal filter equivalent to a convolutional encoder operating on the data sequence. The MLSE implemented using the Viterbi algorithm, referred to here as the VA-MLSE, has M^L+Lstates, where M is the alphabet size of the symbols v_k, i.e., v_kcan take on one of M values. Therefore, the complexity of the MLSE estimator grows exponentially with the ISI span, L₁+L₂. Even for a moderately small alphabet size of 4, and fairly small ISI span L₁=L₂=2, the number of states needed in the MLSE estimator is 4⁴=256, which is considered a large number of states to implement for a Viterbi algorithm.

[0014] The high complexity of the VA-MLSE has an impact on the power consumption of the circuitry implementing the estimator. Keeping the power consumption to the minimum is critical in some applications, such as hand-held and mobile communications terminals. U.S. Pat. No. 5,644,603, “Maximum-Likelihood Sequence Estimator with Variable Number of States,” issued to A. Ushirokawa on Jul. 1, 1997, discloses a means for estimating the ISI span and selecting from a group of VA-MLSEs of different number of states to match the estimated ISI span. This approach may ease the power consumption but does not reduce the hardware/software complexity.

[0015] The use of MLSE in conjunction with forward-error-correction (FEC) coding has been suggested. For example, U.S. Pat. No. 5,673,291, “Simultaneous Demodulation and Decoding of a Digitally Modulated Radio Signal using Known Symbols,” issued to P. Dent on Sep. 30, 1997 discloses an apparatus for performing demodulation and decoding simultaneously using a VA-MLSE. In this approach, a data sequence to be transmitted is encoded using a block or convolutional code. Symbols known to the receiver are inserted into the encoded sequence and the composite sequence is interleaved. The known symbols are used to aid the decoding for recovery of the data sequence. A drawback of this approach is that the known symbol represent an overhead in the channel, thus reducing the bandwidth efficiency of the system.

[0016] Another example of the use MLSE in conjunction with FEC coding is U.S. Pat. No. 5,844,946, “Soft-Decision Receiver and Decoder for Digital Communication,” issued to T. Nagayasu on Dec. 1, 1998. In the first step, the invention of Nagayasu employs a VA-MLSE to process the received signal to estimate the transmitted symbols. In the second step, a maximum a posteriori (MAP) algorithm is used to calculate the soft-decision reliability values for the estimated symbols. In the last step, the soft-decision values are applied to a Viterbi decoder for the convolutional code. A drawback of this approach is its high complexity, particularly the complexity of the MAP algorithm.

[0017] A technique simpler than the MLSE for processing signals with ISI is linear equalization. The theory of linear equalizers is well known to those skilled in the art, see the article: “Adaptive Equalization,” by S. Qureshi, IEEE Communications Magazine, March 1982, pp. 9-16. One implementation of a linear equalizer employs a transversal filter, also referred to as a tapped-delay line filter, which is made up of delay elements, multipliers, and adders. The output of a transversal filter whose input is the channel output sequence {r_k} may be expressed as $\begin{array}{cc}{q}_k=\sum _{i=-N_1}^{N_2}{w}_i^{*}{r}_{k-i}& \left(2\right)\end{array}$

[0018] where w_i, i=−N₁, . . . ,0, . . . ,N₂, are the tap weights, the asterisk denotes complex conjugation, and the parameters N₁and N₂are the number of precursor and postcursor equalizer taps, respectively, so that the total number of taps or multipliers is N₁+N₂+1. Equation (2) is called a finite convolution in light of the fact that it convolves the finite-duration impulse response of the filter, {w_i}, with the filter input, {r_k}, to provide the filter output q_k. The tap weights are selected according to criterion such as the zero-forcing or minimum mean-square-error (MMSE) criterion. In the zero-forcing algorithm, the tap weights are selected such that the filter output q_kcontains as little ISI as possible. The zero-forcing algorithm leads to a filter with a transfer function, w(z), in z-transform notation, that approximates the inverse of the transfer function of the channel, h(z), i.e., w(z)≈1/h(z). In the MMSE criterion, the tap weights are set to minimize the statistical mean value of the square of the error signal v_k−q_k, where v_kis the k'th transmitted symbol. When the noise power is small compared to the signal power, the MMSE criterion leads to a filter that approximates a zero-forcing filter. In general, the output of a linear equalizer will contain noise and some residual ISI. In fact, in removing ISI, a linear equalizer increases the amount of noise in the signal, a phenomenon known as noise enhancement. This phenomenon can be understood by realizing that the transfer function of a channel that exhibits ISI has smaller amplitudes at some frequencies. In fact, ISI can lead to one or more nulls in the channel transfer function. As pointed out above, the removal of ISI requires that the transfer function of the equalizer to approach the inverse of the transfer function of the channel. At frequencies where the channel transfer function has small amplitudes, the equalizer transfer function will have large gains. The large gains amplify the noise, resulting in a reduction of the signal-to-noise ratio at the output of the equalizer. Another effect of equalization is that the equalized noise spectrum is not flat and hence the noise samples are correlated. This effect is called noise colorization. The noise-enhancement and noise-colorization effects degrade the reliability with which the data sequence can be recovered. As a consequence, a linear equalizer does not provide as reliable an estimate of the data sequence as a MLSE.

[0019] An equalizer with the capability to adjust its tap weights in response to variations in the channel characteristics is called an adaptive equalizer. The theory of adaptive equalizers is well known to those skilled in the art, see the article by S. Qureshi referenced above. A commonly used technique for adaptively adjusting the tap weights is the least mean square (LMS) algorithm. In describing the LMS algorithm it proves convenient to represent the tap weights as a column vector with (N₁+N₂+1) elements: w=(w_−N, . . ,w₀, . . . ,w_N)^T, where the superscript T stands for the transpose operation. Let w_kdenote the tap weight vector at time k. A similar notation is used on the equalizer input, thus r_k=(r_k+N, . . . ,r_k, . . . ,r_k−N)^T. Note that the vector r_khas the elements written in the reverse time order, with the newest channel output sample listed first. With this representation, the equalizer output can be written as

[0020] q_k=w_k^Hr_k  (3)

[0021] where the superscript H represents Hermitian transposition, i.e., complex conjugation and transposition combined. Let d_kbe the desired equalizer output for the k'th symbol interval, then the error signal is

[0022] e_k=d_k−q_k.  (4)

[0023] In the LMS algorithm, the equalizer tap weight vector w_k+1for use in the next symbol interval to process the input signal is computed from the current tap weight vector w_kaccording to

[0024] w_k+1=w_k+μr_ke*_k  (5)

[0025] where μ is an adaptation time constant that controls the rate of adaptation and affects how closely the tap weights can be adjusted to the optimum values in response to variations in the channel characteristics.

[0026] As mentioned earlier, a drawback of a linear equalizer is the noise-enhancement effect. To reduce the amount of noise enhancement, a decision feedback equalizer, also well known to those skilled in the art, can be used instead of a linear equalizer. A decision feedback equalizer has a feedforward section that is identical to the transversal filter, with the channel output sequence {r_k} as its input, and a feedback section with estimates of past symbols, denoted as {{circumflex over (v)}_i}, as its input. The output of a decision feedback equalizer may be written as $\begin{array}{cc}{q}_k=\sum _{i=-N_1}^0{w}_i^{*}{r}_{k-i}+\sum _{i=1}^{N_2}{w}_i^{*}{\hat{v}}_{k-i}& \left(6\right)\end{array}$

[0027] where N₁+1 and N₂are the number of taps in the feedforward and feedback sections, respectively, of the equalizer. A comparison of equations (2) and (6) shows that for the decision feedback equalizer a tap weight with a subscript of 1 or higher multiplies a past symbol decision rather than a channel output sample. If the past symbol decisions are correct, then a decision feedback equalizer will have less noise enhancement than a linear equalizer. If an error occurs in the estimated symbols {{circumflex over (v)}_i}, the error would propagate down the feedback section and affect the output for multiple symbols. This phenomenon is called the error-propagation effect of decision feedback equalizers and can degrade the reliability of the data recovery. This effect is particularly noticeable for systems using forward-error correction coding. Since the decoding delay is usually too big for the decoder output to be used as an input to the feedback section, the symbol decisions supplied to the equalizer must be the less-reliable decisions obtained prior to decoding.

[0028] A number of techniques have been suggested to overcome the error-propagation effects in decision feedback equalizers. U.S. Pat. No. 5,541,956, “Adaptive Equalizer and Adaptive Diversity Equalizer,” issued to K. Ueda on Jul. 30, 1996, discloses a system with a decision feedback adaptive equalizer, a linear equalizer, a comparing circuit, and a selecting circuit. The selecting circuit chooses the equalizer that has the better performance as determined by the comparing circuit, which compares the integrated estimation error value of the decision feedback equalizer with the integrated estimation error value of the linear equalizer. Another technique for dealing with error-propagation effects in decision feedback equalizers is disclosed in U.S. Pat. No. 5,668,833, “Decision-Feedback Type Equalizer,” issued to Y. Kurokami et al. on Sep. 16, 1997. The Kurokami invention provides a means for detecting an abnormal state and a selection circuit used for selecting either equalization signals or symbol decisions for supplying them as input signals to the backward equalizer, in order to reduce propagation or magnification of errors caused by noise. U.S. Pat. No. 5,742,642, “Signal Processing Method and Apparatus for Reducing Equalizer Error,” issued to A. Fertner on Apr. 21, 1998, presents a method for detecting incorrect symbol decisions and correcting the errors to prevent propagation of the error with possible adverse effects on subsequent equalizer decisions. U.S. Pat. No. 5,774,504, “Equalization and Decoding for Digital Communication Channel,” issued to S. R. Huszar et al. on Jun. 30, 1998, discloses a multiple sub-channel decision feedback equalizer/decoder which samples the received signal at an integer multiple of the symbol rate, creating multiple sub-channels. Estimates of each of the sub-channels are updated using a locally best estimate in the equalizer/decoder processing, thereby avoiding delay in updating channel estimates in a rapidly changing channel such as a digital cellular communications channels. The techniques proposed by these patents employ various arrangements to ease the error-propagation effects of decision feedback equalizers at the expense of an increase in complexity of hardware and software. Furthermore, the error-propagation effects are only reduced, not completely eliminated.

[0029] The article: “Delayed Decision-Feedback Sequence Estimation,” by A. Duel-Hallen and C. Heegard, IEEE Transactions on Communications, vol. 37, pp. 428-436, May 1989, proposed the use of decision feedback to reduce the number of states in MLSE. The number of states in a delayed decision feedback sequence estimator is M^L−K, where M is the alphabet size, L is the ISI span of the channel, and K is an integer greater than one. The estimator complexity is still an exponential function of the alphabet size but is reduced by including in the estimator a number of symbols less than the ISI span. The article: “Complex Noncoherent Receivers for GMSK Signals,” by N. Benvenuto et al., IEEE Journal on Selected Areas in Communications, vol. 17, No. 11, pp. 1876-1885, November 1999, describes the use of a delayed decision feedback sequence estimator to demodulate a GMSK signal transmitted over a fading channel. U.S. Pat. No. 5,870,433, “Method of Processing Signals in a Viterbi Decoder According to Delayed Decision Feedback Sequence Estimation (DDFSE) Algorithm,” issued to J. Huber et al. on Feb. 9, 1999, discloses a Viterbi decoder which uses a number of feedback filters to determine branch or path metrics in the trellis diagram, where this number is a function of the number of states in the trellis diagram. In the disclosed arrangement, each of the feedback filters being used is split into two parts. The first part contains the portion of the branch metrics that can be different for each path in the trellis diagram. The second part is only determined once for all paths along the path with the smallest path metrics at the end of the first part of the feedback filters. A drawback of these techniques is that the number decoder states is equal to Mⁿwhere M is the alphabet size and n is an integer smaller than the ISI span. This exponential dependence of the number of decoder states on the alphabet size makes the implementation feasible only for small alphabets or when the parameter n can be chosen to be small.

[0030] The journal articles and U.S. patents on equalization cited above consider systems without the use of error-correction coding. Equalizers, linear or decision feedback, have been used in conjunction with error-correction decoders. U.S. Pat. No. 5,872,817, “Joint Viterbi Decoder and Decision Feedback Equalizer,” issued to L. Wei on Feb. 16, 1999, discloses a system which employs trellis coded modulation and a bank of decision feedback equalizers, one for each state in the decoder. The arrangement is intended to provide symbol decisions to the decision feedback equalizers without excessive delay due to decoder by making use of the tentative decisions associated with each state in the decoding trellis. The equalized signal is used to update the decoder path metrics. The article: “Joint Coding and Decision Feedback Equalization for Broadband Wireless Channels,” by S. Ariyavisitakul and Y. Li, IEEE Journal on Selected Areas in Communications, vol. 16, No. 9, pp. 1670-1678, December 1998, describes an approach for joint convolutional coding and decision feedback equalization based on the use of both soft decisions and delayed tentative decisions. Soft decisions are obtained by passing the real and imaginary parts of the equalizer output through a hyperbolic tangent function. Tentative decisions from the Viterbi decoder are used both to cancel ISI caused by multipath with large delays and to adapt the equalizer. The article states that a tentative decoding delay approximately equal to the constraint length of the code is found to be provide near-optimum performance. U.S. Pat. No. 5,546,430, “Detector for Demodulating a Received Signal and Producing an Information Data Signal with Reduced Intersymbol Interference,” issued to K. Liao et al. on Aug. 13, 1996 discloses a detector for decoded trellis-coded modulation signal corrupted by ISI. The detector comprises a predictor, a feedforward filter, and a trellis coded modulation estimator with a feedback filter that is adjusted with respect to the feedforward filter to form a decision feedback equalizer. A general approach of this group of techniques is to remove the ISI using a decision feedback equalizer, aided by arrangements that help to reduce the error propagation, and then decode the ISI-free signal. Such a cascade of two operations is sub-optimum since it yields less reliable data recovery than a technique, such as MLSE, that simultaneously removes the ISI and decodes the signal.

[0031] The article: “Soft-Output Equalization and TCM for Wireless Personal Communications,” by Y. Chen et al., IEEE Journal on Selected Areas in Communications, vol. 16, No. 9, pp. 1679-1690, December 1998, describes the use of a maximum a posteriori probability (MAP) algorithm to realize soft-output equalization in a concatenated equalization and trellis coded modulation (TCM) decoding system. MAP algorithms compute the conditional probabilities of symbols. The computation involves a nonlinear function and requires knowledge of the noise variance. The article proposes a modified MAP algorithm that does not require knowledge of the noise variance and computes the probabilities in the logarithmic domain to avoid the need to calculate a nonlinear function. U.S. Pat. No. 5,825,832, “Method and Device for the Reception of Signals Affected by Inter-Symbol Interface,” issued to V. Benedetto on Oct. 20, 1998, discloses a receiver for a trellis-code modulated signal comprising two cascaded Viterbi decoders. The first decoder is intended essentially to take into account the memory effects of the channel. The output of the first decoder, which comprises a hard decision on the transmitted symbols as well as a reliability parameter, is supplied, possibly after a de-interleaving action, to the second Viterbi decoder that carries out the actual decision. The use of the first decoder instead of an equalizer to handle ISI reduces the noise enhancement and noise correlation effects. Like the techniques discussed in the preceding paragraph, this set of techniques employs a cascade of ISI equalization and FEC decoding operations and hence yields a sub-optimum performance when compared to a technique that simultaneously removes the ISI and decodes the signal.

[0032] U.S. Pat. No. 5,031,195, “Fully Adaptive Modem Receiver using Whitening Matched Filtering,” issued to P. R. Chevillat et al. on Jul. 9, 1991, discloses a technique for combining equalization and decoding of trellis-coded modulation using a decoder with combined ISI-and-code states. The number of states, which is the product of the number of code states and the number of ISI states, can be too large for practice. The Chevillat invention also discloses a decoder that ignores some ISI so as to reduce the complexity.

[0033] The use of an encoder that includes precoding has been employed to pre-distort the signal in order to compensate for the distortion that the channel is expected to introduce. A commonly used preceding technique is the Tomlinson-Harashima preceding algorithm described in the article: “Combined Equalization and Coding Using Precoding,” by G. D. Forney, Jr. and M. V. Eyuboglu, IEEE Communications Magazine, December 1991. Suppose the alphabet of the data is a set with M points: A={±1,±3, . . . ,(M−1)}. Suppose that u_kis the k'th data symbol taken from the signal set A and that the channel impulse response {h_i} is assumed to have only postcursor ISI and is known at the transmitter. The data symbol u_kis precoded into symbol v_kaccording to the following: $\begin{array}{cc}{v}_k=u_k+2{\mathrm{Mz}}_k-\sum _{j\ge 1}^{}{h}_j{v}_{k-j}& \left(7\right)\end{array}$

[0034] where the value of z_kis selected such that v_klies in the interval (−M,M]. The calculation of z_kand the addition of the term 2Mz_kare called a modulo-2M operation. The last term in the above equation removes the ISI caused by the previous symbols. The channel output sample is

[0035] r_k=u_k+2Mz_k+n_k.  (8)

[0036] It can be seen that the channel output has no ISI. To recover the transmitted symbol u_k, the receiver could first performs a modulo-2M operation to yield {tilde over (r)}_kand then selects from the signal set A the point that is closest to {tilde over (r)}_kas the estimated data symbol û_k.

[0037] The use of preceding raises the average transmit power since the maximum precoded symbol amplitude is M, which can be contrasted with the maximum uncoded data symbol amplitude of M−1. The increase in the average transmit power is shown in the article by Forney and Eyuboglu to be M²/(M²−1), which can be significant if M is small. U.S. Pat. No. 5,488,633, “Intersymbol Interference Channel Coding Scheme,” issued to R. Laroia on Jan. 30, 1996, discloses a technique for combining precoding and trellis coding. An intersymbol interference coder uses a feedback loop to apply a dither sequence to a sequence of input signal points. The dither signal applied to each input signal point is a function of the previous signal points in the sequence. It is stated in the patent specification that the precoding loss is independent of the number of coset partitions used to generate the trellis code, thus the preceding loss is reduced compared to prior art.

[0038] U.S. Pat. No. 5,513,216, “Hybrid Equalizer Arrangement for Use in Data Communications Equipment,” issued to S. Gadot et al. on Apr. 30, 1996 and U.S. Pat. No. 5,604,769, “Hybrid Equalizer Arrangement for Use in Data Communications Equipment,” issued to J. Wang on Feb. 18, 1997 disclose techniques for setting the precoder coefficients based on measurements made at the receiver using a hybrid intersymbol interference decision feedback equalizer (ISI-DFE) and a noise predictive decision feedback equalizer (NP-DFE). In particular, a hybrid DFE is designed so that the I(z) coefficient values dominate over the N(z) coefficient values. In the first patent, a respective Tomlinson precoding scheme in the transmitter uses only the I(z) values. In the second patent, the precoding coefficients are set to be (1+I(z)) (1+N(z))−1.

[0039] In certain applications, it is desirable to transmit a constant-envelope signal. Such applications include transmitters that operate the power amplifier at saturation to achieve higher power efficiency. A constant-envelope signal has the desirable property that it is not degraded by a saturating amplifier. Clearly, precoding cannot be used if a constant-envelope signal is desired. Another drawback of precoding is that the channel impulse response must be known at the transmitter.

[0040] I will now discuss prior art in ISI compensation in magnetic storage systems. The use of an equalizer followed by a Viterbi decoder has been proposed for combating ISI in magnetic storage devices. Here, the Viterbi decoder is used to perform maximum likelihood estimation of the read-back data corrupted by ISI by treating the ISI channel as an encoder. U.S. Pat. No. 5,343,335, “Signal Processing System Having Intersymbol-Interference Canceling Means and Method of Same,” issued to M. Hara on Aug. 30, 1994, discloses a reproduction equalizer comprising a linear equalization means, a nonlinear cancellation means for canceling the intersymbol interference included in the linearly equalized signal, a decoding means for decoding the ISI-free signal. U.S. Pat. No. 5,581,568, “Data Detection Apparatus,” issued to M. Togami on Dec. 3, 1996, discloses an arrangement that uses an integral equalizer for low-frequency-emphasizing-type equalization to provide a larger margin in detection timing and a higher signal-to-noise ratio. The arrangement uses a Viterbi decoder to process the equalized signal. U.S. Pat. No. 5,606,464, “Cancellation of Precursor Intersymbol Interference in Magnetic Recording Channels,” issued to 0. Agazzi et al. on Feb. 25, 1997 discloses a technique in which an adaptive filter is used to provide a replica of the precursor ISI, which is then subtracted from a delayed version of the data signal. The signal provided to the adaptive filter (to provide the precursor ISI replica) may be based on tentative decisions generated by a symbol-by-symbol detector. The equalized signal is then supplied to a Viterbi decoder. The invention does not specifically deal with postcursor ISI. It is mentioned in the specification of the patent that postcursor ISI can be compensated for using a conventional technique known as decision-feedback equalization. U.S. Pat. No. 5,889,823, “Method and Apparatus for Compensation of Linear or Nonlinear Intersymbol Interference and Noise Correlation in Magnetic Recording Channels,” issued to 0. Agazzi et al. on Mar. 30, 1999, discloses an arrangement which employs a Viterbi decoder concatenated with a postprocessor. The Viterbi decoder generates N most likely paths. The postprocessor computes metrics for each of these paths. The path with the best metric is selected as the concatenated decoder output. For simplicity of implementation, the Viterbi decoder neglects some of the components of the channel impulse response that result in linear or nonlinear intersymbol interference. It may also neglect noise correlation. The postprocessor computes metrics taking into account the channel components and noise correlation neglected by the Viterbi decoder. The postprocessor can afford to carry out this more detailed analysis because it restricts its search to a small number of paths. The article: “Viterbi Detection of Class IV Partial Response on a Magnetic Recording Channel,” by R. Wood and D. Petersen, IEEE Transactions on Communications, vol. COM-34, No. 5, pp. 454-461, May 1986, proposes a Viterbi decoder for a partial-response signaling with a discrete-time transfer function of (1−D²), which is referred to as a class IV partial response (PR4) signaling. In the proposed arrangement, a filtered, equalized, and sampled signal is supplied to a Viterbi decoder. U.S. Pat. No. 5,949,831, “Method and Apparatus for Data Detection for PRML Data Channels,” issued to J. Coker et al. on Sep. 7, 1999, discloses an arrangement that supplies a sampled and filtered signal simultaneously to a Viterbi detector to provide a Viterbi output and to a matching delay circuit to provide a delayed signal. The Viterbi output is subtracted from the delayed signal and the resulting signal is applied to a filter to provide an output that is used correct the Viterbi output to generate the final decoder output. In these techniques, the Viterbi algorithm is used to decode the ISI. Joint ISI compensation and FEC decoding is not considered.

[0041] The article: “Trellis Coding for Partial-Response Channels,” by J. Wolf and G. Ungerboeck, IEEE Transactions on Communications, vol. COM-34, No. 8, pp. 765-773, August 1986, proposes the use of trellis coding to provide a coding gain over partial-response signaling with a discrete-time transfer function of (1−D), which is referred to as a dicode signaling. The proposed arrangement employs a binary convolutional encoder, a precoder, and at the receiver, a Viterbi decoder with twice as many states as the convolutional encoder. The extra decoder states are to accommodate the states introduced by the partial-response channel. A drawback of this arrangement is that the extra decoder states for accommodating the ISI increase the complexity of the decoder.

[0042] In summary, the prior art on intersymbol interference compensation using a maximum likelihood sequence estimator (MLSE) yields the best reliability in data recovery. The MLSE, however, is very complex. The number of estimator states required is M^L−1where M is the alphabet size of the channel input symbols and L is the length of the ISI span of the channel. Use of delayed decision feedback sequence estimation reduces the number of estimator states to M^L−K, where K is an integer greater than one. But the complexity is still an exponential function of the ISI span. Furthermore, the estimator now must deal with decision errors in the feedback path. Simpler ISI compensation techniques such as linear equalizers, which have a complexity linearly proportional to the ISI span, have inferior performance due to noise enhancement and noise colorization. Decision feedback equalizers improve performance over linear equalizers by reducing the amount of noise enhancement and noise colorization but suffer from error-propagation effects. Techniques to address the error-propagation lead to added complexity. Precoding, such as the Tomlinson-Harashima algorithm, introduces a loss at the transmitter since precoding increases the maximum amplitude of the transmitted symbols. In addition, precoding cannot be used if a constant-envelope signal is to be transmitted. In systems where FEC coding is used, the general prior art has been to compensate for the ISI and then FEC decode the ISI-free signal. Techniques to generate soft-decision for the FEC decoder tend to be complex.

[0043] The object of the present invention is to provide a method for intersymbol interference compensation that meets these goals: (i) a method that is less complex than maximum likelihood sequence estimation and delayed decision feedback sequence estimation; (ii) a method that performs better than the linear equalizer in terms of less noise enhancement and noise colorization; (iii) a method that is substantially free of the error-propagation effects of decision feedback equalizers; and (iv) a method that supports constant-envelope signaling as well as non-constant envelope signaling.

[0044] According to one embodiment of the present invention, the intersymbol interference compensation (ISIC) method comprises an encoding step performed by an encoder and a data estimating step performed by a data estimator. The encoder performs at least a trellis encoding of a data sequence using a trellis forward-error-correction (FEC) code such as a binary convolutional code or trellis coded modulation (TCM) code to provide a sequence of symbols for use as the input sequence to a channel. The output of the channel, referred to as the channel output sequence, comprises of samples represented as digital words. The data estimator advantageously processes the channel output sequence to provide an estimated data sequence. The data estimator comprises at least a partial equalizer, a template generator, and an ISIC decoder. The channel output sequence is supplied to the partial equalizer to provide a partially equalized sequence that is substantially free of the precursor ISI but contains at least some of the postcursor ISI of the channel output samples. The partially equalized sequence is applied to the ISIC decoder, which performs trellis decoding and ISI compensation simultaneously. The ISIC decoder implements a trellis decoding algorithm that computes branch metrics for a decoding trellis based on a set of templates {circumflex over (q)}(•,•). The templates are computed by taking into account the unequalized postcursor ISI and represent the statistical average values of the partially a equalized samples. The template generator supplies the template {circumflex over (q)}(x,y) in response to a pair of vectors (x,y) provided by the ISIC decoder, where x is the vector of symbols associated with the past branch or branches connected to a current branch in the decoding trellis, and y is the vector of symbols associated with the current branch. The number of states in the ISIC decoder is determined by the trellis code and is independent of the ISI span of the channel. The output of the ISIC decoder is the estimated data sequence for use by the data sink.

[0045] In one embodiment of the present invention, the equalizer tap weights are pre-computed and preloaded into the partial equalizer. The templates are either preloaded into the template generator or computed when needed by the template generator using a set of preloaded coefficients representing the ISI profile at the output of the partial equalizer. This is the preferred embodiment when the ISI profile of the channel is time-invariant and known a priori.

[0046] In another embodiment of the present invention, the equalizer tap weights are adaptive, adjusted in response to variations in the ISI profile of the channel. This is the preferred embodiment when the channel is time varying or when the channel ISI profile is not known a priori with sufficient accuracy. The invention provides for methods for partial equalizer adaptation based on known symbols called training symbols and adaptation based on estimated symbols. The desired output of the partial equalizer is the template {circumflex over (q)}(a,b), where a is a vector of past encoded symbols and b is the current encoded symbol. Subtracting the partial equalizer output from the desired output {circumflex over (q)}(a,b) yields an error signal that is used to adapt the equalizer tap weights. In yet another embodiment of the present invention, an ISI profile estimator is employed to estimate the impulse response of the channel. The estimated ISI profile is used to update the templates.

[0047] In yet another embodiment of the present invention, the channel output sequence is supplied to a double-sided partial equalizer, which leaves some of the precursor and postcursor ISI unequalized. In particular, the double-sided partial equalizer removes only the ISI not accounted for by the double-sided templates ŝ(a,b,c), where a, b, and c represent the past, current, and future encoded symbols. (The term “double-sided template” is chosen to signify that ŝ(•,•,•) depends on both past and future symbols. In contrast, the template {circumflex over (q)}(•,•) does not depend on future symbols and will be referred to as a single-sided template. The term “template” will be used to refer to either {circumflex over (q)}(•,•) or ŝ(•,•,•) when its meaning is clear.) Thus, the desired output of the double-sided partial equalizer is ŝ(a,b,c). The output of the double-sided partial equalizer is supplied to a decision-directed-ISIC (DD-ISIC) decoder. In this embodiment of the present invention, the output of the ISIC decoder is not supplied to the data sink but is supplied instead to the DD-ISIC decoder for use as interim data decisions. The DD-ISIC decoder computes the branch metrics using the templates ŝ(x,y,z) with z representing the vector of symbols associated with the future branch or branches in the decoding trellis as determined by the interim data decisions. The output of the DD-ISIC decoder is the estimated data sequence for use by the data sink.

[0048] In yet another embodiment of the present invention, concatenated coding is employed wherein the data sequence is applied to a cascade of an outer FEC encoder, an interleaver and at least a trellis encoder to provide an encoded sequence for use as the channel input. At the data estimator, the channel output samples are advantageously processed by a partial equalizer and an ISIC decoder to provide a sequence that is further advantageously processed by a cascade of a deinterleaver and an outer FEC decoder to provide an estimated data sequence for use by the data sink.

[0049] In yet another embodiment of the data estimator for use with concatenated coding, the ISIC decoder output is supplied to a cascade of a first deinterleaver, a first outer FEC decoder, an outer FEC encoder, and an interleaver to provide an outer-FEC-decoded sequence for use by a DD-ISIC decoder as interim data decisions. The DD-ISIC decoder output is supplied to a cascade of a second deinterleaver and a second outer FEC decoder to provide an estimated data sequence for the data sink.

[0050] In yet another embodiment of the present invention, an error-detection code is employed to detect errors in the outer-FEC-decoded sequence. A selector is used to select the interim data decisions for use by the DD-ISIC decoder. If errors are detected in the outer-FEC-decoded sequence, the interim data decisions are set to be the output of the ISIC decoder; otherwise, they are set to be the outer-FEC-decoded sequence.

[0051] FIG. 1 is a block diagram of a data communications system;

[0052] FIG. 2 is a block diagram of a data storage system;

[0053] FIG. 3 is a block diagram representing either a data communications system or a data storage system, depending on whether channel 300 is a communications channel or a recording channel;

[0054] FIG. 4 is a block diagram depicting the encoding block in one embodiment of the present invention;

[0055] FIG. 5 is a trellis diagram of a constraint length 3, rate 1/2 convolutional code with code generators g⁽¹⁾=(1,1,1) and g⁽²⁾=(1,0,1) used as an exemplary embodiment of the present invention, showing the input/output of the trellis branches and, with darken line segments, showing the encoded path for a data sequence of {u_j}=(1,1,0,1,1,0,0);

[0056] FIG. 6 is a block diagram showing a method for generating the phase signal φ(t) for Gaussian minimum shift keying (GMSK) modulation;

[0057] FIG. 7 shows the phase signal φ(t) and the quadrature baseband signal sin(φ(t)) for minimum shift keying (MSK) (top two graphs) and GMSK (bottom two graphs);

[0058] FIG. 8ashows the normalized autocorrelation values representing the ISI profile of the baseband modulated signal for GMSK with BT=0.3 (left graph) and GMSK with BT=0.1 (right graph);

[0059] FIG. 8bshows the normalized autocorrelation values representing the ISI profile of the baseband modulated signal for class IV partial response (PR4) (left graph) and extended class IV partial response (EPR4) (right graph);

[0060] FIG. 9ais a block diagram of a rate (m+n)/(m+n+1) TCM encoder comprising a rate m/(m+1) binary convolutional encoder and a mapper for choosing a symbol from an alphabet with 2^m+n+1symbols;

[0061] FIG. 9bis a block diagram of a rate 2/3, 4-state TCM encoder comprising a rate 1/2 binary convolutional encoder and a mapper for choosing a symbol from an alphabet with eight symbols;

[0062] FIG. 10 shows an 8-PSK constellation partitioned into two sets and the mapping of the rate 2/3, 4-state TCM encoder output sequence into an 8-PSK symbol and the corresponding complex symbol v_kof the encoded sequence {v_k};

[0063] FIG. 11 is a trellis diagram of the rate 2/3, 4-state TCM used as an example of TCM coding in one embodiment of the present invention, showing the input/output of the trellis branches and, with darken line segments, showing the encoded path for a data sequence of {u_j}=(10,11,10,01,01);

[0064] FIG. 12 is a block diagram of a channel model;

[0065] FIG. 13 is a block diagram of a noiseless channel model;

[0066] FIG. 14 is a block diagram illustrating the calculation of the templates {circumflex over (q)}(x,y) in one embodiment of the present invention;

[0067] FIG. 15 shows a graph of the precursor equalizer tap weights used to remove substantially all of the precursor ISI for the GMSK modulation with BT=0.1 and a graph of the discrete-time impulse response at the output of the precursor equalizer;

[0068] FIG. 16 shows a block diagram of an ISIC equalizer-decoder in one embodiment of the present invention comprising a partial equalizer, a template generator, and an ISIC decoder;

[0069] FIG. 17 shows a block diagram of an ISIC equalizer-decoder in another embodiment of the present invention where {{circumflex over (v)}_k}, an estimate of encoded sequence used by the partial equalizer for tap weight adaptation, is derived from the output sequence of the ISIC decoder;

[0070] FIG. 18 shows a block diagram of an ISIC equalizer-decoder in yet another embodiment of the present invention where {{circumflex over (v)}_k}, an estimate of encoded sequence used by the partial equalizer for tap weight adaptation, is derived using a full equalizer and a slicer;

[0071] FIG. 19 is a decoding trellis, derived from FIG. 5, for a constraint length 3, rate 1/2 binary convolutional code, with the trellis branches labeled by encoder output bits;

[0072] FIG. 20 is a decoding trellis for a constraint length 3, rate 1/2 binary convolutional code, with the branches labeled by the encoded symbols v_kof the encoded sequence {v_k};

[0073] FIG. 21 shows a block diagram of an ISIC equalizer-decoder in one embodiment of the present invention where an ISI profile estimator is employed and, for adaptation, the ISI profile estimator makes use of a replica of the training sequence {v_k}^TR;

[0074] FIG. 22 shows a block diagram of an ISIC equalizer-decoder in another embodiment of the present invention where the ISI profile estimator, for adaptation, makes use of a replica of the training sequence {v_k}^TRand an estimate {{circumflex over (v)}_k} derived from the output sequence of the ISIC decoder;

[0075] FIG. 23 shows a block diagram of an ISIC equalizer-decoder in yet another embodiment of the present invention where the ISI profile estimator, for adaptation, makes use of a replica of the training sequence {v_k}^TRand an estimate {{circumflex over (v)}_k} derived using a full equalizer and a slicer;

[0076] FIG. 24 shows an ISIC equalizer-decoder representing one of the six ISIC equalizer-decoder embodiments depicted in FIGS. 16, 17, 18, 21, 22, and 23;

[0077] FIG. 25 is a block diagram of one embodiment of a data estimator of the present invention comprising an ISIC equalizer-decoder, a double-sided partial equalizer, and a decision-directed-ISIC (DD-ISIC) decoder;

[0078] FIG. 26 shows a decoding trellis for a constraint length 3, rate 1/2 binary convolutional code used to explain the operation of the DD-ISIC decoding algorithm;

[0079] FIG. 27 is a block diagram of an encoder employing concatenated coding in one embodiment of the present invention;

[0080] FIG. 28 is a block diagram of a data estimator in one embodiment of the present invention for recovering the data having been encoded by the encoder of FIG. 27;

[0081] FIG. 29 is a block diagram of a data estimator in another embodiment of the present invention for recovering the data having been encoded by the encoder of FIG. 27 using a DD-ISIC decoder with the interim data decisions estimated by an outer FEC decoder;

[0082] FIG. 30 is a block diagram of an encoder employing concatenated coding and error-detection in yet another embodiment of the present invention; and

[0083] FIG. 31 is a block diagram of a data estimator in one embodiment of the present invention for recovering the data having been encoded by the encoder of FIG. 30.

[0084] FIGS. 1 and 2, which have been described in the “Background of the Invention” section, are block diagrams depicting a data communications system and a data storage system, respectively. FIG. 3 is a block diagram that includes data source 102, encoder 104, channel 300, data estimator 106, and data sink 108. The block diagram represents a data communications system when channel 300 is a communications channel and a data storage system when channel 300 is a recording channel. Encoder 104 and data estimator 106 are the subjects of the present invention. Encoder 104 advantageously processes the data sequence {u_j} of data symbols to provide an encoded sequence {v_k} of encoded symbols. An element of the encoded sequence {v_k} can assume a value from an alphabet A_vof symbols, which may be real or complex. Data estimator 106 advantageously processes the channel output sequence {r_k} of channel output samples to provide an estimated data sequence {û_j} of estimate data symbols, where û_jrepresents an estimate of u_j.

[0085] FIG. 4 shows a block diagram of encoder 400 in one embodiment of the present invention. Encoder 400 comprises trellis encoder 402 and mapper 404. In one embodiment of the present invention, trellis encoder 402 is a binary convolutional encoder. To describe convolutional encoders, which are well known to those skilled in the art, suppose the binary convolutional code has a rate of n_u/n_cand a constraint length K, where K, n_uand n_care integers such that n_uis less than n_c. The data sequence {u_j}, which is the input to trellis encoder 402, is a binary sequence of ones and zeroes. The output of trellis encoder 402 is denoted as the trellis-encoded sequence {c_i}. Different indices are used for the sequences {u_j} and {c_i} to signify that they are, in general, of different lengths. Trellis encoder 402 divides the data sequence {u_j} into groups of n_ubits. For each group of n_ubits, trellis encoder 402 generates n_cbits. The n_coutput bits depend on the current n_udata bits as well as the preceding (K−n_u) data bits, as defined by the code generators g⁽ⁿ⁾, n=1,2, . . . ,n_c. A code generator is a vector of K elements each assuming a value of either 0 or 1. Suppose a code generator is represented as

[0086] g⁽ⁿ⁾=(g₀⁽ⁿ⁾,g₁⁽ⁿ⁾, . . . ,g_K−1⁽ⁿ⁾)  (9)

[0087] where g_l⁽ⁿ⁾ε{0,1}, l=0,1, . . . ,K−1. Suppose the K data bits being advantageously processed by trellis encoder 402 at bit time m is represented by the vector of length K:

[0088] u_m=(u_m−K+1,u_m−K+2, . . . ,u_m−1,u_m).  (10)

[0089] Since trellis encoder 402 processes the data sequence in groups of n_ubits, the index m in the above equation must be a multiple of n_u, i.e., m=n_u,2n_u, . . . . It is assumed that trellis encoder 402 is preloaded with zeroes so that in the above equation, u_j=0 if j<1. As the name “convolutional code” implies, the n_coutput bits are computed by convolving u_mwith g⁽ⁿ⁾for n=1,2, . . . ,n_c: $\begin{array}{cc}\begin{array}{c}{b}_m^{\left(n\right)}=u_m\otimes g^{\left(n\right)}\\ =\sum _{l=0}^{K-1}{u}_{m-l}{g}_l^{\left(n\right)}\\ =u_m{g}_0^{\left(n\right)}\oplus u_{m-1}{g}_1^{\left(n\right)}\oplus \dots \oplus u_{m-K+1}{g}_{K-1}^{\left(n\right)}\end{array}& \left(11\right)\end{array}$

[0090] where {circle around (X)} stands for convolution operation and ⊕ stands for the modulo-2 operation, which is defined by the following set of equations: 0⊕0=0, 1⊕1=0, 1⊕0=1, and 0⊕1=1. The trellis-encoded sequence {c_i} is given in terms of b_m⁽ⁿ⁾according to

[0091] c_(l−1)n+n=b_ln⁽ⁿ⁾  (12)

[0092] for l=1,2, . . . and n=1,2, . . . , n_c.

[0093] As an example of the trellis encoding algorithm suppose the data sequence is {u_j}=(1,1,0,1,1,0,0) and the code is the well-known constraint length 3, rate 1/2 binary convolutional code with code generators g⁽ⁿ⁾=(1,1,1) and g⁽²⁾=(1,0,1). The output sequence can be shown to be {c_j}=(11,01,01,00,01,01,11), which is twice as long as the input sequence. The expression for {c_i} shows the output sequence in pairs of bits to signify the fact that, for rate 1/2 code, trellis encoder 402 generates two bits for every input bit.

[0094] It is customary to think of a trellis encoder as comprising a shift register with K stages, with the data sequence being supplied to the shift register from the left. The content of the shift register at time m is equal to the right hand side of equation (10) written in the reverse order: (u_m,u_m−1, . . . ,u_m−K+2,u_m−K+1). It is also customary to define the encoder state as the oldest K−n_ubits in the shift register. The number of encoder states is equal to 2^K−n. For a K=3, rate 1/2 code, there are four states: 00, 01, 10, and 11. In a binary representation of a state, the leftmost bit is the most recent bit.

[0095] The trellis encoding process can be displayed in the form of a trellis. A trellis diagram for the K=3, rate 1/2 code is depicted in FIG. 5. A state is shown in the figure as a dot. All of the dots on the top row of the figure are state 00, all of the dots on the second row are state 01, and so on. A state is connected to another state by a branch. Each branch in the figure is labeled as data-input/encoded-output. The darkened path in the figure shows the encoding of the data sequence {u_j}=(1,1,0,1,1,0,0). The trellis encoding starts at trellis depth 0 at the all-zero state. The first data bit, which is 1, takes the encoder state from 00 to 10 and the trellis encoder outputs the pair 11. The second data bit, which is also 1, takes the encoder from state 10 to state 11 and the trellis encoder outputs the pair 01. And the process continues until the entire data sequence has been encoded. With reference to FIG. 5, there are two branches emanating from each state. This is due to the fact that the trellis diagram is for a rate 1/2 code. In general, for a rate n_u/n_cbinary convolutional code, there will be 2ⁿbranches emanating from each state; and the branch label will be of the form a_n. . . a₁/b₁. . . b_n, where a_nis the most recent input data bit and b_nis the most recent trellis encoder output bit.

[0096] Referring back to FIG. 4, trellis encoder 402 provides the output sequence {c_i}, which is supplied to mapper 404 to provide the encoded sequence {v_k}. The values assumed by the encoded symbols are taken from an alphabet acceptable to the channel as a valid input. In particular, the processing performed by mapper 404 is determined by the modulation scheme of modulator 122 for the case of a communications channel and of modulator 222 for the case of a data storage channel. I will now describe the mapping for four modulation schemes used in data communications systems: binary phase shift keying (BPSK), quadrature phase shift keying (QPSK), minimum shift keying (MSK), and Gaussian minimum shift keying (GMSK), which are well known to those skilled in the art. I will use the signal space representation in which a member of the sequence {v_k} is of the form v_k=a+jb, where a and b are real numbers and j={square root over (−1)}. (Note that j is an integer when it is used an index as in {u_j}.) For BPSK, mapper 404 maps an input bit c_kinto an output symbol v_kaccording to $\begin{array}{cc}{v}_k=\{\begin{array}{cc}+1;& \mathrm{if}{c}_k=1\\ -1;& \mathrm{if}{c}_k=0\end{array}.& \left(13\right)\end{array}$

[0097] I will refer to the above mapping as antipodal mapping. For BPSK, the output of modulator 122 is the modulated signal:

[0098] s(t)=v_kcos(2πf_ct); (k−1)T<t≦kT  (14)

[0099] where f_cis the carrier frequency and T is the duration of an encoded symbol so that 1/T is the encoded symbol rate. The quantity f_cis sometimes referred to as the radio frequency (RF) and the quantity s(t) as the modulated RF signal.

[0100] For QPSK, mapper 404 maps a pair of input bits into an output symbol according to $\begin{array}{cc}{v}_k=\{\begin{array}{cc}+1+j;& \mathrm{if}\left(c_{2k-1},c_{2k}\right)=\left(1,1\right)\\ +1-j;& \mathrm{if}\left(c_{2k-1},c_{2k}\right)=\left(1,0\right)\\ -1+j;& \mathrm{if}\left(c_{2k-1},c_{2k}\right)=\left(0,1\right)\\ -1-j;& \mathrm{if}\left(c_{2k-1},c_{2k}\right)=\left(0,0\right)\end{array}& \left(15\right)\end{array}$

[0101] For QPSK, the output of modulator 122 is the modulated signal:

[0102] s(t)=Re{v_kexp{2πf_ct}}; (k−1)T<t≦kT  (16)

[0103] where Re stands for “the real part of” and exp is the exponential function.

[0104] It proves convenient to express the modulated RF signal in terms of the complex baseband modulated signal p_M(t):

[0105] s(t)=Re{p_M(t)exp{2πf_ct}}.  (17)

[0106] For BPSK and QPSK, the complex baseband modulated signal is

[0107] p_M(t)=v_k; (k−1)T<t≦kT.  (18)

[0108] In one embodiment of the present invention for MSK and GMSK modulation, the mapping of trellis-encoded sequence {c_k} into the encoded sequence {v_k} includes three steps. In the first mapping step, the trellis-encoded sequence {c_k} is mapped into a sequence {V_k} using antipodal mapping, i.e., set V_k=+1 if c_k=1, and set V_k=−1 if c_k=0. In the second mapping step, beginning with the second pair of symbols in the sequence {V_k}, every other pair of symbols is inverted to provide an inverted sequence, denoted as {{overscore (v)}_k}. In particular, $\begin{array}{cc}{\stackrel{\_}{v}}_k=\{\begin{array}{cc}{V}_k;& \mathrm{if}k=1,2,5,6,9,10,\dots \\ -V_k;& \mathrm{if}k=3,4,7,8,11,12,\dots \end{array}& \left(19\right)\end{array}$

[0109] For example, if {V_k}=(1,−1; 1,1; 1,1; −1,1; −1,−1), then the inverted sequence is {{overscore (v)}_k}=(1,−1; −1,−1; −1,1; 1,−1; −1,−1). In the third mapping step, the inverted sequence is differentially encoded to provide the encoded sequence {v_k} according to

[0110] v_k={overscore (v)}_k{overscore (v)}_k−1.  (20)

[0111] To explain the rationale behind these mapping steps, I will express the complex baseband modulated signal for MSK and GMSK as

[0112] p_M(t)=cos(φ(t))+jsin(φ(t))=exp{jφ(t)}  (21)

[0113] where φ(t) is the phase of the modulated signal. The quantities cos(φ(t)) and sin(φ(t)) are referred to as the in-phase and the quadrature baseband signals, respectively. Consider first MSK for which the phase signal is given by $\begin{array}{cc}\phi \left(t\right)=\phi \left(\left(k-1\right)T\right)+v_k\frac{\pi }{2T}\left(t-\left(k-1\right)T\right);\left(k-1\right)T<t\le \mathrm{kT}.& \left(22\right)\end{array}$

[0114] After some thought and plotting the phase signal for a few values of the trellis-encoded sequence {c_i}, it should become apparent that the three mapping steps are performed to control the polarity of the MSK modulated signal such that the channel output symbol r_kin the absence of noise is positive if c_k=1 and negative if c_k=0. In particular, for an even value of k, the mapping steps ensure that the in-phase baseband signal, cos(φ(t)), will be positive over the two-symbol interval (k−1)T<t≦(k+1)T if c_k=1, and negative if c_k=0 Similarly, for an odd value of k, the mapping steps ensure that the quadrature baseband signal, sin(φ(t)), will be positive over the two-symbol interval (k−1)T<t≦(k+1)T if c_k=1, and negative if c_k=0. This relationship between c_kand the polarity of the baseband in-phase and quadrature components will make it easier for the data estimator to recover the data sequence.

[0115] Consider next the generation of the phase signal φ(t) for GMSK. In the continuous-time notation, the encoded sequence can be represented as $\begin{array}{cc}v\left(t\right)=\sum _k{v}_k{p}_{\mathrm{ua}}\left(t-\left(k-1\right)T\right)& \left(23\right)\end{array}$

[0116] where p_ua(t) is the unit-amplitude pulse such that p_ua(t)=1 for 0<t≦T and equal to 0 elsewhere. FIG. 6 shows that phase signal φ(t) is generated by supplying the signal v(t) to Gaussian filter 602 to generate a frequency signal f(t) and supplying the frequency signal to integrator 604. Gaussian filter 602 has a transfer function given by $\begin{array}{cc}G\left(f\right)=\frac{\pi }{2}\exp \left\{-\frac{\ln 2}{2}{\left(\frac{f}{B}\right)}^2\right\}& \left(24\right)\end{array}$

[0117] where B is the one-sided 3-dB bandwidth. The product of the one-sided 3-dB bandwidth and the symbol duration, BT, is used as a parameter in specifying the GMSK modulation. For example, the European Global System for Mobile Communications (GSM) employs BT=0.3. A smaller value of BT yields a modulated signal that has a narrower spectrum but introduces more ISI. For example, using GMSK with BT=0.1 introduces much more ISI than using GMSK with BT=0.3 but cuts the signal bandwidth by approximately a factor of two.

[0118] With reference to FIG. 6, the frequency signal may be written as $\begin{array}{cc}f\left(t\right)=\sum _k{v}_k{p}_{\mathrm{ug}}\left(t-\mathrm{kT}\right)& \left(25\right)\end{array}$

[0119] where p_ug(t) is the response of Gaussian filter 602 when the input is the unit-amplitude pulse p_ua(t). The phase signal may be written as $\begin{array}{cc}\phi \left(t\right)=\sum _k\left[v_k{\int }_{-\infty }^t{p}_{\mathrm{ug}}\left(\tau -\mathrm{kT}\right)d\tau \right]=\sum _k\left[v_k{\int }_{-\infty }^{t-\mathrm{kT}}{p}_{\mathrm{ug}}\left(x\right)dx\right]& \left(26\right)\end{array}$

[0120] FIG. 7 compares the phase signals and the quadrature signals of MSK and GMSK for the case where the sequence {v_k}=(+1,−1). Curve 702, representing the MSK phase signal, shows that the phase changes linearly by π/2 over a period of T, reaching the maximum value of π/2 at the end of the first symbol. Curve 712, representing the GMSK phase signal, shows that the phase changes more gradually than the MSK case and that the maximum does not reach π/2. Curve 704, representing the MSK quadrature signal, shows that the signal is zero outside the interval of 2T. Curve 714, representing the GMSK quadrature signal, shows that the signal extends beyond the interval of 2T. This GMSK signal extension in the time domain causes ISI. The ISI profile can be estimated by computing the autocorrelation function of the GMSK pulse such as curve 714. The autocorrelation values approximate the modulator's discrete-time transfer function, or, the ISI profile, which will be denoted as f_i, i=0,±1,±2, . . . . The sampling interval is equal to the symbol interval. It is customary to normalize the discrete-time transfer function of the modulation such that f₀=1. For BT=0.1, I have found that f₁=f₋₁=0.52 and f₂=f₋₂=0.08. The discrete-time transfer function of the modulation is shown in FIG. 8aas dots. Graph 802 shows the discrete-time transfer function for GMSK with BT=0.3 and graph 804 shows the discrete-time transfer function for GMSK with BT=0.1. Therefore, as stated above, using GMSK with BT=0.1 introduces much more ISI than using GMSK with BT=0.3.

[0121] MSK and GMSK are members of a class of modulation schemes called continuous phase modulation (CPM), see the article: “Continuous Phase Modulation,” by C. Sundberg, IEEE Communications Magazine, vol. 24, No. 4, pp. 25-38, April 1986 and the article: “Multi-h Phase-Coded Modulation,” by I. Sasase and S. Mori, IEEE Communications Magazine, pp. 46-56, December 1991. Those skilled in the art should recognize that the encoding and mapping methods described above are applicable to CPM.

[0122] I will now describe encoder 400 for two popular modulation schemes in magnetic recording, namely the class IV partial response (PR4) and the extended the extended class IV partial response (EPR4) schemes. The extension of the present invention to other partial response modulation should be obvious to those skilled in the art. For this embodiment of the present invention, trellis encoder 402 is a binary convolutional encoder. Mapper 404 employs two mapping steps. In the first mapping step, the trellis-encoded sequence {c_k} is mapped into a sequence {V_k} using antipodal mapping, i.e., set V_k=+1 if c_k=1, and set V_k=−1 if c_k=0. This step is identical to that described previously for MSK and GMSK. In the second mapping step, the sequence {V_k} is mapped into the encoded sequence {v_k} according to the chosen partial response modulation scheme. For PR4 modulation, which has a discrete-time transfer function of 1−D², the encoded symbol for the k'th symbol interval is given by

[0123] v_k=V_k−V_k−2.  (27)

[0124] For EPR4 modulation, which has a discrete-time transfer function of 1+D−D²−D³, the encoded symbol for the k'th symbol interval is

[0125] v_k=V_k+V_k−1V_k−2−V_k−3.  (28)

[0126] The discrete-time transfer function of the PR4 mapping is shown in FIG. 8bas graph 806 and that of the EPR4 modulator is shown as graph 808. It should be noted that the non-zero ISI components in the PR4 and EPR4 signals are postcursor and that there is no precursor ISI. This may be contrasted with the GMSK modulated signal, which has both non-zero precursor and postcursor ISI.

[0127] In yet another embodiment of the present invention, trellis encoder 402 of encoder 400 is a trellis coded modulation (TCM) encoder, which should be familiar to those skilled in the art, and is described in the article: “Channel Coding with Multilevel/Phase Signals,” by G. Ungerboeck, IEEE Transactions on Information Theory, vol. IT-28, No. 1, pp. 55-66, January 1982. A TCM encoder/mapper with a code rate of (m+n)/(m+n+1) is shown in FIG. 9a. The data sequence {u_j} is supplied to S/P converter 902, which performs serial-to-parallel conversion by dividing the input sequence into groups of length (m+n) bits and presenting one group at a time at its parallel output ports. The first m bits in each group of (m+n) bits, denoted as (u⁽¹⁾,u⁽²⁾, . . . ,u^(m+n)), are supplied to a rate m /(m+1) binary convolutional encoder 904, which encodes the m bits into (m+1) bits, denoted as (c⁽⁰⁾,c⁽¹⁾, . . . ,c^(m)). The other n bits in each group of (m+n) bits of the data sequence are not encoded, i.e., c^(j)=u^(j)for j=m+1, . . . ,m+n. The trellis-encoded vector (c⁽⁰⁾,c⁽¹⁾, . . . ,c^(m+n)is supplied to mapper 906, which selects a symbol based on the trellis-encoded vector from an alphabet containing 2^m+n+1symbols. The mapping used by mapper 906 is pre-defined by a process known as set partitioning, which is familiar to those skilled in the art and is described in the article by Ungerboeck cited above.

[0128] I will now present an example of a TCM encoder that can be used with the present invention. FIG. 9bshows a rate 2/3, 4-state TCM encoder. The output of S/P converter 912 is supplied to convolutional encoder 914, which has delay elements 918-1 and 918-2 and modulo-2 adder 920. Convolutional encoder 914 has code generators g⁽¹⁾=(0,1,0) and g⁽²⁾=(1,0,1). The trellis-encoded vector (c⁽⁰⁾,c⁽¹⁾,c⁽²⁾) is supplied to mapper 916, which selects a symbol based on the trellis-encoded vector from an alphabet containing eight symbols.

[0129] FIG. 10 shows an 8-PSK constellation partitioned into two sets and the mapping of the rate 2/3, 4-state TCM encoder output sequence into an 8-PSK symbol and the corresponding complex symbol v_k. The signal constellation has eight points on circle 1002 of radius one. The signal points shown as open circles and labeled as symbols 0, 2, 4, and 6 are in one set while the those shown as filled-in dots and labeled as symbols 1, 3, 5, and 7 are in another set. To illustrate the mapping of the trellis-encoded vector into a symbol, let (c⁽⁰⁾,c⁽¹⁾,c⁽²⁾)=(0,1,1). The bit c⁽⁰⁾chooses one of the two sets: if c⁽⁰⁾=0, then the set {0,2,4,6} is chosen; if c⁽⁰⁾=1, then the set {1,3,5,7} is Since, for this example, c⁽⁰⁾=0, the set {0,2,4,6} is chosen. This set of four symbols is further partitioned into two sets of two symbols each and the bit c⁽¹⁾chooses between the two sets. In particular, if c⁽¹⁾=0, then the set {0,4} is chosen; otherwise the set {2,6} is chosen. As shown in FIG. 10, the two symbols in each of these two sets are 180° apart and achieve the maximum Euclidean distance between two points on a circle. Thus, set partitioning maximizes the Euclidean distance among the signal points within a set. Returning to the example, since c⁽¹⁾=1, the set {2,6} is chosen. Finally, c⁽²⁾=1 selects symbol 6 from the set. Hence, the trellis encoder vector (0,1,1) is mapped into symbol 6. The complete set of mapping is shown in table 1004 in FIG. 10. The encoder output symbol v_kis a complex number with an in-phase (I) component and a quadrature (Q) component. For example, the trellis-encoded vector (0,0,0) is mapped into symbol 0, which has a complex representation of cos(π/8)+j sin(π/8).

[0130] FIG. 11 is a trellis diagram of the rate 2/3, 4-state TCM code discussed above. A branch on the trellis is labeled u⁽²⁾u⁽¹⁾/symbol. Note that the input bits are written in the reverse order, with the newest bit on the right. For example, if the data sequence is {u_j}=(1,0), then u⁽²⁾u⁽¹⁾=(0,1). There is a pair of parallel branches connecting each pair of states. The input bit u⁽¹⁾determines the next state and u⁽²⁾determines which of the two parallel branches is to be chosen. For example, suppose the current state is 00. If u⁽¹⁾=0, the next state is 00; if u⁽¹⁾=1, the next state is 10. If u⁽²⁾=0, the upper branch of the two parallel branches is chosen; if u⁽²⁾=1, the lower branch is chosen. FIG. 11 shows, with a darken path, the encoded path for an input sequence of {u_j}=(10,11,10,01,01). The encoded sequence is {v_k}=(2,7,1,7,6).

[0131] Those skilled in the art should recognize that the preceding TCM example can easily be generalized, by using the arrangement shown in FIG. 9a, to support a PSK constellation with 2ⁿsymbols, for n greater than 3. They should also recognize that same arrangement can be used to support quadrature amplitude modulation (QAM). Set partitioning of TCM to support QAM is discussed in the article by Ungerboeck cited above.

[0132] Table 1 presents the exemplary encoding embodiments of the present invention. In summary, trellis encoding is performed on the data sequence {u_j} to provide a trellis-encoded sequence {c_k}, which is mapped into an encoded sequence {v_k} for use as input to a channel, which includes a modulator.

[0133] Quantities called templates will be a part of the data estimator embodiments of the present invention. A template is a function of two or three vector arguments and is the response of a noiseless channel model with a truncated ISI profile when the arguments of the templates are applied to the noiseless channel model. A template represents the statistical average values of the channel output samples after certain processing has been performed, as explained below. In the data estimator, templates are compared with processed channel output samples to provide a reliability metric. The results of these comparisons are used to aid data recovery. I will define the templates and show how they can be calculated or estimated. I will start with channel model 1200 shown in FIG. 12. The model is a complex baseband model, i.e., the signals are at the baseband frequency and they are in general complex, having real and imaginary parts. The encoded sequence {v_k} is supplied to modulator (MOD) 1202 to provide a complex baseband modulated signal p_M(t). The modulated signal p_M(t) is supplied to block 1204, which has an impulse response of h_x(t), to provide a signal p_x(t). In the case of a data communications channel, block 1204 models the response of the transmitter and the communications medium. In the case of a data storage channel, block 1204 models the data recorder and the recording medium. From basic systems theory, it is seen that

[0134] p_x(t)=p_M(t){circle around (X)}h_x(t)  (29)

[0135] where {circle around (X)} stands for the convolution operation. The signal p_x(t) is supplied to adder 1206. The other input to adder 1206 is a noise process n_x(t). The output of adder 1206 is supplied to block 1208, which has an impulse response of h_R(t), to provide the signal p_R(t)+n(t), where

[0136] p_R(t)=p_x(t){circle around (X)}h_R(t)  (30)

[0137] and

[0138] n(t)=n_x(t){circle around (X)}h_R(t)  (31)

[0139] are the filtered signal and the filtered noise, respectively. In the case of a data communications channel, block 1208 models the response of the receiver and the matched filter. In the case of a data storage channel, block 1208 models the data reader. Sampler 1210 samples the output of block 1208 once every T seconds to generate the channel output sequence {r_k}, where T is the duration of a symbol. It proves convenient to represent r_kas the sum of a signal component and a noise component:

[0140] r_k=s_k+n_k  (32)

[0141] where,

[0142] s_k=p_R(kT)  (33)

[0143] and

[0144] n_k=n(kT).  (34)

[0145] The noise process n(t) is usually modeled as a zero-mean random process. Therefore, from equation (32), the signal component s_kis the statistical average of the channel output sample r_k. Strictly speaking, the statistical average is a conditional statistical average where the condition is the application of a specific sequence to the channel input. This point would become apparent in the following when we define the templates as statistical averages.

[0146] The above discussion shows that, when a given encoded sequence {v_k} is supplied to channel model 1200, the signal component {s_k} of the channel output sequence {r_k} can be uniquely computed from the characteristics of modulator (MOD) 1202 and the impulse responses h_x(t) and h_R(t) of blocks 1204 and 1208, respectively. The above-described procedure works for either linear or non-linear modulation schemes. The modulation schemes MSK and GMSK are non-linear. When the modulation scheme is linear, such as BPSK, QPSK, M-ary PSK, and QAM, the channel output sequence {r_k} may be expressed as a linear combination of the encoded sequence {v_k}. This is done in equation (1) where the coefficients h_i, i=−L₁, . . . ,0, . . . ,L₂represent the channel impulse response (CIR). More specifically, h_i=h(iT) where h(t) is the continuous-time impulse response of the channel, which is equal to the convolution the impulse response of modulator (MOD) 1202 with the impulse responses h_x(t) and h_R(t) of blocks 1204 and 1208, respectively. For linear modulation, the signal component {s_k} of the channel output sequence {r_k} is given by $\begin{array}{cc}{s}_k=\sum _{i=-L_1}^{-1}{h}_i{v}_{k-i}+h_0{v}_k+\sum _{i=1}^{L_2}{h}_i{v}_{k-i}& \left(35\right)\end{array}$

[0147] In general, not all of the characteristics and impulse responses of the channel are known a priori. If the signal component {s_k} of the channel output is to be computed, one must first estimate the unknown characteristics of the channel. FIG. 13 shows a block diagram of noiseless channel model 1300, which is the same as channel model 1200 with the following exception: (i) the noise process n_x(t) and adder 1206 are absent; and (ii) the impulse responses h_x(t) and h_R(t) of blocks 1204 and 1208 are replaced by impulse response estimates ĥ_x(t) and ĥ_R(t) of blocks 1304 and 1308, respectively. In this exemplary description of the present invention, I have assumed that the characteristics of modulator (MOD) 1202 are known a priori. This assumption should not be considered restrictive. In an application where the characteristics-of the modulator can only be estimated, the calculation of the complex baseband modulated signal p_M(t) can be made based on the estimated characteristics of the modulator. Applying basic systems theory to the noiseless channel model of FIG. 13 yields

[0148] {circumflex over (p)}_x(t)=p_M(t){circle around (X)}ĥ_x(t)  (36)

[0149] and

[0150] {circumflex over (p)}_R(t)={circumflex over (p)}_x(t){circle around (X)}ĥ_R(t).  (37)

[0151] These two equations may be combined to yield

[0152] {circumflex over (p)}_R(t)=p_M(t){circle around (X)}ĥ_XR(t)  (38)

[0153] Here,

[0154] ĥ_XR(t)=ĥ_x(t){circle around (X)}ĥ_R(t)  (39)

[0155] is the impulse response of block 1320, which is the cascade of the blocks 1304 and 1308. The signal output of the noiseless channel model is

[0156] {overscore (s)}_k={circumflex over (p)}_R(kT).  (40)

[0157] In summary, the signal sequence {{overscore (s)}_k} in response to the encoded sequence {v_k} being supplied to the input of noiseless channel model 1300 may be computed as follows: (i) compute the baseband modulated signal p_M(t) for the chosen modulation scheme; (ii) compute {circumflex over (p)}_R(t) using equation (38); and (iii) compute {overscore (s)}_kusing equation (40).

[0158] In the above procedure for calculating the signal sequence {{overscore (s)}_k}, the equations have been presented in the continuous-time domain. Those skilled in the art will recognize that the continuous-time baseband modulated signal p_M(t) and the impulse response ĥ_XR(t) may be replaced by their equivalent discrete-time functions so that the calculation may be carried out by means of digital signal processing. I will illustrate this by describing a computer program that I have developed for simulating one embodiment of the present invention where the modulation is GMSK. In the computer program, the discrete-time calculations are performed at the rate of four times per symbol period T, i.e., the sampling period T_S=T/4. The discrete-time equivalent of the frequency signal given by equation (25) is evaluated at the sampling instants t=t₁=iT_s, i=1,2, . . . , to yield f(i). The integrals in equation (26) are replaced by summations to evaluate the discrete-time phase signal φ(i) at the sampling instants. The discrete-time phase signal φ(i) is used in the discrete-time equivalent of equation (21) to calculate the discrete-time complex baseband signal p_M(i). For the computer program that I have developed, the impulse response of the matched filter, denoted as h_MF(i), is equal to the discrete-time equivalent of the quadrature signal for a GMSK modulator when the encoded sequence is {v_k}=(+1,−1). An example of a continuous-time quadrature signal for GMSK is shown as curve 714 in FIG. 7. For the case where the only ISI is that introduced by the modulation, the estimated impulse response ĥ_XR(t) of equation (39) would just be the impulse response of the matched filter, or, in discrete-time notation, ĥ_XR(i)=h_MF(i). Hence, the discrete-time channel output signal may be computed using the discrete-time equivalent of equation (38): {circumflex over (p)}_R(i)=p_M(i){circle around (X)}ĥ_XR(i)=p_M(i){circle around (X)}h_MF(i). The output of the noiseless channel model, given by equation (40), is {circumflex over (p)}_R(k) where the parameter k is such that kT_sis equal to a boundary of a symbol interval, i.e., kT_sis a multiple of T so that the matched filter is sampled when the signal component is at its maximum level.

[0159] Calculating the signal sequence {{overscore (s)}_k} is simpler when the channel is linear since the signal component {overscore (s)}_kmay be expressed as a linear combination of the encoded sequence {v_k}. Let {overscore (h)}(t) be the estimated impulse response of the channel, which is equal to the convolution of the impulse response of modulator (MOD) 1202 with the estimated impulse responses {overscore (h)}_x(t) and {overscore (h)}_R(t) of blocks 1304 and 1308, respectively. Let {overscore (h)}_i={overscore (h)}(iT), then the sequence {{overscore (h)}_i} represents the discrete-time impulse response, or, the ISI profile, of noiseless channel model 1300. For a linear channel, the signal component {overscore (s)}_kis given by $\begin{array}{cc}{\stackrel{\_}{s}}_k=\sum _{i=-L_1}^{-1}{\hat{h}}_i{v}_{k-i}+{\hat{h}}_0{v}_k+\sum _{i=1}^{L_2}{\hat{h}}_i{v}_{k-i}.& \left(41\right)\end{array}$

[0160] Since the channel with ISI can spread the input signal in time, the channel output usually has a longer duration than the channel input. Suppose an encoded sequence {v_k} is a sequence of zeroes except at time i, i.e., v_k=0 for k≠i. If this sequence is supplied to noiseless channel model 1300, then the output sequence is ( . . . , ĥ₋₁v_i,ĥ₀v_i,ĥ₁v_i, . . . ). I will adopt the indexing convention that {overscore (s)}_i={overscore (h)}₀v_iand refer to {overscore (s)}_ias the primary response of noiseless channel model 1300 to channel input v_i.

[0161] I will now define the templates, in particular the single-sided template {circumflex over (q)}(•,•), which is a function of two arguments. The arguments, which can be either vectors or scalars, assume values from the alphabet A_vof the encoded sequence {v_k}. Let the arguments of the templates be x and y, where x=(x₁,x₂, . . . ,x_L) and y=(y₁,y₂, . . . ,y_L) are vectors of length L_xand L_yrespectively, with elements taken from the alphabet A_vof the encoded sequence {v_k}. For these vector arguments, the template is equal to {circumflex over (q)}(x,y). By definition, {circumflex over (q)}(x,y) is a vector with the same number of elements as the second vector argument y.

[0162] I will use FIG. 14 to motivate the definition of templates for the present invention. The vector arguments x and y of the template {circumflex over (q)}(x,y) represent the input to noiseless channel model 1300. In this case, the encoded sequence {v_k} is expressed as a vector v, where v=(x,y)=(x₁,x₂, . . . ,x_L,y₁,y₂, . . . ,y_L). The signal sequence {{overscore (s)}_k}, representing the output of noiseless channel model 1300, can be computed using the method presented above. The primary response of noiseless channel model 1300 to the encoded symbol y₁is {overscore (s)}_L+1since y₁is the (L_x+1)'th encoded symbol to be supplied to the channel. With reference to FIG. 14, the signal sequence {{overscore (s)}_k} is supplied to precursor equalizer 1402, which removes substantially all of the precursor ISI and possibly some of the postcursor ISI in its input sequence to provide an output sequence {{circumflex over (q)}_k}. The sequence {{circumflex over (q)}_k} is supplied to block 1404, which selects from its input sequence those elements with indices (L_x+1) to (L_x+L_y) to provide the template {circumflex over (q)}(x,y)=({circumflex over (q)}_L+1, . . . ,{circumflex over (q)}_L+L). Since {circumflex over (q)}(x,y) is computed using a channel model without noise, the template approximates the statistical averages for channel model 1200, for which noise is modeled as a zero-mean random process. Since channel model 1200 is in turn a model of channel 300, it follows that, when the encoded vector v=(x,y) is applied to channel 300, the template {circumflex over (q)}(x,y) approximates statistical averages of the channel output samples after the samples have been processed by an equalizer that removes the precursor ISI and possibly some of the postcursor ISI.

[0163] I will now show that templates may be computed from a truncated ISI profile obtained by setting selected components of the ISI profile of the channel to zero. Let {{tilde over (h)}_i} represent the discrete-time system impulse response of noiseless-channel-equalizer model 1408 shown in FIG. 14. Block 1408 is made up of noiseless channel model 1300 and precursor equalizer 1402. According to the present invention, the sequence {{circumflex over (q)}_k} is substantially free of precursor ISI but may contain some of all of the postcursor ISI. In other words, the ISI profile for the sequence {{circumflex over (q)}_k} may be represented as $\begin{array}{cc}{\tilde{h}}_i\approx \{\begin{array}{cc}0;& \mathrm{for}i<0\mathrm{and}i>L_x\\ {\tilde{h}}_i;& \mathrm{for}i=0,1,\dots ,L_x\end{array},& \left(42\right)\end{array}$

[0164] where {ĥ_i} is the ISI profile of noiseless channel model 1300. If L_x=L₂, none of the postcursor ISI is equalized. If L_x<L₂, some of the postcursor ISI is equalized. The discrete-time impulse response {{tilde over (h)}_i} is therefore a truncated ISI profile obtained by setting the precursor and possibly some postcursor components of the ISI profile {ĥ_i} to zero. For a linear channel, the desired sample for the k'th symbol interval at the output of precursor equalizer 1402 may be computed according to $\begin{array}{cc}\begin{array}{c}{\hat{q}}_k=\sum _{i=-L_1}^{L_2}{\tilde{h}}_i{v}_{k-i}\\ \approx {\hat{h}}_0{v}_k+\sum _{i=1}^{L_x}{\hat{h}}_i{v}_{k-i}.\end{array}& \left(43\right)\end{array}$

[0165] It follows that the template {circumflex over (q)}(•,•) may be computed from a truncated ISI profile.

[0166] To complete the discussion on calculating single-sided templates, I will describe the structure of precursor equalizer 1402. For the present invention, block 1402 is a transversal filter with N₁precursor taps and N₂postcursor taps. The total number of equalizer taps is N=N₁+N₂+1. The number of equalizer taps is set to be sufficiently large so that the precursor ISI and selected postcursor ISI components can be equalized. If the vector of equalizer tap weights is w=(w_−N, . . . ,w₀, . . . ,w_N)^Tand the signal vector being advantageously processed by the equalizer is {overscore (s)}_k=({overscore (s)}_k+N, . . . ,{overscore (s)}_k, . . . ,{overscore (s)}_k−N)^T, then the output sample of precursor equalizer 1402 for the k'th symbol interval would be

[0167] {overscore (q)}_k=w^H{overscore (s)}_k.  (44)

[0168] The equalizer tap weights required to provide an output {overscore (q)}_kthat approximates the desired output {circumflex over (q)}_kcan be calculated using the solution to the Wiener-Hopf equation, see the book: Adaptive Filter Theory, Third Edition, by S. Haykin, Prentice-Hall, Inc., 1996, pp. 194-206. The vector of the required equalizer tap weights is given by the following equation, which is well known to those skilled in the art:

[0169] w=R⁻¹p  (45)

[0170] where R⁻¹is the inverse of the N×N autocorrelation matrix R, which is given by

[0171] R=E{{overscore (s)}_k{overscore (s)}_k^H}  (46)

[0172] where E is the statistical averaging operator, also known as the expectation operator. The quantity p is a N×1 cross-correlation column vector:

[0173] p=E{{overscore (s)}_k{circumflex over (q)}_k}.  (47)

[0174] For a non-linear modulation such as GMSK, I have found by means of computer simulation that good performance can be achieved by using the tap weights calculated using a linear model as described above. More specifically, the desired output {circumflex over (q)}_kis computed using the linear model of equation (43). As an example on the application of the Wiener-Hopf solution to GMSK, suppose all of the ISI is introduced by the modulator, i.e., h_i=f_ifor all values of i, where f_iis the i'th coefficient of the discrete-time transfer function of the modulator. Suppose the modulation is GMSK with BT=0.1 so that the discrete-time transfer function is given by graph 804 of FIG. 8a. Consider a precursor equalizer with five precursor taps, one center tap, and three postcursor taps. The equalizer tap weights computed according to equation (45) are shown as graph 1502 of FIG. 15. The discrete-time impulse response of the noiseless-channel-equalizer model 1408 is shown in FIG. 15 as graph 1504, which shows that the precursor ISI has been substantially removed by the precursor equalizer and the postcursor ISI has been left unequalized.

[0175] In summary, the single-sided template {circumflex over (q)}(•,•) is a function of two arguments and is a vector with the same number of elements as the second vector argument. For vector arguments x and y, the single-sided template {circumflex over (q)}(x,y) is the response of a noiseless channel model with a truncated ISI profile when vector y is applied to the channel preceded by vector x. The truncated ISI profile has zero precursor ISI and up to L_xnon-zero postcursor ISI components, where L_xis the length of the first vector argument. The templates may be computed using equation (43) with the encoded sequence {v_k} set to be the vector v, where v=(x,y). For non-linear channels, the templates may be approximated using the linear model of equation (43) or they may be more accurately computed by using the arrangement illustrated in FIG. 14.

[0176] Some embodiments of the present invention make use of the double-sided templates ŝ(•,•,•), which are a function of three arguments. For vector arguments x, y, and z, the double-sided template is equal to ŝ(x,y,z), where x and y are defined above and z=(z₁,z₂, . . . ,z_L) is a vector of length L_zwith elements taken from the alphabet A_vof the encoded sequence {v_k}. The double-sided template ŝ(x,y,z) is the response of a noiseless channel model with a truncated ISI profile when vector y is applied to the channel preceded by vector x and followed by vector z. The truncated ISI profile has non-zero precursor and postcursor ISI: $\begin{array}{cc}{\tilde{h}}_i\approx \{\begin{array}{cc}0;& \mathrm{for}i<-L_z\mathrm{and}i>L_x\\ {\hat{h}}_i;& \mathrm{for}i=-L_z,\dots ,-1,0,1,\dots ,L_x\end{array},& \left(48\right)\end{array}$

[0177] The components of the double-sided templates may be computed according to $\begin{array}{cc}{\hat{s}}_k\approx \sum _{i=-L_z}^l{\hat{h}}_i{v}_{k-i}+{\hat{h}}_0{v}_k+\sum _{i=1}^{L_x}{\hat{h}}_i{v}_{k-i}.& \left(49\right)\end{array}$

[0178] The single-sided templates {circumflex over (q)}(•,•) and the double-sided templates ŝ(•,•,•) differ in the truncated ISI profiles used to generate the templates. In the case of single-sided templates the truncated ISI profile has no non-zero precursor ISI whereas in the case of the double-sided templates the truncated ISI profile may have non-zero precursor ISI.

[0179] In the preferred embodiments of the present invention, the parameters L_xand L_zare chosen to be sufficiently large such that the significant ISI components are not truncated. Truncating significant ISI components will increase the noise enhancement in the data recovery process and lead to a lower data estimation reliability. On the other hand, reducing the parameters L_xand L_zwill decrease the amount of computation needed in the data estimation process. Hence, there is a tradeoff of performance and complexity.

[0180] In the preceding discussion I have used the same vector argument, namely x, for the first arguments of the single-sided templates {circumflex over (q)}(•,•) and the double-sided templates ŝ(•,•,•). This has been done to simplify the discussion and should not be considered a restriction on the present invention. The present invention provides for the use of vector arguments of different lengths for the first arguments of the two types of templates. For reasons that will become apparent later, the second arguments of the two types of templates have the same lengths.

[0181] I will now examine the storage requirement of the templates. Recall that the arguments x, y, and z of the templates ŝ(x,y,z) and {circumflex over (q)}(x,y) are vectors of length L_x, L_yand L_z, respectively, with elements taken from the alphabet A_vof the encoded sequence {v_k}. If the alphabet A_vhas a size of M, then the number of templates ŝ(x,y,z) and {circumflex over (q)}(x,y) is M^L+L+Land M^L, respectively. The number of templates {circumflex over (q)}(x,y) that needs to be stored may be reduced by a factor of M^L−1by storing the scalar templates {circumflex over (q)}(x,y), where y can assume any value in the alphabet A_v, and constructing the vector templates {circumflex over (q)}(x,y) from the scalar templates. To describe this method, it proves useful to consider (x,y) as a single vector with a length of L_x+L_y. The first element of (x,y) is x₁; the L_x'th element is x_L; the (L_x+1)'th element is y₁; and the last or (L_x+L_y)'th element is y_L. Let x_i, i=0,1,2, . . . ,L_y−1, be a vector of L_xconsecutive elements taken from the vector (x,y) such that the last element of x_iis the (L_x+i)'th element of (x,y). For example, x₀=x, x₁=(x₂,x₃, . . . ,x_L,y₁), and x₂=(x₃,x₄, . . . , x_L,y₁,y₂), and so on. With this representation, the L_yelements of the vector template {circumflex over (q)}(x,y) can be approximated as: {circumflex over (q)}(x₀,y₁), {circumflex over (q)}(x₁,y₂), . . . , {circumflex over (q)}(x_L−1,y_L). The approximation is accurate since the truncated ISI profile for calculating single-sided templates has at most L_xpostcursor ISI components. Hence, the vector {circumflex over (q)}(x,y) may be constructed from the scalar templates {circumflex over (q)}(x,y). The number of vector templates {circumflex over (q)}(x,y) is M^L+Lwhile the number of scalar templates {circumflex over (q)}(x,y) is M^L+1. The preferred method is to store the scalar templates instead of the vector templates, so that the storage requirement is reduced by a factor of M^L−1.

[0182] A similar method may be used to construct the vector templates ŝ(x,y,z) from the scalar templates ŝ(x,y,z). Consider (x,y,z) as a single vector with a length of L_x+L_y+L_z: the first element of (x,y,z) is x₁the L_x'th element is x_L; the (L_x+1)'th element is y₁; the (L_x+L_y)'th element is y_L; the (L_x+L_y+1)'th element is z₁; and the last or (L_x+L_y+L_z)'th element is z_L. Let vector x_i, i=0,1,2, . . . ,L_y−1, be a vector of length L_xconstructed from the vector (x,y,z) such that the last element of x_iis the (L_x+i)'th element of (x,y,z). Let z_i, i=2,3, . . . ,L_y+1, be a vector of length L_zconstructed from the vector (x,y,z) such that the first element of z_iis the (L_x+i)'th element of (x,y,z). For example, z₂=(y₂,y₃, . . .), z₃=(y₃,y₄, . . .), and so on, and z_L+1=z. With this representation, the L_yelements of ŝ(x,y,z) can be approximated as: ŝ(x₀,y₁,z₂), ŝ(x₁,y₂,z₃), . . . , ŝ(x_L−1,y_L,z_L+1). Note that x₀=x and z_L+1=z. The approximation is accurate since the postcursor and precursor spans of the truncated ISI profile for calculating double-sided templates are at most L_xand L_z, respectively. The reduction in the storage requirement if the scalar templates ŝ(x,y,z) are stored instead of the vector templates ŝ(x,y,z) is a factor of M^L−1.

[0183] The number of scalar templates ŝ(x,y,z) and {circumflex over (q)}(x,y) that need to be stored is M^L+1+Land M^L+1, respectively. The number of templates is still substantial if M is moderately large. This may lead to a storage problem in some implementations. In one embodiment of the present invention the templates are pre-computed and preloaded into the data estimator. In another embodiment of the present invention, a template is computed when needed using truncated ISI profiles. The implementation choice may be based in part on the cost tradeoff of the hardware needed to store the pre-computed templates against the hardware/software needed to compute the templates. Usually, the storage of pre-computed templates is preferred if the alphabet size M is small, say, 2 or 4, and the ISI span is not too long. When the alphabet size is large or when the ISI span is long, it is more preferable to compute a template when it is needed. The storage of pre-computed templates is also more desirable for a non-linear modulation such as GMSK since the template computation is more involved than linear modulations.

[0184] I will now describe how the templates are used in the present invention. FIG. 16 shows a block diagram of a data estimator in one embodiment of the present invention comprising ISIC equalizer-decoder 1600. The channel output sequence {r_k} is supplied to partial equalizer 1602 to provide a partially equalized sequence {q_k}, which is supplied to ISIC decoder 1604 to provide an estimated data sequence {û_j}, where û_jrepresents an estimate of u_j. Template generator 1606 supplies single-sided templates {circumflex over (q)}(•,•) to partial equalizer 1602 and ISIC decoder 1604. Template generator 1606, after receiving the vector pair (x,y) from ISIC decoder 1604, supplies template {circumflex over (q)}(x,y) to the ISIC decoder. Similarly, template generator 1606, after receiving the vector (a,b) from partial equalizer 1602, supplies template {circumflex over (q)}(a,b) to the partial equalizer. The method with which ISIC decoder 1604 determines the vector pair (x,y) and how it uses the template {circumflex over (q)}(x,y) and the method with which partial equalizer 1602 determines the vector (a,b) and how it uses the template {circumflex over (q)}(a,b) are described later.

[0185] In one embodiment of the present invention the templates are pre-computed and preloaded into template generator 1606. In another embodiment of the present invention, a template is computed when needed from a set of coefficients representing a truncated ISI profile.

[0186] Partial equalizer 1602 removes substantially all of the precursor ISI from the channel output sequence {r_k} so that its output sequence {q_k} is substantially free of precursor ISI and leaves at least some of the postcursor ISI unequalized. Precursor equalizer 1402, which is a part of noiseless-channel-equalizer model 1408 discussed above, is a model of partial equalizer 1602. In contrast to partial equalizer 1602, a linear equalizer or a decision-feedback equalizer performs full equalization to remove both the precursor and postcursor ISI. By performing partial equalization instead of full equalization, the arrangement of the present invention reduces the amount of noise enhancement, thus achieving desirable result that the data estimation can be more reliable.

[0187] In one embodiment of the present invention, partial equalizer 1602 is implemented using a transversal filter and the equalizer tap weights are preloaded. These preloaded equalizer tap weights may be computed using the Wiener-Hopf equation and based on the estimated channel impulse response, as described above. More specifically, the preloaded equalizer tap weights may be determined in accordance with equation (45). This embodiment is preferred if the channel is substantially time invariant and that the estimated channel impulse response is substantially accurate.

[0188] In another embodiment of the present invention, partial equalizer 1602 adapts its equalizer tap weights. This embodiment is preferred if the channel is time varying or if an accurate estimate of the channel impulse response is unavailable a priori. In one embodiment of the present invention, the adaptation of the equalizer tap weights takes place during the reception of a training signal. The encoded symbols transmitted during the training portion of the signal are assumed known to partial equalizer 1602. Let {v_k}^TRdenote the training portion of the encoded sequence {v_k}. The training sequence {v_k}^TRis known to the data estimator and a replica of the sequence is stored in partial equalizer 1602. Let the number of precursor and postcursor tap weights be N₁and N₂, respectively. The numbers N₁and N₂are chosen to be sufficiently large to allow the partial equalizer to equalize the precursor ISI and selected postcursor ISI components. Let the tap weights be denoted as w_i, then the partial equalizer output for the k'th symbol interval is given by equation (2), which is rewritten in expanded form below:

[0189] q_k=w*_Nr_k−N+ . . . +w*₁r_k−1+w*₀r_k+w*₋₁r_k+1+ . . . +w*_−Nr_k+N.  (50)

[0190] Let a be the vector of L_xencoded symbols corresponding to the L_xchannel output samples immediately preceding r_k, i.e.,

[0191] a(v_k−L,v_k−L+1, . . . ,v_k−1).  (51)

[0192] Let b be the encoded symbol corresponding to channel output sample r_k, i.e.,

[0193] b=v_k.  (52)

[0194] Partial equalizer 1602 supplies the pair (a,b) to template generator 1606, which, as illustrated in FIG. 16, responds by supplying the template {circumflex over (q)}(a,b) to the partial equalizer. The template {circumflex over (q)}(a,b) is used by partial equalizer 1602 as the desired value of the equalizer output sample q_kto calculate the error signal:

[0195] e_k={circumflex over (q)}(a,b)−q_k.  (53)

[0196] The error signal is used to update the tap weights. An adaptation algorithm that can be used is the LMS algorithm described by equation (5).

[0197] In applications where the channel is time invariant (but with an unknown impulse response) or varying very slowly, the tap weights may be adapted only during the reception of the initial training signal and re-training signal inserted periodically into the data signal. In applications where it is unacceptable to send periodic re-training signals and tap weight adaptation is needed to track a slowly varying channel, the preferred embodiment of the present invention is to employ decision-directed adaptation using the estimated data sequence {û_j}. FIG. 17 shows a data estimator comprising ISIC equalizer-decoder 1700, which employs decision-directed adaptation during data recovery based on the output of ISIC decoder 1604. During reception of training sequences, the adaptation of partial equalizer 1702 is identical to that of partial equalizer 1602. During data reception, partial equalizer 1702 employs decision-directed adaptation. The estimated data sequence {û_j} is supplied to encoder 1704 to provide the re-encoded sequence {{circumflex over (v)}_k}, which is an estimated of the encoded sequence {v_k)}. Encoder 1704 performs the same steps as encoder 400. In other words, encoder 1704 and encoder 400 provide identical output sequences when supplied with identical input sequences. The re-encoded sequence {{circumflex over (v)}_k} is supplied to partial equalizer 1702, which calculates the vector a and the scalar b of the arguments of the template {circumflex over (q)}(a,b) according to

[0198] a=({circumflex over (v)}_k−L,{circumflex over (v)}_k−L+1, . . . ,{circumflex over (v)}_k−1)  (54)

[0199] and,

[0200] b={circumflex over (v)}_k.  (55)

[0201] The calculation of the error signal and the weight adaptation follow the same steps described above for adaptation during reception of training signals. When using decision-directed adaptation, partial equalizer 1702 includes a delay on the adaptation equal to the combined delay of ISIC decoder 1604 and encoder 1704.

[0202] The re-encoded sequence {{circumflex over (v)}_k} is used by partial equalizer 1702 to adapt its tap weights but is not used to generate its output. Hence, the partial equalizer is a linear feedforward equalizer, not a decision feedback equalizer. Errors in the re-encoded sequence {{circumflex over (v)}_k} can degrade the tap weight adaptation. However, the degradation can be reduced by slowing down the rate of adaptation, i.e., by using a smaller value for the time constant μ in equation (5). In contrast, a decision feedback equalizer cannot significantly reduce the effects of decision errors by decreasing the adaptation rate since the decisions are a part of the equalizer output. Therefore, the partial equalizers of the present invention do not suffer from error-propagation like that exhibited in decision feedback equalizers.

[0203] In applications such as mobile communications the channel may be varying too rapidly for the delay in adaptation introduced by ISIC decoder 1604 and encoder 1704 to be acceptable, it would be necessary either to send a re-training signal more frequently or to employ a means to generate the symbol estimate {circumflex over (v)}_kwith a reduced delay. In yet another embodiment of the present invention, a data estimator comprises ISIC equalizer-decoder 1800 shown in FIG. 18. ISIC equalizer-decoder 1800 includes full equalizer 1810 and slicer 1820. These two blocks are employed to generate symbol estimates with a reduced delay. Full equalizer 1810 removes both the precursor and postcursor ISI in the channel output sequence {r_k}. It is a linear equalizer and can be implemented using a transversal filter with a sufficient number of taps to cover the precursor and postcursor ISI spans. Full equalizer 1810 can also be implemented as a decision feedback equalizer. When implemented as a decision feedback equalizer, full equalizer 1810 will suffer from error propagation. However, the error propagation does not directly affect the data recovery since the output of the full equalizer is used only in adapting tap weights. The effects of the error propagation can be reduced by slowing down the rate of adaptation on full equalizer 1810 and partial equalizer 1802. Referring back to FIG. 18, slicer 1820 makes a symbol decision on each sample provided by full equalizer 1810 to provide the slicer-estimated sequence {{circumflex over (v)}_k}. Slicer 1820 employs maximum likelihood demodulation: the slicer output {circumflex over (v)}_kis set to be the symbol from the alphabet A_vof encoded symbols that is closest in Euclidean distance to the slicer input sample. Full equalizer 1810 and slicer 1820 are familiar to those skilled in the art. Note that I have chosen to use the same notation, {{circumflex over (v)}_k}, to denote the re-encoded sequence, which is the output of encoder 1704, and the slicer-estimated sequence, which is the output of slicer 1820. The choice seems logical since these sequences represent estimates of the encoded sequence {v_k}.

[0204] With reference to FIG. 18, the slicer-estimated sequence {{circumflex over (v)}_k} is supplied to both full equalizer 1810 and partial equalizer 1802 for use in adapting the respective equalizer tap weights. For full equalizer 1810, the error signal is computed as

[0205] e_k={circumflex over (v)}_k−q_k.  (56)

[0206] For partial equalizer 1802, the adaptation is identical to that of partial equalizer 1602 during reception of training sequences. During data recovery, partial equalizer 1802 employs decision-directed adaptation. The error signal is computed according to equation (53) and the pair (a, b) needed to specify the arguments of the template {circumflex over (q)}(a,b) is computed according to equations (54) and (55).

[0207] The three embodiments of the present invention for data estimator shown in FIGS. 16, 17, and 18, comprising ISIC equalizer-decoders 1600, 1700, and 1800, respectively, differ in the methods used to adapt the tap weights of partial equalizers 1602, 1702, and 1802. These three data estimators have the same the ISIC decoder, block 1604, and the same template generator, block 1606.

[0208] In this exemplary description of the present invention, the partial equalizer is assumed to operate at the rate of one sample per symbol. Such an equalizer is generally referred to as a symbol-spaced equalizer. Those skilled in the art should realize that the partial equalizer might employ fractional tap spacing. See the article: “Fractionally-Spaced Equalization: An Improved Digital Transversal Equalizer,” by R. Gitlin and S. Weinstein, The Bell System Technical Journal, Vol. 60, No. 2, pp. 275-296, February 1981. For example, the equalizer taps may be spaced at one half of the symbol duration. In that case, the channel output sequence {r_k} will be at twice the symbol rate so that there will be two channel output samples for each symbol interval and the samples are evenly spaced.

[0209] I will now describe ISIC decoder 1604, which advantageously processes the partially equalized sequence {q_k} to provide the estimated data sequence {û_j}. The ISIC decoder simultaneously performs trellis decoding and compensation of the postcursor ISI. ISIC decoder 1604 has the same number of trellis states as a trellis decoder that those skilled in the art would normally use to decode an ISI-free trellis-encoded signal. In other words, the presence of ISI at the input to ISIC decoder 1604 has no effect on the required number of trellis states, which is uniquely determined by the trellis code used in trellis encoder 402. I will illustrate the ISIC decoding algorithm by using trellis diagrams for the constraint length 3, rate 1/2 code, whose encoding trellis is shown in FIG. 5. FIG. 19 is a decoding trellis derived from FIG. 5. For simplicity, the trellis branches in FIG. 19 show only the encoder output bits while suppressing the input bits. FIG. 20 is a decoding trellis derived from FIG. 19 with the branches labeled by the encoded symbols v⁽¹⁾v⁽²⁾at the output of mapper 404 instead of the encoded bits c⁽¹⁾c⁽²⁾at the output of trellis encoder 402. The mapping of trellis-encoded bit c to encoded symbol v used to derive FIG. 20 from FIG. 19 is antipodal mapping: set v=1 if c=1; and set v=−1 if c=0.

[0210] FIG. 20 shows that at trellis depth (k−1) there are four paths, known as survivor paths, one terminating at each of the four states. Associated with each survivor path is a path metric, P_k−1(S), where S is an integer representing the state where the path terminates. A state with a binary representation of 10, for example, has an integer representation S=2. Both the binary and integer representations are shown in FIG. 20. At trellis depth k, the ISIC decoder must choose for each of the states a survivor path from the two paths converging at that state. Suppose S is the state for which a survivor path is to be selected at trellis depth k. The selection of the survivor path is performed according to these steps: (i) calculate the branch metrics B₁(S) and B₂(S) for the two branches terminating at state S; (ii) calculate the temporary path metrics P_k⁽¹⁾(S)=P_k−1(S₁)+B₁(S) and P_k²(S)=P_k−1(S₂)+B₂(S), where S₁and S₂are the states where the paths terminate at trellis depth (k−1); (iii) select path 1 as the survivor path if P_k⁽¹⁾(S)<P_k⁽²⁾(S) and set P_k(S)=P_k⁽¹⁾(S); otherwise select path 2 as the survivor path and set P_k(S)=P_k⁽²⁾(S) For paths 2001 and 2002, shown in FIG. 20 with some branches darkened, the state under discussion at trellis depth k is S=1; the state at trellis depth (k−1) is S₁=2 for path 2001 and S₂=3 for path 2002.

[0211] The length of each survivor path is D_Mbranches. As is well known to those skilled in the art, D_Mis usually set to be four or five times the constraint length of the trellis code. Each survivor path keeps track of the path metric and the L_xencoded symbols associated with the past branches. In addition, associated with each survivor path is the information that identifies the data bit or bits for each branch of the survivor path. After a survivor path has been selected for each of the trellis states at trellis depth k, ISIC decoder 1604 identifies the path with the smallest path metric, and adds the data bits corresponding oldest branch of the smallest-path-metric path to the estimated data sequence {û_j}. The data bit information associated with the old branch of each survivor path is then discarded and the data bit information is advantageously updated with the data bit information for the newest branch of each survivor path. ISIC decoder 1604 is now ready to perform the processing to advance from trellis depth k to trellis depth (k+1).

[0212] According to one embodiment of the present invention, ISIC decoder 1604 computes the branch metrics using the single-sided templates {circumflex over (q)}(•,•). In describing a decoding trellis at trellis depth k, it is customary to refer to the branches terminating at the states at trellis depth k as the current branches and those terminating at the states at trellis depths (k−1), (k−2), and so on as past branches. The vector y of the vector argument of the single-sided template {circumflex over (q)}(x,y) is the vector of encoded symbols associated with the current branch and the vector x is the vector of the symbols associated with the past branches connected to that particular current branch. If the trellis code is a rate n_u/n_cbinary convolutional code, the vector y has a length L_y=n_c, since each branch has n_cencoded symbols, and y=(v⁽¹⁾,v(2), . . . ,v⁽ⁿ⁾). If the trellis code is a TCM code, each branch has one encoded symbol, hence the vector y has a length of one, i.e., it is a scalar. The length of the vector x could be any integer value L_xbut the preferred embodiment is to set L_x, which defines the span of the postcursor ISI in the truncated ISI profile, to be sufficiently large such that the significant postcursor ISI components of the channel are not truncated. A length smaller than the postcursor ISI span of the channel can be used for L_xbut this would lead to the truncation of some significant postcursor ISI components of the channel and result in reduced data estimation reliability. For the exemplary trellis shown in FIG. 20, the branches corresponding to the vector pair (x,y) are shown darkened for paths 2001 and 2002. In this example, the length of the vector x is set to be four encoded symbols. For path 2001, x=x₁=(−1,−1,1,1) and y=y₁(1,−1); and for path 2002, x=x₂=(−1,1,1,−1) and y=y₂=(−1,1). Let the vector q denote the output of the partially equalized sequence {q_k} for the transition from trellis depth (k−1) to trellis depth k. The branch metric is equal the squared Euclidean distance between {circumflex over (q)}(x,y) and q:

[0213] B=|{circumflex over (q)}(x,y)−q|².  (57)

[0214] Suppose {circumflex over (q)}(x,y)−q=d=(d₁,d₂, . . . ,d_L) then B=|d|²=|d₁|²+|d_2|²+ . . . +|d_L|². For the example shown in FIG. 20, the branch metrics are:

[0215] B₁(S)=|{circumflex over (q)}(x₁,y₁)−q|²  (58)

[0216] and,

[0217] B₂(S)=|{circumflex over (q)}(x₂,y₂)−q|².  (58)

[0218] Those skilled in the art should recognize that the above-described ISIC decoding algorithm is the same as the classical Viterbi algorithm for decoding a trellis-encoded signal with the exception that the branch metric is computed differently for the present invention. Those skilled in the art should also realize that an approximation to the branch metric might be used to reduce the implementation complexity, possibly at the expense of degraded data estimation. For example, the branch metric B=|d₁|+|d₂|+ . . . +|d_L| may be used, where the vector (d₁,d₂, . . . ,d_L)=d={circumflex over (q)}(x,y)−q. This branch metric does not require a squaring operation and is therefore simpler to implement than the squared Euclidean distance metric.

[0219] The three embodiments of the present invention for ISIC equalizer-decoders shown in FIGS. 16, 17, and 18, as blocks 1600, 1700, and 1800, respectively, employ a set of fixed single-sided templates {circumflex over (q)}(•,•). Due to the time-varying behavior of some channels or inaccurate channel modeling, the actual channel impulse response can be different from the truncated ISI profile used to compute the templates {circumflex over (q)}(•,•). In that case, partial equalizers 1602, 1702, and 1802 will remove the residual postcursor ISI not accounted for by {circumflex over (q)}(•,•). This could lead to a substantial increase in noise enhancement if the residual postcursor ISI that the partial equalizer has to remove is substantial. In that case, an improvement in data estimation reliability can be realized if the templates {circumflex over (q)}(•,•) are advantageously updated to include the residual postcursor ISI. In order to update the templates, it is necessary to estimate the ISI profile of the channel.

[0220] FIG. 21 shows a block diagram of ISIC equalizer-decoder 2100 in one embodiment of the present invention. ISIC equalizer-decoder 2100 differs from ISIC equalizer-decoder 1600 in the following manner: (i) template generator 2106 has the capability to update the templates while template generator 1606 does not; (ii) there is an additional block: ISI profile estimator 2108; and (iii) partial equalizer 2102 supplies to ISI profile estimator 2108 a sequence {v_k}^TR, which is a replica of the training portion of encoded sequence {v_k}, while partial equalizer 1602 does not provide {v_k}^TRas an output. ISI profile estimator 2108 is used to estimate the ISI profile of the channel. With reference to FIG. 21, the estimated ISI profile is specified by the sequence of coefficients {ĝ_i}, which is supplied to template generator 2106.

[0221] In one exemplary embodiment of the present invention, ISI profile estimator 2108 employs a transversal filter with N_xpostcursor taps and N_zprecursor taps for a total of (N_x+N_z+1) taps. The parameters N_xand N_zare set equal to the expected spans of the postcursor and precursor ISI, respectively. The tap weights of the transversal filter are {ĝ_i}, i=−N_z, . . . ,0, . . . , N_x. As stated above, the tap weights {ĝ_i} are the estimates of the ISI profile and supplied to template generator 2106 by ISI profile estimator 2108. The estimation technique employed by ISI profile estimator 2108 is similar to the channel estimation algorithm described in the book: Digital Communications, by J. Proakis, McGraw-Hill, 1983, pp. 410-412.

[0222] The estimator input sequence {{tilde over (s)}_k} for the transversal filter's tapped delay line is set to be the replica of the training portion of encoded sequence {v_k} provided by partial equalizer 1602, i.e., {tilde over (s)}_k=v_k. ISI profile estimator 2108 multiplies the estimator input symbols {{tilde over (s)}_k} by the estimator tap weights {ĝ_i} and adds the resulting products to provide an estimated channel output sample: $\begin{array}{cc}{\tilde{r}}_k=\sum _{i=-N_z}^{N_x}{\hat{g}}_i{\tilde{s}}_{k-i}& \left(60\right)\end{array}$

[0223] ISI profile estimator 2108 computes an error signal by subtracting the estimated channel output sample {tilde over (r)}_kfrom the channel output sample r_k:

[0224] {tilde over (e)}_k=r_k−{tilde over (r)}_k.  (61)

[0225] The error signal is used to update the tap weights. Let the (N_x+N_z+1)-by-one column vector ĝ=(ĝ_−N, . . . ,ĝ₀, . . . ,ĝ_N)^Tbe the tap weight vector and denote the tap weight vector at time k as ĝ_k. A similar notation is used for the vector of estimator input symbols: {tilde over (s)}_k=({tilde over (s)}_k+N, . . . ,{tilde over (s)}_k, . . . ,{tilde over (s)}_k−N)^T. Note that the vector {tilde over (s)}_khas the elements written in the reverse time order, with the newest sample listed first. With this representation, the estimated channel output sample can be written as

[0226] {tilde over (r)}_kĝ_k^T{tilde over (s)}_k.  (62)

[0227] The tap weight vector {tilde over (g)}_k+1for use in the next symbol interval to process estimator input sequence {{tilde over (s)}_k} is computed from the current tap weight vector ĝ_kaccording to

[0228] ĝ_k+1=ĝ_k+β{tilde over (s)}_{k*{tilde over (e)}k}  (63)

[0229] where β is an adaptation time constant that controls the rate of adaptation, chosen to work with the expected rate of change of the channel.

[0230] ISI profile estimator 2108 supplies the tap weights {ĝ_i} as the estimated ISI profile to template generator 2106 for use in updating the templates. Template generator 2106 uses the estimated ISI profile as the channel estimate {ĥ_i}, i.e., ĥ_i=ĝ_i, which is truncated according to equation (42) to provide the truncated ISI profile {{tilde over (h)}_i} for use in generating updated single-sided templates.

[0231] Updating the templates can be computationally demanding. If the channel varies slowly, it is not necessary to update the templates every symbol period. In one embodiment of the present invention, template generator 2106 computes the difference between the estimated ISI profile {ĝ_i} and the current channel estimate {ĥ_i} and compares the difference to two preset thresholds to determine if it is necessary to update the templates. An update of the templates is determined to be necessary if one or both of the following conditions are met:

[0232] |ĥ₀−ĝ₀|²>λ₀  (64)

[0233] $\begin{array}{cc}\left[\sum _{i=-N_z}^{-1}{\left|{\hat{h}}_i-{\hat{g}}_i\right|}^2+\sum _{i=1}^{N_x}{\left|{\hat{h}}_i-{\hat{g}}_i\right|}^2\right]>{\lambda }_1& \left(65\right)\end{array}$

[0234] where λ₀and λ₁are two preset thresholds. The first condition states that the tap weight ĝ₀deviates more than the allowed amount λ₀from the current estimate of the channel gain on the desired signal. The second condition states that the residual ISI components have a total power exceeding the allowed amount λ₁. If template generator 2106 has determined that an update of the templates is necessary, it proceeds to perform the update.

[0235] FIG. 22 shows a block diagram of ISIC equalizer-decoder 2200 in one embodiment of the present invention. ISIC equalizer-decoder 2200 differs from ISIC equalizer-decoder 2100 in that the former employs decision-directed ISI profile estimation as well as estimation based on known training signals whereas the latter employs only estimation based on known training signals. ISIC equalizer-decoder 2200 uses the same arrangement as ISIC equalizer-decoder 1700 for obtaining the re-encoded sequence {{circumflex over (v)}_k}. Partial equalizer 2202 supplies to ISI profile estimator 2108 the sequence {v_k}^TR, a replica of the training portion of the encoded sequence {v_k}, during reception of the training signals and the estimated encoded sequence {{circumflex over (v)}_k} during data reception. During reception of the training signals, ISIC equalizer-decoder 2200 operates in the same way as ISIC equalizer-decoder 2100. Specifically, ISIC equalizer-decoder 2200 sets the estimator input sequence {{tilde over (s)}_k} to be the replica of the training portion of encoded sequence {v_k}, i.e., {tilde over (s)}_k=v_k. During reception of data signals, ISIC equalizer-decoder 2200 sets the estimator input sequence {{tilde over (s)}_k} to be the re-encoded sequence {{circumflex over (v)}_k} i.e., {tilde over (s)}_k={circumflex over (v)}_k.

[0236] ISIC equalizer-decoder 2100 is the preferred embodiment for applications where the channel's impulse response is varying very slowly so that the tap weights may be adapted only during the reception of the initial training signal and re-training signal inserted periodically into the data signal. In applications where it is unacceptable to send periodic re-training signals and tap weight adaptation is needed to track a slowly varying channel, the preferred embodiment of the present invention is ISIC equalizer-decoder 2200. In applications such as mobile communications, the channel may be varying too rapidly for the delay introduced by ISIC decoder 1604 and encoder 1704 to be acceptable, the preferred embodiment of the present invention is ISIC equalizer-decoder 2300 shown in FIG. 23. ISIC equalizer-decoder 2300 includes full equalizer 1810 and slicer 1820 to derive the slicer-estimated sequence {{circumflex over (v)}_k} at a reduced delay in an arrangement identical to that used by ISIC equalizer-decoder 1800. ISIC equalizer-decoder 2300 differs from ISIC equalizer-decoder 2200 in the method for generating the sequence {{circumflex over (v)}_k} and that partial equalizer 2302 has an interface with slicer 1820 while partial equalizer 2202 has an interface with encoder 1704.

[0237] Table 2 summarizes the exemplary ISIC equalizer-decoder embodiments of the present invention to illustrate the similarities and differences in the partial equalizer adaptation, ISI profile estimation, and template updating among the embodiments.

[0238] FIG. 24 shows ISIC equalizer-decoder 2400 that will be used in the embodiments of the present invention to be described next. ISIC equalizer-decoder 2400 is one of the six ISIC equalizer-decoder embodiments described above: block 1600 of FIG. 16, block 1700 of FIG. 17, block 1800 of FIG. 18, block 2100 of FIG. 21, block 2200 of FIG. 22, and block 2300 of FIG. 23. In the embodiments of the present invention to be described next, the template generator will supply both the single-sided templates {circumflex over (q)}(•,•) and the double-sided templates ŝ(•,•,•). When used with these embodiments, template generators 1606 and 2106 will be able to provide both types of templates as needed. The inputs and outputs of ISIC equalizer-decoder 2400 are shown in FIG. 24. The vectors (a,b,c), (x,y,z), and (x,y) are inputs to template generators 1606 and 2106, which respond with the templates ŝ(a,b,c), ŝ(x,y,z), and {circumflex over (q)}(x,y). The sequence {r_k} is the channel output sequence described previously. The sequence {Û_j} is the output sequence {û_j} of ISIC decoder 1604 renamed to signify that the estimated-data-sequence output of ISIC equalizer-decoder 2400 will not be supplied directly to the data sink. The training sequence {v_k}^TRis an output of partial equalizers 1602, 1702, 1802, 2102, 2202, or 2302 and the estimated sequence {{circumflex over (v)}_k} is another output of partial equalizers 1702, 1802, 2202, or 2302.

[0239] FIG. 25 shows a block diagram of one embodiment of a data estimator of the present invention. The sequence {Û_j} represents the output sequence of ISIC decoder 1604, which is a block within ISIC equalizer-decoder 2400. For the arrangement shown in FIG. 25, the sequence {Û_j} will be referred to as a sequence of interim data decisions to signify that Û_jwill be used as a tentative data estimate. The sequence of interim data decisions {Û_j} is supplied to decision-directed (DD) ISIC decoder 2514 as an aid to the decoding. Double-sided partial equalizer 2512 advantageously processes the channel output sequence {r_k} to provide a double-sided-partially-equalized sequence {Q_k}. In one embodiment of the present invention, double-sided partial equalizer 2512 is a transversal filter configured to equalize only some of the ISI, leaving the rest of the precursor and postcursor ISI unequalized. In particular, double-sided partial equalizer 2512 removes only the ISI components of the channel not accounted for by the templates ŝ(•,•,•). These are the ISI components that have been set to zero in computing the truncated ISI profile. Let the number of precursor and postcursor equalizer taps of double-sided partial equalizer 2512 be M₁and M₂, respectively. The parameters M₁and M₂are chosen to be sufficiently large to enable the double-sided equalizer to remove the ISI components not accounted for by the templates ŝ(•,•,•). Let the equalizer tap weights be represented by the vector W=(W_−M, . . . ,W₀, . . . ,W_M)^T, which has (M₁+M₂+1) elements. Denote the tap weight vector at time k as W_k. A similar notation is used on the equalizer input, thus r_k=(r_k+M, . . . ,r_k, . . . ,r_k−M)^T. With this representation, the output of double-sided partial equalizer 2512 can be written as

[0240] Q_k=W_k^Hr_k.  (66)

[0241] Like the partial equalizer, the double-sided partial equalizer may have fixed or adaptive tap weights. The choice depends on the time-varying characteristics of the channel, as discussed above. To adapt the equalizer tap weights, double-sided partial equalizer 2512 computes the vector (a,b,c) for each symbol interval. During reception of the training symbols, double-sided partial equalizer 2512 computes the vector a and the scalar b according to equations (51) and (52), respectively, and computes the vector c according to

[0242] c=(v_k+1,v_k+2, . . . ,v_k+L).  (67)

[0243] During data reception, double-sided partial equalizer 2512 computes the vector a and the scalar b according to equations (54) and (55), respectively, and the vector c according to

[0244] c=({circumflex over (v)}_k+1,{circumflex over (v)}_k+2, . . . ,v_k+L).  (68)

[0245] The vector (a,b,c) is supplied to ISIC equalizer-decoder 2400, which returns with the template ŝ(a,b,c). In the next step, double-sided partial equalizer 2512 computes an error signal according to

[0246] e_k=ŝ(a,b,c)−Q_k.  (69)

[0247] The error signal is used to update the tap weights. An adaptation algorithm that can be used is the LMS algorithm:

[0248] W_k+1=W_k+αr_ke*_k  (70)

[0249] where α is an adaptation time constant. Note that if the templates ŝ(•,•,•) perfectly account for the all of the ISI profile of the channel, the equalizer tap weights will converge to W₀=1 and W_i=0 for i≠0. If the channel has an impulse response that differs from the truncated ISI profile used to compute the templates, some or all of the W_ifor i≠0 will be non-zero. Since double-sided partial equalizer 2512 removes only the ISI components not accounted for by the templates ŝ(•,•,•), the noise enhancement introduced by the equalizer is smaller than that introduced by the partial equalizer of ISIC equalizer-decoder 2400. In other words, the amount of equalizer-added noise in the double-sided-partially-equalized sequence {Q_k} is smaller than that in the single-sided-partially-equalized sequence {q_k}. For this reason, it is expected that the data sequence estimated by decoding the sequence {Q_k} should be more reliable than that estimated by decoding {q_k}. With reference to FIG. 25, it is expected that {û_j}, the data sequence estimated by DD-ISIC decoder 2514, is more reliable than {Û_j}, the data sequence estimated by ISIC decoder 1604 within ISIC equalizer-decoder 2400. My computer simulation results have confirmed this hypothesis.

[0250] DD-ISIC decoder 2514 simultaneously decodes the trellis-encoded signal and removes the precursor and postcursor ISI. Like ISIC decoder 1604, DD-ISIC decoder 2514 has the same number of decoder states as a trellis decoder that those skilled in the art would normally use to decode an ISI-free trellis-encoded signal. In other words, the presence of precursor and postcursor ISI at the input the DD-ISIC decoder 2514 has no effect on the required number of trellis states, which is uniquely determined by the trellis code used in trellis encoder 402. DD-ISIC decoder 2514 makes uses of the double-sided templates ŝ(•,•,•). In contrast, ISIC decoder 1604 uses the single-sided templates {circumflex over (q)}(•,•). DD-ISIC decoder 2514 calculates the vector arguments x and y using the same method used by ISIC decoder 1604, and calculates the vector argument z by using the sequence of interim data decisions {Û_j} supplied by ISIC equalizer-decoder 2400.

[0251] I will illustrate the DD-ISIC decoding algorithm by using trellis diagrams for the constraint length 3, rate 1/2 code, whose encoding trellis is shown in FIG. 5. FIG. 26 is a decoding trellis showing four survivor paths at trellis depth (k−1), one terminating at each of the four states. Associated with each survivor path is a path metric. Let P_k−1(S), where S is an integer representing the state where the path terminates. At trellis depth k, DD-ISIC decoder 2514 must choose for each of the states a survivor path from the two paths converging at that state. Suppose S is the state for which a survivor path is to be selected at trellis depth k. The selection of survivor path is performed according to these steps: (i) calculate the branch metrics B₁(S) and B₂(S) for the two branches terminating at state S; (ii) calculate the temporary path metrics P_k⁽¹⁾(S)=P_k−1(S₁)+B₁(S) and P_k⁽²⁾(S)=P_k−1(S₂)+B₂(S), where S₁and S₂are the termination states of the paths at trellis depth (k−1); (iii) select path 1 as the survivor path if P_k⁽¹⁾(S)<P_k⁽²⁾(S) and set P_k(S)=P_k⁽¹⁾(S); otherwise select path 2 as the survivor path and set P_k(S)=P_k⁽²⁾(S). For paths 2601 and 2602, shown in FIG. 26 with some branches darkened, the state under discussion at trellis depth k is S=1 and the state at trellis depth (k−1) is S₁=2 for path 2601 and S₂=3 for path 2602. The algorithm is similar to that for ISIC decoder 1604. The difference is the method used to calculate the branch metrics B₁(S) and B₂(S).

[0252] According to one embodiment of the present invention, DD-ISIC decoder 2514 computes the branch metrics using the double-sided templates ŝ(x,y,z). For the vector argument (x,y,z), the vector x, of length L_x, is the vector of encoded symbols associated with the past branches, the vector y, of length L_y, is the vector of encoded symbols associated with the current branch, and the vector z, of length L_z, is the vector of encoded symbols associated with the future branches. Here, a future branch is a branch in the trellis extending beyond the current trellis depth. For the example shown in FIG. 26, L_x=L_z=4. Since the decoder is for a rate 1/2 binary convolutional code, L_y=2. The vectors x and y are computed using the same method as used by ISIC decoder 1604. For path 2601 in FIG. 26, x=x₁=(−1,−1,1,1) and y=y₁=(1,−1); and for path 2602, x=x₂=(−1,1,1,−1) and y=y₂=(−1,1). The vector z is calculated based on the interim data decisions {Û_j}. DD-ISIC decoder 2514 assumes that {Û_j} is identical to the data sequence {u_j}. For the example shown in FIG. 26, it is assumed that Û_k+1=1 and Û_k+2=0. An input bit of 1 for the (k+1)'th bit interval, i.e., Û_k+1=1, takes the decoding trellis from state 1 at trellis depth k to state 2 at trellis depth (k+1), and an input bit of 0 for the (k+2)'th bit interval, i.e., Û_k+2=0, takes the state back to state 1 at trellis depth (k+2). This path segment, labeled 2603, is shown in the figure as two dashed lines. The output symbols for path segment 2603 is z=(−1,−1,1,−1). DD-ISIC decoder 2514 supplies the vectors arguments (x₁,y₁,z) and (x₂,y₂,z) to ISIC equalizer-decoder 2400, which returns the templates ŝ(x₁,y₁,z) and ŝ(x₂,y₂,z). These templates are used by DD-ISIC decoder 2514 to compute the branch metrics for paths 2601 and 2602 according to

[0253] B₁(S)=|ŝ(x₁,y₁,z)−Q|²  (71)

[0254] and,

[0255] B₂(S)=|ŝ(x₂,y₂,z)−Q|²  (72)

[0256] where Q is the vector of double-sided-partially-equalized symbols for the transition from trellis depth (k−1) to trellis depth k. The rest of the decoding uses the same method as that used by ISIC decoder 1604.

[0257] I will now describe one embodiment of the present invention that employs concatenated coding. Well known to those skilled in the art as a technique for improving the data estimation reliability, concatenated coding employs two FEC codes in cascade. FIG. 27 shows encoder 2700 which implements concatenated coding. The data sequence {u_j} is supplied to outer FEC encoder 2720, which can be either a block encoder or a trellis encoder. In one embodiment of the present invention, outer FEC encoder 2720 employs a Reed-Solomon (RS) code, which is well known to those skilled in the art.

[0258] RS encoding and decoding work with code symbols that are m-bit words. A common code symbol length is m=8, which I will assume for an exemplary embodiment. The code block length n of a RS code is related to m by the relationship: n=2^m−1. For 8-bit code symbols, n=255 so that there are 255 code symbols, or 2040 bits, in a code block. Another parameter needed to define a RS code is k, which is the number of m-bit data symbols being encoded into n code symbols. This is generally referred to as an (n,k) RS code. The rate of the code is k/n. The code is capable of correcting t=(n−k)/2 code symbol errors. For example, a (255, 245) RS code has a code rate of about 0.96 and is capable of correcting up to five code symbol errors in a code block.

[0259] Referring back to FIG. 27, the output bit sequence of outer FEC encoder 2720 is supplied to interleaver 2730 to provide the interleaved bit sequence {U_i}. The interleaved bit sequence is supplied to trellis encoder 402, whose output is supplied to mapper 404 to provide the encoded sequence {v_k}. Trellis encoder 402 and mapper 404 have been described above in detail. Interleaver 2730 provides an output sequence by permuting the s order of the elements of the input sequence. Interleaver types include block interleavers, convolutional interleavers, and pseudo-random interleavers, see the book: Principles of Digital Communication and Coding, by A. Viterbi and J. Omura, McGraw-Hill, 1979, pg. 111 and pp. 114-116, and U.S. Pat. No. 4,547,887, “Pseudo-Random Convolutional Interleaving,” issued to S. Mui on Oct. 15, 1985. For this exemplary embodiment, I will use a block interleaver. Interleaving, coupled with deinterleaving in the data estimator, is employed to break up the error bursts created by the channel and clusters of errors typically found at the output of trellis decoders. Error bursts at the output of trellis decoders are mostly a few bits long. An error burst will most likely affect one or two 8-bit code symbols. Therefore, to break up error bursts at the output of a trellis decoder, an interleaver size of 2×n code symbols should be sufficient. Channel fading considerations may increase the size of the interleaver needed. ISI can also lengthen the error bursts. A larger interleaver could improve the data recovery reliability but will also increase the delay in providing the estimated data to the data sink. Such a tradeoff is familiar to those skilled in the art.

[0260] Suppose the interleaver size is J×n code symbols. Interleaver 2730 divides the input sequence into super-blocks each containing J code blocks. The interleaver writes the code symbols sequentially into memory location 1 through J×n, i.e., the code symbols from a first code block of a super-block are put into memory locations 1, 2, . . . , n, where each memory location holds m bits (for the current example, m=8), and the code symbols from the second code block of the super-block are put into memory locations n+1, n+2, . . . , 2n, and so on, so that the code symbols from the last code block of the super-block are put into memory locations (J−1)n+1, (J−1)n+2, . . . , J×n. The output of interleaver 2730 is the sequence of code symbols from memory locations 1, n+1, . . . , (J−1)n+1, 2, n+2, . . . , (J−1)n+2, . . . , n, 2×n, . . . , J×n. The process repeats for the next super-block of J code blocks.

[0261] For an interleaver size of 2×n code symbols, for example, each super-block is composed of two code blocks. Interleaver 2730 writes the code symbols from a first code block into memory location 1, 2, . . . , n, and the code symbols from the second code block into memory location n+1, n+2, . . . , 2n; and the interleaver output is the sequence of code symbols from memory locations 1, n+1, 2, n+2, . . . , i, n+i, . . . , n, and 2×n. The process repeats for the next super-block of two code blocks.

[0262] FIG. 28 shows a block diagram of a data estimator of one embodiment of the present invention for recovering the data that has been encoded by encoder 2700 and sent over a channel. The channel output sequence {r_k} is supplied to ISIC equalizer-decoder 2400 to provide an output sequence {Û_j}, which is supplied to deinterleaver 2816, whose output sequence is decoded by outer FEC decoder 2818 to provide the estimated data sequence {û_j}, which is supplied to the data sink. With reference to FIGS. 27 and 28, {Û_i} is an estimate of the outer-FEC-encoded sequence {U_i} and {û_j} is an estimate of the data sequence {u_j}. The use of different indices i and j signifies that the sequences are of different lengths. Deinterleaver 2816 puts the bits into the right order by first dividing the estimated sequence of outer-FEC-encoded symbols {Û_i} into super-blocks each containing J RS code blocks. Next, the deinterleaver groups the bits into m-bit code symbols and writes the code symbols sequentially into memory locations 1 through J×n. Finally, deinterleaver 2816 generates an output sequence by reading from the memory in the following order: 1, J+1, 2J+1, . . . , (n−1)J+1 to form the first code block of the super-block. The second code block of the super-block is formed by reading the memory in the following order: 2, J+2, 2J+2, . . . , (n−1)J+2. The last or the J'th code block of the super-block is formed by reading the memory in the following order: J, 2×J, 3×J, . . . , n×J. The deinterleaved sequence is supplied to outer FEC decoder 2818, which decodes each code block of n code symbols to provide k data symbols to form a part of the estimated data sequence {û_j}. For the current embodiment of the present invention, outer FEC decoder 2818 is a RS decoder. The theory and implementation of RS decoders are well known to those skilled in the art.

[0263] Referring back to FIG. 25, errors in the sequence of interim data decisions {Û_j} will cause DD-ISIC decoder 2514 to calculate an incorrect vector z, which in turn will lead to the use of incorrect templates ŝ(x,y,z) in the branch metrics calculation, resulting in a reduction in the data estimation reliability. I will describe later two other embodiments of the present invention for improving the accuracy of the sequence supplied to DD-ISIC decoder 2514 for use as the interim data decisions. FIG. 29 shows a block diagram of a data estimator of yet another embodiment of the present invention for recovering the data that has been encoded by encoder 2700 and sent over a channel. Deinterleavers 2816-1 and 2816-2 are replicas of deinterleaver 2816, outer FEC decoders 2818-1 and 2818-2 are replicas of outer FEC decoder 2818, outer FEC encoder 2720-1 is a replica of outer FEC encoder 2720, and interleaver 2730-1 is a replica of interleaver 2730. The channel output sequence {r_k} is supplied to ISIC equalizer-decoder 2400, whose output sequence {Û_i} is advantageously processed by a cascade of deinterleaver 2816-1 and outer FEC decoder 2818-1 to provide the sequence {Ũ_j}. The sequence {Ũ_j} is advantageously processed by a cascade of outer FEC encoder 2720-1 and interleaver 2730-1 to provide the sequence of interim data decisions {Ũ_i}, which is supplied to DD-ISIC decoder 2514 for use as the interim data decisions in the calculation of the vector z in the argument of the double-sided template ŝ(x,y,z), as described above. The output of DD-ISIC decoder 2514, denoted as {G_i} in FIG. 29, is advantageously processed by a cascade of deinterleaver 2816-2 and outer FEC decoder 2818-2 to provide the estimated data sequence {û_j}. Due to the use of concatenated coding in the arrangement shown in FIG. 29, the sequence of interim data decisions {Ũ_i} is more reliable than the sequence of interim data decisions {Û_j} of FIG. 25. The use of a more reliable sequence of interim data decisions will improve the performance of DD-ISIC decoder 2514.

[0264] A characteristic of RS decoding is that whenever there is a decoding error, i.e. whenever the decoded code block is not a perfect replica of the encoded code block, the decoded sequence usually has more code symbol errors than the input sequence to the decoder. As noted above, the performance of DD-ISIC decoder 2514 is degraded by errors in the interim data decisions used in the computation of the vector z in the argument of the double-sided template ŝ(x,y,z). It is therefore desirable to be able to detect RS decoding errors and reduce the effect of such errors on the performance of DD-ISIC decoder 2514. I will now describe a method to detect RS decoding errors in order to improve the reliability of the interim data decisions supplied to DD-ISIC decoder 2514. This method uses an error-detecting code in addition to the concatenation of forward-error-correction codes.

[0265] FIG. 30 is a block diagram of encoder 3000 of one embodiment of the present invention that employs error detection. The data sequence {u_j} is supplied to error-detection encoder 3010. The output of the error-detection encoder is advantageously processed by the cascade of outer FEC encoder 2720, interleaver 2730, trellis encoder 402, and mapper 404, using the same method described above for encoder 2700. Error-detection encoder 3010 encodes the input sequence using a block code. In particular, the error-detection encoder employs an (n₁,k₁) error-detection code to encode k₁data symbols into n₁code symbols by generating and appending (n₁−k₁) parity-check symbols to the k₁data symbols. This type of error-detection coding is called systematic coding where the encoded block consists of the data symbols and the parity-check symbols. For systematic codes, calculating the parity-check symbols from the observed data symbols and comparing the calculated parity-check symbols to the observed parity-check symbols will detect errors. The theory of error-detection codes is well known to those skilled in the art.

[0266] In one embodiment of the present invention, the error-detection code is an (n₁,k₁) RS code or a shortened RS code. As described above, outer FEC encoder 2720 employs an (n,k) RS code in one embodiment of the present invention. Both (n₁,k₁) and (n,k) RS codes have the same code symbol length m, where m and n are related by n=2^m−1. It is convenient to choose n₁such that it is either equal to k or a sub-multiple of k. If n₁=k, then error-detection encoder 3010 encodes a block of k₁code symbols into k code symbols, which are then encoded by outer FEC encoder 2720 into n code symbols. In such an arrangement, the error-detection code is used to detect a decoding error in the outer FEC decoder. If n₁=k/N, where N is an integer such that k is a multiple of N, then outer FEC encoder 2720 encodes every group of N code blocks provided by error-detection encoder 3010 into a RS code block of length n. In this arrangement, the error-correction code is capable of detecting errors in segments within a decoded code block of the outer FEC decoder. In the first arrangement, when an error is detected at the output of the outer FEC decoder, the entire decoded code block will have to be marked erroneous. In the second arrangement, only those segments with errors need to be marked erroneous.

[0267] FIG. 31 is a block diagram of a data estimator of one embodiment of the present invention that employs error detection to improve the reliability of the interim data decisions supplied to DD-ISIC decoder 2514. In this arrangement, two candidate sequences of interim data decisions are generated and the error-detection code is employed to provide the information needed to select the interim data decisions for the DD-ISIC decoder from the two candidate sequences. With reference to FIG. 31, the output sequence {Û_i} of ISIC equalizer-decoder 2400 is supplied to delay block 3124 to provide the first candidate sequence of interim data decisions {Û_i⁽¹⁾} A cascade of deinterleaver 2816-1 and outer FEC decoder 2818-1 advantageously processes the output sequence {Û_i} of ISIC equalizer-decoder 2400 to provide the tentative outer-FEC-decoded sequence {ũ_i}, which is supplied to a cascade of outer FEC encoder 2720-1 and interleaver 2730-1 to provide the second candidate sequence of interim data decisions {Û_i⁽²⁾} and, in parallel, to a cascade of error detector 3122 and interleaver 2730-2 to provide the error indicator sequence {E_i}. Error detector 3122 performs error detection on the tentative outer-FEC-decoded sequence {ũ_j} to determine if a code block of n₁code symbols contains errors. A code block is said to be erroneous is it has been determined by error detector 3122 to contain errors. Every symbol of an erroneous code block is marked as erroneous although in general only some of the symbols are in error. Thus, the error indicator E_i=1 if Û_i⁽²⁾of the second candidate sequence of interim data decisions is from an erroneous code block; otherwise E_i=0.

[0268] The delay introduced by block 3124 is preferably set to be the combined processing delay of blocks 2816-1, 2818-1, 2720-1, and 2730-1 such that the two candidate sequences of interim data decisions {Û_i⁽¹⁾} and {Û_i⁽²⁾} are lined up at the input ports of selector 3126. Selector 3126 selects the interim data decisions from the two candidate sequences based on the information provided by the error indicator sequence {E_i}. In particular, the sequence of interim data decisions {Z_i} to be supplied to DD-ISIC decoder 2514 is computed according to $\begin{array}{cc}{Z}_i=\{\begin{array}{cc}{\hat{U}}_i^{\left(1\right)};& \mathrm{if}{E}_i=1\\ {\hat{U}}_i^{\left(2\right)};& \mathrm{if}{E}_i=0\end{array}& \left(73\right)\end{array}$

[0269] DD-ISIC decoder 2514 uses {Z_i} as the interim data decisions to compute the vector z by assuming that {Z_i} is a perfect estimate of the sequence {U_i}, which is shown in FIG. 30 as the input to trellis decoder 402.

[0270] The output of DD-ISIC decoder 2514, denoted as {G_i} in FIG. 31, is supplied to deinterleaver 2816-2, whose output is supplied to outer FEC decoder 2818-2. ED decoder 3120, where ED stands for error-detection, removes the error-detection parity check code symbols from the output of outer FEC decoder 2818-2 to provide the estimated data sequence {û_j}.

[0271] I have described above several embodiments of the present invention. These embodiments provide different levels of reliability in data estimation. A higher reliability is achieved by the more complex embodiments. Some embodiments are better suited for applications where the impulse response of the channel is time varying while others, possibly less complex, embodiments are more suitable for time-invariant or very-slowly-varying channels. Those skilled in art should be able to choose the embodiments that are most suitable for their applications.

[0272] The number of trellis states of the ISIC and the DD-ISIC decoders of the present invention is dependent only on the trellis code employed and independent on the ISI span. Hence, the intersymbol interference compensation methods of the present invention are less complex than maximum likelihood sequence estimation and delayed decision feedback sequence estimation. By using a partial equalizer to remove only the precursor ISI, the noise enhancement and noise colorization effects are reduced. Use of the double-sided partial equalizer further reduces these undesirable effects. The methods of the present invention do not employ decision feedback equalization to provide data estimates and are therefore not subject to the error-propagation effects of decision feedback equalizers. Some embodiments of the present invention provide for the use of decision feedback equalization but only as a means to aid the adaptation of the partial equalizer, the double-sided partial equalizer, and the ISI profile estimator. In such a use of decision feedback equalization the error propagation effects can be made insignificant by slowing down the rate of adaptation. The present invention does not employ precoding, hence it can be used to support constant-envelope signaling as well as non-constant envelope signaling.

[0273] The above-described exemplary embodiments are intended to be illustrative in all respects, rather than restrictive, of the present invention. Those skilled in the art will be able to devise various arrangements, which, although not explicitly described herein, embody the principles of the invention, and thus are within its spirit and scope as defined by the following claims.