# Patent

## Title
Singular value decomposing method and related singular value decomposing device

## Abstract

A method for performing a singular value decomposition (SVD) upon a matrix. The method includes the steps of: (a) simplifying the matrix to derive a simplified matrix; (b) performing an iterative matrix multiplication upon the simplified matrix to generate an iterated matrix; (c) extracting a vector of the iterated matrix according to an iteration number of the iterative matrix multiplication; (d) de-correlating the simplified matrix from the vector to update the simplified matrix; (e) repeating steps (b), (c), and (d) until a predetermined number of vectors have been derived; and (f) storing a first unitary matrix determined according to the predetermined number of vectors in the singular value decomposition.

## Background
BACKGROUND
The present invention relates to a singular value decomposing method and related device, and more particularly to a singular value decomposing method having fast-convergence and fewer computations, and a device thereof.
In wireless communication systems, a multiple-input multiple-output (MIMO) transceiver utilizing antenna arrays can significantly enhance the throughput of the transmission data as shown in FIG. 1. FIG. 1 is a diagram illustrating the channels in the antenna arrays in a conventional MIMO system. The transmitter has M t antennas and the receiver has M r antennas. Each of the receiver's antennas Y1 ̃YMr may receive the signal transmitted from each of the transmitter's antennas X1 ̃XMt. In other words, the first transmitter's antennas X1 may have M r transmitting channels h11, h12, . . . , hmr1, and the second transmitter's antennas X2 also have M r transmitting channels h12, h22, . . . , hmr2, and so on. Therefore, the antennas in the MIMO system are utilized to increase the diversity against multi-path fading or spatially separate devices. Furthermore, the linearity of the signal is proportional to the number of antennas utilized at both the transmitter and the receiver. The interference that emerges between the antennas is the main problem of the MIMO system. To solve the inter-interference problem of the MIMO system, various processes are utilized. The singular value decomposition (SVD) process is considered to have the best performance in the elimination of interference. However, the conventional algorithms to solve the singular value decomposition require a large amount of iterative computations, which consequently increase both the converging time and the hardware complexity.
SUMMARY OF THE INVENTION
One of the objectives of the present invention is to provide a singular value decomposing method with fast-convergence and fewer computations, and a related device.
According to an embodiment of the present invention, a method for performing a singular value decomposition (SVD) upon a matrix is disclosed. The method comprises the following steps: (a) simplifying the matrix to derive a simplified matrix; (b) performing an iterative matrix multiplication upon the simplified matrix to generate an iterated matrix; (c) extracting a vector of the iterated matrix according to an iteration number of the iterative matrix multiplication; (d) de-correlating the simplified matrix from the vector to update the simplified matrix; (e) repeating steps (b), (c), and (d) until a predetermined number of vectors have been derived; and (f) storing a first unitary matrix determined according to the predetermined number of vectors in the singular value decomposition.
According to a second embodiment of the present invention, a singular value decomposing device to perform a singular value decomposition (SVD) upon a matrix is disclosed. The singular value decomposing device comprises a first processing circuit, a second processing circuit, a third processing circuit, a fourth processing circuit, a switch circuit, and a storing module. The first processing circuit simplifies the matrix to derive a simplified matrix. The second processing circuit couples to the first processing circuit for performing an iterative matrix multiplication upon the simplified matrix to generate an iterated matrix. The third processing circuit couples to the second processing circuit for extracting a vector of the iterated matrix according to an iteration number of the iterative matrix multiplication. The fourth processing circuit couples to the third processing circuit for de-correlating the simplified matrix from the vector to update the simplified matrix. The switch circuit couples between the fourth processing circuit and the second processing circuit for selectively coupling the simplified matrix to the second processing circuit until a predetermined number of vectors have been derived. The storing module couples to the third processing circuit for storing a first unitary matrix determined according to the predetermined number of vectors in the singular value decomposition.
These and other objectives of the present invention will no doubt become obvious to those of ordinary skill in the art after reading the following detailed description of the preferred embodiment that is illustrated in the various figures and drawings.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a diagram illustrating channels in antenna arrays of a conventional MIMO system.
FIG. 2 is a flowchart illustrating a singular value decomposition (SVD) method upon a channel matrix according to an embodiment of the present invention.
FIG. 3 is a diagram illustrating the singular value decomposing device according to a second embodiment of the present invention.
FIG. 4 is a diagram illustrating the singular value decomposing device according to a third embodiment of the present invention.



