In multiple-input multiple-output (MIMO) systems, the use of lattice reduction methods such as the one proposed by Lenstra-Lenstra-Lovasz (LLL) significantly improves the performance of the suboptimal solutions like zero-forcing (ZF) and zero-forcing deceision-feedback-equalizer (ZF-DFE). Today's high rate data communication demands faster lattice reduction methods. Taking advantage of the temporal correlation of a Rayleigh fading channel, a new method is proposed to reduce the complexity of the lattice reduction methods. The proposed method achieves the same error performance as the original lattice reduction methods, but significantly reduces the complexity of lattice reduction algorithm. The proposed method can be used in any MIMO scenario, such as the MIMO detection, and broadcast cases, which are studied in this work.

In multiple-input multiple-output (MIMO) systems, the use of lattice reduction methods such as the one proposed by Lenstra-Lenstra-Lovasz (LLL) significantly improves the performance of the suboptimal solutions like zero-forcing (ZF) and zero-forcing deceision-feedback-equalizer (ZF-DFE). Today's high rate data communication demands faster lattice reduction methods. Taking advantage of the temporal correlation of a Rayleigh fading channel, a new method is proposed to reduce the complexity of the lattice reduction methods. The proposed method achieves the same error performance as the original lattice reduction methods, but significantly reduces the complexity of lattice reduction algorithm. The proposed method can be used in any MIMO scenario, such as the MIMO detection, and broadcast cases, which are studied in this work.

Lattice-Reduction has become a popular way of improving the performance of MIMO detectors. However, developing an efficient high-throughput VLSI implementation of LR has been a major challenge in the literature. This thesis proposes a hardware-optimized version of the popular LLL algorithm that reduces its complexity by 70% and achieves a fixed runtime while maintaining ML diversity. The proposed algorithm is implemented for 4x4 MIMO systems and uses a novel pipelined architecture that achieves a fixed low processing latency of 40 cycles, resulting in a fixed throughput that is independent of the channel correlation. The proposed LR core, fabricated in 0.13um CMOS, is the first fabricated and tested LR ASIC implementation in the literature. Test results show that the LR core achieves a maximum clock rate of 204 MHz, yielding a throughput of 510 Mbps, thus satisfying the aggressive throughput requirements of emerging 4G wireless standards, such as IEEE-802.16m and LTE-Advanced.

Lattice-Reduction has become a popular way of improving the performance of MIMO detectors. However, developing an efficient high-throughput VLSI implementation of LR has been a major challenge in the literature. This thesis proposes a hardware-optimized version of the popular LLL algorithm that reduces its complexity by 70% and achieves a fixed runtime while maintaining ML diversity. The proposed algorithm is implemented for 4x4 MIMO systems and uses a novel pipelined architecture that achieves a fixed low processing latency of 40 cycles, resulting in a fixed throughput that is independent of the channel correlation. The proposed LR core, fabricated in 0.13um CMOS, is the first fabricated and tested LR ASIC implementation in the literature. Test results show that the LR core achieves a maximum clock rate of 204 MHz, yielding a throughput of 510 Mbps, thus satisfying the aggressive throughput requirements of emerging 4G wireless standards, such as IEEE-802.16m and LTE-Advanced.

The efficient high-throughput VLSI implementation of near-optimal multiple-input multiple-output (MIMO) detectors for 4x4 MIMO systems in high-order quadrature amplitude modulation (QAM) schemes has been a major challenge in the literature. To address this challenge, this thesis introduces a novel scalable pipelined VLSI architecture for a 4x4 64-QAM MIMO receiver based on K-Best lattice decoders. The key contribution is a means of expanding/visiting the intermediate nodes of the search tree on-demand, rather than exhaustively along with three types of distributed sorters operating in a pipelined structure. The combined expansion and sorting cores are able to find the K best candidates in K clock cycles. The proposed architecture has a fixed critical path independent of the constellation order, on-demand expansion scheme, efficient distributed sorters, and is scalable to a higher number of antennas/constellation orders. Fabricated in 0.13um CMOS, it operates at a significantly higher throughput (5.8x better) than currently reported schemes and occupies 0.95 mm2 core area. Operating at 282 MHz clock frequency, it dissipates 135 mW at 1.3 V supply with no performance loss. It achieves an SNR-independent decoding throughput of 675 Mbps satisfying the requirements of IEEE 802.16m and Long Term Evolution (LTE) systems. The measurements confirm that this design consumes 3.0x less energy/bit compared to the previous best design.

