Implementing a high accuracy continuous speech recognizer on a fixed-point processor

[0001] This application claims priority under 35 USC § 119(e)(1) of provisional application No. 60/288,799, filed May 7, 2001.

[0002] This invention relates to speech recognition and more particularly to a high accuracy continuous speech recognizer using a fixed-point processor.

[0003] Recently there has been a sharp increase in the use of wireless communication devices, such as mobile phones, in the car. Such dialing while driving situation fits the classic definition of a hands busy, eyes busy task. Speech recognition is a natural and effective solution. Not only convenience, but also safety concerns motivate the use of voice technology in this situation. Other than mobile phones, as PDA (personal digital assistance) devices become smaller, input becomes more difficult. Speech recognition is a natural way to interact with these small devices because button or touch screens are not feasible or too expensive. All those devices are battery powered. Continuous speech recognition is a resource intensive algorithm. Commercial dictation software requires more than 10 M bytes to install on a disk and 32M bytes RAM to run the applications. A typical embedded system can not afford this much RAM because of its high cost and power consumption. It also lacks disk to store the large amount of static data (acoustic models). A 32-bit, floating point CPU with lots of memory is too expensive and drains too much power. Most of these embedded fixed point processor devices use a 16-bit, fixed point CPU with only on chip memory. It is highly desirable to fit a speech recognition algorithm on such a device without performance degradation or sacrificing functionality.

[0004] A most challenging condition is to provide this for hands free digit dialing in a highway driving condition.

[0005] In accordance with one embodiment of the present invention a continuous speech recognizer with Mel-scaled cepstrum coefficients (MFCC) processing is provided using fixed-point processor with conversion and size (program, model, search space, etc.) reduction.

[0010] Referring to FIG. 1 the input speech xt is sampled at analog-to-digital (A/D) converter 11 and the digital samples are applied to MFCC (Mel-scaled cepstrum coefficients) front end processing 13 to extract speech features used for speech recognition. This is described in S. B. Davis and P. Mermelstein article entitled “Comparison of Parametrix Representation for Monosyllabic Word Recognition in Continuously Spoken Sentences” in IEEE Trans. Acoustic. Speech and Signal Processing; ASSP-28(4);357–366;August 1980. To enhance performance against additive noise, PMC (parallel model combination) 15 is integrated. PMC 15 is described in Technical Report F-INFENG/TR-135, Cambridge University Engineering Department, UK, 1993 by J. F. Gales and S. J. Young entitled “Parallel Model Combination for Speech Recognition and Noise”. The MFCC and Gaussian mean vectors are applied to PMC 15. The features extracted in the noise are used to modify Hidden Markov Models (HMMs) to adapt the models to the noisy environment. The adapted HMMs including mean vectors are applied to the search procedure to recognize the grammar. The search engine 17 is based on time-synchronous one pass procedure described in article by H. Ney entitled “The use of One Stage Dynamic Programming Algorithm for Connected Word Recognition in IEEE Trans. On Acoustics, Speech and Signal Processing, 32(2):263–271, April 1984.

Fixed-Point Issues:

[0011] In a floating-point processor, all numbers are normalized into a format with sign bit, exponent, and mantissa. For example, the IEEE standard for float has 1-bit sign bit, 8-bit exponent, and 23-bit mantissa. The exponent provides a large dynamic range: 2¹²⁸≈10³⁸. The mantissa provides a fixed level of precision. Because every float number is individually normalized into this format, it always maintains a 23-bit precision as long as it is within the 1038 dynamic range. This good precision covering a large dynamic range frees the algorithm designer from worrying about the scaling problems. However, it comes at the cost of more power, larger silicon, and higher cost. In a 16-bit fixed-point processor, on the other hand, the only format is a 16-bit integer, ranging from 0 to 65535 (un-signed) or −32768 to +32767 (signed). The algorithm has to carefully normalize its numerical behavior to within the dynamic range of a 16-bit integer at every stage of the computation.

