A new systolic decomposition for the dynamic time warping algorithm

New systolic architectures for the Dynamic Time Warping (DTW)-algorithm have been evaluated. The DTW-algorithm is used as a non-linear pattern matching technique in isolated and continuous speech recognition systems. A non-conventional decomposition of the recursive DTW-algorithm, bit-serial computation, extensive pipe-lining and simultaneous matching of multiple patterns are used in order to execute the DTW-algorithm in real-time. The proposed decomposition leads to compact realizations of complete systolic arrays on a single chip. A typical realization of an array of 14 systolic processors in a 4μm 1.5 V CMOS process contains approximately 15,000 transistors on a chip area of 11.5 mm². With a clock-frequency of only 100 kHz, we already achieve a matching in real-time (0.2 sec) with 60 reference words. One processor element has been integrated.