| Paper: | SPCOM-L2.3 | ||
| Session: | Performance of MIMO systems | ||
| Time: | Wednesday, May 19, 16:10 - 16:30 | ||
| Presentation: | Lecture | ||
| Topic: | Signal Processing for Communications: Capacity and Performance Analysis, Optimization, and Bounds | ||
| Title: | AN EXPONENTIAL LOWER BOUND ON THE EXPECTED COMPLEXITY OF SPHERE DECODING | ||
| Authors: | Joakim Jaldén; Royal Institute of Technology (KTH) | ||
| Björn Ottersten; Royal Institute of Technology (KTH) | |||
| Abstract: | The sphere decoding algorithm is an efficient algorithm used to solve the maximum likelihood detection problem in several digital communication systems. The sphere decoding algorithm has previously been claimed to have polynomial expected complexity. While it is true that the algorithm has an expected complexity comparable to that of other polynomial time algorithms for problems of moderate size it is a misconception that the expected number of operations asymptotically grow as a polynomial function of the problem size. In order to illustrate this point we derive an exponential lower bound on the expected complexity of the sphere decoder. | ||
| Back | |||
Home -||-
Organizing Committee -||-
Technical Committee -||-
Technical Program -||-
Plenaries
Paper Submission -||-
Special Sessions -||-
ITT -||-
Paper Review -||-
Exhibits -||-
Tutorials
Information -||-
Registration -||-
Travel Insurance -||-
Housing -||-
Workshops