Scalable VLSI architecture for K-best breadth-first decoding

In some embodiments, a device includes a multiple-input multiple-output (“MIMO”) decoder module coupled to a first log-likelihood-ratio (“LLR”) computing unit. The decoder module includes at least one processing unit and at least one sorting unit. The decoder module preferably uses a K-best breadth-first search method to decode data from MIMO sources. In some embodiments, a method includes receiving data representing a vector of receive signal samples detected by multiple receive transceivers. The method further includes performing a K-best breadth-first search on the data to obtain an estimated constellation point. The method further includes providing a user data stream based at least in part on the estimated constellation point.

BACKGROUND

As wireless technology provides faster and more inexpensive devices, it enables people to be more mobile. Such mobility is desirable to many because it enables better collaboration and more efficient transactions.

To improve the performance of wireless devices, and hence improve mobility, designers are turning to the use of multiple-input multiple-output (“MIMO”) systems. MIMO systems have more than one transmitter and more than one receiver, and hence, more than one wireless channel. Such systems work well with existing orthogonal frequency-division multiplexing (“OFDM”) methods of transmission because the orthogonal nature of the carriers helps to prevent interference between the adjacent carriers.

At any given frequency, channel output y is related to channel input s by a matrix H such that:
y=H s+n,(1)
where s, y and n are vectors. The input vector s has MTelements and the output vector y and noise vector n has MRelements. MTand MRare the number of transmit and receive transceivers, respectively. Input vector s is a member of a signal constellation having MTdimensions (ΩMT). Because of this dimensionality, the decoding problem may become computationally demanding. For example, an algorithm to decode y in order to determine which constellation point ŝ was sent over the wireless channel requires solving the equation

s^=arg⁢mins∈ΩMT⁢y-Hs2.(2)
This problem has complexity that grows exponentially with the number of transmit transceivers MT. For instance, with 4 transmit transceivers (MT=4) using 16-QAM, there are in each symbol interval 164or 65,536 constellation points in each frequency bin to be searched in order to locate the signal. Any reduction in this complexity would be advantageous.

SUMMARY

The problem outlined above may at least in part be addressed by K-best breadth-first decoding methods and devices that employ such methods. In some embodiments, a device includes a multiple-input multiple-output (“MIMO”) decoder module coupled to a first log-likelihood-ratio (“LLR”) computing unit. The decoder module includes at least one processing unit and at least one sorting unit. The decoder module preferably uses a K-best breadth-first search method to decode data from MIMO sources.

In some embodiments, a method includes receiving data representing a vector of receive signal samples detected by multiple receive transceivers. The method further includes performing a K-best breadth-first search on the data to obtain an estimated constellation point. The method further includes providing a user data stream based at least in part on the estimated constellation point.

In some embodiments, a mobile device includes a MIMO decoder. The MIMO decoder is preferably configured to perform a K-best breadth-first search as part of converting a receive signal into a data stream provided to a user.

DETAILED DESCRIPTION

It should be understood at the outset that although an illustrative implementation appears below, the present system may be implemented using any number of techniques whether currently known or later developed. The present disclosure should in no way be limited to the illustrative implementations, drawings, and techniques illustrated below, but may be modified within the scope of the appended claims along with their full scope of equivalents.

FIG. 1illustrates an example of a wireless channel transmission: a wireless Internet connection. A combination modem/router104serves as a wireless access node to support a wireless channel106through which wireless devices108access the Internet102. In some embodiments, the wireless device108comprises a computer. In other embodiments, the wireless device108comprises a personal digital assistant (PDA), cellular phone, etc. In some embodiments, the wireless device108is mobile (e.g., a notebook computer).

FIG. 2illustrates how a wireless device108interfaces with the wireless channel106. Transceiver input/output sources206send and receive data over the wireless channel106, and couple to a multiple-input multiple-output (“MIMO”) encoder/decoder module208, where received data are decoded or data to be transmitted are encoded, preferably using orthogonal frequency-division multiplexing (“OFDM”) encoding techniques.

