Home > Publications > International Journal
International Journal
Title Lower Bound on Expected Complexity of Depth-First Tree Search with Multiple Radii
Journal Name IEEE Commun. Lett.
First Author Jun-il Ahn
Coauthor K. Kim
Publication Date 2012.06.01 Link Link icon
Impact Factor (%) 1.16 Date 2013-09-06 13:29
Depth-?rst tree search with multiple radii (DFTSMR) algorithm attains signi?cant complexity reduction over DFTS with a single radius (DFTS-SR) for solving integer leastsquares (ILS) problems. Herein, we derive the lower bound on the expected complexity of DFTS-MR under i.i.d. complex Gaussian environments. Currently, the upper bound on the expected DFTS-MR complexity is known. Our analytical result shows the computational dependence on the statistics of the channel, the noise, and the transmitted symbols. It also re?ects the use of multiple radii, which is one of the main characteristics of DFTS-MR. The resultant lower bound provides an ef?cient means to better understand the complexity behavior of DFTSMR, along with the (known) upper bound.
광주과학기술원 한·러 MT-IT 융합기술연구센터 광주과학기술원정보통신공학부