On computational complexity of optimized temporal decomposition algorithm for speech signal modelling

An optimized algorithm for a temporal decomposition (TD) model of speech is useful for very low-bit-rate speech coding in the context of voice storage applications. The event localizing task associated with the optimized TD is regarded as the major computational component of the algorithm. This paper provides a theoretical analysis of the computational complexity of the optimized TD algorithm which is important from an implementation point of view. Computational complexities of exhaustive, recursive, and Viterbi search techniques as applied to the event localizing task are analyzed. It is proven that Viterbi search achieves the minimum computational complexity with associated cost increasing in proportion to N³ at a fixed event rate, where N is the block size of TD analysis. This result has a significant implication in selecting the block size for a practical implementation of the optimized TD algorithm.