Title of Invention	METHOD AND APPARATUS FOR LIST SPHERE DECODING
Abstract	Method and apparatuses for decoding codewords over a MIMO channel are provided. According to one aspect of the disclosure, a cost function is computed for each constellation point of an Mth rank or spatial layer and Ncand of those constellation points having minimum cost are preserved as candidate points, where Ncand is a parameter specified to the decoding algorithm. In addition, a cost function may be computed for all possible transitions from the Ncand candidate points of the Mth rank to ail possible constellations points of the (M-1)th spatial layer, and A^ of those transitions having minimum cost are preserved as candidate points. The process is repeated for all spatial layers, resulting in the identification of Ncand candidate codewords and their associated cost functions. The algorithm is derived from the list sphere decoding method.

Title of Invention

METHOD AND APPARATUS FOR LIST SPHERE DECODING

Abstract

Method and apparatuses for decoding codewords over a MIMO channel are provided. According to one aspect of the disclosure, a cost function is computed for each constellation point of an Mth rank or spatial layer and Ncand of those constellation points having minimum cost are preserved as candidate points, where Ncand is a parameter specified to the decoding algorithm. In addition, a cost function may be computed for all possible transitions from the Ncand candidate points of the Mth rank to ail possible constellations points of the (M-1)th spatial layer, and A^ of those transitions having minimum cost are preserved as candidate points. The process is repeated for all spatial layers, resulting in the identification of Ncand candidate codewords and their associated cost functions. The algorithm is derived from the list sphere decoding method.

