Intersymbol Interference Channel Coding Scheme

This invention relates to methods for transmitting data over intersymbol interference channels and, more particularly, to methods for minimizing the effects of intersymbol interference on transmitted data.

Intersymbol interference results from the fact that a typical communications channel inherently has memory such that other signals transmitted through the channel interfere with the current, transmitted signal. Prior techniques for minimizing the effects of intersymbol interference have involved "precoding" the signal to be transmitted. These prior art techniques, while allowing both coding and shaping gains on intersymbol interference channels, provide sub-optimal performance because of the "precoding loss" (i.e., the additional power that must be transmitted to minimize the effects of intersymbol interference) associated with these techniques. Because the precoding loss increases whin a more powerful trellis code is used, such precoders cannot approach the channel capacity.

One technique for minimizing the effects of intersymbol interference involves precoding a sequence of signal points to achieve noise whitening on intersymbol interference channels. This precoding is a nonlinear operation that ensures that the channel output or the output of a noise whitening filter is a trellis code sequence affected by additive white Gaussian noise. A so-called "dither signal" is added to each of the signal points in the sequence.. No coding operation (i.e., an operation which achieves coding gain) is performed as part of precoding. Rather, precoding is performed on a sequence of previously trellis coded signal points which could be selected from a shaped constellation. Precoding is performed by using a modulo .lambda.', operation, where .lambda.' is the coset lattice, that is, the lattice in the last level of coset partitioning used to generate the trellis code. Using this scheme, the precoding loss is large when the trellis code is based on a large number of coset partitions. The performance of this scheme degrades with the number of coset partitions used to generate the trellis code.

Intersymbol interference and precoding loss are minimized in accordance with the invention by combining the precoding and coding operations. By performing precoding together with coding, the nonlinear modulo operation is based on the first level of the lattice partitioning used to generate the trellis code. This produces a smaller precoding loss than the prior art precoding techniques and makes the precoding loss independent of the number of coset partitions used to generate the trellis code. Coding is performed by choosing the appropriate nonlinear modulo operation as a function of the current state of the finite-state machine that is used to generate the trellis code.

In an exemplary embodiment of the invention, an intersymbol interference coder uses a feedback loop to apply a dither sequence to a sequence of uncoded input signal points. The dither signal applied to each input signal point is a nonlinear function of the previous signal points in the sequence and the current state of the finite-state machine used to generate the trellis code. The intersymbol interference coder implements, for example, a trellis code by selecting one of two different modulo (mod) operations to determine the magnitude of the dither signal, the selection being made based on the current state of the finite-state machine used to generate the trellis code.

In the drawings:

FIG. 1 is a block diagram of the transmitter portion of a communications system constructed in accordance with the principles of the present invention;

FIG. 2 is a block diagram of the receiver portion of a communications system constructed in accordance with the principles of the present invention;

FIG. 3 shows the first level of partitioning of a two-dimensional lattice that may be used to generate a trellis code in accordance with the invention;

FIG. 4 is a block diagram of the intersymbol interference coder of FIG. 1; and

FIG. 5 is a block diagram of the intersymbol interference decoder of FIG. 2.

FIG. 1 shows the transmitter portion of a communications system which includes an intersymbol interference channel. The transmitter includes a binary data source 100, a constellation encoder 102, an intersymbol interference coder 104, and a transmit filter 106. The transmitter outputs a sequence of signal points for transmission across an intersymbol interference channel 108. Intersymbol interference channel 108 can be represented as an intersymbol interference channel filter 110 and noise applied to an adder (which is diagramatically represented as a noise element 112).

Binary data source 100 outputs data in the form of bits to constellation encoder 102, which maps the bits received from data source 100 to a sequence of signal points selected from a shaped, but uncoded, constellation. Constellation encoder 102 outputs a stream of signal points to intersymbol interference coder 104. In accordance with the invention, intersymbol interference coder 104 adds, as described below, a dither sequence to the stream of signal points to generate an output sequence of signal points that (1) is precoded to minimize the effect of intersymbol interference, and (2) in the receiver, results in a sequence from a predetermined signal-space code (e.g., a trellis code) affected by white Gaussian noise (to achieve coding gain). The output sequence of signal points is passed through a conventional transmit filter 106 and applied to intersymbol interference channel 108.

FIG. 2 shows the receiver portion of the communications system, which receives a sequence of signal points from intersymbol interference channel 108. The receiver includes an equalizer/sampler 200 and a noise prediction error filter 202 which collectively comprise a "noise whitening" filter 203, a Viterbi decoder 204, an intersymbol interference decoder 206, a "constellation" decoder 208, and a data sink 210. Noise prediction error filter 202 has a transfer function H(z). Equalizer/sampler 200, noise prediction error filter 202, Viterbi decoder 204, and constellation decoder 208 can be implemented in a conventional manner that is known to those skilled in the art.

