Abstract:
A method and apparatus to accelerate the evaluation of complex, computationally intense digital signal processing algorithms is disclosed. In one embodiment, a filter accelerator is connected in parallel with a conventional digital signal processor (DSP). The accelerator enhances the speed at which the DSP performs some filtering operations by calculating and maintaining a number of partial results based on a selected number of prior data samples. Each time the DSP receives a new data sample for filtering, the DSP makes use of one or more partial results from the accelerator to speed the calculation of the filtered result. Receipt of the new data sample causes the accelerator to recalculate the partial results, this time using the new data sample. The accelerator thus prepares for receipt of the subsequent data sample, freeing the DSP to perform other operations.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of co-pending, commonly owned provisional U.S. patent application Ser. No. 60/132,975, invented by Bernard J. New and filed May 7, 1999, which is incorporated herein by reference. 
    
    
     FIELD OF THE INVENTION 
     This invention relates generally to methods and apparatus for accelerating complex, processor-intensive signal-processing algorithms, in particular algorithms in which the evaluation depends upon a single final data point. 
     BACKGROUND 
     Some complex signal processing algorithms depend upon a single final data point to produce a processed result. One such algorithm is the finite-impulse-response (FIR) filter, which is commonly found among the algorithms evaluated by a digital signal processor (DSP). 
     FIG. 1 is a flowchart  10  of a direct form of a conventional FIR filter. A series of N input data samples is shifted into shift registers  11   1  through  11   N . Thus, register  11   1  contains a current data sample D N  and registers  11   2  through  11   N  contain a set of previous data samples D 4 , D 3 , D 2 , and D 1 . 
     Registers  11   1  through  11   N  present their corresponding data samples D 1  through D N  on like-named register output lines. Data samples D 1  through D N  are then multiplied in a set of multiply steps  12   1  through  12   N  by a respective set of weighting coefficients C 1  through C N . Finally, an adder  13  sums the resulting weighted samples to provide a filtered output sample D F , where D F =D 1 C 1 +D 2 C 2  . . . +D N C N . Output sample D F  is then loaded into an output register  14 . 
     FIG. 2 depicts a typical hardware implementation  20  of the flowchart of FIG. 1, like-numbered elements being the same in both Figures. For ease of illustration, FIG. 2 illustrates a four-tap filter employing weighting coefficients C 1 -C 4 . The depicted example is limited to five input samples D 1 -D 5 , sample D 5  being the newest and sample D 1  being the eldest. A register  11 , including five individual registers  11   1  through  11   5 , connects to a multiplier  22  via a multiplexer  24 . A register block  26  stores weighting coefficients C 1  through C 4  in a series of registers  26   1  through  26   4  and presents the coefficients to multiplier  22  via a second multiplexer  28 . 
     As depicted below in Table 1, the example begins with the first (eldest) data sample D 1  stored in register  11   5 , the second data sample D 2  stored in register  11   2 , the third data sample D 3  stored in register  11   3 , and the fourth and most recent data sample D 4  stored in registers  11   1  and  11   4 . A new data sample D 5  is then received and latched into input register  11   1  during the first machine cycle (Cycle 1). Multiplexers  24  and  28  then provide the respective contents of registers  11   1  and  26   1  (i.e., D 5  and C 1 ) to multiplier  22 . Multiplier  22  outputs the product D 5 C 1  to an adder  25 , which stores the product D 5 C 1  in an accumulation register  29 . 
     
       
         
               
               
               
               
               
               
               
             
           
               
                   
                 TABLE 1 
               
               
                   
                   
               
               
                   
                 Register 
                 Start 
                 Cycle 1 
                 Cycle 2 
                 Cycle 3 
                 Cycle 4 
               
               
                   
                   
               
             
             
               
                   
                 11 1   
                 D 4   
                 D 5   
                 D 5   
                 D 5   
                 D 5   
               
               
                   
                 11 2   
                 D 2   
                 D 2   
                 D 5   
                 D 4   
                 D 3   
               
               
                   
                 11 3   
                 D 3   
                 D 3   
                 D 2   
                 D 5   
                 D 4   
               
               
                   
                 11 4   
                 D 4   
                 D 4   
                 D 3   
                 D 2   
                 D 5   
               
               
                   
                 11 5   
                 D 1   
                 D 1   
                 D 4   
                 D 3   
                 D 2   
               
               
                   
                   
               
             
          
         
       
     
     Registers  11   2  to  11   5  operate as shift registers. Data sample D 1  is shifted into register  11   2  during the time that data sample D 1  is presented to multiplier  22 . Thus, for the second machine cycle (Cycle 2), each data sample in shift register  11  is similarly shifted, so that data sample D 1  is replaced with data sample D 4 , data sample D 4  is replaced with data sample D 3 , data sample D 3  is replaced with data sample D 2 , and data sample D 2  is replaced with data sample D 5  (see Table 1). 
     Multiplexer  24  selects the D output D OUT  of register  11  while multiplexer  28  selects coefficient C 2  following the foregoing multiply and shift sequence. Multiplier  22  thus supplies the product D 4 C 2  to adder  25 , which sums the product D 4 C 2  with the product D 5 C 1  already in accumulation register  29  and stores the sum (i.e., D 4 C 2 +D 5 C 1 ) in accumulation register  29 . As with data sample D 5  data sample D 4  is shifted into register  11   2  while data sample D 4  is presented to multiplier  22 . Each remaining register  11   3 - 11   5  is similarly updated, so that the contents of registers  11   1 - 11   5  are as depicted above for cycle three of Table 1. 
     The foregoing multiply, accumulate, and shift process continues until each data/coefficient pair is presented to multiplier  22  and the resulting products are summed in accumulation register  29  and then stored in an output register  14 . Upon completing of the filtering of data sample D 5 , the contents of registers  11   1 - 11   5  are as depicted above for cycle four of Table 1. The filter is then prepared to receive the next data sample D 6 . 
     Filter implementation  20  requires N clock cycles to filter each data sample, or one clock cycle for each multiply-accumulate operation performed by multiplier  22  and adder  25 . Since many DSP optimized microprocessors can produce the same result in N clock cycles, such an embodiment cannot be used to accelerate the microprocessor. 
     Some conventional systems employ multiple multiplier/adder pairs operating in parallel to reduce the requisite number of clock cycles and therefore improve speed performance. Unfortunately, such parallel systems are larger, more expensive, and require more power than their sequential counterparts. There is therefore a need for a means of reducing the time required to complete the evaluation of the FIR-filter algorithm without incurring significant increases in power usage, size, and cost. 
     SUMMARY 
     The present invention is directed to methods and apparatus for accelerating complex signal-processing tasks, such as FIR filtering. In one embodiment, an FIR-filter accelerator is connected in parallel with a data path in a conventional DSP. The accelerator calculates and maintains a number of partial results based on a selected number of prior data samples. Each time the DSP receives a new data sample for filtering, the DSP makes use of one or more partial results from the accelerator to speed the calculation of the filtered result. The accelerator then recalculates the partial results using the new data sample in preparation for a subsequent data sample. 
     The filter accelerator can improve the performance of the DSP even if the accelerator hardware operates at a rate slower than that of the DSP. The accelerator can therefore be produced inexpensively by exploiting proven, mass-produced, economical technologies and materials. Moreover, the accelerator can be made relatively small, as the accelerator does not require massively parallel processing means. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a flowchart  10  of a direct form of a conventional FIR filter. 
     FIG. 2 depicts a typical hardware implementation  20  of the flow chart of FIG.  1 . 
     FIGS. 3A-3I are flowcharts depicting the operation of a three-tap FIR filter accelerator in accordance with an embodiment of the invention. 
     FIG. 4 is a block diagram of an accelerator  41  in accordance with the invention. 
     FIG. 5 is a flowchart  50  depicting the operation of a FIR filter accelerator in accordance with the present invention. 
     FIG. 6 is a block diagram of a datapath  60  connected to accelerator  41  of FIG.  4 . 
     FIGS. 7A-7I are flowcharts depicting the operation of a three-tap FIR filter accelerator in accordance with another embodiment of the invention. 
    
    
     DETAILED DESCRIPTION 
     FIGS. 3A-3I are flowcharts depicting the operation of a three-tap FIR filter accelerator in accordance with an embodiment of the invention. The subscript of a given data sample D N  indicates the relative age of the data sample, the lower the subscript number the older the sample. The filter accelerator conventionally produces a filtered data sample D F  by multiplying three consecutive data samples by three respective weighting coefficients C 1 , C 2 , and C 3 . As described below, the filter accelerator presents filtered data D F  in just one clock cycle using a single multiplier, providing speed performance without the disadvantages of parallel processing solutions. 
     Each flowchart in FIGS. 3A-3I depicts the operation of the filter accelerator during a single clock cycle. Referring first to FIG. 3A, a first input data sample D 1  is stored in a data input register  31 . Register  31  presents data sample D 1  to a weighting-coefficient multiplier  32 . Weighting-coefficient multiplier  32  is a single multiplier depicted as including three separate multipliers  32   1  through  32   3  to illustrate that multiplier  32  performs three separate multiplications—one per clock cycle—for each input data sample. Multipliers  32   3 ,  32   2 , and  32   1  respectively symbolize the first, second, and third multiplications. 
     During the first clock cycle, multiplier  32  multiplies data sample D 1  by a weighting coefficient C 3  using multiplier  32   3 . (In each of FIGS. 3A-3I, the active multiplication is highlighted using a multiplier symbol having a solid boundary, whereas the inactive multiplications are contrasted using multiplier symbols with broken boundaries.) Multiplier  32   3  provides a data-sample product D 1 C 3  to an adder  33   1 . This adder adds data-sample product D 3 C 3  with the contents of a register  34   2  and stores the filtered result D F  in sum-of-products register  34   1 , the output register of the filter accelerator. The depicted accelerator has three taps, and so when started requires three data samples before producing the first filtered output. Data sample D 1  is assumed to be the first data sample, so the filtered output D F  is incomplete. 
     During the second clock cycle (FIG.  3 B), multiplier  32  multiplies data sample D 1  by a second weighting coefficient C 2 , sums this product D 1 C 2  with the contents of a register  34   3 , and stores the result in a register  34   2 . Register  34   3  is thus far empty, so register  34   2  stores the product D 1 C 2 . In the third clock cycle (FIG.  3 C), multiplier  32  multiplies data sample D 1  by a third weighting coefficient C 1  and stores the resulting product D 1 C 1  in register  34   3 . 
     FIGS. 3D,  3 E, and  3 F illustrate the receipt and processing of a second input data sample D 2 . Multiplier  32  multiplies data D 2  by coefficient C 3  during the first clock cycle following the receipt of sample D 2 . Adder  33   1  adds the resulting data-sample product D 2 C 3  to the contents of register  34   2  obtained during the processing of the previous data sample D 1 . The resulting sum of products is stored as a filtered result D F  in register  34   1 . The filtered result is still incomplete, as a three-tap filter requires three input data samples upon which to base a result. 
     During the second clock cycle (FIG.  3 E), multiplier  32  multiplies data sample D 2  by coefficient C 2  and adder  33   2  adds the resulting product D 2 C 2  with the contents of a register  34   3 . A second sum-of-products register  34   2  captures the resulting sum of products (D 2 C 2 +D 1 C 1 ). In the third clock cycle (FIG.  3 F), register  34   3  captures the product of data sample D 2  and coefficient C 1 . 
     FIGS. 3G,  3 H, and  3 I illustrate the receipt of a third input data sample D 3 . The third data sample D 3  is the first for which the three-tap filter has enough data to produce a filtered result. During the first clock cycle after receipt of the third sample D 3 , multiplier  32  multiplies data sample D 3  by coefficient C 3 . Adder  33   1  adds the resulting data-sample product D 3 C 3  to the contents of register  34   2  (D 2 C 2 +D 1 C 1 ) obtained during the processing of the previous data samples D 1  and D 2 . The resulting sum of products is stored as a filtered result D F  in register  34   1 . Importantly, the filtered result D F =D 3 C 3 +D 2 C 2 +D 1 C 1  is the first correct filtered result after receiving data sample D 3 , and is available after only one clock cycle. As shown in FIGS. 3H and 3I, registers  34   2  and  34   3  are then updated using data sample D 3  during the second and third clock cycles in the manner described above in connection with FIGS. 3A-3F. The method of FIGS. 3A-3I produces a filtered result before the partial-results in registers  34   2  and  34   3  are updated. The steps illustrated in FIGS. 3G,  3 H, and  3 I are then repeated for each new data sample. 
     FIG. 4 is a block diagram of a DSP-optimized processor  40  connected to an FIR-filter accelerator  41  that performs the method of FIGS. 3A-3I to produce a filtered output D F  in a single clock cycle. Accelerator  41  is a hardware implementation of the flowcharts of FIGS. 3A-3I, like-numbered elements being the same. In addition to the registers depicted in FIGS. 3A-3I, accelerator  41  includes: 
     1. three coefficient shift registers  42   1  through  42   3 , which contain respective weighting coefficients C 1  through C 3 ; 
     2. a multiplier  44  that sequentially performs the multiplications represented as weighting-coefficient multipliers  32   1  through  32   3  in FIGS. 3A-3I; 
     3. an adder  46  (or ALU) that sequentially performs the summations represented by data-sample adders  33   1  and  33   2  in FIGS. 3A-3I; 
     4. a multiplexer  48  for selecting one or the other of the contents of partial-result registers  34   2  and  34   3 ; and 
     5. a de-multiplexer  49  for storing the output from adder  46  in a selected one of partial-result registers  34   2  and  34   3 . 
     Processor  40  presents each new input data sample D x  to multiplier  44  via input register  31 . Multiplier  44  then multiplies data sample D x  by each of the plurality of weighting coefficients C 1  through C 3 . This is accomplished sequentially by successively shifting weighting coefficients C 3  through C 1  through coefficient shift registers  42   3  through  42   1  to present each, in turn, to multiplier  44 . 
     As products are made available to adder  46 , adder  46 : 
     1. adds the first data-sample product, D x C 3 , to the output of partial-result register  34   2  and stores the result in output register  34   1 ; 
     2. adds the second data-sample product, D x C 2 , to the output of partial-result register  34   3  and stores the result in partial-result register  34   2 ; 
     3. directs the last data-sample product, D x C 1 , to partial-result register  34   3 ; and 
     4. pauses, awaiting the next input data sample D (x+1) . 
     Output register  34   1  contains filtered result D F  as soon as the foregoing step one is accomplished; steps two through four can then be accomplished during successive clock cycles while accelerator  41  awaits the next input data sample from processor  40 . Thus, processor  40  can retrieve the result and continue executing instructions with a minimum of delay. Further, this delay does not depend upon the number of input data samples used to calculate the filtered result. 
     FIG. 5 is a flowchart  50  depicting the operation of a filter accelerator in accordance with an embodiment of the invention. Flowchart  50  is similar to the flowcharts of FIGS. 3A-3I, like-numbered elements being the same; however, where the flowcharts of FIGS. 3A-3I represent a method that accommodates three consecutive input data samples, flowchart  50  represents a method that accommodates N consecutive input data samples. In every case, the filtered result is made available one clock cycle after the data sample of interest is latched into input register  31 . While there is no particular limit to the number of consecutive data samples used in the filter calculation, if the number is too great, the accelerator will not be able to update each partial-result register before receiving the next data sample. 
     FIG. 6 is a block diagram of a portion of a datapath  60  in a DSP-optimized processor connected to accelerator  41  of FIG.  4 . In this configuration, accelerator  41  speeds the operation of datapath  60  in implementing a four-tap FIR filter. 
     Datapath  60  includes a multiplier  61 , a pair of multiplexers  62  and  63 , an adder  66 , and an output register  68 . Multiplexers  62  and  63  route data and coefficients around multiplier  61  during processes that do not use accelerator  41 . 
     To make use of accelerator  41  to filter a sequence of data samples, datapath  60  routes each new input-data sample D 4  to multiplier  61  and to accelerator  41 . Multiplier  61  multiplies input-data sample D 4  by a weighting-coefficient C 4  and presents the resulting product, D 4 C 4 , to adder  66  via multiplexer  62 . Then, before output register  34   1  of accelerator  41  (now a partial-result register) is updated with new results based upon new input-data sample D 4 , adder  66  adds the contents of output register  34   1  (FIG. 4) to the output of multiplier  61 . The resulting sum (D 4 C 4 +D 3 C 3 +D 2 C 2 +D 1 C 1 ) is then shifted into output register  68  and presented at the output of datapath  60 . The partial results in registers  34   2  and  34   3  (FIGS. 3A-3I and  4 ) of accelerator  41  are then updated using data sample D 4 . Datapath  60  is free to perform some other useful work as accelerator  41  updates partial-result registers  34   2  and  34   3  in anticipation of a subsequent data sample. 
     The combination of datapath  60  and accelerator  41  provides filtered result D F  based on data samples D 1  through D 4  in the time required for multiplier  61  and adder  66  to perform a single multiply/accumulate operation. Datapath  60  is therefore able to produce a filtered result based on four data samples in a single machine cycle. Moreover, accelerator  41  can be extended to handle more than three input samples, as shown in FIG. 5, for example. 
     Because FIR accelerator  41  prepares partial results between data samples, speed and latency differences between datapath  60  and accelerator  41  are of little consequence; therefore, accelerator  41  can have a slower clock speed than datapath  60 , and consequently can be designed to minimize cost. The filter accelerator can improve the performance of the DSP even if the accelerator is slow relative to the DSP. Thus, accelerator  41  can be implemented in hardware or software using any number of technologies, including programmable logic devices and application-specific integrated circuits. Moreover, the reduced speed sensitivity of the accelerator allows the accelerator to be produced inexpensively by exploiting proven, mass-produced, economical technologies and materials. In another embodiment, accelerator  41  can be time-shared among multiple DSPs, thereby providing additional savings in size, cost, and complexity. 
     FIGS. 7A-7I are flowcharts depicting the operation of a filter accelerator in accordance with another embodiment of the invention. The depicted accelerator includes three taps for simplicity, but can be adapted for use with more or fewer taps. As in previous examples, the subscript of a given data sample D N  indicates the relative age of the data sample, the lower the subscript number the older the sample. The filter accelerator conventionally produces a filtered data sample D F  by multiplying three consecutive data samples by three respective weighting coefficients C 1 , C 2 , and C 3 . The filter accelerator presents filtered data D F  in just one clock cycle using a single multiplier. 
     Each flowchart in FIGS. 7A-7I depicts the operation of the filter accelerator during a single clock cycle. Referring first to FIG. 7A, a first input data sample D 1  is stored in a data input register  70 . Register  70  presents data sample D 1  to a weighting-coefficient multiplier  72 . Weighting-coefficient multiplier  72  is a single multiplier depicted as including three separate multipliers  72   1  through  72   3  to illustrate that multiplier  72  performs three separate multiplications—one per clock cycle—for each input data sample. Multipliers  72   1 ,  72   2 , and  72   3  respectively symbolize the first, second, and third multiplications. 
     During the first clock cycle, multiplier  72  multiplies data sample D 1  by a weighting coefficient C 3  using multiplier  72   1 . (In each of FIGS. 7A-7L, the active multiplication is highlighted using a multiplier symbol  72   X  having a solid boundary, whereas the inactive multiplications are contrasted using multiplier symbols  72   X  with broken boundaries.) Multiplier  72   1  provides a data-sample product D 1 C 3  to an adder  73   1 . This adder adds data-sample product D 1 C 3  with the contents of a partial-result register  74   2  and stores the filtered result D F  in sum-of-products register  74   1 , the output register of the filter accelerator. The depicted accelerator has three taps, and so when started requires three data samples before producing the first filtered output. Data sample D 1  is assumed to be the first data sample, so the filtered output D F  is incomplete. 
     During the second clock cycle (FIG.  7 B), multiplier  72  multiplies data sample D 1  by a second weighting coefficient C 2  and stores the product D 1 C 2  in a partial-result register  74   2 . In the third clock cycle (FIG.  7 C), multiplier  72  multiplies the contents of a data register  71  by a third weighting coefficient C 1 . In the example, data sample D 1  is the first data sample. Consequently, register  71  is empty before receipt of sample D 2 , the second data sample. The resulting product from multiplier  72   3  is therefore 0(C 1 ), or zero. An adder  73   2  adds this zero to the contents of register  74   2  and stores the resulting sum back in register  74   2 . The sum initially stored in register  74   2  is therefore D 1 C 2  +0(C 1 ), or D 1 C 2 . Adders  73   1  and  73   2  are depicted as separate for illustrative purposes, but can be implemented using a single adder. 
     FIGS. 7D,  7 E, and  7 F illustrate the receipt and processing of a second input data sample D 2 . The previous data sample D 1  shifts into register  71  as data sample D 2  shifts into register  70 . Multiplier  72   1  then multiplies data sample D 2  by coefficient C 3  during the first clock cycle following the receipt of sample D 2 . Adder  73   1  adds the resulting data-sample product D 2 C 3  to the contents of register  74   2  obtained during the processing of the previous data sample D 1 . The resulting sum of products is stored as a filtered result D F  in register  74   1 . The filtered result is still incomplete, as the three-tap filter requires three input data samples upon which to base a correct result. 
     During the second clock cycle (FIG.  7 E), multiplier  72   2  multiplies data sample D 2  by coefficient C 2 . Adder  73   2  stores the resulting product D 2 C 2  in partial-result register  74   2 . In the third clock cycle (FIG.  7 F), multiplier  72   3  multiplies data sample D 1  by coefficient C 1 , and adder  73   2  sums the resulting product D 1 C 1  with the product D 2 C 2  in partial-result register  74   2 . The resulting sum of products (D 1 C 1 +D 2 C 2 ) is stored in partial-result register  74   2 . 
     FIGS. 7G,  7 H, and  7 I illustrate the receipt of a third input data sample D 3 . The third data sample D 3  is the first for which the three-tap filter has enough data to produce a correct filtered result. During the first clock cycle after receipt of the third sample D 3 , multiplier  72   1  multiplies data sample D 3  by coefficient C 3 . Adder  73   1  adds the resulting data-sample product D 3 C 3  to the contents of register  74   2  (D 2 C 2  +D 1 C 1 ) obtained during the processing of the previous data samples D 1  and D 2 . The resulting sum of products is stored as a filtered result D F  in register  74   1 . Importantly, the filtered result D F =D 1 C 1 +D 2 C 2 +D 3 C 3  is the first correct filtered result produced from the input data samples, and is available after only one clock cycle from receipt of data sample D 3 . As shown in FIGS. 7H and 7I, register  74   2  is then updated using data samples D 2  and D 3  during the second and third clock cycles in the manner described above in connection with FIGS. 7A-7F. The method of FIGS. 7A-7I thus produces a filtered result before the partial-results in registers  74   2  and  74   3  are updated. The steps illustrated in FIG. 7G,  7 H, and  7 I are then repeated for each new data sample. 
     In typical filters, the receipt of a new data sample triggers the calculation of a filtered result. In contrast, each of the filters and filter accelerators in accordance with the invention begin calculating the filtered result of the next data sample before the next sample arrives. This advance preparation saves valuable processing time. 
     As mentioned previously, the accelerator depicted in FIGS. 7A-7I includes three taps for simplicity, but can be adapted for use with more or fewer taps. For example, each additional tap can employ an additional register connected in series with register  71  and a multiplier  72   N  connected between the output of the additional register and an input of adder  73   2 . 
     While the present invention has been described in connection with specific embodiments, variations of these embodiments will be obvious to those of ordinary skill in the art. For example, application of the invention is not limited to FIR filters, but may be extended for use with any signal-processing algorithm that depends upon a single final data point to produce a processed result. Therefore, the spirit and scope of the appended claims should not be limited to the foregoing description.