EP0383632A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Mapping digital data sequences
Assignee: Motorola Solutions Inc
•
Filing: 1990-02-16
•
Granted: —
•
Expires: 2010-02-16
Abstract
Abstract In a so-called trellis shaping modulation system, instead of mapping a digital data sequence into a sequence of signal points drawn from a finite-dimensional signal point constellation as in typical coded modulation, the data sequence is mapped into a sequence of signal points drawn from a so-called trellis constellation of available infinite-dimensional sequences so that there is no 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; i.e., preferably the region is an approximation to the Voronoi region of the trellis code (where the trellis code is not just a repeated lattice code).
Inventors
- 👤 David G. Jr. Forney
- 👤 Vedat M. Eyuboglu
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-03 21:16
CPC Classifications
H; H04; H04L; H04L27/00; H04L27/32; H04L27/34; H04L27/3405; H04L27/3416; H04L27/3422; H04L27/3411
Claims Analysis
Total Claims: 58
Claim 1
Independent Claim
68 words
A method of mapping a digital data sequence into a signal point sequence for data transmission, comprising 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.
Claim 2
Independent Claim
68 words
A method of mapping a digital data sequence into a signal point sequence for data transmission, comprising 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.
Claim 3
Dependent Claim
31 words
The method of claim 1 wherein said possible signal point sequences are code sequences from a translate of a second code, said second code being of the trellis or lattice type.
Claim 4
Dependent Claim
18 words
The method of claim 1 wherein said fundamental region comprises approximately a Voronoi region of said trellis code.
Claim 5
Dependent Claim
35 words
The method of claim 1 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 some decoder for said code.
Claim 6
Dependent Claim
40 words
The method of claim 4 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.
Claim 7
Dependent Claim
46 words
The method of claim 5 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.
Claim 8
Dependent Claim
35 words
The method of claim 4 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.
Claim 9
Independent Claim
56 words
The method of any preceding claim 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.
Claim 10
Dependent Claim
40 words
The method of claim 8 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.
Claim 11
Dependent Claim
38 words
The method of claim 8 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.
Claim 12
Dependent Claim
45 words
The method of claim 10 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-') r T which is inverse to a syndrome-former matrix H T for said code.
Claim 13
Dependent Claim
60 words
The method of claim 11 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 .
Claim 14
Independent Claim
76 words
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 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.
Claim 15
Independent Claim
76 words
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 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.
Claim 16
Dependent Claim
38 words
The method of claim 13 in which the digital data sequence comprises a succession of data elements, and the step of determining the class of possible sequences comprises mapping each element into a point in an initial constellation.
Claim 17
Dependent Claim
35 words
The method of claim 14 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.
Claim 18
Dependent Claim
22 words
The method of claim 14 in which the mapping of each element is done independently of the mapping of any other element.
Claim 19
Dependent Claim
35 words
The method of claim 14 in which each element is a binary value and said initial constellation comprises 2 b points, where b is the number of bits in each said element of said sequence.
Claim 20
Dependent Claim
19 words
The method of claim 14 in which said initial constellation comprises a portion of a lattice or its translate.
Claim 21
Dependent Claim
19 words
The method of claim 18 in which said portion comprises a fundamental region of a sublattice of said lattice.
Claim 22
Dependent Claim
17 words
The method of claim 19 in which said sublattice is a time-zero lattice of a trellis code.
Claim 23
Dependent Claim
36 words
The method of claim 14 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.
Claim 24
Dependent Claim
39 words
The method of claim 21 in which 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.
Claim 25
Dependent Claim
29 words
The method of claim 22 in which the sequences within said common error region comprise signal points that comprise a final constellation with more points than said initial constellation.
Claim 26
Dependent Claim
19 words
The method of claim 21 in which said representative points are decoded by a minimum-distance decoder for said code.
Claim 27
Dependent Claim
17 words
The method of claim 24 wherein said minimum-distance decoder has decoding delay M and M a 1.
Claim 28
Dependent Claim
68 words
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 2 or 14, 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.
Claim 29
Dependent Claim
29 words
The method of claim 26 in which decoding the sequence of sent signal points is done at time j based on said sent points only up to time j.
Claim 30
Dependent Claim
17 words
The method of claim 1, 20 or 21 wherein said trellis code is a linear trellis code.
Claim 31
Dependent Claim
17 words
The method of claim 1, 20, or 21 wherein said trellis code is a non-linear trellis code.
Claim 32
Dependent Claim
15 words
The method of claim 28 wherein said linear trellis code is a 4-state Ungerboeck code.
Claim 33
Dependent Claim
15 words
The method of claim 28 wherein said linear trellis code is a dual Wei code.
Claim 34
Dependent Claim
20 words
The method of claim 1, 20, or 21 wherein said trellis code is based on a partition of binary lattices.
Claim 35
Dependent Claim
22 words
The method of claim 1, 20 or 21 wherein said trellis code is based on a partition of ternary or quaternary lattices.
Claim 36
Dependent Claim
25 words
The method of claim 8 or 14 in which the mapping of data elements to points in the initial constellation is linear or distance invariant.
Claim 37
Independent Claim
71 words
A method of mapping a digital data sequence into a sequence of signal points to be sent, comprising making a selection of the sequence of signal points to be sent from a class of possible sequences specified by said digital data, said selection being based on the average power of said different possible sequences of said class, said selection being based on not only a finite block of the digital data.
Claim 38
Independent Claim
71 words
A method of mapping a digital data sequence into a sequence of signal points to be sent, comprising making a selection of the sequence of signal points to be sent from a class of possible sequences specified by said digital data, said selection being based on the average power of said different possible sequences of said class, said selection being based on not only a finite block of the digital data.
Claim 39
Dependent Claim
71 words
Apparatus for mapping a digital data sequence into a signal point sequence for data transmission, comprising 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.
Claim 40
Dependent Claim
71 words
Apparatus for mapping a digital data sequence into a signal point sequence for data transmission, comprising 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.
Claim 41
Dependent Claim
80 words
Apparatus for mapping a digital data sequence into a sequence of signal points to be sent, comprising a mapper for determining a class of possible sequences from which a select said sequence to be sent, based on digital data appearing in said digital data sequence up to a time j, and a sequence selector, for every time j, said sequence to be sent from said class of possible sequences based on digital data appearing in said sequence after time j.
Claim 42
Dependent Claim
80 words
Apparatus for mapping a digital data sequence into a sequence of signal points to be sent, comprising a mapper for determining a class of possible sequences from which a select said sequence to be sent, based on digital data appearing in said digital data sequence up to a time j, and a sequence selector, for every time j, said sequence to be sent from said class of possible sequences based on digital data appearing in said sequence after time j.
Claim 43
Dependent Claim
51 words
The method of claim 1, 13, or 36 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.
Claim 44
Dependent Claim
9 words
The method of claim 38 wherein N = 2.
Claim 45
Dependent Claim
9 words
The method of claim 38 wherein N = 4.
Claim 46
Dependent Claim
51 words
The method of claim 1 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 c of the origin of said 2D constellation.
Claim 47
Dependent Claim
53 words
The method of claim 8 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.
Claim 48
Dependent Claim
9 words
The method of claim 42 wherein N = 2.
Claim 49
Dependent Claim
9 words
The method of claim 42 wherein N = 4.
Claim 50
Dependent Claim
73 words
The method of claim 8 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 r from the origin of said constellation are used.
Claim 51
Dependent Claim
60 words
The method of claim 2 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.
Claim 52
Dependent Claim
44 words
The method of claim 46 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.
Claim 53
Dependent Claim
30 words
The method of claim 47 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.
Claim 54
Dependent Claim
21 words
The method of claim 47 in which said operation comprises assigning a large metric to selected historical paths in said trellis.
Claim 55
Dependent Claim
56 words
The method of claim 1, 13, or 35, wherein said step of mapping said digital 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.
Claim 56
Dependent Claim
84 words
The method of claim 9 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.
Claim 57
Dependent Claim
133 words
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.
Claim 58
Dependent Claim
133 words
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.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.