High throughput sphere decoding algorithms: Design and implementation

Multiple-input-multiple-output (MIMO) systems are becoming the de-facto choice for reliable and high speed communication networks. Sphere decoding (SD) algorithms provide robust MIMO detection function for high throughput MIMO systems. In this thesis, first, a parallel depth-first hard output sphere decoding (PDSD) algorithm is proposed. It exploits the rapid search reduction by depth-first algorithms and the parallelism offered by breadth-first algorithms to achieve high throughput. The PDSD algorithm reaps very efficiently onto a programmable multi-processor platforms. The trade-offs between throughput and computation overhead are investigated for 2, 4 and 8 processing elements in a 4 x 4 16-QAM system across a wide range of SNR conditions. Simulation results show that PDSD demonstrates significant throughput improvement without incurring substantial computation overhead by selecting the appropriate number of processing elements.;Soft-output sphere decoding offers better performance than hard-output sphere decoding at the cost of significant increase in computation complexity. A soft-output parallel fixed complexity sphere decoding (PFSD) algorithm is presented. It uses multiple fixed complexity sphere decoders to reduce computation complexity and increase throughput. In addition, PFSD preprocessing overhead is kept low by a parallel QR decomposition algorithm. The PFSD decoder also uses a low complexity LLR algorithm to update soft-outputs in parallel. Through simulation, the PPSD algorithm demonstrates increased throughput and reduced bit error rate of a soft-output solution in a 4 x 4 16-QAM system compared to other soft-output decoders with comparable computation complexity. The PFSD algorithm has been mapped onto a Xilinx XC4VLX160 FPGA. The resulting PFSD decoder can achieve upto 75Mbps throughput for 4 x 4 64-QAM configuration at 100MHz with low control overhead.;Finally, a low complexity interpolation-based parallel QR decomposition (IPQR) algorithm is proposed. It reduces PFSD preprocessing complexity in a MIMO orthogonal frequency division multiplexing (MIMO-OFDM) system. IPQR exploits shared outputs of two permuted channel matrices. A direct mapping method is developed to compute interpolation filter inputs for one channel matrix from another without explicit QR decomposition. IPQR with direct mapping is implemented on a Xilinx XC4VLX160 FPGA. It can perform 1 QR decomposition of a 4 x 4 channel matrix every 0.1mus when clocked at 200MHz.