Note: Descriptions are shown in the official language in which they were submitted.
CA 02186688 2004-09-20
TRANSMITTER ANTENNA DIVERSITY AND FADING-RESISTANT
MODULATION FOR WIRELESS COMMUNICATION SYSTEMS
FIELD OF THE INVENTION
The present invention relates to a method of fading-resistant
modulation for wireless communication systems prone to Rayleigh fading. More
particularly, the method relates to the use of transmitter diversity and the
design
of transmission signal space constellations used therewith which are resistant
to
fading compared to systems not using transmitter diversity. The resulting
constellation symbols are represented as vectors in L-dimensional space and
to their components are transmitted in different antennas, carrier
frequencies, or
time slots which have been designed to undergo essentially independent fading.
The resulting scheme has a significantly superior performance to a system not
using diversity or a system that uses the standard L-dimensional hypercube
(with different components being transmitted over different antennas,
is frequencies, or time slots) as the signal constellation.
BACKGROUND OF THE INVENTION
A major problem associated with wireless communication systems
is fading of the transmitted signal of the type arising due to multi-path
2o propagation of the radio signal in which the amplitude of the signal
undergoes
random fluctuations at the receiver. Such random fluctuations are typically
modelled by a Rayleigh distributed random variable and the resulting fading is
typically referred to as Rayleigh fading. Examples of such channels include
the
mobile radio communications channel where signals are
z t ~~~~g
reflected by walls, furniture, and people.
In a digital communication system information is transmitted as a sequence
of symbols belonging to some signalling alphabet. The signalling alphabet is
represented
as a set of Q vectors in an L-dimensional vector space and is referred to as
the signalling
constellation. These vectors are also referred to as points in the signalling
constellation.
Each transmitted symbol (vector, or point) carries logzQ bits of information.
The problem of signal fading manifests itself as a distortion of the
signalling
constellation where some of the points move closer together. The result is
that at the
receiver errors are made during the detection process (information decoding}
where a
given transmitted constellation point is interpreted as a different
constellation point as a
result of channel noise and errors in transmission occur. Techniques to reduce
the
problem of Rayleigh fading include the use of frequency, time, and antenna
diversity. With
frequency diversity signals are transmitted over different carrier
frequencies; with time
diversity signals are transmitted over different time slots; and with antenna
diversity the
signal is transmitted or received over multiple antennas.
In typical frequency or time diversity the same signal is transmitted over the
different carrier frequencies or time slots. This results in a decrease of the
number of bits
per Hertz and a consequent loss in spectral efficiency. With receiver antenna
diversity the
same signal is received over different antennas, there is no loss in spectral
efficiency, but
there is a requirement for the use of at least two antennas at the receiver
with a sufficient
separation which may be difficult to implement in small terminals.
To maintain a high spectral efficiency frequency or time diversity should be
2
CA 02186688 2003-03-03
based on the transmission of different information symbols over the different
frequencies
or time slots. However if we split the information bit stream into a set of
substreams and
transmit each sub-stream over a different frequency or time slot then there is
no benefit
to using diversity. Thus far the use of antenna diversity has been relegated
mostly to the
receiver. Some schemes of transmitter diversity have been developed where a
signal and
a delayed version of itself have been transmitted on two separate antennas.
The effect is to make the channel frequency selective and to allow for the use
of equalizers at the receiver. Another approach to implement transmitter
diversity is to
transmit different bit streams on the different antennas and use orthogonal
signals so that
the transmissions over the different antennas do not cause mutual
interference. This
scheme then becomes similar to the spectrally efficient schemes for frequency
and time
diversity that we have discussed above but also does not achieve the usual
benefits of
diversity.
If we consider the spectrally efficient transmitter antenna, frequency, and
time diversity schemes where the information bit stream is divided into sub-
streams and
where each sub-stream is transmitted over a different antenna, a different
frequency, or
a different time slot, then taken jointly the transmission of a set of symbols
can be viewed
as the transmission of a super symbol where in the case of BPSK this super-
symbol can
be represented by a vertex in an L-dimensional hyper-cube where L is the
number of
antennas, frequencies, or time slots. The reason for the poor performance of
this scheme
is that the hypercube signalling constellation is not fading-resistant. The
main reason for
the lack of fading-resistance is that for this constellation, compression of
the constellation
3
2186~~8
parallel to any of the coordinate axis (as a result of fading on one antenna,
one frequency,
or one time slot) results in points of the constellation coalescing thereby
resulting in errors
in the detected information bits. It would therefore be very advantageous to
devise
signalling constellations which achieve a high degree of spectral efficiency
and are fading
resistant. Such constellations would consist of points in an L-dimensional
vector space
where L is the number of antennas, carrier frequencies, or time slots with
relatively
independent fading such that strong fading in one coordinate (one antenna,
frequency, or
time slot) does not cause two of the constellation points to approach each
other.
Further, In present state of the art cellular systems the transmitter power is
adjusted once every preselected time frame - power control slot, or power
control sub-
group. For example, power is adjusted every 20 milli-second time frame in the
forward link
(base to mobile) of the IS-95 (CDMA) system or every 1.25 milli-second frame
(power
control group) in the reverse link of this system. In state of the art mobile
radio systems
power control is one of the key issues and future systems will have smaller
and smaller
power control frames. The goal of the power control algorithm is to maintain a
constant
signal to noise ratio at the receiver. However as a result of the required
system overhead
to transmit power control bits and the delay incurred in transmitting the
power control bits
there will always be (residual) variations in the received power level from
frame to frame
regardless of the rate of power control adjustments. As a result of the power
control, the
variation in received power level (i.e. power control error) will be
independent from frame-
to-frame. This variation in power level is similar to the variations that
arise due to fading
and as in the case of diversity discussed above a spectrally efficient coding
scheme
4
2186$8
(signal constellation) is required to mitigate the effect of these power
variations and
consequently reduce the probability of error in the channel.
SUMMARY OF THE INVENTION
The present invention provides a method for fading-resistant modulation for
wireless communication systems and addresses the problem of transmitting
information
with propagating signals through random or fading communication channels in a
spectrally efficient manner. The invention provides a method for the use of
transmitter
antenna, frequency, or time diversity, to attain a significant pertormance
increase over
systems not utilizing diversity and at the same time avoid the loss in
spectral efficiency that
is characteristic of typical transmitter diversity schemes, through the design
of
transmission signal space constellations which are resistant to fading in the
sense that the
fading of the total received signal is significantly improved in comparison to
similar
systems which do not use transmitter diversity, or use transmitter diversity
with the
standard L-dimensional hypercube as the signal constellation.
The technique uses transmitter diversity and can be used in systems that
employ either of the three types of transmitter diversity: antenna diversity,
frequency
diversity, or time diversity. These diversity techniques consist of the
simultaneous
transmission of data modulated signals over a set of L different antennas, L
different
carrier frequencies, or L different time slots, in a coordinated (jointly
encoded) manner.
The waveforms transmitted on the L different antennas are designed to be
orthogonal.
These waveforms are also inherently orthogonal in the case of the use of L
carrier
5
CA 02186688 2003-03-03
frequencies or L time slots.
The L difference antennas, L different carrier frequencies, or L different
time
slots, are chosen so that the signal fading is essentially independent among
them. Ideally
the signal fading over these different diversity paths would be independent.
As in typical
digital modulation schemes the transmitter transmits a sequence of symbols
(waveforms)
from some fixed symbol alphabet. Each waveform may be represented as a vector
in an
L-dimensional vector space. The signaling alphabet can be represented as a set
of vectors
which is typically called the signaling constellation. Each of these vectors
has L
components. In the current invention each of the L components of a
constellation vector
is transmitted in a different antenna (case of antenna diversity), a different
carrier
frequency (case of frequency diversity), or a different time slot or time
frame (case of time
diversity).
If the constellation is chosen as the set of vertices of a hyper-cube then
the transmitter diversity system just described would have the same
performance as a
system with the parameter L=1, i.e. no transmitter diversity. However in the
current
invention we describe methods to make the diversity system have a performance
that is
significantly superior to that of the non-diversity system by changing the
signaling
constellation to a new constellation which is obtained my maximizing a fading-
resistance measure. This measure has the characteristics that under the effect
of
Rayleigh fading the points in the signal constellation maintain a large
separation. In
particular, this fading resistance measure has the characteristics that the
resulting
derived constellation has the property that none of the points of the
constellation are
6
CA 02186688 2003-03-03
superimposed by collapsing the constellation parallel to any of the coordinate
axes.
In a preferred embodiment of the method the points of the signalling
constellation are obtained by starting with the L-dimensional hypercube and
transforming it by applying an orthogonal transformation (a set of rotations
and
reflections) in L-dimensional space. More generally, the fading resistant
constellation is
obtained from the L-dimensional hyper-cube constellation by representing the
hypercube constellation as a matrix, with rows equal to the signaling vectors
(vertices of
the hyper-cube), and multiplying this matrix by an LxL orthogonal matrix. A
procedure
to find good orthogonal transformation matrices is given and some good sets of
rotation
matrices (orthogonal transformation matrices) for the 2,3,4,5 dimensional
cases are
specified.
We also realize that there are other constellations, which are not
obtained from the L-dimensional hyper-cube by an orthogonal transformation,
which
would have a high degree of fading-resistance. One such example is the Kerpez
constellation which was designed for transmitting signals on wireline channels
with non-
symmetric noise characteristics.
In another embodiment of the method of the present invention the signals
transmitted in each antenna, carrier frequency, or time slot, which correspond
to
particular components of the signaling vectors, are differentially encoded: As
for the
previous case (the case of coherent detection) the use of the L-dimensional
hypercube
as a signaling constellation offers no advantage for the transmitter diversity
system over
the case L=1. However, a transformed constellation (different orthogonal
matrix
7
2i $ca~$$
than above) offers significant improvements. This differential scheme can also
be used
in systems with either of the three types of diversity: antenna, frequency, or
time.
In this disclosure we give the approach to find good orthogonal
transformations (generalized rotation matrices} by factoring the orthogonal
matrix into a
product of Givens matrices and doing a computer search for optimum rotation
angles.
Minor modifications to this approach and other approaches will produce other
rotation
matrices which have similar fading resistance and are significantly better
than the
standard hypercube constellation.
The method disclosed herein is advantageous in systems which suffer
from the so-called frequency non-selective fading (also called flat fading)
and where it
is difficult to implement receiver antenna diversity. In such a system it is
typically
desirable to implement transmitter antenna diversity since the receiver
terminal is small
and does not have the required dimensions to allow the installation of
multiple
antennas with sufficient inter-antenna spacing. The base station to mobile
terminal link
of a cellular system is a prime example of this application, especially in
cases where
the transmitted signal bandwidth is not significantly greater than the
coherence
bandwidth of the channel.
In a digital cellular system such as those standardized in IS-136, IS-95,
GSM, information bits are transmitted in blocks (slots, time frames}. In these
systems
the transmitter power is typically controlled (adjusted) so as to attempt to
maintain a
constant power (or signal to noise ratio) at the receiver. In the case of IS-
95 the power
is controlled (adjusted) once every 20 milli-second time frame in the forward
channel
8
218~~88
and once every 1.25 milli-second time frame in the reverse channel. However
when the
terminal is in motion even after the control of power there is still a
residual variation in
the power of the received signal within the power control time frame. This
variation is
similar to signal fading. The method disclosed herein can be used to encode
the
transmitted signal in such a way that different components of each signal
constellation
vector are transmitted in different time slots and hence undergo different
variations in
received power level. The rotated constellations presented (whether for the
case of
coherent detection or differential detection) will have significant
performance gains over
the standard hypercube constellations which in this case correspond to
transmitting all
the components of each constellation point sequentially in the same time
frame.
The present method provides for the joint encoding of signals transmitted
over a set of L-antennas using transformations of the basic hypercube signal
constellation. The invention contemplates joint encoding along time as well as
across
signals transmitted by different antennas. Such methods can be realized using
trellis
codes, convolutional codes, or block codes, where each code symbol is a point
in the
constellations disclosed herein and where the different components of each
constellation point (each trellis code symbol, or convolutional code symbol,
or block
code symbol) are transmitted in the different antennas (or different
frequencies, or
different time slots).
In another application a radio system may use L carrier frequencies that
have a sufficiently large frequency spacing so that the fading is independent
over the
different frequencies. The case L=2 would be sufficient to result in a
significant
9
2185688
improvement with our scheme. In this case we design signal constellations
which can
be represented as sets of points (vectors) in a 2-dimensional space (the
plane). In this
case the hypercube constellation is the well known QPSK constellation (except
that the
two axes correspond to two different carrier frequencies and not the two
different
phases - cos and sin) and applying the method of the present invention the
orthogonal
transformation corresponds to a rotation in the plane and provides an optimum
rotation
angle of approximately 31.7 degrees.
The present invention provides a method of fading-resistant modulation
for wireless communication systems using transmitter antenna diversity. The
method
comprises providing an L-dimensional signalling constellation comprising Q
points,
wherein each point represents a vector in a vector space, the vector space
comprising
L orthogonal coordinate axes, and the constellation points being such that any
two of
them are vectors which differ in a plurality of their components. The method
includes
transmitting each of said L components of said signalling constellation over
one of
either L different antennas, L different carrier frequencies and L different
time slots.
In another aspect the invention provides method of fading-resistant
modulation for wireless communication systems. The method comprises providing
an L-
dimensional signalling constellation comprising L orthogonal coordinate axes
and 2'
constellation points wherein each of said 2~ points represent a vector in a
vector space,
and the constellation points being such that any two of them are vectors which
differ in
a plurality of their components. The method includes transmitting each of said
L
components of said transformed signalling constellation over one of either L
different
CA 02186688 2003-03-03
antennas, L different carrier frequencies and L different time slots.
BRIEF DESCRIPTION OF THE DRAWINGS
The method of fading-resistant modulation for wireless communication
systems in accordance with the present invention will now be discussed, by way
of
example only, reference being had to the accompanying drawings, in which:
Figure 1 is a diagrammatic representation of a fonruard link channel model;
Figure 2 is a schematic block diagram of a receiver for receiving L
orthogonal transmissions;
Figure 3a is a prior art baseline constellation for L=2;
Figure 3b is a rotated constellation (L=2) with Q=4 points constructed
according to the method of the present invention providing increased fading
resistance
in a wireless communication system over the constellation of Figure 3a;
Figure 3c is a Kerpez constellation (L=2) which when used according to
the present invention provides increased fading resistance;
Figure 4a prior art baseline constellation for L=3;
Figure 4b is a rotated constellation (L=3) constructed according to the
present invention;
Figure 5 is a block diagram of a multi-frequency transmitter for a base
station;
Figure 6 is a block diagram of a multi-frequency receiver for receiving
11
- 2186688
transmissions from the transmitter of Figure 5;
Figure 7 illustrates a power control frame with 8 signalling intervals with
the signalling vector L=2;
Figure 8 is a block diagram of a differentially coherent receiver used in
the method of the present invention; and
Figure 9 is a block diagram of a differentially coherent multi-frequency
receiver with L demodulators used in the case where transmitter diversity is
implemented using multi-frequency transmission in which the mobile receiver
does not
track the carrier phases of the L transmissions.
DETAILED DESCRIPTION OF THE INVENTION
A) FADING-RESISTANT MODULATION
Channel Model 1:Multi-Antenna Transmitter Diversity
The forward link channel {base station to mobile terminal) model is
depicted in Figure 1. The base station has L transmitter antennas, the mobile
receiver
has a single antenna, and each of the L links has a different fading
amplitude. The
received signal is given by:
L
r(t)=~ ams~(t)cos(w~t+8~) + n(t), 0<_t<_T
r=Z
The signal from the transmitter's i~' antenna is a pulse amplitude modulated
(PAM)
signal and m~ is the signal amplitude, s;(t) is the pulse shape, a~ is the
fading
12
218bo88
amplitude of link !, and n(t)is a white Gaussian noise process with power
spectral
density No/2. It is assumed that the fading amplitude for a given link is
constant over
the signalling interval [O,Tj and that the receiver uses coherent detection.
The signals
s;(t), s.(t), i#j, are assumed to be orthogonal and all of the energy of
st(t), 1<_i<_L, is
contained in [O,Tj . As an example, the signals may be spread spectrum or code
division multiple access (CDMA) signals.
The optimum receiver consists of a bank of L correlators, as shown in
Figure 2. The output of the it'' correlator is:
T
y~ = 2 f r(t)sJ(t)cos(c~~t+81)dt
0
= almtEs + rh, 1 '-isL
where ES= js;2(t)dt is the pulse energy and rli = 2on(t)s;(t)cos(c~~t+6;)dt, 1
<_i<_L, are
uncorrelated zero-mean Gaussian random variables with variance NoEs. The
received
vector y=(yl,y2,...,yL) is fed into a decision device which estimates the
transmitted
vector m=(ml,m2,...,mL). It is assumed that the receiver can estimate the
fading
amplitudes a;. The receiver finds the L-dimensional constellation point in C,
with
coordinates suitably amplified, that has the closest Euclidean distance to the
received
vector y. That is, the receiver picks the symbol m=(ml,m2,...,mL) E C that
minimizes
L
E(ytlEs-ami)2. A symbol detection error occurs when mom.
r=i
It is noted that the transmission bit rate can be increased with no loss in
performance and without using more bandwidth by transmitting two carriers that
are in
phase-quadrature from each antenna. The received signal becomes:
13
21 ~b6
L
r(t)=~ a;(m;~sJ(t)cos(c~~t+6;)+m;ss;(t)sin(c~~t+6J)) + n(t), 0<_t<_T, ~l. 3~
=i
where m;~ and m;S are the signal levels corresponding to the two orthogonal
carriers
transmitted on the i~" antenna. Orthogonality among s;(t), 1<_i<_L, ensures
that the ZL
signals do not interfere with one another. Similarly, QPSK has the same
performance
as BPSK and the bandwidth efficiency is twice as high.
The communication links shown in Figure 1 are not necessarily
line-of-sight. In a multipath environment, where there is no line-of-sight
component, a
Rayleigh fading model is normally assumed. If the channel delay spread is
small
relative to the symbol period, orthogonality between the L links is still
possible. The
fading amplitudes a; are modelled as independent and identically distributed
Rayleigh
random variables with probability density function
fa(a) = tae -°'2, a>_0. CJ. y~
The assumption of independent fading is valid if the transmitter antennas are
spaced
sufficiently far apart, which is relatively easy to do when the transmitter is
the base
station.
The fading-resistant transmission schemes discussed hereinafter forming
the present invention assume that the receiver is capable of estimating the
fading
amplitude of each link. This is possible if the fading amplitudes vary slowly
over time. If
the fading amplitudes vary quickly over time, the performance of the receiver
will
14
_ 218688
degrade due to estimation errors.
Baseline Scheme: Independent BPSK Signals
The baseline scheme consists of a transmitter with L antennas which
sends either a +1 or -1 bit on each antenna, independently of the rest, and
the output of
the i~' correlator is given by (1.2) with m;E{1,-1}. This corresponds to
sending
independent BPSK signals on each antenna. There is an L-fold expansion in
bandwidth
over the L=1 case in order to have L orthogonal transmissions but the overall
data rate
also increases by a factor of L so that there is no bandwidth penalty.
For optimal detection, the correlator output y~ is fed into a threshold
device which outputs a 1 if the input is positive, and a -1 otherwise. The
probability of
bit error is (e.g. see J. Proakis, Digital Communications, 2nd edition, McGraw-
Hill Book
Company, New York, 1989., p. 717)
Eb/No ,
P(error) _ _ 1 _ ~.5
2 EblNo + 1
where ES = a2E~/2 = E~/2 is the average received bit energy. Eq. {1.5)
applies to each of the L links, and so the overall bit error rate is also
given by (1.5). For
this scheme the overall bit error rate is independent of L and there is no
advantage
over single-antenna BPSK.
2i8~E88
Construction of Fading-Resistant Constellations
The ideal figure of merit in the design of signaling constellations is that of
the probability of symbol error. However, it is an untractable problem in
mathematics to
construct signaling constellations that minimize the probability of error in
Rayleigh
fading channels. As such we will use a sub-optimal figure of merit. Other
similar figures
of merit will yield good signaling constellations. The fundamental property of
a good
signaling constellation is that the encoding of the information bits to the
transmitted
waveforms should be such that a given information bit has an effect on the
signals on a
multiple number of coordinates of the constellation points. In this respect
the L-
dimensional hypercube, with the edges of the cube being aligned with the
coordinate
axes, is the worst constellation since in this case each information bit
affects the signal
in only one coordinate, and with fading in that coordinate the bit is lost. In
other words
any two points of the signaling constellation should have a large number of
components which differ significantly.
The following quantity, hereinafter the constellation figure of merit for the
Rayleigh fading channel, gives an indication of the performance of a signal
constellation at high SNR,
L
CFM~Y~eigh(C) = min II (mt-m;)2/E ~. (o
m,mEC i=1
mom mjxm~
where E is the average symbol energy of the constellation C. Note that (1.6)
is
scale-invariant, that is, CFMRay~e~~,(aC) = CFMRay~ei~(C), where a is a
scalar. We
16
CA 02186688 2003-03-03
describe a method for constructing L-dimensional fading-resistant
constellations which
have a large CFMRa~y~g". We are interested only in constellations where m;~m~,
1_<i<-L.
Given an L-dimensional constellation of Q points, there is applied a
transformation to the constellation which preserves the Euclidean distances
between
points but improves the constellation's resistance to fading. We impose the
restriction
that the transformation preserve Euclidean distances and norms because we do
not
want to degrade the performance of the constellation in the AWGN channel. Such
transformations are called isometries.
The original constellation is represented as a ~C~XL matrix C, where each
row of the matrix corresponds to a point in the L-dimensional constellation.
One
example of a distance-preserving transformation is to multiply this matrix by
an
orthogonal LXL matrix A. The optimal matrix A maximizes the fading-resistance
of the
transformed constellation CA, that is, it maximizes CFMRay~e~~,(CA).
In Appendix A it is shown how an LXL orthogonal matrix A can be written
as the product of (2) rotation matrices and a reflection matrix. From (A.5),
we see that
multiplication of the constellation matrix C by an arbitrary orthogonal matrix
A has the
following geometrical interpretation. The constellation is rotated with
respect to the
(i,j)-plane by an amount 6~~, 1<_i<_L-I, i+1_<j<_L, and there are (2) such
rotations. Then
the constellation is reflected in the i t" axis, where the matrix 1 has (i,i)
entry equal to -
1, and the number of such reflections is equal to the number of -1 elements on
the main
diagonal of I. Writing A=QI, where Q is the product of (2) rotation matrices
in (A.5),
we see that
17
CFM~Y~e~~(CA) = CFMRayleigh(CQII = CFMRayleigh(CQ)
where the second identity in (1.7) follows because the matrix CQI is the
matrix CQ
with several of its columns negated, and negating the columns of a
constellation matrix
does not affect the CFM~ylel~, of the constellation. Rather than look for an
optimal
constellation CA it is sufficient to look for an optimal constellation CQ.
The present method of obtaining an optimal constellation C°Pt = CQ,
that
is, one with maximum CFMRayei~(CQ), given a starting constellation C,
comprises
varying f 2) rotation angles according to a numerical optimization or search
algorithm.
The constellation C is rotated with respect to the (i,j) plane, 1<_i<_L-1,
i+1<-j<_L. Note
that Q does not need to be computed explicitly. There are ~2~ degrees of
freedom and
for L=2,3 and for a large angle discretization interval (for example,
1° ) the search for
the optimal angles can be made exhaustively but for L>_4 and for reasonably
small
discretization intervals {for example, less than 5°) the exhaustive
search method takes
too long. For these larger values of L, we pick at random many different
starting
rotation vectors and use a gradient descent method each time to converge to a
(possibly local) maximum; then a possibly sub-optimal rotation vector is
obtained
corresponding to the maximum of all these trials.
In general, we can start with constellations drawn from L-dimensional
packings. For a given number of constellation points, points are drawn from
the
minimum-energy shells of these packings. These constellations are then rotated
in
L-space so as to maximize CFM~yIe~~. For example, in two dimensions two
possible
18
2186688
packings are ~ and the hexagonal lattice. In three dimensions, possible
packings are
the hexagonal close packing, tetrahedral packing, face centered cubic lattice,
body
centered cubic lattice, and the Z3 lattice. These lattices are defined, for
example, in J.
H. Conway, N. J. A. Sloane, Sphere Packings, Lattices and Groups, Springer-
Verlag,
New York, 1993. Denser packings are preferred because large constellations
drawn
from these packings have better performance in the additive white Gaussian
noise
channel.
For the same bit rate and AWGN channel performance as the baseline
scheme, we start off with the L-cube, which is the constellation for the
baseline
scheme. (This also corresponds to a single energy shell of the ZL lattice.)
For
example, when L=2, the baseline constellation matrix is
1 1
1 -1 C
-1 1
-1 -1
and the four constellation points are shown in Figure 3a. In this case
maximization of
CFMRay~eigh is done by varying only one rotation angle. The optimal angle of
rotation for
this constellation can be found using an exhaustive search to be
6°pt=31.7°, assuming a
discretization interval of 0.1°. This optimal angle can be derived
analytically
as 6°Pt = Stan-'(2) but the derivation is omitted for the sake of
brevity. The optimally
rotated constellation is
19
2~ ~~~~,
-0.325-1.376
-1.3760.325
1.376 -0.325
0.325 1.376
The baseline constellation and the rotated constellation are shown in Figures
3a and
3b. Each row in the constellation matrix corresponds to a point (ml,m2). The
Kerpez
constellation shown in Figure 3c for comparison will be discussed below.
When L=3 the baseline constellation C consists of the vertices of a
three-dimensional cube and optimization is done over three rotation angles.
The
optimal rotation vector can be found using an exhaustive search to be
6~ _ [e12,e13,e23~ _ [24°,36°,66°], using a
discretization interval of 1°. Both the
baseline constellation and the optimally rotated constellation are shown
below,
1 1 1 0.177 0.474 -1.656
1 1 -1 -0.997 -1.003 -0.998
1 -1 -0.480 1.654 -0.181
1
1 -1 -1.655 0
-1 176 0
476
Cpt = .
.
-1 1 1.655 -0.176 -0.476
1
-1 1 0.480 -1.654 0.181
-1
-1 -1 0.997 1.003 0.998
1
-1 -1 -0.177 -0.474 1.656
-1
These constellations are shown in Figures 4a and 4b.
For L>_4, an exhaustive search over the ~2~ rotation angles in order to
218~~~~
maximize CFMRay~ei~ for the L-cube proved to be too time consuming. For these
constellations, many rotation vectors were picked at random, and a gradient
based
approach was used to vary the rotation angles so as to converge to a local
maximum.
For L=4 there are six degrees of freedom and the optimal rotation vector found
was
8~ _ [812,813,e14~~23~e24~834] _
[206°,15°,306°,42°,213°,31°] . For
L=5 there are ten
degrees of freedom and the optimal rotation vector found was
eopt - [~12~813~e14~e15~e23~e24~825~834~e35~e45]
_
[294°,349°,18°,340°,103°,184°,114.deg
ree.,275°,212°,25°]
Kerpez Constellations
In K. J. Kerpez, "Constellations for good diversity performance", IEEE
Trans. Commun., vol. 41, pp. 1412-1421, Sept. 1993, L-dimensional
constellations
were proposed for L-link wireline nonfading channels where the links have
different
noise powers. These constellations were derived heuristically and we note that
they
should also perform well in the case we are considering where the noise powers
are
equal but the fading amplitudes are different.
For these constellations, there are ML constellation points (ml,m2,...,mL) .
Specification of il E { 1,2,...,ML} uniquely identifies the L-dimensional
symbol, which
has j~'coordinate given by
m. _ -2 J + ML + 1, ~ E { 1,2,...,ML]
where ~, 2sj<-L, is related to il, by
21
mod ML+ML ~+1 + I
Mi_i
We consider only the case M=2 so as to have the same bit rate as the baseline
scheme. For example, when L=2, the Kerpez constellation is
3 1
-1 3
3)
-3 -1
1 -3
This constellation, normalized by ~ so that the symbol energy is the same as
that of
the baseline two-dimensional constellation, is shown in Figure 3. As another
example,
when L=3 , the set of constellation points is shown in the first column in
Table 1.1.
Note that, except for the L=2 case, the Kerpez constellations are not rotated
versions
of the baseline L-cube constellations. In fact, the points in a Kerpez
constellation with
L>2 do not all have the same energy.
From K. J. Kerpez, "Constellations For Good Diversity Performance",
IEEE Trans. Commun., Vol. 41, pp. 1412-1421, Sept. 1993., the average symbol
energy of the Kerpez constellation is
E = 3 (2~ - 1)
and the minimum squared distance between constellation points is dm;" = 4(2'x-
1)/3.
22
The constellation figure of merit for the additive white Gaussian noise
channel is thus
4
CFM~YIey = E
For the baseline constellation, dn;" = 4and the constellation symbol energy is
E=L so
that CFMAwGrrfor the baseline constellation is also given by (1.15). Thus, for
the AWGN
channel the probability of symbol error of both the Kerpez and baseline
schemes is the
same at high signal-to-noise ratio. However, unlike the baseline scheme, the
Kerpez
constellation is resistant to fading because no two L-dimensional vectors have
the
same j~' component, 1 <-j<-L. Even if all but one of the L components have a
fading
amplitude of zero, the receiver will be able to determine which of the 2L
vectors was
sent as long as the signal energy in the non-faded component is strong enough.
The output of the ir''correlator is given by (1.2) where m;, 1 <_i<_L, is
given
by (1.11 ). The total transmitter energy in the signalling interval [O,Tj is,
from (1.14),
LESm;2/2 = L2ES(2~-1)l6 and L bits are transmitted during this interval. In
order to
compare the different schemes on the basis of the same energy per bit, we
assume that
ES = 6E6/(L(2~-1))~
As in the previous section, the receiver requires knowledge of the fading
amplitudes a~, 1 <-i<-L. The receiver decides which L-dimensional symbol in C
was
transmitted using the same decision rule as in the previous section. The
probability of
bit error depends on how bit patterns of length L are assigned to
constellation points.
Given an L-dimensional constellation, we may wish to assign bit patterns to
23
- ~ ~ ~~~8:
constellation points such that points separated by d differ in only one bit.
This is
because in an AWGN channel, symbol detection errors are more likely to be
associated with nearest-neighbour symbol pairs than with symbol pairs that are
separated by a larger distance. For the Kerpez constellation it turns out that
there is a
simple method for achieving this as follows.
Method for bit pattern assignment : There are 26 constellation points. For a
given
constellation point with indexes (il,i2,...,iG), il E {1,2,3,...,26},we let
G
il = 1 + E2n-'an,where an E {0,1}. We compute iv using (1.12), for 2sv<_L. If
we
n=1
assign the bit pattern (al,a2,...,aG)to the constellation point (il,i2,...,iG)
then bit patterns
that differ in only one location correspond to constellation points separated
by d . The
proof is given in Appendix B.
As an example, consider the case L=3. In Table 1.1 the mapping between
constellation points and bit patterns is given. Note that il is just the
decimal
representation of the bit pattern alaZa3 plus one. For this constellation d~ =
84 and all
pairs of constellation points separated by this squared distance (there are
twelve of
these pairs) differ in only one bit.
(ZZZI,YlZ2,1713)(I1~12~13)ala2a3
(7,1,5) (1,4,2) 000
(5,-7,1) (2,8,4) 001
(3,3,-3) (3,3,6) 010
(1,-5,-7) (4,7,8) 011
(-1,5,7) (5,2,1 100
)
(-3,-3,3) (6,6,3) 101
24
218~~8$
(-5,7,-1) (7,1,5) 110
(-7,-1,-5) (8,5,7) 111
Table 1.1: Mapping of bit patterns to constellation points fort=3 Kerpez
constellation.
Channel Model 2: Multi-frequency Transmitter Diversity
L orthogonal links can be achieved using a single antenna at the
transmitter and L carrier frequencies. If these carriers are separated far
apart, the links
will be orthogonal and the fading associated with each carrier will be
independent. It
may be easier to ensure orthogonality among links when there is delay spread
by using
a multi-frequency rather than a multi-antenna approach.
Each base station transmits to a mobile using L carriers and a single
antenna. (Cochannel base stations can use the same set of carrier frequencies
(~1~~2~"'~~L)' ) The baseband signal transmitted from the j~' base station at
carrier
frequency cal, 1 <-l<-L, is
sl (t) _ ~ ml~~h(t-iT).
r
h(t) is a band-limited pulse and m~~ is the symbol transmitted during the i~'
signalling
interval [(i-1)T, iTj. For example, in the baseline BPSK scheme, mi ~ E {-
1,1}. The
block diagram for the transmitter is shown in Figure 5.
The receiver has L demodulators and its block diagram is shown in Figure
6. It is assumed that the carrier frequencies are spaced far apart and that
signal
components with center frequencies ~c~~r-c~t2l, ill#~~z, resulting from the
demodulation
218~~~8
operations, are filtered out by the lowpass filtering effect of h(t). The
output of the
matched filter in the l°' branch is sampled at t=kT.
The decision device in Figure 6 makes a decision on the received vector
y = ~l,k~"'~L,kO The decision device is simply a minimum distance decoder
which uses
estimates of the fading amplitudes. When the noise is Gaussian, this decision
device is
optimal. In the case we are considering, this detection strategy is sub-
optimal. We
assume that the mobile receiver correctly estimates the vector of fading
amplitudes a = (ai°),...,aL°)). The transmitted sequence of
interest is
m = (mik),...,mLk)) E C, where C is an L-dimensional constellation. The
decision device
outputs the vector m = (ml,m2,...,mL) E C such that
L
~,, _ C°) ~ 2
~hk aI m1) ,
1=1
is minimized and a symbol decoding error occurs if m#m.
Fading-resistant cellular system
For the scheme we are proposing, mjk), 1 sl<_L, are coordinated and the
receiver makes a decision on the entire received vector y = (v,,k,"',yL,kO In
order for the
fading-resistant modulation scheme to have the same bandwidth efficiency as
uncoded
BPSK, we assume that C has 2L points, so that L bits are transmitted for every
vector
of L symbols. We consider two different fading-resistant schemes. The first
scheme
uses rotated baseline constellations and the second scheme uses Kerpez
constellations. The overall bandwidth occupied by the multi-frequency signal
is 8,
26
2~8~~~~
where 8 is the bandwidth of the transmitted signal when only one carrier is
used and
for L>1 carriers, the bandwidth of a signal at a particular carrier frequency
is BlL.
Thus, the overall bandwidth and bit rate remain unchanged for different L.
There is also
no loss in bandwidth efficiency by having the carriers spaced far apart
because the
spectrum between the carriers is used by the other users.
Channel Model 3: Time Interleaving and Power Control
Diversity can be achieved using time interleaving and power control. In
this case the transmitter uses a single antenna and a single carrier
frequency. During
each signalling interval, the transmitter transmits a coordinate of an L
vector. A vector
of L coordinates is transmitted by transmitting each coordinate in a separate
power
control time frame. The transmitter power remains constant for 8 signalling
intervals
(the duration of a power control time frame), and depending on the power
received by
the mobile receiver, the transmitter may either increase or decrease power
during the
next power control frame. The coordinates of an L vector are each transmitted
in a
different power control frame, and so the fading amplitudes associated with
each
coordinate will be independent, so that the fading-resistant scheme will
perform well
because the likelihood that all L coordinates are received with low energy is
very
unlikely. The larger the value of 8 the simpler the implementation, however,
the power
control scheme will not compensate for shorter durations of fluctuations in
received
power. Figure 7 shows an example. In this case the vector has length L=2 and
the two
coordinates are transmitted in two separate power control frames.
B) DIFFERENTIALLY COHERENT FADING-RESISTANT MODULATION
27
CA 02186688 2003-11-13
Part B describes a bandwidth-efficient fading-resistant transmission
process and several applications thereof. Differential encoding and detection
is used in
this embodiment of the process so that the receiver does not have to track the
carrier
phases of the L transmissions. Further, fading-resistant constellations are
generated by
optimizing a distance measure for the Rayleigh fading channel. Because this
figure of
merit is different than that used in Part A, the resulting optimally rotated
constellations
are also different than those described in Part A. This fading-resistant
transmission
scheme is described by the inventors in V. M. DaSilva, E. S. Sousa,
"Differentially
Coherent Fading-Resistant Transmission From Several Antennas", Proc. 46th IEEE
Vehicular Technology Conference, VTC '96, Atlanta, USA, April 28 -May 1, 1996.
Channel Model 1: Multi-antenna Transmitter Diversity
The base station has L transmitter antennas, the mobile receiver has a
single antenna, and each of the L links has a different fading amplitude. The
received
signal during the signalling interval [kT, (k+1)Tj is
L
r(t) _ ~ a x;>,~s;(t-kTjcos{c~~t+8;) + n(t).
r=i
s;(t) is the pulse shape, a; is the fading amplitude, 81 is the carrier phase,
and x;,k is
the signal level corresponding to the it'' link, respectively. n(t) is white
Gaussian noise
with power spectral density No/2. It is assumed that the fading amplitude and
carrier
phase for a given link are relatively constant over several consecutive
signalling
28
21~~~~
intervals, which is why the dependence of a~(t) and 6;(t) in (2.1 ) on t is
not explicit, and
that the receiver does not use local carriers that are in phase coherence with
the
received signals. The signals st(t), s(t), i#j, are assumed to be orthogonal
and all of
the energy of s;(t), 1 <_i<_L, is contained in [O,Tj .
It is assumed that a; are independent and identically distributed Rayleigh
random variables with probability density function given by (1.4). The fading-
resistant
transmission schemes discussed in this chapter assume that the receiver is
capable of
estimating the fading amplitude of each link.
Baseline Scheme: Differential BPSK
Given L antennas, the transmitter can send either a +1 or -1 bit on each
antenna independently of the rest and the received signal is given by (2.1 )
with
x~,k E {1,-1}. There is an L-fold expansion in bandwidth over the L=1 case in
order to
have L orthogonal transmissions but the overall data rate also increases by a
factor of
L so that there is no bandwidth penalty.
Assuming an optimum receiver for binary differential phase-shift keying,
the conditional probability of bit error for link ! is P(error~ai) _ ~e
azEb~N°,where
T
Eb = 1s;2(t)dtl2 is the bit energy in each link (e.g. see R. E. Ziemer, W. H.
Tranter,
0
Principles of Communications: Systems, Modulation, and Noise, Third edition,
Houghton Mifflin Company, Boston, 1990, p. 485). Averaging over the fading
amplitude, the probability of bit error for each link is (e.g. see J. Proakis,
Digital
Communications, 2nd edition, McGraw-Hill Book Company, New York, 1989., p.
717)
29
2~8~688
P(error) = 1 2. Z >
2(EblNo + 1 ) -
Equation (2.2) applies to each of the L links, and so the overall bit error
rate is also
given by (2.2). For this scheme the overall bit error rate is independent of L
and there is
no advantage in using more than one antenna.
Receiver for fading-resistant transmission
Figure 8 shows a differentially coherent receiver. The noisy decision
variables used by the decision device are given by
c c s s
X ~~k-1 + Xi.k'Yi.k-~
yi.k =
c 2 s 2
(Xi,k-1) + (X,k-1)
where
X,~ = a xi~cos(6i)ES + rl~
X.S - -ax. sin(6.)E + .~S
t.k ~ ~,k ~ s i,k
are the in-phase and quadrature correlator outputs for link I and
(k+1)T
~1 t k = 2 f n(t)si(t-kT) cos(c~~t)dt
kT
(k+1)T
r~~ k = 2 f n(t)si(t-k~ sin(c~~t)dt
kT
are zero-mean Gaussian random variables with variance c2 = NoEs, where
218b~88
1
T
ES = fs;2(t~t, 1<_i<_L, is the pulse energy.
0
The vector of variables (yl,ky2,kwWL,k) is used by the decision device to
decide which L-dimensional information symbol mk = (ml,k,m2,~,...,mL,x) E C
was
transmitted, where C is the constellation of information symbols. The L
simultaneous
transmissions can be viewed jointly as an L-dimensional vector
(xl~,x2~,...,xL~) but the
information symbol transmitted during the signalling interval [kT,(k+1)Tj is
mk E C.
The transmitter transmits the information symbol (ml~,...,mL~) by transmitting
the signal
level x;,k = m;~sgn(x;,k_1) on link l, where sgn(x) = 1 if x>_0 and -1
otherwise. Assuming
that each symbol in C is transmitted equally likely, the bit rate is log2~C~
bits per
symbol, where ~C~ is the number of symbols in the constellation C.
With no loss of generality assume ES=1. At time t=(k+1)T the decision
device outputs the symbol m = (mi,m2,...,mL) E C which minimizes the quantity
L _ 2
(yt~ a m~)
r=i (amly. _ )2 + 1
i i t,k 1
and a decoding error occurs whenever m~mk.
The reason for setting x;~ = m;~sgn(x;,k_1)can be seen by assuming a
noiseless channel. With n(t)=0, we have
y;~ = ax;,ksgn(x;~_1) = am;,ksgn(x;,k_1)sgn(x;,k_1) = am;,kand the decision
device will
correctly determine which information symbol (ml~,m2,k,...,mL~) E C was sent.
Construction Of Fading-Resistant Constellations
The following parameter, which we call the constellation figure of merit for
31
21~~~8
the Rayleigh fading channel, gives an indication of the performance of a
signal
constellation at high SNR,
L 2
CFM~yieign(~ = min lI 1 + y mi - nr lE
m,rnnwnC t 1 (fYl~Wt)2+1 (YI~Wi)2+1
where E is the average symbol energy of the constellation C. At large enough
SNR we
can use the following figure of merit to compare constellations with the same
minimum
Hamming distance d,
L 2
CFMRaYleigh(~ = min II 1 + y mr - nr /E
m,n,wsC r=i (m./w.)2+1 (n./w.)2+1
m*n mr*nr r r r r
Eq. (2.8) looks similar to the distance measure that needs to be maximized in
Part A
above, where coherent detection is assumed. The difference in these two
measures
results from the need to take the previous codeword w into account, for the
differentially
coherent scheme assumed here.
The design problem is to find constellations C which have a large
CFM~YIei~(C~. We are interested only in constellations where m;#n;, 1_<i<_L.
We now
describe a method for searching for L-dimensional fading-resistant
constellations which
have a large CFMRayteigh~ For the baseline scheme, L bits are transmitted
during each
signalling interval and we can view the resulting signal as a vertex of an L-
dimensional
cube. Computation of CFMRaYlel~n(C~ using (2.7) for this L-dimensional cube C
suggests
that the bit error rate for this constellation varies only inversely with SNR,
which agrees
32
2 i ~~~~:8
with (2.2). We can increase CFMRay~ei~n and thus improve the performance of
this
constellation by rotating it in L dimensions.
Applying a transformation to the constellation which preserves the
Euclidean norms of the L-dimensional points, such as a rotation in L-
dimensions,
preserves the total energy of the constellation. Since constellations can only
be
compared fairly when their energies are the same, the transformed
constellation's
CFM~y~e~~ can thus be compared with that of the original constellation without
having
to renormalize the transformed constellation.
As described in Part A above, one starts off with the L-cube. For example,
when L=2, the starting constellation is given by (1.8). The angle of rotation
which
maximizes (2.8) was found to be approximately 6oPt=18.6°, and the
resulting rotated
constellation is
-0.63-1.27
-1.270.63
-
1.27 -0.63
0.63 1.27
Maximizing (2.7) for several values of the parameter yyielded similar optimum
rotation
angles. These resulting rotated constellations were compared using simulations
to
determine the probability of bit error and they were observed to have similar
performance.
When L=3 the starting constellation consists of the vertices of a
three-dimensional cube and optimization is done over three rotation angles.
Eq. (2.8)
33
was maximized over three rotation angles (using a discretization interval of
1°for each
angle), as well as (2.7) for several values of y. Constellations which
maximize (2.7) for
different values of y perform differently over different ranges of SNR.
Simulations
showed that the best constellation among these corresponded to the rotation
vector
8~,t = [612,613,623 - L76°,18°,14°], and this
constellation has good performance over a
moderately large range of SNR. It was also observed that the optimal rotation
vector
which maximizes (2.7) is not very sensitive to the parameter y in that the
same optimal
rotation vector maximized (2.7) over large ranges of y.
For L>_4,an exhaustive search over the (21 rotation angles in order to
maximize CFMRayleigh for the L-cube proved to be too time consuming. For these
constellations, many rotation vectors were picked at random, and a gradient
based
approach was used to vary the rotation angles so as to converge to a local
maximum.
For L=4there are six degrees of freedom, assuming the parameter y is given.
Several
values of y were assumed, and the performance of constellations that maximized
(2.7)
for these different values of y were compared. Simulations showed that the
rotation
vector 8°pt = ~812~813~e14~e23~e24~e34~ -
~2g°~~4°,15°,165°,286°,28°] yielded
a constellation
with good performance over a moderately large range of SNR.
Channel Model 2: Multi-frequency Transmitter Diversity
Transmitter diversity is implemented using multi-frequency transmission
and the mobile receiver does not track the carrier phases of the L
transmissions. The
differentially coherent receiver has L demodulators and its block diagram is
shown in
Figure 9. It is assumed that the carrier frequencies are spaced far apart and
that signal
34
218b~88
components with center frequencies ~wl~-w12~, wl~#wlz, resulting from the
demodulation
operations, are filtered out by the lowpass filtering effect of h(t). The
outputs of the
matched filters in each branch are sampled at t=kT.
Fading-Resistant Cellular System
For the fading-resistant cellular system, x ~~, 1 <_l<_L, are coordinated and
the decision device in Figure 9 makes a decision on the entire received vector
y = ~l,k~"'~L,kO The noisy decision variables used by the decision device are
computed as
XI,Tf'l,k-1 + Xl,k'Yl,k-1
yl,k = , 1 <_l<_L. ~ , I (7)
(Xl,k-1)2 + (Xl,k-1)2
We assume that the mobile receiver correctly estimates the vector of fading
amplitudes
a = (ai°~,...,aL°~). The transmitted vector of interest is m =
(mi k,...,mLk) E C, where C is
an L-dimensional constellation. The decision device outputs the symbol
m = (ml,m2,...,mL) E C which minimizes the quantity
V'r>k - a m~)z
~z. y
=i (am,Jy;,k-1) + 1
and a decoding error occurs whenever m#m.
Channel Model 3: Time Interleaving and Power Control
Diversity can be achieved using time interleaving and power control. In
this case the transmitter uses a single antenna and a single carrier
frequency. During
CA 02186688 2003-12-23
each signalling interval, the transmitter transmits a coordinate of an L
vector. A vector
of L coordinates is transmitted by transmitting each coordinate in a separate
power
control time frame. The transmitter power remains constant for B signalling
intervals
(the duration of a power control time frame), and depending on the power
received by
the mobile receiver, the transmitter may either increase or decrease power
during the
next power control frame. The coordinates of an L vector are each transmitted
in a
different power control frame, and so the fading amplitudes associated with
each
coordinate will be independent, so that the fading-resistant scheme will
perform well.
The larger the value of B the simpler the implementation, however, the power
control
scheme will not compensate for shorter durations of fluctuations in received
power.
Figure 7 shows an example.
Further details of the fading resistant method are disclosed in V. M.
DaSilva, E. S. Sousa, "Fading-resistant transmission from several antennas",
Sixth
International Symposium on Personal, Indoor and Mobile Radio Communications,
PIMRC '95 , Toronto, Canada, September 27-29, 1995, pp. 1218--1222; and Victor
M.
DaSilva, Ph.D. Thesis, "Transmitter Diversity And Fading-Resistant Modulation
For
Wireless Communication Systems", Department of Electrical And Computer
Engineering, University of Toronto, February, 1996 .
It will be appreciated that the method of fading resistant modulation for
wireless communication systems disclosed herein has been described and
illustrated
by way of example only and those skilled in the art will understand that
numerous
36
2~~~~8$
variations of the method may be made without departing from the scope of the
invention.
37
- 2i8~~88
APPENDIX A
We show how an LXL orthogonal matrix A can be written as the product
of (z) rotation matrices and a reflection matrix.
Theorem: (QR factorization)
Given an nXm matrix A with n>_m, there is an nxm matrix Q with orthonormal
columns
and an upper triangular mXm matrix R such that A=QR. If m=n, Q is orthogonal.
(For
example, see R. A. Horn, C. R. Johnson, Matrix Analysis, Cambridge University
Press,
1985., p. 112).
There are several algorithms that can be used to compute Q and R. For
example, methods based on Householder and Givens transformations can be used.
The method based on Givens transformations is of particular usefulness in the
present
invention. If A is an nXn matrix, then A = QR -. QTA = R. The QR factorization
method based on Givens transformations gives us a method for writing QT as the
product of n(n-1)l2 Givens matrices. The method is given below , see G. H.
Golub, C.
F. Van Loan, Matrix Computations, 2nd ed., The John Hopkins University Press,
1989.,
p. 214].
%QR factorization algorithm for an nxn matrix A.
%compute QT, the transpose of Q, so that QT*A is upper triangular matrix R
QT l nxn
Atemp=A
for col = 1: n-1
for row=co! + 1:n,
[c,s] = givens(Atemp(col,con, Atemp(row,con )
%the next step zeros the (row,con element in Atemp
QT--G(col,row,c,s)T*QT
Atemp=G(col, row, c, s)T *Atemp
end
38
_ z ~ ~ ~~88
end
where
function [c,s] = givens(a,b)
%compute c and s so that [c s; -s c]~T[ a; b]=[r, 0], where
r is any real number
if $b=0 $
c= 1; s=0
else
s = b/(a2 + b2)~; c = -aslb
end
and
1
c ... s
G(i,k,c,s) _ ~
-s ... c
1
is an nxn matrix called the Givens (or Jacobi) matrix. It is possible to solve
for 8 such
that c=cosB, s=sing. The matrix consists of 1's on the main diagonal except
for the two
elements c in rows (and columns) l and k. All off-diagonal elements are zero
except
the two elements s and -s. Post-multiplication of a vector by G rotates the
vector
counter-clockwise by 8 degrees with respect to the (i,k) plane. To simplify
notation later
on, we define G(i,k,~ = G(i,k,c,s).
Proposition 1
If an nxn matrix A is orthogonal, then a QR factorization algorithm yields
Q=A1 where 1
39
- 2~8sESs
denotes a matrix in which each main diagonal element is either 1 or -1 and all
off-diagonal elements are zero.
Proof
QT is orthogonal because Q is orthogonal. If A is orthogonal then QTA=R is
also
orthogonal since the product of two orthogonal matrices is an orthogonal
matrix. Since
R is an upper triangular orthogonal matrix, each main diagonal element must be
either
1 or -1 and all off-diagonal elements must be zero. We have A=Ql ~ Q=AI' = A1~
=AI
Proposition 2
Any orthogonal nxn matrix A can be written as the product of n(n-1 )I2 nxn
Givens
matrices and an nxn I matrix.
Proof
The proof follows directly from the proof of the previous proposition. Given
an arbitrary
orthogonal nxn matrix A we have a method for constructing Q, the product of
n(n-1 )I2
Givens matrices, such that A=Ql. Note that the identity matrix is a Givens
matrix as well
as an I matrix.
For example, all 2x2 orthogonal matrices have the form
cos8 sin6
A =
-sin8 cos8
or
218b~~3
core sin6
A =
sin8 -cosh
This is a well known fact (for example, see W. K. Nicholson, Elementary Linear
Algebra with Applications, PWS-KENT Publishing Co., Boston, 1986, p. 282). The
first
form corresponds to G(1,2, ~I2,~ and the second form corresponds to G(1,2, ~(-
12,x).
Proposition 2, together with the QR factorization method using Givens
transformations,
implies that all 3x3 orthogonal matrices have the form
A = G(1,2,612)G(1,3,813)G(2,3,623)l3Xs
cos612 sin812 0 cos813 0 sin613 1 0 0 ~1 0 0
- -sin612 cos812 0 0 1 0 0 cos623 sin623 0 tl 0
0 0 1 -sin813 0 cos613 0 -sin623 cos623 0 0 ~1
In general, any LxL orthogonal matrix A can be factored into L(L-1 )12 (2,
rotation
matrices and an I matrix as follow 1 /s
= C ~ G(l~~e;,>) ~ ILxL
lSisL-1
i+lSjSL
for suitable 8...
41
218~~~~
Appendix B
We prove that the method given in Section 1.1.3 results in the assignment of
bit patterns
that differ in only one location to points in the Kerpez constellation that
are separated by
dmin.
Assume that the bit patterns corresponding to the distinct constellation
points (il, i2, . . . ,
iL) and (jl, j2, . . . , jL) are (al, a2, . . . , aL) and (bi, b2, . . . ,
bL), respectively. Since the points
are distinct, a property of the Kerpez constellation is that i" ~ j" for all v
E {1, 2, . . . , L~.
Define d";~ _ ~i" - wI. From (3~, if dm;~ _ ~v i dv;; then the distance vector
between these
two points, (dl;~, d2;~, . . . , dL;~~, is a permutation of (2L-1, 2L-z, . . .
, 22, 2,1~. According to the
method in Section 1.1.3, we have i 1 = 1 + ~L-12n-1 an and jl = 1 + ~n-i 2n-i
bn. Assume
that these two bit patterns differ in the mth location, 1 < rri < L, that is,
an, n ~ m
bn =
(B.1)
an~1, n=m
We want to show that the distance vector between these two constellation
points is a per-
mutation of (2L-1, 2L-2, . . . , 22, 2,1~.
We have
L
n 1
.~1 - 21 - ~ 2 (bn - an)
n=1
- 2nt 1(CLnl ~ 1 - am)
- ~2"' 1 (B.2)
H2
- . 2 ~ s~~~~
Also, for 2 < v < L, we get
7v - Zv = (~i - 1)2L-°+i mod2L - (il - 1)2L-°+1 mod2L - f 2x111
+- 1 2°i 1l (B.3)
and
L \
(il - 1)2L-°+1 mod2L - ~~ 2n-lanJ 2L-°+i mod2L
n 1
v-1
- 2L+n van mod2L
n=1
v-1
- 2L+ an B.4
n=1
where (B.4) follows from the relation ~n-i 2L+n-"an < 2L-° ~~-i 2n <
2L. Also,
il _ 1 '~" Ln=1 2n lan
2v-1 2v-1
- ~ ,Zn-va + 1 + yn=1 2n 1 an
n ~ 2v-1
n=v
L
2n-°an ~- 1 (B.5)
n=v
where (B.5) follows from the relation 1 + ~n-i 2n 1 an < 1 + ~n i 2n ' =
2°-1. Substituting
(B.4) and (B.5) in (B.3), we have
v-1 L
jv - iv = ~ 2L+n v(bn - an) -f- ~ 2n v(an - bn), 2 < v < L. B.6
n-1 n=v
There are two cases to consider. Case i) 1 < m < v - 1 ~ ~z ~- 1 < v < L. Eq.
(B.6) gives
~j" - i"~ _ ~2L+"'-°(a,n ~ 1 - a",)~ = 2L+'"-°. Case ii) v < m <
L ~ 2 < v < m. Eq. (B.6)
gives ~ j"-i"~ _ ~2"'-v(a",-an,~1)~ = 2m-°. Thus, (dl;~, d2;~, . . . ,
d,n_i;;, d.n;;, dn~+i;;, . . . , dL;~~
_ (2"'-1, 2"'-2, . . . , 2,1, 2L-1, 2L-2, . . . , 2"'~ which is a permutation
of the minimum distance
vector, as required.
~l 3
