A variable-order Markov chain for coding of speech spectra

We present a method that reduces the bit rate of a low rate LPC vocoder by modelling the sequence of quantized spectra by a Markov chain. To minimize the bit rate, one would want to use a high-order chain. Unfortunately, a high-order chain would require an inordinate amount of data for training. We describe in this paper the use of a variable order Markov chain that maximizes the effective use of a given amount of speech data. To reduce the number of states of a high-order chain, we define an equivalence relation on the states, i.e., "similar" states are grouped together in an equivalence class and a single conditional distribution is associated with the equivalence class. We introduce two equivalence relations. In the first, called variable order Markov chain, the equivalence classes represent the most probable states of any order. In the second method, called variable resolution, the equivalence class is obtained by decreasing the quantization accuracy in representing a spectrum that belongs to a more remote past. For an LPC vocoder with 64 possible spectra (using 6-bit vector quantization), the second method is superior to the first and decreases the entropy from 6 bits to 4 bits per spectrum with 256 equivalence classes.