Fast inverse discrete transform using subwords for decompression of information

• US 5,394,349 A
• Filed: 07/10/1992
• Issued: 02/28/1995
• Est. Priority Date: 07/10/1992
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Xing Technology Corp (RealNetworks, Inc.)
• Inventors: Eddy, Christopher R.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US07/911,824
• Time in Patent Office: 963 Days
• Field of Search: 364/725-726
• US Class Current: 708/401
• 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

A method for imparting to a general purpose (CISC), or reduced instruction set (RISC), type of central processing unit (CPU; microprocessor) the characteristics and performance of an integer arithmetic digital signal processor (DSP) which executes instructions acting upon multiple ("S") data elements in parallel. The method is applicable to all finite mathematical computations wherein product and sum terms (for example) will never overflow "1/S" fraction of total word width. "S" need not be a multiple of two, but the method is most useful when it is, such as in algorithms containing "butterfly" type computations. It may be used to advantage in the implementation of all discrete orthogonal transforms, and may be generalized to any size CPU word (e.g.: 16-bit, 32-bit, 64-bit, etc.) subject only to limits imposed by the range of vector spaces being handled. Specific applications include single and multiple dimensional Discrete Cosine Transform for image compression, and real and complex Fast Fourier Transform for coding of audio and similar time sequence data.

Claims

1. A signal processing method comprising the steps of:

receiving a first signal representing information in compressed form to a processor, the processor having a plurality of registers, the information being compressed using a discrete transform technique;

processing whole words of the first signal according to bit length;

partitioning at least one of the whole words into a plurality of subwords;

inverse discrete transforming each of the plurality of subwords in accordance with decomposition control of the processor for determination of all discrete values associated with the plurality of subwords for the one of the whole words prior to passing another of the whole words to the processor for processing; and

concatenating the plurality of subwords using the discrete values for forming the one of the whole words for providing a second signal representing the information in decompressed form.

2. The method of claim 1 further comprising the step of temporarily storing the discrete values in the plurality of registers.

3. The method of claim 2 wherein the information is compressed using a linear, discrete orthogonal transform technique.

4. The method of claim 3 wherein each of the plurality of subwords do not have excursions of value which disturb any other ones of the plurality of subwords.

5. The method of claim 3 wherein the information in compressed form is associated with transform coefficients, the whole words being representations of encoded transform coefficients, the whole words being variable length data strings of a data stream.

6. The method of claim 5 wherein the transform coefficients are specifically limited within a range of values owing to resolution limits associated with the information.

7. The method of claim 6 wherein the discrete values associated with the plurality of subwords are derived from transform partial products formed with the transform coefficients.

8. The method of claim 7 wherein the one of the whole words is partitioned into the plurality of subwords for arithmetically operating on the transform partial products of all the plurality of subwords simultaneously.

9. The method of claim 8 wherein the transform coefficients represent multidimensional data sequences.

10. The method of claim 9 comprising the step of sequentially processing each of the whole words.

11. The method of claim 10 wherein the processor is a program-controlled microprocessor which is an integer processor and not a floating point processor.

12. The method of claim 11 wherein the one of the whole words represents one integer, and the plurality of subwords each represent any of a variety of another integer smaller than the one integer.

13. The method of claim 5 wherein the transform coefficients are used to form transform partial products which are temporarily stored in the plurality of registers.

14. The method of claim 13 wherein the transform partial products are determined and combined to form register values.

15. The method of claim 13 wherein transform partial products are added and subtracted to form register values.

16. The method of claim 14 or claim 15 wherein ones of the register values are combined to form upper and lower subword portions.

17. The method of claim 16 wherein the transform partial products are not pre-computed but are determined in real-time by multiplication using the processor and then temporarily stored in some of the plurality of registers.

18. The method of claim 16 wherein the transform partial products are pre-computed and stored in memory in at least one look-up table for recall and subsequent temporary storage in some of the plurality of registers.

19. The method of claim 18 wherein the transform coefficients are used as indices to the look-up table.

20. The method of claim 19 wherein the entire step of inverse discrete transforming using an inverse discrete cosine transform can be completed in equivalent to four additions.

21. The method of claim 19 wherein the transform partial products are further combined as appropriate for pre-computing the discrete values of the plurality of subwords, the discrete values are then grouped to form the whole words, and the whole words are stored in the look-up table.

22. The method of claim 21 wherein the transform coefficients are for single and multiple dimensional Discrete Cosine Transform for image compression.

23. The method of claim 21 wherein the transform coefficients are for real and complex Fast Fourier Transform for compression of time sequence data.

24. The method of claim 5 wherein the whole words are parsed into data strings representing individual ones of the encoded transform coefficients, each of the subwords being a data string representing an encoded transform coefficient.

25. The method of claim 2 wherein the discrete transform technique is subject to expression as a regular, lattice-type signal flow graph.

26. The method of claim 25 wherein the regular, lattice-type signal flow graph includes repeating structures selected from the group consisting of triad notation and two-element by two-element butterfly notation.

27. The method of claim 2 wherein the discrete transform technique is selected from the group consisting of Discrete Fourier Transform, Karhunen-Loeve Transform, Walsh-Hadamard Transform, Discrete Hartley Transform, Z-Transform, and Discrete Cosine Transform.