FIG. 3illustrates how data flows through a MIMO system. Some elements ofFIG. 3will be elaborated upon in the discussion of subsequent figures. Assuming OFDM using 16 quadrature amplitude modulation (“QAM”) modulation, MIMO encoder module302uses the data to be transmitted to modulate the amplitudes of two carrier waves, which are out of phase by 90° with respect to each other. Next, the modulated data is transmitted through transmit transceivers304. At this point, the data is referred to as the transmitted signal or the transmitted symbol. As the transmitted signal passes through the wireless channel106it is altered by the transmission characteristics of the channel. The transmitted signal is also altered by noise. This noise is assumed to be additive, white, and Gaussian. Thus, the signal received by the receive transceivers308generally appears quite different than the signal sent by the transmit transceivers304. This altered signal is referred to as the receive signal, and is provided to a MIMO decoder module310.

In an alternative embodiment, a different method of modulation or combination of modulation methods is used such as phase shift keying, amplitude shift keying, frequency shift keying, minimum shift keying, 64-QAM, etc.

FIG. 4is a block diagram of a transmit transceiver304. First, data to be transmitted is transformed using an inverse fast Fourier transformation (“IFFT”)402. Next, a cyclic prefix is added to the data404. Finally, the data is converted from digital to analog form (“D/A”)406in preparation for transmission.

FIG. 5is a block diagram of a receive transceiver. First, the received data is converted from analog to digital form (“A/D”)502. Next, the cyclic prefix is removed from the data504. Finally, the data is transformed using a fast Fourier transformation506.

Before considering the MIMO decoder module310, a discussion of decoding may be helpful. Decoding is the idea of estimating the transmit signal most probably sent by transmit transceivers304based on the signal received by receive transceivers308. Considering a mapping of the entire constellation of possibly transmitted signals onto a coordinate system, a similarly mapped received signal will not be located exactly on the transmitted signal, as expected, because of the alteration described in the discussion ofFIG. 3. The received signal will be located somewhere in between all the possibly transmitted signals.

Our task is to identify which of the possibly transmitted signals was actually sent based on the received signal. If we assume that the possibly transmitted signal closest to the received signal is the signal actually sent, a logical approach would be to calculate and store the distances between the received signal and each possibly transmitted signal. We could then compare all the stored distances, and select the possibly transmitted signal corresponding to the minimum distance as the signal actually sent. However, the complexity of such an approach soon becomes unmanageable, as discussed above. One way to circumvent the complexity is to exclude possibly transmitted signals which must be farther away than others without calculating or storing the distance for the excluded signals. However, how do we know certain points are farther away from others in the mapping without calculating their distances?

The answer lies in the idea of partial Euclidean distances, or metrics. If we build a node tree such that each node corresponds to one possibly transmitted signal, the number of levels equals twice the number of transmit transceivers, and the levels alternate between representing real and complex values, we may uniquely describe the distance to a possibly transmitted signal as the vector s in equation 1. Each node in the tree represents an element of the vector sRwhere

sR=[real⁢{s}imag⁢{s}]
We may calculate partial Euclidean distances by calculating various elements of the vector s, but the vector need not be complete before we decide to remove (or “prune”) a node in the tree from further search. Nodes that are estimated to have a low likelihood of being part of the vector representing the possibly transmitted signal with the minimum distance to the received signal are pruned. Additionally, because the distances are non-negative, once we decide to prune a node from search, we may prune all successor nodes without further calculation or storage. We may do so because any node connected to the removed ancestor node will be farther away from the received signal, and consequently not a candidate for the signal actually sent. Hence, we need not waste computing resources calculating or storing these pruned nodes and leaves. However, by doing so, our results are only as certain as our likelihood estimation.

