2004-11-04
`
`Project
`
`IEEE C802.16e-04/516
`IEEE 802.16 Broadband Wireless Access Working Group <http://ieee802.org/16>
`
`Title
`
`Unified MIMO Pre-Coding based on Givens Rotation
`
`Date
`Submitted
`
`Source:
`
`Re:
`Abstract
`Purpose
`
`Notice
`
`Release
`
`Patent
`Policy and
`Procedures
`
`2004-11-04
`
`wentong@nortelnetworks.com
`
`Voice: (613)-763-1315
`(613)-765-7723
`Fax:
`
`Mehdi Ansari, Hadi Baligh and Amir K. Khandani
`Wen Tong, Peiying Zhu, Ming Jia, Dongsheng Yu,
`Jianglei Ma ,Mo-Han Fong, Hang Zhang, Brian
`Johnson
`Nortel Networks
`3500 Carling Avenue
`Ottawa, ON. K2H 8E9
`CANADA
`Response to Recirculation Sponsor Ballot
`To unify the closed loop MIMO pre-coding based Givens rotation.
`To incorporate the changes here proposed into the 802.16e D6 draft.
`This document has been prepared to assist IEEE 802.16. It is offered as a basis for discussion
`and is not binding on the contributing individual(s) or organization(s). The material in this
`document is subject to change in form and content after further study. The contributor(s)
`reserve(s) the right to add, amend or withdraw material contained herein.
`The contributor grants a free, irrevocable license to the IEEE to incorporate material contained
`in this contribution, and any modifications thereof, in the creation of an IEEE Standards
`publication; to copyright in the IEEE’s name any IEEE Standards publication even though it
`may include portions of this contribution; and at the IEEE’s sole discretion to permit others to
`reproduce in whole or in part the resulting IEEE Standards publication. The contributor also
`acknowledges and accepts that this contribution may be made public by IEEE 802.16.
`The contributor
`is
`familiar with
`the
`IEEE 802.16 Patent Policy and Procedures
`<http://ieee802.org/16/ipr/patents/policy.html>, including the statement "IEEE standards may
`include the known use of patent(s), including patent applications, provided the IEEE receives
`assurance from the patent holder or applicant with respect to patents essential for compliance
`with both mandatory and optional portions of the standard." Early disclosure to the Working
`Group of patent information that might be relevant to the standard is essential to reduce the
`possibility for delays in the development process and increase the likelihood that the draft
`publication will
`be
`approved
`for
`publication.
`Please
`notify
`the Chair
`<mailto:chair@wirelessman.org> as early as possible, in written or electronic form, if patented
`technology (or technology under patent application) might be incorporated into a draft standard
`being developed within the IEEE 802.16 Working Group. The Chair will disclose this
`notification via the IEEE 802.16 web site <http://ieee802.org/16/ipr/patents/notices>.
`
`Page 1 of 12
`
`SAMSUNG EXHIBIT 1016
`
`

`

