| With the current trend towards Internet wireless access, there is an increased interest in portable, hand-held digital communication devices, where power is an important performance metric. If we assume that algorithm complexity is a good approximation of the power consumption, then variable complexity algorithms are beneficial since they enable reduced power modes. This dissertation addresses variable complexity algorithms in three areas:; First, we propose a novel variable complexity algorithm (VCA) for transform coding based on energy thresholds. Since our VCA computes a subset of the transform coefficients, it yields different complexity and rate distortion performance than standard transform coders. We present analytical results for the optimal bit allocation in this VCA. Experiments show that our VCA can achieve better rate distortion tradeoff at low rates than the popular JPEG techniques.; Second, we propose a new proxy-based framework that is capable of accelerating video decoding operations of portable devices with wireless access ability. We demonstrate that an adaptive proxy can significantly reduce the complexity of the Inverse Discrete Cosine Transform running at the client without violating any applicable constraint on the proxy-client bandwidth.; Third, we solve the problem of computation control for variable complexity Fano decoders. Fano decoders can provide the desirable tradeoff between bit error rate and decoder complexity. However, buffers are required due to large variations in decoding delays. In order to minimize the overall probability of block loss under a finite buffer size constraint, we propose algorithms for controlling the decoding complexity adaptively with changes of buffer occupancy. For memoryless additive white Gaussian noise channels, our control algorithms can reduce the block loss by as much as 40%. For slow flat Rayleigh fading channels corresponding to low/medium degree of mobility, we introduce prediction algorithms based on finite state Markov models that characterize the memory of the channel. Simulations show that block loss can be lowered by an additional 5% as compared to results obtained under the assumption of memoryless channels. |
