Vector quantization (VQ) is a powerful and effective scheme which is widely used in speech and image coding applications. Two basic problems can be associated with VQ: (i) its large encoding complexity, and (ii) its sensitivity to channel errors. These two problems have been independently studied in the past. In this paper, we examine these two problems jointly. Specifically, the performances of two low-complexity VQs-the tree-structured VQ (TSVQ) and the multi-stage VQ (MSVQ) - when used over noisy channels are analyzed. An algorithms is developed for the design of channel-matched TSVQ (CM-TSVQ) and channel-matched MSVQ (CM- MSVQ) under the squared-error criterion. Extensive numerical results are given for the memoryless Gaussian source and the Gauss-Markov source with correlation coefficient 0.9. Comparisons with the ordinary TSVQ and MSVQ designed for the noiseless channel show substantial improvements when the channel is very noisy. The CM-MSVQ, which can be regarded as a block- structured combined source-channel coding scheme, is then compared with a block-structured tandem source-channel coding scheme (with the same block length as the CM-MSVQ). For the Gauss-Markov source, the CM-MSVQ outperforms the tandem scheme in all cases which we have considered. Furthermore, it is demonstrated that the CM-MSVQ is fairly robust to channel mismatch.