US7782971B2 - Method and device for decoding a signal of multiple input/multiple output system - Google Patents
Method and device for decoding a signal of multiple input/multiple output system Download PDFInfo
- Publication number
- US7782971B2 US7782971B2 US11/662,854 US66285405A US7782971B2 US 7782971 B2 US7782971 B2 US 7782971B2 US 66285405 A US66285405 A US 66285405A US 7782971 B2 US7782971 B2 US 7782971B2
- Authority
- US
- United States
- Prior art keywords
- node
- level
- traversal
- norm
- tree
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related, expires
Links
- 238000000034 method Methods 0.000 title claims abstract description 46
- 239000011159 matrix material Substances 0.000 claims abstract description 36
- 238000011156 evaluation Methods 0.000 claims abstract description 4
- 239000013598 vector Substances 0.000 claims description 35
- 238000004364 calculation method Methods 0.000 claims description 17
- 230000005540 biological transmission Effects 0.000 claims description 10
- 238000004891 communication Methods 0.000 claims description 4
- 230000003247 decreasing effect Effects 0.000 claims description 3
- 238000000354 decomposition reaction Methods 0.000 abstract description 6
- 238000012545 processing Methods 0.000 abstract description 6
- 238000007476 Maximum Likelihood Methods 0.000 description 10
- 238000013459 approach Methods 0.000 description 9
- 238000010586 diagram Methods 0.000 description 6
- 230000008901 benefit Effects 0.000 description 5
- 238000001514 detection method Methods 0.000 description 5
- 238000013138 pruning Methods 0.000 description 5
- 230000006870 function Effects 0.000 description 4
- 238000005457 optimization Methods 0.000 description 4
- 230000009467 reduction Effects 0.000 description 4
- 230000015556 catabolic process Effects 0.000 description 3
- 238000006731 degradation reaction Methods 0.000 description 3
- 238000013461 design Methods 0.000 description 3
- 230000014509 gene expression Effects 0.000 description 3
- 238000010845 search algorithm Methods 0.000 description 3
- 230000009466 transformation Effects 0.000 description 3
- 238000004458 analytical method Methods 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 238000007796 conventional method Methods 0.000 description 1
- 230000007423 decrease Effects 0.000 description 1
- 230000003111 delayed effect Effects 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 238000005562 fading Methods 0.000 description 1
- JEIPFZHSYJVQDO-UHFFFAOYSA-N ferric oxide Chemical compound O=[Fe]O[Fe]=O JEIPFZHSYJVQDO-UHFFFAOYSA-N 0.000 description 1
- 230000010354 integration Effects 0.000 description 1
- 208000013409 limited attention Diseases 0.000 description 1
- 238000010295 mobile communication Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000012552 review Methods 0.000 description 1
- 238000000926 separation method Methods 0.000 description 1
- 229910052710 silicon Inorganic materials 0.000 description 1
- 239000010703 silicon Substances 0.000 description 1
- 238000000638 solvent extraction Methods 0.000 description 1
- 230000002311 subsequent effect Effects 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L25/00—Baseband systems
- H04L25/02—Details ; arrangements for supplying electrical power along data transmission lines
- H04L25/03—Shaping networks in transmitter or receiver, e.g. adaptive shaping networks
- H04L25/03006—Arrangements for removing intersymbol interference
- H04L25/03178—Arrangements involving sequence estimation techniques
- H04L25/03203—Trellis search techniques
- H04L25/03242—Methods involving sphere decoding
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L1/00—Arrangements for detecting or preventing errors in the information received
- H04L1/02—Arrangements for detecting or preventing errors in the information received by diversity reception
- H04L1/06—Arrangements for detecting or preventing errors in the information received by diversity reception using space diversity
- H04L1/0618—Space-time coding
- H04L1/0637—Properties of the code
- H04L1/0656—Cyclotomic systems, e.g. Bell Labs Layered Space-Time [BLAST]
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L25/00—Baseband systems
- H04L25/02—Details ; arrangements for supplying electrical power along data transmission lines
- H04L25/03—Shaping networks in transmitter or receiver, e.g. adaptive shaping networks
- H04L25/03006—Arrangements for removing intersymbol interference
- H04L25/03178—Arrangements involving sequence estimation techniques
- H04L25/03203—Trellis search techniques
Definitions
- the invention relates to methods and devices for decoding a received signal in a multiple input/multiple output system having linear and noisy transmission characteristics.
- MIMO multiple-input multiple-output
- Examples include multiantenna systems or multiuser detection in CDMA.
- the coordinates s i ⁇ O of the symbols s are composed of values chosen from the complex constellation O.
- Real constellations can be considered as a special case.
- a typical solution of (1) for maximum likelihood (ML) detection involves the computation of
- the vectors s are transformed (via a unitary matrix Q) into a space where matrix R is triangular because, as described below, a triangular matrix R allows an efficient implementation of a recursive search algorithm.
- a transformation via a unitary matrix Q leaves the traditional l 2 -norm of the trans-formed vectors unchanged, and therefore (2) is equivalent to a minimization of the Euclidean distance between Hs and y.
- a first aspect of the present invention relates to the method of claim 1 .
- the vectors s are (as in the conventional method described above) transformed (via unitary matrix Q) into a space where matrix R is triangular because, as described below, a triangular matrix R allows an efficient implementation of a recursive search algorithm.
- a norm other than the (squared) l 2 -norm is used. This is, at first sight, a crass contradiction to using a unitary transformation matrix Q (which preserves the l 2 -norm but not other norms), but it has been found that the algorithm will still converge to reasonable values and provide decoding with low error rate.
- using norms other than the l 2 -norm which is expensive to calculate, allows a more efficient implementation of the algorithm in silicon.
- a particularly advantageous norm for application in the first aspect of the invention is the l ⁇ -norm with
- An other useful norm for application in the first aspect of the invention is the l 1 -norm with
- a second aspect of the present invention is described in claim 12 .
- the method comprises at least one traversal of a tree.
- the leaves of the tree represent the possible signal vectors s.
- the traversal comprises the repeated execution of two steps a) and b) while descending along said path through levels i of said tree.
- the steps are step a) operating a first computing means for selecting a next child node in level i from a parent node in level i+1, and
- step b) operating a second computing means for selecting a next node in level j>i other than the parent node to be used in case that a next or future traversal has to start at level j.
- steps a) and b) By the, advantageously concurrent, execution of steps a) and b), it becomes possible to go back to a any higher level quickly, in case that the search ends at a dead end or a sphere constraint is applied, as described below.
- Each tree traversal comprises repeated steps of selecting a next node in level i given a node in level i+1 by finding the complex coordinate s i ⁇ O with a value R ii s i that is closest to a complex value b i
- the coordinate s i is selected by step i) prior to the traversal, determining, for at least some of the pairs of neighboring members s k,j , s k,j+1 of each set C k , a first boundary B k,j given by a line of all numbers of equal distance from R ii s k,j , R ii s k,j+1 , and
- step ii) during said traversal selecting the coordinate s i by comparing, for at least one of said sets C k , said value b i to said first boundaries B k,j , thereby determining the member of set C k whose value R ii s k,j is closest to the value b i .
- Steps i) and ii) are in contrast to [11].
- step i) can be calculated prior to the traversal, which makes the traversal faster.
- This scheme is suited to avoid the evaluation of hyperbolic functions and quadratic equations by storing, for each first boundary B k,j the ratio between the real and imaginary parts of the numbers lying on the boundary.
- This stored (precomputed) ratio can later be accessed and easily compared to the corresponding ratio of b i during the traversals.
- the comparison may advantageously be performed by expanding the corresponding inequality with the denominators of both sides so that checking can be performed without divisions.
- FIG. 1 is an overview over a device for recursive tree traversal
- FIG. 5 is a summary of technical data of the sphere decoder ASIC
- FIG. 6 is a diagram of a transmission system using a device according to the present invention.
- FIG. 7 is block diagram of a first embodiment of a decoder
- FIG. 8 shows the calculation unit of the first embodiment of the decoder
- FIG. 9 illustrates the finite state machine of the calculation unit
- FIG. 10 is a block diagram of a SD ASIC with direct QAM enumeration according to a second embodiment of a decoder
- FIG. 11 illustrates the direct PSK enumeration scheme
- the main idea is to reduce the number of points that need to be considered in the search for the ML solution.
- the list of candidates is constrained to only those points Hs that lie inside a sphere with a given radius C around the received point y: d ( s ) ⁇ C 2 with d ( s ) ⁇ ⁇ Hs ⁇ y ⁇ 2 . (9)
- the operator ⁇ ⁇ denotes the used norm ( ⁇ ⁇ 2 in the example of Eq. 11).
- any constellation point s i that lies between two admissible points is also admissible.
- the admissible set is actually an interval. Checking whether s i is in the admissible set therefore only amounts to comparing s i to the boundaries of that interval.
- radius updating Without radius updating, the order in which nodes are visited is irrelevant for the pruning of the tree. However, radius updating leads to the greatest complexity reduction if symbols with smaller distance are visited first. Also, in order to find admissible symbols as fast as possible depth-first traversal of the tree is mandatory. With the Schnorr-Euchner (SE) enumeration [10], on each level nodes with the smallest PD are followed first, leading to a more rapid shrinkage of the sphere radius. Hence the tree is pruned more efficiently. As an additional advantage of the SE enumeration, the initial sphere radius can be set to infinity. In that case, the first admissible point found is always the so called zero-forcing decision-feedback point.
- SE Schnorr-Euchner
- Dedicated VLSI architectures differ from implementations on DSPs through their potential for massively parallel processing and the availability of customized operations and operation sequences that can be executed in a single cycle.
- the potential of an algorithm to exploit these properties is crucial to guarantee an efficient high throughput implementation.
- VLSI architecture of a high-throughput SD application specific integrated circuit should be designed to ensure that the decoder examines the branches (i.e., children) of a new node in each cycle (or step) and that no node in the tree is ever visited twice.
- This paradigm guarantees maximum throughput efficiency. It is achieved by partitioning the decoder into two parallel units:
- FIG. 1 A corresponding device with an MCU and MEU, as well as additional components to be described below, is shown in FIG. 1 .
- the multiplexer MUX either feeds the selected child node back to the MCU or a node that has been selected by the MEU among those that have not been visited yet.
- the branches that are examined by the MCU on the way down are marked.
- the MEU follows along the same nodes with one cycle delay and computes the PD of the branch that would follow next in the SE enumeration.
- the MCU has found the first complete candidate symbol.
- the MEU has determined that only the branch to node B still meets the updated SC and has already computed its PD. Therefore, the MCU can proceed immediately to check the branch leading to node C in cycle 4 and finally to the leaf E.
- the MCU and MEU carry out separate steps: (step a) the MCU determines the starting child node in level i from the parent node in level i+1 while (step b) the MEU determines the next node in level i+1 other than the parent node, which next node is to be used in case that a next traversal has to start at level i+1.
- the MCU and MEU can advantageously run the steps a) and b) concurrently, e.g. in the same clock cycle.
- step a) the MCU advantageously determines the partial distance T i for the next child node from the partial distance T i+1 , e.g. using Eqs. 16 and 17, or 18, 21b or 21c below.
- step b) the MEU advantageously determines T i+1 of the next parent node in level i+1 of the tree.
- the MEU works on selecting a next node in level i+1 (step b) while the MCU works on selecting a next node in level i (step a).
- the MEU works on selecting a next node in level i+1 (step b) while the MCU works on selecting a next node in level i (step a).
- there can be a larger lag between the MEU and the MCU i.e. the MCU can work in any level j>i in step b while the MCU works on level i in step a.
- a lag of a single level is advantageous because it allows the device to return to any of the pre-ceding levels without time loss.
- Circuit Complexity The circuit complexity is measured by the area required for the integration of all processing elements and the memory. Just as the delay it varies significantly depending on the type of operation and on the associated word-width.
- [ ⁇ ⁇ y ⁇ ⁇ ⁇ y ⁇ ] [ ⁇ ⁇ H ⁇ - ⁇ ⁇ H ⁇ ⁇ ⁇ H ⁇ ⁇ H ⁇ ] ⁇ [ ⁇ ⁇ s _ ⁇ ⁇ ⁇ s _ ⁇ ] + [ ⁇ ⁇ n ⁇ ⁇ ⁇ n ⁇ ] ( 13 )
- the result is a real lattice L 2M of dimension 2M with ⁇ square root over (Q) ⁇ constellation points per dimension.
- the decoder can now explicitly compute the center point of an admissible interval, from which it proceeds with the enumeration in a zig-zag fashion [10] until a constellation point is outside the admissible interval. This condition can be checked based on explicit computation of the boundaries or by simply checking the SC [3].
- Exhaustive Search To directly determine the admissible set, an exhaustive search over the full constellation O can be performed. Explicit sorting of the PDs is subsequently used to realize the SE enumeration. As opposed to the first solution, this method allows for arbitrary complex constellations and does not increase the depth of the search tree. At first sight, the full search appears to have a very high implementation complexity as the PDs need to be computed for all candidate constellations.
- Hybrid Schemes Depending on the constellation, hybrid approaches between exhaustive search and ordered enumeration may also be possible, as proposed in [11]: Starting from PSK modulation, admissible intervals are defined based on the phase of the constellation points. Subsequently, QAM modulation is described as the union of PSK subsets, within which enumeration is straightforward. SE ordering across subsets is achieved through explicit sorting of the PDs.
- the computation of the PD on each level can be decomposed into the computation of an error term e i (s) and the recursive update of the PD:
- the l ⁇ -norm approximation represents a very attractive approach as it leads to greatly reduced search complexity as well as reduced chip area (in the case of a VLSI implementation) at only a minor BER penalty.
- each tree traversal will then have the aim to find a vector s that fulfils the condition of Eq. 21c.
- Each traversal comprises the recursive calculation of T i from T i+1 (according to the used norm, e.g. by applying Eqs. 21a or 21b) along the path.
- the values of b i+1 are stored in the MEU, in a cache sufficiently large to hold the value of b i+1 for each traversed node on the current path.
- a SD ASIC for a 4 ⁇ 4 system with 16-QAM modulation has been realized in a 0.25 ⁇ m technology. It is based on a direct implementation of complex SE enumeration using a decomposition into three nested PSK constellations.
- the square root sphere algorithm is used in conjunction with the l ⁇ -norm.
- the critical path starts with the computation of b i+1 (s), followed by the part of the MCU that finds the starting point for the PSK enumeration, and the metric computation. It then continues with the selection of the minimum and into the MEU, adding up to a total delay of 13.5 ns, allowing for a clock of 75 MHz.
- the active core area of the chip covers only 1 mm2.
- FIG. 6 shows an overview of one possible embodiment of a trans-mission system using the present invention.
- the transmitter splits an incoming highrate data stream into parallel lower-rate streams.
- the data streams may undergo further encoding and are then sent over the transmission medium.
- the data streams are received by receivers and fed to the MIMO detector.
- the data steams from the MIMO detector will then be serialized to form a high-rate data stream.
- the following sections describe two possible embodiments of the MIMO detector.
- FIG. 7 is an overall block diagram of a first embodiment of a sphere decoder. It consists of several parts which will be explained in detail in this chapter. The major blocks in FIG. 7 are:
- Input Handling reads the inputs, stores them until they are needed and provides the right values to the Calculation Unit
- Precalculation Unit this unit does the calculation of the Euclidean distance, searches the nearest constellation point and provides it to the Calculation Unit.
- Calculation Unit controls the algorithm (FSM), provides the Sphere ALU and the Search Unit with the accurate data and has a temporary register storage for the intermediate results
- Search Unit searches the next best constellation point
- Output Handling provides the result in a manner that they can be read from outside the chip
- the Sphere ALU can e.g. calculate expressions of the type of (14) or (21a, b). It can also compute the comparison of (21c). A further speed up in the ALU can be achieved by subtracting the new values from the actual radius instead of adding and comparing them.
- the fundamental task of the Calculation Unit is to feed the ALU with the right inputs at the right time and keep an account of all paths already passed and all paths going to be passed (tree search!). It also controls the algorithm flow. This is why the FSM of this entity plays an important role. While the actual layer is being evaluated, the search unit is fed with the old output values of the ALU, thus calculating the next path for the layer above. If the bottom layer is reached, an extra clock cycle is invested in this embodiment to find the largest ALU output. An overview of the Calculator can be found in the block diagram of FIG. 8 .
- register block where all partial sums of the nodes deviating from and including the present path (here: four layers) are stored. Because all sixteen constellation points in the same branch are calculated at the same time and only one of them is needed immediately, it is necessary to store the intermediate sums for a later use. There are 4 ⁇ 16 registers needed, each one having a width of 14 bit. Then there is one regisister block for the current path(ActPath), another one for the path going to be passed if the actual path is exhausted (NextPath), and a third one for the MIMO-symbol found as solution so far (BestPath). Other required registers are:
- the BestPath is set to the DownPath (in this particular implementation approximated by the ZF solution) and ActSumoldxD for the ALU is the initial sphere radius.
- the algorithm then proceeds to the intermediate layers (layers 3 down to 1 in case of 4 transmit antennas), where it goes down as long as PathOKxS is ‘1’. Meanwhile the RegBlock, NextPath, ActPath, Sumold and CheckedLayer registers are updated continually.
- PathOKxS is ‘0’
- the CheckedLayer register is consulted to find the next upper or parallel layer which hasn't been checked fully.
- the corresponding NextPath is written into the ActPath and the corresponding intermediate sum (also stored together with NextPath) gets the Sumold.
- the second, particularity advantageous embodiment of a device for decoding a received signal in a multiple input/multiple output system also uses the general design of FIG. 1 with a more explicit (i.e., more obvious) separation of MEU and MCU, which carry out a depth-first tree traversal. It uses a decoding scheme as illustrated by FIG. 2 . A more detailed block diagram of the circuit is shown in FIG. 10 .
- s i ( 0 ) argmin s i ⁇ O ⁇ ⁇ arc ⁇ ( b i + 1 ) - arc ⁇ ( s i ) ⁇ , ( 26 ) where arc( . . . ) denotes the phase of a complex number.
- the starting point s i (0) can be computed based on the phases of b i+1 and s i only.
- SE enumeration for PSK modulation now amounts to proceeding from s i (0) in a zig-zag fashion along the unit circle. The procedure is illustrated in FIG. 11 for 16-PSK modulation.
- the direction of the initial step can be found considering the phase of b i+1 and the two neighbors of s i (0).
- the members of a subset lie on a common circle around the origin of the complex plane.
- the following direct QAM enumeration procedure can be used to construct a list of constellation points in SE ordering.
- the PD T i of the preferred child in each subset is calculated in parallel for the different subsets, by PSQ ALU 1 . . . ALU P Q of the MCU, which use the commonly calculated value of b i , which can also be calculated by the MCU.
- the comparison of the PDs of the preferred children and the selection of the next child node having the smallest partial distance T i is carried out by the MIN-SEARCH unit of the MCU.
- the PDs calculated by the MCU are fed to the MEU for storage.
- the MEU stores the two PDs of the preferred nodes that were not selected by the MCU.
- the next candidate is selected by the MEU according to the direct PSK enumeration, and its PD is computed by the PSK ALU of the MEU.
- the operations of the MEU and MCU are carried out concurrently. While the MCU determines a next child node in level i, the MEU determines, in level i+1, a next node other than the selected child node to be used in the set C k of the selected child node.
- the MEU contains a b i+1 cache that stores the values b i+1 for the most recently traversed node on all tree levels.
- the PD of the next candidate is stored in the PED cache of the MEU.
- the PED cache holds P Q candidates for nodes.
- a preferred one of these nodes is calculated by the MIN-SEARCH unit of the MEU and stored in a cache (Preferred children cache), that holds a preferred node for each traversed level.
- a Depth-First unit of the MEU selects the bottom most node in the Preferred children cache and forwards it to the multiplexer MUX for feeding to the MCU.
- PSK Enumeration Recalling that the task of the MCU is to find the starting point of the enumeration, we can conclude that the MCU implements steps 1) and 2) of the first pass in the above described enumeration procedure.
- the MCU employs P Q PSK ALUs. Each of them solves (26) for one PSK subset C k to find the closest constellation point and the initial enumeration direction, which can both be identified through the introduction of suitable decision boundaries instead of using trigonometric functions.
- There is a first type of decision boundaries B k,j and a second type of decision boundaries Q k,j both of which can be determined prior to the traversal of the tree.
- An example of these boundaries for 16-QAM modulation is shown in FIG. 12 .
- Each first boundary B k,j shown as fat lines in FIG. 12 , is attributed to one member s k,j of set C k and is defined by the line of all complex numbers of equal distance from R ii s k,j and R ii s k,j+1 , where s k,j+1 is the nearest neighbor (e.g. in counter-clockwise direction) of s k,j ,
- Each second boundary Q k,j is also attributed to one member s k,j of set C k and is given by the line of all complex numbers of equal distance from the two nearest neighbors R ii s k,j ⁇ 1 and R ii s k,j+1 .
- first and second boundaries can be recorded as the ratio between the real and imaginary-y parts of the numbers lying thereon. They can either be recorded by storage in suitable registers, or, in a VLSI implementation, they can be recorded by hardwiring them into the calculation units of the device. These ratios can, during the traversal, be used for comparison with the ratio of the real and imaginary parts of b i+1 . Even though the term ratio is used in this context, no division is required for storing the same. For example, the ratio for first boundary B 1,1 in the example of FIG.
- the boundaries can be specified in terms of relations between the real and imaginary parts of b i+1 , which can be checked efficiently with very little hardware effort.
- the first decision boundaries B k,j are used for finding the closest point of set C k : If b i+1 lies in the area between B k,j ⁇ 1 and B k,j , the closest point is s k,j .
- the second decision boundaries Q k,j determine the initial direction of the direct PSK enumeration in set C k . If ski was determined to be the closest point to b i+1 and b i+1 lies between Q k,j ⁇ 1 and Q k,j the second closest point is s k,j ⁇ 1 . If, however, s k,j was determined to be the closest point to b i+1 but b i+1 lies between Q k,j and Q k,j+1 , the second closest point is s k,j+1 .
- An advantageous implementation also exploits the symmetry of the constellation to reduce the problem to the first quadrant, thus requiring the examination of the absolute values of the real and imaginary parts of b i+1 only. This adjustment infers extra cost resulting from the need to map the solution in the first quadrant back into the actual quadrant. However, this extra cost is more than compensated for by the reduced number of decision boundaries.
- the triangular matrix R is calculated from the channel matrix H such that all diagonal elements R ii are real valued, which avoids a rotation of the complex plane upon multiplication with R ii and obviates the need to update the boundaries when the values of R ii change.
- the starting point of the enumeration is finally found as the minimum across the preferred children of the different PSK subsets.
- the number of candidates to be compared in the MIN-SEARCH is significantly reduced. Fortunately, this also reduces the delay of the MIN-SEARCH and its contribution to the critical path so that, unlike in ASIC-I, there is no need to deviate from strict SE ordering.
- the MEU executes step 3) in the QAM enumeration procedure described above. For every subset, it keeps track of the preferred children of each node between the current node and the root of the tree. As opposed to the exhaustive search decoder, this only requires a PD cache with P Q entries per tree level, as opposed to 2 Q entries. However, every time a child has been visited by a forward or backward iteration, the corresponding entry in the cache needs to be updated. Consequently, the MEU contains an additional PSK ALU, which is, however, much simpler than the PSK ALUs in the MCU, as no decision boundaries need to be checked. The next constellation point is simply obtained by direct PSK enumeration [cf. FIG. 11 ]. Most of the complexity in evaluating (27) is in computing b i+1 . However, as this term has already been computed in the MCU, it is kept in a small cache in the MEU.
- a MIN-SEARCH constantly determines the preferred child across subsets and places it into the preferred children cache, from which the next node is chosen by the depth-first multiplexer in the case of a leaf or a dead end.
- the implementation described in this section requires the parallel computation of a much smaller number of PDs (compared to the first embodiment) and hence benefits significantly from the l ⁇ -norm approximation, as resource sharing in the squared-norm case is less efficient.
- the length of the overall critical path is reduced by roughly 25% compared to the same architecture, based on the squared l 2 -norm.
- a significant reduction in the average number of visited nodes obtained through the use of the l ⁇ -norm contributes significantly to the high throughput of the chip.
- the corresponding performance loss (due to the use of a suboptimal “norm”) is a 1.4 dB SNR degradation.
- the complexity of the MCU and the memory (cache) requirements in the MEU scale only with P Q . Since P Q ⁇ 2 Q for higher order modulation, the architecture is particularly well suited for large constellations.
- the vectors y and s were assumed to be complex in most cases. They can also be real-valued. Similarly, the matrix H (and the matrices Q and R) are generally assumed to be complex but they can also be real valued.
- the invention can be used in a radio communication system having M transmit antennas and N receive antennas, employing for example spatial multiplexing.
- M transmit antennas and N receive antennas employing for example spatial multiplexing.
- N receive antennas employing for example spatial multiplexing.
- it is applicable to any type of communication channel the characteristics of which can be expressed by (1).
- Other particular examples are other space-time codes or multi-user detection in CDMA.
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Power Engineering (AREA)
- Error Detection And Correction (AREA)
- Digital Transmission Methods That Use Modulated Carrier Waves (AREA)
Abstract
Description
y=Hs+n, (1)
wherein
- y is an N×1 vector describing a received signal,
- H is a channel matrix, wherein H=QR with an M×M upper triangular matrix R and an N×M unitary matrix Q,
- s a transmitted M×1 signal vector whose coordinate values are chosen from a constellation O containing A possible coordinate values,
- n is a N×1 vector of proper independently, identically distributed zero-mean complex Gaussian noise entries,
- M is a number of transmitter sources, and
- N is a number of receiver sinks.
with ∥ ∥2 denoting the Euclidean l2-norm and with ŷ=QHy, and with QH being the conjugate transpose of Q. Other mathematically equivalent methods may be used as well to arrive at an expression similar to (2).
since it is easily implemented in an electronic circuit. Corresponding definitions of the norm are defined for complex-valued xi.
which is, again, fairly easy to implement.
∥Rs−ŷ∥<Ĉ (6)
with ∥ ∥ denoting a norm (any norm, including the l2-norm), Ĉ a positive number and ŷ=(ŷ1, . . . , ŷM)=QHy, and with QH being the conjugate transpose of Q. Each tree traversal comprises the recursive calculation of a partial distance Ti from a partial distance Ti+1 along a path through the tree, wherein the partial distances Ti are defined by
T i =∥e (i)∥ (7)
again with ŷ=(ŷ1, . . . , ŷM)=QHy
-
- the operator ∥ ∥ denotes, unless stated differently, a norm attributing a scalar length to a vector. This may be a norm or semi-norm in the strict mathematical sense or an approximation of a norm or semi-norm in the strict mathematical sense.
- Similarly, the operator | | applied to a complex number defines any norm (or an approximation thereof) of a complex number. In particular, one of the following definitions may be used
- |a+ib|=√{square root over (a2+b2)},
- |a+ib|=max(|a|,|b|), or
- |a+ib|=|a|+|b|
- with a and b being the real and imaginary parts of a complex number.
-
- ε{•} stands for the expectation operator.
- ˜ is the binary “not” operator.
Tree traversal: As known to a person skilled in the art, the type of coding schemes described herein can be expressed in terms of traversals through a tree. Such a tree has leaves representing the possible symbols s and nodes arranged in levels i=1 . . . M, each node representing one possible selection of coordinates si . . . sM from the set of possible coordinates. A traversal is a path descending from node to node through some or all the levels i.
d(s)≦C 2 with d(s)Δ∥Hs−y∥ 2. (9)
{circumflex over (d)}(s)≦Ĉ 2 with {circumflex over (d)}(s)Δ∥Rs−ŷ∥ 2 (9)
where the M-dimensional ŷ=(ŷ1, . . . ŷM)=QHy, and where in the case N>M the radius C needs to be adjusted to yield the modified radius C. As a result of the triangular structure of R, the distance {circumflex over (d)}(s) can now be computed, in the l2-norm, recursively as follows:
T i =∥e (i)∥ (11a)
with vector e(i)=(0, . . . , ei, . . . eM) being the “tail end” of a vector e defined by e=(e1, . . . eM)=Rs−ŷ. The operator ∥ ∥ denotes the used norm (∥ ∥2 in the example of Eq. 11).
but membership in the admissible set cannot simply be determined using the bounds of an admissible interval. We shall explore solutions to this problem in
-
- 1. The metric computation unit (MCU, called “first computing means” in the claims) starts from Ti+1(s) (i.e., the metric of the current node, the “parent node” in level i+1 of the tree) and finds the starting point (“child node” in level i of the tree) for the SE enumeration along with the PD Ti(s) of the corresponding branch. When the bottom of the tree is reached, the MCU stores the symbol corresponding to the current path and updates the radius. In this case, or if the admissible set is empty, a new node branching off the current path further up in the tree is visited next. If no more valid branches (i.e., children) are found, the decoder stops.
- 2. The metric enumeration unit (MEU, called “second computing means” in the claims) operates solely on nodes that have already been visited by the MCU. It carries out the SE enumeration to find the branch with the smallest PD among those that have not been visited yet. It keeps a list of these admissible children for all nodes on the current path. When the MCU reaches a leaf or a dead end, the MEU can decide immediately where (i.e., at which level and which node) the search shouid be continued in the next cycle. Tree traversal is performed depth-first. The MEU advantageously stores at least one PD Ti+1 for each traversed level.
-
- 1. the average number of visited nodes ε{K} before the ML solution is found, which determines the number of cycles per symbol
- 2. the cycle time tCLK, which is given by the critical path through the longest chain of consecutive operations in one cycle.
The first criterion characterizes the efficiency of the tree pruning and can be considered purely on an algorithmic level. The second criterion is concerned with the efficiency of the hardware implementation. The overall throughput is given by Φ=M·log2|O|/(ε{K}tCLK). Note that, as opposed to optimizations that target DSPs, the pure number of operations (FLOPs) is of little significance.
T i(s)=T i+1(s)+|b i(s)|2−2 {b i*(s)R ii s i }+|R ii|2 s i *s i (14)
with
T i(s)←T i+1(s)+|e i(s)|2. (17)
{tilde over (T)} i(s)←√{square root over ({tilde over (T)} i+1(s)2 +|e i(s)2)}. (18)
l1-norm | |x| + |y| | ||
l∞-norm | max(|x|, |y|) | ||
|
⅜(|x| + |y|) + ⅝ max(|x|, |y|) | ||
|
max(max(|x|, |y|), ⅞ max(|x|, |y|) + ½ min(|x|, |y|)) | ||
∥Rs−ŷ∥ ∞ ≦∥Rs−y∥ 2 ∥Rs−y∥ 1 (21)
the accumulated distance at the bottom of the tree is smallest for the l∞-norm. After the radius update, it is therefore more probable that the PD for a certain node further up in the tree is larger than the new radius, as compared to the l2-norm case. Therefore, more branches in the tree will be pruned. The situation is just the opposite for the l1-norm, therefore tree pruning becomes less effective. The impact on complexity is clearly visible in
by
∥Rs−ŷ∥<Ĉ (21c)
∥ ∥ with denoting the norm to be applied. Each tree traversal will then have the aim to find a vector s that fulfils the condition of Eq. 21c. Each traversal comprises the recursive calculation of Ti from Ti+1 (according to the used norm, e.g. by applying Eqs. 21a or 21b) along the path.
which can be computed by evaluating
e i =b i+1 −R ii s i, (21e)
with bi as defined in Eq. 15. Since the value of bi+1 does not depend on the child node, it can be used for the calculation of the PD of several child nodes of the same parent node. It can e.g. be stored for subsequent calculations of the value of ei, e.g. in cases where a search algorithm requires the time delayed computation of the PD of several child nodes of the same parent node. Advantageously, the values of bi+1 are stored in the MEU, in a cache sufficiently large to hold the value of bi+1 for each traversed node on the current path.
-
- ActRadius: Stores the actual sphere radius
- Sumold: Stores the intermediate sum of the path where the algorithm will go down next. This sum is then fed back into the ALU (ActSumoldxD), if the actual layer is not the top layer.
- ActLayer: Stores the actual layer
- CheckedLayer: Stores for each layer, if there is still a constellation point within the sphere or not.
where arc( . . . ) denotes the phase of a complex number. Hence, the starting point si(0) can be computed based on the phases of bi+1 and si only. SE enumeration for PSK modulation now amounts to proceeding from si(0) in a zig-zag fashion along the unit circle. The procedure is illustrated in
-
- Step 1) Within each subset, the preferred child (i.e. a potential next child node) is determined based on a minimization of |arc(bi+1)−arc(si)|, and subsequently the corresponding PD is computed for each potential next child node.
- Step 2) The PDs of the preferred children are compared, and the point with the smallest PD across the subsets is chosen by the MIN-SEARCH unit of the MCU.
- Step 3) Before the next point in the SE ordering can be obtained in the MEU, the constellation point selected in step 2) is replaced by the next candidate in the corresponding subset Ck according to the direct PSK enumeration, and the corresponding PD is computed. The algorithm proceeds with step 2) until all subsets are empty.
|e i(s (i))|2 =|b i+1(s (i+1))−R ii s i|2 (27)
needs to be evaluated for only PQ<<2Q candidate symbols; therefore, it is not worthwhile to pursue resource sharing.
T i(s (i))=T i+1(s (i+1))+|e i(s (i))|2. (28)
- [1] M. Pohst, “On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications,” ACM SIG-SAM, pp. 37-44, 1981
- [2] E. Viterbo and J. Boutros, “A universal lattice code decoder for fading channels,” IEEE Trans. Info. Theory, vol. 45, pp. 1639-1642, July 1999.
- [3] M. O. Damen, H. El Gamal, G. Caire, “On Maximum-Likelihood Detection and the Search for the Closest Lattice Point” IEEE Trans. Info. Theory, vol. 49, no. 10, pp. 2389-2402
- [4] M. O. Damen, A. Chkeif, and J.-C. Belfiore, “Lattice code decoder for space-time codes”, IEEE Comm. Let., pp. 161-163, May 2000
- [5] Albert M. Chan, Inkyu Lee, “A New Reduced-Complexity Sphere Decoder For Multiple Antenna Systems”, Proceedings of IEEE International Communication Conference, ICC, April 2002
- [6] B. Hassibi and H. Vikalo, “On the expected complexity of sphere decoding”, Proc. Asilomar Conf. on Signals, Systems and Computers, 1051-1055, Pacific Grove, Calif., 2001
- [7] B. Hassibi and H. Vikalo: “On the expected complexity of sphere decoding”, Proc. IEEE-ICASSP 2002, Vol. 2, pp. 1497-1500
- [8] U. Fincke and M. Pohst. Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Mathematics of Computation, 463-471, April 1985
- [9] G. J. Foschini, “Layered space-time architecture for wireless communication in a fading environment when using multi-element antennas,” Bell Labs. Tech. Journal, vol. 1, no. 2, pp. 41-59, 1996.
- [10] C. P. Schnorr and M. Euchner: “Lattice basis reduction: Improved practical algorithms and solving subset sum problems”, Math. Programming, 1994, Vol. 66, pp. 181-191
- [11] B. M. Hochwald, S. ten Brink: “Achieving Near-Capacity on a Multiple-Antenna-Channel,” IEEE Trans. Inform. Theory, vol. 51, no. 3, pp. 389-399, March 2003
Claims (28)
y=Hs+n,
∥Rs−ŷ∥<Ĉ
∥Rs−ŷ∥<Ĉ
y=Hs+n,
∥Rs−ŷ∥<Ĉ
T i =∥e (i)∥
y=Hs+n,
y=Hs+n,
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
US11/662,854 US7782971B2 (en) | 2004-09-16 | 2005-09-14 | Method and device for decoding a signal of multiple input/multiple output system |
Applications Claiming Priority (3)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
US61058404P | 2004-09-16 | 2004-09-16 | |
PCT/CH2005/000544 WO2006029546A2 (en) | 2004-09-16 | 2005-09-14 | Method and device for decoding a signal of a multiple input/multiple output system |
US11/662,854 US7782971B2 (en) | 2004-09-16 | 2005-09-14 | Method and device for decoding a signal of multiple input/multiple output system |
Publications (2)
Publication Number | Publication Date |
---|---|
US20090063106A1 US20090063106A1 (en) | 2009-03-05 |
US7782971B2 true US7782971B2 (en) | 2010-08-24 |
Family
ID=35198021
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
US11/662,854 Expired - Fee Related US7782971B2 (en) | 2004-09-16 | 2005-09-14 | Method and device for decoding a signal of multiple input/multiple output system |
Country Status (5)
Country | Link |
---|---|
US (1) | US7782971B2 (en) |
EP (1) | EP1790138B1 (en) |
AT (1) | ATE443961T1 (en) |
DE (1) | DE602005016819D1 (en) |
WO (1) | WO2006029546A2 (en) |
Cited By (10)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US20090154579A1 (en) * | 2007-12-15 | 2009-06-18 | Electronics And Telecommunications Research Institute | Qr decomposition apparatus and method for mimo system |
US8019023B2 (en) | 2006-08-18 | 2011-09-13 | Marvell World Trade Ltd. | Low-complexity scalable architecture for concatenation-assisted symbol-level combining |
US8411778B1 (en) | 2006-08-08 | 2013-04-02 | Marvell World Trade Ltd. | Optimal linear equalizer for MIMO systems with HARQ and/or repetition coding |
US8498195B1 (en) | 2007-03-30 | 2013-07-30 | Marvell International Ltd. | HARQ retransmission scheme for at least two transmit antennas |
US8559543B1 (en) * | 2009-10-09 | 2013-10-15 | Marvell International Ltd. | Soft sphere decoder for MIMO maximum likelihood demodulation |
US8619910B1 (en) | 2007-04-11 | 2013-12-31 | Marvell International Ltd. | Decision feedback equalization for MIMO systems with hybrid ARQ |
US8699601B1 (en) | 2006-08-08 | 2014-04-15 | Marvell World Trade Ltd. | Distance-level combining for MIMO systems with HARQ and/or repetition coding |
US8718166B2 (en) | 2006-08-08 | 2014-05-06 | Marvell World Trade Ltd. | Maximal ratio combining of equalized symbols for MIMO systems with HARQ and/or repetition coding |
US8929472B1 (en) | 2006-07-26 | 2015-01-06 | Marvell International Ltd. | Bit-level combining for MIMO systems with HARQ and/or repetition coding |
US20160233930A1 (en) * | 2013-10-17 | 2016-08-11 | Georgia Tech Research Corporation | An Improved Lattice-Reduction-Aided K-Best Algorithm for Low Complexity and High Performance Communications |
Families Citing this family (17)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
GB2440382B (en) * | 2006-07-21 | 2008-07-09 | Toshiba Res Europ Ltd | Decoder for wireless communication system |
US8121209B2 (en) | 2006-07-25 | 2012-02-21 | Marvell World Trade Ltd. | Concatenation-assisted symbol-level combining for MIMO systems with HARQ and/or repetition coding |
US8090063B2 (en) * | 2006-07-26 | 2012-01-03 | Marvell World Trade Ltd. | Symbol-level combining for multiple input multiple output (MIMO) systems with hybrid automatic repeat request (HARQ) and/or repetition coding |
US8027402B2 (en) * | 2006-07-26 | 2011-09-27 | Marvell World Trade Ltd. | Symbol-level combining for multiple input multiple output (MIMO) systems with hybrid automatic repeat request (HARQ) and/or repetition coding |
WO2008033423A2 (en) * | 2006-09-13 | 2008-03-20 | Marvell Semiconductor, Inc. | Decoding method for alamouti scheme with harq and/or repetition coding |
DE602007011492D1 (en) | 2006-11-24 | 2011-02-03 | Nxp Bv | METHOD AND ARRANGEMENT FOR PRODUCING A SOFTBITS SYSTEM |
KR100932272B1 (en) | 2007-12-13 | 2009-12-16 | 한국전자통신연구원 | Transmission Interference Rejection Method for Multi-User Look |
US9002899B2 (en) * | 2008-07-07 | 2015-04-07 | International Business Machines Corporation | Method of merging and incremental construction of minimal finite state machines |
WO2010015989A2 (en) * | 2008-08-05 | 2010-02-11 | Nxp B.V. | Method and arrangement for generating soft bit information in a receiver of a multiple antenna system |
DE102009014844B4 (en) * | 2009-03-30 | 2016-01-07 | Technische Universität Dresden | Method for determining the search order of nodes in a tree search algorithm, tree search method and detector arrangement for carrying out the methods |
US8311161B2 (en) * | 2009-06-19 | 2012-11-13 | Xilinx, Inc. | Sphere detector performing depth-first search until terminated |
EP2341676A1 (en) * | 2009-12-30 | 2011-07-06 | ST-Ericsson SA | Branch processing of search tree in a sphere decoder |
US8279977B2 (en) * | 2010-12-14 | 2012-10-02 | VeriSilicon | MIMO signal detector, a method of detecting MIMO signals and a MIMO receiver |
ES2433695B1 (en) * | 2012-03-14 | 2015-04-13 | Universidad Politécnica De Valencia | METHOD OF SPHERICAL DECODIFICATION OF SIGNS OF COMMUNICATION SYSTEMS OF MULTIPLE INPUTS AND MULTIPLE OUTPUTS (MIMO) OF MAXIMUM VEROSIMILITY. |
US9362990B1 (en) * | 2015-06-16 | 2016-06-07 | Mbit Wireless, Inc. | Method and apparatus for precomputation based MIMO decoder |
CN108964734A (en) * | 2018-06-29 | 2018-12-07 | 电子科技大学 | A kind of antenna selecting method for nonlinear precoding |
CN115668854A (en) * | 2020-05-14 | 2023-01-31 | 哲库科技有限公司 | Multiple input multiple output detection device and method based on recursive tree search |
Citations (5)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US3922540A (en) | 1974-10-29 | 1975-11-25 | Rca Corp | Approximator for square root of sums of squares |
US20040181419A1 (en) | 2003-03-15 | 2004-09-16 | Davis Linda Mary | Spherical decoder for wireless communications |
US20080267138A1 (en) * | 2002-10-25 | 2008-10-30 | Qualcomm Incorporated | Mimo system with multiple spatial multiplexing modes |
US20080285670A1 (en) * | 2002-10-25 | 2008-11-20 | Qualcomm Incorporated | Mimo wlan system |
US20090190683A1 (en) * | 2004-04-22 | 2009-07-30 | Qualcomm Incorporated | Mimo receiver using maximum likelihood detector in combination with qr decomposition |
-
2005
- 2005-09-14 AT AT05777622T patent/ATE443961T1/en not_active IP Right Cessation
- 2005-09-14 EP EP05777622A patent/EP1790138B1/en not_active Not-in-force
- 2005-09-14 WO PCT/CH2005/000544 patent/WO2006029546A2/en active Application Filing
- 2005-09-14 DE DE602005016819T patent/DE602005016819D1/en active Active
- 2005-09-14 US US11/662,854 patent/US7782971B2/en not_active Expired - Fee Related
Patent Citations (5)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US3922540A (en) | 1974-10-29 | 1975-11-25 | Rca Corp | Approximator for square root of sums of squares |
US20080267138A1 (en) * | 2002-10-25 | 2008-10-30 | Qualcomm Incorporated | Mimo system with multiple spatial multiplexing modes |
US20080285670A1 (en) * | 2002-10-25 | 2008-11-20 | Qualcomm Incorporated | Mimo wlan system |
US20040181419A1 (en) | 2003-03-15 | 2004-09-16 | Davis Linda Mary | Spherical decoder for wireless communications |
US20090190683A1 (en) * | 2004-04-22 | 2009-07-30 | Qualcomm Incorporated | Mimo receiver using maximum likelihood detector in combination with qr decomposition |
Non-Patent Citations (10)
Title |
---|
A. Burg, M. Wenk, M. Zellweger, M. Wegmueller, N. Felber and W. Fichtner; "VLSI Implementation of the Sphere Decoding Algorithm"; pp. 303-306; © 2004. |
Paolo Gastaldo, Sandro Ridella and Rodolfo Zunino; "Vector Quantization Complexity and Quantum Computing"; pp. 3257-3262; © 2004. |
XP-001163616; Bertrand M. Hochwald and Stephan ten Brink; "Achieving Near-Capacity on a Multiple-Antenna Channel"; pp. 389-399; IEE Transactions on Communications, vol. 51, No. 3, Mar. 2003. |
XP-001224144; David Garrett, Linda Davis, Stephan ten Brink, Bertrand Hochwald and Geoff Knagge; "Silicon Complexity for Maximum Likelihood MIMO Detection Using Spherical Decoding"; pp. 1544-1552; IEEE Journal of Solid-State Circuits, vol. 39, No. 9, Sep. 2004. |
XP-002178307; Emanuele Viterbo and Joseph Boutros; A Universal Lattice Code Decoder for Fading Channels; pp. 1639-1642; IEEE Transactions on Information Theory, vol. 45, No. 5, Jul. 1999. |
XP-002353940; Erik Agrell, Thomas Eriksson, Alexander Vardy and Kenneth Zeger; "Closest Point Search in Lattices"; pp. 2201-2214; IEEE Transactions on Information Theory, vol. 48, No. 8, Aug. 2002. |
XP-002353941; Andreas Burg, Moritz Borgmann, Markus Wenk, Martin Zellweger and Wolfgang Fichtner; "VLSI Implementation of MIMO Detection Using the Sphere Decoding Algorithm"; pp. 1566-1577; IEEE Journal of Solid-State Circuits, vol. 40, No. 7, Jul. 7, 2005. |
XP-002353942; A. Burg, M. Borgmann, C. Simon, M. Wenk, M. Zellweger and W. Fichtner; "Performance Tradeoffs in the VLSI Implementation of the Sphere Decoding Algorithm"; pp. 93-97, 2004. |
XP-002368743; Kwan-wai Wong, Chi-ying Tsui, Roger Shu-kwan Cheng and Wai-ho Mow; A VLSI Architecture of K-Best Lattice Decoding Algorithm for MIMO Channels; pp. 273-276; © 2002 IEEE. |
Zhan Guo, Peter Nilsson; VLSI Implementation Issues of Lattice Decoders for MIMO Systems; pp. 477-480; © 2004 IEEE. |
Cited By (17)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US8929472B1 (en) | 2006-07-26 | 2015-01-06 | Marvell International Ltd. | Bit-level combining for MIMO systems with HARQ and/or repetition coding |
US9240867B1 (en) | 2006-07-26 | 2016-01-19 | Marvell International Ltd. | Bit-level combining for MIMO systems with HARQ and/or repetition coding |
US9020062B2 (en) | 2006-08-08 | 2015-04-28 | Marvell World Trade Ltd. | Maximal ratio combining of equalized symbols for MIMO systems with HARQ and/or repetition coding |
US8787486B2 (en) | 2006-08-08 | 2014-07-22 | Marvell World Trade Ltd. | Distance-level combining for MIMO systems with HARQ and/or repetition coding |
US8411778B1 (en) | 2006-08-08 | 2013-04-02 | Marvell World Trade Ltd. | Optimal linear equalizer for MIMO systems with HARQ and/or repetition coding |
US8699601B1 (en) | 2006-08-08 | 2014-04-15 | Marvell World Trade Ltd. | Distance-level combining for MIMO systems with HARQ and/or repetition coding |
US8718166B2 (en) | 2006-08-08 | 2014-05-06 | Marvell World Trade Ltd. | Maximal ratio combining of equalized symbols for MIMO systems with HARQ and/or repetition coding |
US8718177B2 (en) | 2006-08-08 | 2014-05-06 | Marvell World Trade Ltd. | Optimal linear equalizer for MIMO systems with HARQ and/or repetition coding |
US8019023B2 (en) | 2006-08-18 | 2011-09-13 | Marvell World Trade Ltd. | Low-complexity scalable architecture for concatenation-assisted symbol-level combining |
US8498195B1 (en) | 2007-03-30 | 2013-07-30 | Marvell International Ltd. | HARQ retransmission scheme for at least two transmit antennas |
US8619910B1 (en) | 2007-04-11 | 2013-12-31 | Marvell International Ltd. | Decision feedback equalization for MIMO systems with hybrid ARQ |
US8068560B2 (en) * | 2007-12-15 | 2011-11-29 | Electronics And Telecommunications Research Institute | QR decomposition apparatus and method for MIMO system |
US20090154579A1 (en) * | 2007-12-15 | 2009-06-18 | Electronics And Telecommunications Research Institute | Qr decomposition apparatus and method for mimo system |
US9143210B1 (en) | 2009-10-09 | 2015-09-22 | Marvell International Ltd. | Soft sphere decoder for MIMO maximum likelihood demodulation |
US8559543B1 (en) * | 2009-10-09 | 2013-10-15 | Marvell International Ltd. | Soft sphere decoder for MIMO maximum likelihood demodulation |
US20160233930A1 (en) * | 2013-10-17 | 2016-08-11 | Georgia Tech Research Corporation | An Improved Lattice-Reduction-Aided K-Best Algorithm for Low Complexity and High Performance Communications |
US9647732B2 (en) * | 2013-10-17 | 2017-05-09 | Georgia Tech Research Corporation | Lattice-reduction-aided K-best algorithm for low complexity and high performance communications |
Also Published As
Publication number | Publication date |
---|---|
US20090063106A1 (en) | 2009-03-05 |
DE602005016819D1 (en) | 2009-11-05 |
EP1790138A2 (en) | 2007-05-30 |
EP1790138B1 (en) | 2009-09-23 |
WO2006029546A2 (en) | 2006-03-23 |
ATE443961T1 (en) | 2009-10-15 |
WO2006029546A3 (en) | 2006-05-11 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
US7782971B2 (en) | Method and device for decoding a signal of multiple input/multiple output system | |
Zhao et al. | Sphere decoding algorithms with improved radius search | |
KR101124863B1 (en) | Apparatus and method for processing communications from multiple sources | |
US7986752B2 (en) | Parallel soft spherical MIMO receiver and decoding method | |
Mansour et al. | Reduced complexity soft-output MIMO sphere detectors—Part I: Algorithmic optimizations | |
Azzam et al. | Reduced complexity sphere decoding for square QAM via a new lattice representation | |
Trotobas et al. | Detection Algorithms: Theory and Implementation | |
CN107094063B (en) | Semi-exhaustive iterative block decoding method and device | |
US8391378B2 (en) | Metric computation for lowering complexity of MIMO detection algorithms | |
Nguyen et al. | QR-decomposition-aided tabu search detection for large MIMO systems | |
US9025689B2 (en) | Method and apparatus for multiple antenna communications, and related systems and computer program | |
Liu et al. | Low-complexity likelihood information generation for spatial-multiplexing MIMO signal detection | |
Cortez et al. | A very low complexity near ML detector based on QRD-M algorithm for STBC-VBLAST architecture | |
Azzam et al. | Reduced complexity sphere decoding via a reordered lattice representation | |
Burg et al. | Performance tradeoffs in the VLSI implementation of the sphere decoding algorithm | |
Guo et al. | VLSI implementation issues of lattice decoders for MIMO systems | |
Yoon et al. | A detection algorithm for multi-input multi-output (MIMO) transmission using poly-diagonalization and trellis decoding | |
Bello et al. | A survey of VLSI implementations of tree search algorithms for MIMO detection | |
Lee et al. | MIMO maximum likelihood soft demodulation based on dimension reduction | |
Shin et al. | A low‐complexity iterative MIMO detection and decoding scheme using dimension reduction | |
Huynh et al. | Two-level-search sphere decoding algorithm for MIMO detection | |
Izadinasab et al. | Near-optimal MIMO detectors based on MMSE-GDFE and conditional detection | |
Cui et al. | Generalized feedback detection for spatial multiplexing multi-antenna systems | |
Cui et al. | Generalized feedback detection for MIMO systems | |
Cortez et al. | A low-complexity near-ML detector for a 3× n R hybrid space-time code |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
AS | Assignment |
Owner name: ETH ZURICH, SWITZERLAND Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:BURG, ANDREAS;BORGMANN, MORITZ;WENK, MARKUS;AND OTHERS;REEL/FRAME:021871/0079;SIGNING DATES FROM 20080825 TO 20080908 Owner name: ETH ZURICH, SWITZERLAND Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:BURG, ANDREAS;BORGMANN, MORITZ;WENK, MARKUS;AND OTHERS;SIGNING DATES FROM 20080825 TO 20080908;REEL/FRAME:021871/0079 |
|
FEPP | Fee payment procedure |
Free format text: PAYER NUMBER DE-ASSIGNED (ORIGINAL EVENT CODE: RMPN); ENTITY STATUS OF PATENT OWNER: SMALL ENTITY Free format text: PAYOR NUMBER ASSIGNED (ORIGINAL EVENT CODE: ASPN); ENTITY STATUS OF PATENT OWNER: SMALL ENTITY |
|
FEPP | Fee payment procedure |
Free format text: PAT HOLDER CLAIMS SMALL ENTITY STATUS, ENTITY STATUS SET TO SMALL (ORIGINAL EVENT CODE: LTOS); ENTITY STATUS OF PATENT OWNER: SMALL ENTITY |
|
FPAY | Fee payment |
Year of fee payment: 4 |
|
FEPP | Fee payment procedure |
Free format text: MAINTENANCE FEE REMINDER MAILED (ORIGINAL EVENT CODE: REM.) |
|
LAPS | Lapse for failure to pay maintenance fees |
Free format text: PATENT EXPIRED FOR FAILURE TO PAY MAINTENANCE FEES (ORIGINAL EVENT CODE: EXP.); ENTITY STATUS OF PATENT OWNER: SMALL ENTITY |
|
STCH | Information on status: patent discontinuation |
Free format text: PATENT EXPIRED DUE TO NONPAYMENT OF MAINTENANCE FEES UNDER 37 CFR 1.362 |
|
FP | Lapsed due to failure to pay maintenance fee |
Effective date: 20180824 |