You are an expert at summarizing long articles. Proceed to summarize the following text: 
the channel capacity of multiple - input - multiple - output ( mimo ) channels linearly increases with the number of antennas @xcite . maximum - likelihood ( ml ) detection provides the minimum error rate . however , the computational complexity of the simple ml detection algorithm grows exponentially with the number of transmit antennas . thus , we need an efficient algorithm that achieves similar error rate to the ml detection . the qr decomposition m - algorithm ( qrd - mld ) @xcite and sphere decoding ( sd ) @xcite are possibly the most promising algorithms . in @xcite , to reduce the computational complexity , dijkstra s algorithm is applied to sd which achieves same error rate as ml detection . both the qrd - mld and dijkstra s algorithm are tree search based algorithms . dijkstra s algorithm uses the list of unlimited size to keep detection candidates . however , the computational complexities of the qrd - mld and dijkstra s algorithm are still high . to reduce the computational complexity , we propose dijkstra s algorithm with bounded list size . when proposed algorithm s list size is set to achieve the almost same symbol error rate ( ser ) as the qrd - mld , the computational complexity of proposed algorithm is lower than the qrd - mld . this paper is organized as follows . in section 2 , we introduce the system model of mimo channels . in section 3 , we review the qrd - mld and its improvement , then propose dijkstra s algorithm with bounded list size . in section 4 , we show the comparison between the computational complexity of the qrd - mlds and proposed algorithm by computer simulations . finally , we give the conclusion in section 5 . we consider the uncoded system with @xmath0 transmit antennas and @xmath1 receive antennas , and we assume @xmath2 . we assume that the noise at each receive antenna is the additive white gaussian noise ( awgn ) . let @xmath3 be a @xmath4 vector consisting of complex envelopes of transmitted signals with the signal constellation @xmath5 , @xmath6 an @xmath7 fading matrix whose @xmath8 entry is a complex fading coefficient between @xmath9-th transmit antenna and @xmath10-th receive antenna , @xmath11 an @xmath12 complex vector whose component is noise at each receive antenna , and @xmath13 an @xmath12 complex vector whose component is the received signal component at each receive antenna . the model of this channel is written as @xmath14 we assume that the receiver knows the channel state information ` h ` perfectly .    in this case , the ml detection of the transmitted signal over the channel ( 1 ) can be formulated as finding @xmath15 in this section , we propose the new near ml detection algorithm . first , to calculate ( 2 ) efficiently , we explain how to find the ml signal by tree search algorithm in section 3.1 . then , we review near ml detection algorithms called qrd - mld @xcite and its improvement @xcite in section 3.2 . finally , we propose dijkstra s algorithm with bounded list size in section 3.3 . to calculate ( 2 ) efficiently , we compute a qr decomposition of @xmath6 and obtain an upper triangular matrix @xmath16 and a unitary matrix @xmath17 with @xmath18 . since @xmath17 is unitary , @xmath19 let @xmath20 . the ml detection problem ( 2 ) can be reformulated as finding @xmath21 @xmath22 the second equality above follows as the second term in the second equation is irrelevant to @xmath3 .    to calculate ( 4 ) efficiently , we consider a weighted directed graph as follows . the decisions on @xmath23 construct a tree where nodes at @xmath10-th depth are correspond to the candidate of @xmath24 @xcite , and the root node is placed at depth 0 . then , the metric value , which is the weight of branch , between a node @xmath25 that has @xmath26 as ancestor nodes from the root node to its parent node is defined by @xmath27 the distance of each node from the root node , which is called the accumulated metric value in this paper , is equal to the sum of the metric values of branches from the root node to the node itself . the accumulated metric value from the root node to the bottom node whose depth is @xmath0 is @xmath28 because @xmath29 that makes ( 5 ) minimum is equal to @xmath30 of ( 4 ) , the shortest path from the root node to the bottom node corresponds to the ml signal @xcite . the qrd - mld @xcite , which is a breadth - first tree search based algorithm , finds a near ml signal . the qrd - mld keeps only @xmath31 nodes at each depth with the smallest accumulated metric values @xcite , instead of testing all the candidate in @xmath32 according to ( 4 ) . at each depth , only @xmath31 nodes make their child nodes . we call a node that makes its child node detection node in this paper . an improvement to qrd - mld proposed in @xcite reduces the number of detection nodes from the original qrd - mld . this improved qrd - mld has threshold value at each depth . the depth @xmath33 s threshold value @xmath34 is defined by @xmath35 where @xmath36 is the smallest accumulated metric value of the node at @xmath33-th depth in the nodes whose parent node is a detection node . @xmath37 is a fixed constant number , and @xmath38 is the noise variance . at each depth , select the nodes that have smaller accumulated metric value than threshold value @xmath34 . if the number of selected nodes is more than @xmath31 , only @xmath31 nodes with smallest accumulated metric values are selected . note that both algorithms do not always find the ml signal . for small to medium @xmath31 values , the complexity is substantially lower than the simple ml detection algorithm . however , the final result is no longer guaranteed to be the ml signal . dijkstra s algorithm is an efficient algorithm to find the shortest path from a point to a destination in a weighted graph @xcite . dijkstra s algorithm uses the list of unlimited size to keep candidate nodes . if we use dijkstra s algorithm to find the shortest path from the root to one of nodes at the bottom depth , we can get the node with minimum @xmath39 among all nodes at the bottom depth and it corresponds to the ml estimate @xcite . however , this algorithm still has high computational complexity . to reduce the computational complxity , we propose a modified version of dijkstra s algorithm whose list keeps only @xmath40 nodes with the smallest accumulated metric values in the list . we show dijkstra s algorithm with bounded list size .    1 . create an empty list for nodes . 2 .   insert all nodes at the first level into the list . 3 .   select the node a having smallest accumulated metric value in the list and remove it from the list . if the depth of a is @xmath0 , then output the node a and its ancestor nodes as the ml signal and finish this algorithm . 4 .   insert all a s child nodes into the list . 5 . arrange the nodes in the list according to the accumulated metric value by the quick sort . if the list has more than @xmath40 nodes , select the @xmath40 nodes with the smallest accumulated metric values in the list , and discard other nodes from the list . go back to step 3 . the node whose child nodes are inserted into the list is called detection node in this paper . because the discarded nodes , which are decided at step 5 , and their descendant nodes are not examined , the proposed algorithm dose not examine all the candidate in @xmath32 according to ( 4 ) . thus , the proposed algorithm dose not always find the ml signal . when we use ldpc codes @xcite or turbo codes @xcite after detection , we have to compute @xmath41 most likely signals @xcite . such signals can be computed by this algorithm s modification that is finished after output @xmath41 signals with the smallest accumulated metric value . ) symbol error rate ]    ) maximum computational complexity ]    ) maximum computational complexity ]    ) maximum number of detection nodes ]    ) maximum number of detection nodes ]    ) maximum number of comparisons of real numbers ]    ) maximum number of comparisons of real numbers ]    ) symbol error rate ]    ) maximum computational complexity ]    ) maximum computational complexity ]    ) maximum number of detection nodes ]    ) maximum number of detection nodes ]    ) maximum number of comparisons of real numbers ]    ) maximum number of comparisons of real numbers ]    in this section , we compare the computational complexity , the number of detection nodes and the number of comparisons of real numbers among the proposed algorithm and the qrd - mlds . throughout the simulations , we consider the following system model .    * we do two simulations . in the first simulation , the number of transmit antennas @xmath42 , and the number of receive antennas @xmath43 . in the second simulation , the number of transmit antennas @xmath44 , and the number of receive antennas @xmath45 . * the signal constellation at each transmit antenna is 16-qam and all signals are drawn according to the uniform i.i.d . distribution . * the fading coefficients obey the @xmath46 distribution , and the receiver knows it perfectly . * the noise at each recieve antenna obeys the @xmath47 distribution . @xmath48 is caluculated by @xmath49 , where @xmath50 is the average symbol energy . * we transmit 100000 signals , which is 400000 symbols if the number of transmit antennas is @xmath51 and 600000 symbols if the number of transmit antennas is @xmath52 , and every 100 signals , change the fading matrix . if @xmath53 is used and the signal constellation is 16-qam , qrd - mld has symbol error rate ( ser ) near to the ml detection @xcite . so , we use @xmath53 . in qrd - mld s improvement , we use @xmath54 in ( 6 ) as used in @xcite . in order for the proposed algorithm to have the similar ser to qrd - mld and its improvement , we use two versions of proposed algorithm whose list sizes are @xmath55 and @xmath56 . figures 1 and 8 show that the proposed algorithm with @xmath55 , the original qrd - mld and the ml algorithm have almost the same ser throughout this simulations . the proposed algorithm with @xmath56 and qrd - mld s improvement also have similar ser throughout this simulations . we count the number of multiplications and divisions of complex numbers as the computational complexity . since the part of qr decomposition is the common part of all compared algorithms , we do not include that part in comparison of complexity .    in qrd - mlds , we use the quick sort to arrange the nodes and decide @xmath31 nodes with the smallest accumulated metric value at each depth .    because the qrd - mld keeps @xmath31 nodes at each depth , the number of detection nodes and the computational complexity are completely determined by @xmath31 . however , in the proposed algorithm and qrd - mld s improvement , the number of detection nodes and the computational complexity are not fixed . figures 17 are the results of first simulation whose number of transmit antennas and receive antennas are 4 . figures 814 are the results of second simulation whose number of transmit antennas and receive antennas are 6 .    at first , we discuss the result of first simulation . according to figures 2 , 4 and 6 , the propose algorithm with @xmath55 reduece the average computational complexity , average number of detection nodes and average number of comparisons of real numbers from the original qrd - mld . moreover , in the case of high snr , although the proposed algorithm with @xmath55 has much smaller ser than qrd - mld s improvement according to figure 1 , the average computational complexity of proposed algorithm with @xmath55 is almost the same as qrd - mld s improvement . in the case of low snr , the average computational complexity , average number of detection nodes and average number of comparisons of real numbers of the proposed algorithm with @xmath56 are lower than qrd - mld s improvement . in the case of high snr , the average computational complexity , average number of detection nodes and average number of comparisons of real numbers of proposed algorithm with @xmath56 are almost same as qrd - mld s improvement while the proposed algorithm has smaller ser according to figure 1 . according to figures 3 , 5 and 7 , in the case of low snr , maximum computational complexity , maximum number of detection nodes and the maximum number of comparisons of real numbers of the proposed algorithm with @xmath55 are higher than qrd - mlds . however , because the average computational complexity , the average number of detection nodes and the average number of comparisons of real number of the proposed algorithm with @xmath55 are lower than qrd - mlds , we find that the proposed algorithm rarely gets high computational complexity , large number of detection nodes or large number of comparisons of real numbers . according to figure 814 , which is the result of second simulation , the characteristic of proposed algorithm dose not change with the number of antennas . in this paper , we propose a near ml detection algorithm . when the list size is adjusted so that the proposed algorithm has the almost same symbol error rate ( ser ) as the original qrd - mld , the average of the computational complexity and the number of detection nodes are reduced . when the list size is adjusted so that the proposed algorithm has the almost same symbol error rate ( ser ) as the qrd - mld s improvement , in the case of low snr , both the average computational complexity and average number of detection nodes are reduced and in the case of high snr , the computational complexity and average number of detection nodes of proposed algorithm is almost same as qrd - mld s improvement while ser of the proposed algorithm becomes smaller than qrd - mld s improvement . we would like to thank prof . kiyomichi araki for drawing our attention to the reference [ 6 ] . this research is partly supported by the international communications foundation . 99 e. telatar , `` capacity of multi - antenna gaussian channels , '' europ . telecommun . , vol.10 , pp.585595 , nov . g. j. foschini , `` layered space - time architecture for wireless communication in a fading environment when using multi - element antennas , '' bell labs tech . j. , vol.1 , pp.4159 , 1996 . m. o. damen , a. chkeif and j. c. belfiore , `` lattice code decoder for space - time codes , '' ieee commun . lett . , vol.36 , no.5 , pp.166168 , jan . b. hassibi and h. vikalo , `` on the sphere - decoding algorithm i. expected complexity , '' ieee trans . signal proc . , vol.53 , no.8 , pp.28062818 , aug . 2005 . k. j. kim , and r. a. iltis , `` joint detection and channel estimation algorithms for qs - cdma signals over time - varying channels , '' ieee trans . 845855 , may 2002 . j. yue , k. j. kim , g. d. gibson , and r. a. iltis , `` channel estimation and data detection for mimo - ofdm systems , '' proc . ieee globecom , vol.2 , pp.581585 , dec . y. dai , s. sun , and z. lei , `` a comparative study of qrd - m detection and sphere decoding for mimo - ofdm systems , '' proc . ieee pimrc , vol.1 , pp.186190 , sept . h. kawai , k. higuchi , n. maeda , and m. sawahashi , `` adaptive control of surviving symbol replica candidates in qrm - mld for ofdm mimo multiplexing , '' ieee jsac , vol . 24 , no . 6 , pp.11301140 june 2006 . a. v. aho , j. e. hopcoft , and j. d. ullman , data structures and algorithms , chapter 6.3 , addison - wesley , reading , ma , 1983 . t. fukatani , r. matsumoto , and t. uyematsu , `` two methods for decreasing the computational complexity of the mimo ml decoder , '' ieice trans . fundamentals , vol . e87-a , no.10 , pp.25712576 , oct . 2004 . b. m. hochwald and s. ten brink , `` achieving near - capacity on a multiple - antenna channel , '' ieee trans . 51 , vol.51 , no.3 , pp.389399 , mar . r. g. gallager , `` low density parity check codes , '' mit press , cambridge , ma , 1963 . c. berrou and a. glavieux , `` near optimum error correcting coding and decoding : turbo - codes , '' ieee trans . commun . , vol.44 , no.10 , pp.12611271 , oct 1996 .
we propose dijkstra s algorithm with bounded list size after qr decomposition for decreasing the computational complexity of near maximum - likelihood ( ml ) detection of signals over multiple - input - multiple - output ( mimo ) channels . 
 after that , we compare the performances of proposed algorithm , qr decomposition m - algorithm ( qrd - mld ) , and its improvement . when the list size is set to achieve the almost same symbol error rate ( ser ) as the qrd - mld , the proposed algorithm has smaller average computational complexity .