`
`2004-11-04
`
`
`
`
`IEEE C802.16e-04/516
`
`Unified MIMO Pre-coding Based on Givens Rotation
`
` 1
`
`Introduction
`
`For the SVD based MIMO pre-coding technique, the MSS is required to send beam-forming V matrix to the BS, due to
`the unitary structure of matrix V, a number of research work have done to quantize the matrix V in order to reduce the
`feedback overhead in the UL. In this contribution, we show that by using Givens decomposition of matrix V, the Givens
`parameter can be further quantized by using simple 1-bit scalar delta modulation to allow the further reduction of the
`redundancy in time/frequency, the differential-Givens (D-Givens) provide an straightforward scalability to arbitrary
`antenna configurations while achieve the much less computational complexity, lower quantization noise and requires less
`feedback resource. The D-Givens method discussed in this contribution is compared with the Householder method
`introduced in [1].
`
`2 Background
`
`2.1 Givens Rotation
`In the following, we assume that the number of BS transmit antennas is M and the number of MSS receive antennas is N
`and the vector representation of the received signal is: Y=HX+n. In the beam-forming MIMO pre-coding method, the BS
`transmitter needs to know the right-singular matrix V, when the channel matrix is singular-value decomposed as H=USVH.
`The number of non-zero singular values is at most min (M,N). The matrix V contains M2 complex elements but based on
`the fact that it is a unitary matrix, the number of independent variables is M(M-1) real values. By using the Givens
`decomposition, the matrix V is decomposed to a set of M(M-1)/2 unitary matrices. Each matrix is an identity matrix except
`for four of its elements and can be represented by two real values. Besides their ability to decompose the unitary matrix to
`the minimum number of parameters, the resulting parameters are statistically independent. The independence property
`facilitates the quantization procedure. In this contribution, we chose a Givens representation as:
`q
`ˆ
`j
`ˆ
`ˆ
`es
`c
`ˆ
`ˆ
`c
`es
`=
`where the distribution of qˆ and cˆ are independent and
`, in particular, qˆ is uniformly distributed and cˆ
`1 c
`s
`is non-uniformly distributed. Based on the statistical distribution of Givens, the optimum quantizer can be designed to
`achieve maximum compression ratio.
`
` 
`
`,(
`cG
`
`q
`
`)
`
`=
`
`
`
` 
`
`q
`ˆ
`
`j
`
`2
`
`2.2 Delta Modulation
`The Givens parameters qˆ and cˆ are further compressed by using the simplest delta modulator to exploit the channel
`correlation in time or frequency domain, the delta modulator is shown in Figure 1.
`
`
`
`
`
`inputinput
`
`
`4/5/6 Bit Scalar 4/5/6 Bit Scalar
`
`QuantizerQuantizer
`
`
`+1 -1 +1 -1
`
`QuantizerQuantizer
`
`
`
`CQICHCQICH
`
`
`
`Every k frameEvery k frame
`
`
`
`Z-1Z-1
`
`
`
`Accumulator Accumulator
`
`
`
`Every k frameEvery k frame
`
`
`
`1
`
`
`
`Page 2 of 12
`
`-
`-
`-
`

`

`
`2004-11-04
`
`
`
`
`Figure 1 Delta Modulator
`
`IEEE C802.16e-04/516
`
`3 Proposed Solution
`For the unitary pre-coding feedback, the MSS is required to perform the Givens decomposition of unitary
`matrix, the Givens expansions can be truncated (variable number of Givens rotations) to allow feedback partial
`or full the unitary pre-coding vectors. The parameters of each Givens rotations can be quantized and
`compressed by scalar quantizer such as delta modulation and feedback to BS. The BS reconstructs the unitary
`pre-coding vectors/matrix.
`
`4 Advantages
`
`
`• Scalability:
`o Scalable to MIMO pre-coding with large number of transmit antennas to allow standard future proof.
`o Scalable to MIMO pre-coding stream selection. The Givens expansion can be shortened to scale the
`feedback of partial or full set of the Givens rotations to allow BS to perform sub-space or full-space pre-
`coding
`o Givens decomposition will significantly reduce the complexity since the code books search complexity,
`since for Householder based method increases exponentially with respect of the number of transmit
`antennas, the complexity of Givens rotation based method increases polynomial with respect of the
`number of transmit antennas.
`o Lower quantization noise
`o Lower feedback resource required.
`• Reuse:
`o The Givens rotation engine can be implemented with very efficient ORDIC computing. It can be used to
`compute:
` The decomposition of unitary matrix, such as V for the compression of the feedback of V
`[1],[2],[3]
` The Gentleman-Kung systolic based matrix inversion the receiver based schemes [4],[5]
`
`5 Simulation Results
`The simulation conditions and set-up is listed in Table 1
`
`Table 1 Simulation Set Up
`
`Configurations
`
`Parameters
`
`Comments
`
`Optional BAND AMC
`channel
`
`sub-
`
`
`
`Coding Modulation Set
`
`CC coding , K=7, TB
`
`The band allocation in time-direction
`shall be fixed at center band
`
`Coded Symbol Puncture for MIMO
`Pilot
`
`QPSK ½, QPSK, ¾, 16QAM ½, 16QAM
`R=¾, 64QAM R=1/2, 64QAM R= 3/4
`
`Code Modulation Mapping
`
`Single encoder block with uniform bit-
`loading
`
`MIMO Receiver
`
`MMSE-one-shot for SVD
`
`
`
`
`
`
`
`
`
`2
`
`Page 3 of 12
`
`

