Abstract:
Varying embodiments of the present invention provide a MIMO apparatus, such as a transceiver and a method of operation thereof. In an embodiment, the transceiver employs a parallelized., two-stage pipeline architecture that reduces the overall latency of the system. This reduction in latency translates to cost savings and higher data rates for the same hardware clock speed.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates generally to communication systems and more particularly to wireless communication systems. 
       BACKGROUND OF THE INVENTION 
       [0002]    Personal devices, such as computers, phones, personal digital assistants and the like have gained wide popularity in recent years. As technology improves, these devices have become increasingly smaller in size and highly portable. In fact, wireless, portable devices of various types now commonly communicate with one another allowing users flexibility of use and facilitating data, voice and audio communication. To this end, networking of mobile or portable and wireless devices is required. 
         [0003]    With regard to the wireless networking of personal devices, a particular modem, namely modems adapted to the up-coming IEEE 8302.11n industry standard, are anticipated to be commonly employed. This standard allows for an array of antennas to be placed inside or nearby the personal device and a radio frequency (RF) semiconductor device receives signal or data through the array and an analog-to-digital converter, typically located within the personal device, converts the received signal to baseband range. Thereafter, a baseband processor is employed to process and decode the received signal to the point of extracting raw data, which may be files transferred remotely and wireless, from another personal device or similar equipment with the use of a transmitter within the transmitting PC. 
         [0004]    To do so, pointing of the array of antennas, which is essentially multiple antennas, hence the name multi-input-multi-output (MIMO), to the desired location to maximize reception and transmission quality is an issue. For example, data or information rate throughput, signal reception and link range are improved. The latest IEEE802.11n standard currently being developed includes advanced multi-antenna techniques in order to process parallel data streams simultaneously in order to increase throughput capability, and improve link quality by “smartly” transmitting and receiving the RF signals. 
         [0005]    MIMO has drawn attention as the technique for enabling a high-capacity (high-speed) data communication by efficiently using a frequency band. The MIMO is the technique to transmit separate data streams from a plurality of antennas of a transmitter by using a plurality of antennas in both of the transmission and the reception, that is to say, by using the transmitter having a plurality of antennas and the receiver having a plurality of antennas, and individually separate a plurality of transmission signals (data streams) mixed on a transmission path from the signal received by each receiving antenna of the receiver by using a transmission path (channel) estimate value, thereby improving a transmission rate without requiring an enlargement of the frequency band. 
         [0006]      FIG. 1  shows the general structure of a typical MIMO OFDM system according to the prior art. The MIMO transmitter  100  has multiple antennas  110 A- 110 C each capable of transmitting independent signals to a MIMO receiver  120  which is also equipped with multiple receive antennas  130 A- 130 B. The transmitter  100  may comprise a forward error correction (FEC) code encoder  101 , an interleaver  102 , a MIMO constellation Mapper  103 , an OFDM MEMO IFFT  104  and an analog and RF unit  105 . The MIMO receiver  120  may comprise an RF and analog unit  121 , a MIMO FFT  122 , a MIMO demodulator  123  (like a slicer), a de-interleaver  124  and a FEC Decoder  125 , all of which are used to convert the incoming RF signals into spatial streams representing bits of information sent over the channel. The MIMO demodulator receives a plurality of spatial streams of bits, and converts them into information in a format required by the FEC decoder. In some MIMO systems the demodulator performs hard decision and delivers information bits whereas in other systems the decoder delivers soft output for further soft decoding to be performed in a Viterbi decoder, low density parity check (LDPC) decoder or the like. Here the demodulator  123  is a maximum likelihood (ML) demodulator that might employ a K-Best or Fixed Sphere Demodulator algorithm. 
         [0007]    The ML demodulator for a MIMO receiver operates by comparing the received signal vector with all possible noiseless received signals corresponding to all possible transmitted signals. Under certain assumptions, this receiver achieves optimal performance in the sense of maximizing the probability of correct data detection. The main idea behind the a sub-optimal implementation like the K-Best algorithm or the Fixed Sphere algorithm is to perform a search over only a small subset of all possible signals located around the received signal vector. The size of this search may be determined by a combination of performance and hardware requirements. This reduced search space ensures that the demodulator complexity is not only reduced, but also fixed over time—a major advantage for hardware implementation. In order for such a search to operate efficiently, a key point is to order the antennas in such a way that most of the points considered relate to transmit antennas with the poorest signal-to-noise (SNR) conditions. Antennas with, higher SNR conditions are much more likely to be detected correctly, based only on the received signal. 
         [0008]    The ML demodulator has exponential complexity in the number of spatial streams being received. Essentially, the complexity of this decoder increases exponentially with the number of transmit streams, making it impossible to implement for large array sizes and high order digital modulation schemes. 
       SUMMARY OF THE INVENTION 
       [0009]    Varying embodiments of the present invention provide a MIMO apparatus, such as a transceiver and a method of operation thereof. In an embodiment, the transceiver generates look-up tables based on re-occurring calculations whereby searches can be minimized by sorted computations. The hardware can then be re-configured to make extra searches in more useful points and lesser searches elsewhere. This re-configurable structure increases the search speed and reduces the cost (gate count, power consumed) thereby improving the system performance. 
         [0010]    A first embodiment of the present invention is a method of operating a multiple input multiple output (MIMO) demodulator comprising receiving a plurality of spatial streams wherein the plurality of spatial streams comprise in-phase (I) and quadrature (Q) pairs of streams, calibrating the I and Q pairs of the plurality of streams, searching each of the plurality of symbols thereby forming a search subset and systematically pruning the search subset based on a predetermined set of criteria. 
         [0011]    A second embodiment of the present invention is a MIMO transceiver comprising a calibration module for receiving a plurality of spatial streams wherein the plurality of spatial streams comprise inphase (I) and quadrature (Q) pairs of streams wherein each of the plurality of I/Q pairs of streams comprises a plurality of symbols and calibrating the I and Q pairs of the plurality of streams, a decomposition module coupled to the calibration module for decomposing the calibrated I and Q pairs of the plurality of streams, a sorting module coupled to the decomposition module for searching each of the plurality of symbols thereby forming a search subset and systematically pruning the search subset based on a predetermined set of criteria. 
         [0012]    Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0013]      FIG. 1  shows the general structure of a typical MIMO OFDM system according to the prior art. 
           [0014]      FIG. 2  illustrates a flowchart in accordance with an embodiment of the present invention. 
           [0015]      FIG. 3  shows a simplified block diagram of a transceiver system in accordance with an embodiment of the present invention. 
           [0016]      FIG. 4  shows a hardware configuration in conjunction with an embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
       [0017]    The present invention relates generally to communication systems and more particularly to wireless communication systems. The following description is presented to enable one of ordinary skill in the art to make and use the invention and is provided in the context of a patent application and its requirements. Various modifications to the preferred embodiment and the generic principles and features described herein will be readily apparent to those skilled in the art. Thus, the present invention is not intended to be limited to the embodiment shown but is to be accorded the widest scope consistent with the principles and features described herein. 
         [0018]    Varying embodiments of the present invention provide a MIMO apparatus, such as a transceiver and a method of operation thereof. In an embodiment, the transceiver generates look-up tables based on re-occurring calculations whereby searches can be minimized by sorted computations. The hardware can then be re-configured to make extra searches in more useful points and lesser searches elsewhere. This re-configurable structure increases the search speed and reduces the cost (gate count, power consumed) thereby improving the system performance. 
         [0019]      FIG. 2  illustrates a flowchart in accordance with an embodiment of the present invention. Step  210  involves receiving a plurality of spatial streams wherein the plurality of spatial streams comprise inphase (I) and quadrature (Q) pairs of streams wherein each of the plurality of I/Q pairs of streams comprises a plurality of symbols. A second step  220  involves calibrating the I and Q pairs of the plurality of streams. A third step  230  involves searching each of the plurality of symbols thereby forming a search subset. A final step  240  includes systematically pruning the search subset based on a predetermined set of criteria 
         [0020]    The implementation of the present invention is discussed in terms of “in-phase” and “quadrature-phase” spatial streams. The term in-phase is also found in the context of communication signals: 
         [0000]        A ( t )= I ( t ) cos (2 πft +Φ( t )+ Q ( t ) sin (2 πft +Φ( t ))) 
         [0000]    where f and Φ(t) represents a carrier frequency and carrier phase, and A(t) represents the transmitted signal after modulation with a carrier wave, e.g.: cos (2πft+Φ(t)). The component that is in phase with the original carrier is referred to as the in-phase component. The other component, which is always 90° 
         [0000]    
       
         
           
             ( 
             
               
                 π 
                 2 
               
                
               
                   
               
                
               radians 
             
             ) 
           
         
       
     
         [0000]    “out of phase”, is referred to as the quadrature component. 
         [0021]    The system in accordance with the present invention can take the form of an entirely hardware implementation, an entirely software implementation, or an implementation containing both hardware and software elements. In one implementation, this detection procedure is implemented in software, which includes, but is not limited to, application software, firmware, resident software, microcode, etc. 
         [0022]    Furthermore, the method can be implemented in the form of a computer program product accessible from a computer-usable or computer readable medium providing program code for use by or in connection with a computer or any instruction execution system. For the purposes of this description, a computer-usable or computer-readable medium can be any apparatus that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device. 
         [0023]    The medium can be an electronic magnetic, optical, electromagnetic, infrared, or semiconductor system (or apparatus or device) or a propagation medium. Examples of a computer-readable medium include a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk, and an optical disk. Current examples of optical disks include DVD, compact disk-read-only memory (CD-ROM), and compact disk-read/write (CD-R/W). To describe the features of the present invention in more detail, refer now to the following description in conjunction with the accompanying Figures. 
         [0024]      FIG. 3  shows a simplified block diagram of a transceiver system in accordance with an embodiment of the present invention. The transceiver system  300  includes four modules. The first module is the acquisition and calibration module  310  which performs a calibration of the received plurality of spatial streams H wherein the spatial streams H comprise I and Q pairs of streams. The second module is the decomposition module  320  which performs a decomposition of the calibrated I and Q pairs of the plurality of streams wherein each of the plurality of I/Q pairs of streams comprises a plurality of symbols. Typically, each of the plurality of I/Q pairs has 10-50 symbols. The third module is a sorting module  330  which orders the received streams based on a metric. Thus, the sorting module  330  presents an order that requires the least complexity for the next block. The fourth module is a demodulator  340 . 
         [0025]    Calibration module  310  performs an I/Q calibration of the received plurality of spatial streams H. US Patent Application 20090046011 entitled “Method and Apparatus for Calibration for Beamforming of Multi-Input-Multi-Output Orthogonol Frequency Division Multiplexing (OFDM) Transceiver”, which is incorporated by reference in its entirety herein, discloses a calibration technique that could be utilized in conjunction with an embodiment in accordance with the present invention. 
         [0026]    The output of the calibration module  310  is coupled to the decomposition module  320 . Here, the calibrated I and Q pairs of the plurality of streams are decomposed thereby creating a matrix wherein the matrix comprises an upper triangular. A matrix decomposition is a factorization of a matrix into some canonical form. For instance, the QR decomposition expresses H as QR with Q a unitary matrix and R an upper triangular matrix. Accordingly, the system Hx=b (equivalently Q(Rx)=b) is solved by Rx=Q T b=c, and the system Rx=c is solved by “back substitution”. 
         [0027]    The output of decomposition module  320  is coupled to the input of the sorting module  330 . Here, the plurality of symbols are searched thereby forming a search subset. This search subset of the plurality of symbols are then systematically pruned based on a predetermined set of criteria. The criteria can be hardware based (for example, limiting the increase in size of the subset), metric based (for example, removing the elements of the subset which have too large a metric to be possible solutions), performance based (for example, new elements added to the subset around the existing elements with best metric). Based on this systematic pruning process, the component hardware can be re-configured to make extra searches in more useful points and reduce the number of searches elsewhere. As a result of this pruning step, the system performs more efficiently for the same cost. 
         [0028]    With regard to the pruning step, pruning is a term in mathematics and informatics which describes a method of enumeration, which allows parts of a decision tree to be cut. Pruned parts of the tree are no longer considered because the algorithm knows based on already collected data (e.g. through sampling) that these subtrees do not contain the searched object. The decision tree is simplified by removing some decisions. Decision trees are built with the available information and they are supporting tools in a decision making process. However, sometimes the given set of data may be irrelevant, erroneous or unnecessary, in which case the decision tree formed may not be correct; this phenomenon is called overfitting. Also, too much information may misguide the decision policy. When this happens, it becomes necessary to remove nodes from the decision tree that are non-useful. The process of making the decision tree smaller by removing nodes that are not helpful is called pruning. 
         [0029]    The search sequence can be conducted in a variety of ways. For example, a k-best algorithm could be employed. The k-best algorithm is an algorithm to cluster n objects based on attributes into k partitions, k&lt;n. It is similar to the expectation-maximization algorithm for mixtures of Gaussians in that they both attempt to find the centers of natural clusters in the data. It assumes that the object attributes form a vector space. The objective it tries to achieve is to minimize total intra-cluster metric, like, the squared error function 
         [0000]    
       
         
           
             V 
             = 
             
               
                 ∑ 
                 
                   i 
                   = 
                   1 
                 
                 k 
               
                
               
                 
                   ∑ 
                   
                     
                       x 
                       j 
                     
                     ∈ 
                     
                       S 
                       i 
                     
                   
                 
                  
                 
                   
                     ( 
                     
                       
                         x 
                         j 
                       
                       - 
                       
                         μ 
                         i 
                       
                     
                     ) 
                   
                   2 
                 
               
             
           
         
       
     
         [0000]    where there are k clusters S i , i=1, 2, . . . , k, and μ i  is the centroid or mean point of all the points x j , S i . Different metrics like the Λ 1  norm can be used to reduce complexity in certain implementations. 
         [0030]    Another approach is the sorted-tree expansion. In this procedure, an initial sub-optimal tree is constructed with a subset of the leaves chosen for calculation. Based on the metrics returned during the training some of leaves with large metrics are removed from the list and newer leaves with the parent of the smallest metric are added. In this procedure, a close to optimal solution can be made optimal very easily. The algorithm can stop when marginal improvement is achieved with additional leaves. 
         [0031]    It is observed that many calculations in the demodulator are re-occurring. Accordingly, a look up table can be generated based on all the calculations that are repeated multiple times. In an embodiment, the look up tables can include:
   Constellation D i *S i  C×1   Projection R ij *S k  C×3×2   Boundaries D i *b i  Log 2 (C)×3   
 
         [0035]    Although the above-described tables are disclosed, one of ordinary skill in the art will readily recognize that a variety of different tables could be employed while remaining within the spirit and scope of the present invention. Once the table(s) are generated, they are stored for later use by the system. 
         [0036]      FIG. 4  shows a hardware configuration in conjunction with an embodiment of the present invention.  FIG. 4  shows elements  410  and  420  which separate the sign and absolute value of the input. Most constellations used in practice are symmetric on positive and negative sides and this separation will reduce the number of comparison to be made. Blocks  430 ,  440  and  450  make comparisons with decision boundaries T m  which are decided by the constellation. Once the location of the best solution is known relative to the decision boundaries, the encoder  460  along with the sign information from element  410  will determine the constellation point with the least metric corresponding to the input and the multiplexer (MUX)  470  will determine the corresponding metric. The encoder in  460  can be easily implemented as a lookup table from the possible inputs. 
         [0037]    In an embodiment, the hardware unit described here calculates the best metric for the input. A similar hardware unit can be designed for the best-n metrics of the input, where n=2,3,4 . . . as desired by the tree-expansion algorithm. A quick complexity calculation shows that this procedure replaced 3 required multipliers with 3 comparators which are relatively inexpensive in hardware. 
         [0038]    Varying embodiments of the present invention provide a MIMO apparatus, such as a transceiver and a method of operation thereof. In an embodiment, the transceiver generates look-up tables based on re-occurring calculations whereby searches can be minimized by sorted computations. The hardware can then be re-configured to make extra searches in more useful points and lesser searches elsewhere. This reconfiguration requires no change in the hardware unit and all changes are limited to the table being generated. This re-configurable structure increases the search speed and reduces the cost (gate count, power consumed) thereby improving the system performance. 
         [0039]    Any publications, including patents, patent applications and articles, referenced or mentioned in this specification are herein incorporated in their entirety into the specification, to the same extent as if each individual publication was specifically and individually indicated to be incorporated herein. In addition, citation or identification of any reference in the description of some embodiments of the invention shall not be construed as an admission that such reference is available as prior art to the present invention. 
         [0040]    Without further analysis, the foregoing so fully reveals the gist of the present inventive concepts that others can, by applying current knowledge, readily adapt it for various applications without omitting features that, from the standpoint of prior art, fairly constitute essential characteristics of the generic or specific aspects of this invention. Therefore, such applications should and are intended to be comprehended within the meaning and range of equivalents of the following claims. Although these inventive concepts have been described in terms of certain embodiments, other embodiments that are apparent to those of ordinary skill in the art are also within the scope of this invention, as defined in the claims that follow.