Despite what is generally believed, we have recently shown that discrete-distribution HMMs can outperform continuous-density HMMs at significantly faster decoding speeds. Recognition performance and decoding speed of the discrete HMMs are improved by using product-code Vector Quantization (VQ) and mixtures of discrete distributions. In this paper, we present efficient training and decoding algorithms for the discrete-mixture HMMs (DMHMMs). Our experimental results show that the high-level of recognition accuracy of continuous mixture-density HMMs (CDHMMs) can be maintained at significantly faster decoding speeds.