DETAILED DESCRIPTION
Certain terms are used throughout the description and following claims to refer to particular components. As one skilled in the art will appreciate, electronic equipment manufacturers may refer to a component by different names. This document does not intend to distinguish between components that differ in name but not function. In the following description and in the claims, the terms “include” and “comprise” are used in an open-ended fashion, and thus should be interpreted to mean “include, but not limited to . . . ”. Also, the term “couple” is intended to mean either an indirect or direct electrical connection. Accordingly, if one device is coupled to another device, that connection may be through a direct electrical connection, or through an indirect electrical connection via other devices and connections.
Please refer to FIG. 2. FIG. 2 is a flowchart illustrating a singular value decomposition (SVD) method 200 upon a channel matrix H, wherein the channel matrix H is a complex matrix modeled by a wireless Multi-input Multi-output (MIMO) system. According to the embodiment of the present invention, the channel matrix H is embodied by an m*m complex matrix, m≧1. In other words, the channel matrix H is modeled by the channel between m transmitter antennas and m receiver antennas, but this is for the purpose of illustration and not meant to be a limitation of the present invention. In other words, those skilled in this art will readily understand that the present invention can also be applied in the channel matrix modeled between any number of transmitter antennas and any number of receiver antennas. Furthermore, the singular value decomposition method 200 of the present invention is for decomposing the channel matrix H into the form of UΣVT, where the matrices U, V are unitary matrix, the matrix Σ is a diagonal matrix, and VT is the transpose conjugate matrix of the matrix V. Provided that substantially the same result is achieved, the steps of the flowchart shown in FIG. 2 need not be in the exact order shown and need not be contiguous; that is, other steps can be intermediate. The singular value decomposition method 200 comprises the following steps:
Step 202: simplify the channel matrix H to derive a simplified matrix;
Step 204: perform n times iterations of an iterative matrix multiplication upon the simplified matrix to generate an iterated matrix; when the n times iterations is finished, go to step 206, in which n≧1 and one iteration of the iterative matrix multiplication comprises the following steps:
Step 2042: multiply the simplified matrix by the simplified matrix itself to generate the iterated matrix;
Step 2044: determine if the n times iterations are finished; if yes, go to step 206, if no, go to step 2046;
Step 2046: re-assign a word-length for storing the iterated matrix to generate a shifted matrix; and
Step 2048: update the simplified matrix utilizing the shifted matrix, go to step 2042;
Step 206: perform a termination checking upon the iterated matrix to determine if all of the unit vectors of the iterated matrix are extracted; if the termination checking shows that all of the unit vectors of the iterated matrix are extracted, go to step 212, if the termination checking shows that not all of the unit vectors of the iterated matrix are extracted, go to step 208;
Step 208: extract and store the unit vector corresponding to the iterated matrix, then proceed to steps 210, 212, 214, and 220;
Step 210: de-correlate the simplified matrix from the unit vector(s) extracted in step 208 to generate a de-correlated matrix and update the simplified matrix utilizing the de-correlated matrix, go to step 204;
Step 212: derive the unitary matrix V of the matrix composed of the plurality of unit vectors extracted in step 208;
Step 214: utilize the unit vector extracted in step 208 to multiply the channel matrix H to generate a resultant vector;
Step 216: extract and store the unit vector corresponding to the resultant vector, go to step 218 and step 220;
Step 218: derive the unitary matrix U of the matrix composed of the plurality of unit vectors generated in step 216;
Step 220: derive and store an eigenvalue of the matrix according to the unit vector generated in step 208 and the unit vector generated in step 216;
Step 222: generate the diagonal matrix Σ by utilizing the plurality of eigenvalues generated in step 220.
Initially, since three variable matrices exist in the channel matrix H, the singular value decomposition method 200 reduces one of the variable matrices of the channel matrix H when the channel matrix H is received in order to simplify the channel matrix H. Therefore, in step 202, a transpose conjugate operation is first performed upon the channel matrix H to generate a transposed matrix HT; and then the channel matrix H is multiplied by the transposed matrix HT to generate the simplified matrix P, as shown in the following equation:




  
    
      
        
          
            
              P
              =
              
              ⁢
              
                
                  H
                  T
                
                ⁢
                H
              
            
          
        
        
          
            
              =
              
              ⁢
              
                V
                ⁢
                
                  
                
                ⁢
                
                  Σ
                  2
                
                ⁢
                
                  V
                  T
                
              
            
          
        
        
          
            
              
                =
                
                ⁢
                
                  
                    ∑
                    M
                  
                  ⁢
                  
                    
                      σ
                      i
                      2
                    
                    ⁢
                    
                      v
                      i
                    
                    ⁢
                    
                      v
                      i
                      H
                    
                  
                
              
              ,
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




