Trellis shaping for modulation systems

BACKGROUND OF THE INVENTION This application is a continuation-in-part of Forney et al., U.S. patent application Ser. No. 312,254, filed Feb. 16, 1989, now abandoned. This invention relates to modulation systems for sending digital data via a channel. In traditional uncoded modulation systems, to send n bits per N signaling dimensions, a 2.sup.n -point N-dimensional signal constellation is used. Each group of n bits is independently mapped into one of the 2.sup.n signal points. The selected signal point is then transmitted over a channel, e.g., by N uses of a pulse amplitude modulation (PAM) transmitter, or by N/2 uses of a quadrature amplitude modulation (QAM) transmitter. The signal points in the constellation may be selected and organized to achieve a good signal to noise ratio (SNR) efficiency. The key parameters that determine SNR efficiency are the minimum squared distance between the constellation signal points and their average power. In coded modulation systems, by contrast, the digital data are encoded as a sequence drawn from a set of allowable sequences of signal points. The allowable sequences are selected in such a way that the minimum squared distance between allowable sequences in the code is greater than the minimum squared distance between the components of the sequences, namely the signal points. This requires that not all possible sequences be allowable, which in turn means that the number of signal points in the constellation must be expanded. Expansion of the constellation leads to some increase in the average power required to send n bits per N dimensions, but the increase in minimum squared sequence distance outweighs the increase in average power and a net `coding gain` is achieved. There are two basic types of coded modulation systems, block and trellis. In block coded systems, the code sequences are finite length blocks of signal points and are often called code words. Within a given block, the signal points depend on one another, but there is no interdependence between signal points of different blocks. Lattice codes (in which a code word is a point on a translate of a multidimensional lattice) may be regarded as block coded systems, if the code words are construed as defining sequences of signal points. In trellis-coded modulation (Ungerboeck, "Channel Coding with Multilevel/Phase Signals," IEEE Transactions on Information Theory, Vol. IT-28, No. 1, pp. 56-67, January, 1982), on the other hand, code sequences of signal points are in principle infinitely long, and there are signal point interdependencies that extend over the whole sequence. Typically, coded modulation systems have been designed jointly with an associated signal constellation or family of constellations. The constellation itself generally has been of the block type in which the subset of allowable sequences has been the subset of all sequences in the code whose N-dimensional signal points lay in some finite (e.g., 2.sup.n+r -point) N-dimensional signal constellation. Thus, the constellation was the same in each N dimensions and not dependent on signal points outside those N dimensions. It has been recognized that such constellations can achieve improved SNR efficiency if they are shaped to be as nearly spherical as possible. Forney, U.S. patent application Ser. No. 062,497, filed Jun. 12, 1987, assigned to the same assignee as this application and incorporated herein by reference, describes signal constellations which comprise points of a lattice (or a coset of a lattice) that lie within a so-called Voronoi region of a sublattice of the original lattice. A Voronoi region of a lattice is the set of points that are as close to the origin as to any other lattice point. Thus, the use of a Voronoi region of a lattice to define the constellation boundary achieves the advantages of a quasi-spherical constellation. Such Voronoi constellations are also discussed in Conway and Sloane, "A Fast Encoding Method for Lattice Codes and Quantizers," IEEE Trans. Inform. Theory, Vol. IT-29, pp. 820-824, 1983, and Forney, U.S. patent application Ser. No. 181,203, filed Apr. 13, 1988 (which uses some points of the Voronoi constellation to support a secondary channel). SUMMARY OF THE INVENTION The invention concerns so-called trellis shaping modulation systems that achieve improved performance. In some aspects of the invention, instead of mapping a digital data sequence into a sequence of signal points drawn from a signal point constellation as described above, the data sequence is mapped into a sequence of signal points drawn from a so-called sequence space of available sequences that is not merely the Cartesian product of a single N-dimensional constellation used repeatedly in each N dimensions. The region occupied by the available sequences in sequence space is shaped to minimize the required power, e.g., the region may consist of a fundamental region of a trellis code, and more particularly, an approximation to the Voronoi region of a trellis code (where the trellis code is not just a repeated lattice code). In general, in one aspect, the invention features mapping a digital data sequence into a signal point sequence for transmission, by selecting the signal point sequence from a subset of all possible signal point sequences based on the digital data sequence, all possible signal point sequences in the subset lying in a fundamental region of a trellis code, the fundamental region being other than a simple Cartesian product of finite dimensional regions. In general, in another aspect, the invention features mapping a digital data sequence into a sequence of signal points for transmission, by specifying a class of possible sequences based on the digital data, and selecting the signal point sequence from the class, the selection being based on the respective average powers of the possible sequences of the class, the selection being based on not only a fixed-length block of the digital data. Preferred embodiments of the invention include the following features. The class corresponds to a set of sequences specified by a finite-state trellis diagram of unbounded length. The selection is performed by applying a search procedure to the class, e.g., a search procedure of the Viterbi algorithm type. The set of all possible sequences that could be selected from the class lies within a fundamental region of a trellis code, the fundamental region being other than a simple Cartesian product of finite-dimensional regions. The possible signal point sequences are code sequences from a translate of a second code, the second code being of the trellis or lattice type. The fundamental region comprises approximately a Voronoi region of the trellis code. More generally, the fundamental region comprises the set of possible signal point sequences that are decoded to the zero sequence in the trellis code by a decoder for the code. For example, the fundamental region comprises the set of possible signal point sequences that are decoded to the zero sequence in the trellis code by an approximation to a minimum distance decoder for the code having delay M, M greater than or equal to 1. The fundamental region comprises the set of possible signal point sequences that are decoded to a common error region by a fair, exhaustive decoder for the trellis code. The digital data sequence is mapped into an initial signal point sequence belonging to and representing a congruence class of the trellis code, and a signal point sequence is chosen which belongs to the congruence class and has no greater average power than the initial signal point sequence. The digital data sequence is mapped into a sequence of signal points belonging to an initial constellation comprising points lying within a fundamental region of a time-zero lattice of the trellis code. The mapping includes applying a portion of the elements of the digital data sequence to a coset representative generator for forming a larger number of digital elements representing a coset representative sequence. The coset representative generator multiplies a portion of the elements of the digital data sequence by a coset representative generator matrix (H.sup.-1).sup.T which is inverse to a syndrome-former matrix H.sup.T for the code. The digital data sequence is recovered from a possibly noise-corrupted version of the signal point sequence, by decoding the signal point sequence to a sequence of estimated digital elements and forming a syndrome of fewer digital elements based on a portion of the estimated digital elements using a feedback-free syndrome former H.sup.T. In general, in another aspect, the invention features mapping a digital data sequence into a sequence of signal points to be sent, comprising determining a class of possible sequences from which to select the sequence to be sent, based at least on digital data appearing in the digital data sequence up to a time j, and for every time j, selecting the sequence to be sent from the class of possible sequences based on digital data appearing in the sequence after time j. Preferred embodiments include the following features. The mapping of each element is done independently of the mapping of any other element. Decoding the sequence of sent signal points is done at time j based on the sent points only up to time j. The trellis code is either a linear trellis code or a non-linear trellis code. If linear, the trellis code may be a 4-state Ungerboeck code or a dual Wei code. The trellis code is based on a partition of binary lattices, or in some cases a partition of ternary or quaternary lattices. Each signal point in the sequence is selected from an N dimensional constellation divided into regions containing predetermined possible signal points, the regions to which successive signal points in the sequence belong being determined in a manner tending to minimize the energy required to transmit the signal points. In general, in another aspect, the regions are not all fundamental regions of a lattice. At least some of the regions have different average powers. The regions are N-dimensional and are bounded approximately by N-spheres centered on the origin of the constellation. N=2 and there are four regions. The constellation comprises a two-dimensional constellation of signal points lying on the half-integer rid Z.sup.2 +(1/2,1/2). The regions are organized so that rotation of a signal point by 0, 90, 180, or 270 degrees produces another signal point in the same region. The regions have equal numbers of signal points. The regions from which successive signal points in the signal point sequence are drawn based upon the average energies of signal points in the regions. For example, the regions may be determined by decoding a sequence of values derived from the digital data sequence using a decoder for a convolutional code. Each region includes signal points belonging to different cosets of a lattice and each region has an equal number of signal points belonging to each respective coset. The coset from which each signal point is to be drawn is based on a coset representative sequence generated in accordance with a convolutional code. The convolutional code comprises code sequences comprising symbols from a label alphabet, and the sequence of values is generated by passing a sequence of bits of the digital data sequence through a coset representative generator to produce a coset representative sequence, and decoding the coset representative sequence to a minimum weight sequence of labels from the label alphabet. The decoding is by a minimum weight decoding technique, which includes assigning to a branch in a trellis corresponding to the code a weight equal to the average energy of the region of signal points corresponding to that branch of the trellis. The decoding technique comprises assigning to a branch in a trellis corresponding to the code a weight corresponding to the energy of a particular signal point within the region corresponding to that branch of the trellis. The trellis code may be a pseudo-linear trellis code. The signal points in the sequence belong to a 2D constellation and the step of selecting the signal point sequence is constrained so that the signal points in the sequence will usually be within some radius R.sub.c of the origin of the 2D constellation. The step of choosing a signal point sequence belonging to the congruence class is further constrained so as to reduce the peak power of the signal point sequence where the peak power represents the maximum energy of the signal point sequence in some number of dimensions N. The step of choosing a signal point sequence belonging to the congruence class comprises decoding the initial signal point sequence into a final signal point sequence comprising signal points belonging to a 2D constellation, the decoding being constrained so that only final signal point sequences whose signal points usually have magnitudes no greater than some predetermined radius R.sub.c from the origin of the constellation are used. The step of choosing a signal point sequence belonging to the congruence class comprises decoding the initial signal point sequence into a code sequence using a Viterbi algorithm, and in each recursion of the Viterbi algorithm, effecting an operation that will assure that the code sequence is an allowable sequence in the second code. The operation comprises adjusting the metrics of selected historical paths in the trellis of the Viterbi algorithm, so that none of the selected paths will become the most likely path in the next recursion of the Viterbi algorithm. The historical paths are chosen based on whether they include particular state transitions at particular locations in the trellis of the Viterbi algorithm. The operation comprises assigning a large metric to selected historical paths in the trellis. The signal point sequence is selected in a manner to ensure that the digital data sequence can be recovered from a channel-affected version of the signal point sequence which has been subjected to one of a number of predetermined phase rotations. The step of mapping said digital data sequence into a sequence of signal points belonging to an initial constellation includes converting the data elements in the data sequence into groups of bits for selecting signal points from the initial constellation, and the groups of bits are arranged to ensure that the bits can be recovered from a channel-affected version of the transmitted sequence which has been subjected to phase rotations of one, two, or three times 90 degrees. In general, in another aspect, the invention features a modem for transmitting and receiving digital data sequences via a channel comprising means for mapping a digital data sequence into a sequence of signal points to be sent, including a sequence selector for selecting the signal point sequence from a subset of all possible signal point sequences based on the digital data sequence, all possible signal point sequences in the subset lying in a fundamental region of a trellis code, the fundamental region being other than a simple Cartesian product of finite-dimensional regions, a modulator for sending the signal points of the sequence via the channel, a demodulator for receiving a possibly channel-affected version of the signal point sequence from the channel, and means for recovering a digital data sequence from the possibly channel-affected version of the signal point sequence. The invention achieves large shaping gains and total gains with relatively low complexity.