Full Text	FORM 2 THE PATENTS ACT, 1970 (39 of 1970) & THE PATENTS RULES, 2003 COMPLETE SPECIFICATION (See section 10, rule 13) SPHERE DECODING APPARATUS FOR MIMO CHANNEL QUALCOMM INCORPORATED, an American company of 5775 Morehouse Drive , San Diego, California 92121-1714, United States of America The following specification particularly describes the invention and the manner in which it is to be performed. WO 2006/130804 PCT/US2006/021379 SPHERE DECODING APARATUS FOR MIMO CHANNEL Claim of Priority under 35 U.S.C. §119 [0001] The present Application for Patent claims priority to Provisional Application No. 60/686,819 entitled "MIMO-Single Code Word Receivers with List Sphere Decoding" filed June 1, 2005, assigned to the assignee hereof, and hereby expressly incorporated by reference herein. Reference to Co-Pending Applications for Patent [0002] The present Application for Patent is related to co-pending U.S. Patent Application No. 11/022,347 entitled "Capacity based rank prediction for MEMO design," assigned to the assignee hereof, and expressly incorporated by reference herein. BACKGROUND Field [0003] The present disclosure relates generally to communications, and, more specifically, to techniques for decoding codewords received over a communications channel. Background [0004] In a wireless communication system, an RF modulated signal from a transmitter may reach a receiver via a number of propagation paths. The characteristics of the propagation paths typically vary over time due to a number of factors such as fading and multipath. To provide diversity against deleterious path effects and improve performance, multiple transmit and receive antennas may be used. If the propagation paths between the transmit and receive antennas are linearly independent (i.e., a transmission on one path is not a linear combination of the transmissions on the other paths), then the likelihood of correctly receiving a data transmission increases as the number of antennas increases. Generally, diversity increases and performance improves with more transmit and receive antennas. [0005] A multiple-input multiple-output (MIMO) communication system can employ multiple (NT) transmit antennas and multiple (NR) receive antennas for data transmission. A MIMO channel formed by the NT transmit and NR receive antennas may WO 2006/130804 PCT/US2006/021379 be decomposed into Ns independent channels, with Ns [0006] For a full-rank MTMO channel, where NS=NT [0007] A MIMO design can have multiple modes of operation. In one mode of operation, the transmitter can encode the data transmitted on each spatial layer independently, possibly with different rates. The receiver can employ an SIC algorithm that works as follows: Decode the first layer, and then subtract its contribution from the received signal after re-encoding and multiplying the encoded first layer with an "estimated channel," then decode the second layer, and so on. This approach means that each successively decoded layer sees increased signal-to-noise ratio (SNR) and hence can support higher rates. In the absence of error propagation, this mode of operation combined with SIC achieves capacity. The disadvantages of this design arise from the burden of "managing" the rates of each spatial layer, in particular (a) increased CQI (channel quality indicator) feedback signaling overhead (one CQI for each layer); (b) increased ACK/NACK messaging (one message for each layer); (c) complications with the Hybrid ARQ (HARQ) scheme, since each layer can terminate at a different transmission; (d) performance sensitivity to channel estimation errors in channels experiencing increased Doppler effect and/or low SNR; and (e) tighter decoding latency requirements since each successive layer cannot be decoded until the prior layers are decoded. In other modes, a common encoding of a single data stream from a single antenna is provided. Alternatively, a transmitter may encode the data on each spatial WO 2006/130804 PCT/US2006/021379 layer using the same data rate for each layer, and rank prediction may be employed to adapt the number of spatial layers on a packet-by-packet basis depending on the channel conditions and the SNR. [0008] To decode the received codewords, a receiver can employ a low complexity linear receiver such as an MMSE (minimum mean squared error) equalizer for each tone. Alternatively, non-linear receivers such as an ML (maximum likelihood) MIMO decoder can be used to achieve better performance at the cost of a more complex implementation. In particular, the complexity of an ML MIMO decoder is exponential with the rank M and the symbol constellation order Mc. For an overview of prior art decoders for MIMO, see Hochwald and Brink, "Achieving Near-Capacity on a Multiple-Antenna Channel," IEEE Transactions on Communications, Vol. 51, No.3, March 2003, the contents of which are herein incorporated by reference in their entirety. SUMMARY [0009] The disclosure provides methods and apparatuses for decoding codewords over a communications channel. One aspect of the disclosure provides a method comprising receiving at least one codeword sent over a multiple-input multiple-output (MIMO) channel, wherein the at least one codeword comprises a plurality of layers, each layer comprising a constellation point of a plurality of candidate constellation points. The method further comprises for each layer, computing a state cost metric using said codeword for each constellation point of the at least one layer and selecting preferred states of the at least one layer whose state cost metrics meet first preferred criteria, and for each of a plurality of constellation points of said layer, computing a state cost metric using said codeword for each transition from a preferred constellation point of said layer to each constellation point of a following layer, and selecting preferred transitions to said following layer whose state cost metrics meet second preferred criteria. [0010] A further aspect of the disclosure provides a decoding method comprising receiving a codeword comprising a plurality of symbols, each symbol corresponding to at least one of a plurality of candidate constellation points. The method comprises, for a first symbol, computing a cost metric for each candidate constellation point of said first symbol and storing in a memory only those candidate constellation points whose computed cost metrics meet first preferred criteria. The method further comprises for each following symbol and for each candidate constellation point previously stored in WO 2006/130804 PCT/US2006/021379 said memory for the symbol immediately preceding said following symbol, computing a cost metric for each candidate transition from said previously stored candidate constellation point to a candidate constellation point of said following symbol, and storing in said memory only those candidate transitions whose computed cost metrics meet second preferred criteria. [0011] Yet a further aspect of the disclosure provides a decoder apparatus comprising a receiver configured to receive at least one codeword, wherein the at least one codeword comprises a plurality of layers, each layer comprising a constellation point selected from a plurality of candidate constellation points. The decoder further comprises processor configured to, for at least one layer, compute a constellation point metric for the at least one layer, and to select preferred constellation points of the at least one layer whose state cost metrics meet first preferred criteria; the processor further configured to compute a constellation point cost metric for each transition from a preferred constellation point of the layer to each constellation point of a following layer, and selecting preferred transitions to said following layer whose constellation point cost metrics meet second preferred criteria. [0012] The disclosure further provides other methods and apparatuses that implement various aspects, embodiments, and features of the disclosure, as described in further detail below. BRIEF DESCRIPTION OF THE DRAWINGS [0013] FIG. 1 shows a diagram of a wireless multiple-access communication system; [0014] FIG. 2 shows a communication system comprising an SCW transmitter with rank prediction. [0015] FIG. 3 shows an SCW receiver employing either a linear MMSE equalizer or some type of decoder. [0016] FIG. 4 shows a flow chart of one possible algorithmic implementation of a sphere decoder. [0017] FIG. 5 shows a flow chart of one possible algorithmic implementation of a list sphere decoder. [0018] FIG. 6 shows a flow chart of another possible algorithmic implementation of a list sphere decoder. [0019] FIG. 7 shows a trellis diagram for list sphere trellis decoding. WO 2006/130804 PCT/US2006/021379 [0020] FIG. 8 shows candidate constellation pairs having minimum cost in the trellis diagram. [0021] FIG. 9 shows the final trellis diagram with Ncand paths and candidate solution vectors. [0022] Fig. 10 shows a block diagram of an embodiment of an access point and two terminals. DETAILED DESCRIPTION [0023] FIG. 1 shows a wireless communication system 1 with multiple access points (APs) 10 and multiple terminals 20. A base station is a station that communicates with the terminals. A base station may also be called, and may contain some or all of the functionality of, an access point, a Node B, and/or some other network entity. Each access point 10 provides communication coverage for a particular geographic area 2. The term "cell" can refer to an access point and/or its coverage area depending on the context in which the term is used. To improve system capacity, an access terminal coverage area may be partitioned into multiple smaller areas, e.g., three smaller areas 4a, 4b, and 4c. Each smaller area is served by a respective base transceiver subsystem (BTS). The term "sector" can refer to an AP and/or its coverage area depending on the context in which the term is used. For a sectorized cell, the APs for all sectors of that cell are typically co-located within the base station for the cell. The signaling transmission techniques described herein may be used for a system with sectorized cells as well as a system with un-sectorized cells. For simplicity, in the following description, the term "base station" is used generically for a station that serves a sector as well as a station that serves a cell. [0024] Terminals 20 are typically dispersed throughout the system, and each terminal may be fixed or mobile. A terminal may also be called, and may contain some or all of the functionality of, a mobile station, a user equipment, and/or some other device. A terminal may be a wireless device, a cellular phone, a personal digital assistant (PDA), a wireless modem card, and so on. A terminal may communicate with zero, one, or multiple base stations on the forward and reverse links at any given moment. [0025] For a centralized architecture, a system controller 30 couples to APs 10 and provides coordination and control for these base stations. System controller 30 may be WO 2006/130804 PCT/US2006/021379 a single network entity or a collection of network entities. For a distributed architecture, the APs may communicate with one another as needed. [0026] FIG. 2 shows an SCW transmitter with rank prediction. The bits 202 are turbo-encoded 204 and QAM mapped 206 depending on the packet format (PF) 208, 210, specified by a rate prediction algorithm 212. In an embodiment, the coded symbols are then de-multiplexed 214 to M streams 216 or layers, where M 228 can be a 2-bit integer specified by the receiver 226 feedback every 5 m-sec, in addition to a 5-bit CQI 224. The M streams 216 are then spatially mapped 218 to MT OFDM modulators 220 and MT antennas 222. [0027] FIG. 3 shows an SCW receiver 201 employing either a linear MMSE equalizer or some type of decoder 234. In this embodiment, MR antennas 232 receive a signal transmitted over the air. The output of each antenna 232 is OFDM demodulated 233 and input to a linear MMSE equalizer or decoder 234. The linear MMSE equalizer or decoder 234 can each be implemented on a tone-by-tone basis, i.e., for each tone, MR received signals are processed to generate M symbols 236. The linear MMSE equalizer or decoder 234 can also generate information to allow CQI and rank computation 231. The symbols 236 are demultiplexed 235, and a log-likelihood ratio (LLR) 237 can be calculated for each of the M symbols 236. The LLR's 237 may then be supplied to a turbo decoder 238 which outputs decoded bits 239. [0028] Various decoder implementations for an SCW receiver will now be described herein, in particular-, an ML MEMO decoder, a sphere decoder, a list sphere decoder, and a list sphere trellis decoder. [0029] To understand the operation of the ML MTMO decoder, define the following: M R : Number of Receive Antennas M : Rank of MIMO Transmission H : MEMO channel per tone (M R x M) x: Received signal vector per tone (M R x 1) S : Transmit symbol vector per tone (M xl) = [s1 s2 .. .. sM ] n: Noise Vector per tone (M R x 1) [0030] The system equation for a given tone is given as: x = Hs + n (Eq. 1) [0031] The ML MIMO solution is given as: sML=arg min\\x-Hs\\2 (Eq. 2) seA. WO 2006/130804 PCT/US2006/021379 [0032] where A is the lattice defined by having each entry of the M-dimensional vector s be taken from a constellation of 2Mc points. It can be seen that the ML MEMO decoder selects the transmit symbol vector sML that maximizes the likelihood of the received signal vector being x. In some aspects, the complexity of the ML MTMO decoder is exponential with the number of MIMO layers M and the symbol constellation order Mc. [0033] To reduce the exponential complexity of ML MIMO decoding, a technique known as sphere decoding may be employed. To understand sphere decoding, first define the QR decomposition of the channel matrix H: H =QR, where Q is an MRxM unitary matrix (herein defined as any matrix Q such that QQ = I), and R is an upper triangular MxM matrix. Also define s to be the zero-forcing solution [0034] According to Eq. 3, the sphere decoder can restrict its search for a sphere decoder solution sSD to those hypotheses s located inside a sphere of radius "r" centered about the zero-forcing solution s. The sphere decoder thus avoids an exhaustive ML search over all possible hypotheses s. [0035] Using the QR decomposition, the expression in Eq. 3 can be further manipulated as follows: [0036] The form of Eq. 4 takes advantage of the fact that R is triangular to conveniently divide the computation of the term to be minimized among the separate layers i. Note that the same will also be true for any lower triangular decomposition of the matrix H. This form suggests a sphere decoding procedure for decoding a received codeword as described below. [0037] A possible implementation of a sphere decoding procedure is shown in the flow chart diagram of FIG. 4. Note the flow chart diagrams given in this disclosure are WO 2006/130804 PCT/US2006/021379 only meant to be illustrative of possible implementations, and should not be construed to limit the scope of the disclosure. First, an initial value for the sphere radius r is determined, block 301. Next, set i = M for the Mth layer computation, block 302. From a computational viewpoint, the LHS (left-hand side) of Eq. 4 may become the constellation used for M layer. Next, a search over all candidate constellation points is performed to select a candidate constellation point, block 304. In some cases, the constellation point, sM, is selected such that The candidate constellation point IM is saved, e.g. in memory, block 305. [0038] The layer being operated on is then decremented, e.g. i = M -1, as shown in block 306. From a computational viewpoint, the LHS of Eq. 4 now becomes the constellation used for the (M-l)th layer. For SCW design, the constellation used for all layers is the same, i.e., Am = A, Vm = 1,2,...M For a given point sM, select one constellation point, IM-1 such that [0039] If no point ~sM_1 is available for the choice of JM , then the process reverts back to selecting another constellation point IM, as shown in blocks 309 and 310. [0040] For a given pair fM_t, IM, set i = M - 2 , and the operations 304-306 may be repeated. This process of determining candidate points is continued for all subsequent layers up to and including i = 1, at which point a series of candidate points [ $M » M-I > SM~2 '••••' i ] corresponding to a single candidate solution vector scmd is obtained. This may be accomplished by the decrement block 306 and the loop-back to block 303. In the case where i = 0, the vector sccmd is saved, as shown in block 307. [0041] A new update to the radius rupdale may then be calculated and the radius changed to r WO 2006/130804 PCT/US2006/021379 [0042] The process may be repeated with this new radius rupdate, and the procedure is continued until there is no candidate solution vector falling within a radius rupdate- Note that the sphere radius shrinks with each iteration, and hence in general the decoder does not need to evaluate all possible candidate points to obtain the sphere decoder solution SSD- [0043] From the description above, it will be noted that the complexity of the sphere decoder grows with increasing sphere radius "r", and eventually approaches ML complexity. On the other hand, if the radius "r" is selected too small, then the ML solution can potentially lie outside the sphere, leading to incorrect solutions. In general, the preferred sphere radius "r" grows with (a) large eigenvalue spread of the MIMO channel and (b) low SNR. Also, as no soft information is generated by the sphere decoder for alternative codewords, it cannot provide a turbo decoder with soft information for joint decoding. [0044] The list sphere decoder is a MIMO-MAP decoder that, is capable of generating soft-information for use by a turbo decoder, and is based on sphere decoder principles. A possible algorithmic implementation of the list sphere decoder is shown in FIG. 5, to which reference will be made in the description below. [0045] As shown in block 401 of FIG. 5, first select a sphere radius "r," as well as a parameter Ncand whose function will later be described. Then follow blocks 402-406, analogous to blocks 302-306 of FIG. 4, to arrive at a candidate solution vector Scand comprising candidate points Once a candidate solution vector is obtained, an associated cost can be computed as shown in 407, and can be utilized by an outer turbo-decoder to improve performance. The cost for a candidate solution vector can be referred to as an "overall" cost metric, as distinguished from a per-layer cost metric such as computed according to the LHS of Eq. 4. Note that the noise variance a2 can in general be different for different tones. The candidate solution vector-cost association can be entered and stored in a "candidate list" as shown in 409. These steps are repeated for other candidate solutions within the sphere radius "r" until Ncmd candidate solutions reside in the candidate list. The parameter Ncand may also be referred to as a "candidate plurality." Thereafter, an additional candidate solution vector is added to the candidate list only if its associated cost is less than the highest cost already on the candidate list. If this is the case, the candidate solution WO 2006/130804 PCT/US2006/021379 vector cost entry having the highest cost is deleted, thereby maintaining a total of no more than Ncand entries in the candidate list at any time. Alternatively, the first Ncand costs computed by the decoder for a received codeword can be defined to qualify as one of the NCand lowest costs on the candidate list, and thus a general check can be performed as shown in block 408. [0046] In contrast with the sphere decoder, the list sphere decoder is capable of providing soft information for several candidate codewords, as well as soft information for each bit (or symbol) of each candidate codeword. Thus, it may be used in conjunction with other decoders utilizing a priori soft information, such as a turbo decoder. To see this, let Mcbe the modulation order and let M be the rank of the MIMO transmission, resulting in a total of MMc bits transmitted per tone. In a preferred embodiment, the soft extrinsic information (LLR) for each bit bk V k = 1,2..MMc can be approximated as: where includes all the candidate solution vectors with bk = 1; a2 is the noise-variance; is a sub-vector of bits obtained by excluding bk; vector of a-priori LLR information on all corresponding bits present in the vector bm; and max* (a,b) = ln(ea +eb). [0047] From the description of the list sphere decoder given above, the sphere radius "r" does NOT decrease with each iteration. As a result, the complexity increases greatly if the initial sphere radius is selected too large. Furthermore, both the quality of the computed LLR and the complexity increase with increasing values of Ncand. Eq. 5 is an WO 2006/130804 PCT/US2006/021379 equality if Ncand = 2MM°. In general, the performance and complexity of the above algorithm depend on "r" and Ncand. [0048] FIG. 7 shows a trellis diagram for list sphere trellis decoding. The diagram has M stages corresponding to the rank of the MIMO transmission and 2Mc states corresponding to the number of constellation points. For example, for a 16-QAM constellation and Rank 4 transmission, we have M=4 and Mc=4. [0049] Similar to list sphere decoding, a parameter Ncand may be specified, corresponding to the maximum number of entries maintained in the candidate list for each stage. In the example trellis shown in FIG. 7, Ncmd = 2. A possible algorithmic implementation of the general list sphere decoding algorithm is shown in FIG. 6. [0050] In Fig. 6. first, an initialization of Ncand is providedand set i = M, blocks 501-502 of FIG. 6. A cost function R2MM \|\|sM -sM \|\|2 is computed for all constellation point, block 503. In some aspects, only e Ncand points that have the minimum cost are preserved. If Ncand > 2Mc, then preserve only the 2Mc points that have the minimum cost. In a trellis implementation of a decoder, e.g with reference to the trellis diagram of FIG. 7, these states are denoted by the shaded circles. These states can also be referred to as the "preferred" states. [0051] For each of the preferred states selected i, a cost metric associated with each transition from a preferred state of the Mth layer to one of the 2Mc candidate constellation points for the (M-l)th layer is computed, block 505. An individual cost metric can be computed as: [0052] This creates a total of Ncand2Mc candidate pairs [sM, sM_{ ], each with an associated cost metric. The pairs are indicated by the "dotted lines" in FIG. 7, for a trellis implementation [0053] From a mathematical standpoint, it may be observed that the term 6 is essentially computed already been computed earlier in block 503 of FIG . 6, and thus need not be re-computed when performing later computations, e.g. in block 505. Further, the same observation applies to the cost metric computations at subsequent stages i, i.e., the state cost metric computed for the WO 2006/130804 PCT/US2006/021379 (i+l)th stage can be stored and re-used during computation of a state cost metric for the ith stage, or layer, of the trellis. Similarly, need only be computed Ncmd times initially, and can also be stored and re-used for the rest of the Ncand2Mc computations. The same observation applies with respect to the computation of metrics for the subsequent stages i. [0054] Then, from the Ncand2Mc pairs or "dotted paths" shown in FIG. 7, save to memory only the Ncand preferred transitions from layer M to layer M-l having the minimum cost, block 506. Also save to memory the constellation points and costs associated with those preferred transitions. The pairs having minimum cost are denoted by the solid lines in FIG. 8. These paths and costs are stored along with the stored paths and costs from the previous layer to create a record of the trellis path traversed. These paths can also be referred to as the "preferred" transitions. [0055] As illustrated by the loop back to the decrement block 504 in FIG. 5, blocks 505-507 are analogously performed for each subsequent layer up to layer 1. As previously described, only the Ncmd preferred transitions and associated constellation points / costs need be saved in memory for each layer. [0056] Once the layer 1 computations are finished, the final trellis diagram of FIG. 9 is obtained showing Ncand paths and candidate solution vectors. Eq. 5 can subsequently be used to obtain the LLR for each bit. [0057] As further refinements to the list sphere decoding algorithms, the optimization parameter Ncand can be varied depending on the constellation size, as well as across stages, depending on channel conditions for each tone or group of tones, or other factors. In an embodiment, Ncand may be dynamically adjusted to be greater in the presence of worse channel conditions, and lower in the presence of better channel conditions. [0058] Note that in some aspects, the term La[y calculated in Eq. 5 can be omitted if unavailable, for example, if turbo-decoder iterations have yet to be performed, or if the turbo decoding is altogether decoupled from the list sphere decoding. In certain aspects, a list sphere decoder may be concatenated with a turbo decoder, and soft information calculated by the list sphere decoder may be iteratively exchanged with the turbo decoder, and vice versa, until a convergent solution is obtained. WO 2006/130804 PCT/US2006/021379 [0059] Note also that, in general, the decoding procedure described herein may also be implemented using alternative criteria to identify preferred states of each layer. For example, instead of preserving only the Ncand states or transitions having the lowest computed cost metrics, an implementation may preserve those states or transitions whose cost metrics meet certain other criteria, such as being below a preferred cost value. Such alternative criteria also fall within the scope of the present disclosure. [0060] It should be noted, that the above procedures may easily be applied to multi-codeword (MCW) systems, wherein the constellation sizes vary across each stage. In an embodiment, Ncand can be set a constant 256 across all stages to give acceptable performance for an SCW 4x4 MIMO system. [0061] Further, while FIGS. 6-9 are generally discussed in the context of utilizing a trellis diagram, the above methodologies may be utilized without usage of a trellis methodology. For example, the cost metrics may calculated for each layer and constellation point for the layer, without using trellis diagram representation. In such a case, the above calculations may be made for MIMO layers, instead of trellis stages, and constellation point, instead of states of the trellis stages. [0062] FIG. 10 shows a block diagram of an embodiment of an AP lOx and two ATs 20x and 20y in multiple-access multi-carrier communication system 100. At AP lOx, a transmit (TX) data processor 514 receives traffic data (i.e., information bits) from a data source 512 and signaling and other information from a controller 520 and a scheduler 530. For example, controller 520 may provide power control (PC) commands that are used to adjust the transmit power of the active ATs, and scheduler 530 may provide assignments of carriers for the ATs. These various types of data may be sent on different transport channels. TX data processor 514 encodes and modulates the received data using multi-carrier modulation (e.g., OFDM) to provide modulated data (e.g., OFDM symbols). A transmitter unit (TMTR) 516 then processes the modulated data to generate a downlink modulated signal that is then transmitted from an antenna 518. [0063] At each of ATs 20x and 20y, the transmitted and modulated signal is received by an antenna 552 and provided to a receiver unit (RCVR) 554. Receiver unit 554 processes and digitizes the received signal to provide samples. A received (RX) data processor 556 then demodulates and decodes the samples to provide decoded data, which may include recovered traffic data, messages, signaling, and so on. The traffic data may be provided to a data sink 558, and the carrier assignment and PC commands sent for the terminal are provided to a controller 560. WO 2006/130804 PCT/US2006/021379 [0064] Controller 560 directs data transmission on the uplink using the resources that have been assigned to the terminal and indicated in the received assignment. Controller 560 further injects the erasure signature packets when the there is not actual data to transmit, yet desires to keep the assigned resources. [0065] Controller 520 directs data transmission on the downlink using the resources that have been assigned to the terminal. Controller 520 further injects the erasure signature packets when the there is not actual data to transmit, yet desires to keep the assigned resources. [0066] For each active terminal 120, a TX data processor 574 receives traffic data from a data source 572 and signaling and other information from controller 560. For example, controller 560 may provide information indicative of channel quality information, required transmit power, the maximum transmit power, or the difference between the maximum and required transmit powers for the terminal. The various types of data are coded and modulated by TX data processor 574 using the assigned carriers and further processed by a transmitter unit 576 to generate an uplink modulated signal that is then transmitted from antenna 552. [0067] At AP 10x, the transmitted and modulated signals from the ATs are received by antenna 518, processed by a receiver unit 532, and demodulated and decoded by an RX data processor 534. Receiver unit 532 may estimate the received signal quality (e.g., the received signal-to-noise ratio (SNR)) for each terminal and provide this information to controller 520. Controller 520 may then derive the PC commands for each terminal such that the received signal quality for the terminal is maintained within an acceptable range. RX data processor 534 provides the recovered feedback information (e.g., the required transmit power) for each terminal to controller 520 and scheduler 530. [0068] Scheduler 530 may provide an indication to controller 520 to maintain the resources. This indication is provided if more data is scheduled to be transmitted. For the AT 20x, the controller 560 may determine if resources required to be maintained. In certain aspects, controller 520 may perform instructions that provide the functionality of scheduler 530. [0069] Further, controller 560 may perform all or some of the functions discussed with respect to FIGS. 1-9 with respect to the access terminal. [0070] The techniques described herein may be implemented by various means. For example, these techniques may be implemented in hardware, software, or a combination thereof. For a hardware implementation, the processing units (e.g., controllers 520 and WO 2006/130804 PCT/US2006/021379 560, TX and RX processors 514 and 534, and so on) for these techniques may be implemented within one or more application specific integrated circuits (ASICs), digital signal processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices (PLDs), field programmable gate arrays (FPGAs), processors, controllers, micro-controllers, microprocessors, other electronic units designed to perform the functions described herein, or a combination thereof. [0071] For a software implementation, the techniques described herein may be implemented with modules (e.g., procedures, functions, and so on) that include the instructions that may be implemented by one or more processors to perform the functions described herein. The instructions may be stored in memory units, e.g., memory 522 in FIG. 10, on a removable media, or the like that may be read and executed by one or more processors (e.g., controllers 520). The memory unit(s) may be implemented within the processor or external to the processor, in which case it can be communicatively coupled to the processor via various means as is known in the art. [0072J Headings are included herein for reference and to aid in locating certain sections. These headings are not intended to limit the scope of the concepts described therein under, and these concepts may have applicability in other sections throughout the entire specification. [0073] The previous description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein. WO 2006/130804 PCT/US2006/021379 We Claim : 1. A method for list sphere decoding comprising: receiving at least one codeword sent over a multiple-input multiple-output (MIMO) channel, wherein the at least one codeword comprises a plurality of layers, each layer comprising a constellation point of a plurality of candidate constellation points; for each layer, computing a state cost metric using said codeword for each constellation point of the at least one layer, and selecting preferred states of the at least one layer whose state cost metrics meet first preferred criteria; and for each of a plurality of constellation points of said layer, computing a state cost metric using said codeword for each transition from a preferred constellation point of said layer to each constellation point of a following layer, and selecting preferred transitions to said following layer whose state cost metrics meet second preferred criteria. 2. The method of claim 1, further comprising, for each layer, storing in a memory the state cost metrics associated with said selected preferred constellation points and transitions. 3. The method of claim 1, wherein meeting the first preferred criteria comprises being one of a candidate plurality of constellation point s having the lowest state costs for a constellation point. 4. The method of claim 3, wherein meeting the second preferred criteria comprises being one of a candidate plurality of transitions having the lowest constellation point costs for a layer. 5. The method of claim 4, wherein said candidate plurality can be variable across layers, and can be a function of the number of candidate constellation points for each layer. 6. The method of claim 5, wherein said codeword is a multiple-code word (MCW). 7. The method of claim 4, wherein said codeword is a single-code word (SCW). WO 2006/130804 PCT/US2006/021379 8. The method of claim 1, further comprising storing in a memory said constellation point cost metric for a stage after computation, and re-using said stored metric when computing a constellation point cost metric during a following layer. 9. The method of claim 1, further comprising determining candidate codewords from said preferred constellation points and said preferred transitions. 10. The method of claim 9, further comprising computing overall cost metrics for said candidate codewords. 11. The method of claim 10, further comprising selecting a candidate codeword having the lowest overall cost metric. 12. The method of claim 1, wherein the first and second preferred criteria are met when a computed constellation point cost metric is one of a candidate plurality of constellation point cost metrics having the lowest values for a given layer, and wherein said candidate plurality can be variable across layers. 13. The method of claim 12, wherein said candidate plurality is constant for all layers. 14. The method of claim 1, wherein the first preferred criteria are met when a computed state cost metric is lower than a specified threshold. 15. The method of claim 1, further comprising calculating a soft extrinsic information metric for each bit. 16. The method of claim 15, wherein said soft extrinsic information metric for each bit is provided to a turbo decoder. 17. The method of claim 16, wherein said turbo decoder further generates an additional soft extrinsic information metric for each bit. WO 2006/130804 PCT/US2006/021379 18. The method of claim 17, wherein each layer comprises a stage of a trellis and each constellation point comprises a state of one stage of the trellis. 19. A decoding method comprising: receiving a codeword comprising a plurality of symbols, each symbol corresponding to at least one of a plurality of candidate constellation points; for a first symbol: computing a cost metric for each candidate constellation point of said first symbol; storing in a memory only those candidate constellation points whose computed cost metrics meet first preferred criteria; for each following symbol, and for each candidate constellation point previously stored in said memory for the symbol immediately preceding said following symbol: computing a cost metric for each candidate transition from said previously stored candidate constellation point to a candidate constellation point of said following symbol; and storing in said memory only those candidate transitions whose computed cost metrics meet second preferred criteria. 20. The method of claim 19, further comprising determining candidate codewords from the candidate constellation points and candidate transitions stored in said memory. 21. The method of claim 19, wherein said codeword is transmitted over a MIMO channel, and said symbols of said codeword are simultaneously transmitted on different antennas over said MEMO channel. 22. The method of claim 21, wherein said MIMO channel is characterized by a channel matrix H; further comprising providing an upper triangular matrix R related to the matrix H by a unitary transformation, and wherein said computed cost metric for each symbol is a function of the coefficients in the rows of the matrix R corresponding to said symbol and all symbols preceding said symbol. WO 2006/130804 PCT/US2006/021379 23. The method of claim 19, wherein meeting said first preferred criteria comprises being a candidate constellation point having an associated cost metric that is one of the a first candidate plurality of lowest cost metrics for all candidate constellation points. 24. The method of claim 23, wherein said first candidate plurality is less than the total number of candidate constellation points for a symbol. 25. The method of claim 24, wherein meeting said second preferred criteria comprises being a candidate transition having an associated cost metric that is one of a second candidate plurality of lowest cost metrics for all candidate transitions for that symbol, wherein said second candidate plurality is less than the total number of candidate transitions from a candidate constellation point of the preceding symbol to a candidate constellation point of the following symbol, and wherein said first candidate plurality is equal to said second candidate plurality. 26. The method of claim 19, wherein meeting said second preferred criteria comprises being a candidate transition having an associated cost metric that is one of a second candidate plurality of lowest cost metrics for all candidate transitions. 27. The method of claim 26, wherein said second candidate plurality is less than the total number of candidate transitions from a candidate constellation point of the preceding symbol to a candidate constellation point of the following symbol. 28. The method of claim 19, wherein each of said following symbols comprises a symbol following in time. 29. The method of claim 19, wherein each of said following symbols comprises a symbol following in rank. 30. A decoder apparatus comprising: a receiver configured to receive at least one codeword sent over a multiple-input multiple-output (MEMO) channel, wherein the at least one codeword comprises a plurality of layers, each layer comprising a constellation point selected from a plurality of candidate constellation points; and WO 2006/130804 PCT/US2006/021379 a processor configured to, for at least one layer, compute a constellation point metric for the at least one layer, and to select preferred constellation points of the at least one layer whose state cost metrics meet first preferred criteria; the processor further configured to compute a constellation point cost metric for each transition from a preferred constellation point of the layer to each constellation point of a following layer, and selecting preferred transitions to said following layer whose constellation point cost metrics meet second preferred criteria. 31. The apparatus of claim 30, further comprising a memory for storing, for each stage, the state cost metrics associated with the preferred states and the preferred transitions. 32. The apparatus of claim 30, wherein meeting the first preferred criteria comprises being one of a candidate plurality states having the lowest state costs for the stage. 33. The apparatus of claim 32, wherein meeting the second preferred criteria comprises being one of said candidate plurality of transitions having the lowest state costs for the stage. 34. The apparatus of claim 33, wherein the MIMO channel is characterized by a channel matrix H, wherein the rank of the matrix H is M, further comprising providing an upper triangular matrix R related to said channel matrix H, wherein said state cost metric for each state of the number of stages is expressed as wherein the state cost metric of said Mth stage is expressed as wherein: R is an upper triangular matrix related to the matrix H by a unitary transformation; RMM denotes the entry of said matrix R corresponding to the Mth row and the Mth column; sM denotes a candidate constellation point of the Mth layer; and SM denotes the Mth entry of the zero-forcing solution WO 2006/130804 PCT/US2006/021379 35. The apparatus of claim 34, wherein the state cost metric for each transition of the ith stage is expressed as follows: ; wherein i denotes an index to a stage of the trellis; Rij denotes the entry of the R matrix corresponding to the ith row and the jth column; si denotes a candidate constellation point of the ith layer; and s' denotes the ith entry of the zero-forcing solution 36. The apparatus of claim 30, further comprising a soft information processor for computing soft extrinsic information for each bit associated with each constellation point associated with each layer of a candidate codeword, wherein a candidate codeword can be determined from said preferred states and preferred transitions. 37. A decoder apparatus comprising: means for receiving at least one codeword sent over a multiple-input multiple-output (MIMO) channel, wherein the at least one codeword comprises a plurality of layers, each layer comprising a constellation point selected from a plurality of candidate constellation points; and means for determining preferred constellation points of at least onelayer and preferred transitions having constellation point cost metrics meeting first criteria for the at least one layer. 38. The apparatus of claim 37, wherein meeting said first criteria comprises being one of a candidate plurality of states having the lowest state costs for each stage. 39. A processor readable media comprising instructions thereon that may be utilized by a processor, the instructions comprising: instructions for a first symbol, of a codeword comprising a plurality of symbols, each symbol corresponding to at least one of a plurality of candidate constellation points, computing a cost metric for each candidate constellation point of said first symbol; WO 2006/130804 PCT/US2006/021379 instructions for storing in a memory only those candidate constellation points whose computed cost metrics meet first preferred criteria; and instructions, for each following symbol and for each candidate constellation point previously stored in said memory for the symbol immediately preceding said following symbol, computing a cost metric for each candidate transition from said previously stored candidate constellation point to a candidate constellation point of said following symbol; and 40. The processor readable media of claim 39, further comprising instructions for storing in said memory only those candidate transitions whose computed cost metrics meet second preferred criteria. ABSTRACT "SPHERE DECODING APPARATUS FOR MIMO CHANNEL" Method and apparatuses for decoding codewords over a MIMO channel are provided. According to one aspect of the disclosure, a cost function is computed for each constellation point of an Mth rankor spatial layer and Ncand of those constellation points having minimum cost are preserved as candidate points, where Ncand is a parameter specified to the decoding algorithm. In addition, a cost function may be computed for all possible transitions from the Ncand candidate points of the Mth rank to ail possible constellations points of the (M-l)th spatial layer, and AA of those transitions having minimum cost are preserved as candidate points. The process is repeated for all spatial layers, resulting in the identification of Ncand candidate codewords and their associated cost functions. The algorithm is derived from the list sphere decoding method.

