United States Patent (19)
`Rohani et al.
`
`54 METHOD AND APPARATUS FORTRELLIS
`DECODING IN A MULTIPLEACCESS
`SYSTEM
`75 Inventors: Kamyar Rohani, Fort Worth;
`Amitava Ghosh, Bedford, both of
`Tex.
`73) Assignee: Motorola, Inc., Schaumburg, Ill.
`21 Appl. No.: 983,199
`22 Filed:
`Nov.30, 1992
`
`s
`
`-
`
`- - - - - - - - - - - - -
`
`- - -
`
`-
`
`- - -
`
`-
`
`- - -
`
`-
`
`- -
`
`-
`
`- - - - -37.77
`
`................
`(58. Field of Search ..................... 375/94, 39, 101, 58,
`375/99; 371/43; 370/18, 110.1, 110.2, 110.3,
`110.4, 111, 74, 19, 20, 21; 455/33.1, 54.1
`References Cited
`U.S. PATENT DOCUMENTS
`5,005,188 4/1991 Clark ..................................... 375/94
`5,029,186 7/1991 Maseng et al...
`... 375/94
`5,103,459 4/1992 Gilhousen et al. .
`... 370/18
`5,134,635 7/1992 Hong et al. ........................... 371/43
`
`56
`
`
`
`USOO5406585A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,406,585
`Apr. 11, 1995
`
`5,136,612 8/1992 Bil.......................................... 370/18
`5,140,615 8/1992 Jasper et al. ........................ 375/100
`Primary Examiner-Stephen Chin
`Assistant Examiner-Hai H. Phan
`Attorney, Agent, or Firm-Raymond J. Warren
`57
`ABSTRACT
`A method is provided of discerning a signal of a desired
`user on a channel having a desired user and a plurality
`of interfering users, each, upon occasion, transmitting
`an identifiable, known pilot symbol. The method in
`
`cludes the steps of determining a channel response of
`
`the desired user and each of the interfering users and
`calculating a metric equal to the squared difference
`between a received signal and a sum of the products of
`o
`transmitted signals and channel responses for the de
`sired user and each of the plurality of interfering users.
`The method also includes the step of discerning the
`- signal of the desired user based, at least in part, upon a
`minimum metric
`o
`
`14 Claims, 2 Drawing Sheets
`
`ERICSSON v. UNILOC
`Ex. 1031 / Page 1 of 6
`
`

`

`U.S. Patent
`US. Patent
`
`Apr. 11, 1995
`Apr. 11, 1995
`
`Sheet 1 of 2
`Sheet 1 of 2
`
`5,406,585
`5,406,585
`
`
`
`
`
`ERICSSON V. UNILOC
`
`Ex. 1031 /Page 2 of6
`
`ERICSSON v. UNILOC
`Ex. 1031 / Page 2 of 6
`
`

`

`U.S. Patent
`
`Apr. 11, 1995
`
`Sheet 2 of 2
`
`5,406,585
`
`
`
`FIG4
`
`- PROR ART m
`
`ERICSSON v. UNILOC
`Ex. 1031 / Page 3 of 6
`
`