[0012] In addition to the data format limitation, another consideration is that some operations can be done efficiently, others cannot. A fixed-point DSP processor usually incorporates a hardware multiplier so that addition and multiplication can be completed in one CPU cycle. However, there is no hardware for division and it takes more than 20 cycles to do it by a routine. To avoid division, we want to pre-compute the inverted data. For example, we can pre-compute and store 1/σ instead of σ for the Gaussian probability computation. Other than the explicit divisions, there are also implicit divisions hidden in other operations. For example, pointer arithmetics is used heavily in the memory management in the search algorithm. Pointer subtraction actually incurs a division. Division can be approximated by multiplication and shift. However, unlike DSP algorithms, pointer arithmetics cannot tolerate any error; such substitute is accurate only within a range of values. Algorithm design has to take this into consideration and make sure it is accurate under all possible running conditions.

[0013] Fixed-point problems can be very tedious to accommodate in algorithms, and some algorithms simply cannot be done using only 16-bit of precision. For example, audio and ADSL (Asynchronous Digital Subscriber Line) modem algorithms require very high precision FFT (Fast Fourier Transforms); they need 32-bit FFT to do the job right. Fortunately, we found that 16-bit resolution is not a problem for speech recognition algorithm. With careful scaling, one can convert the algorithm to fixed-point with no performance degradation.

[0014] In a speech recognition algorithm, MFCC computation is where most of the fixed-point issues occur. Search, although more complicated and consumes the most MIPS, simply accumulates scores; therefore does not present much numerical precision problem. Following are the major steps in MFCC computation:

• [0015] 1. Preemphasis. y_t=x_t−0.96×x_t-1.
• [0016] 2. Hamming Window. z_t=ω_t×y_t.
• [0017] 3. FFT. ƒ_n^r+i+ƒ_nⁱ=FFT(z_t), ∀n=0 . . . 255.
• [0018] 4. Complex FFT to power spectrum.
  P_n=(ƒ_n^r)²+(ƒ_nⁱ)².
• [0019] 5. Mel scale power spectrum into filter bank.
  b_m=Melfilter(P_n), ∀m=0 . . . 19.
• [0020] 6. Log filter bank. b_m^l=log(b_m).
• [0021] 7. Inverse cosine transform log filter bank into MFCC.
  c_i=Inv cos×fm(b_m^l), ∀i=0 . . . 7.

[0022] In accordance with the present invention these steps illustrated in FIG. 2 are performed in a unique manner to achieve the results in a fixed point processor. In these steps all the numeric variables in the algorithm need to be normalized and represented in a suitable Q-point. Q-n means there are n bits to the right of the decimal point. For example, for a 16-bit word, a Q 11 format covers the range from −16 to +16. To simplify the process, we classify the variables into two categories: dynamic Q-point and fixed Q-point. They are separated by the log operation in step 6 above. All variables before the log step 6 (Steps 1–5) are dynamic Q-point; all variables after that are fixed Q-point (Step 7) as illustrated in FIG. 2. This is because log reduces the dynamic range tremendously. It is possible to represent the range by a fixed Q-point 16-bit format after log. Before log, however, the dynamic range is too large to be covered by 16-bit; thus frame-dependent dynamic Q-point is required.

The design principals for fixed Q-point variables are:

• [0023] Compute dynamic ranges for all variables.
• [0024] Inspect the dynamic range and choose a fixed Q-point for each variable.
  • [0025] For array variables (e.g. MFCC), each dimension may have different dynamic range. Choose a normalization factor for each of the dimension to normalize the dynamic range so they can all use the same Q-point.
• [0026] Choose an appropriate place in the algorithm to incorporate the normalization factors.

[0027] Lower dimension MFCC has larger dynamic range. We choose the following normalization factors and use Q 11 to represent the 8 MFCC and 8 Δ-MFCC:

• • [0028] 16 4 4 2 2 2 1 1 4 2 2 1 1 1 1 1

[0029] The normalization factors are incorporated in the inverse cosine transform Step 7. For variables before the log step, the dynamic range is very large and thus fixed Q-point is not feasible. We have to normalize each frame of data differently to maintain adequate precision. The design principals are:

• [0030] Normalize to take advantage of the full 16-bit dynamic range.
• [0031] Remember the normalization factors and compensate before output.

[0032] Floating-point processor normalizes every number independently. We cannot afford to do that because the scaling needs to be compensated before output. However, we can normalize every frame of data for every algorithm step. The compensation can be done in the log step easily. Such normalization is to scale up an array of values with a factor so that the largest value will be using the full 16-bit resolution.

