Trellis precoding for modulation systems

• US 5,159,610 A
• Filed: 01/16/1992
• Issued: 10/27/1992
• Est. Priority Date: 05/12/1989
• Status: Expired due to Term

• Current Assignee: CIF Licensing LLC
• Original Assignee: Codex Corporation
• Inventors: Forney, G. David Jr., Eyuboglu, Vedat M.
• Primary Examiner(s): Chin, Stephen
• Application Number:
  US07/823,586
• Time in Patent Office: 285 Days
• Field of Search: 375/17, 375/18, 375/27, 375/38, 375/39, 375/42, 375/58, 375/67, 375/11, 375/12, 371/2, 371/37, 371/39, 371/40, 371/41, 371/43, 371/50, 332/9 R, 332/10
• US Class Current: 375/290
• CPC Class Codes: H04L 2025/03656 Initialisation
• CPC Class Codes: H04L 2025/03662 to a fixed value
• CPC Class Codes: H04L 2025/03808 Transmission of equaliser coefficients
• CPC Class Codes: H04L 25/03044 using fractionally spaced delay lines or combinations of fractionally integrally spaced taps
• CPC Class Codes: H04L 25/03343 Arrangements at the transmitter end
• CPC Class Codes: H04L 27/3422 in which the constellation is not the n - fold Cartesian product of a single underlying two-dimensional constellation

Abstract

In general the invention features mapping a digital data sequence into a signal point sequence for data transmission over a channel characterized by a non-ideal response, by selecting the signal point sequence from a subset of all possible signal point sequences based on the digital data sequence and upon the response, all possible signal point sequences in the subset lying in a fundamental region of a filtered trellis code, the fundamental region being other than a simple Cartesian product of finite-dimensional regions.

Claims

1. A method of mapping a digital data sequence into a signal point sequence for data transmission over a channel characterized by a non-ideal response, comprising

defining a filtered trellis code,

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

2. The method of claim 1 in which said filtered trellis code is the code whose sequences are c'"'"'(D)=c(D)g(D) where g(D) is the formal inverse of a response related to said non-ideal response of said channel and c(D) is any code sequence in a selected ordinary trellis code.

3. The method of claim 2 in which the selecting step tends to minimize the average power of the signal point sequence e(D)=[x(D)-c(D)] g(D), where x(D) is an initial sequence to which said digital data sequence is initially mapped.

4. The method of claim 3 wherein x(D) lies in a fundamental region of said ordinary trellis code.

5. The method of claim 4 wherein said fundamental region of said ordinary trellis code is a simple Cartesian product of finite dimensional regions.

6. The method of claim 2 in which said selecting of said signal point sequence comprises reduced state sequence estimation with respect to said filtered trellis code.

7. The method of claim 6 in which the reduced state sequence estimation uses no more states than the number of states of the ordinary trellis code.

8. The method of claim 2 wherein said fundamental region of said filtered trellis code comprises approximately a Voronoi region of said filtered trellis code.

9. The method of claim 2 wherein said fundamental region of said filtered trellis code comprises the set of said possible signal point sequences that are decoded to the zero sequence in said filtered trellis code by some decoder for said filtered trellis code.

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

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

12. The method of claim 1 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^T.

13. The method of claim 1 wherein said selecting comprises selecting an initial sequence lying in a fundamental region of said filtered trellis code that is a simple Cartesian product of finite-dimensional regions.

14. The method of claim 5 wherein said finite dimensional fundamental region is a fundamental region of the time-zero lattice of said ordinary trellis code.

15. The method of claim 2 wherein said selecting comprises

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

choosing a signal point sequence belonging to and representing a congruence class of said filtered trellis code and which has no greater average power than said initial sequence, and wherein

said mapping includes applying a portion of the elements of said diqital data sequence to a coset representative generator for forming a larger number of digital elements representing a coset representative sequence.

16. 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^-1)^T which is inverse to a syndrome-former matrix H^T for said filtered trellis code.

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

18. The method of claim 2 wherein said ordinary trellis code is a linear trellis code.

19. The method of claim 2 wherein said ordinary trellis code is a non-linear trellis code.

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

21. The method of claim 2 wherein said ordinary trellis code is based on a partition of binary lattices.

22. The method of claim 2 wherein said ordinary trellis code is based on a partition of ternary or quaternary lattices.

23. The method of claim 15 in which the mapping of said digital data sequence into said initial sequence is linear or distance invariant.

24. The method of claim 2 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.

25. The method of claim 24 wherein N=2.

26. The method of claim 24 wherein N=4.

27. The method of claim 24 wherein said selecting is constrained so that said signal point sequence will usually be within some sphere of radius R_c.

28. The method of claim 6 wherein said reduced state sequence estimation comprises a step wherein, in each recursion, there is an operation that will assure that said sequence c(D) is an allowable sequence.

29. The method of claim 28 wherein said operation comprises adjusting the metrics of selected paths in the trellis of said reduced state sequence estimation, so that none of said selected paths will become the most likely path in the next recursion.

30. The method of claim 29 in which said paths are chosen based on whether they include particular state transitions at particular locations in said trellis.

31. The method of claim 29 in which said operation comprises assigning a large metric to said selected paths in said trellis.

32. The method of claim 2 wherein said step of mapping said diqital data sequence into said signal point sequence is arranged 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.

33. The method of claim 14 wherein said step of mapping said diqital 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.

34. The method of claim 13 wherein said initial sequence is a code sequence from a translate of a second code, said second code being of the trellis or lattice type.

35. Apparatus for mapping a digital data sequence into a signal point sequence for data transmission over a channel characterized by a non-ideal response, comprising

means for accepting said digital data sequence, and

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

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

means for mapping a said diqital data sequence into a signal point sequence for data transmission over a channel characterized by a non-ideal response, including a sequence selector for selecting said signal point sequence from a subset of all possible signal point sequences based on said diqital data sequence and upon said response, all said possible signal point sequences in said subset lying in a fundamental region of a filtered 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.

37. The modem of claim 36 wherein said means for recovering comprises

an adaptive prediction filter,

wherein, during data transmission, said prediction filter is kept fixed, and

a g(D) element through which the final prediction error from the prediction filter is passed in order to reconstruct the equalizer error.