Claims

We claim:

1. A method of mapping a digital data sequence into a signal point sequence for transmission, said signal point sequence belonging to a set of possible sequences of signal points, comprising

receiving said digital data sequence, and

selecting said signal point sequence from a subset of all said possible signal point sequences based on said digital data sequence, said subset being characterized in that all said possible signal points sequences in said subset lie in a fundamental region of a trellis code, said fundamental region being other than a simple Cartesian product of finite-dimensional regions.

2. A method of mapping a digital data sequence into a sequence of signal points for transmission, said sequence of signal points belonging to a set of possible sequences of signal points, comprising

specifying a class of possible sequences based on said digital data,

selecting said signal point sequence from said class, said selection being based on the respective average powers of said possible sequences of said class, said selection being based not only on a fixed-length block of said digital data, but also on other digital data.

3. The method of claim 2 wherein said class corresponds to a set of sequences specified by a finite-state trellis diagram of unbounded length.

4. The method of claim 2 or 3 wherein said selecting comprises applying a search procedure to said class.

5. The method of claim 4 wherein said search procedure comprises a Viterbi algorithm type search.

6. The method of claim 2 wherein the set of all possible sequences that could be selected from said class lies within a fundamental region of a trellis code, said fundamental region being other than a simple Cartesian product of finite-dimensional regions.

