 |
Claims  |
|
|
I claim:
1. Apparatus comprising
means for receiving a succession of blocks of input data, and
means for defining an alphabet of codewords each associated with a unique
one of the possible values of said input data blocks and for generating,
in response to said blocks of input data, the associated ones of said
codewords,
each of the codewords of said alphabet being comprised of a combination of
at least two modulated signal points taken from a predetermined
constellation of modulated signal points, said alphabet of codewords
having built-in X-fold diversity so that each of the codewords of said
alphabet differs from each other codeword of said alphabet at at least X
particular signal points positions, where X is an integer greater than
unity, and the minimum squared Euclidean distance between said codewords
being greater than the absolute minimum squared Euclidean distance
associated with said alphabet.
2. The invention of claim 1 further comprising means for transmitting a
signal representing said ones of said codewords.
3. The invention of claim 1 wherein said blocks of input data are received
at a rate of m bits every T seconds, where T is a predetermined signalling
interval M>0 and wherein said constellation includes more than 2.sup.m
modulated signal points.
4. The invention of claim 1 wherein said constellation of modulated signal
points is an M-PSK constellation, where M is a selected integer.
5. The invention of claim 1 wherein said defining and generating means
generates said ones of said codewords by encoding said each block of input
data into blocks of encoded bits and by selecting the signal points which
comprise each one of said ones of said codewords in response to said each
block of encoded bits.
6. The invention of claim 5 wherein said ones of said codewords occur in
successive frames of J codewords each, wherein particular ones of the
codewords of said alphabet differ in exactly X signal point positions, two
of which are the k.sup.th and q.sup.th signal point positions, and wherein
said apparatus further comprises means for generating a re-ordered
succession of the signal points of the codewords of each frame in such a
way that the signal points at said k.sup.th and q.sup.th signal point
positions are separated by more than J signal points in said succession.
7. The invention of claim 1 wherein each of the codewords of said alphabet
differs from each other codeword of said alphabet at at least X particular
signal point positions and wherein said apparatus further comprises means
for transmitting the signal points comprising said ones of said codewords
in respective signalling intervals.
8. The invention of claim 5 wherein said ones of said codewords occur in
successive frames of codewords and wherein said apparatus further
comprises means for generating a re-ordered succession of the signal
points of the codewords of each frame in such a way that the signal points
at corresponding signal point positions of the codewords within each frame
are grouped together.
9. The invention of claim 8 further comprising means for transmitting a
signal representing said re-ordered signal points using carrier phase
differences.
10. The invention of claim 8 further comprising means for transmitting a
signal representing the re-ordered signal points using carrier phase
differences augmented by a constant value.
11. The invention of claim 5 wherein said ones of said codewords occur in
successive frames of codewords, wherein each of said codewords is
comprised of N signal points, and wherein said apparatus further comprises
means for re-ordering the signal points of the codewords of each frame in
such a way that, for i=1, 2, . . . , N, the respective i.sup.th signal
points of the codewords of a frame are arranged in respective groups.
12. The invention of claim 5 wherein said ones of said codewords occur in
successive frames of codewords and wherein said apparatus further
comprises means for generating a re-ordered succession of the signal
points of the codewords of each frame in such a way that, in the
re-ordered succession, the separation between the signal points within
each codeword is increased.
13. A method for decoding a plurality of sequences of received signal
points received over respective fading channels, each of said sequences
representing a particular transmitted 2N-dimensional codeword of a
predetermined block code, said code being of a type comprised of an
alphabet of codewords each of which is, in turn, comprised of a
combination of at least two modulated signal points of a constituent
constellation, said alphabet being an alphabet which can be formed by (a)
selecting particular concatenations of the signal points of the
constituent constellation to be a first set of elements, (b) grouping the
last-defined set of elements into subsets, (c) selecting at least ones of
the elements of particular selected concatenations of the subsets of step
(b), and (d) repeating steps (b), (c) and (d) until 2N-dimensional
elements are formed, whereby those elements are said 2N-dimensional
codewords, said method comprising the steps of
measuring, for each particular sequence, the squared Euclidean distance
between each received signal point of that particular sequence and all
possible transmitted signal points to provide an ensemble of preliminary
signal point metrics associated with said each received signal point of
said particular sequence,
combining the resulting ensembles of preliminary signal point metrics to
generate an ensemble of final signal point metrics,
finding, for each of a plurality of elements made up of concatenations of
received signal points, the closest element from each of the subsets of
possible transmitted elements by adding the final signal point metrics
corresponding to each element of that particular subset and selecting as
said closest element the element corresponding to a subset metric equal to
the smallest such sum,
finding, for each of a plurality of higher-dimensional elements made up of
concatenations of the previously selected closest elements, the closest
element from each of the higher-dimensional subsets of possible
transmitted elements by adding the subset metrics corresponding to each
possible concatenation of subsets of that particular higher-dimensional
subset and selecting, as said closest element, the element corresponding
to a higher-dimensional subset metric equal to the smallest such sum, and
iterating the second of said finding steps until a single 2N-dimensional
element is selected, said 2N-dimensional element being the decoded
codeword.
14. Apparatus comprising
means for receiving a succession of blocks of input data at a rate of m
bits every T seconds, where T is a predetermined signalling interval m>0,
means for defining an alphabet of codewords each associated with a unique
one of the possible values of said input data blocks and for generating,
in response to said blocks of input data, the associated ones of said
codewords,
each of the codewords of said alphabet being comprised of a combination of
at least two modulated signal points taken from a predetermined
constellation of modulated signal points, said constellation including
more than 2.sup.m modulated signal points and said alphabet of codewords
having built-in diversity.
15. The invention of claim 14 wherein said defining and generating means
generates said ones of said codewords by encoding said each block of input
data into blocks of encoded bits and by identifying the signal points
which comprise each one of said ones of said codewords in response to said
each block of encoded bits.
16. The invention of claim 15 wherein said constellation of modulated
signal points is an M-PSK constellation, where M is a selected integer.
17. The invention of claim 16 wherein M is other than an integral power of
2.
18. The invention of claim 15 wherein the minimum squared Euclidean
distance between said codewords is greater than the absolute minimum
squared Euclidean distance associated with said alphabet.
19. The invention of claim 18 further comprising means for re-ordering the
signal points of the resulting stream of codewords in such a way as to
increase the separation between those signal points of each codeword which
provide said built-in diversity.
20. The invention of claim 19 further comprising means for transmitting a
signal representing the re-ordered signal points using carrier phase
differences.
21. The invention of claim 19 further comprising means for transmitting a
signal representing the re-ordered signal points using carrier phase
differences augmented by a constant value.
22. A method comprising the steps of
receiving a succession of blocks of input data, and
generating, in response to said blocks of input data, associated codewords
of an alphabet of codewords each associated with a unique one of the
possible values of said input data blocks,
each of the codewords of said alphabet being comprised of a combination of
at least two modulated signal points taken from a predetermined
constellation of modulated signal points, said alphabet of codewords
having built-in X-fold diversity, where X is an integer greater than
unity, and the minimum squared Euclidean distance between said codewords
being greater than the absolute minimum squared Euclidean distance
associated with said alphabet.
23. The invention of claim 22 comprising the further step of transmitting a
signal representing said associated codewords.
24. The invention of claim 23 wherein said blocks of input data are
received at a rate of m bits every T seconds, where T is a predetermined
signalling interval, and wherein said constellation includes more than
2.sup.m modulated signal points.
25. The invention of claim 24 wherein said constellation of modulated
signal points is an M-PSK constellation, where M is a selected integer.
26. The invention of claim 25 wherein in said generating step said one of
said codewords is generated by encoding said each block of input data into
blocks of encoded bits and by selecting the signal points which comprise
said one of said codewords in response to said each block of encoded bits.
27. The invention of claim 22 wherein each of the codewords of said
alphabet differs from each other codeword of said alphabet at at least X
particular signal point positions.
28. The invention of claim 26 wherein each of the codewords of said
alphabet differs from each other codeword of said alphabet at at least X
particular signal point positions and wherein said method comprises the
further step of transmitting the signal points comprising said associated
codewords in respective signalling intervals.
29. The invention of claim 27 wherein said associated codewords occur in
successive frames of codewords and wherein said method comprises the
further step of generating a re-ordered succession of the signal points of
the codewords of each frame in such a way that the signal points at
corresponding signal point positions of the codewords within each frame
are grouped together.
30. The invention of claim 29 comprising the further step of transmitting a
signal representing said re-ordered signal points using carrier phase
differences.
31. The invention of claim 29 comprising the further step of transmitting a
signal representing the re-ordered signal points using carrier phase
differences augmented by a constant value.
32. The invention of claim 27 wherein said associated codewords occur in
successive frames of codewords, wherein each of said codewords is
comprised of N signal points and wherein said method comprises the further
step of re-ordering the signal points of the codewords of each frame in
such a way that, for i=1, 2, . . . , N, the respective i.sup.th signal
points of the codewords of a frame are arranged in respective groups.
33. The invention of claim 27 wherein said associated codewords occur in
successive frames of codewords and wherein said method comprises the
further step of generating a re-ordered succession of the signal points of
the codewords of each frame in such a way that, in the re-ordered
succession, the separation between the signal points within each codeword
is increased.
34. The invention of claim 27 wherein said associated codewords occur in
successive frames of J codewords each, wherein particular ones of the
codewords of said alphabet differ in exactly X signal point positions, two
of which are the k.sup.th and q.sup.th signal point positions, and wherein
said method comprises the further step of generating a re-ordered
succession of the signal points of the codewords of each frame in such a
way that the signal points at said k.sup.th and q.sup.th signal point
positions are separated by more than J signal points in said succession.
35. A method comprising the steps of
receiving a succession of blocks of input data at a rate of m bits every T
seconds, where T is a predetermined signalling interval m>0,
generating, in response to said blocks of input data, associated codewords
of an alphabet of codewords each associated with a unique one of the
possible values of said input data blocks,
each of the codewords of said alphabet being comprised of a combination of
at least two modulated signal points taken from a predetermined
constellation of modulated signal points, said constellation including
more than 2.sup.m modulated signal points and said alphabet of codewords
having built-in diversity.
36. The invention of claim 35 wherein in said generating step said ones of
said codewords are generated by encoding said each block of input data
into blocks of encoded bits and by identifying the signal points which
comprise each one of said generated codewords in response to said each
block of encoded bits.
37. The invention of claim 36 wherein said constellation of modulated
signal points is an M-PSK constellation, where M is a selected integer.
38. The invention of claim 37 wherein M is other than an integral power of
2.
39. The invention of claim 36 wherein the minimum squared Euclidean
distance between said codewords is greater than the absolute minimum
squared Euclidean distance associated with said alphabet.
40. The invention of claim 39 comprising the further step of reordering the
signal points of the resulting stream of codewords in such a way as to
increase the separation between those signal points of each codeword which
provide said X-fold built-in diversity.
41. The invention of claim 40 comprising the further step of transmitting a
signal representing the re-ordered signal points using carrier phase
differences.
42. The invention of claim 40 comprising the further step of transmitting a
signal representing the re-ordered signal points using carrier phase
differences augmented by a constant value.
43. A method comprising the steps of
receiving a succession of blocks of input data, and
defining an alphabet of 2N-dimensional codewords each associated with a
unique one of the possible values of said input data blocks and
generating, in response to each of said blocks of input data, the
associated one of said codewords,
each of the codewords of said alphabet being comprised of a combination of
at least two modulated signal points of a constituent constellation, said
alphabet of codewords having built-in diversity, and said alphabet being
an alphabet which can be formed by (a) selecting particular concatenations
of the signal points of the constituent constellation to be a first set of
elements, (b) grouping the last-defined set of elements into subsets, (c)
selecting at least ones of the elements of particular selected
concatenations of the subsets of step (b), and (d) repeating steps (b),
(c) and (d) until 2N-dimensional elements are formed, whereby those
elements are said 2N-dimensional codewords.
44. A method for decoding a sequence of received signal points representing
a transmitted 2N-dimensional codeword of a predetermined block code, said
code being of a type comprised of an alphabet of codewords each of which
is, in turn, comprised of a combination of at least two modulated signal
points of a constituent constellation, said alphabet being an alphabet
which can be formed by (a) selecting particular concatenations of the
signal points of the constituent constellation to be a first set of
elements, (b) grouping the last-defined set of elements into subsets, (c)
selecting at least ones of the elements of particular selected
concatenations of the subsets of step (b), and (d) repeating steps (b),
(c) and (d) until 2N-dimensional elements are formed, whereby those
elements are said 2N-dimensional codewords, said method comprising the
steps of
measuring the squared Euclidean distance between each received signal point
and all possible transmitted signal points to provide an ensemble of
signal point metrics associated with said each received signal point,
finding, for each of a plurality of elements made up of concatenations of
received signal points, the closest element from each of the subsets of
possible transmitted elements by adding the signal point metrics
corresponding to each element of that particular subset and selecting as
said closest element the element corresponding to a subset metric equal to
the smallest such sum,
finding, for each of a plurality of higher-dimensional elements made up of
concatenations of the previously selected closest elements, the closest
element from each of the higher-dimensional subsets of possible
transmitted elements by adding the subset metrics corresponding to each
possible concatenation of subsets of that particular higher-dimensional
subset and selecting, as said closest element, the element corresponding
to a higher-dimensional subset metric equal to the smallest such sum, and
iterating the second of said finding steps until a single 2N-dimensional
element is selected, said 2N-dimensional element being the decoded
codeword. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
The present invention relates to coded modulation techniques and, more
particularly, the use of such techniques in fading channel applications,
e.g., digital cellular mobile radio.
During the past decade, trellis-coded modulation has proven to be a
practical power-efficient and bandwidth-efficient modulation technique for
channels with additive white Gaussian noise (AWGN). This technique has now
been widely used in commercial telephone-line modems and has resulted in
an increase of line rates of those modems to as much as 19.2 Kbits/s.
More recently, those in the art have investigated the applicability of
trellis-coded modulation to a further class of channels--specifically,
fast-fading channels, i.e., channels in which the signal amplitude can
vary so drastically over short time intervals that it is not practical to
track it and thereby to accurately recover the transmitted information.
Indeed, the signal amplitude may be so weak that, even if it could be
tracked, accurate data recovery may, again, not be possible. Mobile radio
channels of various types fall within this category. As in telephone-line
modem applications, the use of trellis codes in such channels provides
so-called "coding gain" in signal power (compared to so-called "uncoded"
modulation approaches). The ultimate result is an enhanced capability for
accurate information recovery without requiring additional signal
bandwidth. Unfortunately, it turns out that the improvement in error rate
performance achieved for a given amount of coding gain is significantly
less for the fast-fading channel than for, say, the telephone-line
channel. For example, 3 dB of coding gain can provide as much as three
orders of magnitude improvement in the error rate for the telephone-line
channel, but only about a factor-of-three improvement for the fast-fading
channel. This disparity arises principally out of the very nature of the
fast-fading channel, i.e., its fading characteristics.
SUMMARY OF THE INVENTION
The prior art has recognized that it is possible to take into account the
occurrence of fast fades in the channel--and thereby provide enhanced
coding gain--by using a combination of (a) particular trellis codes
exhibiting so-called "built-in time diversity" with (b)
interleaving/deinterleaving techniques which re-order the transmitted
signal points. At the same time, however, I have recognized that, in
general, such prior art solutions may be less than wholly satisfactory for
particular applications. Digital cellular mobile radio (hereafter referred
to more simply as "mobile radio") is a notable example.
In particular, realization of the potential coding gain of such schemes
necessitates the use of an interleaver/deinterleaver whose characteristics
are such that a significant amount of transmission delay may be introduced
at both the transmitter and the receiver. The real-time nature of, for
example, mobile radio systems means that such delay may have a significant
negative impact on system performance. Moreover, realization of the
potential coding gain entails even greater delay in systems which use a
time-division-multiple-access (TDMA) approach--which has now been
incorporated into the North American standard for next-generation mobile
radio. (This effect arises from the fact that, in a TDMA system, the
signal points originating from a particular one source are much closer to
one another in time than would otherwise be the case.) Additionally, the
fact that a trellis decoder, in order to output any particular signal
point, needs to wait until it has received a number of subsequent signal
points may result in certain yet additional delays and/or may waste some
of the channel capacity in some specific applications. Such applications
include systems involving speech encoders which encode on a block-by-block
basis.
In accordance with the present invention, I have realized that utilizing
interleaved block-coded modulation with built-in time diversity can
achieve comparable or better coding gain than the above-described prior
art while affording a large number of advantages thereover. Such
advantages include: less implementational complexity; less
interleaver/deinterleaver and decoding delay; the availability of higher
bandwidth efficiency for some codes; enhanced flexibility in arriving at a
system design having a desired tradeoff among complexity, power efficiency
and bandwidth efficiency; and fewer system issues in general.
In preferred embodiments, a constant-amplitude type of signal constellation
is used in order to account for the fast variations in signal amplitude
that are the hallmark of mobile radio and other fast-fading channels.
Moreover, due to the fast variation in carrier phase that occurs in such
channels, use of a non-coherent differential detection method is
preferred. Both of these criteria are advantageously satisfied by the use
of M-point differential phase shift keying, or M-DPSK.
In accordance with a feature of the invention, the particular way in which
the signal points are re-ordered by the interleaver is matched to the
particular block code being used, thereby advantageously increasing the
effective, although not the actual, size of the interleaver and thus
contributing to the aforementioned reduced interleaver/deinterleaver delay
.
BRIEF DESCRIPTION OF THE DRAWING
In the drawing,
FIG. 1 is a block diagram of a data communications system embodying the
principles of the invention;
FIG. 2 is a chart which helps explain certain terminology and concepts;
FIG. 3 shows an 8-PSK constellation which forms the basis of a number of
the block codes disclosed herein;
FIG. 4 depicts a codebook for a first block-coded modulation scheme in
accordance with the invention;
FIG. 5 illustrates the operation of the interleaver shown in FIG. 1 with
respect to the first block-coded modulation scheme;
FIGS. 6 and 7 graphically depict a second block-coded modulation scheme in
accordance with the invention;
FIGS. 8 and 9 graphically depict a third block-coded modulation scheme in
accordance with the invention;
FIG. 10 illustrates the operation of the interleaver with respect to the
third block-coded modulation scheme;
FIGS. 11-13 graphically depict a fourth block-coded modulation scheme in
accordance with the invention;
FIG. 14 is a block diagram of the encoder/mapper of FIG. 1 for a fifth
block-coded modulation scheme in accordance with the invention;
FIGS. 15-17 show the details of various parts of the encoder/mapper of FIG.
14;
FIG. 18 shows a 12-PSK constellation which forms the basis of a sixth
block-coded modulation scheme in accordance with the invention;
FIGS. 19-20 graphically depict the sixth block-coded modulation scheme; and
FIG. 21 is a block diagram of circuitry for implementing the sixth
block-coded modulation scheme.
DETAILED DESCRIPTION
In the transmission system of FIG. 1, input data on leads 11 is applied to
a 2N-dimensional block encoder/mapper 13 at a rate of m bits per T-second
signalling interval, where m can be an integer or a fractional number.
Block encoder/mapper 13 accumulates a block of input data comprised of N
signalling intervals' worth of bits and then uses a selected
2N-dimensional block code to encode the accumulated N.times.m bits into N
groups of (m+r) encoded bits those groups being provided successively on
leads 16. Here, the parameter r is the average number of redundant bits
per signalling interval introduced by the block encoder/mapper 13. Each
allowed bit pattern of the (m+r)-bit group is associated with a particular
signal point of a two-dimensional (2D) M(.ltoreq.2.sup.m+r)-PSK
constellation, where M is a selected integer. Specifically, the signal
point on leads 16 during the n.sup.th signalling interval is denoted
P.sub.n. The block code is referred to as being "2N-dimensional" because
each signal point has 2 dimensions and each "codeword" output by the block
encoder/mapper 13 is represented by N signal points.
Attention is directed briefly to FIG. 2 which will be helpful in
understanding certain of the terminology and concepts used herein. The
2N-dimensional block encoder/mapper generates 2N-dimensional "codewords".
Each codeword is comprised of a sequence of N "signal points". Each signal
point is a point in a predetermined two-dimensional
"constellation"--illustratively shown in FIG. 2 as a phase shift keying
constellation having eight signal points, or 8-PSK. This 2N-dimensional
codeword is delivered during N "signalling intervals," one signal point in
each signalling interval. The assemblage of all 2N-dimensional codewords
is referred to as the "2N-dimensional constellation," with each codeword
being an "element" of the 2N-dimensional constellation. The 2N-dimensional
constellation is also referred to as a codebook or as an alphabet. In the
description to follow, each 2N-dimensional codeword is often treated as a
concatenation of two constituent N-dimensional elements of a constituent
N-dimensional constellation, where the constituent N-dimensional
constellation may be arrived at similarly to the 2N-dimensional
constellation. This view may be iterated for the N/2 -, N/4, etc.,
dimensional elements and constellations.
Returning to FIG. 1, the N successive 2D signal points output by
encoder/mapper 13 on leads 16 in response to each group of N.times.m input
bits are applied to interleaver 21. The function of the latter is to
re-order the signal points P.sub.n so that the signal points belonging to
any particular codeword will be separated from one another in time when
transmitted. This approach reduces the likelihood that a fade in the
channel will affect more than one of the N signal points in a codeword. In
preferred embodiments, the block code used in block encoder/mapper 13 has
built-in time diversity, to be described in detail hereinbelow, and this
time separation of the signal points greatly enhances the ability of such
a code to accurately recover the transmitted data, as will also be
described. Furthermore, in accordance with a feature of the invention, the
block code and the interleaver re-ordering algorithm are chosen jointly so
as to yet further enhance this ability.
Finally, the re-ordered signal points Q.sub.n output by the interleaver on
leads 24 are applied to modulator 25 whose output, in turn, is applied to
fast-fading channel 30. Modulator 25 is described more fully hereinbelow.
In the receiver, demodulator 41 and deinterleaver 44 perform the inverse
functions of modulator 25 and interleaver 21, respectively. Accordingly,
the output of the latter, on leads 45, is the received, but
channel-corrupted sequence of signal points, P.sub.n, corresponding to the
sequence of signal points appearing on leads 16 at the output of
encoder/mapper 13. These are applied to block decoder 51 which recovers
and provides, on leads 53, the originally transmitted input data. In
accordance with a feature of the invention, as described more fully
hereinbelow, block decoder 51 illustratively operates on the bais of
so-called "soft decisions" similar to the maximum-likelihood decoder
conventionally used for trellis-coded signals in AWGN environments.
At this point, it will be useful to explain the concept of time diversity
coding in the context of a first particular illustrative block-code
modulation scheme--referred to as Code I--that may be implemented in the
illustrative embodiment of FIG. 1.
In particular, an 8-PSK signal constellation, as shown in FIG. 3, is
illustratively used in implementing a four-dimensional (4D) code, meaning
that each codeword generated by the code is comprised of two 2D points of
the 8-PSK constellation. Those points are transmitted in respective
signalling intervals. The eight points of the constellation are labelled 0
through 7. In this case, the parameters m and r are each equal to 1.5
and, of course, N=2. Thus, block encoder/mapper 13 generates a 3-bit word
in each of two successive signalling intervals, each such word
identifying, by its bit values, a particular one of the signal points 0
through 7.
The encoding/mapping of the (N.times.m)=3 bits input to block
encoder/mapper 13 on leads 11 into codewords on leads 16 is shown in the
table of FIG. 4 wherein each 3-bit pattern in parentheses denotes the
values of the (m+r=) 3 encoded bits and is simply the binary version of
the decimal label of its associated signal point. There are 2.sup.3 =8 bit
patterns, and hence 8 codewords. Notationally, each codeword is referenced
hereinafter in the form (x,y) where x and y are, respectively, the first
and second signal points comprising the codeword.
Significantly, each of the codewords of Code I differs from any other
codeword in both of the constituent 2D points. Thus, for example, neither
the first nor the second signal point of the codeword (0,0) is the same as
the first or second signal point of any other codeword. The significance
of this property may be understood by considering the case when the
amplitude of one of the two constituent signal points is so severely
attenuated due to a channel fade that the information carried by it is
completely lost. It is nonetheless possible to recover that information as
long as the other constituent signal point of the codeword has been
accurately recovered. In particular, if the first signal point of a
recovered codeword is "3" whereas the second signal point is lost, the
transmitted codeword can nonetheless be determined to have been (3,7)
because no other codeword has "3" as its first signal point. (This
analysis is an oversimplification of how the decoding process is
preferably carried out, but is useful for purposes of explanation.) Thus
it is seen that this code provides built-in enhanced immunity to
fade-induced transmission errors via the mechanism of time diversity. That
is, information about each input data bit appears redundantly in the time
domain within the coded signal. Thus, for example, information about each
of the three bits of the input bit pattern 010 appears both in the first
signal point "3" and in the second signal point "7" of the corresponding
codeword (3,7).
In general, a code is said to have X-fold time diversity, where X is an
integer greater than unity, if each codeword, which is comprised of an
ordered sequence of signal points, differs from each other codeword at at
least X signal point positions. It will thus be appreciated that Code I
has two-fold built-in time diversity. There are, indeed, a number of ways
in which the signal points of FIG. 3 can be combined into a codebook of 4D
codewords exhibiting two-fold built-in time diversity. Advantageously,
however, the one shown in FIG. 4 has the further advantage of maximizing
the minimum squared Euclidean distance between codewords (given the
requirement of two-fold time diversity), which further enhances the error
immunity of the overall coding scheme. That distance is "4" for this code.
It is important at this point to emphasize that what is being described is
a coded modulation scheme. By this meant a scheme in which, (a) in order
to reduce the signal bandwidth requirement resulting from the introduction
of the redundant bits, the size of the signal constellation is increased
to more than 2.sup.m signal points and (b) the block encoding and
constellation mapping are interdependent. This is in sharp contrast to
conventional block coding schemes in which (a) the introduction of the
redundant bits is accommodated by expanding the signal bandwidth and (b)
the block coding and constellation mapping bear no relationship to one
another.
More specifically, it is appropriate at this point to compare (a) a code
embodying the principles of the present invention which uses signal points
from a 2D M-PSK constellation to (b) a scheme which may, for example,
block encode the input bits using, for example, a Reed-Solomon or other
block code and then transmit the resulting encoded bits as a sequence of
signal points each taken from the same 2D M-PSK constellation. In such a
case, the resulting ensemble of sequences of transmitted signal points may
have some of the attributes of a code embodying the principles of the
present invention, such as X-fold time diversity and some coding gain. Any
such approach, however, would not be concerned with the minimum Euclidean
distance between the transmitted sequences of signal points, as is the
case with the present invention. As a result, the minimum squared
Euclidean distance between the transmitted sequences of signal points may
be as small as a metric herein defined as the "absolute minimum squared
Euclidean distance" associated with the alphabet in question. That metric
is given by the minimum squared Euclidean distance between any pair of
signal points of the 2D M-PSK constellation multiplied by the diversity
parameter "X". Thus, for example, the absolute minimum squared Euclidean
distance of a 4D code having 2-fold time diversity and using the 2D 8-PSK
constellation of FIG. 3 is 1.17, which is the minimum squared Euclidean
distance between the codewords of the 4D code comprised of the codewords,
(0,0), (1,1), (2,2) . . . (7,7). Codes embodying the present invention, by
contrast, have a minimum squared Euclidean distance between the
transmitted sequences of signal points, i.e., between the codewords, which
is greater than the aforementioned absolute minimum squared Euclidean
distance. For Code I, for example, which also has two-fold diversity and
also uses the constellation of FIG. 3, the minimum squared Euclidean
distance between codewords is 4.
A further distinction is that conventional block encoding approaches
typically use the same constellation that would be used by their uncoded
counterparts. Thus, for example, to transmit (integer) m information
bits/signalling interval in an uncoded system, then the constellation used
would have 2.sup.m modulated signal points. Even if r redundant
bits/signalling interval were introduced by the conventional block code,
the same constellation would still be used and the band rate would be
increased by a factor of (m+r)/m in order to accommodate these redundant
bits. By contrast, coded modulation approaches, such as the present
invention, accommodate at least some of the redundant bits by expanding
the size of the constellation to have more than 2.sup.m modulated signal
points.
Furthermore, there are a number of ways in which the input bit patterns can
be assigned to the various codewords in FIG. 4. Advantageously, however,
the particular assignment scheme shown in FIG. 3 has the further advantage
of reducing the number of bit errors that occur when the transmitted
codeword is decoded incorrectly. Specifically, a Gray coding type of
scheme is used to assign the input bit patterns to the codewords. Assume
that the second of the two signal points of a codeword may be lost and the
information bits will be recovered based solely on the first received
signal point. Now note in FIG. 4 how codewords whose first signal point
are the closest to each other in Euclidean distance are assigned to bit
patterns which differ in only one bit position. The underlying concept is
that the signal points that are closest to one another are the ones that
are most likely to be confused with one another. This being so, the
adoption of the aforementioned Gray coding type of scheme for assigning
the bit patterns assures that the minimum number of bit errors are
associated with such most-likely-to-occur decoding errors. Thus since
signal points 0 and 1 have the minimum distance between them, the bit
patterns "000" and "001" respectively assigned to them differ in only one
bit position. (It is not possible with this particular code to
simultaneously provide such enhanced error correction capability for an
assumed fading of the first signal point, but some overall advantage is
nonetheless achieved by treating only one case.) Finally, it may be noted
that this Gray coding concept is used whenever, and to the extent,
possible in the other codes to be described herein although specific
mention thereof will not be made herein.
It will be appreciated that if a particular one signal point is lost due to
fading, there is a significant likelihood that time-adjacent signal that
is points may also be lost. Therefore, in accordance with a principle
known in the art, the error immunity afforded by the built-in time
diversity of the code can be enhanced by time-separating the two signal
points of each codeword so that it is less likely that the two points of
the codeword will fade concurrently. It is to this end that the signal
points P.sub.n on leads 16 of FIG. 1 are applied to interleaver 21.
Specifically, interleaver 21 takes in and stores a frame of J codewords,
graphically depicted in FIG. 5 as being stored in respective rows of a
storage matrix maintained within the interleaver. At the point in time
depicted in the figure, signal points P.sub.1 and P.sub.2 of a first
codeword are stored in the first row, signal points P.sub.3 and P.sub.4 of
a second codeword are stored in the second row, etc. In the most
straightforward type of implementation, the interleaver may wait until all
J of the codewords have been read in. It then may read out the signal
points that make up the codewords on a column-by-column basis, i.e., first
the odd-numbered signal points P.sub.1, P.sub.3, . . . , P.sub.2J-1, and
then the even-numbered signal points P.sub.2, P.sub.4, . . . , P.sub.2J.
(In more efficient implementations, it may be possible for the interleaver
to begin reading out the odd-numbered signal points before all J codewords
have been read in, as long as enough codewords have been read in to assure
a synchronous flow of signal points on leads 24.) Note that the signal
points at corresponding signal point positions of the codewords within the
frame are now grouped together. That is, for i=1,2, . . . , N, the
respective i.sup.th signal points of the codewords of a frame are arranged
in respective groups. Thus, as desired, the two signal points of each
codeword, appearing in a re-ordered succession on interleaver output leads
24, are now advantageously quite separated in time--specifically by J
signalling intervals. The process obviously repeats for successive frames
of J codewords.
Ideally, the effectiveness of the interleaver is maximized when the
parameter J is greater than or equal to 1/4 of the carrier wavelength
divided by the minimum vehicle speed of interest multiplied by the
signalling rate. (This formula is based on the assumption that there is
only a single user per mobile radio channel, as is the case when a
frequency-division-multiplexing-access (FDMA) approach is used. The
considerations surrounding the case where several users are
time-multiplexed onto one channel--the so-called TDMA approach--are
treated at a more opportune point hereinbelow.) For particular
applications, however, a value of J less than this optimum may have to be
used to reduce the transmission delay introduced by the
interleaver/deinterleaver. (This may be necessary to ensure a desired
level of data throughput or to avoid unnatural conversational delays that
may otherwise be introduced into a conversation.)
Finally, the re-ordered signal points Q.sub.n output by the interleaver on
leads 24 are applied to .pi./M-Shifted M-DPSK modulator 25, whose carrier
phase is shifted from that in the previous signalling interval by
2.pi.Q.sub.n /M augmented by a constant value of .pi./M radians. In
accordance with a feature of the invention, I have recognized that the use
of such .pi./M-shifted modulation can help to reduce the peak-to-average
power ratio and can ameliorate potential timing recovery problems in the
receiver.
Moreover, I have recognized that the fact that the transmitted signal
points are interleaved advantageously eliminates, in the decoder, the
correlation between the noise samples introduced by the M-DPSK
demodulating process.
Code I has a bandwidth efficiency of 1.5 bits/signalling interval and a 8.9
(14.3) dB coding gain--relative to, say, an uncoded 4-DPSK scheme having
the same information bit rate--for a mobile channel at a 20 (60)
miles/hour vehicle speed assuming a bit error rate of 10.sup.-3. These
coding gains assume a particular "interleaving length" (given by the
interleaving frame size, which is 2J for this case, divided by the
signalling rate) of 37 ms, which is dic | | |