`

`
`2004-11-04
`
`
`
`
`
`
`MLD receiver for OL and CL SM
`
`IEEE C802.16e-04/516
`
`FFT parameters
`
`Carrier 2.6GHz, 10MHz, 1024-FFT
`
`
`
`Guard tone 79 left, 80 right
`
`CP=11.2ms, Sampling rate = 8/7, Sub-
`carrier spacing = 11.2kHz
`
`Frame Length
`
`5ms frame, DL:UL=2:1
`
`Feedback delay
`
`2 frames
`
`MIMO Configurations
`
`4x2
`
`Channel Model
`
`ITU-PA, 3km/h, Antenna Correlation: 20%
`Perfect Channel Estimation
`
`Feedback
`
`SVD: perfect pre-coding matrix V without
`quantization
`
`
`
`
`
`
`
`
`
`
`
`
`
`D-Givens: per this contribution
`
`Householder: Ref[1]
`
`
`
`5.1.1 Performance
`The partial simulation results based on 0 frame delay are shown in Figure 2. and Figure 3.
`
`10MHz, 0-Frame delay, Corr. 0.2, Perfect Channel
`Estimation,QPSK, CC
`
`Perf ect SV D QPSK 1/ 2
`
`Perf ect SV D QPSK 3 / 4
`
`D - Givens QPSK 1/ 2
`
`D - Givens QPSK 3 / 4
`
`Ho useho ld er QPSK 1/ 2
`
`Ho useho ld er QPSK 3 / 4
`
`1.00E+00
`
`1.00E-01
`
`1.00E-02
`
`BER
`
`1.00E-03
`
`1.00E-04
`
`-3
`
`-1
`
`1
`
`3
`
`5
`SNR(dB)
`
`7
`
`9
`
`11
`
`13
`
`
`
`Figure 2 Performance Comparison of D-Givens/Householder based pre-coding
`
`
`
`3
`
`Page 4 of 12
`
`

`

`
`2004-11-04
`
`
`
`
`IEEE C802.16e-04/516
`
`10MHz, 0-Frame delay, Corr. 0.2, Perfect Channel
`Estimation,16QAM, CC
`
`Perf ect SV D QA M - 16 1/ 2
`
`Perf ect SV D QA M - 16 3 / 4
`
`D - Givens QA M - 16 1/ 2
`
`D - Givens QA M - 16 3 / 4
`
`Ho useho ld er QA M - 16 1/ 2
`
`Ho useho ld er QA M - 16 3 / 4
`
`1.00E+00
`
`1.00E-01
`
`1.00E-02
`
`BER
`
`1.00E-03
`
`1.00E-04
`
`4
`
`6
`
`8
`
`10
`
`12
`SNR(dB)
`
`14
`
`16
`
`18
`
`20
`
`
`
`Figure 3 Performance Comparison of Givens/Householder based pre-coding
`It can be seen that the D-Givens based method achieve the better performance than the Householder method.
`Figure 4 shows the throughout curve for comparing perfect SVD, D-Givens and Householder based methods
`with 2-frame delay.
`
`
`10MHz,ITU-PA, 3km/h, 2-Frame delay, 4-transmits 2-streams Antenna
`Correlation 20%, Perfect Channel Estimation
`
`4x2x2 Householder (CL)
`4x2x2 D-Givens (CL)
`4x2x2 Perfect SVD (CL)
`
`1.4
`
`1.2
`
`1.0
`
`0.8
`
`0.6
`
`0.4
`
`0.2
`
`0.0
`
`AMC Band Throughput (Mbps)
`
`-2
`
`0
`
`2
`
`4
`
`6
`
`8
`10
`12
`SNR(dB)
`
`14
`
`16
`
`19
`
`22
`
`24
`
`
`
`Figure 4 Comparison of perfect SVD, D-Givens and Householder
`
`5.1.2 Feedback Resource Requirement
`The feedback resources requirement and comparison is shown in Figure 5. As we can see the D-Givens
`requires less feedback resources. See Appendix-A for details.
`
`
`
`
`4
`
`Page 5 of 12
`
`

`