FIG. 6illustrates a K-best breadth-first tree traversal algorithm for pruning that implements the decoding. Each node in the tree represents real or imaginary part of a possibly transmitted QAM signal. The number of branches per node is the square root of the QAM size for the real search. For example, 16-QAM results in each node having four branches. Beginning at root node602, the distance to each of the four nodes on the level below it are calculated. This illustrates the breadth-first aspect of the method, i.e., distances for nodes on the same row are calculated before distances for nodes on another row are calculated. For K=2, the nodes corresponding to the two smallest distances are selected: nodes604and606. These nodes are named survivor nodes because they are the only nodes to escape pruning. This illustrates the K-best aspect of the method, i.e., the number K represents the amount of survivor nodes. The value for K may be selected, adjusted as needed, and optimized via simulation. Next, from each survivor node, the distance to each of 4 corresponding nodes on the level below it are calculated, and the K-best selection process continues until the leaf row is reached. For illustration purposes, the node tree depicted is small.

At the leaf row, all survivor nodes are used for log-likelihood-ratio (“LLR”) computation. Because we are not absolutely certain that we have not pruned the signal actually sent, K is preferably sufficiently large to provide performance on par with maximum-likelihood performance, which would not prune the node with the smallest distance during the search.

Turning toFIG. 7and one implementation of the K-best, breadth-first search algorithm described above, data from the receive transceivers308are sent to a channel estimator712before entering the decoder module310. The channel estimator712helps ensure proper equalization, i.e., compensation for phase and amplitude introduced due to wireless multi-path channel. The channel estimator712also supplies the decoder module310with the matrix H. Computation of ∥y−Hs∥2could be rewritten as

yR=[real⁢{y}imag⁢{y}],
HRis the 2MR×2MTreal domain representation for the channel matrix H where

HR=[real⁢{H}-imag⁢{H}imag⁢{H}real⁢{H}]
and sRis 2MT×1 real domain representation of transmitted vector given by

sR=[real⁢{s}imag⁢{s}],
The matrix HRis then decomposed by QR decomposition logic714into matrices Q and R. Q is 2MR×2MT, and has orthonormal columns. R is 2MT×2MT, and upper triangular, i.e., all elements below the main diagonal are zero. Q and R are calculated such that

HR=Q⁡[R0]=[Q1Q2]⁡[R0],(3)
where 0 is a (2MR−2MT)×2MTzero matrix, Q1is a 2MR×2MTmatrix and Q2is a 2MR×(2MR−2MT) matrix. In order to mathematically prune nodes, a constraint may be placed on equation 2,
d(sR)=∥yR−HRsR∥2, whered(sR)<r2,   (4)
thus pruning nodes farther away than a distance, r. Applying the decomposition result, equation (3), to equation (4):
∥yR−HRsR∥<r2,   (5)

Multiplication logic704performs the multiplication by Q1T, and K-best search logic706implements the breadth-first search on the data. The logic706calculates the elements for the sRvector and the corresponding distance to each node by calculating a b-metric and a T-metric. The logic706calculates the b-metric and T-metric using

The full distance d(sR) from the received signal to the possibly transmitted signal is the partial Euclidean distance of a leaf, so d(sR)=T1(sR). The approximated solution is the point corresponding to the lowest T1(sR).

The log-likelihood-ratio (“LLR”) computing unit708computes the bit decision reliability (soft-decision) of the K-best detection. Denoting the kthinformation bit as xk, there exists a unique mapping between the bit sequence and the transmitted signal vector: [x1. . . xMT·log2(Q)]T=bit mapping(s), where Q is the QAM constellation size.

Equation (12) illustrates computation of the LLR based on survivor nodes.

After error correction, the solution is then provided to a user via a data stream. The data stream can take any number of formats such as image data, sound data, etc. The solution can also be a piece of information that the wireless device108uses to ultimately cause a data stream to be provided to a user. The solution can also be a piece of information that a data stream provided to the user is based on.

Preferably, the LLR computing unit708and forward correction logic710are not part of the MIMO decoder module310. In an alternative embodiment, they are part of the MIMO decoder module310.

