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

• US RE40,854 E1
• Filed: 08/19/2003
• Issued: 07/14/2009
• Est. Priority Date: 06/12/1990
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Iwadare, Masahiro
• Primary Examiner(s): Ngo; Chuong D
• Application Number:
  US10/642,968
• Time in Patent Office: 2,156 Days
• Field of Search: 708/400, 708/401, 708/402, 708/403, 708/404
• US Class Current: 708/400
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence

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).

Claims

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.

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² 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.

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² multiplications.

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) (3N/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.

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² 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.

28. The apparatus of claim 19 wherein said transform carrying out means calculates fewer than N(N−

1) additions.

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;

$\mathrm{xt}\left(m,n\right)=2<br><br>\text{/}<br><br>N<br><br>\underset{k=0}{\overset{N-1}{\sum <br><br>}}<br><br>y<br><br>\left(m,k\right)<br><br>\cos \left[2<br><br>\mathrm{\pi <br><br>}<br><br>\left(n+\mathrm{n0}\right)<br><br>\left(k+1<br><br>\text{/}<br><br>2\right)<br><br>\text{/}<br><br>N\right]$

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.

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² 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<br><br>\left(m,k\right)=\underset{n=0}{\overset{N-1}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{xh}<br><br>\left(n\right)<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}\left[2<br><br>\mathrm{\pi <br><br>}<br><br>\left(k+1<br><br>\text{/}<br><br>2\right)<br><br>\left(n+n<br><br>\text{\hspace{1em}<br><br>}<br><br>0\right)<br><br>\text{/}<br><br>N\right]$

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² 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<br><br>\left(m,k\right)=\underset{n=0}{\overset{N-1}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{xh}<br><br>\left(n\right)<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}\left[2<br><br>\mathrm{\pi <br><br>}<br><br>\left(k+1<br><br>\text{/}<br><br>2\right)<br><br>\left(n+n<br><br>\text{\hspace{1em}<br><br>}<br><br>0\right)<br><br>\text{/}<br><br>N\right]$

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;

$\mathrm{xt}\left(m,n\right)=2<br><br>\text{/}<br><br>N<br><br>\underset{k=0}{\overset{N-1}{\sum <br><br>}}<br><br>y<br><br>\left(m,k\right)<br><br>\cos \left[2<br><br>\mathrm{\pi <br><br>}<br><br>\left(n+\mathrm{n0}\right)<br><br>\left(k=1<br><br>\text{/}<br><br>2\right)<br><br>\text{/}<br><br>N\right]$

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;

$\underset{k=0}{\overset{M-1}{\sum <br><br>}}<br><br>y<br><br>\left(m,k\right)<br><br>\cos \left[2<br><br>\mathrm{\pi <br><br>}<br><br>\left(n+\mathrm{n0}\right)<br><br>\left(k=1<br><br>\text{/}<br><br>2\right)<br><br>\text{/}<br><br>N\right]$

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.