Multiuser Spatio-Temporal Coding for Wireless Communications
`
`Jibing Wang and Kung Yao
`
`
`
`Department of Electrical Engineering
`University of California, Los Angeles
`
`
`We give some simulation results in section IV. Finally
`conclusions are drawn in section V.
`II. MULTIUSER SPATIO-TEMPORAL VECTOR CODING
`A. Channel Models
`The input-output model for the M-user multiple access ISI
`channel corrupted by additive noise is given by
`
`
`
`Abstract- In this paper, we consider how to design the
`optimal space-temporal communication systems for the multiple
`access channels with inter symbol interference (ISI) under the
`assumption that the transmitters know the channel state
`information (CSI) perfectly. We optimize the spatio-temporal
`vector coding (STVC) and the space-frequency multiple input multiple
`output (MIMO) discrete matrix multitone (DMMT) information
`structure for the multiple access channels such that the total
`information capacity is maximized. The optimization problem is a
`convex programming problem and the iterative waterfilling algorithm
`[10] is employed to find the optimal solution. The simulation results
`show that a remarkable capacity improvement is achievable by the
`joint multiuser spatio-temporal optimization.
`
`I. INTRODUCTION
`Space-time coding has become an active research area recently
`[1, 2]. Most work, including the space-time trellis coding [3] and
`space-time block coding [4], assumes the flat fading channels.
`However in broadband wireless communications, the frequency
`selective channels are encountered. Possible solutions include
`combining the space-time coding with multiple input multiple
`output (MIMO) equalizer [5] or with OFDM [6,7]. On the other
`hand, in cellular communication systems, the multiple access
`interference (MAI) is dominant. How to design the space-time
`codes in multiuser environment is still an open issue.
`
`=
`y
`where { }i and { }v
`
`0= are the transmitted data and the
`mx
`h
`channel impulse response coefficients for the i-th user,
`kn is the
`respectively. v is known as the channel memory and
`additive gaussian noise. In the vector coding case each input
`block of size N is padded with v zeros [8]. Therefore the
`channel model of (1) can be expressed in the matrix form as
`
`=
`1
`
`i
`
`m
`
`=
`
`0
`
`k
`
`m
`
`i m
`
`, (1)
`
`+
`
`n
`
`k
`
`i
`−
`mk
`
`xh
`
`i m
`
`M
`
`v
`
`∑ ∑
`
`
`
`k
`
`n
`n
`
`+
`
`k
`
`
`1
`
`, (2)
`
`
`
`
`
`+
`
`i k
`
`+
`
`1
`
`x
`x
`
`i k
`
`
`
`
`
`0
`
`
`
`
`
`hh
`
`i v
`
`
`
`
`
`k
`
`+
`
`1
`
`=
`
`k
`
`
`M
`
`∑
`
`=
`
`1
`
`i
`
`
`
`y
`y
`
`
`
`0
`i
`0
`
`
`h
`i
`0
`
`
`i v
`
`000
`
`
`
` 
`
`y
`
`−++
`vNk
`
`1
`
` 
`
` 
`
`n
`
`−++
`vNk
`
`1
`
` 
`
` 
`
`
`
`x
`
`i
`−+
`1
`Nk
`
` 
`
`
`
`
`
`0
`h
`i
`0
`
`
`i
`0
`
`
`hh
`
`i v
`
`
`
`0
`
`h
`
`i v
`
`h
`
`
`
`
`
`or more compactly
`
`In [8] the information capacity for wireless MIMO dispersive
`channels is analyzed under the assumption that the channel side
`information is available at both the transmitter and the receiver. The
`asymptotically optimal spatio-temporal vector coding (STVC) and
`the space-frequency MIMO discrete matrix multitone (DMMT)
`information structure are proposed to achieve the channel capacity.
`In this paper, we basically extend the work in [8] to the multiuser
`scenario. We analyze, from the information capacity point of view,
`how to design the optimal spatio-temporal communication
`systems over the multiple access dispersive channels. We assume
`that the transmitters know the channel state information (CSI)
`perfectly. The iterative waterfilling algorithm [10] is employed to
`optimize the STVC and the space-frequency DMMT structures over
`the multiple access channels such that the total information capacity
`is maximized. Our simulation results show that the system capacity
`can be greatly increased by the joint multiuser spatio-temporal
`optimization.
`
`The rest of the paper is organized as follows. Section II
`provides the MIMO multiple access ISI channel models. The
`multiuser spatio-temporal total capacity is maximized by
`employing the iterative waterfilling algorithm. To reduce the
`computation complexity, the multiuser DMMT structure is
`discussed in section III. We prove that the optimal transmitter
`design can be solved by the iterative waterfilling algorithm.
`
`xH
`
`i
`
`i
`
`+
`
`n
`
`. (3)
`
`=
`
`y
`
`∑
`
`=M
`
`i
`
`1
`
`Now, consider the MIMO multiple access ISI channel
`models with MT transmit antennas at each transmitter
`(mobile) and MR
`receive antennas at
`the
`receiver
`(basestation). Assume that the receive vector of each receive
`=
`y
`j
`M
`, and that for the i-th user, the
`antenna is
`,
`,1
`,
`transmit data vector of each
`transmit antenna
`is
`=
`x
`k
`M
`,
`,1
`,
`.
`
`R
`
`j
`
`T
`
`k i
`
`For the i-th user, the channel matrix from the k-th transmit
`j-th
`antenna
`to
`the
`receive antenna
`is denoted by
`=
`=
`=
`H
`j
`kM
`iM
`M
` ,,
`,1
` ,
`,1
`,
` ,
`,1
`,
`.
`
`
`
`
`kj
`i
`
`,
`
`R
`
`T
`
`, (4)
`
` 
`
`
`
`1
`
`y
`
`RMy
`
` 
`
`=
`
`
`
`y
`
`Denote
`
`Authorized licensed use limited to: Purdue University Fort Wayne. Downloaded on March 03,2023 at 00:52:17 UTC from IEEE Xplore. Restrictions apply.
`
`0-7803-7376-6/02/$17.00 (c) 2002 IEEE.
`
`27
`
`276
`
`Smart Mobile Technologies LLC, Exhibit 2016
`Page 1 of 4
`
`