FIG. 8illustrates the architecture of the K-best breadth-first real search logic (“K-Best search logic”)706, for a 4×4 transceiver configuration, and its connection to the LLR computing unit708. Each processing unit (e.g.804) in the search logic processes one level of the node tree. Every two levels of the node tree correspond to the real and imaginary part of the partial Euclidean distances respectively. As such, for a 1×1 configuration the outputs for processing unit #2804are passed to the LLR802by a multiplexer (“MUX”)808. Similarly, 2×2 and 3×3 configurations correspond to processing units #4and #6respectively (not shown). For a 4×4 configuration, the outputs for processing unit #8806are passed to the LLR802by the MUX808. Configuration information is passed to each processing unit via the wires such as the QAM_mode and ant_mode parameters. Other parameters may also be passed, allowing for custom parameterization. Each processing unit receives data about the R matrix from the QR decomposition logic714via the wire labeled R_data y_hat_data. Each processing unit also receives ŷ data from the multiplication logic704. Preferably, the same wire delivers both pieces of data to each processing unit. In an alternative embodiment, separate wires are used. Some processing units also receive survivor metric and survivor symbol information as inputs via the wires labeled survivor_metric and survivor_sym. The MUX808supplies the LLR computing unit802with the ultimate survivor metric and symbol based on the configuration information.

FIG. 9illustrates the ability to map non-square configurations to an equivalent square configuration using the QR decomposition as long as MTis less than or equal to MR. For example, in the 3×3 scenario902, the decomposition results in a 3×3 matrix R and 3×1 vector ŷ. However, in the 4×3 scenario904(representing an added transceiver), the decomposition results in a 3×3 R and a 3×1 ŷ as well. Hence, no modification to the search logic need be made when a input or output source is added or removed as long as MTis less than or equal to MR. In addition, because each processing unit can process QPSK, 16-QAM, and 64-QAM, among other modulation methods, the designed architecture can support any combination of transceiver configurations.

FIG. 10is a block diagram of a processing unit explicitly showing the logical calculation of the b-metric and T-metric via the b-metric module1002and the T-metric module1004as described in equations 10 and 11. Considering the b-metric module1002first, ŷ data is input into MUX1006. R data (Rij) is multiplied with survivor symbol data (sR,i) at1008before being subtracted from ŷito form the b-metric at1010. The b-metric is then supplied to the MUX1006as feedback, and supplied to the T-metric module1004. The T-metric module1004multiplies R data (Rij) with sRdata (sR,i) at1012. The sRdata is preferably provided via a look-up table (not shown). The product is subtracted from the b-metric at1014. The difference is then squared at1016. The square is then added to the previous survivor metric (Ti+1) at1020.

The T-metric is then passed to K number of sorting units1022, K representing the number of survivor nodes. By adding more sorting units1022, we can increase the value of K, thus making the processing unit scalable. Initially, all the registers in the sorting units are set to the maximum possible value. At each incoming metric, the larger value of the two inputs is passed to the next sorting unit while the smaller one is stored at the current sorting unit.

FIG. 11illustrates the architecture for parallel search logic, an alternative embodiment, to increase the throughput of the K-best search. This architecture doubles throughput without scaling clock speed by adding another K-best search logic1106and LLR computing unit1108parallel to a first K-best search logic1102and LLR unit1104. R and ŷ data are input into the MUX1101, and supplied to either parallel branch. DEMUX1110then outputs the LLR data. This parallelization can occur more than once.

FIG. 12illustrates the architecture for folded processing units, an alternative embodiment. This architecture halves the throughput, but reduces area complexity. Each unit1202-1206processes two levels of the node tree by feeding its output back into its input once. For example, after the processing unit1202finishes calculating the b-metric and T-metric as described above, the output is fed back into the same processing unit1202, and it calculates the next iteration of metrics. Only then does the output travel to the processing unit1204. The MUXs1208-1210enable the processing units to select the correct input. In even further alternative embodiments, each processing unit is responsible for any number of iterations.

