The sparse Fourier transform (SFT) seeks to recover k non-negligible Fourier coefficients from a k-sparse signal of length N (k«N). A single frequency signal can be recovered via the Chinese remainder theorem (CRT) with sub-sampled discrete Fourier transforms (DFTs). However, when there are multiple non-negligible coefficients, more of them may collide, and multiple stages of sub-sampled DFTs are needed to deal with such collisions. In this paper, we propose a combinatorial aliasing-based SFT (CASFT) algorithm that is robust to noise and greatly reduces the number of stages by iteratively recovering coefficients. First, CASFT detects collisions and recovers coefficients via the CRT in a single stage. These coefficients are then subtracted from each stage, and the process iterates through the other stages. With a computational complexity of O(klog klog 2N) and sample complexity of O(klog 2N), CASFT is a novel and efficient SFT algorithm.

We aim to establish a highly efficient transmitting power control (TPC) scheme suitable for the reverse link of high-speed CDMA packet communication systems. Reservation-based access is assumed to be used for packet transmission in the reverse link. First, we describe a hybrid TPC that we created to cope with average interference changes. The target receiving power in the hybrid TPC is set according to the interference averaged over a comparatively long period of time. We show, using experiments on our high-speed packet communication experimental system, that hybrid TPC can effectively reduce transmission power consumption and PER compared with basic receiving power based TPC. Furthermore, we need to change the transmitting power according to the instantaneous interference to cope with instantaneous interference changes slot by slot. However, in a high-speed packet communication system, the interference level can change dramatically in a very short period of time. The TPC of cdma2000 or W-CDMA cannot efficiently cope with rapidly and greatly changing interference levels. Therefore, we created another two novel TPCs. Interference is divided in these TPCs into intra-cell and inter-cell interference. The supposed inter-cell interference level is changed according to the change in the probability distribution of the inter-cell interference, and the necessary transmitting power for a packet is calculated based on intra-cell allocation information and the supposed inter-cell interference level. Computer simulations show that, with the proposed TPCs, throughput can be increased by more than 200% compared with the type of TPC used in cdma2000 or W-CDMA, and the transmitting power consumption in a mobile host (MH) can also be vastly reduced.