US4959842A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Signal constellations
Assignee: Motorola Solutions Inc
•
Filing: 1988-04-13
•
Granted: 1990-09-25
•
Expires: 2008-04-13
Abstract
Abstract A Voronoi signal constellation with ties includes those points of a lattice Λ (or a coset Λ+c) that lie within a Voronoi region of a sublattice Λ' of Λ, Λ' being other then a scaled version of Λ, and the constellation includes more than |Λ/Λ'| points, where |Λ/Λ'| is the order of the lattice partition Λ/Λ'. In order aspects, the lattices Λ and Λ' are of dimension greater than two; the sublattice Λ' is a version of a binary lattice of depth at least two and normalized informativity less than one; a method is provided of mapping from m data bits to a point drawn from a Voronoi constellation of more than 2 m points, based on an N-dimensional lattice partition Λ/Λ'; and Voronoi constellations are provided comprising points of a lattice Λ (or a coset Λ+c) that lie within a Voronoi region of a sublattice Λ' of Λ, the sublattice Λ' comprising a binary lattice of depth two and normalized informativity less than one. Such sublattices Λ' are also useful in lattice quantizers.
Inventors
- 👤 G. David Forney, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 21:45
CPC Classifications
H; H04; H04L; H04L27/00; H04L27/32; H04L27/34; H04L27/345; H04L27/3461; H04L27/3477; H04L27/3405; H04L27/3416; H04L27/3427
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
98 words
Apparatus for communicating data over a channel comprising an encoder for selecting a series of signal points from a constellation of available points, said constellation comprising points of a lattice Λ (or a coset Λ+c, where c is a translation vector) that lie within a Voronoi region of a sublattice Λ' of Λ, Λ' being other than a scaled version of Λ, said constellation comprising more than |Λ/Λ'| points, where |Λ/ζ'| is the order of the lattice partition Λ/Λ', and a modulator for modulating a carrier on said channel in accordance with said selected series of signal points.
Claim 2
Dependent Claim
98 words
Apparatus for communicating data over a channel comprising an encoder for selecting a series of signal points from a constellation of available points, said constellation comprising points of a lattice Λ (or a coset Λ+c, where c is a translation vector) that lie within a Voronoi region of a sublattice Λ' of Λ, Λ' being other than a scaled version of Λ, said constellation comprising more than |Λ/Λ'| points, where |Λ/ζ'| is the order of the lattice partition Λ/Λ', and a modulator for modulating a carrier on said channel in accordance with said selected series of signal points.
Claim 3
Dependent Claim
100 words
Apparatus for communicating data over a channel comprising an encoder for selecting a series of signal points from a constellation of available points, said constellation comprising points of a lattice Λ (or a coset Λ+c, where c is a translation vector) that lie within a Voronoi region of a sublattice Λ' of Λ, said lattices Λ and Λ' being of dimension greater than two, said constellation comprising more than |Λ/Λ'| points, where |Λ/Λ'| is the order of the lattice partition Λ/Λ', and a modulator for modulating a carrier on said channel in accordance with said selected series of signal points.
Claim 4
Dependent Claim
100 words
Apparatus for communicating data over a channel comprising an encoder for selecting a series of signal points from a constellation of available points, said constellation comprising points of a lattice Λ (or a coset Λ+c, where c is a translation vector) that lie within a Voronoi region of a sublattice Λ' of Λ, said lattices Λ and Λ' being of dimension greater than two, said constellation comprising more than |Λ/Λ'| points, where |Λ/Λ'| is the order of the lattice partition Λ/Λ', and a modulator for modulating a carrier on said channel in accordance with said selected series of signal points.
Claim 5
Dependent Claim
91 words
Apparatus for communicating data over a channel comprising an encoder for selecting a series of signal points from a constellation of available points, said costellation comprising points of a lattice Λ (or a coset Λ+c, where c is a translation vector) that lie within a Voronoi region of a sublattice Λ' of Λ, Λ' comprising a version of a binary lattice of depth at least two and normalized informativity less than one, and a modulator for modulating a carrier on said channel in accordance with said selected series of signal points.
Claim 6
Dependent Claim
91 words
Apparatus for communicating data over a channel comprising an encoder for selecting a series of signal points from a constellation of available points, said costellation comprising points of a lattice Λ (or a coset Λ+c, where c is a translation vector) that lie within a Voronoi region of a sublattice Λ' of Λ, Λ' comprising a version of a binary lattice of depth at least two and normalized informativity less than one, and a modulator for modulating a carrier on said channel in accordance with said selected series of signal points.
Claim 7
Dependent Claim
26 words
The apparatus of claim 1, 2, or 3 wherein said constellation includes all points of said Voronoi region, including all boundary points in Λ (or Λ+c).
Claim 8
Dependent Claim
20 words
The apparatus of claim 1, 2, or 3 wherein c is selected so that said constellation has a predetermined symmetry.
Claim 9
Dependent Claim
15 words
The apparatus of claim 5 wherein said symmetry is a rotational symmetry about the origin.
Claim 10
Dependent Claim
14 words
The apparatus of claim 6 wherein said rotational symmetry is three-way, four-way, or six-way.
Claim 11
Dependent Claim
32 words
The apparatus of claim 1, 2, or 3 wherein said encoder may encode at least one element of said data into any one of at least two different points of said constellation.
Claim 12
Dependent Claim
23 words
The apparatus of claim 8 wherein the result of said encoding is that said at least two different points occur with equal probability.
Claim 13
Dependent Claim
39 words
The apparatus of claim 8 wherein, when said one data element appears, said encoder chooses among said at least two different points based on a secondary stream of data, thereby providing an opportunistic secondary channel for said secondary stream.
Claim 14
Dependent Claim
20 words
The apparatus of claim 8 wherein said at least two different points lie on the boundary of said Voronoi region.
Claim 15
Dependent Claim
19 words
The apparatus of claim 1, 2, or 3 wherein sublattice Λ' is of a different type from lattice Λ.
Claim 16
Dependent Claim
21 words
The apparatus of claim 1, 2, or 3 wherein said series of signal points is selected based on a coset code.
Claim 17
Dependent Claim
25 words
The apparatus of claim 1, 2, or 3 wherein said lattice Λ is a version of an integer lattice Z N , N an integer.
Claim 18
Dependent Claim
32 words
The apparatus of claim 1, 2, or 3 wherein said lattice Λ is a ternary or quaternary lattice whose constituent 2D lattice is a version of the hexagonal lattice Λ 2 .
Claim 19
Dependent Claim
21 words
The apparatus of claim 1 or 2 wherein said sublattice Λ' is a version of the Schlafli lattice D 4 .
Claim 20
Dependent Claim
16 words
The apparatus of claim 1, 2, or 3 wherein said constellation is 16-, 24-, or 32-dimensional.
Claim 21
Dependent Claim
19 words
The apparatus of claim 1, 2, or 3 wherein said sublattice Λ has an 8-state or 16-state trellis diagram.
Claim 22
Dependent Claim
21 words
The apparatus of claim 1, 2, or 3 wherein said sublattice is based on a partition E 8 /RD 8 *.
Claim 23
Dependent Claim
26 words
The apparatus of claim 1, 2, or 3 wherein said sublattice Λ comprises the mod-2 lattice H 16 *=Λ.sub.(16,5), where (16,5) is a first-order Reed-Muller code.
Claim 24
Dependent Claim
19 words
The apparatus of claim 1, 2, or 3 wherein said sublattice Λ' comprises the mod-2 lattice X 24 *=Λ.sub.(24,6).
Claim 25
Dependent Claim
17 words
The apparatus of claim 1, 2, or 3 wherein said sublattice Λ' comprises the mod-2 lattice Λ.sub.(32,7).
Claim 26
Independent Claim
157 words
A method of mapping from m data bits to a point drawn from a Voronoi constellation of more than 2 m points, based on an N-dimensional lattice partition Λ/Λ', m and N being positive numbers, comprising mapping said m bits to one of 2 m initial signal points x, each said initial point x consisting of N coordinates (x 1 , . . . , x N ), each coordinate taking on one of a predetermined set of values, the number of elements in all such sets of coordinate values not being identical, each initial point being a point in a coset of Λ that belongs to a distinct equivalence class modulo Λ', decoding said initial signal point x into a point λ in Λ with a minimum-distance decoder for Λ, and deriving the apparent error e=x-λ (or a translate e-c of such apparent error, where c is a translation vector) as the said Voronoi constellation point.
Claim 27
Independent Claim
157 words
A method of mapping from m data bits to a point drawn from a Voronoi constellation of more than 2 m points, based on an N-dimensional lattice partition Λ/Λ', m and N being positive numbers, comprising mapping said m bits to one of 2 m initial signal points x, each said initial point x consisting of N coordinates (x 1 , . . . , x N ), each coordinate taking on one of a predetermined set of values, the number of elements in all such sets of coordinate values not being identical, each initial point being a point in a coset of Λ that belongs to a distinct equivalence class modulo Λ', decoding said initial signal point x into a point λ in Λ with a minimum-distance decoder for Λ, and deriving the apparent error e=x-λ (or a translate e-c of such apparent error, where c is a translation vector) as the said Voronoi constellation point.
Claim 28
Dependent Claim
54 words
The method of claim 23 wherein said point drawn from said constellation is used for transmission on a channel and is taken as said apparent error e if λ is the unique closest point to x, or otherwise is selected from the set [e] of equivalent constellation points that are equally close to x.
Claim 29
Dependent Claim
65 words
In apparatus for quantizing a real N-tuple r comprising a minimum-distance decoder for finding the closest point λ in an N-dimensional lattice Λ' to r, N being a positive number, and means for indicating said closest point as a quantized representation of r, the improvement in which said lattice Λ' is a binary lattice of depth at least 2 and normalized informatively less than one.
Claim 30
Dependent Claim
65 words
In apparatus for quantizing a real N-tuple r comprising a minimum-distance decoder for finding the closest point λ in an N-dimensional lattice Λ' to r, N being a positive number, and means for indicating said closest point as a quantized representation of r, the improvement in which said lattice Λ' is a binary lattice of depth at least 2 and normalized informatively less than one.
Claim 31
Dependent Claim
13 words
The improvement of claim 25 wherein said lattice is 16-, 24- or 32-dimensional.
Claim 32
Dependent Claim
15 words
The improvement of claim 25 wherein said lattice has an 8-state or 16-state trellis diagram.
Claim 33
Dependent Claim
19 words
The improvement of claim 25 wherein said lattice is based on a lattice partition E 8 /RD 8 *.
Claim 34
Dependent Claim
16 words
The improvement of claim 25 wherein said lattice Λ comprises the mod-2 lattice H 16 *=Λ.sub.(16,5).
Claim 35
Dependent Claim
16 words
The improvement of claim 25 wherein said lattice Λ' comprises the mod-2 lattice X 24 *=Λ.sub.(24,6).
Claim 36
Dependent Claim
14 words
The improvement of claim 25 wherein said lattice Λ' comprises the mod-2 lattice Λ.sub.(32,7).
References Cited (Backward Citations)
US3805191A
Cited
US4538284A
Cited
US4495477A
Cited
US4562426A
Cited
US4630287A
Cited
US4713817A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-09-24 | 1994-03-26 | 1994-09-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-09-24 | 1998-03-26 | 1998-09-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-09-24 | 2002-03-26 | 2002-09-25 | $7700.00 | Window Closed / Lapsed |