wherein M is the rank of the channel matrix H, σi, which composes the diagonal matrix Σ, is the i-th singular value in descending order, meaning that σ1>σ2> . . . >σM, and vi is the i-th column vector of the unitary matrix V. Please note that, although this embodiment is for simplifying the channel matrix H by eliminating the unitary matrix U, this is not meant to be the limitation of the present invention. Those skilled in this art will readily understand that the multiplication between the channel matrix H and the transposed matrix HT can be switched to generate the simplified matrix P that eliminates the unitary matrix V, i.e., P=HHT=UΣ2UT, which also falls within the scope of the present invention.
When the simplified matrix P is obtained, the iterative matrix multiplication is performed upon the simplified matrix P to generate an iterated matrix P2n in the step 204, in which the n times iterations is performed in the iterative matrix multiplication. However, this is not meant to be the limitation of the present invention. In another embodiment of the present invention, the iterative matrix multiplication performs m times iterations upon the simplified matrix P to generate the iterated matrix of P2m. The iterative matrix multiplication is illustrated in the following equation:




  
    
      
        
          
            
              
                P
                
                  2
                  n
                
              
              =
              
              ⁢
              
                
                  (
                  
                    
                      H
                      T
                    
                    ⁢
                    H
                  
                  )
                
                
                  2
                  n
                
              
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  (
                  
                    V
                    ⁢
                    
                      
                    
                    ⁢
                    
                      Σ
                      2
                    
                    ⁢
                    
                      V
                      T
                    
                  
                  )
                
                
                  2
                  n
                
              
            
          
        
        
          
            
              =
              
              ⁢
              
                V
                ⁢
                
                  
                
                ⁢
                
                  Σ
                  
                    2
                    
                      n
                      +
                      1
                    
                  
                
                ⁢
                
                  V
                  T
                
              
            
          
        
        
          
            
              
                =
                
                ⁢
                
                  
                    ∑
                    M
                  
                  ⁢
                  
                    
                      σ
                      i
                      
                        2
                        
                          n
                          +
                          1
                        
                      
                    
                    ⁢
                    
                      v
                      i
                    
                    ⁢
                    
                      v
                      i
                      H
                    
                  
                
              
              ,
            
          
        
      
    
    
      
        (
        2
        )
      
    
  