[0033] The computation basically involves multiplication and addition. Although data memory is 16-bit only, the accumulator is 32-bit (or even 40-bit). The inputs to an operation have to be 16-bit values; the output value can be 32-bit. The normalization can be done at the 16-bit input or at the 32-bit output. For example, in the pre-emphasis step you can normalize the 16-bit input speech samples, x_t; or the 32-bit x_t−0.96×x_t-1 pre-emphasized output. Normalizing the 16-bit input may give you less resolution because the worst case needs to be accommodated but may not occur. Normalizing the 32-bit output will give you more resolution at the cost of more computation or memory. This is because the 32-bit output needs to be scaled back to 16-bit to be fed into next step of the algorithm, and normalization is a two-pass process. We choose to normalize the 32-bit output: x_t−0.96×x_t-1, ω_t×y_t, and (ƒ_n^r)²+(ƒ_n^t)², to achieve the best possible resolution; then scale them back to 16-bit: y_t, z_t, and p_n respectively.

[0034] Because 16-bit FFT can already achieve no degradation in recognition performance, there is no need for a 32-bit FFT. For a 256-point FFT, there is a multiply-and-add at each butterfly stage, a scale down of factor 2 is needed at each stage to accommodate overflow in worst case. That amounts to a total of 8 bits scale down for an 8-stage, 256-point FFT.

[0035] A square-triangle mel-frequency filter bank is used to convert the 128-point power spectrum p_n into a 20-point mel-scale filter bank b_m in Step 5. The 20-point b_m is stored in 32-bit because this is the value fed into the log dynamic range reduction operation. It is important to maintain as much resolution as possible. This is the only 32-bit value array. All other values in the algorithm are in 16-bit.

[0036] The log(x) operation in Step 6 is implemented by polynomial fit for x=0.5–1.0. The curve is very smooth, thus the polynomial fit is very accurate. Input x is first normalized to between 0.5 and 1.0 in Q 15, then fed into the polynomial evaluation. Using the C54 native POLY mnemonic to compute polynomial is very fast; and it avoids the need for a large lookup table. The compensation for all previous normalization factors is done here because it is only shift. A 2-base log is implemented so the compensation can be done by shift. A 10-base log can be computed by simply multiplying a factor.

[0037] To elaborate on the polynomial log implementation a little bit, the following MATLAB commands are used to obtain the coefficients of the polynomial that fit log2(x) for x=0.5 to 1.0.

• [0038] x=[0.5 :0.0.001.0];
• [0039] y=log2(x);
• [0040] z=polyfit (x, y, 8);
• [0041] z*347.8996
  First an array of x between 0.5 and 1.0 is created, with 0.001 sampling interval. Then y=log2(x) is computed. Then we use an 8th-order polynomial to fit the (x, y) pair. The 347.8996 factor applied on the coefficients is to scale the largest coefficient to −32768 to take advantage of the 16-bit resolution because we can only compute the polynomial in 16-bit integer. The output of log is in Q 9. It is fed into the inverse cosine transform matrix multiplication to generate MFCC in Q 11 in Step 7.

[0042] The Q 11 MFCC can be converted back to floating-point values. We have compared it with the MFCC from the floating-point version of the algorithm. They are very close: identical to the second and third decimal points even for very low energy frames.

PMC Issues:

Other than MFCC computation, PMC also presents fixed-point problems. A simplified PMC is implemented that compensates only mean (not variance); and it uses the log-add assumption (instead of the more accurate log-normal assumption). The major steps are:

• [0043] 1. Compute noise MFCC profile.
• [0044] 2. Cosine transform MFCC into log mel-scale filter bank.
  b^l=Cos×fm(C_i), ∀i=0 . . . 7, m=0 . . . 19.
• [0045] 3. Expotential—use polynominal fit to do exp. to convert log filter bank into linear filter bank.
  b_m=exp(b_m^l)
• [0046] 4. Model combination in the linear filter bank domain.
• [0047] 5. Convert the noise—compensated linear filter bank into MFCC by log and inverse cosine transform.