`

`METHOD AND APPARATUS FORTRELLIS
`DECODNG IN A MULTIPLE-ACCESS SYSTEM
`
`5,406,585
`2
`X={x1 . . . x} is a transmitted signal vector, N is a
`noise vector, and on is a noise variance, a log-likeli
`hood function of the received vector R, given that X is
`transmitted, has the form as follows:
`
`Such a function can be used to describe the likelihood of
`reception of the vector, R, for a binary communications
`channel with time-varying channel gain and additive
`white Gaussian noise and zero mean signal level.
`While the Viterbi algorithm has worked well, the
`success of the Viterbialgorithm is based upon a white
`Gaussian noise source. In slow frequency hopping, code
`division multiple access (SFH-CDMA) communication
`systems noise, due to interference, may not be Gaussian
`where interfering communication units transmit in syn
`chronism. A need exists for a method of extending maxi
`mum likelihood decoding to SFH-CDMA systems.
`SUMMARY OF THE INVENTION
`A method is provided of discerning a signal of a
`desired user on a channel having a desired user and a
`plurality of interfering users, each, upon occasion,
`transmitting an identifiable, known pilot symbol. The
`method includes the steps of determining a channel
`response of the desired user and each of the interfering
`users and calculating a metric equal to the squared dif
`ference between a received signal and a sum of the
`products of transmitted signals and channel responses
`for the desired user and each of the plurality of interfer
`ing users. The method also includes the step of discern
`ing the signal of the desired user based, at least in part,
`upon a minimum metric.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 comprises a block diagram of a transmitter
`and receiver in accordance with the invention.
`FIG. 2 graphically depicts a summation of two inter
`fering signals on a channel in accordance with the in
`vention.
`FIG. 3 comprises a more detailed block diagram of
`the MU-Viterbi Decoder of FIG. 1.
`FIG. 4 illustrates a prior art cell of a cellular system
`containing a plurality of users.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`The solution to the problem of providing a method of
`using maximum likelihood decoding in a SFH-CDMA
`system lies, conceptually, in determining a channel re
`sponse for each of a desired user 100 and a number of
`interfering users 101 and using such channel response to
`determine a minimum metric. The minimum metric is
`the squared difference between a received signal and
`sum of the products of transmitted signals and channel
`responses.
`In a SFH-CDMA system an incoming signal, R, at
`the receiver is a superposition of the desired signal and
`the interference signals from the non-desired users.
`Such a signal may be represented by the equation as
`follows:
`
`15
`
`10
`
`FIELD OF THE INVENTION
`The invention relates to communication system and
`in specific to cellular communication systems.
`BACKGROUND OF THE INVENTION
`Wireless, radio frequency (rf) receivers are well
`known. Such receivers are constructed to receive and
`demodulate information signals modulated onto an irf
`carrier wave. Modulation methods include such alterna
`tives as frequency shift keying (FSK), quadrature phase
`shift modulation (QPSK), or quadrature amplitude
`modulation (QAM).
`Within a receiver, the information signal is recovered
`by mixing the received signal to a zero-rf state and
`comparing the remaining signal against known stan
`20
`dards. In a FSK system is and 0s may be detected by
`the presence or absence of frequency shifts detected at
`the zero-rf state. In QPSK or QAM systems the re
`ceived signal is mixed to a zero-rf state and the remain
`ing signal compared to constellations of known sym
`bols. The known symbols are multidimensional, using
`25
`amplitude and phase as encoding parameters. The use of
`multidimensional symbols allows QPSK and QAM sys
`tems to transmit multiple bits within each symbol, con
`siderably increasing data throughput within such com
`munication systems.
`30
`A key element of decoding symbols lies in being able
`to sense the timing of transmitted symbols. One method
`of acquiring proper timing in a receiver is provided by
`transmitting known pilot symbols at regular intervals.
`The transmission of known pilots not only provides an
`35
`indication of the start and end of data frames but can
`also be used to determine a complex channel vector, ,
`operating on the known pilot, P, to produce a received
`vector, R.
`The complex channel vector is calculated by dividing
`40
`the received vector, R., by the known transmitted pilot
`vector, P. The quotient is a complex value that may
`then be used to provide a better estimate of symbols
`received between pilots by dividing the received sym
`bols by the complex channel vector.
`45
`As a further aid to reliability in decoding information,
`convolutional coding may be used to improve the noise
`resistance of a communicated signal. A convolutional
`coder with constraint length K=3 and code ratek/n=
`may be used to encode a signal with a high degree of
`50
`reliability over a channel with convolutional coding.
`Decoding of a channel using convolutional coding is
`typically based upon maximum likelihood (Viterbi)
`decoding (see Digital Communications Fundamentals
`and Applications, by Bernard Sklar, Prentice Hall,
`55
`1988, pgs. 315-374). Under Viterbi decoding, state tran
`sitions (t1t) of a convolutionally coded signal are plot
`ted in a trellis diagram in a series of possible paths defin
`ing a received signal at a time, ti. Under the Viterbi
`algorithm a metric is calculated defining a measure of
`60
`similarity, or distance, between a received signal at time
`ti, and all the trellis paths entering each state at time ti.
`The metric is then used to eliminate those trellis paths
`that could not possibly be candidate paths. The best
`metric path (most likely answer) under the Viterbialgo
`65
`rithm is the path with the lowest cumulative metric.
`In general, in a system where R={r1 . . . ri) is a
`received signal vector, is a constant channel estimate,
`
`ERICSSON v. UNILOC
`Ex. 1031 / Page 4 of 6
`
`

`

`3
`
`M
`
`5,406,585
`4
`(13) and packetizer (14). CD-pilots are inserted into the
`small data bursts in a pilot insertion stage (15). The
`signal is then filtered (16) before transmission over a
`channel (17) to a receiver (20).
`At the receiver (20) after filtering (25) the pilots are
`extracted (24) and a channel vector, , is estimated (23).
`The data, R, after the pilot is removed (24) is de-inter
`leaved (22) before decoding in the multi-user (MU)
`Virterbi decoder (21).
`-
`Decoding within the MU Virterbi decoder (21), in
`accordance with the invention, is based upon the chan
`nel vector, W, and the number of interferers. In general,
`the log-likelihood function is determined in a Channel
`Response means (50) of the MU Virterbi decoder (21)
`and can be expressed as follows:
`
`R = (.x -- S, A)+ N
`where i is channel response of the ith user, X is a
`desired transmitted signal, and X2-XM are interferers. It
`may be noted that the interferers are not Gaussian noise
`sources, but they are information bits (or symbols) pro
`duced by other users.
`10
`The method of using maximum likelihood decoding
`in a SFH-CDMA system described herein is applicable
`to a packetized (burst transmission) multiple access
`system. In such a system packets of data are transmitted
`at predefined locations within a data frame for a prede
`15
`fined duration where each packet is composed of n
`information bits (symbols). It is assumed that due to
`short duration of these packets, the channel characteris
`tics remain constant. Such an assumption can be made
`with reasonable accuracy in cellular communication
`20
`channels for packet sizes with duration's shorter than 2
`S.
`Such an assumption is supported by results that show,
`for a subscriber unit moving at 35 mph, fading occurs at
`a Doppler rate of 30 Hz. With a hopping rate of 500 Hz
`25
`(2 ms windows) the channel response is relatively con
`Stant.
`Within each packet of data an embedded pilot vector
`of size M is transmitted which may be represented as
`follows:
`30
`
`L
`M
`LR = 21 -1/(2o') ri- i
`
`J
`
`E
`
`I?)
`
`From the log-likelihood function it can be observed that
`the variance (on?) of the receiver noise is constant and
`the channel vector must be known. As such, the maxi
`mum likelihood decoder (21) uses the mean square crite
`rion over all possible reference signals. Here, the refer
`ence signals are the sum of the desired as well as the
`interferers perturbed by the known channel vector. For
`each possible output the Euclidean branch metric, bk(),
`is precalculated in the metric calculator (51) using the
`equation as follows:
`for all j(1,2,... m, bkG)=r-uk(j)
`
`P=p1, p2, ... pM)
`
`where the elements of each pilot (P) are the complex
`vectors from a suitable constellation (e.g., QPSK or
`35
`QAM). These elements may be transmitted at any time
`(position) within the transmitted packet where such
`position is known to the receiver. Pilot vectors are
`chosen independently for different co-channel transmit
`ters such that each transmitting source can be indepen
`dently identified (estimated). Such identifiability may be
`maintained through the selection of orthogonal pilot
`codes for each co-channel user.
`Channel responses, i, of each transmitting user are
`determined by cross correlation of known pilots in a
`45
`received signal at a peak value to produce a channel
`response value, i, for each signal (XI-X). Note that
`the number of pilot vectors, M, is equal to the number
`of interfering users plus desired user. This allows a
`channel vector to be estimated as follows:
`50
`
`W=1, 2, . . .
`
`.
`
`55
`
`which corresponds to the short term channel character
`istics of transmitted signals from the desired as well as
`interfering users.
`FIG. 1 is a block diagram of a multi-user (MU) trans
`mitter (10) using embedded pilots. Included within the
`transmitter (10) are provisions for forward error correc
`tion (FEC) (11), constellation mapping (12), interleav
`ing (13), packetizing (14), pilot insertion (15), and trans
`mit (TX) filtering (16).
`A frame of bits, B, (typically 40 ms of data) is input to
`the FEC (11) where the bits (B) are convolutionally
`coded (e.g., rate=3, K=3). The output of the FEC (11)
`is then modulated using a given constellation mapping
`65
`(12) (e.g., QAM or QPSK). The output (X) of constella
`tion mapping (12) is then interleaved and packetized
`into small data bursts (less than 2 ms) in an interleaver
`
`where
`u0)=11x+...+YMXk.
`and xk is in the set {1,2,... m}
`where m is the number of points in the constellation.
`As an example, for QPSK modulation and two users
`(M=2) there are 16 possible hypothetical received sig
`nals (hypothesis) to choose from. FIG. 2 is a graphical
`representation of 16 possible hypothesis (labeled 1-16)
`derived from the superposition of one QPSK constella
`tion upon another QPSK constellation.
`For each symbol received within the receiver (20) the
`branch metric, bn(j), is calculated in metric calculator
`51 for each of the 16 hypothesis (FIG. 2) using trellis
`decoding or non-trellis decoding. The hypothesis with
`the smallest metric is chosen as the most appropriate
`solution to discern the signal, in discerning means 52.
`Where trellis decoding is used the 16 branch metrics
`are pre-calculated. The pre-calculated branch metrics
`are then used within the trellis structure over successive
`symbols to determine the most likely distance through
`the trellis under a trellis decoding algorithm (e.g., pgs.
`333-337 of Digital Communications Fundamentals and
`Applications by Bernard Sklar, Prentice Hall, 1988).
`A single hypothesis for the case of QPSK modulation
`and three interferers (M=3) is discerned in discerning
`means 52 as shown in FIG. 2. In the case of three inter
`ferers the number of hypothesis is equal to the number
`of points in the constellation (4). In the case of three
`interferers the number of branch metrics rises to 64.
`We claim:
`1. A method of discerning a signal of a desired user on
`a channel having the desired user and a plurality of
`interfering users, each, upon occasion, transmitting an
`
`ERICSSON v. UNILOC
`Ex. 1031 / Page 5 of 6
`
`

`

`10
`
`-
`5,406,585
`6
`5
`rality of interfering users; and, discerning the signal of
`identifiable, known mutually orthogonal pilot symbol,
`such method comprising the steps of determining a
`the desired user based, at least in part, upon a minimum
`channel response of the desired user and at least one of
`metric.
`the plurality of the interfering users based upon trans
`8. The method of claim 7 wherein the step of calculat
`mitted identifiable, known mutually orthogonal pilot 5
`ing a metric further includes calculating a metric for
`symbols of the desired user and at least one of the plu
`each symbol of a symbol constellation of the desired
`rality of interfering users; calculating a metric based
`user and at least one of the plurality of interfering users.
`upon the channel responses of the desired user and at
`9. The method as in claim 8 further including the step
`least one of the plurality of interfering users; and, dis
`of tracing a trellis path for each symbol of the symbol
`cerning the signal of the desired user based, at least in
`constellation of the desired user and at least one of the
`part, upon the metric.
`plurality of interfering users.
`2. The method of claim 1 wherein the step of calculat
`10. The method as in claim 9 further including a step
`ing a metric further includes a step of calculating a
`of accumulating a cumulative metric for each path of a
`metric for each symbol of a symbol constellation of the
`plurality of trellis paths.
`desired user and at least one of the plurality of interfer- 15
`11. The method as in claim 10 wherein the step of
`ing users.
`discerning the signal of the desired user further includes
`3. The method as in claim 2 further including a step of
`a step of selecting the cumulative metric having the
`tracing a trellis path for each symbol of the symbol
`smallest relative value as the trellis path representing
`constellation of the desired user and at least one of the
`the desired signal.
`plurality of interfering users.
`20
`12. The method as in claim 7 further including a step
`4. The method as in claim 3 further including a step of
`of defining the metric as a Euclidean metric.
`accumulating a cumulative metric for each path of a
`13. An apparatus for discerning a signal of a desired
`plurality of trellis paths.
`user on a channel having the desired user and a plurality
`5. The method as in claim 4 wherein the step of dis
`of interfering users, each, upon occasion, transmitting
`cerning the signal of the desired user further includes a 25
`an identifiable, known mutually orthogonal pilot sym
`step of selecting the cumulative metric having the
`bol, such apparatus comprising: means for determining
`smallest relative value as the trellis path representing
`a channel response of the desired user and at least one of
`the desired signal.
`the plurality of interfering users based upon the trans
`6. The method as in claim 1 further including a step of
`mitted identifiable, known mutually orthogonal pilot
`defining the metric as a Euclidean metric.
`30
`symbols of the desired user and at least one of the plu
`7. A method of discerning a signal of a desired user on
`rality of interfering users; means for calculating a metric
`a channel having the desired user and a plurality of
`equal to the squared difference between a received
`interfering users, each, upon occasion, transmitting an
`signal and a sum of the products of transmitted signals
`identifiable, known mutually, orthogonal pilot symbol,
`and channel responses for the desired user and at least
`such method comprising the steps of determining a 35
`one of the plurality of interfering users; and, means for
`channel response of the desired user and at least one of
`discerning the signal of the desired user based, at least in
`the plurality of interfering users based upon the trans
`mitted identifiable, known mutually orthogonal pilot
`part, upon a minimum metric.
`14. The apparatus as in claim 13 wherein the means
`symbol of the desired user and at least one of the plural
`for identifying the signal of the desired user further
`ity of interfering users; calculating a metric equal to the
`40
`comprises means for determining the desired signal by
`squared difference between a received signal and a sum
`reference to a trellis path.
`of the products of transmitted signals and channel re
`sponses for the desired user and at least one of the plu
`
`45
`
`50
`
`55
`
`65
`
`ERICSSON v. UNILOC
`Ex. 1031 / Page 6 of 6
`
`