Fast system and method for computing modulated lapped transforms

• US 6,073,153 A
• Filed: 06/03/1998
• Issued: 06/06/2000
• Est. Priority Date: 06/03/1998
• Status: Expired due to Fees

• Current Assignee: Neiversan Networks Co LLC (Intellectual Ventures LLC)
• Original Assignee: Microsoft Corporation
• Inventors: Malvar, Henrique S.
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US09/089,949
• Time in Patent Office: 734 Days
• Field of Search: 708/400, 708/402, 708/409
• 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

The present invention is embodied in a system and method for fast computation of a spatial transform of an input signal. The computation system includes a window processor having a window function and an operator having a first set of weights. The window processor receives the input signal as sample blocks and the operator is adapted to apply butterfly coefficients determined by the window function to produce resulting vectors. Also, the window processor maps the input signal to a cascade of butterflies using the first set of weights and reorders the cascade of butterflies. A transform processor having a transform module computes a spatial transform from the reordered cascade of butterflies to produce transform coefficient. A coefficient combination operator combines the transform coefficients to produce an encoded output corresponding to the input signal.

Claims

1. A computer-implemented method for efficiently computing a biorthogonal modulated lapped transform, said method comprising:

receiving a first sample and a second sample;

multiplying the first and second samples by a first pre-computed set of ratios of window coefficients to produce respective first and second multiplied outputs;

combining the first and second samples with the first and second multiplied outputs to produce respective first and second combined outputs;

multiplying the first and second combined outputs by a second pre-computed set of ratios of window coefficients to produce respective third and fourth multiplied outputs;

delaying the third multiplied output and allowing the fourth multiplied output to be undelayed; and

producing resulting vectors from the delayed third multiplied output and the undelayed fourth multiplied output, wherein the resulting vectors represent a windowed signal.

2. The method of claim 1, wherein the third multiplied output is delayed by storing the third multiplied output in a memory of a one block delay buffer.

3. The method of claim 2, wherein the first sample comprises a first discrete set of samples of an input signal and the second sample comprises a second discrete set of samples of the input signal.

4. The method of claim 3, wherein the number of samples of the first discrete set of samples equals the number of samples of the second discrete set of samples.

5. The method of claim 4, wherein half of the resulting vectors are stored in the memory of the one block delay buffer and current contents of the delay buffer are recovered.

6. The method of claim 1, further comprising computing a spatial transform from the resulting vectors to produce transform coefficients and combining the transform coefficients to produce an encoded output corresponding to the input signal.

7. A fast computation system stored on computer readable memory of a computer system for efficiently computing a biorthogonal modulated lapped transform, the fast computation system comprising:

a window module for applying butterfly coefficients determined by a given window function for replacing first and second samples having values with a linear combination of the values of the samples, the window module comprising,

a first multiplication submodule for multiplying the first and second samples by a first pre-computed set of ratios of window coefficients to produce respective first and second multiplied outputs,

a combination module for combining the first and second samples with the first and second multiplied outputs to produce respective first and second combined outputs, and

a second multiplication submodule for multiplying the first and second combined outputs by a second pre-computed set of ratios of window coefficients to produce respective third and fourth multiplied outputs; and

a delay module for delaying the third multiplied output and allowing the fourth multiplied output to be undelayed and producing resulting vectors from the delayed and undelayed samples, wherein the resulting vectors represent a windowed signal.

8. The fast computation system of claim 7, wherein the delay module comprises a storage submodule for storing the third multiplied output in a memory of a one block delay buffer.

9. The fast computation system of claim 8, wherein the first sample comprises a first discrete set of samples of an input signal and the second sample comprises a second discrete set of samples of the input signal.

10. The fast computation system of claim 9, where in the number of samples of the first discrete set of samples equals the number of samples of the second discrete set of samples.

11. The fast computation system of claim 10, wherein the storage submodule is adapted for storing half of the resulting vectors in the memory of the one block delay buffer and recovering current contents of the delay buffer.

12. The fast computation system of claim 7, further comprising a transform module for computing a spatial transform from the resulting vectors to produce transform coefficients and coefficient operator for combining the transform coefficients to produce an encoded output corresponding to the input signal.