[0048] The PMC steps are illustrated in FIG. 3. In step 1 the noise MFCC profile is computed as discussed above. The 2-base exponential, y=2^x, in Step 3 is implemented by polynomial fit for x=0–1. Input x is in 16-bit Q 9, consistent with the MFCC design. It is first normalized to between 0 and 1, then fed into the polynomial evaluation. It is more accurate than the piecewise linear table lookup because both functions are very smooth. It is fast because it uses the C54 DSP native POLY instruction. And most importantly, it does not need the large lookup table, which is very critical because memory is a premium in an embedded system. The normalization is compensated before outputting a 32-bit linear filter bank value. Because the exponential operation increases dynamic range tremendously, it is possible that the linear filter bank value may be more than 32-bit. This was not done in the MFCC computation because all the normalizations before the log operation take care of it. To avoid overflow of the exponential polynomial, we need to normalize x into a range that can be accommodate by the exponential polynomial. The exponential polynomial will not handle the full 16-bit range as exponent. This normalization then needs to be compensated in the log operation in step 5, which follows the exponential operation. The normalization before and after the exp2 operation in the PMC algorithm enables handling more than 32 bits of resolution, which is necessary to cover the dynamic range required by the PMC algorithm.

Software Design Issues

[0049] To elaborate polynominal fill for Pow 2 from 0 to 1.0. are MATLAB commands

• [0050] x=[0:,0.01:1.0];
• [0051] y=pow2(f);
• [0052] z=polyfit (x, y, 6);
• [0053] z*16384

[0054] In an embedded system, resource is very scarce and needs to be critically conserved. Many seemingly innocent system function calls actually use a lot of resources. For example, string operation and memory allocation are all very expensive. Calling one string function will cause the whole string library to be included; and malloc( ) actually gives you more than what you need. The following major issues are addressed as represented by steps in FIG. 4.

• [0055] Streamline data structures so that all model data are efficient to store and also computable, as opposed to the typical two format scheme: one for disk storage and the other for computation.
• [0056] Examine the allocation of local and global variables to balance memory efficiency and program modularity. Local variables consume stack size. This is especially important for recursive routines.
• [0057] Replace all string operations with efficient integer operations.
• [0058] Remove all malloc( ) and free( ). Design algorithm to do memory management and garbage collection. The algorithm is tailored for exact data structure to be efficient.
  Experimental Conditions
  Two corpora were used to calibrate the performance:
• [0059] TI digits: This is the publically available corpus. 1 to 7 continuous digit strings, very clean studio quality recording, 8700 test files.

[0060] WAVES digits: This is a proprietary corpus. It is a very challenging corpus collected in car (Pontiac Grand AM), with hands-free visor mounted microphone for 20 speakers, 10 male and 10 female. The text consists of 4, 7, and 10 continuous digit strings. There are three driving conditions: parked, stop and go city driving, and highway. 800 utterances per condition were used to calibrate the performance. Because it is hands-free data, the highway condition has a SNR about zero dB.

[0061] To recognize TI digits, we used the utterances in the training part of the corpus, which does not include the 8700 test files.

[0062] Recognizing WAVES digits with HMMs trained with TI digits will result substantial increase in error rate, due to the acoustic mismatch (e.g. microphone, background noise) between the recording conditions of the two tasks. See Y. Gong. Speech recognition in noisy environments: A survey. Speech Communication, 16(3):261–291, April 1995. As there is not enough speech data to train HMMs on WAVES corpus, to recognize WAVES digits a more elaborated procedure is applied. The procedure transforms HMMS trained on TI digits to the acoustic environment of the WAVES database by using a subset of WAVES database (not included in the test files). See Y. Gong and J. J. Godfrey. Transforming HMMS for Speaker-Independent Hands Free Speech Recognition in the Car. In Proc. of IEEE Int. Conf. on Acoustics, Speech and Signal Processing, pages I-297, Phoenix, March 1999.

Results

Program Size

The resource are computed using C code compiled by C54 compiler, there is no assembly code optimization considered. The unit is 16-bit word.

[0063]

	C-compiled size
	Program	6K word
	Constant table	1K word
	Stack	1.5K word

[0064] Because there is no performance degradation for fixed-point version compared to floating-point version, all the performances are calibrated using fixed-point codes. Recognition accuracy in terms of Word Error Rate (WER) and Sentence Error Rate (SER) is reported. Search space, which depends on task and varies a lot, is also reported. Search space size is computed using Chebychev's inequality: P(|x−μ|>5σ)<1/25. This is a very loose bound. It actually covers more than 99% of the population as opposed to the 96% predicted by the equation.