7. The method of claim 3 wherein there is a set of possible sequences which may be selected from said class and the set of all said possible sequences that could be selected from said class lies within a fundamental region of a trellis code, said fundamental region being other than a simple Cartesina product of finite-dimensional regions.

8. The method of claim 1 or 2 wherein said possible signal point sequences are code sequences from a translate of a code of the trellis or lattice type.

9. The method of claim 1, 6 or 7 wherein said fundamental region comprises approximately a Voronoi region of said trellis code.

10. The method of claim 1, 6 or 7 wherein said fundamental region comprises the set of said possible signal point sequences that are decoded to the zero sequence in said trellis code by a decoder for said code.

11. The method of claim 10 wherein said fundamental region comprises the set of said possible signal point sequences that are decoded to the zero sequence in said trellis code by an approximation to a minimum distance decoder for said code.

12. The method of claim 10 wherein said fundamental region comprises the set of said possible signal point sequences that are decoded to the zero sequence in said trellis code by a minimum distance decoder with delay M, wherein M is greater than or equal to 1.

13. The method of claim 10 wherein said fundamental region comprises the set of said possible signal point sequences that are decoded to a common error region by a fair, exhaustive decoder for said trellis code.

14. The method of claim 1 wherein said selecting comprises

mapping said digital data sequence into an initial signal point sequence belonging to and representing a congruence class of said trellis code, and

