CAREER: Exploring the Complexity Limits of Joint Data Detection and Channel Estimation: Exact, Polynomial-Complexity Solutions and Ultra-Fast Approximations

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

Future communication systems will be required to operate very close to their theoretical limits and achieve high performance with limited resources (e.g., bandwidth, energy, complexity). In order to realize these goals, the receiver of a communication system should be able to decode the digital data in the presence of channel uncertainty (e.g., unknown channel quality, interference, etc.). The current state of knowledge regarding the complexity of these receivers is that their complexity grows exponentially with the sequence length. This is unacceptable when practical implementation of these algorithms is of interest. A number of fundamental questions thus arise: (i) How accurate is the conventional wisdom that complexity grows exponentially with the sequence length? (ii) What is the impact of the above question on the design of near-optimal, approximate algorithms suited for ultra-fast integrated circuit implementation? (iii) How can the complexity/performance tradeoff of these approximate algorithms be analyzed, and how can it be improved? This research addresses the aforementioned fundamental questions using a novel approach in looking at the problem of joint data detection and channel estimation, consisting of two main thrusts: (a) On the theoretical front, the current state of knowledge is challenged, by investigating a broad class of communication scenarios for which the exact solution can be obtained with only polynomial complexity. (b) Utilizing the constructive proofs of the aforementioned statements, a family of novel receivers is investigated with near-optimal performance, linear complexity, and moreover, algorithmic structure that is suitable for high-speed hardware implementation.