Full Text

FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
(See section 10, rule 13)
SPHERE DECODING APPARATUS FOR MIMO CHANNEL
QUALCOMM INCORPORATED,
an American company of 5775 Morehouse Drive ,
San Diego, California 92121-1714, United States of America
The following specification particularly describes the invention and the manner in which it is to be performed.

WO 2006/130804 PCT/US2006/021379
SPHERE DECODING APARATUS FOR MIMO CHANNEL
Claim of Priority under 35 U.S.C. §119
[0001] The present Application for Patent claims priority to Provisional Application No. 60/686,819 entitled "MIMO-Single Code Word Receivers with List Sphere Decoding" filed June 1, 2005, assigned to the assignee hereof, and hereby expressly incorporated by reference herein.
Reference to Co-Pending Applications for Patent
[0002] The present Application for Patent is related to co-pending U.S. Patent Application No. 11/022,347 entitled "Capacity based rank prediction for MEMO design," assigned to the assignee hereof, and expressly incorporated by reference herein.
BACKGROUND Field
[0003] The present disclosure relates generally to communications, and, more specifically, to techniques for decoding codewords received over a communications channel.
Background
[0004] In a wireless communication system, an RF modulated signal from a transmitter may reach a receiver via a number of propagation paths. The characteristics of the propagation paths typically vary over time due to a number of factors such as fading and multipath. To provide diversity against deleterious path effects and improve performance, multiple transmit and receive antennas may be used. If the propagation paths between the transmit and receive antennas are linearly independent (i.e., a transmission on one path is not a linear combination of the transmissions on the other paths), then the likelihood of correctly receiving a data transmission increases as the number of antennas increases. Generally, diversity increases and performance improves with more transmit and receive antennas.
[0005] A multiple-input multiple-output (MIMO) communication system can employ multiple (NT) transmit antennas and multiple (NR) receive antennas for data transmission. A MIMO channel formed by the NT transmit and NR receive antennas may