FIG. 13illustrates a sorting unit, specifically a single-input sorting unit. As discussed withFIG. 10, a switch comparator1302compares a metric (“M2”) stored in storage1303with an incoming metric (“M1”) preferably by subtracting them. The sign bit1304of the answer indicates which metric is larger, and the switch comparator1302forwards the larger metric (“LM”) and routes the smaller metric (“SM”) to storage1303.

FIG. 14illustrates a double-input sorting unit for increased throughput, an alternative embodiment. Here, M1and M3are input metrics and M2and M4are stored metrics. First, M1and M2are compared via a 2-input switch comparator1402, the larger metric being L1and the smaller metric being S2. Next, M3and M4are compared via another 2-input switch comparator1404, the larger metric being L2and the smaller metric being S2. Finally, the outputs of the first two comparisons are input into a 4-input switch comparator1406resulting in LM1and LM2, the two largest metrics, being forwarded, and SM1and SM2, the two smallest metrics, being stored1408,1410. However, because the sort preferably occurs in two stages, critical path delay will increase.

FIG. 15illustrates a high-speed double-input sorting unit for increased throughput with the same critical path delay as a single-input sorting unit. In order to select two smaller and larger metrics, 6 comparisons are preferably taken simultaneously:X1=MSB {M1-M2},X2=MSB {M1-M3},X3=MSB {M1-M4},X4=MSB {M2-M3},X5=MSB {M2-M4}, andX6=MSB {M3-M4},
where if the most significant bit (“MSB”) of the difference of A and B equals 1, then A is less than B (if MSB {A−B}=1, then A<B). Hence,if X2=1, X3=1, X4=1, and X5=1, then M1and M2are the two smallest metrics.If X1=1, X3=1, X4≠1, and X6=1, then M1and M2are the two smallest metrics.If X1=1, X2=1, X5≠1, and X6≠1, then M1and M2are the two smallest metrics.If X1≠1, X2≠1, X5=1, and X6=1, then M1and M2are the two smallest metrics.If X1≠1, X4=1, X3≠1, and X6≠1, then M1and M2are the two smallest metrics.
Otherwise, M3and M4are the two smallest metrics. Such an algorithm is programmed into the control logic1502, which supplies switch comparator1504with the necessary routing information. Specifically, the largest metrics, LM1and LM2, are output from the sorting unit, while the smallest metrics, SM1and SM2are stored in storage1506and1508respectively. Exclusive use of these high-speed sorting units enables a reduction of the total number of sorting units to K/2.

FIG. 16illustrates a method of implementing one embodiment of the algorithm described above. After beginning at1602, data is received from the receive transceivers at1604. Next, a K-best breadth-first search is performed to obtain an estimation of which constellation point was sent at1606. Next, at1608, the user is provided with a data stream based at least in part on the estimate before the end is reached at1610. Two or more of the various actions depicted can be combined together and performed simultaneously. Furthermore, the order can be reversed.

The system described above may be implemented on a wireless device such as any general-purpose computer.FIG. 17illustrates a typical, general-purpose computer system1780suitable for implementing one or more embodiments disclosed herein. In various embodiments, the storage1784comprises volatile memory (e.g., random access memory), non-volatile storage (e.g., Flash memory, hard disk drive, CD ROM, etc.), and combinations thereof. The storage1784comprises software that is executed by the processor1782. One or more of the actions described herein are performed by the processor1782during execution of the software.

Also, techniques, systems, subsystems, and methods described and illustrated in the various embodiments as discrete or separate may be combined or integrated with other systems, modules, techniques, or methods without departing from the scope of the present disclosure. Other items shown or discussed as directly coupled or communicating with each other may be coupled through some interface or device, such that the items may no longer be considered directly coupled to each other but may still be indirectly coupled and in communication, whether electrically, mechanically, or otherwise with one another. Other examples of changes, substitutions, and alterations are ascertainable by one skilled in the art and could be made without departing from the spirit and scope disclosed herein.