The efficient high-throughput VLSI implementation of near-optimal multiple-input multiple-output (MIMO) detectors for 4x4 MIMO systems in high-order quadrature amplitude modulation (QAM) schemes has been a major challenge in the literature. To address this challenge, this thesis introduces a novel scalable pipelined VLSI architecture for a 4x4 64-QAM MIMO receiver based on K-Best lattice decoders. The key contribution is a means of expanding/visiting the intermediate nodes of the search tree on-demand, rather than exhaustively along with three types of distributed sorters operating in a pipelined structure. The combined expansion and sorting cores are able to find the K best candidates in K clock cycles. The proposed architecture has a fixed critical path independent of the constellation order, on-demand expansion scheme, efficient distributed sorters, and is scalable to a higher number of antennas/constellation orders. Fabricated in 0.13um CMOS, it operates at a significantly higher throughput (5.8x better) than currently reported schemes and occupies 0.95 mm2 core area. Operating at 282 MHz clock frequency, it dissipates 135 mW at 1.3 V supply with no performance loss. It achieves an SNR-independent decoding throughput of 675 Mbps satisfying the requirements of IEEE 802.16m and Long Term Evolution (LTE) systems. The measurements confirm that this design consumes 3.0x less energy/bit compared to the previous best design.

NTRU is a public key cryptosystem, which was first introduced in 1996. It is a ring-based cryptosystem and its security relies on the complexity of a well-known lattice problem, i.e. shortest vector problem (SVP). There is no efficient algorithm known to solve SVP exactly in arbitrary high dimensional lattices. However, approximate solutions to SVP can be found by lattice reduction algorithms. LLL is the first polynomial time algorithm that finds reasonable short vectors of a lattice. The best known attacks on the NTRU cryptosystem are lattice attacks. In these attacks, the lattice constructed by the public key of the system is used to find the private key. The target vector, which includes private key of the system is one of the short vectors of the NTRU lattice. In this thesis, we study NTRU cryptosystem and lattice attacks on NTRU. Also, we applied an attack to a small dimensional NTRU lattice.

The objective of the dissertation research is to understand the complex interaction between the algorithm and hardware aspects of symbol detection that is enhanced by lattice reduction (LR) preprocessing for wireless MIMO communication systems. The motivation for this work stems from the need to improve the bit-error-rate performance of conventional, low-complexity detectors while simultaneously exhibiting considerably reduced complexity when compared to the optimal method, maximum likelihood detection. Specifically, we first develop an understanding of the complex Lenstra-Lenstra-Lovász (CLLL) LR algorithm from a hardware perspective. This understanding leads to both algorithm modifications that reduce the required complexity and hardware architectures that are specifically optimized for the CLLL algorithm. Finally, we integrate this knowledge with an understanding of LR-aided MIMO symbol detection in a highly-correlated wireless environment, resulting in a joint LR/symbol detection algorithm that maps seamlessly to hardware. Hence, this dissertation forms the foundation for the adoption of lattice reduction algorithms in practical, high-throughput wireless MIMO communications systems.

No description available.

Lattice reduction aided techniques have been successfully applied to a wide range of applications. Efficient and robust lattice basis reduction algorithms are valuable. In this thesis, we present an O(n^4 logB) hybrid Jacobi method for lattice basis reduction, where n is the dimension of the lattice and B is the maximum length of the input lattice basis vectors. Building upon a generic Jacobi method for lattice basis reduction, we integrate the size reduction into the algorithm to improve its performance. To ensure the convergence and the efficiency of the algorithm, we introduce a parameter to the Lagrange reduction. To improve the quality of the computed bases, we impose a condition on the size reduction, delay the structure restoration, and include a postprocessing in the hybrid method. Our experiments on random matrices show that the proposed algorithm produces better reduced bases than the well-known LLL algorithm and BKZ 2.0 algorithm, measured by both the orthogonality defect and the condition number of the basis matrix. Moreover, our hybrid method consistently runs faster than the LLL algorithm, although they have the same theoretical complexity. We have also investigated two potential applications of the hybrid method. The application simulations show that the hybrid method can improve the stability of the communication channels for Multi-Input Multi-Output systems, and can partially discover the plain text when attacking the GGH cryptosystem. / Thesis / Doctor of Philosophy (PhD) / Lattice reduction aided techniques have been successfully applied to a wide range of applications. Efficient and robust lattice basis reduction algorithms are valuable. In this thesis, we present an O(n^4 logB) hybrid Jacobi method for lattice basis reduction, where n is the dimension of the lattice and B is the maximum length of the input lattice basis vectors. Our experiments on random matrices show that the proposed algorithm produces better reduced bases than the well-known LLL algorithm and BKZ 2.0 algorithm, measured by both the orthogonality defect and the condition number of the basis matrix. We have also investigated two potential applications in MIMO systems and cryptosystems.