choosing a signal point sequence belonging to said congruence class and which has no greater average power than said initial signal point sequence.

15. The method of claim 14 wherein said mapping comprises mapping said digital data sequence into a sequence of signal points belonging to an initial constellation comprising points lying within a fundamental region of a time-zero lattice of said trellis code.

16. The method of claim 1 or 2 wherein said mapping includes applying a portion of the elements of said digital data sequence to a coset representative generator for forming a larger number of digital elements representing a coset representative sequence.

17. The method of claim 15 wherein said coset representative generator comprises a multiplication of a portion of the elements of said digital data sequence by a coset representative generator matrix (H.sup.-1).sup.T which is inverse to a syndrome-former matrix H.sup.T for said code.

18. The method of claim 17 further comprising recovering the digital data sequence from a possibly noise-corrupted version of the signal point sequence, including decoding the signal point sequence to a sequence of estimated digital elements and forming a syndrome of fewer digital elements based on a portion of the estimated digital elements using a feedback-free syndrome former H.sup.T.

19. A method of mapping a digital data sequence into a sequence of signal points to be sent, comprising

determining a class of possible sequences from which to select said sequence to be sent, based at least on digital data appearing in said digital data sequence up to a time j, and

for every time j, selecting said sequence to be sent from said class of possible sequences based on digital data appearing in said sequence after time j.

20. The method of claim 19 in which

the digital data sequence comprises a succession of data elements, and

the step of determining the class of possible sequences comprises mapping of each element into a point in an initial constellation.

21. The method of claim 19 or 20 in which the sequence of said points in said initial constellation into which said succession of data elements are mapped comprise a representative sequence of said class of possible sequences.

22. The method of claim 20 in which said mapping of each element of said succession of elements is done independently of said mapping of any other element of said succession of elements.

23. The method of claim 20 in which each element is a binary value and said initial constellation comprises 2.sup.b points, where b is the number of bits in each said element of said sequence.

24. The method of claim 20 in which said initial constellation comprises a portion of a lattice or a translate of said lattice.

25. The method of claim 24 in which said portion comprises a fundamental region of a sublattice of said lattice.

26. The method of claim 25 in which said sublattice is a time-zero lattice of a trellis code.

27. The method of claim 20 in which the step of selecting said sequence to be sent comprises a decoding of a said sequence of points in said initial constellation by a decoder for a trellis code.

28. The method of claim 22 in which said possible sequence in said class lie in a fundamental region of said trellis code, said fundamental region comprises a common error region of said decoder, and said decoding comprises decoding said sequence of points in said initial constellation to error sequences within said common error region.