The output of intersymbol interference channel 108 is input to equalizer/sampler 200 and noise prediction error filter 202 which output the sequence to Viterbi decoder 204. Alternatively, the output of channel 108 can provided directly to Viterbi decoder 204 (in which case, channel filter 110 has a transfer function H(z)). The output of intersymbol interference channel 108 (or the output of noise prediction error filter 202 if used in the noise whitening context) is a sequence from the predetermined signal-space code affected by noise, such as white Gaussian noise. Viterbi decoder 204 is a maximum likelihood-type detector which operates to identify the sequence of signal points and effectively removes this noise. The transmitted constellation point is then uniquely recovered from the output of Viterbi decoder 204 by intersymbol interference decoder 206, as described below in the discussion of FIG. 5. Constellation decoder 208 receives a sequence of signal points from intersymbol interference decoder 206 and outputs bits, which blocks of signal points, to data sink 210.

To generate the trellis code, a two-dimensional (2D) lattice .lambda.=Z.sup.2 is partitioned into cosets of the coset lattice .lambda.', which is a sublattice of Z.sup.2. (The notation "Z.sup.2 " indicates that both coordinates of all points on a plane are integers.) FIG. 3 shows the 2D lattice .lambda. that in the first level of partitioning is partitioned into two subsets .lambda..sub.A and .lambda..sub.B. For this example .lambda..sub.A =RZ.sup.2 and its coset (in .lambda.).lambda..sub.B =RZ.sup.2 +(0,1) represent the first level of partitioning, i.e., .lambda./.lambda..sub.a /.lambda.' from a chain of lattice partitions. Points on the lattice .lambda. identified by "x" and "o.revreaction., respectively represent points from subsets .lambda..sub.A and .lambda..sub.B. For all coset codes with redundancy 1 bit/2D, all outgoing transitions from any trellis state either correspond to signal points in .lambda..sub.A or signal points in .lambda..sub.B, but not in both. The output of constellation encoder 102 (FIG. 1) is an uncoded sequence of points on .lambda..sub.A.

At the origin of the lattice in FIG. 3 is a region identified by the letter V (shown as a shaded region). This region is the Voronoi region of the lattice .lambda..sub.A. The Voronoi region contains all points on the plane which are closer to the origin than to any other point on the lattice. The Voronoi region is bounded on two sides by solid lines, indicating that the signal points along those lines are included in the region. The remaining two sides of the Voronoi region are bounded by dashed lines, indicating that the signal points along those lines are excluded from the region. The significance of the Voronoi region will be made clear below.

In accordance with the present invention, the operations of a) trellis coding to provide coding gain and b) precoding to overcome the effects of intersymbol interference, are combined into a single operation. The intersymbol interference coder of the invention is used to transmit data over intersymbol interference channels while realizing both coding and shaping gains. By combining trellis coding and precoding in a single operation, the invention achieves a smaller precoding loss than was possible in the prior art. Also, the precoding loss of the intersymbol interference coder of the invention is independent of the number of coset partitions used to generate the trellis code.

FIG. 4 shows a block diagram of intersymbol interference coder 104. Intersymbol interference coder 104 includes a trellis coder 400, a filter 402, modulo operation means 404, and adders 406 and 407. As discussed above, intersymbol interference coder 104 receives a signal point on lead 408 and outputs the signal point for transmission over intersymbol interference channel 108 on lead 410. Filter 402, modulo operation means 404, and adder 406 form a feedback loop between a node 412 at the output of intersymbol interference coder 104 and adder 406. With the intersymbol interference coder 104, the output of noise prediction error filter 202 will be a.sub.n +q.sub.n affected by white Gaussian noise, where q.sub.n is a point on either .lambda..sub.A or .lambda..sub.B. The output of filter 402 also is applied to adder 407 to be added to the signal from node 412 to form the input to trellis coder 400.

Filter 402 has a transfer function H(z)-1, giving intersymbol interference coder 104 an effective transfer function of 1/H(z) if the modulo operation is ignored (i.e., replaced by a simple connection). Thus, ignoring the operation of modulo operation means 404, intersymbol interference coder 104 would have a transfer function that is the reciprocal of the transfer function of noise prediction error filter 202.

In accordance with the invention, intersymbol interference coder 104 ensures that the input to Viterbi decoder 204 is the trellis code sequence a.sub.n +q.sub.n affected by additive white Gaussian noise. This is accomplished by selecting the appropriate mod operation in modulo operation means 404. Coder 104 selects the appropriate mod operation based on the current state of the finite-state machine which generates the trellis code. If the current state dictates that the present output be in .lambda..sub.A, modulo .lambda..sub.A operation is selected. If, on the other hand, the current state requires the output to be in .lambda..sub.B, modulo .lambda..sub.B is selected. After the modulo operation, the output a.sub.n +q.sub.n of noise prediction error filter 202 (assuming no noise) is used to determine the next state of the finite-state machine.

