This paper describes the derivation and verification of a phoneme model of English speech. The model is used to generate a stream of phonemically labeled speech frames to model speech input for the design of a distributed speech understanding system. New computer architectures to perform speech understanding in real time should incorporate information about the characteristics of English speech. In order to predict the performance of a new architecture, it is necessary to simulate the design using either massive amounts of speech data or, as an alternative, a statistical model of speech. A statistically generated phoneme stream is used to avoid the difficulty of performing computationally intensive acoustic parameterization on the enormous amount of speech input data which would be required to obtain representative phoneme distributions and patterns of speech.

Highly parallel computer architectures and algorithms for speech analysis operations are surveyed. The classes of architectures considered include SIMD, skewed-SIMD, MIMD, and data flow machines, associative processors, and pipelined systolic and wavefront arrays. Parallel algorithms for digital filtering, FFTs, and linear predictive coding are summarized. System requirements are analyzed in terms of number and complexity of processors, memory requirements, and nature and complexity of inter-processor communications.

A speaker independent isolated word speech recognition system is developed based on computer generated phonemes (CGP). A CGP is a vector of features that has been generated to represent a region of speech. The CGP creation algorithm looks for stable sounds in the incoming word through the use of a similarity measure. When a stable sound is detected a CGP is created to represent it. In addition to the creation of CGPs for stable vocal tract sounds, when unvoiced fricatives occur at either the beginning or end of a word a representative CGP is created. Using a heavily constrained dynamic time warping algorithm, the CGPs of the incoming word are then compared against reference templates, which consist of previously created strings of CGPs. The identity of the reference template which is closest in distance to the incoming test word is chosen as the estimate of the test word.

Parallel processing is applied to the speech analysis tasks of homomorphic prediction for pole/zero spectral estimation and cepstrum pitch determination. A number of issues bearing on the feasibility of the use of large-scale parallel processing for speech applications are addressed. The speedup over serial implementations is analyzed. The processing task considered consists of a number of distinct algorithms, including FFTs, autocorrelation and covariance LPC analyses, and inverse filtering. The compatibility of adjacent algorithms in the processing sequence is considered in terms of the number of processors used by successive algorithms, the compatibility of the allocation of data to processors, and the type of interprocessor communication needed at the junctures between algorithms. Based on the analyses, the conditions under which the parallel implementation should be most efficient are derived.

Synchronous, highly parallel algorithms to perform dynamic time warping are presented. Algorithms are developed for two classes of parallel systems: SIMD (single instruction stream-multiple data stream) machines and arrays of VLSI processors. The machine capabilities required for the SIMD and VLSI array approaches are compared, and algorithm complexities are given.

Image correlation is representative of a wide variety of window-based image processing tasks. The way in which multimi-croprocessor systems (e.g., PASM) can use SIMD parallelism to perform image correlation is examined. Two fundamental algorithm strategies are explored. In one approach, all of the data that will be needed in a processor are transferred to the processor and operated on there. In the other, each processor performs all possible operations on its local data, generating partial results which are then transferred to the processor in which they are needed. The "time/space/inter-processor-transfer" complexities of the two algorithm approaches are analyzed in order to quantify the differences resulting from the two -strategies. For both approaches, the asymptotic time complexity of the N-processor SIMD algorithms is (1/N)th that of the corresponding serial algorithms.

Due to advances in VLSI technology, large scale arrays of microprocessors forming parallel processing systems have become feasible. The use of such a microprocessor array operating in the SIMD (single instruction stream-multiple data stream) mode to perform image resampling is explored. A general theory of resampling in terms of offsets is developed. From this, an approach to performing resampling in an SIMD environment is given. Detailed analysis of the SIMD algorithm is presented, and computational speedup over conventional uniprocessor approaches is shown to be approximately a factor of N where N is the number of processors used.

This paper examines measures for evaluating the performance of algorithms for single instruction stream–multiple data stream (SIMD) machines. The SIMD mode of parallelism involves using a large number of processors synchronized together. All processors execute the same instruction at the same time; however, each processor operates on a different data item. The complexity of parallel algorithms is, in general, a function of the machine size (number of processors), problem size, and type of interconnection network used to provide communications among the processors. Measures which quantify the effect of changing the machine-size/problem-size/network-type relationships are therefore needed. A number of such measures are presented and are applied to an example SIMD algorithm from the image processing problem domain. The measures discussed and compared include execution time, speed, parallel efficiency, overhead ratio, processor utilization, redundancy, cost effectiveness, speed-up of the parallel algorithm over the corresponding serial algorithm, and an additive measure called "sprice" which assigns a weighted value to computations and processors.

The complexity of the speech understanding task requires extensive computation. To improve the processing speed, methods are explored by which the various tasks involved in speech understanding can be structured for execution on a parallel processing system. An architecture is described in which a speech understanding system is decomposed into a series of distributed processing computation stations.

PASM, a large-scale multimicroprocessor system being designed at Purdue University for image processing and pattern recognition, is described. This system can be dynamically reconfigured to operate as one or more independent SIMD and/or MIMD machines. PASM consists of a parallel computation unit, which contains N processors, N memories, and an interconnection network; Q microcontrollers, each of which controls N/Q processors; N/Q parallel secondary storage devices; a distributed memory management system; and a system control unit, to coordinate the other system components. Possible values for N and Q are 1024 and 16, respectively. The control schemes and memory management in PASM are explored. Examples of how PASM can be used to perform image processing tasks are given.

The use of the SIMD (single instruction stream-multiple data stream) mode of parallelism to perform linear predictive coding analysis is explored. Parallel algorithms for the autocorrelation formulation of linear prediction are presented and analyzed. The algorithms are evaluated in terms of the number of arithmetic operations and interprocessor data transfers required.

Pattern classification techniques, which have been successful in determining if a segment of speech is voiced or unvoiced, are used to determine if a speech segment is voiced, unvoiced, or a combination of the two (mixed). The technique employs a binary decision procedure first to determine if the segment is predominantly voiced or unvoiced, and then to determine if the segment is produced by a mixture of the two modes of excitation. The sequence of decisions is structured as a binary tree. Also presented is a method of determining which features of the speech segment are to be used in making each of the binary decisions in the tree. In preliminary tests, classification accuracy of 95% has been obtained.

Features for use in a pattern classification scheme to identify simultaneous periodic and noiselike excitation of a segment of speech are examined. Pattern classification techniques have been applied with considerable success to the problem of classifying a speech segment as voiced or unvoiced. The features that have proven adequate for the voiced/unvoiced decision have not sufficed for the three-way voiced/unvoiced/mixed excitation classification. The incorporation of periodicity measures (e.g. from pitch determination algorithms) into such a pattern classification framework are examined. A variety of features which compare periodicity in different bands of the frequency spectrum are presented.

An algorithm for making the voiced/unvoiced decision in speech analysis is presented. Three features (LPC normalized minimum error, ratio of energy content at high to low frequencies, and input RMS) define a three-dimensional space in which the decision making process is viewed as a pattern classification problem. This is formulated as a linear program which runs on a training set to find a hyperplane dividing the V/UV regions if they are separable, or minimizing the distance by which misclassification occurs if they are not. A procedure is given for selecting the features and constructing the training set.