Apple, Inc. v. Motorola, Inc. et al
Filing
97
Declaration of Carlos A. Rodriguez filed by Defendants Motorola Mobility, Inc., Motorola, Inc. re: 96 Claims Construction Initial Brief, 95 Motion Requesting Claims Construction (Attachments: # 1 Exhibit 1 - Patent No. 6,275,983, # 2 Exhibit 2 - Patent No. 5,969,705, # 3 Exhibit 3 - Patent No. 5,566,337, # 4 Exhibit 4 - Patent No. 5,455,599, # 5 Exhibit 5 - Patent No. 6,424,354, # 6 Exhibit 6 - Reissued Patent No. RE 39,486, # 7 Exhibit 7 - Patent No. 5,929,852, # 8 Exhibit 8 - Patent No. 5,946,647, # 9 Exhibit 9 - Patent No. 5,481,721, # 10 Exhibit 10 - Patent No. 6,493,002, # 11 Exhibit 11 - Patent No. 6,175,559, # 12 Exhibit 12 - Patent No. 5,490,230, # 13 Exhibit 13 - Patent No. 5,319,712, # 14 Exhibit 14 - Patent No. 5,572,193, # 15 Exhibit 15 - Excerpts from '983 Patent Prosecution History, # 16 Exhibit 16 - Excerpts from '354 Patent Prosecution History, # 17 Exhibit 17 - Excerpts from '486 Patent Prosecution History, # 18 Exhibit 18 - Excerpts from '230 Patent Prosecution History, # 19 Exhibit 19 - Apple's Infringement Contentions Claim Chart for '983 Patent, # 20 Exhibit 20 - Apple's Infringement Contentions Claim Chart for '705 Patent, # 21 Exhibit 21 - Apple's Infringement Contentions Claim Chart for '337 Patent, # 22 Exhibit 22 - Apple's Infringement Contentions Claim Chart for '599 Patent, # 23 Exhibit 23 - Apple's Infringement Contentions Claim Chart for '354 Patent, # 24 Exhibit 24 - Apple's Infringement Contentions Claim Chart for '486 Patent, # 25 Exhibit 25 - Apple's Infringement Contentions Claim Chart for '852 Patent, # 26 Exhibit 26 - Apple's Infringement Contentions Claim Chart for '647 Patent, # 27 Exhibit 27 - Apple's Infringement Contentions Claim Chart for '721 Patent, # 28 Exhibit 28 - Apple's Infringement Contentions Claim Chart for '002 Patent, # 29 Exhibit 29 - Excerpts from NeXTSTEP Object-Oriented Programming and the Objective C Language, # 30 Exhibit 30 - July 30, 2010 ITC Order Construing Terms of Asserted Claims in Inv. No. 337-TA-704, # 31 Exhibit 31 - April 4, 2011 Joint Motion to Amend Filed in ITC Inv. No. 337-TA-710, # 32 Exhibit 32 - Excerpts from '002 Patent Prosecution History, # 33 Exhibit 33 - Patent No. 5,588,105, # 34 Exhibit 34 - Patent No. 5,659,693, # 35 Exhibit 35 - Henderson & Card Article, # 36 Exhibit 36 - Patent No. 5,202,961, # 37 Exhibit 37 - Patent App. No. 08/316,237) (Hansen, Scott)
EXHIBIT 11
111111
(12)
United States Patent
Brown
(54)
1111111111111111111111111111111111111111111111111111111111111
US006175559Bl
(10)
(45)
METHOD FOR GENERATING PREAMBLE
SEQUENCES IN A CODE DIVISION
MULTIPLE ACCESS SYSTEM
(75)
Inventor:
(73)
Patent No.:
US 6,175,559 Bl
Date of Patent:
Jan.16,2001
References Cited
(56)
U.S. PATENT DOCUMENTS
5,260,976 * 11/1993 Dolivo et a!. .......................... 375/94
5,457,704 * 10/1995 Hoeher eta!. ......................... 371/43
5,790,537 * 8/1998 Yoon et a!. .......................... 370/342
Tyler Brown, Mundelein, IL (US)
Assignee: Motorola, Inc., Schaumburg, IL (US)
* cited by examiner
( *)
Notice:
Under 35 U.S.C. 154(b), the term of this
patent shall be extended for 0 days.
(21)
Appl. No.: 09/348,571
(22)
Filed:
(51)
(52)
(58)
Int. Cl? ...................................................... H04J 13/00
U.S. Cl. ............................................. 370/335; 370/208
Field of Search ..................................... 370/320, 335,
370/342, 479, 393, 441, 208, 203; 375/140,
141, 146, 147
Jul. 7, 1999
202
Primary Examiner-Douglas W. Olms
Assistant Examiner-Ken Vanderpuye
(74) Attorney, Agent, or Firm-Kenneth A Haas
(57)
ABSTRACT
The present invention provides a method for generating
preamble sequences in a code division multiple access
system. The method includes forming an outer code in a
mobile station. The mobile station forms an inner code. The
mobile station multiplies the outer code to the inner code to
generate the preamble sequence.
8 Claims, 3 Drawing Sheets
200
201
PREAMBLE
GENERATOR
. .IN. ___,. FO~R~UA~T~IO...,_N
.
SOURCE
LOCAL
OSCILLATOR
210
SPREADING
CODE
SPREADING
CODE
CHANNEL
DECODER
219
ESTIMATED
INFORMATION
BITS
220
U.S. Patent
Jan. 16,2001
US 6,175,559 Bl
Sheet 1 of 3
100
DELAY N SYMBOLS
c (k)
c; {k}
DELAY 2N SYMBOLS
DELAY
{M-t)N
SYMBOLS 1---____.,
c (m-1}}
0
1
~IG.
-PRIOR ART-
300
co (k)---,-- c (k)
c; (k)
~IG.
3
401...-----------..
FORM AN OUTER CODE
400
403...-------L-----..
FORM AN INNER CODE
405.---_ _ ____.__ _ _ _---,.
MULTIPLY OUTER CODE TO INNER CODE
TO GENERATE PREAMBLE SEQUENCE
~IG.
4
U.S. Patent
Jan.16,2001
US 6,175,559 Bl
Sheet 2 of 3
200
202
'-""IN=Fo~RM:-:-::A O~N
T=I
SOURCE
zriG. 2
SPREADING
CODE
ESTIMATED
INFORMATION
BITS
220
SPREADING
CODE
zriG. s
50J r - - - - - - - - - - - - - - - - - . ,
MULTIPLY RECEIVED PREAMBLE BY AN OUTER CODE
505
CORRELATE RESULTING SIGNAL WITH A SERIES
OF M ORTHOGONAL SIGNALS
507.----_ _____._ _ __,
MULTIPLY CONSECUTIVE SYMBOLS
500
511
CALCULATE PHASE OF THE RESULTING
COMPLEX NUMBER
513
\...r-M-UL-TI-PL-Y-T-HE-P-HA_S_E-BY-TH-E-S-YM-BO-L-P-ER-10---,D
515
DIVIDE BY 211 TO OBTAIN THE DIFFERENCE
BETWEEN THE TRANSMITTER AND THE RECEIVER
OSCILLATOR FREQUENCIES
U.S. Patent
Jan.16,2001
Sheet 3 of 3
US 6,175,559 Bl
600
603
I
------,----
601
1
I
I
I
s 7s1(k) ~
~ 0(k)
ONE EMBODIMENT OF THE INVENTION WITH K=B, N=48, M=6, L=4
~IG.
6
US 6,175,559 Bl
1
2
METHOD FOR GENERATING PREAMBLE
SEQUENCES IN A CODE DIVISION
MULTIPLE ACCESS SYSTEM
precision, and allow the receiver to determine which transmitter is about to begin transmission.
A prior art preamble generator which generates binary
signals of +1 and -1s is shown in FIG. 1. The generator
consists of two orthogonal Gold code generators. The inner
code, c;(n), comprises 256 chips that are modulated by 16
symbols, C 0 (m), corresponding to one transmitter's code, C 0 •
The total code is therefore:
FIELD OF THE INVENTION
5
The present invention relates generally to communication
systems, and more particularly to a method for generating
preamble sequences in a communication system.
BACKGROUND OF THE INVENTION
10
M-1
c(k) =
~
c;(k- mN)co(m)
Access channels in Code Division Multiple Access
m=O
(CDMA) systems typically include the transmission of a
short signal known to the base station before the transmission of the information. This allows the base station to detect
The inner code is typically common to all transmitters.
15
the presence of a user who has data to transmit. Because
The preamble output from this generator suffers from sevmultiple mobile stations may be trying to access this channel
eral problems. First, the autocorrelation function has large
simultaneously, each user must use a different code. These
peaks at multiples of 256 chips, which makes the accuracy
codes must be designed such that the correlator needed in the
of the estimated arrival time of the transmission poor.
base station must be of relatively low complexity. The codes
Second, small differences between transmit and receive
20
must also be robust to large differences between the carrier
oscillator frequencies cause the receiver to misidentify
frequency of the received signal and the base station's
which transmitter is sending the preamble.
receiver oscillator. They should also lend themselves to
Consequently, a need exists for a method for generating
simple implementation of automatic frequency control cirpreamble sequences in a spread spectrum communication
cuits.
25 system. Further, a need exists for a method for estimating the
In the transmitter of a typical spread spectrum commudifference between the carrier frequency of the received
nication system, a source of information bits is first channel
signal and the receiver oscillator frequencies.
coded and then used to modulate a signal which has a
bandwidth on the order of the information rate. Coherent,
BRIEF DESCRIPTION OF THE DRAWINGS
noncoherent, or differential modulation may be used. This 30
FIG. 1 depicts a preamble generator in accordance with
signal is then spread to a wider bandwidth by multiplication
the prior art;
with a spreading code. The signal is then translated in
FIG. 2 depicts a spread-spectrum communication system
frequency to a carrier frequency determined by the freincluding a preamble generator in accordance with the
quency of a local oscillator and transmitted through an
antenna. The signal goes through a channel where it may be 35 preferred embodiment of the present invention;
modified by additive noise, changes in amplitude and phase
FIG. 3 depicts a preamble generator in accordance with
as occurs in multipath fading, and changes in carrier frethe preferred embodiment of the present invention;
quency as when the transmitter is in motion relative to the
FIG. 4 depicts a flow chart depicting the preferred method
receiver. The output of the channel is mixed to baseband
for generating preamble sequences in accordance with the
with a receiver oscillator whose frequency is known by 40 preferred embodiment of the present invention;
some means to be close to that of the transmitter oscillator.
FIG. 5 depicts a flow chart depicting the preferred method
It is then fed to a receiver which, by some means, knows the
for estimating the difference between the carrier frequency
arrival time of this signal. The receiver first despreads the
of the received signal and the receiver oscillator frequency
incoming signal by multiplication with the same spreading
in accordance with the preferred embodiment of the present
code used in transmission. The signal is then demoduated 45 invention; and
and finally decoded to yield estimates of the transmitted
FIG. 6 depicts the inner and outer codes in accordance
information bits.
with the preferred embodiment of the present invention.
The processes of determining the arrival time and carrier
frequency of the received signal are called time and freDETAILED DESCRIPTION OF A PREFERRED
quency acquisition respectively. One method of performing 50
EMBODIMENT
time and frequency acquisition involves the transmission of
The present invention provides a method for generating
a short training signal prior to the transmission of the
preamble sequences in a CDMA communication system.
information-bearing signal. There may be a period of time
The method comprises forming an outer code and an inner
between the preamble and the transmission of information.
This preamble also serves a second purpose in systems 55 code at a mobile station. The mobile station then multiplies
the outer code by the inner code to generate a preamble
where the receiver does not know when a transmission will
sequence.
begin. In some systems, such as IS-95C and WCDMA
systems, there may be a number of transmitters which
The present invention can be better understood with
periodically begin transmissions. By looking for the presreference to FIGS. 2-6. FIG. 2 illustrates a spread-spectrum
ence of the preamble, the receiver can determine if a 60 communication system 200 including a preamble generator
transmission is about to begin and if so from which trans201 in accordance with the preferred embodiment of the
mitter to expect further transmission.
present invention. In the preferred embodiment of the
The signal generated by the preamble generator should be
present invention, communication system 200 utilizes a
easily detectable by the receiver, allow the receiver to
Code Division Multiple Access (CDMA) system protocol.
determine the timing of the transmission with high precision 65 One such protocol is described in "Personal Station-Base
and accuracy, allow the receiver to determine the carrier
Station Compatibility Requirements for 1.8 to 2.0 GHz Code
frequency of the received signal with high accuracy and
Division Multiple Access (CDMA) Personal Communica-
US 6,175,559 Bl
3
4
tion Systems" (American National Standards Institute
described in "Principles of Communication Systems" by
Taub and Schilling, pubblished in 1986 by McGraw Hill,
(ANSI) J-STD-008). In alternate embodiments, communiherein incorporated by reference. In an alternate embodication system 200 may utilize other digital spread spectrum
ment of the present invention, the code words are taken from
cellular communication system protocols such as, but not
limited to, developing 3G standards such as the CDMA2000 5 a set of orthogonal Gold codes of length P. The codewords
may also be derived from a set of orthogonal codewords by
vision and Wideband CDMA for UMTS.
upsampling. If w is a codeword of length P 1 from a set of
Communication system 200 includes an information
orthogonal codewords, then the codeword, s, which has
source 202 that provides a digital signal. The digital signal
length P equal to a multiple of P 1 can be formed by
is input to channel coder 203, which performs channel
duplicating elements of w:
coding on the information as well known in the art. The 10
output from channel coder 203 is sent to modulator 205,
p
n = 0, 1, ... , ?; -1, k = 0, 1, ... , P1 -1
which modulates the information as is well-known in the art.
The modulated data is then sent to spreader 207, which
spreader the modulated information utilizing a spreading
15
The preamble generator of the present invention can be
code.
implemented in custom hardware, programmable hardware,
Mixer 209 receives a signal from either preamble genor software in a microprocessor.
erator 201 or spreader 207. This is controlled by switch 204.
It is not necessary for the vectors s 1 to be orthogonal,
Mixer 209 mixes the information utilizing a local oscillator
vectors which have low crosscorrelation can also be used.
210, and sends the mixed signal over the air from a trans20 The invention can also employ quadrature codes instead of
mitter to a receiver via antenna channel 211.
codes which only take on values of +/-1.
Channel 211 sends the signal to mixer 213. Mixer 213
FIG. 4 depicts a flow chart 400 depicting the preferred
method for generating preamble sequences in accordance
mixes the signal, and sends the mixed signal to despreader
with the preferred embodiment of the present invention.
215. Despreader 215 despreads the signal utilizing the same
1
spreading code used to spread the signal. The despread 25
signal is then sent to a demodulator 217, which demodulates
respect to FIG. 6 above. The mobile station then forms ( 403)
the signal. The demodulated signal is then sent to channel
an inner code, as described above with respect to FIG. 6. The
decoder 219, which decodes the signal to generate informamobile station then multiplies ( 405) the outer code by the
tion bits 220.
inner code to generate a preamble sequence. The process
A preamble generator 201 in accordance with the pre- 30 then ends (499).
ferred embodiment of the present invention is shown in FIG.
FIG. 5 depicts a flow chart 500 depicting the preferred
3. Preamble generator 201 preferably includes two codes.
method for estimating the difference between the carrier
Both codes are preferably of length N chips, where N is the
frequency of the received signal and the receiver oscillator
total number of symbols in the preamble. The preamble
frequency in accordance with the preferred embodiment of
chips c(k) are given by
35 the present invention. Flow chart 500 is preferably done at
a base station. The base station receives (501) a preamble
from a mobile station. The mobile station multiplies (503)
the received preamble by an outer code matching the outer
By choosing c;(k) and C0 (k) appropriately, the deficiencies
code used by the base station. The base station then correwith the prior art scheme can be removed.
As an example of the preferred embodiment, FIG. 6 40 lates ( 505) the resulting signal with a series of M orthogonal
signals to obtain a series of M correlated output symbols.
depicts inner code 601 c;(k) and the outer code 603 C0 (k). In
The base station then multiplies (507) consecutive correthe preferred embodiment as depicted in FIG. 6, outer code
lated output symbols with the first symbol in each pair being
603 is periodic with period K chips and is preferably formed
complex conjugated. The base station averages (509) (M-1)
from sections of a maximal-length sequence, but is alter45 results. The base station then calculates (511) the phase of
nately a Gold or Kasami sequence. Outer code 603 is
the resulting complex number. The mobile station then
preferably common for all transmitters. Inner code 601,
multiplies (513) the phase by the symbol period.
which is preferably different for different transmitters, prefThe base station then divides (515) by (2n) to obtain the
erably comprises a series of M orthogonal codewords of
difference between the transmitter and the receiver oscillator
length P:
50 frequencies. The process then ends (599).
Thus, the present invention provides a means of generatM-1
ing preamble sequences that can be detected by a base
c;(k) = ~ si(k- jP)
j=O
station with simple circuitry. In addition, when the transmitter and receiver oscillator frequencies are not exactly
55 equal, the preamble received at the base station appears very
where fl, j=0,1, ... ,M-1, is a set of orthogonal codewords.
different from, or highly uncorrelated with, the other preIt is not-required that the orthogonal codewords are unique.
ambles in the set. The preambles also allow the difference
If the total number of transmitters that transmit to the
between the transmitter and receiver oscillator frequencies
receiver is L, then their L inner codes c/(k), preferably
to be calculated in a straightforward manner at the base
comprises a series of orthogonal codewords:
60 station.
While this invention has been described in terms of
M-1
certain examples thereof, it is not intended that it be limited
ci(k)= ~s{(k-jP) 1=1,2, ... ,L-1
to the above description, but rather only to the extent set
j=O
forth in the claims that follow.
65
I claim:
1. A method for generating preamble sequences m a
These codewords are preferably taken from a set of
Hadamard codewords of length P. Hadamard codewords are
CDMA system, the method comprising the steps of:
~~~l~~~~~i~~~~~!~(~~~~ In doo~:ra~o~:~~i~::~:~~~· ~~~
US 6,175,559 Bl
6
5
forming an outer code in a mobile station, wherein the
M-1
outer code is formed from a generator from the group
c;(k) = ~ w1(k- jP)
consisting of a maximum length sequence generator, a
j=O
Kasami sequence generator, and a Gold sequence gen5
erator;
forming an inner code in the mobile station; and multiwhere wj, j=0,1, . . . ,M-1 are a set of Hadamard
plying the outer code by the inner code to generate a
codewords of length 16, M=256, and P=16.
preamble sequence.
2. A method for generating preamble sequences in a
7. A method for estimating the difference between the
CDMA system in accordance with claim 1, wherein the 10 carrier frequency of the received signal and the receiver
period of the outer code comprises k symbols, wherein k is
oscillator frequencies comprising:
a positive integer.
multiplying a received preamble by an outer code;
3. A method for generating preamble sequences in a
CDMA system in accordance with claim 1, wherein the
correlating the resulting signal with the series of M
inner codes are formed as a series of M orthogonal code
orthogonal signals;
15
words having a length P, wherein M and P are positive
multiplying consecutive symbols with the first symbol of
integers.
each pair being complex conjugated;
4. A method for generating preamble sequences in a
CDMA system in accordance with claim 1, wherein the
averaging (M-1) results;
inner codes comprise a set of Hadamard code words.
calculating the phase of the resulting complex number;
5. A method for generating preamble sequences m a 20
multiplying the phase by the symbol period; and
CDMA system, the method comprising the steps of:
forming an outer code in a mobile station;
dividing by (2n) to get the difference between the carrier
forming an inner code in the mobile station utilizing the
frequency of the received signal and the receiver oscilfollowing equation:
lator frequency.
25
8. A method for generating preamble sequences in a
M-1
CDMA system, the method comprising the steps of:
c;(k) = ~ s1 (k- jP)
forming an outer code in a mobile station, the outer code
j=O
comprising a 3840 symbol segment of a Gold-sequence
of length 33554431;
30
where sj, j=0,1, . . . ,M-1 are a set of orthogonal
forming an inner code in the mobile station, the inner code
codewords of length P, where M and P are positive
being of the form:
integers; and
multiplying the outer code by the inner code to generate
a preamble sequence.
35
6. A method for generating preamble sequences in a
CDMA system, the method comprising the steps of:
forming an outer code in a mobile station, the outer code
comprising a 3840 symbol segment of an m-sequence
of length 33554431;
40
forming an inner code in the mobile station, the inner code
being of the form:
M-1
c;(k) =
~ Wj(k- jP)
j=O
where wj, j=0,1, . . . ,M-1 are a set of Hadamard
codewords of length 16, M=256, and P=16.
* * * * *