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

未来的通信系统将被要求非常接近它们的理论极限来操作，并且利用有限的资源（例如，带宽、能量、复杂度）。为了实现这些目标，通信系统的接收机应该能够在存在信道不确定性的情况下（例如，未知的信道质量、干扰等）。关于这些接收器的复杂性的当前知识状态是它们的复杂性随着序列长度呈指数增长。这是不可接受的，当这些算法的实际实现是ofintest。因此出现了一些基本的问题：（1）传统的智慧，复杂性增长与序列长度呈指数增长是多么准确？ (ii)上述问题对设计适用于超快集成电路实现的接近最优的近似算法有什么影响？(iii)如何分析这些近似算法的复杂性/性能权衡，以及如何改进它？本研究解决了上述基本问题，使用一种新的方法来看待联合数据检测和信道估计的问题，包括两个主要的推力：（a）在理论方面，目前的知识状态受到挑战，通过调查广泛的一类通信场景，可以获得精确的解决方案，只有多项式的复杂性。(b)利用上述陈述的建设性证明，一个家庭的新颖的接收机进行了研究，接近最优的性能，线性复杂度，而且，算法结构，这是适合于高速硬件实现。

Future communication systems will be required to operate very close totheir theoretical limits and achieve high performance with limitedresources (e.g., bandwidth, energy, complexity). In order to realizethese goals, the receiver of a communication system should be able todecode the digital data in the presence of channel uncertainty (e.g.,unknown channel quality, interference, etc.). The current state ofknowledge regarding the complexity of these receivers is that theircomplexity grows exponentially with the sequence length. This isunacceptable when practical implementation of these algorithms is ofinterest. A number of fundamental questions thus arise: (i) Howaccurate is the conventional wisdom that complexity growsexponentially with the sequence length? (ii) What is the impact ofthe above question on the design of near-optimal, approximatealgorithms suited for ultra-fast integrated circuit implementation?(iii) How can the complexity/performance tradeoff of these approximatealgorithms be analyzed, and how can it be improved?This research addresses the aforementioned fundamental questionsusing a novel approach in looking at the problem of joint datadetection 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 whichthe 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-optimalperformance, linear complexity, and moreover, algorithmic structurethat is suitable for high-speed hardware implementation.