US5561618A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for performing a fast Hadamard transform
Assignee: Qualcomm Inc
•
Filing: 1993-12-22
•
Granted: 1996-10-01
•
Expires: 2013-12-22
Abstract
Abstract A method and apparatus are provided for performing a Hadamard transform operation. The basic building block of the apparatus is an FHT engine having a difference circuit for subtracting the input symbol from a delayed processed symbol, first multiplexer for providing either the difference of the delayed processed symbol and the input symbol or the input symbol, a summing circuit for adding the input symbol to the delayed processed symbol and a second multiplexer for providing either the sum of the input and the delayed processed symbol or the delayed processed symbol as an output. This basic engine is designed to work in conjunction with a variety of different memory configurations. The engines can then be placed in series to perform a Hadamard transform of all defined orders. In addition, two methods of optimizing the use of memory resources are described. On involves the optimal configuration of the memory elements and the second involves truncation. Also, provided is a method and apparatus for performing the transform on samples provided as a serial bit stream to the apparatus.
Inventors
- 👤 Houtan Dehesh
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 18:03
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/14; G06F17/145
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
96 words
In an integrated circuit, a method for performing a transformation comprising the steps of: receiving an input symbol; subtracting said input symbol from a delayed processed symbol to provide a difference symbol; selecting a processed symbol from said difference and said input symbol in an alternating manner; storing said processed symbol in a memory element for a predetermined duration to provide said delayed processed symbol; summing said processed symbol with said input symbol to provide a sum symbol; and selecting a transformed output symbol from said sum and said delayed processed symbol in an alternating manner.
Claim 2
Dependent Claim
96 words
In an integrated circuit, a method for performing a transformation comprising the steps of: receiving an input symbol; subtracting said input symbol from a delayed processed symbol to provide a difference symbol; selecting a processed symbol from said difference and said input symbol in an alternating manner; storing said processed symbol in a memory element for a predetermined duration to provide said delayed processed symbol; summing said processed symbol with said input symbol to provide a sum symbol; and selecting a transformed output symbol from said sum and said delayed processed symbol in an alternating manner.
Claim 3
Dependent Claim
66 words
The method of claim 1 wherein said step of delaying said processed symbol comprises the steps of: shifting a plurality of stored processed symbols into arrays each having different indices including a final index; and storing said processed symbol into an array with an initial index; wherein the stored processed symbol stored in an array with said final index is provided as said delayed processed symbol.
Claim 4
Dependent Claim
93 words
The method of claim 1 wherein said step of receiving said input symbol comprises receiving the bits of said input symbol serially; wherein said step of subtracting said input symbol from a delayed processed symbol further comprises subtracting a borrow symbol from said delayed processed symbol and further comprises providing said borrow symbol in accordance with said step of subtracting; and wherein said step of summing said processed symbol with said input symbol further comprises summing a carry symbol with said processed symbol and said input symbol to further provide said carry symbol.
Claim 5
Dependent Claim
162 words
A circuit for performing a fast transform comprising: a first fast transform circuit having a first input for receiving data to be transformed, a second input for receiving delayed data, a first output for providing processed data, and a second output for providing first transformed data for performing a partial Hadamard transform function; p1 a second fast transform circuit having a first input for receiving said first transformed data, a second input for receiving delayed data, a first output for providing processed data, and a second output for providing second transformed data for performing said partial Hadamard transform function; a first delay circuit for receiving said processed data from said first fast transform circuit and for providing said delayed data to said second input of said first fast transform circuit; and a second delay circuit for receiving said processed data from said second fast transform circuit and for providing said delayed data to said second input of said second fast transform circuit.
Claim 6
Dependent Claim
162 words
A circuit for performing a fast transform comprising: a first fast transform circuit having a first input for receiving data to be transformed, a second input for receiving delayed data, a first output for providing processed data, and a second output for providing first transformed data for performing a partial Hadamard transform function; p1 a second fast transform circuit having a first input for receiving said first transformed data, a second input for receiving delayed data, a first output for providing processed data, and a second output for providing second transformed data for performing said partial Hadamard transform function; a first delay circuit for receiving said processed data from said first fast transform circuit and for providing said delayed data to said second input of said first fast transform circuit; and a second delay circuit for receiving said processed data from said second fast transform circuit and for providing said delayed data to said second input of said second fast transform circuit.
Claim 7
Dependent Claim
86 words
The circuit as set forth in claim 4 further comprising: a third fast transform circuit having a first input for receiving said second transformed data, a second input for receiving delayed data, a first output for providing processed data, and a second output for providing third transformed data for performing said partial Hadamard transform function; a third delay circuit for receiving said processed data from said third fast transform circuit and for providing said delayed data to said second input of said third fast transform circuit.
Claim 8
Dependent Claim
120 words
The circuit as set forth in claim 5 wherein said third fast transform circuit comprises: subtractor circuit for subtracting data from said first input from data from said second input to produce a difference symbol; first multiplexer circuit for selecting a processed symbol from said difference symbol and data from said first input in a first alternating manner and providing said processed symbol on said first output as said processed data; summer circuit for summing said data from said first input with data from said second input to provide a sum symbol; and second multiplexer circuit for selecting said transformed data from said delayed processed symbol and said sum symbol in a second alternating manner provided on said first output.
Claim 9
Dependent Claim
36 words
The circuit as set forth in any one of claims 5 or 6 wherein said delayed data from said third delay circuit is delayed half as long as said delayed data from said second delay circuit.
Claim 10
Dependent Claim
36 words
The circuit as set forth in any one of claims 5 or 6 wherein said delayed data from said third delay circuit is delayed twice as long as said delayed data from said second delay circuit.
Claim 11
Dependent Claim
30 words
The circuit as set forth in claim 4 wherein said delayed data from said first delay circuit is delayed half as long as said delayed data from said second circuit.
Claim 12
Dependent Claim
31 words
The circuit as set forth in claim 4 wherein said delayed data from said first delay circuit is delayed twice as long as said delayed data from said second delay circuit.
Claim 13
Dependent Claim
114 words
The circuit as set forth in any one of claims 4, 5, 9 or 10 wherein said first and second fast transform circuits subtract data from said first input from data from said second input to produce a difference symbol, select a processed symbol from said difference symbol and data from said first input in a first alternating manner and providing said processed symbol on said first output as said processed data, sum said data from said first input with data from said second input to provide a sum symbol, and select said transformed data from said delayed processed symbol and said sum symbol in a second alternating manner provided on said first output.
Claim 14
Dependent Claim
122 words
The circuit as set forth in claim 4 wherein said first and second fast transform circuits comprise: subtractor circuit for subtracting data from said first input from data from said second input to produce a difference symbol; first multiplexer circuit for selecting a processed symbol from said difference symbol and data from said first input in a first alternating manner and providing said processed symbol on said first output as said processed data; summer circuit for summing said data from said first input with data from said second input to provide a sum symbol; and second multiplexer circuit for selecting said transformed data from said delayed processed symbol and said sum symbol in a second alternating manner provided on said first output.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-10-01 | 2000-04-01 | 2000-10-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-10-01 | 2004-04-01 | 2004-10-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-10-01 | 2008-04-01 | 2008-10-01 | $7700.00 | Window Closed / Lapsed |