Signal constellations

• US 4,959,842 A
• Filed: 04/13/1988
• Issued: 09/25/1990
• Est. Priority Date: 04/13/1988
• Status: Expired due to Term

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Codex Corporation
• Inventors: Forney, G. David Jr.
• Primary Examiner(s): Safourek, Benedict V.
• Application Number:
  US07/181,203
• Time in Patent Office: 895 Days
• Field of Search: 375/39, 375/42, 375/54, 375/57, 332/9 R, 332/10, 332/103, 332/104, 332/106, 332/115, 370/77, 370/110.1, 370/110.4, 370/119, 371/43, 371/44, 341/56, 341/80
• US Class Current: 375/261
• CPC Class Codes: H04L 27/3427 in which the constellation is the n - fold Cartesian product of a single underlying two-dimensional constellation
• CPC Class Codes: H04L 27/3477 by using the outer points of the constellation or of the constituent two-dimensional constellations

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.

Claims

1. 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.

4. 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).

5. The apparatus of claim 1, 2, or 3 wherein c is selected so that said constellation has a predetermined symmetry.

6. The apparatus of claim 5 wherein said symmetry is a rotational symmetry about the origin.

7. The apparatus of claim 6 wherein said rotational symmetry is three-way, four-way, or six-way.

8. 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.

9. The apparatus of claim 8 wherein

the result of said encoding is that said at least two different points occur with equal probability.

10. 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.

11. The apparatus of claim 8 wherein said at least two different points lie on the boundary of said Voronoi region.

12. The apparatus of claim 1, 2, or 3 wherein sublattice Λ

'"'"' is of a different type from lattice Λ

.

13. The apparatus of claim 1, 2, or 3 wherein said series of signal points is selected based on a coset code.

14. The apparatus of claim 1, 2, or 3 wherein said lattice Λ

is a version of an integer lattice Z^N, N an integer.

15. 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 Λ

₂.

16. The apparatus of claim 1 or 2 wherein said sublattice Λ

'"'"' is a version of the Schlafli lattice D₄.

17. The apparatus of claim 1, 2, or 3 wherein said constellation is 16-, 24-, or 32-dimensional.

18. The apparatus of claim 1, 2, or 3 wherein said sublattice Λ

has an 8-state or 16-state trellis diagram.

19. The apparatus of claim 1, 2, or 3 wherein said sublattice is based on a partition E₈ /RD₈ *.

20. The apparatus of claim 1, 2, or 3 wherein said sublattice Λ

comprises the mod-2 lattice H₁₆ *=Λ

.sub.(16,5), where (16,5) is a first-order Reed-Muller code.

21. The apparatus of claim 1, 2, or 3 wherein said sublattice Λ

'"'"' comprises the mod-2 lattice X₂₄ *=Λ

.sub.(24,6).

22. The apparatus of claim 1, 2, or 3 wherein said sublattice Λ

'"'"' comprises the mod-2 lattice Λ

.sub.(32,7).

2. 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.

3. 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.

23. 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₁, . . . , 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.

24. 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.

25. 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.

26. The improvement of claim 25 wherein said lattice is 16-, 24- or 32-dimensional.

27. The improvement of claim 25 wherein said lattice has an 8-state or 16-state trellis diagram.

28. The improvement of claim 25 wherein said lattice is based on a lattice partition E₈ /RD₈ *.

29. The improvement of claim 25 wherein said lattice Λ

comprises the mod-2 lattice H₁₆ *=Λ

.sub.(16,5).

30. The improvement of claim 25 wherein said lattice Λ

'"'"' comprises the mod-2 lattice X₂₄ *=Λ

.sub.(24,6).

31. The improvement of claim 25 wherein said lattice Λ

'"'"' comprises the mod-2 lattice Λ

.sub.(32,7).