| Efficient signal processing algorithms are essential in various communication systems, such as on-chip interconnect buses, wireless communication systems, magnetic recording channels, and cryptosystems. These efficient algorithms either have low computational complexities or have modular structures that are favorable in hardware implementations. In this dissertation, we investigate several efficient signal processing algorithms in different areas. These areas include crosstalk avoidance codes, multiple-input and multiple-output (MIMO) communication systems, and discrete Fourier transforms (DFTs) over finite fields.;Crosstalk avoidance codes (CACs) are of great interest since they are promising in combating the crosstalk delay problem of interconnect on-chip buses in deep sub-micron technology. As feature shrinks, the gate delay is reduced while the interconnect delay increases due to increasingly more severe crosstalk between adjacent wires. CACs are a promising technology that can reduce the crosstalk delay effectively. However, CACs require extra logic circuits as encoders and decoders (CODECs), but CODECs of the CACs are so complex, prohibiting the usage of CACs in practice. The areas and the delays of our CAC CODECs based on numeral systems all increase quadratically with the width of bus. Furthermore, to increase the code rates of CACs, we propose two dimensional CACs (TDCACs). We investigate the properties of TDCACs with and without memory, respectively.;We also investigate efficient algorithms in MIMO detection. We apply several novel ordering schemes to K-Best detectors, and show that they can improve the reliability of K-Best detecting results. The hardware implementations of our ordering schemes show that they only incur a small overhead in comparison with traditional ordering schemes, and they can achieve a high throughput with a pipelined architecture. Furthermore, we also propose a list MIMO detection algorithm using the memory-constrained tree search strategy. This algorithm offers a flexible balance of computational complexity and memory requirement, which can be tuned by the number of available memory units.;DFTs over finite fields find wide applications in various communication systems, and cyclotomic fast Fourier transforms (CFFTs) can reduce their multiplicative complexities greatly. As DFTs over non-characteristic-2 fields are taken into consideration in modern communication systems, we generalize CFFTs to arbitrary finite fields by devising efficient algorithms for cyclic convolutions over arbitrary finite fields. We also analyze the computational complexities of CFFTs in theory, and our results confirm the advantages of CFFTs. To further reduce the computational complexity of DFTs, we propose composite cyclotomic Fourier transforms, which integrate CFFTs and the idea of the prime-factor algorithm as well as the Cooley-Tukey algorithm. |
