Algorithm design for efficient implementation of coding and signal processing systems

Advanced error control coding and signal processing techniques find wide applications in various communication systems, such as magnetic recording channels, fiber optical channels, wireline and wireless communication systems. Low-density parity-check (LDPC) codes and multiple-multiple-output (MIMO) technology have been receiving a lot of attention, since they greatly increase the capacity and improve the performance of future communication systems. In this dissertation, we focus on designing algorithms that enable efficient hardware implementations of LDPC codes and MIMO detection systems.;Quasi-cyclic (QC) LDPC codes are of great interest since their regular code structure leads to efficient hardware implementations. We propose and implement in FPGA two partly parallel decoder architectures for QC LDPC codes to improve the decoding throughput and memory requirement of existing decoders. Our over-lapped message passing (OMP) decoder achieves the maximum throughput gain and hardware utilization efficiency (HUE) due to overlapping, hence has higher throughput and HUE than previously proposed OMP decoders while maintaining the same hardware requirements and the same error performance. We also show that the maximum throughput gain and HUE achieved by our OMP decoder are ultimately determined by the given code. Thus, we propose a coset-based construction method, which results in QC LDPC codes that allow our optimal OMP decoder to achieve higher throughput and HUE. To further reduce the memory requirement of our OMP decoder, we propose the parallel turbo-sum-product (PTSP) decoder architecture. Implementation results show that our PTSP decoder achieves better error performance, faster convergence and hence higher throughput than the OMP decoder with reduced memory requirement.;Hardware implementations of tree search based MIMO detection often have limited performance due to large memory requirement or high computational complexity of sophisticated MIMO detection algorithms. We propose new tree search based detection algorithms that achieve maximum likelihood (ML) performance under any given memory constraints and with reduced computational complexity. To this end, we make two main contributions. First, we propose a memory-constrained tree search (MCTS) algorithm that bridges the gap between the sphere decoding (SD) and stack algorithms. Our MCTS algorithm dynamically adapts to any pre-specified memory constraint and offers a graceful tradeoff between computational complexity and memory requirement while maintaining the ML performance. When the memory size is set to the minimum, our MCTS algorithm is similar to the SD algorithm. As the memory size increases, the average computational complexity of our MCTS algorithm decreases. When the memory size becomes large, our MCTS algorithm is similar to the stack algorithm, having similar average computational complexity but requiring significantly less memory. Second, to further reduce the computational complexity of tree search based ML detection algorithms, we propose novel ordering schemes that can be easily embedded in the QR decomposition and take into account both the channel matrix and the received signal (noise); simulation results show that our ordering schemes lead to reduced average computational complexity for the SD and MCTS algorithms, and the reduction is significant at low to medium SNR region.