Since the unitary matrix V does not vary after the n times iterations, it is obvious that the gap between the largest singular value σ1 and other smaller singular values σ2, . . . , σm will be enlarged after the n times iterations are performed upon the simplified matrix P. Therefore, the iterated matrix P2n can be approximated as σ12+1 v1v1T, in which only the vector (i.e., v1) that corresponds to the largest singular value σ1 is left in the iterated matrix P2n. One iteration of the iterative matrix multiplication first multiplies the simplified matrix P by the simplified matrix P itself to generate the first order simplified matrix P2 (i.e., step 2042), and then updates the first order simplified matrix P2 to be the simplified matrix P for performing the next iteration. In practice, however, to avoid the overflow of the most significant bit (MSB) of the first order simplified matrix P2, the step 2046 may require the iteration to re-assign a word-length for storing the first order simplified matrix P2 and for generating a shifted matrix. Then, the shifted matrix is updated to be the simplified matrix P for performing the next iteration until the n times iterations are finished. In other words, a dynamic shift operation is performed upon each iterated matrix in the iteration of the iterative matrix multiplication. More specifically, in step 2046, all the elements in the simplified matrix P should be binary shifted t bits such that the maximum element of |2t*{Re(P), Im(P)}| can be expressed without losing its most significant bit. Furthermore, the step 2044 determines if the n times iterations are finished. If the n times iterations are not finished yet, the iteration must be performed until the n times iterations are completed. When the n times iterations are finished, meaning that the iterated matrix P2n(≅σ12n+1v1v1T) is obtained, the unit vector corresponding to the largest singular value σ1 can be extracted from the iterated matrix P2n in step 208. Before the unit vector can be extracted, termination checking is performed upon the iterated matrix P2n in step 206 to determine if all of the unit vectors corresponding to all of the singular values have been extracted. If all of the unit vectors are extracted, the unitary matrix V of the matrix composed of the plurality of unit vectors is derived in step 212. Otherwise, the unit vector of the iterated matrix P2n is extracted in step 208.
After the unit vector corresponding to the largest singular value σ1 is obtained, the correlated components in the channel matrix H should be eliminated for deriving the next singular value and the corresponding unit vector. Therefore, the unit vector corresponding to the largest singular value σ1 is de-correlated from the simplified matrix P in step 210 to generate a de-correlated matrix Pd and the simplified matrix P is updated utilizing the de-correlated matrix Pd. The following equations illustrate the initial condition of the singular value decomposition method 200 of the present invention:




  
    
      
        {
        
          
            
              
                
                  
                    
                      ∑
                      M
                    
                    ⁢
                    
                      
                        v
                        i
                      
                      ⁢
                      
                        v
                        i
                        T
                      
                    
                  
                  =
                  
                    I
                    M
                  
                
                ,
              
            
          
          
            
              
                
                  
                    
                      v
                      i
                      T
                    
                    ⁢
                    
                      v
                      j
                    
                  
                  =
                  0
                
                ,
                
                  ∀
                  
                    i
                    ≠
                    
                      j
                      .
                    
                  
                
              
            
          
        
      
    
    
      
        (
        3
        )
      
    
  




Therefore, after deriving the unit vectors corresponding to v1 ̃vk, the step 210 further subtracts the unit vectors corresponding to v1 ̃vk from an identity matrix IM to generate a subtracted matrix Psub; and the subtracted matrix Psub is multiplied by the simplified matrix P. Accordingly, the de-correlated matrix Pd can be obtained through the following derivation:




  
    
      
        
          P
          d
        
        =
        
        ⁢
        
          
            (
            
              
                I
                M
              
              -
              
                
                  ∑
                  
                    i
                    =
                    1
                  
                  k
                
                ⁢
                
                  
                    v
                    i
                  
                  ⁢
                  
                    v
                    i
                    T
                  
                
              
            
            )
          
          ⁢
          
            (
            
              
                H
                T
              
              ⁢
              H
            
            )
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            (
            
              
                
                  v
                  
                    k
                    +
                    1
                  
                
                ⁢
                
                  v
                  
                    k
                    +
                    1
                  
                  T
                
              
              +
              
                
                  v
                  
                    k
                    +
                    2
                  
                
                ⁢
                
                  v
                  
                    k
                    +
                    2
                  
                  T
                
              
              +
              ...
            
            )
          
          ⁢
          
            (
            
              
                
                  σ
                  1
                  2
                
                ⁢
                
                  v
                  1
                
                ⁢
                
                  v
                  1
                  T
                
              
              +
              
                
                  σ
                  2
                  2
                
                ⁢
                
                  v
                  2
                
                ⁢
                
                  v
                  2
                  T
                
              
              +
              ...
            
            )
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          (
          
            
              
                σ
                
                  k
                  +
                  1
                
                2
              
              ⁢
              
                v
                
                  k
                  +
                  1
                
              
              ⁢
              
                v
                
                  k
                  +
                  1
                
                T
              
            
            +
            
              
                σ
                
                  k
                  +
                  2
                
                2
              
              ⁢
              
                v
                
                  k
                  +
                  2
                
              
              ⁢
              
                v
                
                  k
                  +
                  2
                
                T
              
            
            +
            ...
          
          )
        
      
    
  




Therefore, the de-correlated matrix Pd can be utilized for deriving the unit vector corresponding to vk+1 in step 204.
Since the iterated matrix P2n is generated continuously in step 204, the unit vectors corresponding to the respective singular values σ1, . . . , σm are obtained and stored one by one in step 208. When all of the unit vectors corresponding to the respective singular values σ1, . . . , σm are obtained, a normalizing operation can be performed upon the unit vectors to generate the eigenvectors v1, . . . , vm, respectively, in which the eigenvectors v1, . . . , vm are utilized to derive the unitary matrix V of the matrix (step 212). Accordingly, the unitary matrix V of the matrix can be obtained. Please note that the step 208 in conjunction with the step 212 is not a limitation of the present invention for obtaining the eigenvectors v1, . . . , vm. In another embodiment of the present invention, each eigenvector vi is obtained through the normalization upon any column or row vector of the iterated matrix P2n obtained in step 204. Furthermore, in another embodiment of the present invention, the eigenvector vi corresponding to the singular value σi can be obtained by simply eliminating the portion of σi2n+1 of the iterated matrix P2n(≅σi2n+1 viviT).
Whenever the unit vector corresponding to the largest singular value σi is obtained in step 208, the unit vector is further utilized to multiply the channel matrix H to generate a resultant vector Pu in step 214 as illustrated in the following equation:

Pu=Hvi=(UΣVT)vi=(Σ12u1v1T+Σ22u2v2T+ . . . +Σm2umvmT)vi=Σi2ui  (4)

Similar to the step 208, the unit vector corresponding to the largest singular value σ1 can be extracted from the resultant vector Pu in step 216. Since the iterated matrix P2n is generated continuously in step 204, the unit vectors corresponding to the respective singular values σ1, . . . , σm are obtained and stored one by one in step 208. When all of the unit vectors corresponding to the respective singular values σ1, . . . , σm are obtained, a normalizing operation can be performed upon the unit vectors to generate the eigenvectors u1, . . . , um, respectively, in which the eigenvectors u1, . . . , um are utilized to derive the unitary matrix U of the matrix (step 218). Accordingly, the unitary matrix U of the matrix can be obtained. Please note that, in another embodiment of the present invention, each eigenvector ui is obtained through the normalization upon any column or row vector of the resultant vector Pu obtained in step 214.
In addition, whenever the unit vectors (corresponding to vi and ui respectively) corresponding to the largest singular value σi are obtained in step 208 and 216, the unit vectors are further utilized to multiply the channel matrix H to generate the singular value σi in step 220 as illustrated in the following equation:

σi=uiTHvi  (5)

When all of the singular value σ1 ̃σm are obtained, the diagonal matrix Σ can be derived in step 222.
According to the above-mentioned disclosure of the present invention, the computation of the singular value decomposition method 200 is division free and square-root free. In other words, no division or square-root operation are performed in the singular value decomposition method 200, thereby lowering the total computational complexity (i.e., multiplication and add (MAC)) to decompose the channel matrix H and having the characteristic of fast-convergence. In addition, the singular value decomposition method 200 is reconfigurable to various sizes of channel matrices, such as 4*4 matrix or 4*3 matrix. Furthermore, since the eigenvectors vi, ui, and σi can be derived separately in the embodiment of the present invention, the singular value decomposition method 200 possesses high parallelism compared with the conventional method.
Please refer to FIG. 3. FIG. 3 is a diagram illustrating a singular value decomposing device 300 according to a second embodiment of the present invention. The singular value decomposing device 300 is utilized for performing a singular value decomposition (SVD) upon a channel matrix to generate a unitary matrix of the channel matrix. In order to describe the present invention more clearly, the singular value decomposing device 300 is utilized to decompose the channel matrix H for generating the unitary matrix V of the first embodiment as shown in FIG. 2. In other words, the channel matrix H is the complex matrix modeled by the wireless Multi-input Multi-output (MIMO) system, and the channel matrix H is an m*m complex matrix, where m≧1, which is modeled by the channel between m transmitter antennas and m receiver antennas, and both these examples are for the purposes of illustration and are not meant to be limitations of the present invention. The singular value decomposing device 300 comprises a first processing circuit 301, a second processing circuit 302, a third processing circuit 303, a fourth processing circuit 304, a switch circuit 305, and a storing module 306. The first processing circuit 301 receives the channel matrix H to simplify the channel matrix H to derive the simplified matrix P as illustrated in the above-mentioned equation (1). The second processing circuit 302 couples to the first processing circuit 301 for performing the n times iterations of the iterative matrix multiplication upon the simplified matrix P to generate the iterated matrix P2n as illustrated in the above-mentioned equation (2). The third processing circuit 303 couples to the second processing circuit 302 for extracting a unit vector of the iterated matrix P2n after n times iterations of the iterative matrix multiplication. The fourth processing circuit 304 couples to the third processing circuit 303 for de-correlating the simplified matrix P from the unit vectors extracted in the third processing circuit 303 to generate the de-correlated matrix Pd. The switch circuit 305 couples between the fourth processing circuit 304 and the second processing circuit 302 for selectively coupling the de-correlated matrix Pd to the second processing circuit 302 until a predetermined number of unit vectors have been derived; and the storing module 306 couples to the third processing circuit 303 for storing the unitary matrix V determined according to the predetermined number of unit vectors extracted in the third processing circuit 303.
Furthermore, the first processing circuit 301 comprises a first arithmetic unit 3011 and a second arithmetic unit 3012. The first arithmetic unit 3011 performs a transpose conjugate operation upon the channel matrix H to generate a transposed matrix HT, and the second arithmetic unit 3012 couples to the first arithmetic unit 3011 for multiplying the channel matrix H by the transposed matrix HT to generate the simplified matrix P. The second processing circuit 302 comprises a third arithmetic unit 3021, and a shifting module 3022. The third arithmetic unit 3021 multiplies the de-correlated matrix Pd by the de-correlated matrix Pd itself for n times to generate the iterated matrix P2n. The shifting module 3022 couples to the third arithmetic circuit 3021 for re-assigning a word-length for storing the iterated matrix P2n to generate a shifted matrix, and updating the de-correlated matrix Pd utilizing the shifted matrix until the iteration number is equal to the predetermined value, i.e., n iterations. The fourth processing circuit 304 comprises a fourth arithmetic unit 3041 and a fifth arithmetic unit 3042. The fourth arithmetic unit 3041 subtracts the eigenvectors (i.e.,




  
    
      ∑
      
        i
        =
        1
      
      k
    
    ⁢
    
      
        v
        i
      
      ⁢
      
        v
        i
        T
      
    
  
  )




derived from the unit vectors extracted in the third processing circuit 303 by an identity matrix IM to generate a subtracted matrix Psub. The fifth arithmetic unit 3042 multiplies the simplified matrix P by the subtracted matrix Psub to generate another de-correlated matrix Pd. The storing module 306 comprises a fifth processing circuit 3061 and a storing unit 3062. The fifth processing circuit 3061 normalizes the unit vectors extracted in the third processing circuit 303 to derive a plurality of eigenvectors v1 ̃vm, respectively. The storing unit 3062 couples to the fifth processing circuit 3061 for storing the unitary matrix V composed of the plurality of eigenvectors v1 ̃vm.

Initially, the switch circuit 305 switches to the fourth processing circuit 304 for coupling the simplified matrix P to the second processing circuit 302. Then, the switch circuit 305 switches to the shifting module 3022. Accordingly, the third arithmetic unit 3021 multiplies the simplified matrix P by the simplified matrix P itself to generate the first order simplified matrix P2, and the first order simplified matrix P2 is then inputted to the shifting module 3022, wherein the shifting module 3022 re-assigns the word-length of the simplified matrix P2 to avoid the overflow of the most significant bit (MSB) of the first order simplified matrix P2. Then, the shifted matrix is generated, and the switch circuit 305 couples the shifted matrix to the third arithmetic unit 3021 for performing the next iteration until the n iteration is finished. In other words, the shifting module 3022 performs the dynamic shift operation upon each iterated matrix in the iteration of the iterative matrix multiplication. More specifically, all the elements in the simplified matrix P should be binary shifted t bits such that the maximum element of |2t*{Re(P), Im(P)}| can be expressed without losing its most significant bit. When the second processing circuit 302 and the switch circuit 305 finish the n times iterations, the third processing circuit 303 further performs the termination checking upon the iterated matrix P2n to determine if all of the unit vectors corresponding to all of the singular values σ1, . . . , σm have been extracted. If not all of the unit vectors corresponding to all of the singular values σ1, . . . , σm have been extracted, the third processing circuit 303 extracts the unit vectors of the iterated matrix P2n. In this case, when the n times iterations are finished, the iterated matrix P2n(≅σ12n+1v1v1T) is obtained, and the unit vector corresponding to the largest singular value σ1 can then be extracted from the iterated matrix P2n in the third processing circuit 303. After deriving the unit vectors corresponding to v1 ̃vk, the fourth processing circuit 304 performs the following calculation to generate the de-correlated matrix Pd:




  
    
      
        
          P
          d
        
        =
        
        ⁢
        
          
            (
            
              
                I
                M
              
              -
              
                
                  ∑
                  
                    i
                    =
                    1
                  
                  k
                
                ⁢
                
                  
                    v
                    i
                  
                  ⁢
                  
                    v
                    i
                    T
                  
                
              
            
            )
          
          ⁢
          
            (
            
              
                H
                T
              
              ⁢
              H
            
            )
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            (
            
              
                
                  v
                  
                    k
                    +
                    1
                  
                
                ⁢
                
                  v
                  
                    k
                    +
                    1
                  
                  T
                
              
              +
              
                
                  v
                  
                    k
                    +
                    2
                  
                
                ⁢
                
                  v
                  
                    k
                    +
                    2
                  
                  T
                
              
              +
              ...
            
            )
          
          ⁢
          
            (
            
              
                
                  σ
                  1
                  2
                
                ⁢
                
                  v
                  1
                
                ⁢
                
                  v
                  1
                  T
                
              
              +
              
                
                  σ
                  2
                  2
                
                ⁢
                
                  v
                  2
                
                ⁢
                
                  v
                  2
                  T
                
              
              +
              ...
            
            )
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          (
          
            
              
                σ
                
                  k
                  +
                  1
                
                2
              
              ⁢
              
                v
                
                  k
                  +
                  1
                
              
              ⁢
              
                v
                
                  k
                  +
                  1
                
                T
              
            
            +
            
              
                σ
                
                  k
                  +
                  2
                
                2
              
              ⁢
              
                v
                
                  k
                  +
                  2
                
              
              ⁢
              
                v
                
                  k
                  +
                  2
                
                T
              
            
            +
            ...
          
          )
        
      
    
  




wherein the second arithmetic unit 3041 subtracts the eigenvectors (i.e.,




  
    
      ∑
      
        i
        =
        1
      
      k
    
    ⁢
    
      
        v
        i
      
      ⁢
      
        v
        i
        T
      
    
  
  )




derived from the unit vectors extracted in the third processing circuit 303 by the identity matrix IM, and the third arithmetic unit 3042 multiplies the simplified matrix P by the subtracted matrix Psub to generate another de-correlated matrix Pd. Then, the switch circuit 305 couples the de-correlated matrix Pd to the second processing circuit 302 for deriving the unit vector corresponding to vk+1.

When the termination checking of the third processing circuit 303 determines that all of the unit vectors corresponding to all of the singular values σ1, . . . , σm have been extracted, the fifth processing circuit 3061 normalizes the unit vectors extracted in the third processing circuit 303 to derive a plurality of eigenvectors v1 ̃vm, respectively. The storing unit 3062 couples to the fifth processing circuit 3061 for storing the unitary matrix V composed of the plurality of eigenvectors v1 ̃vm. Accordingly, the unitary matrix V of the channel matrix H can be obtained. Please note that the eigenvector vi corresponding to the singular value σi can also be obtained without the normalization in the fifth processing circuit 3061. In other words, in another embodiment of the present invention, the fifth processing circuit 3061 simply eliminates the portion of σi2n+1 of the iterated matrix P2n(≅σi2n+1 v1v1T) to obtain the eigenvector vi.
Please refer to FIG. 3 in conjunction with FIG. 4. FIG. 4 is a diagram illustrating a singular value decomposing device 400 according to a third embodiment of the present invention. The singular value decomposing device 400 is utilized for performing the singular value decomposition (SVD) upon the channel matrix H to generate the unitary matrix V, the unitary matrix U, and the diagonal matrix Σ of the channel matrix H as shown in FIG. 2. Similarly, the channel matrix H is the complex matrix modeled by the wireless Multi-input Multi-output (MIMO) system, and the channel matrix H is an m*m complex matrix, where m≧1, which is modeled by the channel between m transmitter antennas and m receiver antennas, and both these examples are for the purposes of illustration and are not meant to be limitations of the present invention. Not including the components of the singular value decomposing device 300, the singular value decomposing device 400 further comprises a sixth processing circuit 307, a seventh processing circuit 308, an eighth processing circuit 309, and a ninth processing circuit 3010. The sixth processing circuit 307 couples to the storing module 306 for multiplying the channel matrix H by the eigenvectors vi to generate the resultant vectors Pu respectively. The seventh processing circuit 308 couples to the sixth processing circuit 307 for deriving the unitary matrix U of the channel matrix H, wherein the unitary matrix U is composed of a plurality of normalized vectors (i.e., eigenvectors) ui generated from normalizing the resultant vectors Pu respectively. The eighth processing circuit 309 couples to the sixth processing circuit 307 for multiplying the channel matrix H by the eigenvectors vi obtained in the storing module 306 and eigenvectors ui obtained in the sixth processing circuit 307 to generate the corresponding singular values σi. The ninth processing circuit 3010 couples to the eighth processing circuit 309 for deriving the diagonal matrix Σ of the channel matrix H according to the singular values σi obtained in the eighth processing circuit 309.
According to the third embodiment as shown in FIG. 3, once eigenvectors vi are generated, the sixth processing circuit 307 multiplies the channel matrix H by the eigenvectors vi to obtain the resultant vector Pu as illustrated by the equation (4), i.e., Pu=σi2ui. After normalizing the resultant vector Pu, the eigenvectors ui can be obtained. Please note that the eigenvectors ui can also be obtained without performing the normalization upon the resultant vector Pu. In another embodiment of the present invention, the eigenvector ui corresponding to the singular value σi can be obtained by simply eliminating the portion of σi2 of the iterated matrix Pu (i.e., σi2 ui).
Then, the unitary matrix U of the channel matrix H can be derived in the seventh processing circuit according to the eigenvectors ui, i=1 ̃M.
In addition, according to the above-mentioned disclosure, once eigenvectors vi are is obtained in the fifth processing circuit 3061, the corresponding eigenvectors ui are also obtained in the sixth processing circuit 307, and therefore the corresponding singular values σi can be obtained in the eighth processing circuit 309 by multiplying the channel matrix H by the eigenvectors vi and the eigenvectors ui as illustrated in the equation (5). When all of the singular value σ1 ̃σm are obtained, the diagonal matrix Σ can be derived in the ninth processing circuit 3010.
According to the above-mentioned disclosure of the present invention, the computation of the singular value decomposing device 400 is division free and square-root free. In other words, no division or square-root operation are performed in the singular value decomposing device 400 to therefore lower the total computational complexity (i.e., multiplication and add (MAC)) to decompose the channel matrix H and obtain the characteristic of fast-convergence. In addition, the singular value decomposing device 400 is reconfigurable to various sizes of channel matrices, such as a 4*4 matrix or 4*3 matrix. Furthermore, since the eigenvectors vi, ui, and σi can be derived separately in the embodiment of the present invention, the singular value decomposing device 400 possesses high parallelism compared with the conventional one.
Those skilled in the art will readily observe that numerous modifications and alterations of the device and method may be made while retaining the teachings of the invention.

## Claims

1. A method for performing a singular value decomposition (SVD) upon a matrix, the method comprising:
(a) simplifying the matrix to derive a simplified matrix;
(b) using a processing circuit for performing an iterative matrix multiplication upon the simplified matrix to generate an iterated matrix;
(c) extracting a vector of the iterated matrix according to an iteration number of the iterative matrix multiplication;
(d) de-correlating the simplified matrix from the vector to update the simplified matrix;
(e) repeating steps (b), (c), and (d) until a predetermined number of vectors have been derived; and
(f) storing a first unitary matrix determined according to the predetermined number of vectors in the singular value decomposition.

2. The method of claim 1, wherein step (f) comprises:
(f-1) normalizing the predetermined number of vectors to derive a plurality of first normalized vectors, respectively; and
(f-2) storing the first unitary matrix composed of the first normalized vectors.

3. The method of claim 2, further comprising:
(g) multiplying the matrix by the first normalized vectors to generate a plurality of resultant vectors, respectively; and
(h) deriving a second unitary matrix of the singular value decomposition, wherein the second unitary matrix is composed of a plurality of second normalized vectors generated from normalizing the resultant vectors, respectively.

4. The method of claim 3, wherein step (g) multiplies the matrix by a normalized vector derived in step (f-1) before all of the first normalized vectors are derived in step (f-1).

5. The method of claim 1, wherein step (a) comprises:
performing a transpose conjugate operation upon the matrix to generate a transposed matrix; and
multiplying the matrix by the transposed matrix to generate the simplified matrix.

6. The method of claim 1, wherein step (b) comprises:
(b-1) multiplying the simplified matrix by the simplified matrix itself to generate the iterated matrix;
(b-2) re-assigning a word-length for storing the iterated matrix to generate a shifted matrix;
(b-3) updating the simplified matrix utilizing the shifted matrix; and
(b-4) repeating steps (b-1), (b-2) and (b-3) until the iteration number is equal to a predetermined value.

7. The method of claim 1, wherein step (d) comprises:
subtracting the vectors extracted in step (c) by an identity matrix to generate a subtracted matrix; and
multiplying the subtracted matrix by the simplified matrix to update the simplified matrix.

8. The method of claim 1, further comprising:
(g) multiplying the matrix by the predetermined number of vectors to generate a plurality of resultant vectors, respectively; and
(h) deriving a second unitary matrix composed of a plurality of normalized vectors generated from normalizing the resultant vectors, respectively, and storing the second unitary matrix.

9. The method of claim 8, wherein step (g) multiplies the matrix by one of the predetermined number of vectors to derive a resultant vector before all of the predetermined number of vectors are derived.

10. The method of claim 1, wherein the matrix is a Multi-input Multi-output (MIMO) channel matrix.

11. A singular value decomposing device, for performing a singular value decomposition (SVD) upon a matrix, the singular value decomposing device comprising:
a first processing circuit, for simplifying the matrix to derive a simplified matrix;
a second processing circuit, coupled to the first processing circuit, for performing an iterative matrix multiplication upon the simplified matrix to generate an iterated matrix;
a third processing circuit, coupled to the second processing circuit, for extracting a vector of the iterated matrix according to an iteration number of the iterative matrix multiplication;
a fourth processing circuit, coupled to the third processing circuit, for de-correlating the simplified matrix from the vector to update the simplified matrix;
a switch circuit, coupled between the fourth processing circuit and the second processing circuit, for selectively coupling the simplified matrix to the second processing circuit until a predetermined number of vectors have been derived; and
a storing module, coupled to the third processing circuit, for storing a first unitary matrix determined according to the predetermined number of vectors in the singular value decomposition.

12. The singular value decomposing device of claim 11, wherein the storing module comprises:
a fifth processing circuit, for normalizing the predetermined number of vectors to derive a plurality of first normalized vectors, respectively; and
a storing unit, coupled to the fifth processing circuit, for storing the first unitary matrix composed of the first normalized vectors.

13. The singular value decomposing device of claim 12, further comprising:
a sixth processing circuit, coupled to the storing module, for multiplying the matrix by the first normalized vectors to generate a plurality of resultant vectors, respectively; and
a seventh processing circuit, coupled to the sixth processing circuit, for deriving a second unitary matrix of the singular value decomposition, wherein the second unitary matrix is composed of a plurality of second normalized vectors generated from normalizing the resultant vectors, respectively.

14. The singular value decomposing device of claim 13, wherein the sixth processing circuit multiplies the matrix by a normalized vector derived by the fifth processing circuit before all of the first normalized vectors are derived by the fifth processing circuit.

15. The singular value decomposing device of claim 11, wherein the first processing circuit comprises:
a first arithmetic unit, for performing a transpose conjugate operation upon the matrix to generate a transposed matrix; and
a second arithmetic unit, coupled to the first arithmetic unit, for multiplying the matrix by the transposed matrix to generate the simplified matrix.

16. The singular value decomposing device of claim 11, wherein the second processing circuit comprises:
a third arithmetic unit, for multiplying the simplified matrix by the simplified matrix itself to generate the iterated matrix;
a shifting module, coupled to the third arithmetic circuit, for re-assigning a word-length for storing the iterated matrix to generate a shifted matrix, and updating the simplified matrix utilizing the shifted matrix until the iteration number is equal to a predetermined value.

17. The singular value decomposing device of claim 11, wherein
the fourth processing circuit comprises:
a fourth arithmetic unit, for subtracting the vectors extracted in the third processing circuit by an identity matrix to generate a subtracted matrix; and
a fifth arithmetic circuit, coupled to the fourth arithmetic unit, for multiplying the subtracted matrix by the simplified matrix to update the simplified matrix.

18. The singular value decomposing device of claim 11, further comprising:
an eighth processing circuit, coupled to the storing module, for multiplying the matrix by the predetermined number of vectors to generate a plurality of resultant vectors, respectively; and
a ninth processing circuit, coupled to the eighth processing circuit, for deriving a second unitary matrix composed of a plurality of normalized vectors generated from normalizing the resultant vectors, respectively, and storing the second unitary matrix.

19. The singular value decomposing device of claim 18, wherein the eighth processing circuit multiplies the matrix by one of the predetermined number of vectors to derive a resultant vector before all of the predetermined number of vectors are derived.

20. The singular value decomposing device of claim 11, wherein the matrix is a Multi-input Multi-output (MIMO) channel matrix.