`
`2004-11-04
`
`
`
`
`IEEE C802.16e-04/516
`
`Feedback Resource Comparison
`
`3 Transmit Antenna
`4 Transmit Antenna
`
`16
`
`14
`
`12
`
`10
`
`02468
`
`# of Feedback Bits Per V Matrix
`
`2 streams
`
`3 streams
`
`2-streams
`
`3 streams
`
`Givens
`Household
`Antenna Configuration
`
`
`
`Figure 5 Feedback Resources Comparison
`
`5.1.3 Quantization Error
`In Figure 6, we can see the D-Givens based method has less quantization error than the Householder based
`method, see Appendix-B for details. This reduces the inter-stream interface significantly.
`
`Comparsion of Quantization SNR
`(ITU-PA, 3km/h)
`
`Givens
`Household
`
`25
`
`20
`
`15
`
`10
`
`05
`
`Reconstruction SNR (dB)
`
`N=4,S=3
`
`N=4,S=2
`CL-MIMO Configurations
`
`N=2,S=2
`
`Figure 6 Comparison of Quantization SNR
`
`
`
`5.1.4 Compression Complexity
`Figure 7 shows the computational complexity comparison of Givens based method and Householder based
`method, the major advantages of the Givens based method is the low complexity at MSS side. In this Figure, we
`show the complexity for the direct Givens computation approach, indeed, by using CORDIC technique fast
`Givens rotations can be achieved with even less computing complexity.
`
`
`
`5
`
`Page 6 of 12
`
`

`

`
`2004-11-04
`
`
`
`
`IEEE C802.16e-04/516
`
`Compexity Comparison at MSS
`(Givens vs Househloder)
`
`Givens
`Housholder
`
`1.40E+03
`
`1.20E+03
`
`1.00E+03
`
`8.00E+02
`
`6.00E+02
`
`4.00E+02
`
`2.00E+02
`
`0.00E+00
`
`Number of Multipliser
`
`2x2
`
`3x2
`
`4x2
`
`4x3
`
`CL-MIMO Configurations (MxS)
`
`
`
`Figure 7 Comparison of computational complexity
`
`6 Summary
`In summary, the Differential Givens based unitary pre-coding method has the following advantages.
`• Scalability to allow flexible extension to transmit antenna and data streams
`• D-Givens based unitary pre-coding has significant lower complexity at MSS side
`• D-Givens based unitary pre-coding requires less feedback resource
`• D-Givens based unitary pre-coding generate lower quantization noise
`• D-Givens based unitary pre-coding has better performance
`
`7 Text Proposal
`Start text proposal
`---------------------------------------------------------------------------------------------------------------------------
`[Add a new section 8.4.8.3.6.2 as follows]
`
`8.4.8.3.6.1 Unitary Matrix Pre-coding for 3 and 4 Transmit Antennas
`A unitary matrix V can be applied at BS actual transmit antennas to perform the closed loop MIMO pre-coding with s
`(cid:213) (cid:213)
`= S
`=
`1
`
`
`
`baj, ),
`
`
`
` where
`
`P i
`
`iG ,(
`
`
`+=
`1
`
`transmit streams. The V matrix is expanded by using Givens decomposition as:
`
`V
`
`i
`
`j
`
`, the delta modulation is further applied to the
`
`
`
`
`
`
`
`0
`M
`
`2
`ea
`M
`
`a
`M
`
`0
`
`L
`
`jb
`
`L
`
`0
`M
`
`0
`M
`
`L
`
`0
`MO
`
`L
`
`1
`
`6
`
`L
`
`0
`M
`
`-- -
`
`a
`M
`
`1
`
`jb
`
`2
`ea
`M
`
`1
`
`L
`
`O
`
`L
`
`0
`
`L
`
`L
`
`1
`OM
`
`0
`M
`
`0
`M
`
`0
`
`L
`
`L
`
`L
`
`
`
`
`
`
`
`,(
`iG
`
`,
`),
`baj
`
`=
`
`
`
`Page 7 of 12
`
`-
`

`

