Abstract:
The sampling rate of a digital signal is reduced by storing a series of partial sums of the digital signal instead of the signal itself, thus reducing the memory size required to perform the sampling-rate reduction.

Description:
TECHNICAL FIELD 
       [0001]    Embodiments of the current invention related to digital-signal processing and, in particular, to anti-aliasing filters. 
       BACKGROUND 
       [0002]    Analog audio or image signals are converted to digital form by “sampling,” i.e., repeatedly measuring the signal amplitude over time or over the image; the set of samples thus obtained constitutes a digital approximation of the initial signal and can be used to reproduce the signal. Decimation, or “downsampling,” is an operation in digital-signal or -image processing in which a set of samples is reduced in size. For example, a set of 100 samples may be decimated by a factor of two by selecting 50 samples that best represent the analog signal defined by the original 100 samples. The selection may be made by simply selecting every odd (or even) sample or, in more sophisticated operations, by replacing every pair of original samples with their average. 
         [0003]    Because decimation reduces the effective sampling rate of the signal, however, care must be taken that the new sampling rate is at least twice the frequency of any components of interest within the original signal (the so-called Nyquist frequency). If the original signal included components with frequencies above the Nyquist frequency, they will be “aliased” and corrupt the components of interest in the sample set. An anti-aliasing filter may be used to remove these high-frequency components; in decimation operations, an averaging filter is commonly used as an anti-aliasing filter. An averaging filter outputs a pointy at a location n (i.e., the nth point y), given an input set of points x, by averaging N input points x for each output pointy. This operation is expressed formally in Equation (1) 
         [0000]    
       
         
           
             
               
                 
                   
                     y 
                     n 
                   
                   = 
                   
                     
                       1 
                       N 
                     
                      
                     
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             n 
                           
                         
                         
                           n 
                           + 
                           N 
                           - 
                           1 
                         
                       
                        
                       
                         x 
                         k 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0004]    For example, if 10 input points x are averaged for each output pointy (N=10), then y 0  is the average of x 0  through x 9 , y 1  is the average of x 1  through x 10 , y 2  is the average of x 2  through x 11 , and so on. The sum needed for each new average may be computed by taking the value of the sum in the last average, subtracting the value of the “oldest” sample, and adding the value of the “newest” sample. For example, to compute the average of x 1  through x 10 , the value of x 0  is subtracted from the sum of x 0  through x 9  (which is already computed for the previous average), and the value of x 10  is added. More formally, the sum of input points x from x n  to x m  is given below in Equation (2). 
         [0000]    
       
         
           
             
               
                 
                   
                     S 
                     
                       n 
                       , 
                       m 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         k 
                         = 
                         n 
                       
                       m 
                     
                      
                     
                       x 
                       k 
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    The value of a “next” sum is therefore defined by Equation (3), 
         [0000]        S   (n+1),(m+1)   =S   n,m   −x   n   +x   (m+1)    (3)
 
         [0000]    in which the distance between n and m is defined by N, and thus m=n+(N−1). For the sake of illustration, Equation (3) becomes, using the example above, the expression shown below in Equation (4). 
         [0000]        S   1,10   =S   0,9   −x   0   +x   10    (4)
 
         [0000]    In general, Equation (1) may be re-written as an average of computed sums, as shown below in Equation (5). 
         [0000]    
       
         
           
             
               
                 
                   
                     y 
                     n 
                   
                   = 
                   
                     
                       1 
                       N 
                     
                      
                     
                       S 
                       
                         n 
                         , 
                         m 
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0005]    While this approach is attractive because it requires only one additional addition and subtraction operation per sample, it requires that the N−1 previous samples be stored in memory (because, at each new sample, the process must know the value of the “oldest” sample in order to subtract it). This memory requirement becomes even more severe in the case of operations such as raster-order image streaming, which requires the storage of N−1 previous lines of samples. The memory required for such storage may exceed the local storage space available to a processor, requiring the use of slower, system memory. In the worst case, the fetching and retrieval from system memory is too slow to keep up with the incoming data rate, and the filtering process fails. A need therefore exists for a decimation operation that has a lower memory requirement. 
       SUMMARY 
       [0006]    In general, various aspects of the systems and methods described herein reduce the amount of required memory required for downsampling a stream of digital samples. History information about prior input samples is required to compute later output points, but the present invention saves as few as one carefully selected input data point and one partial sum of prior input samples (instead of an entire history of prior input samples). Using only this reduced set of history information, the present invention computes values for downsampled output data in accordance with a selected decimation rate and filter size. 
         [0007]    In one aspect, a method for computationally downsampling digital samples of a signal includes computing a first sum S n,m  of a first set of N digital samples x n  . . . x m . The first sum S n,m  comprises a partial sum S (m−p),m , N&gt;1, m=n+N, and p&lt;N. The partial sum S (m−p),m  is stored in a hardware register. A second sum S (m−p),(m−p+N)  of a second set of N digital samples x (m−p)  . . . x (m−p−N)  is computed by adding the partial sum S (m−p),m  to a sum of N−p digital samples x m  . . . x (m−p+N) ; the first and second sets of digital samples overlap to include some samples in common. The digital samples are decimated based at least in part on the first sum S n,m  and the second sum S (m−p),(m−p+N) . 
         [0008]    The digital sample x n  may be stored in a hardware register. A third sum S (n+1),(m+1)  may be computed by subtracting x n  from the first sum S n,m  and by adding another digital sample x (m+1) . N may be 16 and the digital samples may be decimated by a factor of 10.3. The digital samples may correspond to a one- or two-dimensional signal; the two-dimensional signal may correspond to raster-scan image data; partial sums may be stored corresponding to a row of input data. 
         [0009]    In another aspect, a system for downsampling digital samples includes an averaging filter having N taps (where N&gt;1). A first memory stores a first digital sample, and a second memory stores a partial sum of two or more digital samples. The averaging filter computes an average of N digital samples using the stored digital sample and the stored partial sum. 
         [0010]    An interpolator may used for interpolating between outputs of the averaging filter. The digital samples may correspond to a one- or two-dimensional signal. The two-dimensional signal may correspond to raster-scan image data; partial sums may be stored corresponding to a row of input data. 
         [0011]    These and other objects, along with advantages and features of the present invention herein disclosed, will become more apparent through reference to the following description, the accompanying drawings, and the claims. Furthermore, it is to be understood that the features of the various embodiments described herein are not mutually exclusive and can exist in various combinations and permutations. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]    In the drawings, like reference characters generally refer to the same parts throughout the different views. In the following description, various embodiments of the present invention are described with reference to the following drawings, in which: 
           [0013]      FIG. 1  is a flowchart for downsampling a stream of digital data in accordance with an embodiment of the invention; 
           [0014]      FIG. 2  is a representation of downsampling a stream of digital data in accordance with an embodiment of the invention; 
           [0015]      FIG. 3  is another representation of downsampling a stream of digital data in accordance with an embodiment of the invention; 
           [0016]      FIG. 4  is an illustrative example of downsampling a stream of digital data in accordance with an embodiment of the invention; and 
           [0017]      FIG. 5  is a system for downsampling a stream of digital data in accordance with an embodiment of the invention; 
       
    
    
     DETAILED DESCRIPTION 
       [0018]    A method  100  for downsampling digital samples, in accordance with embodiments of the present invention, appears in  FIG. 1 . In a first step  102 , a first set of digital samples is received and the sum of the samples is computed. As explained in greater detail below, this sum is used to compute the average of these samples (by, e.g., an averaging filter) and the result is one of the set of decimated output points. The number of samples used to compute each sum (and later, to compute each average), N, may correspond to the size (i.e., number of “taps”) of the averaging filter (and may thus remain constant throughout the downsampling operation  100 ). As one of skill in the art will understand, the current invention is not limited to any particular filter size/tap number N. 
         [0019]    In a second step  104 , a part of the computed sum is stored in a hardware register. Further information about the digital samples (i.e., their values) need not be saved or retained, thus reducing the memory requirements of the downsampling operation  100 . In other words, the method  100  saves partial sums of samples instead of the samples themselves. 
         [0020]    In a third step  106 , a second sum of a second set of digital samples is computed. The first and second sets of digital samples “overlap”—that is, share some samples in common—and the partial sum of the first set of samples saved in step  104  corresponds to this overlapping section. Instead of saving the first set of samples and re-computing the sum of the overlapping section, the method  100  saves the partial sum and adds it to the new, non-overlapping section of the second set of samples. 
         [0021]    In a fourth step  108 , the input digital samples are decimated using the first and second sums. As explained in greater detail below, the first and second sums may be just two of a great many sums computed. The number of samples included in each sum, which samples are included in which sums, and the number of sums are all design parameters that depend on the decimation ratio, the filter size N, and/or other design parameters. 
         [0022]    A graphical representation  200  of one embodiment of the method  100  is shown in  FIG. 2 . An incoming stream of digital samples  202  begins with a first sample x n  and includes, N samples later, a second sample x m  (i.e., m=n+N−1). The first sum  204  of the first set of N samples x n  . . . x m  is S n,m ; a second sum  206  of a second set of N samples overlaps the first sum  204  by p samples in an overlapping region  208 . The beginning of the overlapping region is thus p samples less than the end x m  of the first sum  204  and may be represented by x (m−p) . The second sum  206  may thus be represented by S (m−p),(m−p+N) , and the partial sum of the overlapping region  208  is S (m−p),m . 
         [0023]    At a first time  210 , at the beginning of the digital samples  202 , the samples  202  are added to the first sum S n,m    204  (and may be discarded after said addition). At a second, later time  212 , the overlapping region  208  is reached. At this point, the partial sum S (m−p),m    208  is computed and saved separately from the first sum S n,m    204 . The entire first sum S n,m    204  may be saved or only the non-overlapping part of it (i.e., S n,(m−p−1) ) may be saved; the invention is not limited to any particular type of storage. 
         [0024]    At a still later time  214 , no further samples are required for the first sum  204 . The partial sum  208  is added to the second sum  206 , and additional samples  202  are added as necessary to the second sum  206 . As  FIG. 2  illustrates, the N samples of the first sum  204  are not needed to compute the second sum  206 ; only the partial sum  208  need be stored. The process continues with a third sum S (n+2N),(m−2N)    216  having an overlapping region S (m+N−p),(m+N)    218 , and additional sums and additional overlapping regions are computed in a similar manner. 
         [0025]    The three sums  204 ,  206 ,  216  may be used to compute three output points y 1 , y 2 , y 3  by dividing each of the sums  204 ,  206 ,  216  by N. In this very simple example, the decimation factor is given by the frequency of the computation of the sums; if, for example, a new sum is computed for every ten input samples, the decimation factor is ten. 
         [0026]    A more sophisticated decimation scheme  300  is depicted in  FIG. 3 . In addition to the first  204 , second  206 , and third  216  sums described above with reference to  FIG. 2 , the scheme  300  takes additional sums  302 ,  304 , and  306 . Each pair of sums (the first sum  204  and the first additional sum  302 ; the second sum  206  and the second additional sum  304 ; and the third sum  216  and the third additional sum  206 ) is bilinerally interpolated to produce each output point y 1 , y 2 , y 3 . 
         [0027]    Each additional sum  302 ,  304 ,  306  has the same number of samples (i.e., N) as the first  204 , second  206 , and third  216  sums, but is shifted by one sample (i.e., the first additional sum  302  is S (n+1),(m+1) , the second additional sum  304  is S (n+N+1),(m+N+1) , and the third additional sum  306  is S (n+2),(m+2) ). Each additional sum  302 ,  304 ,  306  may therefore be derived from the first  204 , second  206 , and third  216  sums by subtracting out the first sample (e.g., x n ) and adding in the next sample (e.g., x n+N ). This first sample may be stored for each additional sum  302 ,  304 ,  306  (along with the partial sums  208 ,  218 ) so that it is available. 
         [0028]    If a decimation scheme requires higher-order (e.g., third-order) interpolation, additional sums may be taken and additional input data samples may be stored to compute those sums. For example, the above method describes interpolating between two sums, S n,m  and S (n+1),(m+1) , which in one embodiment stores the input sample x n . If a third-order interpolation is desired, a third sum S (n+2),(m+2) , may be computed by additionally storing x (n+1) . Similarly, if bilinear interpolation is used, but the additional sum is shifted by two or more samples, additional samples may be stored to compute the second sum. For example, if the first sum is S n,m  and the second sum is S (n+2),(m+2) , both x n  and x (n+1)  (or their sum) may be stored. 
         [0029]    An illustrative example  400  of one embodiment of the invention is shown in  FIG. 4 . In this example, the averaging filter has sixteen taps, so N=16. The decimation factor is 10.3, meaning that for every  103  input samples x, 10 output samples y are produced. The method uses bilinear interpolation of sums produced by the averaging filter to calculate the output samples y. For example, filter outputs y 0  and y 1  are interpolated to make a first final output point, y 10  and y 11  are interpolated to make a second, y 20  and y 21  a third, y 30  and y 31  a fourth, and y 41  and y 42  a fifth (note that the coordinates of the fifth output point (41 and 42) are shifted by one, with respect to the trend in the rest of the output points (0, 10, 20, 30, etc.) to account for the “0.3” part of the “10.3 decimation factor). Each output y of the averaging filter is based on an average of sixteen input points (because N=16). The filter outputs y 0 , y 10 , y 20 , y 30 , and y 41  are given below by Equations (6)-(10). 
         [0000]    
       
         
           
             
               
                 
                   
                     y 
                     0 
                   
                   = 
                   
                     
                       1 
                       N 
                     
                      
                     
                       S 
                       
                         0 
                         , 
                         15 
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
             
               
                 
                   
                     y 
                     10 
                   
                   = 
                   
                     
                       1 
                       N 
                     
                      
                     
                       S 
                       
                         10 
                         , 
                         25 
                       
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
             
               
                 
                   
                     y 
                     20 
                   
                   = 
                   
                     
                       1 
                       N 
                     
                      
                     
                       S 
                       
                         20 
                         , 
                         35 
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
             
               
                 
                   
                     y 
                     30 
                   
                   = 
                   
                     
                       1 
                       N 
                     
                      
                     
                       S 
                       
                         30 
                         , 
                         45 
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
             
               
                 
                   
                     y 
                     41 
                   
                   = 
                   
                     
                       1 
                       N 
                     
                      
                     
                       S 
                       
                         41 
                         , 
                         56 
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
         [0030]    The sums appearing in Equations (6)-(10) may be found in accordance with Equations (11)-(15), which highlight the partial sums re-used in each sum. For example, the partial product S 10,15  appears in Equations (11) and (12), the partial product S 20,25  appears in Equations (12) and (13), the partial product S 30,35  appears in Equations (13) and (14), and the partial product S 41,45  appears in Equations (14) and (15). 
         [0000]        S   0,15   =S   0,9   +S   10,15    (11)
 
         [0000]        S   10,25   =S   10,15   +S   16,19   +S   20,25    (12)
 
         [0000]        S   20,35   =S   20,25   +S   26,29   +S   30,35    (13)
 
         [0000]        S   30,45   =S   30,35   +S   36,40   +S   41,45    (14)
 
         [0000]        S   41,56   =S   41,45   +S   46,50   +S   51,56    (15)
 
         [0000]    And as described above, the rest of the sums S 1,16 , S 11,26 , S 21,36 , S 31,46 , and S 42,57  may be found by subtracting out the “oldest” sample from the corresponding above sums and adding in the next sample, as given below in Equations (16)-(20) 
         [0000]        S   1,16   =S   0,15   −x   0   +x   16    (16)
 
         [0000]        S   11,26   =S   10,25   −x   10   +x   26    (17)
 
         [0000]        S   21,36   =S   20,35   −x   20   +x   36    (18)
 
         [0000]        S   31,46   =S   30,45   −x   30   +x   46    (19)
 
         [0000]        S   42,57   =S   41,56   −x   41   +x   57    (20)
 
         [0000]    Thus, for each new sum, only the previous partial sum (e.g., S 1,16 , S 11,26 , S 21,36 , S 31,46 , and S 42,57 ) and the previous “oldest” sample (e.g., x 0 , x 10 , x 20 , x 30 , and x 41 ) is stored. 
         [0031]    The above discussion contemplates a one-dimensional stream of input data samples, such as samples corresponding to an audio signal. The digital samples may, however, correspond to a two-dimensional digital image or video stream (received in, for example, raster order). In this case, instead of saving a single partial sum, a number of partial sums corresponding to one line of the image/video is stored. In addition, instead of storing a single “oldest” point, a number of points corresponding to an oldest line of the image/video is stored. As one of skill in the art will understand, embodiments of the current invention may be applied to input data having higher-order dimensions (e.g., third dimension or greater); in each case, the intermediate-sum storage has a dimension one less than that of the input data. For example, one-dimensional input data may use an intermediate sample, two-dimensional input data uses am intermediate one-dimensional array of values, three-dimensional input data uses an intermediate two-dimensional array, and so on. 
         [0032]    In one embodiment, the number of taps N of the averaging filter is selected to comply with the desired decimation ratio. If, for example, the number of taps N increases to approximately two times the decimation rate, the partial sums may overlap/intersect. With reference to  FIG. 2 , this effect occurs when the distance  220  falls to zero. As one of skill in the art will realize, however, increasing N to this point may be unnecessary because the minimum size of N (as required by the Nyquist) frequency) is less than two times the decimation rate. 
         [0033]    A system  500  for downsampling signals is shown in  FIG. 5 . An incoming stream of data  502 , having a high sample rate, is received by an averaging filter  504 . The filter  504  provides a series of averaged filter outputs  506  to an interpolator  508 ; the interpolator  508 , in turn, interpolates between two or more filter outputs  506  to provide a final output  510 . A first memory  512  stores one or more “oldest” sample points that may be used to compute sums derived from already-computed sums. A second memory  512  stores partial sums for use in computing sums of the input data  502 . In various embodiments, the filter  504  and the interpolator  508  may be digital-logic devices implemented with, for example CMOS transistors, and may be custom-tailored devices, part of an ASIC design, or software modules implemented on a conventional processor (such as a digital-signal processor) programmed to carry out the operations described above. The memories  510 ,  512  may be any kind of volatile or non-volatile storage media, such as random-access memory, a register file, or custom registers. One of skill in the art will understand that the present invention is not limited to the particular combination of components in  FIG. 5 , and that the components may be combined or further split apart without deviating from the intent of the invention. The memories  510 ,  512 , for example, may be combined. 
         [0034]    It should also be noted that embodiments of the present invention may be provided as one or more computer-readable programs embodied on or in one or more articles of manufacture. The article of manufacture may be any suitable hardware apparatus, such as, for example, a floppy disk, a hard disk, a CD ROM, a CD-RW, a CD-R, a DVD ROM, a DVD-RW, a DVD-R, a flash memory card, a PROM, a RAM, a ROM, or a magnetic tape. In general, the computer-readable programs may be implemented in any programming language. Some examples of languages that may be used include C, C++, or JAVA. The software programs may be further translated into machine language or virtual machine instructions and stored in a program file in that form. The program file may then be stored on or in one or more of the articles of manufacture. 
         [0035]    Certain embodiments of the present invention were described above. It is, however, expressly noted that the present invention is not limited to those embodiments, but rather the intention is that additions and modifications to what was expressly described herein are also included within the scope of the invention. Moreover, it is to be understood that the features of the various embodiments described herein were not mutually exclusive and can exist in various combinations and permutations, even if such combinations or permutations were not made express herein, without departing from the spirit and scope of the invention. In fact, variations, modifications, and other implementations of what was described herein will occur to those of ordinary skill in the art without departing from the spirit and the scope of the invention. As such, the invention is not to be defined only by the preceding illustrative description.