29. The method of claim 28 in which the sequences within said common error region comprise signal points that comprise a final constellation with more points than said initial constellation.

30. The method of claim 27 in which said representative points are decoded by a minimum-distance decoder for said code.

31. The method of claim 30 wherein said minimum-distance decoder has decoding delay M and M.gtoreq.1.

32. A method of recovering a digital data sequence from a received sequence consisting of the sequence of signal points chosen to be sent in accordance with the method of claim 15 or 20, comprising

decoding the sequence of sent signal points to recover the sequence of points of the initial constellation, and

inverse mapping the sequence of points of the initial constellation to recover the digital data sequence.

33. The method of claim 32 in which decoding the sequence of sent signal points is done at time j based on said sent points only up to time j.

34. The method of claim 1, 6, 7, 26, or 27 wherein said trellis code is a linear trellis code.

35. The method of claim 1, 6, 7, 26, or 27 wherein said trellis code is a non-linear trellis code.

36. The method of claim 34 wherein said linear trellis code is a 4-state Ungerboeck code.

37. The method of claim 34 wherein said linear trellis code is a dual Wei code.

38. The method of claim 1, 6, 7, 26, or 27 wherein said trellis code is based on a partition of binary lattices.

39. The method of claim 1, 6, 7, 26, or 27 wherein said trellis code is based on a partition of ternary or quaternary lattices.

40. The method of claim 2 wherein each signal point in said sequence is selected from an N-dimensional constellation divided into regions containing predetermined possible signal points, the regions to which successive signal points in said sequence belong being determined in a manner tending to minimize the energy required to transmit the signal points.

41. A method of mapping a digital data sequence into a sequence of signal points for transmission, comprising

specifying a class of possible sequences based on said digital data,

selecting said signal point sequence from said class, said selection being based on the respective average powers of said possible sequences of said class,

each signal point in said sequence being selected from an N-dimensional constellation divided into regions containing predetermined possible signal points, the regions to which successive signal points in said sequence belong being determined in a manner tending to minimize the energy required to transmit the signal points,

some said regions being other than fundamental regions of a lattice.

42. The method of claim 40 or 41 wherein at least some of said regions have different average powers.

43. The method of claim 42 wherein said regions are N-dimensional and are bounded approximately by N-spheres centered on the origin of the constellation.

44. The method of claim 43 wherein N=2 and there are four said regions.

45. The method of claim 40 or 41 wherein said constellation comprises a two-dimensional constellation of signal points lying on the half-integer grid Z.sup.2 +(1/2,1/2).

46. The method of claim 40 or 41 wherein said regions are organized so that rotation of a signal point by 0, 90, 180, or 270 degrees produces another signal point in the same region.

47. The method of claim 40 or 41 wherein said regions have equal numbers of signal points.

48. The method of claim 40 or 41 further comprising

determining the regions from which successive signal points in said signal point sequence are drawn based upon the average energies of signal points in said regions.

49. The method of claim 40 further comprising

determining the regions from which successive signal points in said signal point sequence are drawn by decoding a sequence of values derived from said digital data sequence using a decoder for a convolutional code.

50. The method of claim 40 or 41 wherein each said region includes signal points belonging to different cosets of a lattice and each region has an equal number of signal points belonging to each respective said coset.

51. The method of claim 40 wherein said selection of said regions is based on a coset representative sequence generated by a coset representation generator in accordance with a convolutional code.

52. The method of claim 49 in which said decoding is by a minimum weight decoding technique.

53. The method of claim 52 wherein the decoding technique comprises assigning to a branch in a trellis corresponding to the code a weight equal to the average energy of the region of signal points corresponding to that branch of the trellis.

54. The method of claim 52 wherein the decoding technique comprises assigning to a branch in a trellis corresponding to the code a weight corresponding to the energy of a particular signal point within the region corresponding to that branch of the trellis.

55. The method of claim 50 wherein said coset representative generator effects a multiplication of a portion of the elements of said digital data sequence by a coset representative generator matrix (H.sup.-1).sup.T which is inverse to a syndrome former matrix H.sup.T for said code.