WO 2006/130804 PCT/US2006/021379
be decomposed into Ns independent channels, with Ns [0006] For a full-rank MTMO channel, where NS=NT [0007] A MIMO design can have multiple modes of operation. In one mode of operation, the transmitter can encode the data transmitted on each spatial layer independently, possibly with different rates. The receiver can employ an SIC algorithm that works as follows: Decode the first layer, and then subtract its contribution from the received signal after re-encoding and multiplying the encoded first layer with an "estimated channel," then decode the second layer, and so on. This approach means that each successively decoded layer sees increased signal-to-noise ratio (SNR) and hence can support higher rates. In the absence of error propagation, this mode of operation combined with SIC achieves capacity. The disadvantages of this design arise from the burden of "managing" the rates of each spatial layer, in particular (a) increased CQI (channel quality indicator) feedback signaling overhead (one CQI for each layer); (b) increased ACK/NACK messaging (one message for each layer); (c) complications with the Hybrid ARQ (HARQ) scheme, since each layer can terminate at a different transmission; (d) performance sensitivity to channel estimation errors in channels experiencing increased Doppler effect and/or low SNR; and (e) tighter decoding latency requirements since each successive layer cannot be decoded until the prior layers are decoded. In other modes, a common encoding of a single data stream from a single antenna is provided. Alternatively, a transmitter may encode the data on each spatial

