Fast calculation apparatus for carrying out a forward and an inverse transform

Abstract

In an apparatus for carrying out a linear transform calculation on a product signal produced by multiplying a predetermined transform window function and an apparatus input signal, an FFT part ( 23 ) carries out fast Fourier transform on a processed signal produced by processing the product signal in a first processing part ( 21 ). As a result, the FFT part produces an internal signal which is representative of a result of the fast Fourier transform. A second processing part ( 22 ) processes the internal signal into a transformed signal which represents a result of the linear transform calculation. The apparatus is applicable to either of forward and inverse transform units ( 11, 12 ).

1. An apparatus for carrying out a forward modified discrete cosine transform comprising:
 an input signal;  
 a multiplier, said multiplier multiplying a predetermined forward transform window function and said input signal and outputting as a result a product signal;  
 transform carrying out means connected to said multiplier for carrying out a linear forward modified discrete cosine transform on said product signal and for outputting a forward modified discrete cosine transformed signal representative of said linear forward modified discrete cosine transform, wherein said transform carrying out means further comprises:  
 a first processing device connected to receive said product signal from said multiplier, said first processing device outputting a processed signal;  
 means connected to said first processing device for receiving said processed signal and carrying out a forward fast Fourier transform on said processed signal and outputting an internal signal representative of said forward fast Fourier transform; and  
 a second processing device connected to receive said internal signal from said means for carrying out a forward fast Fourier transform, said second processing device processing said internal signal and outputting as a result said forward modified discrete cosine transformed signal.  
 
     
     
       2. An apparatus as recited in  claim 1 , wherein said product signal produced by said multiplier, is a succession of zeroth through (N/4−1)th and (N/4)th through (N−1)th product data, where N represents an integral multiple of four;
 said first processing device includes a particular processing means connected to said multiplier for processing said zeroth through said (N/4−1)th product data into a succession of (3N/4) through Nth particular data having a first polarity in common;  
 said first processing device further includes a specific processing means connected to said multiplier for processing said (N/4)th through said (N−1)th product data into a succession of zeroth through (3N/4−1)th specific data having a second polarity in common, said second polarity being different from said first polarity; and  
 a calculating means is connected to said particular processing means, said specific processing means, and said means for carrying out a forward fast Fourier transform, for calculating said processed signal by using a predetermined signal and each of said (3N/4) through said Nth particular and said zeroth through said (3N/4−1)th specific data.  
 
     
     
       3. An apparatus as recited in  claim 2 , wherein said predetermined signal represents exp(−2πjn/(2N)), and said calculating means multiplies said exp(−2πjn/(2N)) and each of said (3N/4) through said Nth particular data and said zeroth through the (3N/4−1)th specific data to produce said processed signal, where j represents an imaginary unit, n being variable between 0 and N−1, both inclusive. 
     
     
       4. An apparatus as recited in  claim 2 , wherein said calculating means comprises:
 combining means connected to said particular and said specific processing means for combining said particular and said specific data successions into a succession of zeroth through (N−1−2p)th and 2pth through (N−1)th combined data, where p is variable between 0 and N/2−1, both inclusive;  
 a subtractor connected to said combining means, said subtractor subtracting said (N−1−2p)th combined datum from said 2pth combined datum to produce a difference and output a local signal representative of said difference; and  
 internal multiplying means connected to said subtractor and said means for carrying out a forward fast Fourier transform, for multiplying a predetermined signal with said local signal into an internal product to make said processed signal represent said internal product.  
 
     
     
       5. An apparatus as recited in  claim 4 , wherein said predetermined signal represents exp(−2πjp/N), and said internal multiplying means multiples said exp(−2πjp/N) and said local signal to produce said processed signal, where j represents an imaginary unit, p being variable between 0 and N−1, both inclusive. 
     
     
       6. An apparatus as recited in  claim 1 , wherein said internal signal is a succession of zeroth through (K−1)th and kth through (N/2−1)th internal data, where N represents an integral multiple of four, k being variable between 0 and N−1, both inclusive, and wherein said second processing device includes internal multiplying means connected to said means for carrying out a forward fast Fourier transform, for multiplying said kth internal datum and exp(−2πj(k+½)/(2N)) into a local product to make said forward transformed signal represent said local product, where j represents an imaginary number. 
     
     
       7. An apparatus for carrying out an inverse modified discrete cosine transform comprising:
 an input signal comprising a modified discrete cosine transformed signal;  
 transform carrying out means for carrying out a linear inverse modified discrete cosine transform on said input signal and for outputting an inverse modified discrete cosine transformed signal representative of a result of said linear inverse modified discrete cosine transform;  
 a multiplier connected to said transform carrying out means, said multiplier multiplying a predetermined inverse transform window function and said inverse modified discrete cosine transformed signal to produce a product signal; wherein said transform carrying out means comprises:  
 a first processing device which receives said input signal and outputs a processed signal;  
 internal transform carrying out means connected to said first processing device for carrying out an inverse fast Fourier transform on said processed signal and for outputting as a result of said inverse fast Fourier transform an internal signal; and  
 a second processing device connected to said internal transform carrying out means to receive said internal signal and output as a result of processing said internal signal said inverse modified discrete cosine transformed signal.  
 
     
     
       8. An apparatus as recited in  claim 7 , said input signal being a succession of zeroth through (N−1)th apparatus input data, where N represents an integral multiple of four, wherein said first processing device includes a first multiplier, said multiplier multiplying said zeroth through said (N−1)th apparatus input data and exp(2π(N/4+½)k/N) and outputting as a result a first product, said processed signal representing said first product, where j represents an imaginary unit, k being variable between 0 and N−1, both inclusive. 
     
     
       9. An apparatus as recited in  claim 7 , said internal transform carrying out means producing, as said internal signal, a succession of zeroth through (N−1)th internal data, where N represents an integral multiple of four, wherein said second processing device includes a second multiplier connected to said internal transform carrying out means, said multiplier multiplying said zeroth through said (N−1)th internal data and exp(−2πj(n+N/4+½)/(2N)) into a second product, said inverse transformed signal representing said second product, where j represents an imaginary unit, n being variable between 0 and N−1, both inclusive. 
     
     
       10. An apparatus as recited in  claim 7 , wherein said input signal is a succession of zeroth through (N/2−1)th apparatus input data, where N represents an integral multiple of four;
 said first processing device includes a particular processing means for processing said 2kth apparatus input datum into a kth particular datum, where k is variable between 0 and N/2−1, both inclusive and a specific processing means for processing said (2k+1)th apparatus input datum into a (N−1−k)th specific datum; and  
 a calculating means connected to said particular and said specific processing means for calculating said processed signal by using a predetermined signal and each of said kth particular and said (N−1−k)th specific data.  
 
     
     
       11. An apparatus as recited in  claim 10 , wherein said predetermined signal represents exp(2πjk/N), where j represents an imaginary unit, and said calculating means multiplies said predetermined signal and said kth particular datum. 
     
     
       12. An apparatus as recited in  claim 7 , said internal transform carrying out means producing, as said internal signal, a succession of zeroth through (p−1)th and pth through (N/2−1)th internal data, where N represents an integral multiple of four, p being variable between 0 and (N/2−1), both inclusive, wherein said second processing device comprises:
 a multiplier connected to said internal transform carrying out means, said multiplier multiplying said pth internal datum and exp(2πj(p+½)/2N) resulting in a local product to make said inverse transformed signal represent said local product, j representing an imaginary unit, said local product being a succession of zeroth through (N/4−1)th and (N/4)th through (N/2−1)th product data;  
 a particular processing means connected to said multiplier for processing said zeroth through said (N/4−1)th product data into a first succession of (3/N4−1)  (   3 N/ 4 − 1   )th through (N/2)th particular data in a descending order and a second succession of (3N/4)th through Nth particular data in an ascending order, said particular data of said first and said second successions having a first polarity in common; and  
 a specific processing means connected to said multiplier for processing said (N/4)th through (N/2−1)th product data into a first succession of zeroth through (N/4−1)th specific data in an ascending order and a second succession of (N/2−1)th through (N/4)th specific data in a descending order, the specific data of said first and said second successions having a second polarity in common, said second polarity being different from said first polarity.  
 
     
     
       13. The apparatus of  claim 1  wherein said input signal is an audio signal. 
     
     
       14. The apparatus of  claim 1  wherein said modified discrete cosine transformed signal has a block length N of  512 . 
     
     
       15. The apparatus of  claim 1  wherein said transform carrying out means calculates fewer than N 2    multiplications.   
     
     
       16. The apparatus of  claim 1  wherein said transform carrying out means calculates fewer than N( N− 1   )  additions.   
     
     
       17. The apparatus of  claim 1  wherein said processed signal is formed by multiplying said input signal by a predetermined factor. 
     
     
       18. The apparatus of  claim 17  wherein said modified discrete cosine transformed signal comprises said internal signal representative of said forward fast Fourier transform multiplied by a second predetermined factor. 
     
     
       19. The apparatus of  claim 7  wherein said modified discrete cosine transformed signal is a transformed audio signal. 
     
     
       20. The apparatus of  claim 7  wherein said modified discrete transformed signal has a block length N of  512 . 
     
     
       21. The apparatus of  claim 7  wherein said transform carrying out means calculates fewer than N 2    multiplications to carry out said inverse discrete cosine transform.   
     
     
       22. The apparatus of  claim 21  wherein said transform carrying out means calculates fewer than N( N− 1   )  additions to carry out said inverse discrete cosine transform.   
     
     
       23. The apparatus of  claim 7  wherein said processed signal comprises said input signal multiplied by a predetermined factor. 
     
     
       24. The apparatus of  claim 23  wherein said inverse modified discrete cosine transform signal comprises said internal signal representative of said inverse forward fast Fourier transform multiplied by a second predetermined factor. 
     
     
       25. An apparatus for carrying out an inverse transform comprising:
   an input signal y ( m,k );      transform carrying out means for carrying out a linear inverse transform xt ( m,n )  on said input signal y ( m,k )  and for outputting an inverse transformed signal representative of a result of said linear inverse transform, said linear inverse transform being defined by:           xt   (     m   ,   n     )     =     2   ⁢     /     ⁢   N   ⁢       ∑     k   =   0       N   -   1       ⁢       y   ⁡     (     m   ,   k     )       ⁢     cos   [     2   ⁢     π   ⁡     (     n   +   n0     )       ⁢     (     k   +     1   ⁢     /     ⁢   2       )     ⁢     /     ⁢   N     ]                     where m represents a block number, n represents a sample number, N represents a block length and k is an integer between  0  and N− 1 ;        a multiplier connected to said transform carrying out means, said multiplier multiplying a predetermined inverse transform window function and said inverse transformed signal to produce a product signal; wherein said transform carrying out means comprises:        a first processing device which receives said input signal y ( m,k )  and outputs a processed signal, said processed signal comprising a product signal formed by multiplying said input signal y ( m,k )  by a predetermined factor;        internal transform carrying out means connected to said first processing device for carrying out an inverse fast Fourier transform on said processed signal and for outputting as a result of said inverse fast Fourier transform an internal signal; and        a second processing device connected to said internal transform carrying out means to receive said internal signal and output as a result of processing said internal signal said inverse transformed signal.     
     
     
       26. The apparatus of  claim 17  wherein N is  512 . 
     
     
       27. The apparatus of  claim 17  wherein said transform carrying out means calculates fewer than N 2    multiplications.   
     
     
       28. The apparatus of  claim 19  wherein said transform carrying out means calculates fewer than N( N− 1   )  additions.   
     
     
       29. An apparatus for carrying out an inverse transform comprising:
   a transformed discrete audio input signal having a block size  ( N )  of  512 ;        transform carrying out means for carrying out a linear inverse transform on said input signal by calculating fewer than N   2    multiplications and fewer than N ( N− 1   )  additions, and for outputting an inverse transformed signal representative of a result of said linear inverse transform;        a multiplier connected to said transform carrying out means, said multiplier multiplying a predetermined inverse transform window function and said inverse transformed signal to produce a product signal; wherein said transform carrying out means comprises:        a first processing device which receives said input signal and outputs a processed signal;        internal transform carrying out means connected to said first processing device for carrying out an inverse fast Fourier transform on said processed signal and for outputting as a result of said inverse fast Fourier transform an internal signal; and        a second processing device connected to said internal transform carrying out means to receive said internal signal and output as a result of processing said internal signal said inverse transformed signal.     
     
     
       30. An apparatus for carrying out a forward transform comprising:
   an input signal x ( n );      a multiplier for multiplying a predetermined forward transform window function and said input signal x ( n )  to produce a product signal to produce a product signal xh ( n );      transform carrying out means connected to said multiplier for carrying out a linear forward transform on said product signal xh ( n )  and for outputting a forward transformed signal y ( m,k )  representative of a result of said forward transform, said linear forward transform being defined by;           y   ⁡     (     m   ,   k     )       =       ∑     n   =   0       N   -   1       ⁢           ⁢       xh   ⁡     (   n   )       ⁢     cos   ⁢           [     2   ⁢     π   ⁡     (     k   +     1   ⁢     /     ⁢   2       )       ⁢     (     n   +     n   ⁢           ⁢   0       )     ⁢     /     ⁢   N     ]                   where m represents a block number, n represents a sample number, N represents a block length and k is an integer between  0  and N− 1 ;        wherein said transform carrying out means comprises:        a first processing device which receives said product signal xh ( n )  and outputs a processed signal, said processed signal comprising a product signal formed by multiplying said product signal xh ( n )  by a predetermined factor;        internal transform carrying out means connected to said first processing device for carrying out a forward fast Fourier transform on said processed signal and for outputting as a result of said forward fast Fourier transform an internal signal; and        a second processing device connected to said internal transform carrying out means to receive said internal signal and output as a result of processing said internal signal said forward transformed signal.     
     
     
       31. An apparatus for carrying out a forward transform comprising:
   an input signal having a block size  ( N )  of  512 ;        a multiplier for multiplying a predetermined forward transform window function and said input signal to produce a product signal; and        transform carrying out means connected to said multiplier for carrying out a linear forward transform on said product signal by calculating fewer than N   2    multiplications and fewer than N ( N− 1   )  additions, and for outputting a forward transformed signal representative of a result of said linear forward transform;        wherein said transform carrying out means comprises:        a first processing device which receives said product signal and outputs a processed signal;        internal transform carrying out means connected to said first processing device for carrying out a forward fast Fourier transform on said processed signal and for outputting as a result of said forward fast Fourier transform an internal signal; and        a second processing device connected to said internal transform carrying out means to receive said internal signal and output as a result of processing said internal signal said forward transformed signal.     
     
     
       32. An apparatus for carrying out a forward modified discrete cosine transform comprising:
   an input signal;        a multiplier, said multiplier multiplying a predetermined forward transform window function and said input signal and outputting as a result a product signal; and        transform carrying out means connected to said multiplier for carrying out a linear forward modified discrete cosine transform on said product signal and for outputting a forward modified discrete cosine transformed signal representative of said linear forward modified discrete cosine transform, wherein said transform carrying out means comprises:        a first processing device connected to receive said product signal having N samples, N being an integer, from said multiplier, said first processing device outputting a processed signal having M samples, M being an integer different from N;        means connected to said first processing device for receiving said processed signal and for carrying out a forward fast Fourier transform on said processed signal, and for outputting an internal signal representative of said forward fast Fourier transform; and        a second processing device connected to receive said internal signal from said means for carrying out a forward fast Fourier transform, said second processing device processing said internal signal and outputting as a result said forward modified discrete cosine transformed signal.     
     
     
       33. The apparatus as claimed in  claim 32 , wherein M is smaller than N. 
     
     
       34. The apparatus as claimed in  claim 32 , wherein M is equal to N/ 2 . 
     
     
       35. An apparatus for carrying out an inverse modified discrete cosine transform comprising:
   an input signal having M samples, M being an integer;        transform carrying out means carrying out a linear inverse modified discrete cosine transform on said input signal and for outputting an inverse modified discrete cosine transformed signal having M samples representative of said linear inverse modified discrete cosine transform; and        a multiplier connected to said transform carrying out means, said multiplier multiplying a predetermined inverse transform window function and said linear inverse modified discrete cosine transformed signal to produce a product signal having N samples, N being an integer different from M, wherein said transform carrying out means comprises:        a first processing device which receives said input signal, said first processing device outputting a processed signal;        internal transform carrying out means connected to said first processing device for carrying out an inverse fast Fourier transform on said processed signal as a result of processing said inverse fast Fourier transform an internal signal; and        a second processing device connected to said internal transform carrying out means to receive said internal signal and output as a result of processing said inverse modified discrete cosine transformed signal.     
     
     
       36. The apparatus as claimed in  claim 35 , wherein M is smaller than N. 
     
     
       37. The apparatus as claimed in  claim 35 , wherein M is equal to N/ 2 . 
     
     
       38. An apparatus for carrying out a forward transform comprising:
   an input signal x ( n );      a multiplier for multiplying a predetermined forward transform window function and said input signal x ( n )  to produce a product signal xh ( n ) ; and        transform carrying out means connected to said multiplier for carrying out a linear forward transform on said product signal xh ( n )  and for outputting a forward transformed signal y ( m,k )  representative of a result of said forward transform, said linear forward transform being defined by;           y   ⁡     (     m   ,   k     )       =       ∑     n   =   0       N   -   1       ⁢           ⁢       xh   ⁡     (   n   )       ⁢     cos   ⁢           [     2   ⁢     π   ⁡     (     k   +     1   ⁢     /     ⁢   2       )       ⁢     (     n   +     n   ⁢           ⁢   0       )     ⁢     /     ⁢   N     ]                   where m represents a block number, n represents a sample number, N represents a block length and k is an integer between  0  and N− 1 ;        wherein said transform carrying out means comprises:        a first processing device which receives said product signal xh ( n )  having N samples and outputs a processed signal having M samples, M being an integer different from N, said processed signal comprising a product signal formed by multiplying said product signal xh ( n )  by a predetermined factor;        internal transform carrying out means connected to said first processing device for carrying out a forward fast Fourier transform on said processed signal and for outputting as a result of said forward fast Fourier transform an internal signal; and        a second processing device connected to said internal transform carrying out means to receive said internal signal and output as a result of processing said internal signal said forward transformed signal.     
     
     
       39. The apparatus as claimed in  claim 38 , wherein M is smaller than N. 
     
     
       40. The apparatus as claimed in  claim 38 , wherein M is equal to N/ 2 . 
     
     
       41. An apparatus for carrying out an inverse transform comprising:
   an input signal y ( m,k )  having M samples, M being an integer;        transform carrying out means for carrying out a linear inverse transform on said input signal y ( m,k )  and for outputting an inverse transformed signal xt ( m,n )  representative of a result of said linear inverse transform, said linear inverse transform being defined by:           xt   (     m   ,   n     )     =     2   ⁢     /     ⁢   N   ⁢       ∑     k   =   0       N   -   1       ⁢       y   ⁡     (     m   ,   k     )       ⁢     cos   [     2   ⁢     π   ⁡     (     n   +   n0     )       ⁢     (     k   =     1   ⁢     /     ⁢   2       )     ⁢     /     ⁢   N     ]                     where m represents a block number, n represents a sample number, N represents a block length and k is an integer between  0  and N− 1 ;        a multiplier connected to said transform carrying out means, said multiplier multiplying a predetermined inverse transform window function and said inverse transformed signal xt ( m,n )  to produce a product signal having N samples, N being an integer different from M;        wherein said transform carrying out means comprises:        a first processing device which receives said input signal y ( m,k )  and outputs a processed signal, said processed signal comprising a product signal formed by multiplying said input signal y ( m,k )  by a predetermined factor;        internal transform carrying out means connected to said first processing device for carrying out an inverse fast Fourier transform on said processed signal and for outputting as a result of said inverse fast Fourier transform an internal signal; and        a second processing device connected to said internal transform carrying out means to receive said internal signal and output as a result of processing said internal signal said inverse transformed signal.     
     
     
       42. The apparatus as claimed in  claim 41 , wherein M is smaller than N. 
     
     
       43. The apparatus as claimed in  claim 41 , wherein M is equal to N/ 2 . 
     
     
       44. An apparatus for carrying out an inverse transform comprising:
   an input signal y ( m,k )  having M samples, M being an integer;        transform carrying out means for carrying out a linear inverse transform on said input signal y ( m,k )  and for outputting an inverse transformed signal xt ( m,n )  representative of a result of said linear inverse transform, said linear inverse transform xt ( m,n )  being determined using the sum:           ∑     k   =   0       M   -   1       ⁢       y   ⁡     (     m   ,   k     )       ⁢     cos   [     2   ⁢     π   ⁡     (     n   +   n0     )       ⁢     (     k   =     1   ⁢     /     ⁢   2       )     ⁢     /     ⁢   N     ]                 where m represents a block number, n represents a sample number, N represents a block length and k is an integer between  0  and M− 1 ;        a multiplier connected to said transform carrying out means, said multiplier multiplying a predetermined inverse transform window function and said inverse transformed signal xt ( m,n )  to produce a product signal having N samples, N being an integer different from M;        wherein said transform carrying out means comprises:        a first processing device which receives said input signal y ( m,k )  and outputs a processed signal, said processed signal comprising a product signal formed by multiplying said input signal y ( m,k )  by a predetermined factor;        internal transform carrying out means connected to said first processing device for carrying out an inverse fast Fourier transform on said processed signal and for outputting as a result of said inverse fast Fourier transform an internal signal; and        a second processing device connected to said internal transform carrying out means to receive said internal signal and output as a result of processing said internal signal said inverse transformed signal.     
     
     
       45. The apparatus as claimed in  claim 44 , wherein M is smaller than N. 
     
     
       46. The apparatus as claimed in  claim 44 , wherein M is equal to N/ 2 .