Note: Descriptions are shown in the official language in which they were submitted.
CA 02238680 1998-05-27
TITLE OF THE INVENTION: MultiCode Spread Spectrum Communications
System
NAMES OF THE INVENTORS: Michel T. Fattouche, Hatim Zaghloul, Paul
R. Milligan and David L. Snell
Field of the Invention: The invention deals with the field of multiple access
communications using Spread Spectrum modulation. Multiple access can be
classified as either random access, polling, TDMA, FDMA, CDMA or any
combination thereof. Spread Spectrum can be classified as Direct Sequence,
Frequency-Hopping or a combination of the two.
Background of the Invention: Commonly used spread spectrum techniques
are Direct Sequence Spread Spectrum (DSSS) and Code Division Multiple
Access (CDMA) as explained respectively in Chapters 13 and 15 of "Digital
Communication" by J.G. Proakis, Third Edition, 1995, McGraw Hill. DSSS
(See Simon M.K. et al., "Spread Spectrum Communications Handbook,"
Revised Edition, McGraw-Hill, 1994 and see Dixon, R.C., "Spread Spectrum
systems with commercial applications," Wiley InterScience, 1994) is a
communication scheme in which information symbols are spread over code
bits (generally called chips). It is customary to use noise-like codes called
pseudo-random noise (PN) sequences. These PN sequences have the property
that their auto-correlation is almost a delta function. In other words, proper
codes perform an invertible randomized spreading of the information
sequence. The advantages of this information spreading are:
1. The transmitted signal can be buried in noise and thus has a low
probability
of intercept.
2. The receiver can recover the signal from interferers (such as other
transmitted codes) with a jamming margin that is proportional to the
spreading code length.
3. DSSS codes of duration longer than the delay spread of the propagation
channel can lead to multipath diversity implementable using a Rake
receiver.
4. The FCC and Industry Canada have allowed the use of unlicensed low
power DSSS systems of code lengths greater than or equal to 10 (part 15
rules) in some frequency bands (the ISM bands).
2
CA 02238680 1998-05-27
It is the last advantage (i.e. advantage 4. above) that has given much
interest
recently to DSSS.
An obvious limitation of DSSS systems is the limited throughput they
can offer. In any given bandwidth, W, a code of length M will reduce the
cffective bandwidth to W/M. To increase the overall bandwidth efficiency,
system designers introduced Code Division Multiple Access (CDMA) where
multiple DSSS communication links can be established simultaneously over
the same frequency band provided each link uses a unique code that is noise-
like, i.e. provided the cross-correlation between codes is almost null.
Examples of CDMA is the next generation of digital Cellular communications
in North America: "the TIA Interim 3"tandard IS-95," (see QUALCOMM Inc.,
"An overview of the application of Code Division Multiple Access (CDMA)
to digital cellular systems and personal cellular networks," May 21, 1992 and
see Viterbi, A.J., "CDMA, Principles of Spread Spectrum Communications,"
Addison-Wesley, 1995) where a Base Station (BS) communicates to a number
of Mobile Stations (MS) simultaneously over the same channel. The MSs
share one carrier frequency during the mobile-to-base link (also known as the
reverse link) which is 45MHz away from the one used by the BS during the
base-to-mobile link (also known as the forward link). During the forward
link, the BS transceiver is assigned N codes where N is less than or equal to
M
and M is the number of chips per DSSS code. During the reverse link each
MS is assigned a unique code.
CDMA problems are:
1. The near-far problem on the reverse link: an MS transmitter "near" the BS
receiver can overwhelm the reception of codes transmitted from other MSs
that are "far" from the BS.
2. Synchronization on the reverse link: synchronization is complex
(especially) if the BS receiver does not know in advance either the identity
of the code being transmitted, or its time of arrival.
Summary of the Invention: We have recognized that low power DSSS
systems would be ideal communicators provided the problems of CDMA
could be resolved. In order to avoid both the near-far problem and the
synchronization problem that exist on the reverse link of a CDMA system, we
have opted in this patent to use only the forward link at all times for MCSS
3
CA 02238680 1998-05-27
Types I and II. This is achieved within a specified channel by allowing only
one transceiver to transmit at a time within a certain coverage area. Such a
transceiver is forced during transmission to act as the BS in transmit mode
while the remaining transceivers are forced to act as MSs in receive mode. In
this patent, we refer to such a modulation scheme as MultiCode Spread
Spectrum (MCSS).
On the other hand, both the near-far problem and the synchronization
problem that exist on the reverse link of a CDMA system are reduced
drastically by using MCSS Type III. In this case, each user is assigned one
code and each code is assigned a guard time such that it starts to transmit
only
after a given amount of time relative to any adjacent codes. By forcing the
users to have separate start times, MCSS Type III forces the codes to be
(quasi) orthogonal as long as the guard time between adjacent codes is long
enough.
When viewed as DSSS, a MCSS receiver requires up to N correlators (or
equivalently up to N Matched Filters) (such as in QUALCOMM Inc,."An
overview of the application of Code Division Multiple Access (CDMA) to
digital cellular systems and personal cellular networks, May 21, 1994 and as
in Viterbi, A.J., "CDMA, Principles of Spread Spectrum Communications,"
Addison-Wesley, 1995) with a complexity of the order of NM operations.
When both N and M are large, this complexity is prohibitive. In addition, a
nonideal communication channel can cause InterCode Interference (ICI), i.e.
interference between the N SS codes at the receiver. In this patent, we
introduce three new types of MCSS. MCSS Type I allows the information in a
MCSS signal to be detected using a sequence of partial correlations with a
combined complexity of the order of M operations. MCSS Type II allows the
information in a MCSS signal to be detected in a sequence of low complexity
parallel operations while reducing the ICI. MCSS Type III allows the
information in a MCSS signal to be detected in a sequence of low complexity
Multiply and Accumulate (MAC) operations implementable as a filter, which
reduce the effect of multipath. In addition to low complexity detection and
ICI
reduction, our implementation of MCSS has the advantage that it is spectrally
efficient since N can be made approximately equal to M. In DSSS, N=1 while
in CDMA typically N < 0.4M.
Description of the Invention:
4
CA 02238680 1998-05-27
The description of the invention consists of six parts. The first three parts
correspond to trie transmitter for each one of the three types of MCSS
introduced in this patent, while the last three parts correspond to the
receiver
for each one of the three types of MCSS.
Description of the Transmitter for MCSS Type I:
Figure 1 illustrates a block diagram of the transmitter for MCSS Type I
with an input of V frames of B data symbols each, every VBT seconds and an
output of P frames of M multicoded SS symbols each, every PMTc seconds
where T is the duration of one data symbol and Tc is the duration of one chip
in a spread spectrum code. The data symbols can be either analog or digital.
If
digital, they belong to an alphabet of finite size. If analog, they correspond
to
the samples of an analog signal.
Figure 1 is described as follows:
= The first block in Figure 1 is a serial-to-parallel converter (101) with an
input of B data symbols and an output of one frame of B data symbols,
every BT seconds.
= The second block is a 2 Dimensional (2D) shift register (102) with an input
of V frames of B data symbols each (input by shifting the frames from left
to right V times) and an output of Q frames of B data symbols each, every
VBT seconds.
= When the data symbols are analog, the third block (103) in Figure 1
corresponds to an analog pulse modulator with several possible modulation
schemes such as Pulse Amplitude Modulation (PAM), Pulse Position
Modulation (PPM), Pulse Frequency Modulation (PFM), etc. When the
data symbols are digital, the third block is a channel encoder/modulator
(103) with an input of Q frames of B data symbols each and an output of P
frames of J modulated symbols each, every QBT seconds. The channel
encoder/modulator performs two functions: (1) to encode and (2) to
modulate the data symbols. The first function offers protection to the
symbols against a non ideal communication channel by adding redundancy
to the input sequence of data symbols while the second function maps the
protected symbols into constellation points that are appropriate to the
communication channel. Sometimes it is possible to perform the two
functions simultaneously such as in the case of Trellis Coded Modulation
(TCM). For simplicity, we assume throughout the patent that the two
CA 02238680 1998-05-27
functions are performed simultarieously and refer to the block performing
the two functions as the channel encoder/modulator.
Different types of channel encoders are available:
= If the 2D shift register (102) is operated wi*'i V=Q, then the encoder
performs block encoding, otherwise if V<Q, the encoder performs
convolutional encoding. Furthermore, if B>J then the encoder is a trellis
encoded modulator either with block encoding if V=Q or with
convolutional encoding with V<Q.
= If B=J, the code rate is Q/P, i.e. the encoder takes Q data symbols in
and generates P encoded data symbols out where P>Q. Furthermore, if
V<Q then (V-1) is the constraint length of the convolutional encoder.
= If the 2D shift register (102) is operated with B> 1, then it can act as an
interleaver which interleaves the data symbols prior to the channel
encoder (103), otherwise if B=1 the channel encoder does not rely on
interleaving. Another possible form of interleaving is to interleave the
coded data symbols after the channel encoder (not shown in Figure 1).
Different types of modulators are available such as: Binary Phase Shift
Keying (BPSK), Quadrature Phase Shift Keying (QPSK), Multilevel Phase
Shift Keying (MPSK), Quadrature Amplitude Modulation (QAM),
Frequency Shift Keying (FSK), Continuous Phase Modulation (CPM),
Amplitude Shift Keying (ASK), etc. All amplitude and frequency
modulation schemes can be demodulated either coherently or
noncoherently. All phase modulation schemes can de demodulated either
coherently or differentially. In the latter case, differential encoding is
required in the modulator such as in Differential BPSK (DBPSK),
Differential QPSK (DQPSK), Differential MPSK (DMPSK), etc.
Even though the output of the channel encoder/modulator (103)
corresponds to an encoded and modulated data symbol, we will refer to it
of as a `modulated symbol'.
= The fourth block is a spreader type I(104) with an input of P frames of J
modulated symbols each and an output of P frames of N spread spectrum
symbols each, of length M chips per spread spectrum symbol, every PMTc
seconds. The spreader type I(104) is explained further below in Figures 2-
5.
6
CA 02238680 1998-05-27
= The fifth block is a 3 Dimensional (3D) shift register (105) with an input
of
P frames of N spread spectrum symbols each (input by shifting the PN
symbols from inside to outside M chip times), and an output of M frames
of N chips each (output by shifting MN chips from left to right P times)
every PMTc seconds.
= The sixth block is a set of M adders (106). Each adder has an input of N
chips and an output of one multicoded SS symbol, every MTc seconds.
= The seventh block is a parallel-to-serial converter (107) with an input of
one frame of M multicoded SS symbol and an output of M multicoded SS
symbol every MTc seconds.
The spreader type I(104) in Figure 1 is described further in Figure 2 with
an input of P frames of J modulated symbols each, generated by the channel
encoder/modulator (103) in Figure 1, and an output of P frames of N spread
spectrum symbols each, of length M chips per spread spectrum symbol. Figure
2 is described as follows:
= The first block in Figure 2 is a set of P converters (201) with an input of
one frame of J modulated symbols per converter, and an output of one
frame of N subsets of modulated symbols per converter. The ith subset
contains a number J; of modulated symbols where Jl +J2 +...+JN =J and
i=1,...,N.
= The second block is a set of N computing means (202) with an input of one
subset of modulated symbols per computing means, and an output of one
spread spectrum symbol, of length M chips per computing means.
The set of N computing means (202) in Figure 2 is described further in
Figure 3 which displays only the ith computing mean where i=1,...,N. The ith
computing mean has as an input the ith subset of modulated symbols, and as
an output the ith spread spectrum symbol of length M chips. Figure 3 is
described as follows.
= The first block in Figure 3 is the ith mapper (301) with two inputs and one
output. The two inputs are: (1) the ith subset of modulated symbols which
contains a number J; of modulated symbols, and (2) Li spread spectrum
codes of length M chips each. The output is the ith spread spectrum
symbol. The ith mapper chooses from the set of L; spread spectrum codes
the code corresponding to the ith subset of modulated symbols to become
7
CA 02238680 1998-05-27
the ith spread spectrum code representing an invertible randomized
spreading of the ith subset of modulated symbols.
= The second block in Figure 3 is the ith source (302) of L; spread spectrum
codes with an output of Li spread spectrum codes of 1 ngth M chips each.
The ith source (302) can be thought of as eithei a lookup table or a code
generator. Two different implementations of the ith source are shown in
Figures 4 and 5.
Remarks on the "invertible randomized spreading":
1. In this patent, the invertible randomized spreading of a signal using a
spreader is only invertible to the extent of the available arithmetic
precision
of the machine used to implement the spreader. In other words, with finite
precision arithmetic, the spreading is allowed to add a limited amount of
quantization noise.
2. Moreover, the randomized spreading of a signal is not a perfect
randomization of the signal (which is impossible) but only a pseudo-
randomization. This is typical of spread spectrum techniques in general.
3. Finally, in some cases such as over the multipath communication channel,
it is advantageous to spread the signal over a bandwidth wider than 25% of
the coherence bandwidth of the channel. In this patent, we refer to such a
spreading as wideband spreading. In the indoor wireless channel, 25% of
the coherence bandwidth ranges from 2MHz to 4MHz. In the outdoor
wireless channel, 25% of the coherence bandwidth ranges from 30KHz to
60KHz. In other words, in this patent wideband spreading corresponds to a
spreading of the information signal over a bandwidth wider than 30KHz
over the outdoor wireless channel and wider than 2MHz over the indoor
wireless channel, regardless of the bandwidth of the information signal and
regardless of the carrier frequency of modulation.
The ith source (302) of Figure 3 can also be generated as in Figure 4 as a
set of Li transforms with an input of one preset sequence of length M chips
per transform and an output of one spread spectrum code of length M chips
per transform. In other words, the ith source of spread spectrum codes could
be either a look-up table containing the codes such as in Figure 3 or a number
of transforms generating the codes such as in Figure 4.
8
CA 02238680 1998-05-27
The ith source (302) of Figure 3 can also be generated as in Figure 5 as two
separate blocks.
= The first block (501) consists of a set of L; transforms with an input of
one
preset sequence of length M chips per transform and an output of one
spread spectrum code of length M chips per transform.
= The second block is a randomizing transform (502) with an input of L;
transformed codes of length M chips each generated by the first block
(501) and an output of Li spread spectrum codes of length M chips each.
= The randomizing transform consists of two parts. The first part is a
randomizing look-up table (503) which contains a set of M preset values:
al,;, a2,;,...,aM,;. The second part multiplies each transformed symbol from
the set of transformed symbols generated by the first transform (501) by
the set of M preset values generated by the randomizing look-up table
(503). The multiplication is performed chip-by-chip, i.e. the kth chip in the
ith transformed symbol is multiplied by the kth value ak ; in the set of M
preset values for all values of k=1, ..., M.
Description of the Transmitter for MCSS Type II:
Figure 6 illustrates a block diagram of the transmitter for MCSS Type II
with an input of VB data symbols every VBT seconds and an output of PM
multicoded SS symbols every PMTc seconds. Figure 6 is described as follows:
= The first block in Figure 6 is a serial-to-parallel converter (601) with an
input of B data symbols and an output of one frame of B data symbols,
every BT seconds.
= The second block is a 2 Dimensional (2D) shift register (602) with an input
of V frames of B data symbols each (input by shifting the frames from left
to right V times) and an output of Q frames of B data symbols each, every
VBT seconds.
= The third block is a channel encoder/modulator (603) with an input of Q
frames of B data symbols each and an output of P frames of J modulated
symbols each, every QBT seconds. The function of the channel
encoder/modulator is exactly the same as the --`:annel encoder/modulator
(103) described above for MCSS type I in Figure 1.
= The fourth block is a spreader type II (604) with an input of P frames of J
modulated symbols each and an output of P frames of M multicoded SS
9
CA 02238680 1998-05-27
symbols each, every PMTc seconds. The spreader type II is explained
further below in Figures 7-9.
= The fifth block is a 2 Dimensional (2D) shift register (605) with an input
of
P frames of M multicoded SS symbols each, and an output of P frames of
M multicoded SS symbols each (output by shifting the M frames from left
to right P times) every PMTc seconds.
= The sixth block is a parallel-to-serial converter (606) with an input of one
frame of M multicoded SS symbols and an output of M multicoded SS
symbols every MTc seconds.
The spreader type II (604) in Figure 6 is described further in Figure 7
with an input of P frames of J modulated symbols each, generated by the
channel encoder/modulator (603) in Figure 6, and an output of P frames of M
multicoded SS symbols each. Figure 7 is described as follows:
= The first block in Figure 7 is a set of P converters (701) with an input of
one frame of J modulated symbols per converter, and an output of one
frame of M subsets of modulated symbols per converter. The ith subset
contains a number of J; of modulated symbols where J, +J2 +...+JM =J and
i=1,...,M.
= The second block is a set of P M-point transforms (702) with an input of M
subsets of modulated symbols per transform, and an output of a frame of M
multicoded SS symbols per transform. The P M-point transforms perform the
invertible randomized spreading of the M subsets of modulated symbols.
The set of P M-point transforms (702) in Figure 7 is described further in
Figure 8 which displays only the ith M-point transform where i=1,...,N. The
input of the ith transform is the ith subset of J; modulated symbols, and the
output is the ith frame of M multicoded SS symbols. In Figure 8, the ith M-
point transform is the randomizing transform (801) similar to the randomizing
transform (502) in Figure 5 with the set of preset values given as: a1,;,
aZ.;, ...,
aM,;. In this case, the kth preset value ak,; multiplies the kth subset of Jk
modulated symbols to generate the kth multicoded SS symbol.
The ith M-point transform (801) in Figure 8 can further include a
second M-point transform (902) as described in Figure 9.
CA 02238680 1998-05-27
= The first M-point transform (901) is the ith randomizing transform with an
input of the ith subset of J; modulated symbols, and an output of the ith
frame of M transformed symbols.
= The second M-point transform (902) is the ith second M-point transform
with an input of the ith frame of transformed symbols, and an output of the
ith frame of M multicoded SS symbols.
Description of the Transmitter for MCSS Type III:
Figure 10 illustrates a block diagram of the transmitter for MCSS Type
III with an input of a stream of data symbols and an output of a stream of
multicoded SS symbols. Figure 10 is described as follows:
= The first block is a channel encoder/modulator (1001) with an input of a
stream of data symbols and an output of a stream of modulated symbols.
The function of the channel encoder/modulator is similar to the channel
encoder/modulator for MCSS types I and II (103) and (603) respectively
except its operation is serial. Such a representation is commonly used in
textbooks to implicitly imply that the data rate of the output stream of
modulated symbols could be different from the input stream of data
symbols. In other words, the channel encoder/modulator can add
redundancy to the input stream of data symbols to protect it against
channel distortion and noise. The type of redundancy varies depending on
the type of encoding used. In block encoding, the redundancy depends only
on the current block of data. In convolutional encoding, it depends on the
current block and parts of the previous block of data. In both types of
encoding trellis coding can be used which modulates the modulated
symbols output from the encoder.
Even though Figure 10 does not contain an interleaver, it is possible to
include one either before the channel encoder/modulator or after.
= The second block is a spreader type III (1002) with an input of a stream of
modulated symbols and an output of a stream of multicoded SS symbols.
The spreader type III is further explained in Figures 11-13.
= The third block is a ramper (1003) with an input of multicoded SS symbols
and an output of a ramped multicoded SS symbols. The ramper is further
explained in Figure 14.
11
CA 02238680 1998-05-27
The spreader type III (1002) in Figure 10 is described further in Figure 11
as two blocks with an input of a stream of modulated symbols, generated by
the channel encoder/modulator (1001) in Figure 10, and an output of a stream
of multicoded SS symbols.
= The first block is a randomizer (1101) with an input of a stream of
modulated symbols and an output of a randomized modulated symbols. The
randomizer is described further in Figure 12.
= The second block is a computing means (1102) with an input of the stream
of randomized modulated symbols and an output of a stream of multicoded SS
symbols. The computing means is described further in Figure 13.
In Figure 12 the randomizer (1101) from Figure I 1 is described further as
two parts.
= The first part is a chip-by-chip multiplier (1201) with two inputs and one
output. The first input is the stream of modulated symbols and the second
input is a stream of preset values output from a randomizing lookup table
(1202). The output is the product between the two inputs obtained chip-by-
chip, i.e. the kth randomized modulated symbols is obtained by multiplying
the kth modulated symbol with the kth preset value ak.
= The second part is the randomizing lookup table (1202) which is the source
of a stream of preset values: ...,ak,ak+l,... As mentioned before, the
randomizing sequence is only pseudo-randomizing the modulated symbols.
In Figure 13 the computing means (1102) from Figure 11 is described
further as a filter which performs the invertible randomized spreading of the
stream of modulated symbols.
Figure 14 illustrates the ramper (1003) in Figure 10 as a mixer with two
inputs and one output. The first input is the stream of multicoded SS symbols,
the second input is a linearly ramping carrier frequency ej2if `Z which ramps
the multicoded SS stream over the time `t' thereby generating a stream of
ramped multicoded SS symbols where j= -1--l and f o is a constant.
Description of the Receiver for MCSS Type I:
Figure 15 illustrates a block diagram of the receiver for MCSS type I & II
with an input of PM multicoded SS symbols, every PMTc seconds and an
12
CA 02238680 1998-05-27
output of VB estimated data symbols, every VBT seconds. Figure 15 is
described as follows:
= The first block in Figure 15 is a serial-to-parallel converter (1501) with
an
input of M multicoded SS symbols and an output of one frame of M
multicoded SS symbols every MTc seconds.
= The second block is a 2 Dimensional (2D) shift register (1502) with an
input of one frame of M multicoded SS symbols each (input by shifting the
frame from left to right P times) and an output of P frames of M
multicoded SS symbols each, every PMTc seconds.
= The third block is a despreader type I(1503) with an input of P frames of
M multicoded SS symbols each and an output of P frames of J despread
symbols each every PMTc seconds. The despreader type I is further
explained below.
= The fourth block is a channel decoder/demodulator (1504) with an input of
P frames of J despread symbols each and an output of V frames of B
estimated data symbols each, every VBT seconds. The channel
decoder/demodulator performs two functions: (1) to map the despread
symbols into protected data symbols and (2) either to detect errors, or to
correct errors, or both. Sometimes, the two functions can be performed
simultaneously. In this case, the channel decoder/demodulator performs
soft-decision decoding, otherwise, it performs hard-decision decoding. By
perfonning the two function, the channel encoder/demodulator accepts the
despread symbols and generates estimated data symbols
= The fifth block is a 2 Dimensional (2D) shift register (1505) with an input
of V frames of B estimated data symbols each, and an output of V frames
of B estimated data symbols (output by shifting the V frames from left to
right) every VBT seconds. If the 2D shift register (102) is operated with
B>1, then it might act as an interleaver. In this case, the receiver requires
a
de-interleaver which is accomplished using the 2D shift register (1505).
= The sixth block is a parallel-to-serial converter (1506) with an input of
one
frame of B estimated data symbols and an output of B estimated data
symbols, every VBT seconds.
The despreader type I(1504) in Figure 15 is described further in Figure 16
with an input of P frames of M multicoded SS symbols each from the received
13
CA 02238680 1998-05-27
sequence of multicoded SS symbols, and an output of P frames of J despread
symbols each. Figure 16 is described as follows:
= The first block in Figure 16 is a set of P parallel-to-serial converters
(1601)
with an input of one frame of M multicoded SS s,,mbols per converter, and
an output of M multicoded SS symbols per converter.
= The second block is a set of N computing means (1602) each having the
same input of M multicoded SS symbols and an output of one computed
value per computing means.
= The third block is a detector (1603) with an input of N computed values
and an output of J despread symbols per detector. When the data symbols
are digital, the detector can make either hard decisions or soft decisions.
When the data symbols are analog, L; is necessarily equal to 1 for i=l,...,N
and the detector is not required.
The set of N computing means (1602) in Figure 16 is described further in
Figure 17 which displays only the ith computing mean where i=1,...,N. The ith
computing mean has as an input the M multicoded SS symbols, and as an
output the ith computed value. Figure 17 is described as follows.
= The first block in Figure 17 is a set of L; partial correlators (1701). The
nth
partial correlator has two inputs where n=1,2,...,L;. The first input consists
of the M multicoded SS symbols and the second input consists of the nth
spread spectrum code of length M chips out of the ith source of Li spread
spectrum codes. The output of the nth partial correlator is the nth partially
correlated value obtained by correlating parts of the first input with the
corresponding parts of the second input.
= The second block is the ith source (1702) of L; spread spectrum codes
with an output of L; spread spectrum codes of length M chips each.
= The third block is the ith sub-detector (1703) with an input of Li partially
correlated values and an output of the ith computed value. The ith sub-
detector has two tasks. First using the L; partially correlated values it has
to
obtain the full correlation between the M multicoded SS symbols and each
one of the Li spread spectrum codes of length M chips obtained from the
ith source (1702). Then, it has to select the spread spectrum code
corresponding to the largest correlation. Such a detected spread spectrum
code together with the corresponding full correlation value form the ith
computed value.
14
CA 02238680 1998-05-27
The detector (1703) in Figure 16 takes all the computed values from each
one of the N computing means and outputs J despread symbols. Based on
the function of each sub-detector, one can say that the detector (1603) has
two tasks at hand. First, it has to map each detected spread spectrum code
into a first set of despread symbols, then it has to map each full correlation
value into a second set of despread symbols. In other words, the first set of
despread symbols correspond to spread spectrum codes that form a subset
of the spread spectrum codes corresponding to the second set of despread
symbols.
It is also possible to have several layers of sub-detectors completing
different levels of partial correlations and ending with N spread spectrum
codes corresponding to the largest full correlation values per computing
means. In this case, the tasks of the detector are first to map each detected
spread spectrum code (obtained through the several layers of sub-
detection) into sets of despread symbols, then to map each full correlation
value into a final set of despread symbols.
Description of the Receiver for MCSS Type II:
Figure 15 illustrates a block diagram of the receiver for MCSS Type II
with an input of PM multicoded SS symbols every PMTc seconds and an
output of VB estimated data symbols every VBT seconds. Figure 15 illustrates
also the block diagram of the receiver for MCSS Type I and has been
described above.
The despreader type II (1504) in Figure.15 is described further in Figure 18
with an input of P frames of M multicoded SS symbols each, and an output of
P frames of J despread symbols each. Figure 18 is described as follows:
= The first block in Figure 18 is a set of P M-point transforms (1801) with an
input of one frame of M multicoded SS symbols per transformer, and an
output of M transformed symbols per transformer.
= The second block is a set of P detectors (1802) with an input of M
transformed symbols per detector, and an output of J despread symbols per
detector. Once again the detector can either make soft decisions or hard
decisions.
CA 02238680 1998-05-27
Description of the Receiver for MCSS Type III:
Figure 19 illustrates a block diagram of the receiver for MCSS Type III
with an input of a stream of ramped multicoded SS symbols and an output of a
stream of estimated data symbols. Figure 19 is descri;.ed as follows:
= The first block in Figure 19 is a de-ramper (1901) with an input of the
stream of ramped multicoded SS symbols and an output of an estimated
stream of multicoded SS symbols. The de-ramper is further described in
Figure 20.
= The second block is a de-spreader Type III (1902) with an input of the
estimated stream of multicoded SS symbols and an output of a stream of
detected symbols. The de-spreader type II is further explained in Figure
21-23.
= The third block is a channel decoder/demodulator (1903) with the input
consisting of the stream of detected symbols, and an output of a stream of
estimated data symbols. It is clear from Figure 19 that no de-interleaver is
included in the receiver. As mentioned above, if an interleaver is added to
the transmitter in Figure 10, then Figure 19 requires a de-interleaver.
Figure 20 illustrates the deramper (1901) in Figure 19 as a mixer with two
inputs and one output. The first input is the ramped multicoded SS symbols
and the second input is a linearly ramping carrier frequency which deramps
the ramped multicoded SS stream thereby generating an estimated stream of
multicoded SS symbols.
The despreader type III (1902) in Figure 19 is described further in Figure
21 as three blocks.
= The first block is a computing means (2101) with an input of an estimated
stream of multicoded SS symbols and an output of a stream of randomized
despread symbols. Figure 22 describes the computing means (2101) in Figure
21 as a filter (2201) which performs the despreading process.
= The second block is a de-randomizer (2102) with an input of a stream of
randomized despread symbols and an output of a stream of despread symbols.
The de-randomizer (2102) is described further in Figure 23.
= The third block is a detector (2103) with an input of a stream of despread
symbols and an output of a stream of detected symbols. When the detector is a
16
CA 02238680 1998-05-27
hard-decision detector it makes a decision on the despread symbols such that
the detected values takes a finite number of values out of a predetermined
alphabet of finite size. When the detector is a soft-decision detector the
detected symbols are the same as the despread symbols.
The de-randomizer (2102) is described further in Figure 23 as two parts.
= The first part is a chip-by-chip multiplier (2301) with two inputs and an
output. The first input is a stream of randomized despread data symbols and
the second input is a stream of preset values output from a de-randomizing
lookup table (2302). The output is the chip-by-chip product between the two
inputs, i.e. the kth despread symbol is obtained as the product between the
kth
randomized despread symbol and the kth preset value bk.
= The second part is a de-randomizing lookup table (2302) which outputs a
stream of preset values: ...,bk,bk+l ,...
Preferred Embodiments of the Invention:
From the above description of the invention, it is clear that the
contribution of the invention is primarily in the spreader in the transmitter
and
in the despreader in the receiver for each one of the three type of MCSS
introduced in the patent. The secondary contribution of the patent resides in
the channel encoder/modulator and in the extra components that can be used
in both the transmitter and in the receiver for each three types such as: the
ramping and de-ramping of the signal and diversity techniques. For these
reasons, we have separated the preferred embodiments of the invention into
three parts. Each part corresponds to the spreader and the despreader for each
one of the three types of MCSS and its extras.
Preferred Embodiments of the Spreader/Despreader for MCSS Type I:
= In Figure 1, the spreader Type I(104) performs an invertible randomized
spreading of the modulated symbols which carry either digital information
or analog information, and in Figure 15 the despreader Type I(1503)
performs a reverse operation to the spreader Type I(104) within the limits
of available precision (i.e. with some level of quantization noise).
= In Figure 1, the spreader Type I(104) performs an invertible randomized
spreading of the modulated, and in Figure 15 the despreader Type I(1503)
performs a reverse operation to the spreader Type I(104) while taking into
17
CA 02238680 1998-05-27
account the effects of the communications channel such as noise, distortion
and interference. The effects of the channel are sometimes unknown to the
receiver (e.g. over selective fading channels which cause intersymbol
interference). In such cases, the channel has to be estimated using for
example a pilot signal known to the receiver as in "MultiCode Direct
Sequence Spread Spectrum," by M. Fattouche and H. Zaghloul, US patent
#5,555,268, Sept. 1996.
= In Figure 2, if Jk=O for any k=1,...,N then the output of the kth computing
means is the all zeros spread spectrum codes of length M chips.
= In Figure 2, if the modulated symbols are M-ary symbols, then a preferred
value for L; is M to the power of J;. In other words, by choosing one spread
spectrum code out of L; codes, J; symbols of information are conveyed.
= In Figure 3, a preferred function for the ith mapper is to choose one spread
spectrum code (out of the Li available codes) based on one part of the ith
subset of Ji modulated symbols while the second part of the subset is used
to choose the symbol that multiplies the chosen spread spectrum code. In
other words, assuming that the kth spread spectrum code Sk is chosen by
the ith mapper (301) (out of the Li available codes) based on the first part
of the ith subset of Ji modulated symbols and that the symbol ~ is chosen
to multiply Sk based on the second part of the ith subset of J; modulated
symbols, then the ith spread spectrum symbol out of the ith mapper (301)
is Sk~. This is equivalent to spreading ~ over Sk.
= In Figure 3, ~ can be chosen as a DBPSK symbol, a DQPSK symbol, a
DMPSK symbol, a QAM symbol, a FSK symbol, a CPM symbol, an ASK
symbol, etc.
= In Figure 3, the Li spread spectrum codes, out of the ith source (302) of L;
available spread spectrum codes, correspond to Walsh codes. Each Walsh
code in Figure 3 is generated in Figure 4 as the output of an M-point Walsh
transform where the input is a preset sequence of length M chips with (M-
1) chips taking a zero value while one chip taking a unity value.
= In Figure 3, the Li spread spectrum codes, out of the ith source (302) of Li
available spread spectrum codes, correspond to randomized Walsh codes.
Each Walsh code generated in Figure 4 as the output of an M-point Walsh
transform is randomized in Figure 5 using a chip-by-chip multiplier where
the kth chip of each Walsh code is multiplied by the preset value ak ; output
from the ith randomizing lookup table.
18
CA 02238680 1998-05-27
= In Figure 5, the M preset values { al ;,a2i ,...,aM;} are chosen such that
their
amplitudes: Iat,;I,Ia2;I,...,laM,;I are all equal to unity.
= In Figure 3, a preferred value for L; is 2 and a preferred value for M is 10
with the two preferred spread spectrum codes out of the ith source (302)
taking the values:
{ CI,C2 IC3 ,C4.+C5.,C6,,C7,,C8,,C9 X10} and
{ C 1 ,C2 ,C3 ,C4 C5 ,-C6 1-C7 ,-C8 ,-C9 ,-C 10 } (1)
= In equation (1), preferred values for the chips
`c1,c2,c3,C4,C5,C6,c7,cS,c9,clo'
are `1,-1,1,1,1,j, j,j,j,j' which we refer to as the 'Wi-LAN codes Type I'.
Preferred Embodiments of the Spreader/Despreader for MCSS Type II:
= In Figure 6, the spreader Type II (604) performs an invertible randomized
spreading of the modulated symbols which carry either digital information
or analog information, and in Figure 15 the despreader Type II (1503)
performs a reverse operation to the spreader Type II (604) within the limits
of available precision (i.e. with some level of quantization noise).
= In Figure 6, the spreader Type II (604) performs an invertible randomized
spreading of the modulated, and in Figure 15 the despreader Type II (1503)
performs a reverse operation to the spreader Type 11 (604) while taking
into account the effects of the communications channel such as noise,
distortion and interference. As mentioned above, the effects of the channel
are sometimes unknown to the receiver (e.g. over selective fading channels
which cause intersymbol interference). In such cases, the channel has to be
estimated using for example a pilot signal known to the receiver as in
"MultiCode Direct Sequence Spread Spectrum," by M. Fattouche and H.
Zaghloul, US Patent #5,555,268, Sept. 1996.
= Two preferred types of pilot signals can be used to estimate the effects of
the channel on the information-bearing data symbols:
1. Pilot Frames inserted either before, during or after the Data frames of
M multicoded SS symbols; and
2. Pilot Symbols inserted within each data frame of M multicoded SS
symbols.
Pilot frames estimate the long term effects of the channel, while pilot
symbols estimate the short term effects of the channel.
= When channel estimation is used in the receiver as mentioned above, it is
possible to use coherent detection with phase modulation, such as BPSK,
19
CA 02238680 1998-05-27
QPSK and MPSK, after removing the effects of the channel from the phase
of the received signal. On the other hand, if the effects of the channel are
not removed, differential detection is selected instead with differentially-
encoded phase modulation such as DPSK, DQPSK and DMPSK.
= Furthermore, when channel estimation is used in the receiver as mentioned
above, it is possible to use amplitude modulation together with coherent
detection of phase modulation, such as ASK and QAM, after removing the
effects of the channel from the phase and the amplitude of the received
signal. On the other hand, if the effects of the channel are not removed,
differential detection is selected instead with differentially-encoded phase
and amplitude modulation such as Differential QAM using the star
constellation.
= A preferred modulation technique is QAM when the channel is estimated
and its effects removed.
= Another preferred modulation technique is DMPSK when the effects of the
channel are not removed. In this case, a reference symbol is chosen at the
beginning of each frame output from the channel modulator/modulator
(603).
= In Figure 6, a preferred channel encoder/modulator (603) is a Reed-
Solomon channel encoder used for encoding M-ary symbols and for
correcting errors caused by the channel at the receiver. If the data symbols
are binary, it is preferred to choose to combine several input bits into one
symbol prior to encoding. A preferred technique to combine several bits
into one symbol is to combine bits that share the same position within a
number of consecutive frames. For example, the kth bit in the nth frame
can be combined with the kth bit in the (n+l)th frame to form a dibit,
where k=1,...,Q.
= In Figure 6, if the data symbols are M-ary, a preferred value for B is unity
when using a Reed-Solomon encoder, i.e. no interleaver is required in this
case.
= In Figure 7, preferred values for J1,J2,...,JM are unity.
= In Figure 8, preferred values for { al,;, a2,;,...,aM,; } are such that
their
amplitudes: iat,; I,la2,; I,...,IaM,;I are all equal to unity.
= In Figure 9, preferred ith second M-point transform (902) is a Discrete
Fourier Transform (DFT).
CA 02238680 1998-05-27
= When J1=J2=...=JM=1, Iat,;I=Ia2.;I=...=IaM,;I=l and the ith second M-point
transform is a DFT, the MCSS transmitter is similar to the one in the issued
patent: "Method and Apparatus for Multiple Access between Transceivers
in Wireless Communications using OFDM Spread Spectrum," by M.
Fattouche and H. Zaghloul, US Patent # 5,282,222, Jan. 25 1994.
= The generated spread spectrum codes using
= J1=J2=...=JM=1,
= Ia1,;I=1a2,;I=...=IaM,;1=l,
= the ith second M-point transform as a DFT, and
= the channel encoder as a Reed-Solomon encoder without an interleaver
are referred to as the 'Wi-LAN codes Type II'.
= Another preferred embodiment of the ith second M-point transform (902)
is a Circular FIR (CFIR) filter of length M coefficients which performs an
M-point circular convolution between each block of M modulated symbols
and its own coefficients. In this case, a preferred embodiment of the M-
point transform (1801) is also a CFIR filter of length M coefficients which
performs the inverse operation of the spreading CFIR filter by performing
an M-point circular convolution between each block of M multicoded SS
symbols and its own coefficients. When the channel is estimated, the
despreading CFIR filter can also invert the effects of the channel using
either
1. a linear algorithm such as Zero Forcing Equalization (ZFE) and
Minimum Mean Square Equalization (MMSE); or
2. a nonlinear algorithm such as Decision Feedback Equalization (DFE)
and Maximum Likelihood (ML).
The effect of a nonideal frequency-selective communication channel is to
cause the multicodes to loose their orthogonality at the receiver. In the case
when ZFE is employed, the CFIR filter acts as a decorrelating filter which
decorrelates the M multicoded symbols from one another at the receiver
thereby forcing the symbols to be orthogonal.
An advantage of using CFIR filter for spreading and despreading the data
symbols is that IF-sampling can be inherently employed in the MCSS
receiver without increasing the complexity of the digital portion of the
receiver since interpolation and decimation filters can be included in the
CFIR filters.
21
CA 02238680 1998-05-27
Preferred Embodiments of the Spreader/Despreader for MCSS Type III:
= In Figure 10, the spreader Type III (1002) performs an invertible
randomized spreading of the stream of modula+ed symbols which carry
either digital information or analog information, and in Figure 19 the
despreader Type I(1902) performs a reverse operation to the spreader
Type III (1002) within the limits of available precision (i.e. with some
level of quantization noise).
= In Figure 10, the spreader Type III (1002) performs an invertible
randomized spreading of the stream of modulated symbols, and in Figure
19 the despreader Type III (1902) performs a reverse operation to the
spreader Type III (1002) while taking into account the effects of the
communications channel such as noise, distortion and interference. As
mentioned above, the effects of the channel are sometimes unknown to the
receiver (e.g. over selective fading channels which cause intersymbol
interference). In such cases, the channel has to be estimated using for
example a pilot signal known to the receiver as in "MultiCode Direct
Sequence Spread Spectrum," by M. Fattouche and H. Zaghloul, US Patent
#5,555,268 Sept. 1996.
= A preferred randomizer (1101) in Figure 11 is a trivial one with no effect
on the modulated symbols.
= Another preferred randomizer (1101) is one where the preset values out of
the randomizing lookup table (1202) :{.... ak_l,ak,ak+l, } have amplitudes
which are equal to unity.
= In Figure 13, a preferred filter is a Finite Impulse Response (FIR) filter
with the coefficients obtained as the values of a polyphase code.
= In Figure 13, a preferred filter is an FIR filter with the coefficients
obtained
as approximations to the values of a polyphase code.
= In Figure 13, a preferred filter is an FIR filter with the following 16
coefficients:
{1,1,1,1,
forming its impulse response where j=V--I. The 16 coefficients
correspond to the following polyphase code:
22
CA 02238680 1998-05-27
e'00(0),ej10(0),e j20(0), e j30(0)
ejoe(1) _ile(1) ej20(1),ej36(1),
,C ,
j0A(2) e.10(2) _j20(2) ej30(2)e
C , ,C e
e 6(3)'C_je(3)'ej2e(3)'ej3A(3)}
where 0(0)=0, 0(1)=27c/4, 9(2)=4n/4, 8(3 )=6n/4, and j= -\[-1 .
= In Figure 13, another preferred filter is an FIR filter with 64 coefficients
corresponding to the following polyphase code:
e'OA(0),ea 1A(0),ej20(0), e j30(0), e' 40(0), e'50(0),e'60(0),ej7A(0)
~09(1) 0(1), ej20(1),ej30(1)'C_j49(1)' ej50(1)'ej69(1)' ej70(1),
e,00(2)ej 10(2)ej20(2)'ej30(2)'d 40(2)' d 50(2)'ej69(2)'ej79(2),
e'00(3)'ej 10(3),ej20(3), e j30(3), e 40(3) e'50(3),ej68(3),ej79(3)
,
d 00(4) 10(4)20(4) ej30(4)'d40(4), d 50(4), ej60(4)'ej7e(4)~
, >
ejo9(5) ~ 10(5) ej20(5)ej30(5)id 40(5)' ej50(5)'ej69(5)'ej70(5)'
ej09(6)~ej10(6)~ej20(6) ej30(6)~ej40(6), ej50(6)'ej60(6)'ej78(6),
doe(7) ~10(7) ej2e(7) C_j30(7)~e40(7) ej50(7)~ej69(7)~e.i70(7)}
where 0(0)=0, 0(1)=27t/8, 0(2)=47r/8, 0(3)=67r/8, 0(4)=8n/8, 0(5)=107/8,
0(6)=12TE/8, 0(7)=147c/8, and j= [--I .
= In general, a preferred filter in Figure 13 with M coefficients
corresponding to a polyphase code can be obtained as the concatenation of
the rows of an \[M- x-\[M- matrix (assuming -vrM- is an integer) with the
coefficient in the ith row and kth column equal to e'(i-1)e(k-1) where
0(k)=2nk/-,[M-, and j=-\[--I.
= Another preferred filter in Figure 13 with M coefficients corresponding to
a binary approximation of a polyphase code can be obtained as the
concatenation of the rows of an ~M x-N matrix with the coefficient in
the ith row and kth column determined as follows:
= when (i-1)0 (k-1) is an integer number of Tz/2, the coefficient is equal to
ej(`-1)e(k-1) where 0(k)=2-xk/-,,rM-, otherwise
= when (i-1) 6(k-1) is not an integer number of Tc/2, the coefficient is equal
to e' "/2 where n is an integer number which minimizes the value:
(nn/2 - (i-1)8(k-l))2.
We refer to the spread spectrum code corresponding to the coefficients of a
filter representing a binary approximation of a polyphase code as discussed
above as the 'Wi-LAN code Type III' .
23
CA 02238680 1998-05-27
For example when M=64, the above procedure produces the following
filter coefficients:
{1,1,1,1,1,1,1,1,
1, l,j,j,- l,-1,-j,-j,
1,j,-1,-j,1,j,-1,-j,
1,- l,j,-j,-1, l,-j,j,
= A preferred filter in Figure 21 performs a reverse operation to the filter
(1301) in Figure 13.
= Another preferred filter in Figure 21 performs a matching filtering
operation to the filter (1301) in Figure 13.
= A preferred de-randomizer (2102) in Figure 21 is one where the preset
values out of the de-randomizing lookup table (2302) :{...,bk_,,bk,bk+l.===}
performs a reverse operation to the randomizer (1101) in Figure 11.
= Another preferred de-randomizer (2102) in Figure 21 is one where the
preset values out of the de-randomizing lookup table (2302):
{...,bk_t,bk,bk+i,... } are equal to the reciprocal of the preset values out
of the
randomizing lookup table (1202) in Figure 12, i.e. bk= 1/ak for all values of
k.
= A preferred diversity technique for MCSS Type III is shown in Figure 24
where we have L branches with one de-ramper (2401) per branch. Each de-
ramper linearly de-ramps the received signal using a linearly deramping
carrier frequency of fixed slope and unique intercept. Each intercept
corresponds to a unique time of arrival of the different multipath
components. The outputs of the L de-rampers are then combined in the
combiner (2402) using any appropriate combining technique such as: co-
phasing combining, maximum ratio combining, selection combining, equal
gain combining, etc. The output of the combiner is then despread using the
de-spreader (2403) and input into the channel decoder/demodulator (2404)
to generate the estimated data symbols.
= A preferred value for fo in Figure 14 is 1/(2tiMTc) where ti is the relative
delay between the first arriving radio signal and the second arriving radio
signal at the receiver, M is the number of coefficients in the spreading
filter
24
CA 02238680 1998-05-27
(1301) in Figure 13 and T, is the duration of one chip (or equivalently it is
the unit delay in the spreading filter (1301)). In other words, the symbol
rate at both the input and the output of the spreading filter (1301) is 1/ Tc.
A person skilled in the art could make immaterial
modifications to the invention described in this patent document
without departing from the essence of the invention that is
intended to be covered by the scope of the claims that follow.