Trellis coder 400 is a finite state machine which generates the trellis code. Trellis coder 400 deals with all levels of partitioning of the trellis code, but mod operations are based only on the first level of trellis partitioning.

To understand why the output of noise whitening filter 203 is a valid sequence from a trellis code, consider the following. Assume that the past sequence of output signal points . . . , a.sub.0 +q.sub.0, . . . , a.sub.n-2 +q.sub.n-2, a.sub.n-1 +q.sub.n-1 form a valid trellis sequence. If the output a.sub.n-1 +q.sub.n-4 leaves the trellis in a state that allows only those transitions that correspond to points in .lambda..sub.A, trellis coder 400 selects mod .lambda..sub.A operation. If instead, however, a.sub.n-1 +q.sub.n-1 leaves the trellis in a state that allows only those transitions that correspond to points in .lambda..sub.B, trellis coder 400 selects mod .lambda..sub.B operation. Performing a mod .lambda..sub.A operation implies, as described below, quantizing the feedback signal f.sub.n to the nearest point q.sub.n in .lambda..sub.A and determining the quantization error m.sub.n. Similarly, a mod .lambda..sub.B operation refers to quantizing f.sub.n to the nearest point q.sub.n in .lambda..sub.B and determining the quantization error m.sub.n.

The quantization in the modulo operation means 404 is performed such that the error m.sub.n (the dither signal that is applied to adder 406) is always a point in the Voronoi region V of .lambda..sub.A. Since the current input signal point on lead 408 is always a point in .lambda..sub.A (signal points a.sub.n are selected from an uncoded constellation), a.sub.n +q.sub.n corresponds to a valid transition in the finite-state machine of the trellis code, taking the finite-state machine to a new state. This process is continually repeated for successive next inputs (e.g., a.sub.n+1). In this manner, intersymbol interference coder 104 ensures that the input to the Viterbi decoder in the receiver is a valid trellis sequence (affected by additive white Gaussian noise).

As discussed above, the precoding loss is the overhead transmitted energy required to overcome the effects of intersymbol interference caused by channel 108. In the embodiment of FIG. 4, the precoding loss is the average energy of m.sub.n, which is the average energy of the Voronoi region V of the lattice .lambda..sub.A. By combining the precoding operation, that is, the addition of a dither sequence (a sequence of successive dither signals m.sub.n) to the sequence of input channel signal points, with the coding operation, intersymbol interference coder 104 performs modulo operations based on sublattices in the first level of lattice partition used to generate the trellis code. The sublattices in the first level partition are more dense (finer) than later partitions of the lattice. Hence, the lattice corresponding to the first level partition has a smaller Voronoi region than that of the lattices corresponding to later partitions, and thus, has a smaller average energy. This produces a smaller precoding loss. Operating on the first level partition also makes the precoding loss independent of the number of coset partitions that generate the trellis code.

Intersymbol interference coder 10.4 will operate successfully if the sequence of signal points a.sub.n can be uniquely recovered from the output a.sub.n +q.sub.n of Viterbi decoder 204. The symbol a.sub.n +q.sub.n denotes an estimate of the quantity a.sub.n +q.sub.n.) Intersymbol interference decoder 206, shown in greater detail in FIG. 5, performs this decoding operation.

Referring to FIG. 5, intersymbol interference decoder 206 includes a filter 500 and a quantizer 502. Filter 500 has a transfer function 1/H(z) which is the inverse of the transfer function of noise prediction error filter 202. In the absence of channel errors, filter 500 receives a signal point having a value a.sub.n +q.sub.n from the output of the Viterbi decoder 204. The sequence a.sub.n +q.sub.n is filtered by filter 500 to give a signal a.sub.n -m.sub.n. Because m.sub.n is always in the Voronoi region V of the lattice .lambda..sub.A, and a.sub.n is a point on .lambda..sub.A, quantizer 502 can recover a.sub.n from a.sub.n -m.sub.n simply by quantizing, in a conventional manner, to the nearest point in lattice .lambda..sub.A (such that the quantization error is within Voronoi region V).

Intersymbol interference coder 104 has been described in the context of receiving a sequence of signal points which are selected from an uncoded constellation. It is to be understood, however, that intersymbol interference coder 104 could receive signal points encoded using a first trellis code which intersymbol interference coder 104 converts to a different trellis code.

It will be apparent to one skilled in the art that other modifications can be made to the described embodiment without departing from the scope of the invention. For example, although the invention has been described in the context of 2D trellis coded signal points with a 1 bit/2D redundancy, the present invention is equally applicable to trellis codes of other dimensions and redundancies, and to other signal-space codes. Also, unshaped constellations, and constellations of different sizes and different dimensionality could be used.