56. The method of claim 45 further comprising recovering the digital data sequence from a possibly noise-corrupted version of the signal point sequence, including decoding the signal point sequence to a sequence of estimated digital elements and forming a syndrome of fewer digital elements based on a portion of the estimated digital elements using a feedback-free syndrome former H.sup.T.

57. The method of claim 49 or 51 wherein said convolutional code is a 4-state Ungerboeck code.

58. The method of claims 1, 6, 7, 26, 27 in which said trellis code is a pseudo-linear trellis code.

59. The method of claim 1, 2, or 19 wherein the step of selecting said signal point sequence is further constrained so as to reduce the peak power of said signal point sequence where said peak power represents the maximum energy of said signal point sequence in some number of dimensions N.

60. The method of claim 59 wherein N=2.

61. The method of claim 59 wherein N=4.

62. The method of claim 59 wherein the signal points in said sequence belong to a 2D constellation and the step of selecting said signal point sequence is constrained so that the signal points in said sequence will usually be within some radius R.sub.c of the origin of said 2D constellation.

63. The method of claim 14 wherein the step of choosing a signal point sequence belonging to said congruence class is further constrained so as to reduce the peak power of said signal point sequence where said peak power represents the maximum energy of said signal point sequence in some number of dimensions N.

64. The method of claim 63 wherein N=2.

65. The method of claim 63 wherein N=4.

66. The method of claim 14 wherein the step of choosing a signal point sequence belonging to said congruence class comprises decoding said initial signal point sequence into a final signal point sequence comprising signal points belonging to a 2D constellation, said decoding being constrained so that only final signal point sequences whose signal points usually have magnitudes no greater than some predetermined radius R.sub.c from the origin of said constellation are used.

67. The method of claim 14 wherein the step of choosing a signal point sequence belonging to said congruence class comprises

decoding said initial signal point sequence into a code sequence using a Viterbi algorithm, and

in each recursion of the Viterbi algorithm, effecting an operation that will assure that said code sequence is an allowable sequence in said second code.

68. The method of claim 67 wherein said operation comprises adjusting the metrics of selected historical paths in the trellis of said Viterbi algorithm, so that none of said selected paths will become the most likely path in the next recursion of the Viterbi algorithm.

69. The method of claim 68 in which said historical paths are chosen based on whether they include particular state transitions at particular locations in the trellis of the Viterbi algorithm.

70. The method of claim 68 in which said operation comprises assigning a large metric to selected historical paths in said trellis.

71. The method of claim 1, 2, or 19, wherein said signal point sequence is selected in a manner to ensure that said digital data sequence can be recovered from a channel-affected version of said signal point sequence which has been subjected to one of a number of predetermined phase rotations.

72. The method of claim 15 wherein said step of mapping said digital data sequence into a sequence of signal points belonging to an initial constellation includes converting said data elements in said data sequence into groups of bits for selecting signal points from said initial constellation, and said groups of bits are arranged to ensure that said bits can be recovered from a channel-affected version of said transmitted sequence which has been subjected to phase rotations of one, two, or three times 90 degrees.

73. A modem for transmitting and receiving digital data sequences via a channel comprising

means for mapping a said digital data sequence into a sequence of signal points to be sent, including a sequence selector for selecting said signal point sequence from a subset of all possible signal point sequences based on said digital data sequence, all said possible signal point sequences in said subset lying in a fundamental region of a trellis code, said fundamental region being other than a simple Cartesian product of finite-dimensional regions,

a modulator for sending said signal points of said sequence via said channel,

a demodulator for receiving a possibly channel-affected version of said signal point sequence from said channel, and

means for recovering a digital data sequence from said possibly channel-affected version of said signal point sequence.

74. Apparatus for mapping a digital data sequence into a signal point sequence for transmission, comprising

means for receiving said digital data sequence, and

a sequence selector for selecting said signal point sequence from a subset of all possible signal point sequences based on said digital data sequence, all said possible signal point sequences in said subset lie in a fundamental region of a trellis code, said fundamental region being other than a simple Cartesian product of finite-dimensional regions.

75. Apparatus for mapping a digital data sequence into a signal point sequence for data transmission, comprising

means for specifying a class of possible signal point sequences based on said digital data sequence, and

means for selecting said signal point sequence from said class based on the respective average powers of said possible sequences of said class and based on not only a fixed-length block of the digital data.