`
`2004-11-04
`
`
`
`parameters
`
`)(ka
`
` and
`
`)(kb
`
`. For
`
`)(ka
`
`, delta
`
`
`
` )(kd
`
`=
`
`
`
` )(ka
`
`--
`
`(ˆ ka
`
`)1
`
` is quantized by a 1-bit quantizer which outputs
`
`IEEE C802.16e-04/516
`
`∑- =
`
`1 1
`
`k i
`
`
`
` )(~ ka
`
`=
`
`
`
` ([ kdQ
`
`)]
`
`.
`
`
`
`(ˆ ka
`
`=
`
`)1
`
`
`
` )(~ ia
`
`+
`
`a
`
`)1(
`
`is the reconstruction of
`
`
`
`( -ka
`
`)1
`
`. The 1-bit quantization index for
`
`)(~ ka
`
` and
`
`is mapped onto CQICH and fed back to BS to re-generate the unitary matrix V.
`
`~
` )(kb
`
`
`---------------------------------------------------------------------------------------------------------------------------
`End text proposal
`
` Reference
`
`
`
` 8
`
`
`[1] Intel: Improved MIMO Feedback and Per-Stream ABL for OFDMA/OFDM Systems
`[2] Beceem: Closed Loop MIMO Pre-coding
`[3] Motorola: Closed-Loop MIMO for IEEE 802.16e
`[4] TI: An enhanced closed-loop MIMO design for OFDM/OFDMA-PHY
`[5] Nokia: Closed-Loop MIMO Pre-coding with Limited Feedback
`[6] IEEE P802.16-REVd/D5-2004 Draft IEEE Standards for local and metropolitan area networks part 16: Air interface
`for fixed broadband wireless access systems
`
`9 APPENDIX-A
`
`9.1 Feedback Resources
`The feedback resource requirement for Givens based method vs. the Householder based method is listed in
`Table 2.
`
`D-Givens
`2 streams 3 streams 4 streams
`6
`6
`
`10
`12
`12
`18
`24
`20
`26
`36
`44
`
`2-streams
`9
`11
`15
`19
`
`Householder
`3 streams
`12
`15
`21
`27
`
`4 streams
`
`21
`29
`37
`
`
`3
`4
`6
`8
`
`Table 2 Feedback resource
`
`+S
`In this case, with n transmit antennas, we assume that the Householder method requires ∑
`n
`=
`1
`i
`-----
`2
`2
`(
`)
`((
`)
`(
`bit for S streams.
`streams, while the D-Givens method requires
`sn
`sn
`n
`n
`
`))
`
`3
`
`i
`
`bits for S
`
`10 APPENDIX-B
`
`10.1 Compression Quantization SNR
`
`)]
`[
`
`(
`=
`g
` where
`The performance of each schemes are evaluated based on the following metric:
`log*10
`SIR
`mean
`10
`
`lk ,
`g
`is signal-to-interference ratio for the l th sub-carrier of the k th frame due to quantization. It is defined
`
`lk ,
`
`
`
`7
`
`Page 8 of 12
`
`-
`-
`

`

`
`2004-11-04
`
`
`
`
`. The
`
`
`
` ),( lkh
`
` is the ideal channel coefficient, and
`
`2
`
`IEEE C802.16e-04/516
`
`
`
` ),( lkh
`
`is reconstructed channel coefficient
`
`by
`
`g
`
`,
`lk
`
`=
`
`|
`
`2
`
`
` |),( lkh
`(cid:217)-
` ),( lkh
`|
`
`
` |),( lkh
`for the l th sub-carrier of the k th frame, respectively.
`
`
`Case Number
`
`CL-MIMO
`
`
`
`N = 4, S = 3
`
`ITU-PA, 3 km/hr
`
`N = 4, S = 2
`
`N = 2, S = 2
`
`Givens
`
`11.8884dB
`
`12.6734dB
`
`22.6832dB
`
`Table 3 Comparison of Quantization SNR
`
`Household
`
`6.7908dB
`
`6.3509dB
`
`15.9478dB
`
`11 APPENDIX-C
`
`11.1 Complexity Comparison
`The following notations are used in this appendix:
`
`
`N
`
`M
`S
`
`NC
`
`4C = 64
`
`3C = 32
`
`2C = 16
`
`Number of transmitter antenna
`
`Number of receiver antenna
`
`Number of streams
`
`
`
`Size of codebook of unit N-vector
`
` Table 4: Definition of common parameters
`
`11.1.1 Complexity of Household Method
`
`Step 1: Quantization. In this step, vector quantization of a column vector should be done by searching a codebook
`according to the following criterion
`
`=
`
`ˆ
`v
`
`arg
`
`||max
`
`H
`vu
`
`||
`
`
`
`where v is the vector to be quantized, u is the codeword vector in a pre-determined codebook. vˆ is the output of the
`quantizer.
`As household scheme is an iterative approach, the first quantized vector is the first column of matrix V and in next
`iteration, first quantized vector is the first column of a reduced size matrix within FV , where F is the household
`reflection matrix from first iteration. This process could continue until reaching number of streams.
`
`To search the codebook, inner product of the vector to be quantized and each codeword in the codebook should be
`calculated and compared, and the codeword with the largest norm of inner product with vector to be quantized is chosen
`
`
`
`8
`
`Page 9 of 12
`
`(cid:217)
`

`

`
`2004-11-04
`
`
`
`as the quantized vector. The complexity of this process is summarized in Table 5, which takes into account that the first
`element of the vector to be quantized and the first element of each codeword are all real.
`
`
`IEEE C802.16e-04/516
`
`Iterations
`
`1
`
`2
`
`3
`
`Real Multiplications
`NC
`
`1-NC
`
`2-NC
`
`
`
`Complex Multiplications
`
`(
`
`*)1
`N
`NC
`--
`*)2
`NC
`--
`*)3
`NC
`
`(
`
`(
`
`N
`
`N
`
`
`
`
`
`
`
`1
`
`2
`
`Table 5: Code book search complexity for Household method
`
`
`Step 2: Computing Household reflection matrix F . The Household transform matrix can be calculated as follows
`2
`=
`IF
`2||
`||
`w
`-= ˆ
`01[=
` where vˆ is the output of quantization process and
`...
`]0
`I is an identity matrix.
`e
`vw
`e
`. Table 6
`shows the complexity of calculating the Household reflector matrix, in which the fact such as F is a Hermitian matrix is
`considered.
`
`Hww
`
`
`
`T
`
`Iterations
`
`1
`
`2
`
`3
`
`(
`
`(
`
`N
`
`--
`)(2
`N
`
`2/)3
`
`
`
`Complex Multiplications
`-NN
`(
`--
`)(1
`N
`N
`
`2/)1
`
`
`
`2/)2
`
`
`
`Real Divisions
` ( -NN
`
`
`
`
`)1
`
`(
`
`N
`
`--
`)(1
`N
`
`)2
`
`
`
`(
`
`N
`
`--
`)(2
`N
`
`
`
`)3
`
`Table 6: Complexity of calculation of Household reflection matrix
`If the codebook is not large, the Household reflection matrix F can be pre-calculated for each codeword and stored. If this
`is the case, then this part of complexity can be saved.
`
`Step 3: In the 3rd step, the obtained Household reflection matrix F calculated in step 2 is used to convert V in an
`iterative way. The complexity of calculation of FV is summarized in Table 7. In complexity estimation, such factors are
`taken into account that first row and column of the matrix don’t have to be calculated and only those columns (specified
`by number of streams) to be feedback are updated.
`
`Iterations
`
`1
`
`2
`
`3
`
`Complex Multiplications
`--
`
` (NN
`
`)(1
`)1
`R
`---
`)(2
`)(1
`N
`R
`---
`)(3
`)(2
`N
`R
`
`)2
`
`
`
`)3
`
`
`
`(
`
`N
`
`(
`
`N
`
`Table 7: Complexity of Household reflection operation
`Summary: The complexity of Household scheme is summarized in Table 8. As each complex multiplication equals to
`four real multiplications, total complexity given is expressed in terms of real multiplication and divisions. It should be
`noted that number of stream R should be smaller than or equal to N
`
`Steps
`
`Complex Multiplications
`
`Complex Divisions
`
`
`
`9
`
`Page 10 of 12
`
`-
`-
`

`

`IEEE C802.16e-04/516
`
`
`
`
`
`+
`iN
`
`(
`
`)(1
`
`iN
`
`)
`
`
`
`S
`
`∑=
`
`i
`
`1
`
`[
`(4
`
`
`
`CiN )
`
`+
`C
`----
`
`iN )1(
`
`iN )1(
`
`]
`
`
`
`S
`
`∑=
`
`i
`
`1
`
`[
`(2
`
`+
`iN
`
`)(1
`
`iN
`
`)
`
`]
`
`
`
`S
`
`∑=
`
`i
`
`1
`
`S
`
`-∑
`(4
`=
`1
`
`i
`
`+
`iN
`
`--
`
` )( iRiN
`
`)
`
`
`
`)(1
`
`2004-11-04
`
`
`
`
`
`1
`
`2
`
`3
`
`Total
`
`S
`
`)
`
`]
`
`
`
`S
`
`(
`
`)(1
`
`
`
`)
`
`+
`iN
`
`iN
`
`0
`
`∑=
`
`1
`
`i
`
`[
`(
`
`(
`
` CiN 4)
`
`+
`+
`+
`+
`(
`42)(1
`
`i)4
`iN
`R
`C
`----
`)1(
`)1(
`iN
`iN
`
`∑=
`
`1
`
`i
`
`S
`
`[
`(4
`
`(
`
`
` CiN )
`
`+
`+
`+
`(
`)(1
`)
`iN
`iR
`C
`----
`)1(
`)1(
`iN
`iN
`
`)
`
`]
`
`
`
`∑=
`
`i
`
`1
`
`Total (without step 2)
`
`Table 8: Summary of Household complexity in MSS
`The complexity analysis shown in Table 8 is terminal side. For the base station, the feedback information from
`the terminal is used to reconstruct the right singular matrix V and complexity required for that are in fact the
`combined complexity of steps 2 and 3 in Table 8 as in the base station, there is no need for codebook search. If
`household matrix is pre-calculated, then the complexity for base station is only the complexity of step 3 in
`terminal. For convenience, Table 9 lists the complexity at the base station for household method.
`
`
`
`Complex Multiplications
`
`Complex Divisions
`
`Complexity in BS
`
`+
`iN
`
`--
`
` )( iRiN
`
`)
`
`)(1
`
`
`
`
`
`S
`
`-∑
`(4
`=
`1
`
`i
`
`Table 9: Household complexity for BS
`
`11.1.2 Complexity of Givens Rotation
`
`In Givens method, the right side singular matrix V is first decompose into a set of Givens matrices. Each Given matrix
`contains one real element and one complex element, which is quantized using non-uniform scalar quantizer. The
`quantized bits are fed back.
`
`The Givens method can be implemented into two major steps:
`Step 1: In this step, the right side singular matrix V is decomposed into product of a set of Givens matrices. The
`1,2G is calculated, where
`1,2G is the same as
`decomposition is done in an iterative way. The first Givens matrix denoted by
`)1,1(G
`)2,1(G
`)1,2(G
`)2,2(G
`. It is then multiplied with V
`an identity matrix except that it has non-trivial elements at
`,
`,
`,
`to obtain
`
` VGV '=
`
`
`1,2
`
`
`
`)1,2('V
` is zeroed. If the whole matrix V needs to be feedback, the procedure continues iteratively until an identity
`where
`matrix is obtained
`
`=
`GI
`
` VGG...
`
`
`1,3
`1,2
`
`
`
`
`
`NN ,
`
`1
`
`Normally, the elements of the first column is zeroed out one by one first which is then followed zeroing of elements along
`the 2nd column and so on. As V is unitary, only lower triangle of the matrix needs to be zeroed in order to get the identity
`matrix.
`
`
`
`10
`
`Page 11 of 12
`
`-
`-
`-
`-
`-
`-
`-
`-
`-
`-
`-
`-
`-
`-
`

`

`2004-11-04
`
`
`
`
`Table 10 shows the complexity of Givens decomposition. Some considerations are taken into account when getting the
`numbers, which include the fact that as Givens matrix contains only four non-trivial elements, therefore only certain rows
`
` VGV '=
`needs to be calculated when doing each step of Givens decomposition like
`. Also if only certain streams are
`ji,
`needed to feedback, the columns corresponding to rest streams do not need to be updated in Givens decomposition.
`
`IEEE C802.16e-04/516
`
`Real Multiplications
`--
`)(1
`R
`
`)1
`
`
`
`(12
`
`N
`
`(12
`
`N
`
`--
`)(2
`R
`
`)2
`
`
`
`(12
`
`--
`
` iRiN )(
`
`)
`
`
`
`R
`
`∑=
`
`i
`
`1
`
`Givens Decomp
`
`Zero 1st column
`
`Zero 2nd column
`
`….
`
`Total
`
`
`
`Table 10: Complexity of Givens decompostion
`Step 2: After obtaining the set of Givens matrices, the non-trivial elements in them are quantized using scalar non-
`uniform quantization. In fact there are only two independent numbers in each Given matrix which needs quantization. The
`quantization process is trivial and needs some table look-up. Its complexity can be ignored.
`At BS, the feedback information are used to reconstruct the right singular matrix V . In Givens scheme, the reconstruction
`process is similar as the decomposition process in the MSS, namely,
`=
`
`H
`GG
`1,2
`
`H
`1,3
`
`
`
`G...
`
`H
`
`NN ,
`
`V
`
`r
`
`I
`
`1
`
`
`
`So the complexity is similar as shown in Table 10.
`
`11.1.3 Complexity Comparison
`
`The complexity of household and givens are calculated from above analysis for different scenarios. Table 11 list the
`results at terminal side. As can be seen from the table, complexity of Household scheme is in general much higher than
`the Givens scheme at the MSS side. In the scenarios presented here, the Household scheme requires 7 to 32 times of
`complexity required by the Givens scheme. This is particularly intolerable for the MSS where the size the power
`consumption budget is normally very limited.
`
`
`
`N=2 S=2
`
`N=3 S=2
`
`N=4 S=2
`
`N=4 S=3
`
`1. Givens
`
`2. Household without step 2
`
`Ratio: 2 over 1
`
`12
`
`88
`
`7.3
`
`24
`
`372
`
`16.3
`
`36
`
`1168
`
`32.4
`
`96
`
`1320
`
`13.8
`
`Table 11: Complexity comparison at MSS
`
`However, at the BS side, the story is quite different. As shown in Table 12, the Givens and Household schemes require
`similar complexity at BS. The reason for this is that the dominate factor in Household complexity at BS side is due to the
`codebook search. In base station, there is no codebook search for household and therefore, complexity of these two
`schemes is similar.
`
`
`
`N=2 S=2
`
`N=3 S=2
`
`N=4 S=2
`
`N=4 S=3
`
`1. Givens
`
`2. Household
`
`Ratio: 2 over 1
`
`12
`
`8
`
`0.6
`
`24
`
`24
`
`1
`
`36
`
`48
`
`1.3
`
`96
`
`120
`
`1.3
`
`Table 12: Complexity comparison at base station
`
`11
`
`
`
`Page 12 of 12
`
`-
`