WO 2006/130804 PCT/US2006/021379

layer using the same data rate for each layer, and rank prediction may be employed to adapt the number of spatial layers on a packet-by-packet basis depending on the channel conditions and the SNR.
[0008] To decode the received codewords, a receiver can employ a low complexity linear receiver such as an MMSE (minimum mean squared error) equalizer for each tone. Alternatively, non-linear receivers such as an ML (maximum likelihood) MIMO decoder can be used to achieve better performance at the cost of a more complex implementation. In particular, the complexity of an ML MIMO decoder is exponential with the rank M and the symbol constellation order Mc. For an overview of prior art decoders for MIMO, see Hochwald and Brink, "Achieving Near-Capacity on a Multiple-Antenna Channel," IEEE Transactions on Communications, Vol. 51, No.3, March 2003, the contents of which are herein incorporated by reference in their entirety.
SUMMARY
[0009] The disclosure provides methods and apparatuses for decoding codewords over a communications channel. One aspect of the disclosure provides a method comprising receiving at least one codeword sent over a multiple-input multiple-output (MIMO) channel, wherein the at least one codeword comprises a plurality of layers, each layer comprising a constellation point of a plurality of candidate constellation points. The method further comprises for each layer, computing a state cost metric using said codeword for each constellation point of the at least one layer and selecting preferred states of the at least one layer whose state cost metrics meet first preferred criteria, and for each of a plurality of constellation points of said layer, computing a state cost metric using said codeword for each transition from a preferred constellation point of said layer to each constellation point of a following layer, and selecting preferred transitions to said following layer whose state cost metrics meet second preferred criteria.
[0010] A further aspect of the disclosure provides a decoding method comprising receiving a codeword comprising a plurality of symbols, each symbol corresponding to at least one of a plurality of candidate constellation points. The method comprises, for a first symbol, computing a cost metric for each candidate constellation point of said first symbol and storing in a memory only those candidate constellation points whose computed cost metrics meet first preferred criteria. The method further comprises for each following symbol and for each candidate constellation point previously stored in

WO 2006/130804 PCT/US2006/021379

said memory for the symbol immediately preceding said following symbol, computing a cost metric for each candidate transition from said previously stored candidate constellation point to a candidate constellation point of said following symbol, and storing in said memory only those candidate transitions whose computed cost metrics meet second preferred criteria.
[0011] Yet a further aspect of the disclosure provides a decoder apparatus comprising a receiver configured to receive at least one codeword, wherein the at least one codeword comprises a plurality of layers, each layer comprising a constellation point selected from a plurality of candidate constellation points. The decoder further comprises processor configured to, for at least one layer, compute a constellation point metric for the at least one layer, and to select preferred constellation points of the at least one layer whose state cost metrics meet first preferred criteria; the processor further configured to compute a constellation point cost metric for each transition from a preferred constellation point of the layer to each constellation point of a following layer, and selecting preferred transitions to said following layer whose constellation point cost metrics meet second preferred criteria.
[0012] The disclosure further provides other methods and apparatuses that implement various aspects, embodiments, and features of the disclosure, as described in further detail below.
BRIEF DESCRIPTION OF THE DRAWINGS
[0013] FIG. 1 shows a diagram of a wireless multiple-access communication system;
[0014] FIG. 2 shows a communication system comprising an SCW transmitter with
rank prediction.
[0015] FIG. 3 shows an SCW receiver employing either a linear MMSE equalizer or
some type of decoder.
[0016] FIG. 4 shows a flow chart of one possible algorithmic implementation of a
sphere decoder.
[0017] FIG. 5 shows a flow chart of one possible algorithmic implementation of a list
sphere decoder.
[0018] FIG. 6 shows a flow chart of another possible algorithmic implementation of a
list sphere decoder.
[0019] FIG. 7 shows a trellis diagram for list sphere trellis decoding.

WO 2006/130804 PCT/US2006/021379
[0020] FIG. 8 shows candidate constellation pairs having minimum cost in the trellis
diagram.
[0021] FIG. 9 shows the final trellis diagram with Ncand paths and candidate solution
vectors.
[0022] Fig. 10 shows a block diagram of an embodiment of an access point and two
terminals.
DETAILED DESCRIPTION
[0023] FIG. 1 shows a wireless communication system 1 with multiple access points (APs) 10 and multiple terminals 20. A base station is a station that communicates with the terminals. A base station may also be called, and may contain some or all of the functionality of, an access point, a Node B, and/or some other network entity. Each access point 10 provides communication coverage for a particular geographic area 2. The term "cell" can refer to an access point and/or its coverage area depending on the context in which the term is used. To improve system capacity, an access terminal coverage area may be partitioned into multiple smaller areas, e.g., three smaller areas 4a, 4b, and 4c. Each smaller area is served by a respective base transceiver subsystem (BTS). The term "sector" can refer to an AP and/or its coverage area depending on the context in which the term is used. For a sectorized cell, the APs for all sectors of that cell are typically co-located within the base station for the cell. The signaling transmission techniques described herein may be used for a system with sectorized cells as well as a system with un-sectorized cells. For simplicity, in the following description, the term "base station" is used generically for a station that serves a sector as well as a station that serves a cell.
[0024] Terminals 20 are typically dispersed throughout the system, and each terminal may be fixed or mobile. A terminal may also be called, and may contain some or all of the functionality of, a mobile station, a user equipment, and/or some other device. A terminal may be a wireless device, a cellular phone, a personal digital assistant (PDA), a wireless modem card, and so on. A terminal may communicate with zero, one, or multiple base stations on the forward and reverse links at any given moment.
[0025] For a centralized architecture, a system controller 30 couples to APs 10 and provides coordination and control for these base stations. System controller 30 may be

WO 2006/130804 PCT/US2006/021379

a single network entity or a collection of network entities. For a distributed architecture, the APs may communicate with one another as needed.
[0026] FIG. 2 shows an SCW transmitter with rank prediction. The bits 202 are turbo-encoded 204 and QAM mapped 206 depending on the packet format (PF) 208, 210, specified by a rate prediction algorithm 212. In an embodiment, the coded symbols are then de-multiplexed 214 to M streams 216 or layers, where M 228 can be a 2-bit integer specified by the receiver 226 feedback every 5 m-sec, in addition to a 5-bit CQI 224. The M streams 216 are then spatially mapped 218 to MT OFDM modulators 220 and MT antennas 222.
[0027] FIG. 3 shows an SCW receiver 201 employing either a linear MMSE equalizer or some type of decoder 234. In this embodiment, MR antennas 232 receive a signal transmitted over the air. The output of each antenna 232 is OFDM demodulated 233 and input to a linear MMSE equalizer or decoder 234. The linear MMSE equalizer or decoder 234 can each be implemented on a tone-by-tone basis, i.e., for each tone, MR received signals are processed to generate M symbols 236. The linear MMSE equalizer or decoder 234 can also generate information to allow CQI and rank computation 231. The symbols 236 are demultiplexed 235, and a log-likelihood ratio (LLR) 237 can be calculated for each of the M symbols 236. The LLR's 237 may then be supplied to a turbo decoder 238 which outputs decoded bits 239.
[0028] Various decoder implementations for an SCW receiver will now be described herein, in particular-, an ML MEMO decoder, a sphere decoder, a list sphere decoder, and a list sphere trellis decoder.
[0029] To understand the operation of the ML MTMO decoder, define the following:
M R : Number of Receive Antennas
M : Rank of MIMO Transmission
H : MEMO channel per tone (M R x M)
x: Received signal vector per tone (M R x 1)
S : Transmit symbol vector per tone (M xl) = [s1 s2 .. .. sM ]
n: Noise Vector per tone (M R x 1)
[0030] The system equation for a given tone is given as:
x = Hs + n (Eq. 1)
[0031] The ML MIMO solution is given as:
sML=arg min\\x-Hs\\2 (Eq. 2)
seA.

WO 2006/130804 PCT/US2006/021379