13. A computer-implemented method for efficiently computing an inverse biorthogonal modulated lapped transform, said method comprising:

receiving a first sample and a second sample representing decoded and inverse transformed data of an original input signal;

delaying the second sample and allowing the first sample to be undelayed;

multiplying the first undelayed sample and the second delayed sample by a first pre-computed set of ratios of window coefficients to produce respective first and second multiplied outputs;

multiplying the first and second multiplied outputs by a second pre-computed set of ratios of window coefficients to produce respective third and fourth multiplied outputs; and

combining the third and fourth multiplied outputs to produce respective first and second combined outputs corresponding to a reconstructed version of the input signal.

14. The method of claim 13, wherein the second sample is delayed by storing the second sample in a memory of a one block delay buffer.

15. The method of claim 14, wherein the first sample comprises a first discrete set of samples of the input signal and the second sample comprises a second discrete set of samples of the input signal.

16. The method of claim 15, wherein the number of samples of the first discrete set of samples equals the number of samples of the second discrete set of samples.

17. The method of claim 16, wherein half of the resulting vectors are stored in the memory of the one block delay buffer and current contents of the delay buffer are recovered.

18. A computer-implemented method for efficiently computing an orthogonal modulated lapped transform with a predefined sine window, said method comprising:

multiplying a first sample by a first pre-computed ratio of window coefficients to produce a first multiplied output and multiplying a second sample by a second pre-computed ratio of window coefficients to produce a second multiplied output;

combining the first and second multiplied outputs to produce a first combined output, applying a first value to the first combined output to produce a first applied output, and applying a second value to the second combined output to produce a second applied output;

combining the first applied output with the first sample to produce a second combined output and combining the second applied output with the second sample to produce a third combined output;

delaying the second combined output and allowing the third combined output to be undelayed and applying a third value to the delayed second combined output and the third combined output; and

producing respective resulting vectors from the delayed and undelayed outputs, wherein the resulting vectors represent a windowed signal.

19. The method of claim 18, wherein the second combined output is delayed by storing the second combined output in a memory of a one block delay buffer.

20. The method of claim 19, wherein the first sample comprises a first discrete set of samples of an input signal and the second sample comprises a second discrete set of samples of the input signal.

21. The method of claim 20, wherein the number of samples of the first discrete set of samples equals the number of samples of the second discrete set of samples.

22. The method of claim 21, wherein half of the resulting vectors are stored in the memory of the one block delay buffer and current contents of the delay buffer are recovered.

23. The method of claim 18, further comprising computing a spatial transform from the resulting vectors to produce transform coefficients and combining the transform coefficients to produce an encoded output corresponding to the input signal.

24. A computer-implemented method for efficiently computing an inverse biorthogonal modulated lapped transform, said method comprising:

receiving a first sample and a second sample representing decoded and inverse transformed data of an original input signal and applying a first value to the first and second samples to produce respective first and second applied outputs;

delaying the second applied output and allowing the first applied output to be undelayed;

applying a second value to the first applied output to produce a third applied output, and applying a third value to the second applied output to produce a fourth applied output and combining the third and fourth applied outputs to produce a first combined output;

multiplying the first combined output by a first pre-computed ratio of window coefficients to produce a first multiplied output and multiplying the first combined output by a second pre-computed ratio of window coefficients to produce a second multiplied output;

combining the first and second multiplied outputs with the first applied output and the second delayed applied output to produce respective second and third combined outputs corresponding to a reconstructed version of the input signal.

25. The method of claim 24, wherein the second applied output is delayed by storing the second sample in a memory of a one block delay buffer.

26. The method of claim 25, wherein the first sample comprises a first discrete set of samples of the input signal and the second sample comprises a second discrete set of samples of the input signal.

27. The method of claim 26, wherein the number of samples of the first discrete set of samples equals the number of samples of the second discrete set of samples.

28. The method of claim 27, wherein half of the resulting vectors are stored in the memory of the one block delay buffer and current contents of the delay buffer are recovered.