Back to EveryPatent.com
| United States Patent |
5,214,672
|
|
Eyuboglu
, et al.
|
May 25, 1993
|
Trellis precoding for fractional bits/baud
Abstract
A digital data sequence is mapped into a signal point sequence e(D) for
data transmission over a channel h(D) to produce a channel output sequence
y(D)=e(D)h(D). e(D) is chosen so that the signal points in the sequence
y(D) belong to a class of possible sequences based on the digital data
sequence, the class being based on a time-varying trellis code derived
from an N-dimensional time-invariant trellis code by using different
transformed versions of its underlying lattices for respectively different
N-dimensional symbols.
| Inventors:
|
Eyuboglu; Vedat (Boston, MA);
Chen; Michael P. (Boston, MA)
|
| Assignee:
|
Codex Corporation (Mansfield, MA)
|
| Appl. No.:
|
505418 |
| Filed:
|
April 6, 1990 |
| Current U.S. Class: |
375/254; 375/265; 714/792 |
| Intern'l Class: |
H04L 027/34 |
| Field of Search: |
375/39,27,34
371/43
332/103,106
|
References Cited
U.S. Patent Documents
| 4077021 | Feb., 1978 | Csajka etal. | 371/43.
|
| 4586182 | Apr., 1986 | Gallager | 371/43.
|
| 4713817 | Dec., 1987 | Wei | 375/39.
|
| 4959842 | Sep., 1990 | Forney, Jr. | 332/103.
|
| 5048054 | Sep., 1991 | Eyuboglu et al. | 375/8.
|
Other References
"Rotationally Invariant Convolutional Channel Coding with Expanded Signal
Space--Part I: 180.degree. and--Part II:Nonlinears Codes" IEEE JSAC, pp.
659-686.
"Multidimentional Constellations--Part I:Introduction, Figures of Merit,
and Generalized Cross Constellations", IEEE JSAC, pp. 877-892, Aug. 1989.
Forney et al., "Efficient Modulation for Band-Limited Channels", JSAC, vol.
2, No. 5, Sep., 1984.
Forney and Wei, IEEE Journal on Selected Areas in Communication 7:877-892,
1989 "Multidimensional Constellations--Part I:Introduction, Figures of
Merit and Generalized Cross Constallations".
Forney, IEEE Journal on Selected Areas in Communications 1-43, 1988
"Multidemensional Constallations-Part II: Voroni Constallations".
Forney et al., IEEE Transactions on Information Theory 34:1123-1151, 1988,
"Coset Codes--Part I: Introduction and Geometrical Classication".
Wei IEEE Transactions on Information Theory 33:483-501, 1987 "Trellis-Coded
Modulation with Multidimensional Constellations".
Price, "Nonlinearly Feedback-Equalized PAM vs Capacity, for Noisy Filter
Channels" 22-12-22-17.
Salz, The Bell System Technical Journal 52:1341-1373, 1973 "Optimum
Mean-Square Decision Feedback Equalization".
Chevillat et al., Transactions on Communications 35:869-874, 1987 "Rapid
Training of a Voiceband Data-Modem Receiver Employing an Equalizer with
Fractional-T Spaced Coefficients".
|
Primary Examiner: Kuntz; Curtis
Assistant Examiner: Tse; Young
Attorney, Agent or Firm: Fish & Richardson
Claims
We claim:
1. A method of mapping a digital data sequence into a signal point sequence
e(D) for data transmission over a channel with impulse response h(D) to
produce a channel output sequence y(D)=e(D)h(D), comprising the steps of
defining a class of possible sequences based on a time-varying trellis code
derived from an N-dimensional time-invariant trellis code C by using
different transformed versions of its underlying lattices for respectively
different N-dimensional symbols, and
choosing e(D) so that the signal points in the sequence y(D) belong to said
class of possible sequences based on said digital data sequence.
2. The method of claim 1 wherein said class comprises a signal space
translate of a time-varying trellis code C.sub.s, where the translation is
a code sequence from a translate of a trellis code C.sub.c determined
based on said digital data sequence, and said time-varying trellis code
C.sub.s is derived from an N-dimensional time-invariant trellis code
C(.LAMBDA./.LAMBDA.', C.sub.s ) by using different transformed versions of
its underlying lattices .LAMBDA. and .LAMBDA. for respectively different
N-dimensional signal points.
3. The method of claim 1 wherein said class comprises a signal space
translate of a trellis code C.sub.s, where the translation is a code
sequence from a translate of a time-varying trellis code C.sub.c
determined based on said digital data sequence and said time varying
trellis code C.sub.c is derived from an N dimensional time-invariant
trellis code C(L/L', C.sub.c) by using different transformed versions of
its underlying lattices L and L' for respectively different N dimensional
signal points.
4. The method of claim 1 wherein said class comprises a signal space
translate of a label translate of a time-varying trellis code C.sub.s,
where the label translate is based on a portion of said digital data
sequence and the signal space translation is based on another portion of
the elements of said digital data sequence, and the time-varying trellis
code C.sub.s is derived from an N-dimensional time-invariant trellis code
C(.LAMBDA./.LAMBDA.', C.sub.s) by using different transformed versions of
its underlying lattices .LAMBDA. and .LAMBDA.' for respectively different
N-dimensional signal points.
5. The method of claim 1 wherein said class comprises a signal space
translate of a label translate of a trellis code C.sub.s, where the label
translate is based on a portion of said digital data sequence, where the
signal space translation is based on another portion of the elements of
said digital data sequence and is a code sequence from a time-varying
trellis code C.sub.c which is derived from an N-dimensional-time invariant
trellis code C(L/L', C.sub.c) by using different transformed versions of
its underlying lattices L and L' for respectively different N-dimensional
signal points.
6. The method of claim 1 wherein said class of possible sequences is
identified by some sequence of subregions into which N-space has been
partitioned, said sequence of subregions being specified by a label
sequence determined based on a portion of the digital data sequence and
said signal points in said subregions belonging to a coset of a
time-varying trellis code C.sub.c, where the sequences from said
time-varying trellis code C.sub.c are chosen based on another portion of
the elements of said digital data sequence, and the time-varying trellis
code C.sub.c is derived from an N-dimensional time-invariant trellis code
C(L/L', C.sub.c) by using different transformed versions of its underlying
lattices L and L' for respectively different N-dimensional signal points.
7. The method of claim 1 wherein said class of possible sequences is
identified by some sequence of subregions into which N-space has been
partitioned, said sequence of subregions being specified by a label
sequence, which belongs to a coset of a convolutional code C.sub.s, based
on a portion of the elements of the digital data sequence and using
different scaled versions of said subregions for respectively different
N-dimensional signal points, said coset being determined based on another
portion of the digital data sequence, where the signal points in the
sequence y(D) are chosen based on a portion of the elements of said
digital data sequence, and wherein said subregions are scaled versions of
each other.
8. A method of mapping a digital data sequence into a signal point sequence
e(D) for data transmission over a channel h(D) (h(D) not a constant) to
produce a channel output sequence y(D)=e(D)h(D), comprising the steps of
defining a label translate of a trellis code C.sub.s based on a portion of
said digital data sequence, and
choosing e(D) so that y(D) belongs to a signal space translate of said
label translate, said signal space translation being specified based on
another portion of the elements of said digital data sequence and being a
code sequence from a trellis code C.sub.c.
9. A method of mapping a digital data sequence into a signal point sequence
e(D) for data transmission over a channel h(D) (h(D) not a constant) to
produce a channel output sequence y(D)=e(D)h(D), comprising the steps of
defining a label sequence based on a portion of the elements of the digital
data sequence,
specifying a sequence of subregions into which N-space has been partitioned
based on said label sequence, signal points in said subregions belonging
to a coset of a trellis code C.sub.c, and
choosing e(D) so that the signal points in the sequence y(D) belong to said
specified sequence of subregions, sequences from said trellis code C.sub.c
being chosen based on another portion of the elements of said digital data
sequence.
10. The method of claim 6, 7 or 9 wherein said label sequence belongs to a
coset of a convolutional code C.sub.s.
11. The method of claim 1, 2, 3, 4, 5, or 6 wherein said transformed
versions are respectively used periodically.
12. The method of claim 11 wherein each period in which said transformed
versions are used periodically encompasses multiple N-dimensional symbols.
13. The method of claim 1, 2, 3, 4, 5, or 6 wherein only two said different
transformed versions are used alternatingly.
14. The method of claim 1, 2, 3, 4, 5, or 6 wherein said transformed
versions comprise rotated or scaled or rotated and scaled versions of said
underlying lattices.
15. The method of claim 2, 3, 4, 5, 8, or 9 further comprising the step of
filtering said trellis code C.sub.s to form a filtered trellis code
C.sub.s, whose sequences are c.sub.s '(D)=c.sub.s (D)g(D) where g(D) is
the formal inverse of a response related to the channel response h(D), and
c.sub.s (D) is any code sequence in the trellis code C.sub.s.
16. The method of claim 15 in which the signal point sequence selection
tends to minimize the average power of the signal point sequence
e(D)=y(D)g(D).
17. The method of claim 16 wherein said signal point sequence e(D) lies in
a fundamental region of said filtered trellis code C.sub.s '.
18. The method of claim 15 wherein said signal point sequence e(D) lies in
a fundamental region of said filtered trellis code C.sub.s '.
19. The method of claim 18 wherein said fundamental region of said filtered
trellis code C.sub.s ' comprises a Voronoi region of said filtered trellis
code C.sub.s '.
20. The method of claim 15 in which the signal point sequence is selected
based on reduced state sequence estimation with respect to said filtered
trellis code C.sub.s '.
21. The method of claim 20 in which the reduced state sequence estimation
uses no more states than the number of states of the original filtered
trellis code C.sub.s '.
22. The method of claim 15 wherein said signal point sequence is selected
by
mapping said digital data sequence into an initial sequence belonging to
and representing a congruence class of said trellis code C.sub.s, and
choosing a signal point sequence belonging to and representing a congruence
class of said filtered trellis code C.sub.s ' and which has no greater
average power than said initial sequence, and 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.
23. The method of claim 22 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 trellis code
C.sub.s.
24. The method of claim 23 further comprising the step of 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 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.
25. The method of claim 1, 2, 3, 4, 5, 6, 7, 8 or 9 further comprising the
step of 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.
26. The method of claim 2, 3, 4, 5, 8, or 9 wherein said trellis code
C.sub.s is a linear trellis code.
27. The method of claim 25 wherein said linear trellis code C.sub.s is a
4-state Ungerboeck code.
28. The method of claim 2, 3, 4, 5, 8, or 9 wherein said trelis code
C.sub.s is a non-linear trellis code.
29. The method of claim 2, 3, 4, 5, 8, or 9 wherein said trellis code
C.sub.s is based on a partition of binary lattices.
30. The method of claim 2, 3, 4, 5, 8, or 9 wherein said trellis code
C.sub.s is based on a partition of ternary or quaternary lattices.
31. The method of claim 1, 2, 3, 4, 5, 6, 7, 8, or 9 further comprising the
step of selecting said signal point sequence in a manner which is
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.
32. The method of claim 31 wherein N=2.
33. The method of claim 31 wherein N=4.
34. The method of claim 1, 2, 3, 4, 5, 6, 7, 8, or 9 further comprising the
step of mapping said digital data sequence into said signal point sequence
in a manner 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 particular phase rotations.
Description
BACKGROUND OF THE INVENTION
This invention relates to modulation systems for sending digital data via a
channel.
In a quadrature amplitude modulation (QAM) system, for example, two key
parameters are the baud rate 1/T and the number of bits per baud .beta..
The bit rate R of the QAM system is given by R=.beta./T, measured in bits
per second (b/s).
Transmission equipment, such as a voiceband modem, operates at one of a
number of possible bit rates (e.g., in the range 9.6 to 19.2 kb/s)
depending on the line quality or the user's requirement. Therefore, for a
given baud rate such a modem must be able to operate at different values
of .beta., which may be a fraction, and the different values of .beta. may
not differ simply by integers. For example, if the baud rate is 2743
symbols/s, then to send at conventional modem rates of 19.2, 16.8, and
14.4 kb/s requires .beta.=7, 6.125 and 5.25, respectively.
When .beta. is a rational number of the form .beta.=n+d/2.sup.m, where n
and 0.ltoreq.d<2.sup.m are integers, a higher-dimensional (higher than
two-dimensional) QAM constellation of dimension L=2.sup.m+1 with
2.sup..beta.L/2 points can be used to represent .beta.L/2 bits over L
dimensions. Higher-dimensional constellations save in average power when
their signal points are chosen to lie within hyperspheres instead of
hypercubes. This saving, called shaping gain, can be as high as 1.53 dB.
Because the size of the signal constellation increases rapidly with n and
m, mapping from bits to signal points can be cumbersome. For example, in
an uncoded system (one in which there is no interdependence between
selected signal points), to send 7.5 bits/baud, a four-dimensional
constellation with 2.sup.15 =32,768 points is needed, which may be too
large to handle. However, such a 4D constellation can be formed by the
Cartesian product of simple 128-point and 256-point two-dimensional
constellations. More generally, a simple way of sending .beta.=n+d/2.sup.m
bits per two-dimensions is to define a series of frames each encompassing
the bits in a group of 2.sup.m bauds and then for each frame send n
bits/baud for (2.sup.m -d) bauds and send (n+1) bits/baud for d bauds. The
average power per two-dimensions for this scheme is approximately
P.sub..beta. =P.sub.n (1+d/2.sup.m), where P.sub.n is the average power of
a 2.sup.n -point two-dimensional (2D) QAM constellation (The 2D
constellations are scaled to have the same minimum distance between
adjacent points.). This approach is approximately as efficient as a
conventional QAM system sending an integer number of bits/baud. However,
the imbalance in size between the two 2D constituent constellations
creates a large peak-to-average ratio (PAR) in two-dimensions, making the
system susceptible to other impairments such as nonlinear distortion or
phase jitter.
Generalized cross-constellations, described by Forney and Wei,
"Multidimensional Constellations--Part I: Introduction, Figures of Merit,
and Generalized Cross Constellations," IEEE JSAC, pp 877-892, August,
1989, offer an alternative way of generating higher-dimensional
constellations to represent fractional bits/baud. Here, the
higher-dimensional constellation is a subset of the signal points in a
Cartesian product of identical expanded two-dimensional constellations;
simple coding rules are used to construct the subset. A generalized
cross-constellation has a low 2D constellation expansion ratio (CER) and a
low PAR in two-dimensions; however, it also generally has a low shaping
gain.
Higher-dimensional constellations with simplified bit mapping and with
significant shaping gain can be constructed using the Voronoi region of a
lattice .LAMBDA.' as the boundary of the signal point set, Forney,
"Multidimensional Constellations--Part II: Voronoi Constellations," IEEE
JSAC, pp 877-892, August, 1989. If signal points are chosen from some
lattice .LAMBDA., then .LAMBDA. and .LAMBDA.' must be scaled such that the
Voronoi region of .LAMBDA. contains 2.sup..beta.L/2 points from .LAMBDA.;
that means the order .vertline..LAMBDA./.LAMBDA.'.vertline. of the lattice
partition .LAMBDA./.LAMBDA.' must be 2.sup..beta.L/2. The mapping of bits
to signal points involves a decoding operation whose complexity is that of
a minimum-distance decoder for .LAMBDA.'. The inverse mapping is
accomplished by a simple hard-decision decoding operation. A Voronoi
constellation generally is more complex to generate than a generalized
cross constellation. For given lattices .LAMBDA. and .LAMBDA.', the
Voronoi constellation can typically support only certain fractional values
of .beta., and that by using different versions of .LAMBDA.'.
An important expansion of the Voronoi constellation technique is trellis
shaping disclosed in U.S. patent application Ser. No. 312,254, filed Feb.
16, 1989, assigned to the same assignee as this application, and
incorporated herein by reference. In trellis shaping, the signal
constellation is constructed on a sequence basis rather than on a block
basis. Instead of the Voronoi region of a lattice, the decision regions
associated with trellis codes are used to form the signal constellation
boundary. In analogy to Voronoi constellations, in trellis shaping the
mapping from bits to signal points involves a decoder for the trellis
code. Trellis shaping offers a better performance/complexity trade-off
than Voronoi constellations; but, it also can support only certain
fractional values of .beta..
An extension of Voronoi constellations and trellis shaping to non-ideal
channels with linear distortion or correlated noise has been disclosed in
U.S. Pat. No. 5,048,054, assigned to the same assignee as this invention,
and incorporated by reference. This extension, called lattice or trellis
precoding, provides the performance of ideal decision feedback
equalization (DFE), preserves the coding gain of known coded modulation
schemes designed for ideal channels, and, in addition, provides shaping
gain. Trellis precoding is similar to trellis shaping, however, it
involves a decoder for a filtered trellis code rather than for the
ordinary trellis code. Trellis precoding is a practically important
scheme, but, like trellis shaping, is limited in the fractional values of
.beta. that it can support.
SUMMARY OF THE INVENTION
The invention can support values of .beta. (bits per baud) that differ by
fractions without significantly modifying the underlying trellis codes
used in the previously disclosed trellis precoding scheme. This is
achieved by using a shaping trellis code C.sub.s which is derived from
some conventional trellis code C(.LAMBDA./.LAMBDA.',C) by using different
versions of the underlying lattices .LAMBDA. and .LAMBDA.' at different
times, in a periodic fashion. For example, if C is an N-dimensional
trellis code, to send (N/2).beta.=n+(d/2.sup.m)(N/2) bits/N-dimensions,
where 0.ltoreq.d<2.sup.m, we define a frame (period) of length
L/2=(N/2)2.sup.m bauds, and use the code C for (N/2)(2.sup.m -d) bauds,
and its scaled version RC for (N/2)d bauds.
In general, in one aspect, the invention features mapping a digital data
sequence into a signal point sequence e(D) for data transmission over a
channel h(D) to produce a channel output sequence y(D)=e(D)h(D). e(D) is
chosen so that the signal points in the sequence y(D) belong to a class of
possible sequences based on the digital data sequence, the class being
based on a time-varying trellis code derived from an N-dimensional
time-invariant trellis code by using different transformed versions of its
underlying lattices for respectively different N-dimensional symbols.
Preferred embodiments include the following features. In some embodiments,
the class comprises a signal space translate of a time-varying trellis
code C.sub.s, where the translation is a code sequence from a translate of
a trellis code C.sub.c determined based on the digital data sequence, and
the time-varying trellis code C.sub.s is derived from an N-dimensional
time-invariant trellis code C(.LAMBDA./.LAMBDA.', C.sub.s) by using
different transformed versions of its underlying lattices .LAMBDA. and
.LAMBDA.' for respectively different N-dimensional signal points.
In some embodiments, the class comprises a signal space translate of a
trellis code C.sub.s, where the translation is a code sequence from a
translate of a time-varying trellis code C.sub.c determined based on the
digital data sequence and the time-varying trellis code C.sub.c is derived
from an N-dimensional time-invariant trellis code C(L/L ', C.sub.c) by
using different transformed versions of its underlying lattices L and L'
for respectively different N-dimensional signal points.
In some embodiments, the class comprises a signal space translate of a
label translate of a time-varying trellis code C.sub.s, where the label
translate is based on a portion of the digital data sequence and the
signal space translation is based on another portion of the elements of
the digital data sequence, and the time-varying trellis code C.sub.s is
derived from an N-dimensional time-invariant trellis code
C(.LAMBDA./.LAMBDA.', C.sub.s) by using different transformed versions of
its underlying lattices .LAMBDA. and .LAMBDA.' for respectively different
N-dimensional signal points.
In some embodiments, the class comprises a signal space translate of a
label translate of a trellis code C.sub.s, where the label translate is
based on a portion of the digital data sequence, where the signal space
translation is based on another portion of the elements of the digital
data sequence and is a code sequence from a time-varying trellis code
C.sub.c which is derived from an N-dimensional time-invariant trellis code
C(L/L', C.sub.c) by using different transformed versions of its underlying
lattices L and L' for respectively different N-dimensional signal points.
In some embodiments, the class of possible sequences is identified by some
sequence of subregions into which N-space has been partitioned, the
sequence of subregions being specified by a label sequence which belongs
to a coset of a convolutional code C.sub.s and the coset is determined
based on a portion of the digital data sequence and the signal points in
the subregions belonging to a coset of a time-varying trellis code C
.sub.c, where the sequences from the trellis code C.sub.c are chosen based
on another portion of the elements of the digital data sequence, and the
time-varying trellis code C.sub.c is derived from an N-dimensional
time-invariant trellis code C(L/L', C.sub.c) by using different
transformed versions of its underlying lattices L and L' for respectively
different N-dimensional signal points.
In some embodiments, the class of possible sequences is identified by some
sequence of subregions into which N-space has been partitioned, the
sequence of subregions being specified by a label sequence which belongs
to a coset of a convolutional code C.sub.s, the signal points in the
subregions belonging to a coset of a trellis code C.sub.c, where sequences
from the trellis code C.sub.c are chosen based on another portion of the
elements of the digital data sequence and using different approximately
scaled versions of the subregions for respectively different N-dimensional
signal points.
In general, in another aspect, the invention features choosing e(D) so that
y(D) belongs to a signal space translate of a label translate of a trellis
code C.sub.s, the label translate being based on a portion of the digital
data sequence, and the signal space translation is specified based on
another portion of the elements of the digital data sequence and is a code
sequence from a trellis code C.sub.c.
In general, in another aspect, the invention features choosing x(D) so that
the signal points in the sequence y(D) belong to some sequence of
subregions into which N-space has been partitioned, the sequence of
subregions being specified by a label sequence which belongs to a coset of
a convolutional code C.sub.s, the coset being determined based on a
portion of the digital data sequence, the signal points in the subregions
belonging to a coset of a trellis code C.sub.c, and where sequences from
the trellis code C.sub.c are chosen based on another portion of the
elements of the digital data sequence.
In preferred embodiments, the versions are respectively used periodically
(e.g., two different versions used alternatingly) wherein each period
encompasses multiple N-dimensional symbols. The transformed versions
comprise rotated and/or scaled versions of the underlying lattices. The
trellis code C.sub.s is filtered to form a filtered trellis code C.sub.s '
whose sequences are c.sub.s '(D)=c.sub.s (D)g(D) where g(D) is the formal
inverse of a response related to the channel response h(D), and c.sub.s
(D) is any code sequence in the trellis code C.sub.s. The signal point
sequence selection tends to minimize the average power of the signal point
sequence e(D)=y(D)g(D). The signal point sequence e(D) lies in a
fundamental region of the filtered trellis code C.sub.s '. The signal
point sequence is selected based on reduced state sequence estimation with
respect to the filtered trellis code C.sub.s '. The reduced state sequence
estimation uses no more states than the number of states of the original
trellis code C.sub.s '. The fundamental region of the filtered trellis
code comprises approximately a Voronoi region of the filtered trellis code
C.sub. s '. The digital data sequence is recovered 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.
The signal point sequence is selected by mapping the digital data sequence
into an initial sequence belonging to and representing a congruence class
of the original trellis code C.sub.s, and choosing a signal point sequence
belonging to and representing a congruence class of the filtered trellis
code C.sub.s ' and which has no greater average power than the initial
sequence, and wherein 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 comprises a
multiplication of 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 trellis code C.sub.s may be a linear trellis code or a non-linear
trellis code. The linear trellis code C.sub.s is a 4 state Ungerboeck
code. The trellis code C.sub.s is based on a partition of binary lattices,
or a partition of ternary or quaternary lattices.
The step of selecting the signal point sequence 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. In some embodiments, N=2 or N=4. The step of
mapping the digital data sequence into the signal point sequence is
arranged 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.
Other advantages and features will become apparent from the following
description of the preferred embodiment and from the claims.
DESCRIPTION OF THE PREFERRED EMBODIMENT
We first briefly describe the drawings.
FIG. 1 is a block diagram of trellis precoding.
FIG. 2 is a framing scheme.
FIG. 3 is a block diagram of an alternatively sealed trellis code
transmitter.
FIG. 4 is a trellis diagram.
FIG. 5 is a reduced state trellis.
FIG. 6 is a diagram of the steps of a Viterbi algorithm.
FIG. 7 is a trellis for a Wei code.
FIG. 8 is a general block diagram of a transmitter and a receiver used in
precoding.
FIG. 9 is a block diagram of a transmitter.
FIG. 10 is a block diagram of a receiver.
FIG. 11 is a block diagram of binary encoding for trellis precoding.
FIG. 12 is a block diagram of a Wei binary convolutional encoder.
FIGS. 13A, 13B are diagrams of quadrants of signal sets.
FIGS. 14A, 14B are diagrams of quadrant shifting.
FIG. 15 is a diagram of portions of the trellis precoder of FIG. 9.
FIG. 16 is a block diagram of a binary syndrome former.
FIG. 17 is a block diagram of the binary portion of the trellis decoder.
FIG. 18 is a block diagram of a binary inverse syndrome former.
FIG. 19 is a block diagram of a constellation former.
FIG. 20 is a diagram of a quadrant labeling scheme.
FIG. 21 is a diagram of a phase-invariant labeling scheme.
FIG. 22 is a diagram of an encoder for trellis precoding based on
label-translates of trellis codes.
FIG. 23 is a diagram of a decoder for trellis precoding based on
label-translates.
FIG. 24 is a diagram of an encoder for trellis precoding based on regions.
FIG. 25 is a diagram of a decoder for trellis precoding based on regions.
FIG. 26 is a diagram of regions derived from a 4-way partition.
TRELLIS PRECODING
First we will summarize the principles of trellis precoding. Certain
terminology and principles which underlie the invention are set forth in
Appendix A.
Referring to FIG. 1, trellis precoding is an encoding technique based on a
discrete-time channel 40 operating at a baud rate 1/T. (If the actual
channel is continuous-time, or discrete-time operating at a higher
sampling rate, the discrete time channel at the baud rate can be
constructed by appropriate filtering, sampling or sampling-rate conversion
operations, as described in the trellis precoding patent application cited
above).
We assume the following input-output relationship for the channel:
r(D)=e(D)h(D)+n(D)
where e(D) is the channel input, h(D) is a causal, stable channel response
and n(D) is a noise sequence that can be modeled approximately as Gaussian
and white.
Let C.sub.s (.LAMBDA..sub.s /.LAMBDA..sub.s ';C.sub.s) be a time invariant
trellis code based on N-dimensional lattices .LAMBDA..sub.s and
.LAMBDA..sub.s ' and a rate-k.sub.s /(k.sub.s +r.sub.s) binary
convolutional code C.sub.s. As in the trellis shaping patent application
cited above (Assumption A), we assume that C.sub.s has the property that
all possible symbols assigned to trellis branches leaving any state
s.sub.k of the encoder belong to a coset .LAMBDA..sub.0s +a(s.sub.k) of
some lattice .LAMBDA..sub.0S, called the time-zero lattice of C.sub.s.
The following theorem, which is proven in the Appendix, plays a central
role in trellis precoding:
Theorem 1. Let R.sub.0 be any fundamental region of the N-dimensional
time-zero lattice .LAMBDA..sub.0s of C.sub.s, and let
x(D).epsilon.(R.sub.0).sup..infin. and c.sub.s (D).epsilon.C.sub.s be
unknown sequences whose sum is y(D)=x(D)+c.sub.s (D). Then x(D) and
c.sub.s (D) can be uniquely determined from y(D).
This important theorem implies that if x(D) is an information-bearing
signal that lies in the region (R.sub.0).sup..infin., then instead of
transmitting x(D), one may transmit e(D)=[x(D)+c.sub.s (D)]g(D), where
g(D)=1/h(D), and still be able to recover x(D) at the receiver, provided
that c.sub.s (D).epsilon.C.sub.s. Any desired criterion may be used to
select the code C.sub.s and the code sequence c.sub.s (D). First, we
consider strictly an average power criterion, in which case the code
C.sub.s and the code sequence c.sub.s (D) are chosen to minimize the
average power of the transmitted sequence e(D) (the mean-squared `error`).
In FIG. 1, the first step in trellis precoding is to map the incoming bit
stream 42 into the information-bearing signal x(D) using a trellis code 44
to map to words and simple mapping 46 to map from words to x(D). For
simplicity, the fundamental region R.sub.0 in N-space can be chosen as the
Cartesian product of simple two-dimensional rectangular regions.
To obtain coding gain we choose x(D) from a coset of some trellis code
C.sub.c (.LAMBDA..sub.c /.LAMBDA..sub.c ', C.sub.c). Without much loss of
generality, we assume that .LAMBDA..sub.c and .LAMBDA..sub.c ' are both
N-dimensional binary lattices and that C.sub.c is based on a binary
rate-k.sub.c /(k.sub.c +r.sub.c) convolutional encoder. It is essential
that C.sub.s be a subcode of C.sub.c, which is assured if .LAMBDA..sub.s
is a sublattice of .LAMBDA..sub.c '. This implies that if c.sub.s (D) is a
sequence from C.sub.s and x(D) is a sequence from C.sub.c, then c.sub.s
(D)+x(D) is also a sequence from C.sub.c.
To send .beta. bits per two dimensions, we will initially require that the
fundamental volume of .LAMBDA..sub.0s be 2.sup.N.beta./2+r c times larger
than the fundamental volume of .LAMBDA..sub.c, so that 2.sup.N.beta./2+r c
points from .LAMBDA..sub.c can be placed in R.sub.0 (to accommodate the
N.beta./2 information bits and r.sub.c redundant bits); i.e.,
.vertline..LAMBDA..sub.c /.LAMBDA..sub.0s .vertline.=2.sup.N.beta./2+r c.
Now, given C.sub.c and C.sub.s, we can determine the values of .beta. that
trellis precoding can support. First, we write the partition
.LAMBDA..sub.c /.LAMBDA..sub.0s more explicitly in terms of the partition
chain .LAMBDA..sub.c /.LAMBDA..sub.0c /.LAMBDA..sub.s /.LAMBDA..sub.0s. We
have
.vertline..LAMBDA..sub.c /.LAMBDA..sub.0c .vertline.=2.sup.r c
.vertline..LAMBDA..sub.0c /.LAMBDA..sub.c '.vertline.=2.sup.k c
.vertline..LAMBDA..sub.s /.LAMBDA..sub.0s .vertline.=2.sup.r s.
Furthermore, if we define .vertline..LAMBDA..sub.c '/.LAMBDA..sub.s
.vertline.=2.sup.j, where j is some integer, then it follows that
log.sub.2 .vertline..LAMBDA..sub.c /.LAMBDA..sub.0s .vertline.=r.sub.c
+k.sub.c +r.sub.s +j, and therefore since also log.sub.2
.vertline..LAMBDA..sub.c /.LAMBDA..sub.0s
.vertline.=N.beta./2+r.sub.c,N.beta./2=k.sub.c +r.sub.s +j; that means
trellis precoding can support .beta.=(2/N)(k.sub.c +r.sub.s +j) bits per
two dimensions (i.e., per baud in a QAM system).
Suppose we replace the code C.sub.s by its scaled and rotated version
RC.sub.s that is based on the partition R.LAMBDA..sub.s /R.LAMBDA..sub.s
', where R is the N-dimensional rotation operator defined in G. D. Forney,
Jr. "Coset codes--Part 1: Introduction and Geometrical Classification,"
IEEE Inform. Vol. Theory IT-34, pp. 1123-1151, Sep. 1, 1988. Then
.vertline..LAMBDA..sub.c '/R.LAMBDA..sub.s .vertline.=2.sup.j+N/2 and
hence .beta.=(2/N)(k.sub.c +r.sub.s +j)+1. This illustrates that for
binary lattices, trellis precoding can be scaled to support integer
increments in .beta., by simply replacing the code C.sub.s by its rotated,
scaled versions. A similar effect can be achieved by replacing the code
C.sub.c by its scaled and rotated version RC.sub.c.
Having discussed the scaling and the mapping of bits into the information
bearing sequence x(D), we now proceed to describe the remaining operations
in trellis precoding.
Referring again to FIG. 1, once x(D) is determined, the trellis precoder 48
tries to find a code sequence c.sub.s (D).epsilon.C.sub.s such that the
sequence
e(D)=[x(D)-c.sub.s (D)]g(D)
has as small an average power as possible. The `error sequence` e(D) is
then transmitted.
The received sequence is given by
##EQU1##
Since x(D) is chosen from a translate C.sub.c +a(D) of C.sub.c,
y(D)=x(D)-c.sub.s (D) is also a code sequence in C.sub.c +a(D). Therefore,
a conventional decoder 50 for C.sub.c can estimate y(D) with essentially
the same error probability as if x(D) were detected with an ideal DFE
which cancels the ISI due to the tail of the impulse response. If the
decoder can correctly recover y(D)=x(D)-c.sub.s (D), then it follows from
Theorem 1 that x(D) can be correctly extracted using the simple
hard-decision decoder 52 corresponding to the region
(R.sub.0).sup..infin.. In order to prevent an error in y.sub.k from
triggering error propagation, the syndrome-former methods, disclosed in
the trellis precoding patent application cited above, may be used. The
original bit stream 42 may then be recovered by inverse mapping 54.
FRACTIONAL BITS PER BAUD
As demonstrated above, using trellis codes based on binary lattices,
trellis precoding can support values of .beta., the transmitted bits/baud,
that differ by integers. In the invention, trellis precoding can also
support fractional differences in .beta. without significantly changing
the shaping code C.sub.s.
This is achieved by deriving the shaping code C.sub.s from some
time-invariant code C by using different (rotated, scaled) versions of its
underlying lattices, .LAMBDA. and .LAMBDA.', at different times in a
periodic fashion. (Again, a similar effect can be achieved by deriving the
coding code C.sub.c from some time invariant code C(L/L', C.sub.c) by
using a different rotated, scaled version of its underlying lattices L and
L'). As we saw above, if C(.LAMBDA./.LAMBDA.',C) can support k.sub.c
+r.sub.s +j bits/N-dimensions, then it can be made to support k.sub.c
+r.sub.s +j+(N/2) bits/N-dimensions, by replacing .LAMBDA. and .LAMBDA.'
by R.LAMBDA. and R.LAMBDA.', respectively. To send (N/2).beta.=k.sub.c
+r.sub.s +j+(d/2.sup.m)(N/2) bits/N-dimensions, where 0.ltoreq.d>2.sup.m,
we define a frame (period) of length L/2=(N/2)2.sup.m bauds, and use the
code C for (N/2)(2.sup.m -d) bauds, and its scaled version RC for (N/2)d
bauds.
Using RC and C at different times will create an imbalance in 2D
constellation sizes and result in a PAR that is higher than that of
trellis precoding with time-invariant trellis codes. However, using
constellation constraints, this imbalance will be substantially
eliminated.
In the preferred embodiment, we use the 4D 16-state Wei code (described in
the trellis precoding patent application) as the code for fundamental
coding gain, and we use the 2D 4-state Ungerboeck code (described in the
trellis precoding patent application) as the code for shaping gain. With
this combination N=4, k.sub.c =3, and r.sub.s =2, and we can send at rates
n+0.5 bits/baud using time-invariant scaling, where n>2 is an integer. To
transmit at 19.2 kb/s using a baud rate of 1/T=2743 symbols/s, however, we
need to send 7 bits/baud. This may be done as follows.
The 4D 16-state Wei code C.sub.c is based on a rate-3/4 convolutional
encoder and the four-dimensional partition Z.sup.4 /2Z.sup.4. This code
adds one redundant bit every four dimensions (N=4, r.sub.c =1). On the
other hand, the code C.sub.s is derived from the mod-2 trellis code C
which is based on a rate-1/2 binary convolutional encoder and the
two-dimensional partition Z.sup.2 /2Z.sup.2. Equivalently, C can be
described by a rate-2/4 convolutional encoder and the four-dimensional
partition Z.sup.4 /2Z.sup.4 (N=4, k.sub.s =2). In this form, C has the 4D
time-zero lattice RZ.sup.4. To send 6.5 bits per symbol using these codes,
we would pick C.sub.s =8C such that it is based on the partition 8Z.sup.4
/16Z.sup.4, with time-zero lattice 8RZ.sup.4. Then
.vertline..LAMBDA..sub.c /.LAMBDA..sub.0s .vertline.=.vertline.Z.sup.4
/8RZ.sup.4 .vertline.= 2.sup.14 =2.sup.2.times.6.5+1 =2.sup.2.beta.+r c.
On the other hand, to send 7.5 bits/symbol, we would pick C.sub.s =8 RC
such that it is based on the partition 8RZ.sup.4 /16RZ.sup.4, with
time-zero lattice 16Z.sup.4. Then .vertline..LAMBDA..sub.c
/.LAMBDA..sub.0s .vertline.=.vertline.Z.sup.4 /16Z.sup.4
.vertline.=2.sup.2.times.7.5+1 =2.sup.16.
Thus, referring to FIG. 2, we can send an average of 7 bits/symbol (i.e., 7
bits/baud) by using a frame of 4 bauds or L=2.times.4=8 dimensions, and by
sending 13 and 15 bits in alternate 4D blocks using respectively the
8Z.sup.4 /16Z.sup.4 and the 8RZ.sup.4 /16RZ.sup.4 based codes for shaping.
Referring to FIG. 3, the alternating of codes is achieved by including in
the transmitter a framer-blocker 60 which assembles the bits into frames
and organizes the frames into blocks 62.
Every two bauds, the coding code C.sub.c will output the two symbols
(x.sub.2k and x.sub.2k+1) and these would be processed by the precoder
which will operate on a 2D trellis representation of the trellis code
C.sub.s. Referring to FIG. 4, for the first two bauds of the frame, this
trellis corresponds to the trellis of the code 8C, whereas for the next
two bauds, it corresponds to the trellis of the code 8RC. The decoder will
search through this time-varying trellis to find a sequence c.sub.s (D).
FILTERED TRELLIS CODES
The time varying trellis code discussed in the preceding section is
subjected to a filtering process to form a filtered trellis code in the
same manner as described in the trellis precoding patent application cited
above. This is accomplished in the shaping/precoding operation 48 in FIG.
1. More specifically, we seek a c.sub.s '(D) that minimizes
.parallel.e(D).parallel..sup.2=.parallel.x'
(D)-c.sub.s'(D).parallel..sup.2, where c.sub.s '(D) (58 in FIG. 1) is any
sequence of the form c.sub.s (D)g(D), c.sub.s (D).epsilon.C.sub.s. We call
the set of all such c.sub.s '(D) the filtered trellis code C.sub.s
'=C.sub.s g. To implement trellis precoding, we need a minimum
mean-squared error (MMSE) decoder for C.sub.s.
Even if C.sub.s can be represented by a finite-state trellis, however,
C.sub.s ' in general cannot. Indeed, if s.sub.k is the state of an encoder
that generates a code sequence c.sub.s (D).epsilon.C.sub.s at time k, then
the state of the sequence c.sub.s '(D)=c.sub.s (D)g(D) at time k is
s.sub.k '=[s.sub.k ;p.sub.k ], where p.sub.k =[c.sub.s,k-1, c.sub.s,k-2, .
. . ] represents the state of the `channel` whose response is g(D). The
number of possible values of p.sub.k is not finite, even if g(D) has
finite degree, because the set of possible code symbols c.sub.s,k-i,
i=1,2, . . . , is a coset of a lattice and thus has infinitely many
elements. Therefore, in general, an MMSE decoder for C.sub.s ' cannot be
realized by a trellis search.
REDUCED-STATE DECODERS FOR FILTERED TWO-DIMENSIONAL TRELLIS CODES
We now show how to construct a class of near optimum `reduced-state`
trellis decoders for C.sub.s ', using reduced-state sequence estimation
(RSSE) principles.
In this section, we shall assume that C.sub.s is a two-dimensional trellis
code derived from a scaled, rotated version of some 2D code C which is
based on the partition .LAMBDA./.LAMBDA.'=Z.sup.2 /R.sup.k s.sup.+r
sZ.sup.2 ; these codes can be represented by trellises that have 2.sup.k s
transitions per branch where each branch is associated with a unique coset
of a scaled, rotated version of R.sup.k s.sup.+r sZ.sup.2. In what
follows, we will denote the partition used at time k as .LAMBDA..sub.s,k
/.LAMBDA.'.sub.s,k, k=1, . . . , L/2. In the next section, we will show
how the method may be extended to higher-dimensional trellis codes. It
will be apparent that two-dimensional codes are the most natural ones to
use when g(D) is a complex-valued response.
Two relevant principles of reduced-state sequence estimation are, first, to
keep track only of the last K code symbols c.sub.s,k-i,
1.ltoreq.i.ltoreq.K, even when the filter response q(D) has degree greater
than K, and second, to keep track of c.sub.s,k-i only with respect to its
membership in one of .vertline..LAMBDA..sub.s,k-i /.LAMBDA..sub.k
(i).vertline.=2.sup.j i=J.sub.i cosets .LAMBDA..sub.k (i)+a(c.sub.s,k-i)
of some lattice .LAMBDA..sub.k (i). The sequence of lattices,
.LAMBDA..sub.k (i) must satisfy the property that j.sub.i, i=1, . . . ,K,
is a non-increasing sequence so, as a code symbol c.sub.s,k-i becomes less
recent, the information that is kept about it becomes coarser and coarser,
until it is forgotten altogether (at i=K).
A code symbol c.sub.s,k-i, 1.ltoreq.i.ltoreq.K, in .LAMBDA..sub.s,k-i
belongs to one of J.sub.i cosets of .LAMBDA..sub.k (i). We denote this
coset by a(c.sub.s,k-i). Then, the `coset state` of a code sequence
c'.sub.s (D)=c.sub.s (D)g(D) at time k can be defined as t.sub.k
=[a(c.sub.s,k-l), . . . , a(c.sub.s,k-K)].
Next we concatenate coset states t.sub.k with encoder states s.sub.k to
obtain `super-states` v.sub.k :
v.sub.k =[s.sub.k ;t.sub.k ]=[s.sub.k ;a(c.sub.s,k-1), . . . ,
a(c.sub.s,k-K)].
Note that given the current state v.sub.k and the code symbol c.sub.s,k,
the next state v.sub.k+1 is uniquely determined. The uniqueness is
guaranteed by the condition that J.sub.i is a non increasing sequence.
Referring to FIG. 5, the super-states define a reduced state trellis, which
we sometimes call a super-trellis. In this trellis, signal points
associated with all branches 27 leaving a super-state 25 belong to a coset
of the time-zero lattice .LAMBDA..sub.s0,k. If .LAMBDA..sub.s,k ' is a
sublattice of .LAMBDA..sub.k (1), then as in the ordinary trellis there
are 2.sup.k s branches leaving any super-state, each associated with one
of the 2.sup.k s cosets of .LAMBDA..sub.s,k ' whose union is the given
coset of .LAMBDA..sub.s0,k. If .LAMBDA..sub.k (1) is a sublattice of
.LAMBDA..sub.s,k ', on the other hand, then there is a branch for each of
the 2.sup.j 1.sup.-r s cosets of .LAMBDA..sub.k (1) whose union is the
given coset of .LAMBDA..sub.s0,k.
The number of possible values that v.sub.k can take is finite. In fact, if
.LAMBDA..sub.k (i) is a sublattice of .LAMBDA..sub.sk '(j.sub.i
.gtoreq.k.sub.s +r.sub.s) for all i<K, and .LAMBDA..sub.k (K) is a
sublattice of .LAMBDA..sub.s0,k (j.sub.K .gtoreq.r.sub.s), then the total
number of super-states is given by
S'=S.pi..sub.1.ltoreq.i.times.K 2.sup.J i.sup.-r s.
Having described the reduced-state trellis, we now show how the Viterbi
algorithm is used to search these trellises. Let g(D)=g.sub.K
(D)+g.sub..infin. (D), where g.sub.K (D)=1+g.sub.1 D+ . . . +g.sub.K
D.sup.K is the polynomial corresponding to the first K+1 terms of g(D),
and g.sub..infin. (D) is a residual component of possibly infinite span.
Let g.sub..infin. (D)=g.sub.N (D)/g.sub.D (D), where g.sub.N (D) and
g.sub.D (D) are both finite-order polynomials. Then g.sub.N (D) has the
same delay as g.sub..infin. (D), whose delay is at least K+1.
Suppose that the input to the reduced state decoder is x'(D). Referring to
FIG. 6, let us define the Euclidean distance path metric of a code
sequence c.sub.s '(D) at a given time k as the cumulative sum
.GAMMA..sub.k =.SIGMA..sub.j.ltoreq.k .gamma..sub.j
of the branch metrics .gamma..sub.j,j.ltoreq.k, computed (31) according to
.gamma..sub.' (D)=.parallel.x'(D)--c.sub.s '(D).parallel..sup.2
=.parallel.x (D)-c.sub.s (D)g.sub.K (D)-w(D).parallel..sup.2
where w(D)=c.sub.s (D)g.sub..infin. (D), which means that w(D) satisfies
w(D)=-w(D)[g.sub.D (D)-1+c.sub.s (D)g.sub.N (D),
with w.sub.k =0, for k.ltoreq.0. Note that [g.sub.K (D)-1], g.sub.N (D),
and [1-g.sub.D (D)] all have a delay of at least 1; the Viterbi algorithm
(VA) can proceed in a recursive manner 37 by comparing metrics (33) of
merging paths and retaining 35 the surviving sequences with minimum path
metrics. Therefore, the VA needs to store the w.sub.k 's for every
surviving path. It should be noted that even though only K terms of the
filter response g(D) are taken into account in the trellis construction,
its entire memory is included in the branch metric computations.
Among these reduced-state decoders, there is one that particularly stands
out in terms of its tradeoff of performance against complexity. This is
the special case of parallel decision-feedback decoding (PDFD), where the
reduced-state trellis is simply the trellis of the original code C.sub.s.
This is obtained by setting K=0. The PDFD decoder is the simplest in this
class, and its performance is the poorest, although it often performs
close to the optimum decoder.
A practical VA has a finite decoding delay M. We can assume that it
effectively makes a decision on the kth symbol c.sub.s,k based on
observations x.sub.k, x.sub.k+1, . . . , x.sub.k+M, assuming the correct
node at time k is v.sub.k. (Under this assumption the VA will always
select a true code sequence.) For M=0, such a decoder becomes a simple
decision-feedback decoder (DFD), where in every symbol interval the
decoder performs filtering using past decisions, and operates like a
hard-decision decoder by selecting the closest signal point c.sub.k
appropriate coset of .LAMBDA..sub.s0,k using a MMSE decoder for
.LAMBDA..sub.s0,k. Clearly in this case, regardless of the channel
response, the error sequence will always lie in [R.sub.V
(.LAMBDA..sub.s0,k)].sup..infin., where R.sub.V (.LAMBDA..sub.s0,k), is
the Voronoi region of the time-zero lattice .LAMBDA..sub.s0,k, and the
average power of these regions will determine the average power of the
transmitted symbols. Since .LAMBDA..sub.s0,k may be time-varying, the size
of the signal constellation boundary may be time-varying also. This may
translate into a higher peak-to-average ratio. However, this will be
controlled by putting constraints into the decoder as will be explained
later.
The error sequence e(D)=x(D)-c.sub.s (D) will lie in some decision region
of the RSSE decoder for the filtered trellis code C.sub.s '. The average
power of this region will essentially determine the shaping gain that can
be achieved. This region, and thus the shaping gain will generally depend
on the interaction between the shaping code C.sub.s and the filter g(D),
as we have seen with MMSE decoders.
In practice, we can measure the shaping gain of an error region as follows.
We take an input sequence x'(D), which is uniformly distributed in some
simple fundamental region of C.sub.s '. We decode it and obtain an error
sequence e(D). This sequence will be uniformly distributed in the common
error region of the decoder. The output mean-squared error (MSE) gives the
shaping gain. For M=0, we get the shaping gain of the regions R.sub.v
(.LAMBDA..sub.s0,k), k=1, . . . , L/2. As M is increased towards infinity,
the error region will change and the output MSE will monotonically
decrease towards a limit which depends on the reduced-state trellis being
used.
REDUCED-STATE DECODERS FOR FILTERED MULTIDIMENSIONAL TRELLIS CODES
We now extend these reduced-state decoding methods to higher dimensional
(N>2) trellis codes C.sub.s, such as the dual Wei codes. The dual Wei
codes are duals of the Wei codes of the kind disclosed in Wei,
"Trellis-Coded Modulation with Multidimensional Constellations," IEEE
Trans. Inform. Theory, Vol. IT-33, pp. 483-501, 1987, incorporated herein
by reference. These codes are `mod 2` trellis codes, which can always be
regarded as being based upon the lattice partition .LAMBDA..sub.s
/.LAMBDA..sub.s '=Z.sup.N /2Z.sup.N, and on some rate k/N binary
convolutional code C that selects cosets of 2Z.sup.N in Z.sup.N. These
cosets can be specified by N/2 cosets of 2Z.sup.2 in Z.sup.2.
It follows that the N-dimensional trellis code can be represented by a
two-dimensional trellis, which is periodically time-varying with period
N/2. At times nN/2, the trellis has S states and 2.sup.m branches per
state as in the original N-dimensional trellis, whereas at intermediate
times (kN/2)+j, j=1, 2, . . . , (N/2-1), the number of states may be
larger, where the exact number of states depends on the specific code in
use.
As an example, consider the 4D 8-state dual Wei code, which can be viewed
as a period-2, time-varying trellis code based on the partition Z.sup.4
/2Z.sup.4 and a rate-1/4 convolutional encoder. This trellis is
illustrated in FIG. 7. Note that there are 8 states at even times, with 2
distinct branches leaving each state, and there are 16 states at odd
times, with one branch leaving each state.
Once a two-dimensional trellis is obtained, reduced state decoders can be
defined as in the previous section. The operation of the VA is then
similar, except it has to account for the additional time-varying nature
of the trellis.
CONSTRUCTION OF THE DISCRETE-TIME CHANNEL MODEL
So far, we have assumed a canonical discrete-time channel model described
by
r(D)=e(D)h(D)+n(D)
where e(D) is a complex input sequence, h(D) is a complex, stable, causal
response with h.sub.0 =1 and n(D) is a white Gaussian noise component
which is independent of e(D). For best results we will choose h(D) to be
minimum phase. In practice, the physical channel will rarely obey this
canonical model; the channel response is often nonminimum-phase, the noise
can be correlated and, furthermore, the physical channel is often
continuous-time. Therefore, referring to FIG. 8, in practice, the physical
channel 201 is often augmented by linear transmitter and receiver filters
202,204 in the transmitter and in the receiver, respectively, to construct
a discrete time channel 205 that obeys the canonical model.
In addition to providing the canonical discrete-time channel, it is
desirable that these filters also help optimize the performance of the
trellis precoder. It has been shown in the case of Tomlinson precoding
that the optimum transmitter filter has a brickwall (or flat) spectrum
within the Nyquist band (for continuous-time channels this result holds
under certain mild conditions (Price, "Nonlinearly Feedback Equalized PAM
versus Capacity for Noisy Filtered Channels," Proc. ICC-72, June, 1972,
supra)); the optimum receiver filter, on the other hand, consists of a
matched filter sampled at the baud rate (and at the optimum sampling
phase), followed by a discrete time noise whitening filter that produces a
minimum-phase combined response h(D) (Price, supra). This noise-whitening
filter can be described by the cascade of a zero-forcing linear equalizer
and a minimum-phase linear prediction (error) filter for the residual
noise sequence appearing at the output of the linear equalizer. The
prediction filter represents the channel model h(D).
In practice, it may sometimes be preferable to allow the overall
discrete-time channel to deviate from the canonical model to arrive at a
better trade-off between ISI and noise. For example, the selection of the
filter may be based on the output MSE. Of course, due to the presence of
ISI, minimum MSE does not guarantee minimum error probability.
Nevertheless, this criterion is often used in practice because of ease in
adaptive implementation, and because it is believed that often (if not
always) it leads to lower error probability, particularly at low SNR.
Under the MSE criterion, the optimum transmitter spectrum is different; it
has the `water-pouring characteristic` found in information theory (J.
Salz, "Optimum mean-squared error decision feedback equalization," BSTJ,
vol. 52, pp. 1341-1373, 1973). For the moderate or high SNR's found on
telephone lines, however, a `water-pouring spectrum` can be closely
approximated by a brickwall spectrum. The minimum MSE receiver filter also
consists of a matched filter sampled at the baud rate and a discrete-time
filter that produces a white residual error sequence. The whitening filter
can now be represented by the cascade of a MSE linear equalizer and a
prediction error filter for the error sequence (ISI+noise) that appears at
the output of that equalizer.
Under the MSE criterion, the received sequence can be written as
r(D)=e(D)h(D)+n'(D), where the error sequence n'(D) is now
signal-dependent and possibly non-Gaussian; the trellis precoder can still
operate in the same manner. Here, it may be helpful to note that with an
optimum transmitter filter, the overall response h(D) is independent of
the SNR (in fact, it is the same filter that we obtain under the no ISI
criterion.)
In practice, the combination of the matched filter and the MSE linear
equalizer can be implemented as a digital transversal equalizer with a
fractional tap-spacing of T/M, where T is the baud interval and M is
chosen sufficiently large to avoid aliasing. Since the characteristics of
the physical channel is often unknown, an adaptive training algorithm is
needed to learn this equalizer. This can be accomplished by transmitting a
known training sequence such as a pseudo-noise (PN) sequence modulating a
QPSK signal structure prior to data transmission, and then using a
least-mean square (LMS) algorithm (J. Proakis, "Digital Communications,"
McGraw-Hill, 1983). Once the equalizer is learned, an adaptive minimum MSE
linear predictor can be realized. This predictor has a tap-spacing of T
and it whitens the residual error sequence. Its steady state coefficients
form the desired channel response h(D) of the model. So far, we have
implicitly assumed that all filters are infinitely long. Of course, in
practice, the linear equalizer and the predictor are implemented with
finite length filters; nevertheless, when these are sufficiently long the
general discussion presented above will approximately apply.
After a sufficiently long training period, the information about h(D) is
passed back to the transmitter for use during trellis precoding. During
data transmission an adaptive algorithm may continue to adjust the
coefficients of the linear equalizer to track small variations in the
channel response. However, the prediction filter is kept fixed. It is
conceivable to update the predictor as well, provided that this
information can be relayed back to the transmitter using a `service
channel` and proper synchronization between the transmitter and the
receiver can be maintained. Alternatively, the receiver may monitor the
true current values of the prediction filter coefficients and may request
a new training signal if the discrepancy becomes excessive.
MODEM IMPLEMENTATION
One application of trellis precoding is to a voiceband modem operating at a
baud rate of 2743 symbol/s and a bit rate of 19.2 kb/s, thus sending 7
bits/baud. The transmitter and the receiver are implemented mostly in
digital form.
The transmitter 102 and the receiver 104 of such a modem are shown
respectively in Figs. 9, 10. Based on the optimality discussion above, the
transmitter filter 106 is chosen to have a square-root-of-raised-cosine
characteristics with a small excess bandwidth (.ltoreq.12%), thus
approximating a brickwall spectrum. During training, a known pseudo-random
four-point QAM sequence 107 .times.(D) is transmitted via train/data
switch 105 for a sufficiently long period of time to allow the receiver to
learn first its adaptive equalizer 108 and subsequently its adaptive
prediction filter 110. The complex output of the transmitter filter is
modulated to a carrier frequency w.sub.c (radians/s) and the real part of
the modulated signal is D/A converted, filtered by an analog filter, and
transmitted over the channel, all by unit 107. In the receiver 104, the
received signal is filtered by an analog filter 109 and then A/D converted
at a sufficiently high nominal sampling rate M/T (the sampling phase is
controlled by a timing recovery circuitry). The sequence of digital
samples z.sub.n is fed into an equalizer delay line 108 with a tap spacing
of T/M, where n is the sampling index.
To describe the operation of the adaptive receiver, we denote the complex
coefficients of the linear equalizer as c.sub.n, -N.sub.1
.ltoreq.n.ltoreq.N.sub.2 (N.sub.1 +N.sub.2 +1 taps). The output of the
equalizer is computed once every baud; then, it is demodulated to obtain
the sequence r.sub.k '. We assume that all coefficients are initially set
to zero. The initial values may also be determined using a fast
initialization method such as the scheme described in (Chevillat et al.,
"Rapid Training of a Voice-band Data Modem Receiver Employing an Equalizer
with Fractional T spaced Coefficients, IEEE Trans. Commun., vol. COM-35,
pp. 869-876, Sept. 1987). In any case, the coefficients of the linear
equalizer are adjusted according to c.sub.n,k+1
=c.sub.n,k.sup.-.alpha..epsilon..sub.k z.sub.n *, n=-N.sub.1, . . . , O, .
. . ,N.sub.2 where .epsilon..sub.k =r.sub.k '-x.sub.k is the error between
the equalizer output r.sub.k ' and the known transmitted symbol x.sub.k,
and k is the index for the baud interval. If the step size .alpha. is
sufficiently small, then the coefficients will converge to values which
minimize the MSE. Furthermore, if N.sub.1 and N.sub.2 are sufficiently
large, the filter converges to the optimum MSE linear equalizer that we
described earlier.
Once the equalizer has converged, its outputs r.sub.k ' are fed into a
T-spaced prediction (error) filter with coefficients h.sub.0 =1 (fixed),
h.sub.1, and h.sub.2. This filter produces r(D), the output of the channel
model. Its coefficients are updated according to
h.sub.i, k+1 =h.sub.i,k -.beta..epsilon.*.sub.k-i .epsilon.'hd k, i=1,2
where .epsilon.'.sub.k =r.sub.k -x.sub.k -x.sub.k-1 h.sub.1,k -x.sub.k-2
h.sub.2,k is the final error after prediction and .beta. is another small
step size. Again, when .beta. is sufficiently small, these coefficients
will converge to their values which minimize the MSE. If the overall
channel model can be represented by a three coefficient model as we
assumed here, we expect the residual error sequence to be approximately
white, as explained earlier.
After convergence, the coefficients h.sub.1 and h.sub.2 are sent back to
the transmitter for use during trellis precoding. This can be
accomplished, for example, by simply encoding the coefficients into binary
words and transmitting these using 4-QAM signaling. These words are
typically sent in a small frame which has a flag for recognizing the start
of the frame and an error control check to detect transmission errors. In
what follows, we denote the estimated channel response by h(D), and its
formal inverse by g(D).
During transmission of actual data from a data terminal equipment (DTE)
120, the prediction filter 110 is kept fixed, but the linear equalizer 108
is continually adapted in a decision-directed mode to track small channel
variations. (It is also possible to update the prediction filter along
with the precoder coefficients. The latter would be updated using a side
channel.) Because of trellis precoding, it is not possible to generate the
error signal .epsilon..sub.k directly at the equalizer output, since
decisions are available at the output of the prediction filter 110 h(D).
Therefore, to reconstruct the equalizer error, the final prediction error
e'.sub.k =r.sub.k -Y.sub.k ' between the output r.sub.k of the prediction
error filter and the estimated channel symbol Y.sub.k ' is passed through
g(D) 122. The estimates Y.sub.k ' can be obtained with no delay using a
simple slicing operation, or they can be obtained from the Viterbi
decoder, albeit after some delay. Experiments indicate that this structure
operates reliably even in the presence of decision errors.
Referring again to FIG. 9, in the trellis precoder 124 we use a
four-dimensional 16-state Wei code for coding (denoted as C.sub.c) and a
two-dimensional 4-state Ungerboeck code for shaping (denoted as C.sub.s).
and we send 7 bits per two dimensions (or baud). The code C.sub.s is
derived from trellis code C which is based on a rate-1/2 4-state binary
convolutional encoder and the two dimensional partition Z.sup.2 /2Z.sup.2.
Equivalently, C can be described by a rate-2/4 convolutional encoder and
the four-dimensional partition Z.sup.4 /2Z.sup.4. We use a four baud frame
to define C.sub.s, where in the first two bauds C.sub.s =8C and the next
two bauds C.sub.s =8RC, as described earlier. Thus, the time zero lattice
is 8RZ.sup.4 during the first two bauds and 16Z.sup.4 during the next two
bauds of the frame. The code C.sub.c, on the other hand, is based on a
rate-3/4 binary convolutional encoder and the 4 D partition Z.sup.4
/2Z.sup.4. This code adds one redundant bit every four dimensions (or
equivalently, every two bauds). Note that a fundamental region of the time
zero lattice 8RZ.sup.4 will contain exactly 2.sup.2.times.6.5+1 =2.sup.14
points from any coset of the lattice Z.sup.4 ; i.e., .vertline.Z.sup.4
/8RZ.sup.4 .vertline.=2.sup.14, and a fundamental region of the time zero
lattice 16Z.sup.4 will contain 2.sup.2.times.7.5+1 =2.sup.16 points from
any coset of Z.sup.4.
A small buffer 130 is filled with bits received from the DTE at the rate of
7 bits per (2D) signaling interval. Referring also to FIG. 2, during the
two bauds, 4j and 4j+1 [the two bauds 4j+2, 4j+3] a scrambler 132 takes 7
[8] and then 6[7] bits from this buffer, respectively. The scrambled bits
are delivered to a binary encoder in groups of 13 [15] so-called I bits,
labeled I6(4j) through I0(4j) and I5(4j+1) through I0(4j+1) [I7 (4j+2)
through I0(4j+2) and I6(4j+3) through I0(4j+3)], at two successive times
4j and 4j+1[4j+2 and 4j+3].
Referring to FIG. 11, the I-bits I2(4j)I1(4j) [I2(4j+2) I1(4j+2)] are taken
to represent an integer mod 4 and are differentially encoded by a coding
differential encoder 150 to produce two differentially encoded bits
ID2(4j)ID1(4j) ID2(4j+2)ID1(4j+2)] according to the relation
ID2(4j)ID1(4j) I1(4j)Z1(4j) .sub.4 .sym.ID2(4j-2)ID1(4j-2)
[ID2(4j+2)ID1(4j+2)=I2(4j+2)I1(4j+2).sym..sub.4 ID2(4j)ID1(4j)]
where .sym..sub.4 represents mod-4 addition.
The bits ID1(4j) and I0(4j) [ID1(4j+2) and I0(4j+2)] enter a rate 2/3, 16
state binary convolutional encoder 152, which produces one redundant bit
Y0(4j) [Y0(4j+2)]. Referring to FIG. 12, this encoder includes a
sequential circuit 246 having four delay-2 shift registers 248 and three
mod-2 adders 250. (This encoder can also be realized using other
circuits.)
Referring again to FIG. 11, the bits ID2(4j)ID1(4j) I0(4j)
[ID2(4j+2)ID1(4j+2)I0(4j+2)]and the redundant bit Y0(4j) [Y0(4j+2)] enter
a bit converter 154 that generates four output bits
Z1(4j)Z0(4j)Z1(4j+1)Z0(4j+1) [Z1(4j+2)Z0(4j+2)Z1(4j+3)Z0(4j+3)] according
to the following table. Note that the corresponding bracketed headings for
the table are [ID2(4j+2)
ID1(4j+2)I0(4j+2)Y0(4j+2)Z1(4j+3)Z0(4j+3)Z1(4j+2)Z0(4j+2)]:
__________________________________________________________________________
ID2(4j)
ID1(4j)
I0(4j)
Y0(4j)
Z1(4j+1)
Z0(4j+1)
Z1(4j)
Z0(4j)
__________________________________________________________________________
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 1 0 0 1 0 0
0 0 1 1 1 1 0 0
0 1 0 0 1 0 1 0
0 1 0 1 0 1 1 0
0 1 1 0 1 1 1 0
0 1 1 1 0 0 1 0
1 0 0 0 0 1 0 1
1 0 0 1 1 1 0 1
1 0 1 0 0 0 0 1
1 0 1 1 1 0 0 1
1 1 0 0 1 1 1 1
1 1 0 1 0 0 1 1
1 1 1 0 1 0 1 1
1 1 1 1 0 1 1 1
__________________________________________________________________________
These output bits are used to select one of 16 cosets of 2Z.sup.4 whose
union is the four-dimensional grid Z.sup.4 +(0.5, 0.5, 0.5, 0.5). Each
such coset is represented by a pair of cosets of 2Z.sup.2 in the
two-dimensional grid Z.sup.2 +(0.5, 0.5). These are selected individually
by Z1(4j)Z0(4j) and Z1(4j+1)Z0(4j+1)[Z1(4j+2)Z0(4j+2) and
Z1(4j+3)Z0(4j+3)].
The remaining I-bits I3(4j) through I6(4j) [I3(4j+2) through 17(4j+2)] pass
through unchanged and are relabeled as Z2(4j) through Z5(4j) [Z2(4j+2)
through Z6(4j+2)]. They are combined with Z1(4j)Z0(4j) [Z1(4j+2)Z0(4j+2)]
to form the six-tuple Z5(4j)Z4(4j) . . . Z0(4j) [seven-tuple
Z6(4j+2)Z5(4j+2)...Z0(4j+2)]. Similarly, the I bits I2(4j+1) through
I5(2j+1) [I2(4j+3) through I6(4j+3)] together with Z1(4j+1)Z0(4 j+1)
[Z1(4j+3)Z0(4j+3)] form the six-tuple Z5(4j+1)Z4(4j+1) . . . Z0(4j+1)
[seven-tuple Z6(4j+3)Z5(4j+3) . . . Z0(4j+3)].
The I-bits I1(4j+1)I0(4j+1) [I1(4j+3)I0(4j+3)]sequentially enter a rate-1/2
inverse syndrome former (H.sup.-1).sup.T 156. H is a syndrome former of
the binary code C defined above. Referring to FIG. 14, (H.sup.-).sup.T
produces two pairs of S bits S1(4j)S0(4j) [S1(4j+2)S0(4j+2)]and
S1(4j+1)S0(4j+1) [ S1(4j+3)S0(4j+3)]. As discussed earlier and disclosed
in Forney and Eyuboglu, Trellis Shaping for Modulation Systems, United
States Patent Application cited above, (H.sup.-1).sup.T is the left
inverse of (H).sup.T discussed below, and is included to limit error
propagation.
Referring to FIGS. 13A, 13B during the two bauds 4j and 3j+1 [4j+2 and
4j+3], the 16bits [18-bits] generated in this manner are mapped into two
initial signal points r(4j) and r(4j+1) [r(4j+2) and r(4j+3)]chosen from a
256-point [512-point] two dimensional square signal set which lies on the
grid Z.sup.2 +(0.5, 0.5). First, the six tuple [seven-tuple] Z-bits are
used to select a signal point from the 64-point [128-point] region-0
signal set 261. This signal set is divided into four subsets which are
cosets of 2Z.sup.2 (indicated by different shadings in FIGS. 13A and 13B).
The signal points are labeled such that Z1 and Z0together select one of
the cosets according to the labeling shown in the lower left corner of
FIG. 13A. The labeling of the remaining bits Z5,Z4,Z3,Z2 is shown only for
coset a. For other cosets, the labeling can be obtained by the rule that
90 degree rotation of a point around the center (4,4) [8,0] of the
region-0 signal points result in the same labeling.
The Wei encoder 152 (FIG. 15) insures that the minimum distance between
allowable sequences of region 0 points is kept large.
The S-bits S1,S0 determine the final region of the initial point according
to the rule:
______________________________________
S1S0 Region
______________________________________
00 0
01 1
10 2
11 3
______________________________________
Referring to FIGS. 14A, 14B, the signal points in region-0 are moved to the
region chosen by the S-bits in such a way that they remain in the same
coset of 8Z.sup.2 [8RZ.sup.2 ]. This is done by offsetting the region-0
point by (0,0), (0,-8), (-8, -8), or (-8,0) [(0,0), (-8,-8), (-16,0), or
(+8,-8)]. It follows that the translated final point is in the same coset
of Z.sup.2 as the region-0 point. Therefore, the minimum distance between
allowable sequences remains unchanged. The signal points obtained in this
manner form the initial sequence x(D). Thus the S-bits can be viewed as a
coset representative sequence which determines the coset of 16Z.sup.2 in
8Z.sup.2 [16RZ.sup.2 in 8RZ.sup.2 ] for the elements of initial sequence
x(D).
Referring to FIG. 15, the initial sequence x(D) is transformed into the
transmitted sequence e(D) using parallel decision feedback decoding (PDFD)
294 (which, along with the circuitry of FIG. 3, is part of the trellis
precoder 124 of FIG. 9). It is possible to replace PDFD by a more powerful
RSSE decoder, or by some other reduced complexity decoder for the filtered
trellis code C.sub.s '.
As we saw earlier, the optimum decoder selects from the shaping code
C.sub.s the code sequence c.sub.s (D) which minimizes the mean-squared
error between the sequences x'(D)=x(D)g(D) and c.sub.s '(D)=c.sub.s
(D)g(D). The transmitted sequence is the error sequence e(D)=x'(D)-c.sub.s
'(D). The code sequence selected by PDFD will not generally result in
minimum MSE, however, experiments indicate that the excess MSE will often
be small. For example, for a channel with two coefficents, PDFD can
achieve 0.5-0.85 dB shaping gain, depending on the values of h.sub.1 and
h.sub.2.
Now, we consider the operation of PDFD in some detail. First, we describe
the shaping code C.sub.s.
Referring again to FIGS. 14A and 14B, the two-dimensional symbols of this
code are chosen from the integer lattice 8Z.sup.2 [8RZ.sup.2 ]299. These
symbols are partitioned into four subsets which correspond to the (four)
cosets of 16Z.sup.2 in 8Z.sup.2 [16RZ.sup.2 and 8RZ.sup.2 ] and are
labeled as A, B, C and D as shown in the lower-left corner of FIG. 14A.
All possible sequences c.sub.s (D) in the shaping code C.sub.s are
represented by the trellis diagram of FIG. 4. Here, from any state there
are two branches 302, each branch representing a two dimensional subset.
For example, state 0 has two branches labeled A and B.
PDFD operates recursively using the Viterbi algorithm and in synchronism
with the four-dimensional Wei encoder such that ever other baud it
releases two delayed error symbols e(4j-M) and e(4j+1-M) [e(4j+2-M) and
e(4j+3-M)], where M (an even number) is the decoding delay measured in
number of bauds. Every baud interval, the VA has in storage four path
metrics .lambda..sub.i (4j+l)[.lambda..sub.i (4j+l+2)], i=0,1,2,3, and
l=0,1, one for each state in the trellis diagram. The VA also has in
storage a finite history of previously hypothesized error symbols e.sub.i
(4j+l-m) [e.sub.i (4j+2+l-m)], i=0,1,2,3, l=0,1 and m=1,2, . . . ,M, one
for each state. In each iteration (every baud), the paths are extended by
incrementing path metrics by the branch metrics; the branch metric for the
path branch p(p=1,2) from the i 'th state is described by
b.sub.i,p (4j+l)=.vertline.e.sub.i (4j+l-1) h.sub.1 -e.sub.i (4j+l-2)
h.sub.2 +x(4j+l)-c.sub.i,p (4j+l).vertline..sup.2
[b.sub.i,p (4 j+l+2)=.vertline.-e.sub.i (4j+l+1) h.sub.i -e.sub.i
(4j+l)h.sub.2 +x(4j+l+2)-c.sub.i,p (4j+l+2).vertline..sup.2 ]
where c.sub.i,p (4j+l) [c.sub.i,p (4j+l+2)] is a symbol from the coset of
16Z.sup.2 [16RZ.sup.2 ] associated with this branch that gives the minimum
value for the branch metric. For each state i' after the transition, the
accumulated metric of the two merging paths are compared and the path with
the smaller metric is declared a survivor; its path metric becomes the new
path metric for state i and the error symbol for the surviving transition
(i*,p*), which is given by
e.sub.i' (4j+l)=-e.sub.i* (4j+l-1)h.sub.1 -e.sub.i* (4j+l-2) h.sub.2
+x(4j+l)-c.sub.i*,p* (4j+l), [e.sub.i' (4j+l+2)=-e.sub.i* (4j+l1)h.sub.1
-e.sub.i* (4j+l) h.sub.2 +i x(4j+l+2)-c.sub.i*,p* (4j+l+2)]
becomes its most recent error symbol stored in its path history for
subsequent use. Every other baud, or when l=1, the algorithm determines
the state with the minimum path metric, traces back its error symbol
history for M symbols, and releases the error symbols for times 4j-M and
4j-M+1[4j-M+2 and 4j-M+3] as outputs.
Note that the error symbols generated by the precoder 124 lie inside the
Voronoi region of the sublattice 16Z.sup.2, [16RZ.sup.2 ] which is a
square of side 16 [a rotated square of side 16.sqroot.2], centered at the
origin, independent of the channel response h(D). When h.sub.1 and h.sub.2
are both non-integers and h(D) is FIR, then the error symbols can take
infinitely many values within that square.
In trellis precoding using trellis codes that are based on partitions of
binary lattices, the elements e.sub.j of the transmitted sequence belong
to a 2D constellation that lies within a square boundary. Furthermore,
trellis precoding expands the size of the 2D constellation. Moreover, all
these effects, and in addition, the further imbalance in the sizes of 15
the Voronoi regions of the time zero lattices .LAMBDA..sub.s0,k, increase
the peak-to average ratio of the transmitted symbols, which may be
undesirable. It is possible to reduce the PAR and obtain a more circular
boundary by applying constraints to PDFD (FIG. 7). For example, PDFD can
be constrained in such a way that it only selects code sequences c.sub.s
'(D) (from the filtered code C.sub.s ') which result in transmitted
sequences e(D) whose elements e.sub.j have magnitudes no greater than some
predetermined radius R.sub.c ; i.e., .vertline.e.sub.j
.vertline..ltoreq.R.sub.c. When R.sub.c is not too small, the decoder can
proceed without violating the constraint.
This type of constraint can be incorporated into any RSSE type decoder very
easily by deemphasizing those branches of the trellis whose mean squared
error (MSE) metrics exceed R.sub.c.sup.2, by multiplying them with an
appropriately chosen number Q. The larger Q gets, the harder the
constraint becomes. This reduces the probability of choosing points lying
outside the constraint circle. When Q is sufficiently large, and R.sub.c
is not very small, points outside the constraint circle will never be
selected. Note that if R.sub.c is too small, circle one should not
disallow branches, because this may force the decoder to choose an illegal
sequence as a code sequence, and then the initial sequence x(D) cannot be
correctly recovered in the receiver.
When the transmitted sequence e(D) is filtered before transmission over the
channel, it may be beneficial to apply the constraint in higher dimensions
(on groups of successive elements of the sequence e(D)), in order to
minimize the PAR after the filtering. For example, the constraint may be
applied in four dimensions by comparing the sum of the two most recent
branch metrics against some squared radius R.sub.c.sup.2. The decoder
could force the condition .vertline.e.sub.2j .vertline..sup.2
+.vertline.e.sub.2j+1 .vertline..sup.2 <R.sub.c ', R.sub.c ' being the
radius of a 4D square. This constraint may be applied blockwise or
sequentially in a sliding window fashion.
The VA is further slightly modified to insure that the code sequence
c.sub.s ' (D) it selects is an allowable sequence from C.sub.s ', since
otherwise the initial sequence x(D) cannot be correctly recovered.
Whenever the VA traces back the path history to make a decision, it traces
back other paths as well to determine whether they end in the same state;
when they don't, those paths are pruned by setting their current path
metric to a very large value. This insures that only allowable code
sequences are selected.
The precoded sequence e(D) is passed through the transmitter shaping filter
106 (FIG. 10), D/A converted, filtered by the analog front end 107 and
subsequently transmitted over the channel.
At the receiver, the received signal r(t) is first filtered by the analog
filter 109 (FIG. 10) to remove out-of-band noise, and A/D converted into a
digital stream (z.sub.n) at a rate of M/T. This digital stream is input
into the adaptive linear equalizer 108 with N.sub.1 +N.sub.2 +1 taps and a
tap-spacing of T/M (not to be confused with the case of M for delay
elsewhere). The output of this filter is sampled at the baud rate 1/T,
then demodulated and subsequently filtered by the prediction filter h(D)
110 to approximately produce the received sequence
r(D)=e(D)h(D)+n'(D)=x(D)-c.sub.s (D)+n'(D)=y(D)+n'(D)
As we discussed earlier the elements of y(D) lie in the same coset of
2Z.sup.4 in Z.sup.2 as x(D), and thus the same coset of 2Z.sup.2 in
Z.sup.2. Therefore, the minimum distance between possible sequences y(D)
is no smaller than the minimum distance between possible input sequences
x(D) and the sequence y(D) can be decoded with a Viterbi decoder 133 for
x(D), except the decoder must be slightly modified to take into account
the potentially different signal set boundaries for the elements y.sub.j
of y(D).
It can be shown that the shape and size of the signal set boundary for
y.sub.j 's depend on the channel coefficients h.sub.1 and h.sub.2. For
example, if h.sub.1 and h.sub.2 are both real, then the boundary will be a
square of side length 2(1+h.sub.1 +h.sub.2), again centered at the origin.
If the output constellation size is of concern, it may be beneficial to
limit the magnitudes of the coefficients during training. This may be
accomplished using a constrained adaptation algorithm.
It is possible to make the decoder 133 transparent to the constellation
expansion that is caused by the channel filter. If we take the received
sequence y(D) and translate it by some sequence a(D), where the elements
of a(D) are elements of the lattice 16Z.sup.2 [16RZ.sup.2 ], then the
modified sequence y(D)-a(D)=x(D)-c.sub.s (D)-a(D) is still equal to x(D)
mod C.sub.s, since the component c.sub.s (D)+a(D) is an allowable code
sequence. It follows that the received sequence can be translated inside
the Voronoi region of 16Z.sup.2 [16RZ.sup.2 ]. The Viterbi algorithm for
the (coding) code C.sub.c can now operate on this translated sequence
assuming a square boundary of side 16 during the first two bauds of a
frame and a rotated square of boundary of side 16 .sqroot.2 during the
next two bauds of the frame and output a delayed estimated sequence y"(D).
Every other baud, the VA will produce two delayed decisions y"(4j) and
y"(4j+1) [y"(4j+2) and y"(4j+3)]. To extract the I-bits from these, we
first obtain the Z bits by translating the decisions into region 0, in
such a way that the 2D elements remain in the same coset of 8Z.sup.2
[8RZ.sup.2 ]. Then, the Z bits can be extracted using an inverse mapping
according to FIGS. 15A and 15B.
To extract the S-bits, we first label the regions (as before) according to
______________________________________
Region
SQ1SQ2
______________________________________
0 00
1 01
3 11
2 10
______________________________________
Then, the regions of y"(4j) and y"(4j+1) determine the labels
SQ1(4j)SQ0(4j) [SQ1(4j+2)SQ0(4j+2)]and
SQ1(4j+1)SQ0(4j+1)[SQ1(4j+3)SQ0(4j+3)]. It is easy to show that
SQ1(i)SQ0(i)=S1(i)S0(i).sym..sub.2 B1(i)B0(i), where i=4j or 4j+1[4j+2or
4j+3], .sym..sub.2 represents exclusive-or operation and B1(i)B0(i) is a
binary two-tuple represeting the coset (A=00, B=11, C=01 and D=10) of
16Z.sup.2 [16RZ.sup.2 ] for the code symbol c.sub.s (i) chosen during
precoding by PDFD.
Referring to Figs. 16 and 17, the labels SQ1(i)SQ0(i) are then sequentially
passed through a feedback-free syndrome former H.sup.T 256. The
syndrome-former has the property that any allowable sequence of coset
labels B1(i)B0(i) will produce an all-zero sequence at its output.
Furthermore, (H.sup.-1).sup.T H.sup.T =I, the identity matrix. Therefore,
a sequence which first passes through (H.sup.-1).sup.T and then through
H.sup.T will remain unchanged. Thus, as shown in FIG. 17, at the output of
the syndrome-former we obtain the transmitted bits I1'(4j+1)I0'(4j+1)
[I1(4j+3) I0'(4j+3)], as long as the estimates y"(i) are correct. When
there are occasional errors, they do not create catastrophic error
propagation, because H.sup.T is feedback free.
Referring again to FIG. 17, the remaining information bits can be recovered
by an inverse bit converter 286 and a coding differential decoder 288
which operates according to the relation:
I2'(4j)I1'(b 4j)=ID2'(4j)ID1'(4j).theta..sub.4 ID2'(4j-2)ID1'(b 4j-2)
[I2'(4j+2)I1'(4j+2)=ID2'(4j+2)ID1'(b 4j+2).theta..sub.4 ID2'(4j)ID1'(4j)]
where .theta..sub.4 is a modulo-4 subtraction. Referring again to FIG. 11
the I bits are then descrambled in a descrambler which forms part of unit
133 and delivered to the DTE via a buffer 135.
DIFFERENTIAL CODING FOR SHAPING
Suppose the channel introduces a phase rotation of 90k degrees, k=1, 2, or
3. The translation of the error point into regiont-1 is then rotated
around the point (4,4,) [8,0] by the same amount. Since the Wei code is
transparent to 90k degree phase rotations, the mapping used in the
transmitter guarantees that the Z bits can be correctly recovered.
Unfortunately, this is not true for the region labels SQ1SQ0.
To remedy this situation, the label sequence SQ1SQ0 can be generated
according to the phase-invariant labeling shown in FIG. 18. In order to
guarantee that the relationship SQ1SQ0=S1S0.sym..sub.2 B1B0 still holds, a
differential encoding operation is necessary. This is done as follows:
Referring to FIG. 19, for each signal point obtained through region-0
mapping 258, we extract its subregion label SQ1SQ0 with a subregion
extractor 306 according to FIG. 20. A shaping differential encoding 308
and a map into offsets 310 use the bits SQ1SQ0 and S1S0 to offset the
region --0 point into two new points x0(i) and x1(i), where i=4j [4j+2] or
i=4j+1 [4j+3] such that they remain in the same coset of Z.sup.2. This
mapping can be described by the following two tables:
______________________________________
SQ0 SQ1 S0 S1 D00 D01 D10 D11
______________________________________
0 0 0 0 0 0 1 1
0 0 0 1 1 0 0 1
0 0 1 0 0 1 1 0
0 0 1 1 1 1 0 0
0 1 0 0 0 1 0 1
0 1 0 1 0 0 0 0
0 1 1 0 1 1 1 1
0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 0
1 0 0 1 1 1 1 1
1 0 1 0 0 0 0 0
1 0 1 1 0 1 0 1
1 1 0 0 1 1 1 1
1 1 0 1 0 1 1 1
1 1 1 0 1 0 1 1
1 1 1 1 0 0 1 1
______________________________________
Di0 Di1 .DELTA. i (offset)
______________________________________
0 0 0.0+j0.0 [0.0-j0.0]
0 1 0.0-j8.0 [-8.0-j8.0]
1 0 -8.0+j0.0 [8.0-j8.0]
1 1 -8.0-j8.0 [-16.0-j8.0]
______________________________________
In the PDFD decoder, the point x0(i) is used for branches corresponding to
cosets A and B, whereas xl(i) is used for branches corresponding to cosets
C and D. It can be shown that if SQ1SQ0 is the subregion label of the
received point, then SQ1SQ0=S1S0.sym..sub.2 B1B0. Therefore, by passing
the subregion label (which is rotationally invariant) through the
syndrome-former H.sup.T we can recover the bits I0(4j+1) and I1(4j+1)
[I0(4j+3) and I1(4j+3)]even in the presence of 90k degrees phase offset.
HEXAGONAL 2D CONSTELLATIONS
If we choose the underlying shaping trellis code C(.LAMBDA./.LAMBDA.';C) as
a code based on a partition .LAMBDA./.LAMBDA.' of so-called ternary or
quaternary lattices whose constituent 2D lattice and sublattice
.LAMBDA..sub.2 and .LAMBDA..sub.2 ' are versions of the hexagonal 2D
lattice .LAMBDA..sub.2, then the elements e.sub.j of the transmitted
sequence will be bounded within a region R.sub.v (.LAMBDA..sub.2 ') which
is hexagonal rather than square. Such a constellation has the advantage of
being more nearly spherical.
ALTERNATIVE FORMULATION BASED ON LABEL TRANSLATES
In the preferred embodiment of trellis precoding, we have used a linear
(mod-2) code C.sub.s. This allowed us to use the syndrome-former mapping
methods for preventing error propagation. It is possible to give an
alternative formulation of trellis precoding, based on label translates of
trellis codes, such that the syndrome-former methods can be applied with
nonlinear trellis codes, as well.
As before, for coding we use an N dimensional trellis code C.sub.c
(.LAMBDA..sub.c /.LAMBDA..sub.c ';C.sub.c), where .LAMBDA..sub.c
/.LAMBDA..sub.c ' is a binary lattice partition of order 2.sup.n c and
C.sub.c is a binary, rate-k.sub.c /n.sub.c convolutional code (n.sub.c
=k.sub.c +r.sub.c). For shaping and precoding, we use a trellis code
C.sub.s (.LAMBDA..sub.s /.LAMBDA..sub.s '; C.sub.s) based on a binary rate
k.sub.s /n.sub.s convolutional code C.sub.s (n.sub.s =k.sub.s +r.sub.s).
As shown in FIG. 22, a sequence of r.sub.s -tuples s(D) enters an inverse
syndrome former (H.sup.-1).sup.T for the convolutional code C.sub.s to
produce a sequence of n.sub.s -tuples t(D), which specifies a
label-translated code C.sub.s (.LAMBDA..sub.s /.LAMBDA..sub.s '; C.sub.s
.sym..sub.2 t(D)). The trellis precoder will select the channel output
sequence y(D) from a coset C.sub.s (.LAMBDA..sub.s /.LAMBDA..sub.s ';
C.sub.s .sym..sub.2 t(D))+d(D) of this label-translated code, where d(D)
is a coset representative sequence identifying cosets of .LAMBDA..sub.s in
some translate .LAMBDA..sub.c +a of .LAMBDA..sub.c.
A sequence of k.sub.c -tuples i(D) enters the convolutional encoder Cc to
produce a sequence of n.sub.c -tuples b(D). The sequence b(D) together
with an uncoded sequence of n.sub.f -tuples v(D)specifies the coset
representative sequence d(D). Then a channel output sequence y(D) that
lies in C.sub.s (.LAMBDA..sub.s /.LAMBDA..sub.s '; C.sub.s +t(D))+d(D) can
be identified by d(D) which specifies a sequence of cosets of
.LAMBDA..sub.s in .LAMBDA..sub.c +a, a sequence z(D)=c.sub.s (D)+t(D) with
c.sub.s (D).epsilon.C.sub.s, which further specifies a sequence of cosets
of .LAMBDA..sub.s ' in .LAMBDA..sub.s +d(D) and a sequence
.lambda.(D).epsilon..LAMBDA..sub.s ' which selects a particular sequence
in that coset. A decoder will find the sequences c.sub.s (D) and
.lambda.(D), such that the resulting y(D), after filtering by the channel
inverse g(D), has as small an average power as possible. The transmitted
sequence e(D) is the filtered sequence: e(D)=y(D)g(D).
In the receiver, after appropriate front end filtering, we obtain the
observations r(D)=e(D)h(D)+n(D)=y(D)+n(D). Referring to FIG. 23, the
sequences i(D), v(D) and s(D) can be recovered as follows. First, since
.LAMBDA..sub.s is a sublattice of .LAMBDA..sub.c ', the sequence y(D) is a
legitimate code sequence from C.sub.c. Therefore, a conventional decoder
for C.sub.c can be used to find an estimate y(D), as before, with the same
decoding complexity and probability of error as that of the code C.sub.c
on an ideal channel, h(D)=1. As before, it is possible to translate r(D)
to a fundamental region of .LAMBDA..sub.s ', thus making the decoder
essentially independent of the channel response h(D) without affecting the
performance. In the absence of decoding errors, the sequence d(D),
representing the cosets of .LAMBDA..sub.s ' in .LAMBDA..sub.c +a, can be
obtained directly from y(D). This can be used to recover the sequences
b(D) and v(D). The information sequence i(D) can be found using a decoder
for the convolutional code C.sub.c. The sequence z(D)=c.sub.s (D).sym.t(D)
representing the coset of .LAMBDA..sub.s ' in .LAMBDA..sub.s and be
recovered also directly from y(D). The estimate of the sequence s(D) is
obtained by passing z(D) through a syndrome former H.sup.T ; i.e.,
s(D)=z(D)H.sup.T =c.sub.s (D)H.sup.T .sym.t(D)H.sup.T
=s(D)(H.sup.-1).sup.T H.sup.T =s(D), where we used the well-known fact
that c.sub.s (D)H.sup.T =0. If H.sup.T is chosen to be feedback free, then
s(D) can be recovered without catastrophic error propagation.
The selection of the sequence e(D) can be done, as before, using RSSE
techniques, with the slight modification that trellis branches will now
correspond to cosets of .LAMBDA..sub.s ' in .LAMBDA..sub.s +d.sub.k as
identified by the label-translates z(D)=c.sub.s (D).sym.t(D), the coset
representative sequence d(D) and the sequence .lambda.(D), and the branch
metrics are computed according to
.vertline.e.sub.j .vertline..sup.2 =.vertline.y(z.sub.k =t.sub.k
+c.sub.s,k, d.sub.k,.lambda..sub.k)-.SIGMA..sub.j.gtoreq.1 e.sub.k-j
h.sub.j .vertline..sup.2.
Here we have used the notation y(z.sub.k, =t.sub.k .sym.c.sub.s,k, d.sub.k,
.lambda..sub.k) to indicate a channel output symbol Y.sub.k specified by
z.sub.k, d.sub.k and .lambda..sub.k.
With this method, we can send .beta.N/2=k.sub.c +n.sub.f +r.sub.s bits per
N dimensions, where n.sub.f = log.sub.2 .vertline..LAMBDA..sub.c
'/.LAMBDA..sub.s .vertline.. As before, we can increment n.sub.f by N/2
(or equivalently, by 1 bit per two dimensions) by replacing .LAMBDA..sub.s
by R.LAMBDA..sub.s, because log.sub.2
.vertline..LAMBDA..sub.c,/R.LAMBDA..sub.s .vertline.=log.sub.2
.vertline..LAMBDA..sub.c '/.LAMBDA..sub.s .vertline.+N/2. (Or similarly,
we can increment n.sub.f by N/2 by replacing .LAMBDA..sub.c by
R.LAMBDA..sub.c). To send (N/2).beta.=k.sub.c +r.sub.s j+(d/2.sup.m)(N/2)
bits/N dimensions, where 0.ltoreq.d.ltoreq.2.sup.m, we can again define a
frame of length (N/2)2.sup.m bauds, and use the code C.sub.s for
(N/2)(2.sup.m -d) bauds, and its scaled versions RC.sub.s for (N/2)d
bauds. (A similar effect can be achieved by replacing the coding code
C.sub.c by its time-varying versions based on the codes C.sub.c ad RC.sub.
c). The implementation given above for the time invariant case remains
essentially unchanged, except one now has to take into account the
variations in scaling. Again, constellatation constraints can be applied
to control PAR.
B. ALTERNATIVE FORMULATION BASED ON REGIONS
It is possible to formulate trellis precoding using convolutional codes and
N dimensional regions, instead of trellis codes. This formulation is more
general in some respects. In this section, we describe this formulation,
first using time invariant regions, and then with regions having
time-varying scaling to support fractional rates.
As before, for coding we use an N dimensional trellis code C.sub.c
(.LAMBDA..sub.c /.LAMBDA..sub.c '; C.sub.c), where .LAMBDA..sub.c
/.LAMBDA..sub.c ' is a binary lattice partition of order 2.sup.n c and
C.sub.c is a binary, rate-k.sub.c /n.sub.c convolutional code. For shaping
and precoding, instead of a trellis code, we use a binary, rate k.sub.s
/n.sub.s convolutional code C.sub.s and a set of N-dimensional regions
R(j), j=1, . . . ,J, where J may be infinite. Each region is partitioned
into 2.sup.n s subregions R.sub.n (j), j=1, . . . ,J in such a way that
every subregion contains an equal number of points from each of the
2.sup.n c cosets of .LAMBDA..sub.c ' in a translate .LAMBDA..sub.c +a of
.LAMBDA..sub.c. To transmit at a rate .beta., where .beta..gtoreq.(2/N)
(k.sub.c +r.sub.s), the regions must be properly scaled such that each
subregion contains 2.sup.n c.sup.+n f points from .LAMBDA..sub.c +a, where
n.sub.f =.beta.N/2-k.sub.c -r.sub.s.
We select the elements of the channel output sequences y(D) from cosets of
.LAMBDA..sub.c ' in .LAMBDA..sub.c +a, as specified by the sequence of
n.sub.c -tuples b(D) produced by the convolutional encoder C.sub.c, from
within one of the subregions R.sub.n (j). Any signal point y.sub.k from
.LAMBDA..sub.c +a, in any one of the regions R(j), can be identified by a
quadruplet: y(b.sub.k, v.sub.k, z.sub.k, j.sub.k), where an index j.sub.k
selects a region R(j), an n.sub.s -tuple z.sub.k selects a subregion
R.sub.n (j), an n.sub.c -tuple b.sub.k specifies one of 2.sup.n c cosets
of .LAMBDA..sub.c ' in .LAMBDA..sub.c +a, and an n.sub.f - tuple v.sub.k
picks one of 2.sup.n f points of that coset in R.sub.n (j). As illustrated
in FIG. 24, the convolutional encoder produces the sequence of n.sub.c
-tuples b(D), and uncoded symbols form the sequence of n.sub.f -tuples
v(D). The sequences j(D) and z(D) which identify the subregions are
selected as follows. First, a sequence of r.sub.s - tuples, s(D), is
mapped into a sequence of n.sub.s - tuples t(D) according to
t(D)=s(D)(H.sup.-1).sup.T, where (H.sup.-1).sup.T is a right inverse to
the n.times.r syndrome-former matrix for C.sub.s. Then, in the key step of
trellis precoding, a decoder selects j(D) and z(D).epsilon.t(D).sym..sub.2
C.sub.s such that the transmitted sequence e(D)=y(D)g(D) has as small an
average power as possible.
Since y(D) is a code sequence from C.sub.c (.LAMBDA..sub.c /.LAMBDA..sub.c
'; C.sub.c), it can be decoded, as before, by a decoder for C.sub.c. Again
the decoding complexity and the probability of error will be the same as
if the code C.sub.c was used on an ideal channel. Referring to FIG. 25, if
y(D) is the estimated channel output sequence, then z(D) can be extracted
by identifying the subregions R.sub.z (j) in which the elements y.sub.k
lie. The estimates b(D), v(D) can be found directly from y(D) with an
inverse map. The sequence s(D) can be extracted directly from z(D) with a
syndrome-former H.sup.T according to (s(D)=z(D)H.sup.T, because c.sub.s
(D)H.sup.T =0 and (H.sup.-1).sup.T H.sup.T =I, where I is the r.times.r
identity matrix. If H.sup.T is chosen to be feedback free, then s(D) can
be recovered with no error propagation.
Having discussed the operational principles, we now turn to the selection
of the index sequences j(D) and z(D). To minimize the output average
power, we need to search a trellis with states s.sub.k '=[s.sub.k ;
j.sup.k-1, z.sup.k-1 ], where j.sup.k-1 =(j.sub.k-1, . . . j.sub.k-k) and
z.sup.k-1 =(z.sub.k-1, . . . z.sub.k-K). If J and K are both finite, then
this trellis will have a finite number of states. But even in that case,
it is often necessary to reduce complexity to make the search feasible.
Again, this can be accomplished by an RSSE like shaping decoder. An RSSE
trellis can be constructed by applying set partitioning principles to the
past values of j.sub.k-i and z.sub.k-i, i=1, . . . L.ltoreq.K. Then, the
VA can be applied to search the reduced-state trellis with the branch
metrics
.vertline.e.sub.k .vertline..sup.2 =.vertline.y(b.sub.k, v.sub.k, z.sub.k
=t.sub.k .sym..sub.2 c.sub.s,k, j.sub.k -.SIGMA..sub.j.ltoreq.1 e.sub.k-j
h.sub.j .vertline..sup.2
where c.sub.s,k is an n.sub.s -tuple corresponding to the branches of the
convolutional code, and the minimization is over all possible values of
j.sub.k. Here the minimization is over all possible indices j.sub.k,
1.ltoreq.j.sub.k .ltoreq.J, for the regions R(j). Notice that, for large
values of J, this minimization can be very time-consuming, if one has to
compute the above metric for all possible values of j.sub.k. Now we will
show how this problem is avoided, when the regions are chosen as
fundamental regions of lattices.
But first we should note that when the channel is ideal (h(D)=1), and the
number of regions is one (J=1), then the method described above reduces to
trellis shaping on regions. Notice that in that case, the minimization
step in the branch metric computations is absent.
Now let .LAMBDA..sub.s /.LAMBDA..sub.s ' be an N dimensional lattice
partition of order 2.sup.n s. Next, let R(1) be a fundamental region of
.LAMBDA..sub.s ', and then form an exhaustive partition of N-space into
regions R(j)-R(1)+.lambda..sub.j, were .lambda..sub.j is an element of
.LAMBDA..sub.s ', with .LAMBDA..sub.1 =0. Then partition each R(j) into
2.sup.n s subregions R.sub.n (j), such that each subregion is a
fundamental region of .LAMBDA..sub.s, and furthermore, each subregion
contains an equal number of points from the 2.sup.n c cosets of
.LAMBDA..sub.c ' in .LAMBDA..sub.c +a. Notice that the regions R(j) differ
by points on the lattice .LAMBDA..sub.s ', and hence the minimizing step
in the branch metric computations is now only as complex as decoding
.LAMBDA..sub.s '. An example is shown in FIG. 26 for a 4-way partition of
the type Z.sup.2 /2Z.sup.2.
We may point out that although we have used the syndrome-former methods to
generate the coset representative sequence t(D) in the extensions we
described above, other mapping methods can be used also. However, in that
case, to recover t(D) from z(D) a binary decoder for C.sub.c associated
with the set of coset representatives must be used to extract c.sub.s (D)
and then form t(D)=c.sub.s (D).sym.z(D).
Finally, we should also point out that when C.sub.s is a linear code, the
original formulation based on fundamental regions of time zero lattices is
identical to the formulation based on label translates, and they both can
be posed as a special case of the formulation based on regions.
With this method, we can also send .beta.N/2=k.sub.c +n.sub.f +r.sub.s bits
per N dimensions. As before, we can increment n.sub.f by N/2 by replacing
.LAMBDA..sub.c by R.LAMBDA..sub.c, to send (N/2).beta.=k.sub.c +r.sub.s
+j+(d/2.sup.m)(N/2) bits per N dimensions, where 0.ltoreq.d<2.sup.m. We
can again define a frame of length (N/2)2.sup.m bauds, and use the code
C.sub.c for (N/2)2.sup.m -d.sub.0 bauds, and its scaled version RC.sub.c
for (N/2)d bauds. A similar effect can be achieved by varying the scaling
of the subregions. The implementation given above for the time-invariant
case remains essentially unchaged except one now has to take into account
the time-varying nature of the code or the scaling. Again, constraints can
be applied to reduce the peak to average ratio.
Other embodiments are also within the following claims. For example, other
reduced-complexity decoders (e.g., M algorithm) could be used.
APPENDIX A
TERMINOLOGY AND PRINCIPLES
We first discuss terminology and principles which underlie the invention.
Trellis Precoding
A lattice .LAMBDA. is a collection of N-dimensional vectors c, which form a
group under ordinary vector addition A fundamental region R(.LAMBDA.) of
.LAMBDA. is a region of N-space which contains one and only one point (a
coset representative) from each distinct coset (translate) .LAMBDA.+a of
.LAMBDA.. All fundamental regions of a given lattice have the same volume,
V(.LAMBDA.), and their translates R(.LAMBDA.)+c, c.epsilon..LAMBDA., form
a tesselation of N-space. This induces the following coset decomposition:
Any N-vector y can be uniquely decomposed as y=c+e, where
c.epsilon..LAMBDA. and e.epsilon.R(.LAMBDA.); that means, y is equivalent
to a coset representative e.epsilon.R(.LAMBDA.) modulo .LAMBDA.. The
translates R(.LAMBDA.)+c may be viewed as the decision regions D(c) of a
decoder D(.LAMBDA.), whose error regions D(c)-c are all equal to
R(.LAMBDA.) (to show this correspondence explicitly, in what follows, we
will sometimes write R(.LAMBDA., D) or D(.LAMBDA., R)). Thus, if
e.epsilon.R(.LAMBDA.) is a coset representative, but otherwise an unknown
information bearing vector, then it can be recovered from y=c+e, without
any knowledge about c, by first finding the lattice point c using the
decoder D(.LAMBDA., R) and then forming the error e=y-c.
The Voronoi region R.sub.V (.LAMBDA.) of a lattice .LAMBDA. is defined as
the set of points that are at least as close to the origin as to any other
lattice point. The Voronoi region is a fundamental region corresponding to
a minimum distance decoder of .LAMBDA. (we ignore the effect of ties at
the boundary points).
A rate-k/n convolutional code C is the set of sequences c(D) of q-ary
n-tuples, which can be generated by a kxn generator matrix G as its input
ranges over all sequences of q-ary k-tuples. In analogy to the fundamental
region of a lattice, we can define a set R of sequences of q-ary n-tuples,
which contains one and only one sequence (a coset representative) from
every coset C.sym..sub.2 a(D) of C, where .sym. represents modulo-q
addition. Then, any sequence of q-ary n-tuples z(D) has the unique
decomposition z(D)=t(D).sym..sub.2 c(D), where t(D).epsilon.R and
c(D).epsilon.C. An unknown coset representative sequence t(D).epsilon.R
can be recovered from z(D)=t(D).sym..sub.2 c(D), by first finding the code
sequence c(D) using the decoder D(C,R) for the set of coset
representatives R, and then forming t(D) =z(D).beta..sub.2 c(D).
If .LAMBDA.' is a sublattice of .LAMBDA., then .LAMBDA. is the union of
.vertline..LAMBDA./.LAMBDA.'.vertline.=V(.LAMBDA.')/V(.LAMBDA.) cosets of
.LAMBDA.' in .LAMBDA.. Then we say .LAMBDA./.LAMBDA.' is a lattice
partition of order .vertline..LAMBDA./.LAMBDA.'.vertline., and each
fundamental region R(.LAMBDA.') of .LAMBDA.' will contain
.vertline..LAMBDA./.LAMBDA.'.vertline. points from .LAMBDA..
In general, a signal-space trellis code C(.LAMBDA./.LAMBDA.';C) is based on
an N-dimensional lattice partition .LAMBDA./.LAMBDA.' of order q.sup.n and
a rate k/n, q-ary convolutional code C. Each coded output n-tuple b.sub.k
selects one of the q.sup.n cosets .LAMBDA.' +.zeta.(b.sub.k) of .LAMBDA.'
in .LAMBDA., or some translate of .LAMBDA., according to some labeling
function .zeta.(b.sub.k). The trellis code C(.LAMBDA./.LAMBDA.';C) is the
set of all sequences c(D) that belong to a sequence of cosets of .LAMBDA.'
that could be selected by the code sequences in C. To simplify exposition,
we shall often consider two-dimensional Ungerboeck-type trellis codes
based on 2.sup.n -way two dimensional lattice partitions Z.sup.2 /R.sup.n
Z.sup.2, where Z.sup.2 is the lattice of integer pairs and R is the
two-dimensional rotation operator defined by the 2.times.2 matrix {1,1).
(1,-1)}. In sequence space, a lattice .LAMBDA. can also be viewed as a
trellis code C(.LAMBDA./.LAMBDA.; C)=(.LAMBDA. ).sup.oo, which is based on
the trivial lattice partition .LAMBDA./.LAMBDA. and a trivial rate-1
convolutional code, whose generator matrix G is an identity.
For all known codes C, given any encoder state s.sub.k, the set of all
possible next outputs is a coset of some lattice .LAMBDA..sub.0, called
the time-zero lattice The fundamental regions R.sub.0 of the time zero
lattice play a central role in trellis precoding. For a two-dimensional
code C(Z.sup.2 /R.sup.n Z.sup.2 ; C), the time-zero lattice is
.LAMBDA..sub.0 =R.sup.n-k Z.sup.2.
If C is a linear code, i.e., a group under sequence addition, then it will
carry the key properties of lattices. For example, we can define a
fundamental region R(C) of C as a set of sequences that contains one and
only one sequence (a coset representative) from each distinct coset C+a(D)
of C. Also say any sequence y(D) can be uniquely decomposed as
y(D)=c(D)+e(D), where c(D).epsilon.C and e(D).epsilon.R(C). Thus, a coset
representative sequence e(D).epsilon.R(C) can be recovered from y(D)
=c(D)+e(D), without any knowledge about c(D), by first finding the
sequence c(D) using the decoder D(C,R) for the fundamental region R(C),
and then forming the error sequence e(D)=y(D)-c(D).
A trellis code is linear, if and only if the labeling function .zeta.(b) is
linear; i.e., .zeta.(b.theta.b')=.zeta.(b)+.zeta.(b), where b, b' are two
q-tuples. Most known trellis codes, although nonlinear, exhibit sufficient
reqularity such that their geometric properties such as distance profile
or the shape of their Voronoi regions are independent of the code sequence
c(D). All trellis codes with an isometric labeling function exhibit such
geometric uniformity. For such codes, the decision regions for some given
decoder are not simple translates of each other. But they can be
transformed into another by isometric transformations, which consist of
translations, rotations or reflections. The following theorems play an
important role in trellis precoding.
Theorem 1: Let C.sub.s be a trellis code, possibly nonlinear, with a
time-zero lattice .LAMBDA..sub.0s, then any sequence y(D) can be uniquely
decomposed as y(D)=e(D)+c.sub.s (D), where c.sub.s (D).epsilon.C.sub.s and
e(D) is a coset representative sequence whose elements belong to some
fundamental region R.sub.0s of .LAMBDA..sub.0s. An unknown coset
representative sequence e(D) can be recovered from y(D) by first finding
the code sequence c.sub.s (D) with a hard-decision decoder based on
R.sub.0s and then forming the error sequence e(D)=y(D)-c.sub.s (D) Proof:
Suppose at time k we are in state s.sub.k C.sub.s. Then the next allowable
symbols c.sub.s,k belong to some coset .LAMBDA..sub.0s +a(s.sub.k) of the
time-zero lattice .LAMBDA..sub.0s. Hence, we can use a decoder D(R.sub.0s)
for .LAMBDA..sub.0s +a(s.sub.k) to obtain the decomposition y.sub.k
=e.sub.k +c.sub.s,k, where c.sub.s,k .epsilon..LAMBDA..sub.0s +a(s.sub.k)
and e.sub.k .epsilon.R.sub.0s. Next, we let c.sub.s,k determine the
next-state s.sub.k+1 and then repeat the same argument for time k+1, and
so on. Thus, starting from a kown state s.sub.0, the sequences e(D) and
c.sub.s (D) in the decomposition y(D)=e(D)+c.sub.s (D) will be uniquely
determined. Q.E.D.
Theorem 1 implies that if e(D) is some information-bearing signal whose
symbols e.sub.k are constrained to lie in the fundamental region R.sub.0s,
then we can add an unknown code sequence c.sub.s (D) from C.sub.s to e(D),
and we will be able to recover e(D) from the resulting sequence
y(D)=e(D)+c.sub.s (D) perfectly without the knowledge of c.sub.s (D). In
fact, the above proof shows that the symbols e.sub.k can be recovered with
no delay from the symbols y.sub.k up to time k by a simple `hard decision`
decoder for C.sub.s. Typically, R.sub.0s is chosen as a simple rectangular
region, and then decisions on c.sub.c,k may be made coordinate by
coordinate.
If C(.LAMBDA./.LAMBDA.'; C) is a trellis code, then its label translate
C(.LAMBDA./.LAMBDA.'; C+a(D)) is obtained by replacing the convolutional
code C by its coset C.theta..sub.2 (D). When C(.LAMBDA./.LAMBDA.'; C) is
geometrically uniform, then C(.LAMBDA./.LAMBDA.'; C.theta..sub.2 (D)) has
the same geometric properties as C(.LAMBDA./.LAMBDA.'; C) and it is
related to C(.LAMBDA./.LAMBDA.'; C) by an isometric transformation (for
linear codes that isometric transformation is a simple translation).
Theorem 2: If c.sub.c (D) and c.sub.s (D) are code sequences in
N-dimensional codes C.sub.c and C.sub.s, respectively, and .LAMBDA..sub.s
is a sublattice of .LAMBDA..sub.c ', then y(D)=c.sub.c (D)+c.sub.s (D) is
a code sequence in C.sub.c.
Proof: Every sequence c.sub.s (D) is a sequence of elements of
.LAMBDA..sub.s and therefore of .LAMBDA..sub.c ', which means that
y(D)=c.sub.c (D).+-.c.sub.s (D) is a sequence with elements in the same
sequence of cosets of .LAMBDA..sub.c ' as c.sub.c (D), so it must be in
C.sub.c. Q.E.D.
Top