For TI-digit, CMN (6) (Cepstrum Mean Removal) is enabled and PMC is disabled. 16 dimension MFCC (8 static, 8 dynamic), 428 mean and 270 variance vectors were used. The total model size is 21.5 K words.

[0065]

	WER/SER	search space
	TI digits	0.6%/1.9%	4.1K words

For WAVES digits, CMN is disabled and PMC is enabled. 16 dimension MFCC, 428 mean and 428 variance vectors were used. The total model size is 25.3K words.

[0066]

	WER/SER	search space
	parked	0.8%/4.3%	3.3K word
	stop and go	2.0%/9.5%	7.2K
	highway	8.6%/33.8%	14K word

[0067] As shown in the above table, error rate increases as noise increases Search space size also increases as noise increases.

[0068] Although there is no performance degradation from floating-point to fixed-point; larger model does provide better performance. We used a larger model for WAVES digits with 20 dimension MFCC (10 static, 10 dynamic), 1957 mean and 270 variance vectors were used. The total model size is 59K words. Unlike the smaller models above, it cannot fit into the C5410 on-chip memory.

[0069]

	WER/SER	search space
	parked	0.6%/2.4%	2.4K word
	stop and go	1.2%/6.3%	5.3K word
	highway	5.1%/21.9%	9.7K word

[0070] As shown in the above table, larger model provides better performance. The search space also decreases because larger model is more accurate and thus results in better discrimination between confusing paths.

[0071] Most of the computation is consumed by search routine. Search time, like search space size, varies a lot depending on many factors: grammar perplexity, noise level, and model size, etc. We profile the MIPS consumed by various parts of the algorithm using two typical utterances: a very clean TI digit utterance and a very noisy WAVES hands-free, highway digit utterance. The cycle counts are done on a 100 MHz 5410 DSP chip, both program and data reside on zero-wait-state on-chip RAM.

[0072] The TI digit utterance is 1.36 seconds long; it takes 39 million cycles to complete the recognition. That amounts to 39/100/1.36=0.29 real time. We did not profile any further for this utterance because it is already much faster than real time.

[0073] The WAVES digit utterance is 1.66 seconds long; it takes 177 million cycles to complete the recognition. That amounts to 177/100/1.66=1.07 real time. The 177 million cycles are distributed among various parts of the algorithm:

[0074]

	Algorithm	cycles (in million)
	MFCC	21
	PMC	41
	Utterance detection	15.7
	Gaussian score	11.5
	Search and memory management	87.8

[0075] The time consumed by MFCC and utterance detection is relatively constant per frame of speech; it increases proportional to the length of the utterance. The time consumed by PMC is proportional to the model size. The time consumed by search and Gaussian score computation (incurred by search) varies a lot.

[0076] It is very difficult to quote the exact MIPS needed by a recognition algorithm because it varies a lot. From our analysis above, a 100 MHz 5410 can recognize a relatively clean utterance much faster than real time. The very noisy utterance can also be recognized very close to real time. A small buffer of MFCC is needed to buffer up frames whenever the computation falls behind real time. For a system with 8 dimension MFCC, 20 ms frame; a (8*50=400) words buffer can buffer 1 second of speech.

[0077] We only report continuous digits task because it is the most difficult small vocabulary task. For command phrase and speaker-dependent tasks, the number will be much better, i.e. lower error rate, smaller search space, and less MIPS.

[0078] We have shown that fixed-point implementation incurs no performance degradation on a speech recognition algorithm. This is validated on a very challenging, hands-free, highway, zero dB SNR corpus. This algorithm has been implemented on a low cost 16-bit, fixed-point DSP using only on-chip RAM.

[0079] All the number reported above are from C-compiled code, with no assembly code optimization. As shown in the tables, the search space is still quite small for the most difficult condition. We can afford to increase the search beam to improve performance depending on system configuration. There are also different allocations of mean and variance sizes that may provide better size vs. accuracy trade-off. Assembly optimization can be easily added to the MFCC algorithm to cut down on program size and MIPS.