[0032] where A is the lattice defined by having each entry of the M-dimensional vector s be taken from a constellation of 2Mc points. It can be seen that the ML MEMO decoder selects the transmit symbol vector sML that maximizes the likelihood of the received signal vector being x. In some aspects, the complexity of the ML MTMO decoder is exponential with the number of MIMO layers M and the symbol constellation order Mc.
[0033] To reduce the exponential complexity of ML MIMO decoding, a technique known as sphere decoding may be employed. To understand sphere decoding, first define the QR decomposition of the channel matrix H: H =QR, where Q is an
MRxM unitary matrix (herein defined as any matrix Q such that Q*Q = I), and R is an upper triangular MxM matrix. Also define s to be the zero-forcing solution

[0034] According to Eq. 3, the sphere decoder can restrict its search for a sphere decoder solution sSD to those hypotheses s located inside a sphere of radius "r" centered
about the zero-forcing solution s. The sphere decoder thus avoids an exhaustive ML search over all possible hypotheses s.
[0035] Using the QR decomposition, the expression in Eq. 3 can be further manipulated as follows:

[0036] The form of Eq. 4 takes advantage of the fact that R is triangular to conveniently divide the computation of the term to be minimized among the separate layers i. Note that the same will also be true for any lower triangular decomposition of the matrix H. This form suggests a sphere decoding procedure for decoding a received codeword as described below.
[0037] A possible implementation of a sphere decoding procedure is shown in the flow chart diagram of FIG. 4. Note the flow chart diagrams given in this disclosure are

WO 2006/130804 PCT/US2006/021379
only meant to be illustrative of possible implementations, and should not be construed to limit the scope of the disclosure. First, an initial value for the sphere radius r is determined, block 301. Next, set i = M for the Mth layer computation, block 302. From a computational viewpoint, the LHS (left-hand side) of Eq. 4 may become
the constellation used for M* layer. Next, a search over all candidate constellation points is performed to select a candidate constellation point, block 304. In some cases, the constellation point, sM, is selected such that
The candidate constellation point IM is saved, e.g. in memory, block 305.
[0038] The layer being operated on is then decremented, e.g. i = M -1, as
shown in block 306. From a computational viewpoint, the LHS of Eq. 4 now becomes

the constellation used for the (M-l)th layer. For SCW design, the constellation used for all layers is the same, i.e., Am = A, Vm = 1,2,...M For a given point sM, select one
constellation point, IM-1 such that

[0039] If no point ~sM_1 is available for the choice of JM , then the process reverts back
to selecting another constellation point IM, as shown in blocks 309 and 310.
[0040] For a given pair fM_t, IM, set i = M - 2 , and the operations 304-306 may
be repeated. This process of determining candidate points is continued for all
subsequent layers up to and including i = 1, at which point a series of candidate points
[ $M » *M-I > SM~2 '••••' *i ] corresponding to a single candidate solution vector scmd is
obtained. This may be accomplished by the decrement block 306 and the loop-back to
block 303. In the case where i = 0, the vector sccmd is saved, as shown in block 307.
[0041] A new update to the radius rupdale may then be calculated and the radius
changed to r
WO 2006/130804 PCT/US2006/021379
[0042] The process may be repeated with this new radius rupdate, and the procedure is continued until there is no candidate solution vector falling within a radius rupdate- Note that the sphere radius shrinks with each iteration, and hence in general the decoder does not need to evaluate all possible candidate points to obtain the sphere decoder solution
SSD-
[0043] From the description above, it will be noted that the complexity of the sphere decoder grows with increasing sphere radius "r", and eventually approaches ML complexity. On the other hand, if the radius "r" is selected too small, then the ML solution can potentially lie outside the sphere, leading to incorrect solutions. In general, the preferred sphere radius "r" grows with (a) large eigenvalue spread of the MIMO channel and (b) low SNR. Also, as no soft information is generated by the sphere decoder for alternative codewords, it cannot provide a turbo decoder with soft information for joint decoding.
[0044] The list sphere decoder is a MIMO-MAP decoder that, is capable of generating soft-information for use by a turbo decoder, and is based on sphere decoder principles. A possible algorithmic implementation of the list sphere decoder is shown in FIG. 5, to which reference will be made in the description below.
[0045] As shown in block 401 of FIG. 5, first select a sphere radius "r," as well as a parameter Ncand whose function will later be described. Then follow blocks 402-406, analogous to blocks 302-306 of FIG. 4, to arrive at a candidate solution vector Scand
comprising candidate points Once a candidate solution vector is obtained, an associated cost can be computed as shown in 407, and

can be utilized by an outer turbo-decoder to improve performance. The cost for a candidate solution vector can be referred to as an "overall" cost metric, as distinguished from a per-layer cost metric such as computed according to the LHS of Eq. 4. Note that the noise variance a2 can in general be different for different tones. The candidate solution vector-cost association can be entered and stored in a "candidate list" as shown in 409. These steps are repeated for other candidate solutions within the sphere radius "r" until Ncmd candidate solutions reside in the candidate list. The parameter Ncand may also be referred to as a "candidate plurality." Thereafter, an additional candidate solution vector is added to the candidate list only if its associated cost is less than the highest cost already on the candidate list. If this is the case, the candidate solution

WO 2006/130804 PCT/US2006/021379

vector cost entry having the highest cost is deleted, thereby maintaining a total of no more than Ncand entries in the candidate list at any time. Alternatively, the first Ncand
costs computed by the decoder for a received codeword can be defined to qualify as one of the NCand lowest costs on the candidate list, and thus a general check can be performed as shown in block 408.
[0046] In contrast with the sphere decoder, the list sphere decoder is capable of providing soft information for several candidate codewords, as well as soft information for each bit (or symbol) of each candidate codeword. Thus, it may be used in conjunction with other decoders utilizing a priori soft information, such as a turbo decoder. To see this, let Mcbe the modulation order and let M be the rank of the
MIMO transmission, resulting in a total of MMc bits transmitted per tone. In a preferred embodiment, the soft extrinsic information (LLR) for each bit bk V k = 1,2..MMc can be approximated as:

where

includes all the candidate solution vectors with bk = 1; a2 is the noise-variance;

is a sub-vector of bits obtained by excluding bk;
vector of a-priori LLR information on all
corresponding bits present in the vector bm; and
max* (a,b) = ln(ea +eb).
[0047] From the description of the list sphere decoder given above, the sphere radius "r" does NOT decrease with each iteration. As a result, the complexity increases greatly if the initial sphere radius is selected too large. Furthermore, both the quality of the computed LLR and the complexity increase with increasing values of Ncand. Eq. 5 is an

WO 2006/130804 PCT/US2006/021379
equality if Ncand = 2MM°. In general, the performance and complexity of the above algorithm depend on "r" and Ncand.
[0048] FIG. 7 shows a trellis diagram for list sphere trellis decoding. The diagram has M stages corresponding to the rank of the MIMO transmission and 2Mc states corresponding to the number of constellation points. For example, for a 16-QAM constellation and Rank 4 transmission, we have M=4 and Mc=4.
[0049] Similar to list sphere decoding, a parameter Ncand may be specified, corresponding to the maximum number of entries maintained in the candidate list for each stage. In the example trellis shown in FIG. 7, Ncmd = 2. A possible algorithmic
implementation of the general list sphere decoding algorithm is shown in FIG. 6.
[0050] In Fig. 6. first, an initialization of Ncand is providedand set i = M, blocks
501-502 of FIG. 6. A cost function R2MM ||sM -sM ||2 is computed for all constellation point, block 503. In some aspects, only e Ncand points that have the minimum cost are preserved. If Ncand > 2Mc, then preserve only the 2Mc points that have the minimum
cost. In a trellis implementation of a decoder, e.g with reference to the trellis diagram of FIG. 7, these states are denoted by the shaded circles. These states can also be referred to as the "preferred" states.
[0051] For each of the preferred states selected i, a cost metric associated with each transition from a preferred state of the Mth layer to one of the 2Mc candidate constellation points for the (M-l)th layer is computed, block 505. An individual cost metric can be computed as:

[0052] This creates a total of Ncand2Mc candidate pairs [sM, sM_{ ], each with an
associated cost metric. The pairs are indicated by the "dotted lines" in FIG. 7, for a
trellis implementation
[0053] From a mathematical standpoint, it may be observed that the term
6 is essentially computed already been computed earlier in

block 503 of FIG . 6, and thus need not be re-computed when performing later
computations, e.g. in block 505. Further, the same observation applies to the cost
metric computations at subsequent stages i, i.e., the state cost metric computed for the

WO 2006/130804 PCT/US2006/021379
(i+l)th stage can be stored and re-used during computation of a state cost metric for the ith stage, or layer, of the trellis. Similarly, need only be computed
Ncmd times initially, and can also be stored and re-used for the rest of the Ncand2Mc
computations. The same observation applies with respect to the computation of metrics for the subsequent stages i.
[0054] Then, from the Ncand2Mc pairs or "dotted paths" shown in FIG. 7, save to memory only the Ncand preferred transitions from layer M to layer M-l having the
minimum cost, block 506. Also save to memory the constellation points and costs associated with those preferred transitions. The pairs having minimum cost are denoted by the solid lines in FIG. 8. These paths and costs are stored along with the stored paths and costs from the previous layer to create a record of the trellis path traversed. These paths can also be referred to as the "preferred" transitions.
[0055] As illustrated by the loop back to the decrement block 504 in FIG. 5, blocks 505-507 are analogously performed for each subsequent layer up to layer 1. As previously described, only the Ncmd preferred transitions and associated constellation
points / costs need be saved in memory for each layer.
[0056] Once the layer 1 computations are finished, the final trellis diagram of FIG. 9
is obtained showing Ncand paths and candidate solution vectors. Eq. 5 can subsequently
be used to obtain the LLR for each bit.
[0057] As further refinements to the list sphere decoding algorithms, the optimization parameter Ncand can be varied depending on the constellation size, as well as across stages, depending on channel conditions for each tone or group of tones, or other factors. In an embodiment, Ncand may be dynamically adjusted to be greater in the presence of worse channel conditions, and lower in the presence of better channel conditions.
[0058] Note that in some aspects, the term La[y calculated in Eq. 5 can be omitted if unavailable, for example, if turbo-decoder iterations have yet to be performed, or if the turbo decoding is altogether decoupled from the list sphere decoding. In certain aspects, a list sphere decoder may be concatenated with a turbo decoder, and soft information calculated by the list sphere decoder may be iteratively exchanged with the turbo decoder, and vice versa, until a convergent solution is obtained.

WO 2006/130804 PCT/US2006/021379

[0059] Note also that, in general, the decoding procedure described herein may also be implemented using alternative criteria to identify preferred states of each layer. For example, instead of preserving only the Ncand states or transitions having the lowest computed cost metrics, an implementation may preserve those states or transitions whose cost metrics meet certain other criteria, such as being below a preferred cost value. Such alternative criteria also fall within the scope of the present disclosure. [0060] It should be noted, that the above procedures may easily be applied to multi-codeword (MCW) systems, wherein the constellation sizes vary across each stage. In an embodiment, Ncand can be set a constant 256 across all stages to give acceptable performance for an SCW 4x4 MIMO system.
[0061] Further, while FIGS. 6-9 are generally discussed in the context of utilizing a trellis diagram, the above methodologies may be utilized without usage of a trellis methodology. For example, the cost metrics may calculated for each layer and constellation point for the layer, without using trellis diagram representation. In such a case, the above calculations may be made for MIMO layers, instead of trellis stages, and constellation point, instead of states of the trellis stages.
[0062] FIG. 10 shows a block diagram of an embodiment of an AP lOx and two ATs 20x and 20y in multiple-access multi-carrier communication system 100. At AP lOx, a transmit (TX) data processor 514 receives traffic data (i.e., information bits) from a data source 512 and signaling and other information from a controller 520 and a scheduler 530. For example, controller 520 may provide power control (PC) commands that are used to adjust the transmit power of the active ATs, and scheduler 530 may provide assignments of carriers for the ATs. These various types of data may be sent on different transport channels. TX data processor 514 encodes and modulates the received data using multi-carrier modulation (e.g., OFDM) to provide modulated data (e.g., OFDM symbols). A transmitter unit (TMTR) 516 then processes the modulated data to generate a downlink modulated signal that is then transmitted from an antenna 518. [0063] At each of ATs 20x and 20y, the transmitted and modulated signal is received by an antenna 552 and provided to a receiver unit (RCVR) 554. Receiver unit 554 processes and digitizes the received signal to provide samples. A received (RX) data processor 556 then demodulates and decodes the samples to provide decoded data, which may include recovered traffic data, messages, signaling, and so on. The traffic data may be provided to a data sink 558, and the carrier assignment and PC commands sent for the terminal are provided to a controller 560.

WO 2006/130804 PCT/US2006/021379

[0064] Controller 560 directs data transmission on the uplink using the resources that have been assigned to the terminal and indicated in the received assignment. Controller 560 further injects the erasure signature packets when the there is not actual data to transmit, yet desires to keep the assigned resources.
[0065] Controller 520 directs data transmission on the downlink using the resources that have been assigned to the terminal. Controller 520 further injects the erasure signature packets when the there is not actual data to transmit, yet desires to keep the assigned resources.
[0066] For each active terminal 120, a TX data processor 574 receives traffic data from a data source 572 and signaling and other information from controller 560. For example, controller 560 may provide information indicative of channel quality information, required transmit power, the maximum transmit power, or the difference between the maximum and required transmit powers for the terminal. The various types of data are coded and modulated by TX data processor 574 using the assigned carriers and further processed by a transmitter unit 576 to generate an uplink modulated signal that is then transmitted from antenna 552.
[0067] At AP 10x, the transmitted and modulated signals from the ATs are received by antenna 518, processed by a receiver unit 532, and demodulated and decoded by an RX data processor 534. Receiver unit 532 may estimate the received signal quality (e.g., the received signal-to-noise ratio (SNR)) for each terminal and provide this information to controller 520. Controller 520 may then derive the PC commands for each terminal such that the received signal quality for the terminal is maintained within an acceptable range. RX data processor 534 provides the recovered feedback information (e.g., the required transmit power) for each terminal to controller 520 and scheduler 530.
[0068] Scheduler 530 may provide an indication to controller 520 to maintain the resources. This indication is provided if more data is scheduled to be transmitted. For the AT 20x, the controller 560 may determine if resources required to be maintained. In certain aspects, controller 520 may perform instructions that provide the functionality of scheduler 530.
[0069] Further, controller 560 may perform all or some of the functions discussed with respect to FIGS. 1-9 with respect to the access terminal.
[0070] The techniques described herein may be implemented by various means. For example, these techniques may be implemented in hardware, software, or a combination thereof. For a hardware implementation, the processing units (e.g., controllers 520 and

WO 2006/130804 PCT/US2006/021379
560, TX and RX processors 514 and 534, and so on) for these techniques may be implemented within one or more application specific integrated circuits (ASICs), digital signal processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices (PLDs), field programmable gate arrays (FPGAs), processors, controllers, micro-controllers, microprocessors, other electronic units designed to perform the functions described herein, or a combination thereof.
[0071] For a software implementation, the techniques described herein may be implemented with modules (e.g., procedures, functions, and so on) that include the instructions that may be implemented by one or more processors to perform the functions described herein. The instructions may be stored in memory units, e.g., memory 522 in FIG. 10, on a removable media, or the like that may be read and executed by one or more processors (e.g., controllers 520). The memory unit(s) may be implemented within the processor or external to the processor, in which case it can be communicatively coupled to the processor via various means as is known in the art. [0072J Headings are included herein for reference and to aid in locating certain sections. These headings are not intended to limit the scope of the concepts described therein under, and these concepts may have applicability in other sections throughout the entire specification.
[0073] The previous description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

WO 2006/130804 PCT/US2006/021379
We Claim :
1. A method for list sphere decoding comprising:
receiving at least one codeword sent over a multiple-input multiple-output (MIMO) channel, wherein the at least one codeword comprises a plurality of layers, each layer comprising a constellation point of a plurality of candidate constellation points;
for each layer, computing a state cost metric using said codeword for each constellation point of the at least one layer, and selecting preferred states of the at least one layer whose state cost metrics meet first preferred criteria; and
for each of a plurality of constellation points of said layer, computing a state cost metric using said codeword for each transition from a preferred constellation point of said layer to each constellation point of a following layer, and selecting preferred transitions to said following layer whose state cost metrics meet second preferred criteria.
2. The method of claim 1, further comprising, for each layer, storing in a memory the state cost metrics associated with said selected preferred constellation points and transitions.
3. The method of claim 1, wherein meeting the first preferred criteria comprises being one of a candidate plurality of constellation point s having the lowest state costs for a constellation point.

4. The method of claim 3, wherein meeting the second preferred criteria comprises being one of a candidate plurality of transitions having the lowest constellation point costs for a layer.
5. The method of claim 4, wherein said candidate plurality can be variable across layers, and can be a function of the number of candidate constellation points for each layer.
6. The method of claim 5, wherein said codeword is a multiple-code word (MCW).
7. The method of claim 4, wherein said codeword is a single-code word (SCW).

WO 2006/130804

PCT/US2006/021379

8. The method of claim 1, further comprising storing in a memory said constellation point cost metric for a stage after computation, and re-using said stored metric when computing a constellation point cost metric during a following layer.
9. The method of claim 1, further comprising determining candidate codewords from said preferred constellation points and said preferred transitions.

10. The method of claim 9, further comprising computing overall cost metrics for said candidate codewords.
11. The method of claim 10, further comprising selecting a candidate codeword having the lowest overall cost metric.
12. The method of claim 1, wherein the first and second preferred criteria are met when a computed constellation point cost metric is one of a candidate plurality of constellation point cost metrics having the lowest values for a given layer, and wherein said candidate plurality can be variable across layers.
13. The method of claim 12, wherein said candidate plurality is constant for all layers.
14. The method of claim 1, wherein the first preferred criteria are met when a computed state cost metric is lower than a specified threshold.

15. The method of claim 1, further comprising calculating a soft extrinsic information metric for each bit.
16. The method of claim 15, wherein said soft extrinsic information metric for each bit is provided to a turbo decoder.
17. The method of claim 16, wherein said turbo decoder further generates an additional soft extrinsic information metric for each bit.

WO 2006/130804 PCT/US2006/021379
18. The method of claim 17, wherein each layer comprises a stage of a trellis and each constellation point comprises a state of one stage of the trellis.
19. A decoding method comprising:
receiving a codeword comprising a plurality of symbols, each symbol corresponding to at least one of a plurality of candidate constellation points;
for a first symbol:
computing a cost metric for each candidate constellation point of said first symbol;
storing in a memory only those candidate constellation points whose computed cost metrics meet first preferred criteria;
for each following symbol, and for each candidate constellation point previously stored in said memory for the symbol immediately preceding said following symbol:
computing a cost metric for each candidate transition from said previously stored candidate constellation point to a candidate constellation point of said following symbol; and
storing in said memory only those candidate transitions whose computed cost metrics meet second preferred criteria.
20. The method of claim 19, further comprising determining candidate codewords from the candidate constellation points and candidate transitions stored in said memory.
21. The method of claim 19, wherein said codeword is transmitted over a MIMO channel, and said symbols of said codeword are simultaneously transmitted on different antennas over said MEMO channel.
22. The method of claim 21, wherein said MIMO channel is characterized by a channel matrix H; further comprising providing an upper triangular matrix R related to the matrix H by a unitary transformation, and wherein said computed cost metric for each symbol is a function of the coefficients in the rows of the matrix R corresponding to said symbol and all symbols preceding said symbol.

WO 2006/130804 PCT/US2006/021379
23. The method of claim 19, wherein meeting said first preferred criteria comprises being a candidate constellation point having an associated cost metric that is one of the a first candidate plurality of lowest cost metrics for all candidate constellation points.
24. The method of claim 23, wherein said first candidate plurality is less than the total number of candidate constellation points for a symbol.
25. The method of claim 24, wherein meeting said second preferred criteria comprises being a candidate transition having an associated cost metric that is one of a second candidate plurality of lowest cost metrics for all candidate transitions for that symbol, wherein said second candidate plurality is less than the total number of candidate transitions from a candidate constellation point of the preceding symbol to a candidate constellation point of the following symbol, and wherein said first candidate plurality is equal to said second candidate plurality.
26. The method of claim 19, wherein meeting said second preferred criteria comprises being a candidate transition having an associated cost metric that is one of a second candidate plurality of lowest cost metrics for all candidate transitions.
27. The method of claim 26, wherein said second candidate plurality is less than the total number of candidate transitions from a candidate constellation point of the preceding symbol to a candidate constellation point of the following symbol.
28. The method of claim 19, wherein each of said following symbols comprises a symbol following in time.
29. The method of claim 19, wherein each of said following symbols comprises a symbol following in rank.
30. A decoder apparatus comprising:
a receiver configured to receive at least one codeword sent over a multiple-input multiple-output (MEMO) channel, wherein the at least one codeword comprises a plurality of layers, each layer comprising a constellation point selected from a plurality of candidate constellation points; and

WO 2006/130804 PCT/US2006/021379

a processor configured to, for at least one layer, compute a constellation point metric for the at least one layer, and to select preferred constellation points of the at least one layer whose state cost metrics meet first preferred criteria; the processor further configured to compute a constellation point cost metric for each transition from a preferred constellation point of the layer to each constellation point of a following layer, and selecting preferred transitions to said following layer whose constellation point cost metrics meet second preferred criteria.
31. The apparatus of claim 30, further comprising a memory for storing, for each stage,
the state cost metrics associated with the preferred states and the preferred transitions.
32. The apparatus of claim 30, wherein meeting the first preferred criteria comprises
being one of a candidate plurality states having the lowest state costs for the stage.
33. The apparatus of claim 32, wherein meeting the second preferred criteria comprises being one of said candidate plurality of transitions having the lowest state costs for the stage.
34. The apparatus of claim 33, wherein the MIMO channel is characterized by a channel matrix H, wherein the rank of the matrix H is M, further comprising providing an upper triangular matrix R related to said channel matrix H, wherein said state cost
metric for each state of the number of stages is expressed as
wherein the state cost metric of said Mth stage is expressed as
wherein:
R is an upper triangular matrix related to the matrix H by a unitary transformation;
RMM denotes the entry of said matrix R corresponding to the Mth row and the Mth column;
sM denotes a candidate constellation point of the Mth layer; and
SM denotes the Mth entry of the zero-forcing solution

WO 2006/130804 PCT/US2006/021379
35. The apparatus of claim 34, wherein the state cost metric for each transition of the ith stage is expressed as follows:

; wherein
i denotes an index to a stage of the trellis;
Rij denotes the entry of the R matrix corresponding to the ith row and the jth column;
si denotes a candidate constellation point of the ith layer; and
s' denotes the ith entry of the zero-forcing solution
36. The apparatus of claim 30, further comprising a soft information processor for computing soft extrinsic information for each bit associated with each constellation point associated with each layer of a candidate codeword, wherein a candidate codeword can be determined from said preferred states and preferred transitions.
37. A decoder apparatus comprising:
means for receiving at least one codeword sent over a multiple-input multiple-output (MIMO) channel, wherein the at least one codeword comprises a plurality of layers, each layer comprising a constellation point selected from a plurality of candidate constellation points; and
means for determining preferred constellation points of at least onelayer and preferred transitions having constellation point cost metrics meeting first criteria for the at least one layer.
38. The apparatus of claim 37, wherein meeting said first criteria comprises being one
of a candidate plurality of states having the lowest state costs for each stage.
39. A processor readable media comprising instructions thereon that may be utilized by
a processor, the instructions comprising:
instructions for a first symbol, of a codeword comprising a plurality of symbols, each symbol corresponding to at least one of a plurality of candidate constellation points, computing a cost metric for each candidate constellation point of said first symbol;

WO 2006/130804 PCT/US2006/021379

instructions for storing in a memory only those candidate constellation points whose computed cost metrics meet first preferred criteria; and
instructions, for each following symbol and for each candidate constellation point previously stored in said memory for the symbol immediately preceding said following symbol, computing a cost metric for each candidate transition from said previously stored candidate constellation point to a candidate constellation point of said following symbol; and
40. The processor readable media of claim 39, further comprising instructions for storing in said memory only those candidate transitions whose computed cost metrics meet second preferred criteria.

ABSTRACT
"SPHERE DECODING APPARATUS FOR MIMO CHANNEL"
Method and apparatuses for decoding codewords over a MIMO channel are provided. According to one aspect of the disclosure, a cost function is computed for each constellation point of an Mth rankor spatial layer and Ncand of those constellation points having minimum cost are preserved as candidate points, where Ncand is a parameter specified to the decoding algorithm. In addition, a cost function may be computed for all possible transitions from the Ncand candidate points of the Mth rank to ail possible constellations points of the (M-l)th spatial layer, and AA of those transitions having minimum cost are preserved as candidate points. The process is repeated for all spatial layers, resulting in the identification of Ncand candidate codewords and their associated cost functions. The algorithm is derived from the list sphere decoding method.

Documents:

2135-MUMNP-2007-ABSTRACT(20-1-2012).pdf

2135-mumnp-2007-abstract.doc

2135-mumnp-2007-abstract.pdf

2135-MUMNP-2007-CLAIMS(AMENDED)-(20-1-2012).pdf

2135-MUMNP-2007-CLAIMS(AMENDED)-(26-3-2012).pdf

2135-MUMNP-2007-CLAIMS(MARKED COPY)-(20-1-2012).pdf

2135-mumnp-2007-claims.doc

2135-mumnp-2007-claims.pdf

2135-MUMNP-2007-CORRESPONDENCE 16-6-2008.pdf

2135-MUMNP-2007-CORRESPONDENCE(12-9-2011).pdf

2135-MUMNP-2007-CORRESPONDENCE(13-3-2012).pdf

2135-mumnp-2007-correspondence(19-3-2008).pdf

2135-MUMNP-2007-CORRESPONDENCE(27-1-2012).pdf

2135-mumnp-2007-correspondence-others.pdf

2135-mumnp-2007-correspondence-received.pdf

2135-mumnp-2007-description (complete).pdf

2135-MUMNP-2007-DRAWING(20-1-2012).pdf

2135-mumnp-2007-drawings.pdf

2135-MUMNP-2007-FORM 1(20-1-2012).pdf

2135-mumnp-2007-form 2(title page)-(17-12-2007).pdf

2135-MUMNP-2007-FORM 2(TITLE PAGE)-(20-1-2012).pdf

2135-MUMNP-2007-FORM 26(20-1-2012).pdf

2135-MUMNP-2007-FORM 3 16-6-2008.pdf

2135-MUMNP-2007-FORM 3(12-9-2011).pdf

2135-MUMNP-2007-FORM 3(20-1-2012).pdf

2135-MUMNP-2007-FORM PCT-IB-304(20-1-2012).pdf

2135-mumnp-2007-form-1.pdf

2135-mumnp-2007-form-18.pdf

2135-mumnp-2007-form-2-1.doc

2135-mumnp-2007-form-2-2.doc

2135-mumnp-2007-form-2-3.doc

2135-mumnp-2007-form-2.doc

2135-mumnp-2007-form-2.pdf

2135-mumnp-2007-form-26.pdf

2135-mumnp-2007-form-3.pdf

2135-mumnp-2007-form-5.pdf

2135-mumnp-2007-form-pct-isa-237.pdf

2135-mumnp-2007-form-pct-separate sheet-237.pdf

2135-MUMNP-2007-KOREAN DOCUMENT(27-1-2012).pdf

2135-mumnp-2007-pct-search report.pdf

2135-MUMNP-2007-PETITION UNDER RULE 137(20-1-2012).pdf

2135-MUMNP-2007-PROSECUTION HISTORY OF EP DOCUMENT(20-1-2012).pdf

2135-MUMNP-2007-PROSECUTION HISTORY OF US DOCUMENT(20-1-2012).pdf

2135-MUMNP-2007-REPLY TO EXAMINATION REPORT(20-1-2012).pdf

2135-MUMNP-2007-REPLY TO HEARING(26-3-2012).pdf

2135-MUMNP-2007-SPECIFICATION(AMENDED)-(26-3-2012).pdf

2135-MUMNP-2007-TAIWAN DOCUMENT(27-1-2012).pdf

2135-mumnp-2007-wo international publication report(17-12-2007).pdf

abstract1.jpg

« Previous Patent

Next Patent »

Patent Number

251876

Indian Patent Application Number

2135/MUMNP/2007

PG Journal Number

16/2012

Publication Date

20-Apr-2012

Grant Date

12-Apr-2012

Date of Filing

17-Dec-2007

Name of Patentee

QUALCOMM INCORPORATED

Applicant Address

5775 MORESHOUSE DRIVE, SAN DIEGO, CALIFORNIA 92121-1714,

Inventors:

#	Inventor's Name	Inventor's Address
1	SAMPATH HEMANTH	3745 CHRMEL VIEW ROAD #6, SAN DIEGO, CALIFORNIA 92130,
2	KADOUS TAMER	11116 LVY HILL DRIVE, SAN DIEGO, CALIFORNIA 92131

PCT International Classification Number

H03M13/41,H04B7/08

PCT International Application Number

PCT/US2006/021379

PCT International Filing date

2006-06-01

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1	60/686,819	2005-06-01	U.S.A.