`

`III. MULTIUSER DISCRETE MATRIX MULTITONE
`In the space-time vector coding, the main disadvantage is the
`associated computational complexity of the eigendecomposition.
`Complexity can be greatly reduced by using the discrete matrix
`multitone (DMMT) [8]. In DMMT systems, each length-N input
`)
`block is extended to the length-N+v block by adding the cyclic
` ,1 =
`
`=
`×∈
`R
`xx
`,
`for
`,
`
`prefix. Denote
`i
`M
`,
`kj
`E
`C
`i
`=
`=
`,
`,1
`,
`,
`. Then we have that the insertion of
`,1
`j
`kM
`M
`
`
`,R and
`,H circulant.
`the cyclic prefix makes the matrices
`Definition [11]: A matrix A that has the following form
`A
`A
`
`
`A
`A
` A is circulant N by N
`is a matrix with circulant block if
`=
`=
`matrix for all
`.
`,1
`,
`,
`,1
`,
`k
`jK
`J
`
`
`
` ,1 =
`iR and
`,
`,
`From this definition, we have that for all
`i
`M
`iH are matrices with circulant block. Now our optimization
`problem is to find the set of positive semidefinite matrices
`{ }M
`1=R
` with circulant block under the respective trace
`constraints such that the sum of the total capacity in (7) is
`maximized. Suppose that the noise is the additive white
`gaussian noise (AWGN), and
`=
`R
`0Nn
`We will show that the iterative waterfilling algorithm will
`converge to the positive semidefinite matrices with circulant
`block. First we give without proof some basic properties of
`matrices with circulant block.
`Proposition 1. The product and sum of the matrices with
`circulant block are also matrices with circulant block. This is
`easy to shown since we know that the product and sum of the
`circulant matrices are also circulant matrices.
`From Proposition 1 we can see that the sum capacity
`optimization problem with the additional constraints that
`{ }M
`1=R
` are matrices with circulant block is still a convex
`programming problem.
`Proposition 2 A matrix A is a Hermitian matrix with
`circulant block
`if and only
`if
`it has
`the following
`decomposition
`
`I
`
`. (9)
`
`i
`
`i
`
`*=
`FA
`
`PV '
`
`*
`
`*
`
`FP
`
`, (10)
`
`where F is the block diagonal inverse discrete Fourier
`transform (IDFT) matrix [8] with each diagonal block the
`unitary IDFT matrix; P is the permutation matrix in [8]; V is
`block diagonal, with each block containing the unitary
`matrices; and is a diagonal real matrix.
`Proposition 3. If A is a nonsingular Hermitian matrix with
`circulant block, A-1 is also a Hermitian matrix with circulant
`block. This is easy to show from Proposition 2.
`
`1
`R
`log
`+
`vN
`
`( )*nn
`=
`R
`En
`where * denotes conjugate transpose,
` , and
`(
`)*
`
` ,1 =
`R =
`,
`i
`M
`i E xx
`. Assume the respective
`, for
`input power constraints are
`(
`)
`=R
`
` ,1 =
`i
`Therefore, the sum capacity optimization problem can be
`stated as
`
`E
`
`i
`
`,
`
`
`
`,
`
`i
`
`M
`
`. (8)
`
`max
`
`
`
` imize
`
`1
`+
`vN
`
`log
`
` subject to
`
`trace
`
`
`
`M
`
`=
`1
`
`i
`
`n
`
`i
`
`HRH
`
`i
`
`i
`
`*
`i
`
`−
`
`log
`
`R
`
`n
`
` ,
`
`, for
`
`i
`
`,
`
`M
`
`,
`
`, for
`
`
`
`,
`
`M
`
`.
`
`1
`∑+
`R
`+
`vN
`)
`(
`=R
`
` ,1 =
`E
`i
`0≥
` ,1 =
`iR
`i
`It is not hard to see that the above problem is a convex
`programming problem,
`and
`the
`iterative multiuser
`waterfilling algorithm converges to the optimal solution from
`any starting point [10]. The optimum set of covariance
`matrices can be found by iteratively waterfilling each user’s
`covariance matrix regarding the other user’s signal as
`additional noise. More specifically, { }M
`1=R
` are given as
`iR match to those of
`following: let the eigenvectors of
`−
`
`i
`
`i
`
`1
`
`M
`
`∑+
`
`j
`
`,1
`
`j
`
`i
`
`
`
`RH
`
`*
`i
`
`n
`
`HRH
`
`j
`
`j
`
`*
`j
`
`H
`
`i
`
`, while using the waterfilling
`
`i
`
`i
`
`i
`
`i
`
`i
`
`*
`i
`
`i
`
`=
`≠
`iR . All of the
`algorithm [9] to generate the eigenvalues of
`input covariance matrices are optimized iteratively in this
`manner. We can easily see that { }M
`1=R
` obtained by this
`algorithm are positive semidefinite matrices.
`V VR =
`, then for
`Assume the eigendecomposition of
`the i-th user, the subchannels that should be used for
`transmission are determined by the nonzero elements of the
`iV are
`diagonal matrix
` , and the corresponding columns of
`the optimum transmit filters for those subchannels.
`
`
`
`
`Authorized licensed use limited to: Purdue University Fort Wayne. Downloaded on March 03,2023 at 00:52:17 UTC from IEEE Xplore. Restrictions apply.
`
`=
`
`,
`
`i
`
`,
`,1
`
`
`M
`
`, (5)
`
` 
`
`x
`1
`i
`
`
`x
`
`TM
`i
`
` 
`
`=
`
`x
`
`i
`
`
`
`H
`1,1
`i
`
`
` 
`
`=
`
`H
`
`i
`
`Then for this multiuser MIMO multiple access channel, we
`obtain exactly the same input output relation as (3).
`
`B. Multiuser Spatio-Temporal Total Capacity
`
`The normalized (per transmission) sum capacity for the
`multiple access channels is given by
`
`
`=
`
`I
`
`sum
`
`1
`+
`vN
`
`log
`
`R
`
`n
`
`i
`
`i
`
`trace
`
`M
`
`∑+
`
`=
`
`1
`
`i
`
`HRH
`
`i
`
`i
`
`−
`
`*
`i
`
`, (7)
`
`n
`
`i
`
`i
`
`*
`
`k i
`
`j
`i
`
`(
`
`T
`
`T
`
`=
`
`,
`
`i
`
`,
`,1
`
`
`M
`
`. (6)
`
` 
`
`H
`
`TM
`
`,1
`i
`
`
`1,
`
`H
`
`RM
`i
`
`
`
`H
`
`,
`TMRM
`i
`
`NN
`
`kj
`i
`
`kj
`i
`
`
`
` 
`
`1,1
`
`,1
`
`J
`
`K
`
`1,
`
`
`
`,
`JK
`
`jk ,
`
` 
`
`=
`
`A
`
`
`0-7803-7376-6/02/$17.00 (c) 2002 IEEE.
`
`27
`
`277
`
`Smart Mobile Technologies LLC, Exhibit 2016
`Page 2 of 4
`
`

`

`achievable by utilizing the space-diversity. We also notice
`that the multiuser STVC channel capacity is slightly higher
`than the multiuser DMMT channel capacity. The difference is
`basically due to the transmitted power penalty associated with
`the cyclic prefix.
`
`
`V. CONCLUSIONS
`
`In this paper, the total information capacities of the STVC
`and DMMT over the multiple access ISI channels are
`maximized by optimizing the covariance matrices of all the
`users. The iterative waterfilling algorithm is employed to find
`the optimal solution. The simulation results show that a
`significant capacity gain is achieved by the joint multiuser
`and spatial-temporal optimization. From the optimization we
`obtain the optimal space-time or space-frequency parallel
`channels for each user.
`
`ACKNOWLEDGEMENT
`
`This work was partially supported by NASA-Dryden grant
`NCC-2-374 and a UC CORE grant sponsored by ST
`Microelectronics, INC.
`
`
`
`REFERENCES
`[1] A. Naguib and A.R. Calderbank, “Space-time coding and
`signal processing
`for high data
`rate wireless
`communications,” Wire. Commun. Mob. Comput, pp.13-
`34, Jan 2001.
`[2] Z. Liu, G. B. Giannakis, S. Zhou, and B. Muquet,
`“Space-time
`coding
`for
`broadband wireless
`communications,” Wire. Commun. Mob. Comput, pp.35-
`53, Jan 2001.
`[3] V. Tarokh, N. Seshadri and A.R. Calderbank, “Space-
`time codes for high data rate wireless communication:
`performance criterion and code construction,” IEEE
`Trans. Inform. Theory, vol. 44, pp.744-765, Mar 1998.
`[4] V. Tarokh, H. Jafarkhani and A.R. Calderbank, “Space-
`time block coding
`for wireless communications:
`performance results, ” IEEE JSAC, vol.17, pp.451-460,
`Mar 1999.
`[5] W. Choi and J. M. Cioffi, “Space-time block codes over
`frequency selective Rayleigh fading channels,” in Proc.
`VTC’99: pp. 2541-2545.
`[6] H. Bölcskei and A. J. Paulraj, “Space-frequency coded
`broadband OFDM systems,” in Proc WCNC’00, pp.1-6,
`Sep, 2000.
`[7] H. Bölcskei, D. Gesbert, and A. J. Paulraj, “On the
`capacity of OFDM-based spatial multiplexing systems,”
`IEEE Trans. Commun., accepted for publication.
`[8] G.G. Raleigh and J. M. Cioffi, “Spatio-temporal coding
`for wireless communication,” IEEE Trans. Comm, vol.
`46, pp. 357-366, Mar 1998.
`[9] N. Al-Dhahir and J. M. Cioffi, “Block transmission over
`dispersive channels: Transmit filter optimization and
`realization, and MMSE-DFE receiver performance,”
`IEEE Trans. Inform. Theory, vol. 42, pp. 137-160, Jan
`1996.
`
`Lemma
`
`*
`i
`
`M
`
`∑+
`
`j
`
`,1
`
`j
`
`i
`
`n
`
`HRH
`
`j
`
`j
`
`−
`
`1
`
`*
`j
`
`H
`
`i
`
` is a Hermitian matrix
`
`
`
`
`
`RH
`=
`≠
`with circulant block, if Rn is a Hermitian matrix with
`circulant block, and for all j=1,…,M, Hj are matrices with
`circulant block, and Rj are Hermitian matrices with circulant
`block. The lemma can be easily proved by using Proposition
`1 and 3.
`Now comes the main result.
`Theorem The optimal set of Hermitian matrices { }M
`1=R
` with
`circulant block under the respective trace constraints (8) can
`be found by the iterative waterfilling algorithm such that the
`sum capacity of (7) is maximized.
`Proof: Without loss of generality, we choose the initial value
`of the iterative algorithm to be diagonal matrices. Then from
`the above Lemma, at the first step of the iteration,
`−
`=
`∑+
`RHA
`
`j
`
`M
`
`n
`
`j
`
`j
`
`i
`
`
`
`*
`i
`
`i
`
`i
`
`i
`
`1
`
`H
`
`i
`
` is a Hermitian matrix
`
`
`
`*
`j
`
`HRH
`
`j
`
`=
`≠
`,1
`iA has the
`with circulant block for all i=1,…,M. Therefore
`eigendecomposition form (10) as shown in Proposition 2.
`iR such that
`iR has the
`The iterative waterfilling optimizes
`=
`FPV PVFR
`iA , hence
`, where
`same eigenvectors as
` is a diagonal positive definite real matrix. From
`Proposition 2,
`iR is also a Hermitian matrix with circulant
`block. By induction, we can see that after each iteration step,
`iR is Hermitian and with circulant block for all i=1,…,M.
`We also know that the sum capacity increases after each
`iteration [10]. Since the programming problem is convex, this
`iterative waterfilling will converge to the global optimal
`solution. Therefore, the Hermitian matrices with circulant
`block can be found by the iterative waterfilling algorithm.

`From this theorem, we know that the optimal transmitter
`design for the multiuser DMMT system can be solved by the
`iterative waterfilling algorithm.
`
`
`i
`
`*
`
`*
`
`*
`i
`
`i
`
`i
`
`i
`
`SIMULATION RESULTS
`IV.
`We use a 4-path channel model for all of the users with the
`average power of each path given by {0dB, -0.25dB, -0.6dB,
`-1dB}, and each path obeys the identical independent
`Rayleigh fading. The channel parameters of all the users are
`generated randomly. For the multiuser STVC cases, assume
`that the energy constraints of all the users obey that
`(
`)
`+
`vNS
`=
` ,1 =
`i
`M
`required to transmit the cyclic prefix, the input energy
`constraint for the multiuser DMMT system is assumed as
`NS
`S
`=
`x=
`M
`0N
`we assume that the block length N is equal to 10, while there
`are 5 users in the multiple access channel. The capacity
`versus SNR of the multiuser 3×3 STVC system is compared
`to the capacity of the 2×2 and 1×1 cases in Fig. 1. A similar
`comparison for the multiuser DMMT system is depicted in
`Fig. 2. As we can see, remarkable performance gains are
`
`, for
`
`
`
`,
`
`M
`
`. Due to the extra energy
`
`. Define the SNR as
`
`SNR
`
`. In the simulation
`
`E
`
`i
`
`E
`
`i
`
`x
`
`x
`
`Authorized licensed use limited to: Purdue University Fort Wayne. Downloaded on March 03,2023 at 00:52:17 UTC from IEEE Xplore. Restrictions apply.
`
`0-7803-7376-6/02/$17.00 (c) 2002 IEEE.
`
`27
`
`278
`
`Smart Mobile Technologies LLC, Exhibit 2016
`Page 3 of 4
`
`

`

`[10] W. Yu, W. Rhee, S. Boyd, and J. M. Cioffi, “Iterative
`water-filling
`for Gaussian vector multiple access
`channels, ” In Proc. IEEE ISIT, Jun 2001.
`[11] P. Davis, Circulant matrices. John Wiley & Sons, 1979.
`
`
`
`Mt=1 Mr=1
`Mt=2 Mr=2
`Mt=3 Mr=3
`
`22
`
`20
`
`18
`
`16
`
`14
`
`12
`
`10
`
`Capacity (Bits/Transmission)
`
`02468
`
`0
`
`5
`
`15
`
`20
`
`10
`SNR (dB)
`
`Fig.1. Capacity versus SNR for the multiuser STVC system:
`block length N=10, M=5
`
`
`
`
`
`
`Mt=1 Mr=1
`Mt=2 Mr=1
`Mt=3 Mr=3
`
`0
`
`5
`
`18
`
`16
`
`14
`
`12
`
`10
`
`02468
`
`Capacity (Bits/Transmission)
`
`10
`SNR (dB)
`
`15
`
`20
`
`
`Fig.2. Capacity versus SNR for the multiuser DMMT system:
`block length N=10, M=5
`
`
`
`
`
`Authorized licensed use limited to: Purdue University Fort Wayne. Downloaded on March 03,2023 at 00:52:17 UTC from IEEE Xplore. Restrictions apply.
`
`0-7803-7376-6/02/$17.00 (c) 2002 IEEE.
`
`27
`
`279
`
`Smart Mobile Technologies LLC, Exhibit 2016
`Page 4 of 4
`
`