US5394349A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fast inverse discrete transform using subwords for decompression of information
Assignee: Intel Corp
•
Filing: 1992-07-10
•
Granted: 1995-02-28
•
Expires: 2012-07-10
Abstract
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.
Inventors
- 👤 Christopher R. Eddy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 08:39
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/14; G06F17/147
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
138 words
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.
Claim 2
Dependent Claim
138 words
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.
Claim 3
Dependent Claim
20 words
The method of claim 1 further comprising the step of temporarily storing the discrete values in the plurality of registers.
Claim 4
Dependent Claim
17 words
The method of claim 2 wherein the information is compressed using a linear, discrete orthogonal transform technique.
Claim 5
Dependent Claim
28 words
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.
Claim 6
Dependent Claim
37 words
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.
Claim 7
Dependent Claim
25 words
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.
Claim 8
Dependent Claim
26 words
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.
Claim 9
Dependent Claim
34 words
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.
Claim 10
Dependent Claim
13 words
The method of claim 8 wherein the transform coefficients represent multidimensional data sequences.
Claim 11
Dependent Claim
16 words
The method of claim 9 comprising the step of sequentially processing each of the whole words.
Claim 12
Dependent Claim
23 words
The method of claim 10 wherein the processor is a program-controlled microprocessor which is an integer processor and not a floating point processor.
Claim 13
Dependent Claim
34 words
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.
Claim 14
Dependent Claim
25 words
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.
Claim 15
Dependent Claim
18 words
The method of claim 13 wherein the transform partial products are determined and combined to form register values.
Claim 16
Dependent Claim
17 words
The method of claim 13 wherein transform partial products are added and subtracted to form register values.
Claim 17
Dependent Claim
23 words
The method of claim 14 or claim 15 wherein ones of the register values are combined to form upper and lower subword portions.
Claim 18
Dependent Claim
34 words
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.
Claim 19
Dependent Claim
35 words
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.
Claim 20
Dependent Claim
17 words
The method of claim 18 wherein the transform coefficients are used as indices to the look-up table.
Claim 21
Dependent Claim
27 words
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.
Claim 22
Dependent Claim
46 words
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.
Claim 23
Dependent Claim
21 words
The method of claim 21 wherein the transform coefficients are for single and multiple dimensional Discrete Cosine Transform for image compression.
Claim 24
Dependent Claim
23 words
The method of claim 21 wherein the transform coefficients are for real and complex Fast Fourier Transform for compression of time sequence data.
Claim 25
Dependent Claim
35 words
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.
Claim 26
Dependent Claim
21 words
The method of claim 2 wherein the discrete transform technique is subject to expression as a regular, lattice-type signal flow graph.
Claim 27
Dependent Claim
29 words
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.
Claim 28
Dependent Claim
32 words
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.
References Cited (Backward Citations)
US4293921A
Cited
US4449194A
Cited
US4554629A
Cited
US4646256A
Cited
US4837724A
Cited
US4912668A
Cited
US4829465A
Cited
US4831574A
Cited
US4760543A
Cited
US4849922A
Cited
US4791598A
Cited
US5008848A
Cited
US5253192A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-02-27 | 1998-08-29 | 1999-02-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-02-27 | 2002-08-29 | 2003-02-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-02-27 | 2006-08-29 | 2007-02-28 | $7700.00 | Window Closed / Lapsed |