US4646256A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Computer and method for the discrete bracewell transform
Assignee: Leland Stanford Junior University
•
Filing: 1984-03-19
•
Granted: 1987-02-24
•
Expires: 2004-03-19
Abstract
Abstract Disclosed is a special purpose computer and method of computation for performing an N-length real-number discrete transform. For a real-valued function f( tau ) where tau has the values 0,1, . . .,(N-1), the Discrete Bracewell Transform (DBT) H ( nu ) is as follows: <IMAGE> where, nu =0,1, . . .,N-1 cas theta =cos theta +sin theta . The DBT is performed without need for employing real and imaginary parts, and in efficient embodiments, is executed efficiently and in less time than the Discrete Fourier Transform (DFT). The process steps for the original transform and the inverse retransformation are the same.
Inventors
- 👤 Ronald N. Bracewell
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 08:16
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/14; G06F17/141; G06F17/142
Claims Analysis
Total Claims: 61
Claim 1
Independent Claim
171 words
A method of performing a discrete transform on an input sequence of N input data values, F 0 ,j, where N is equal to 2 P , where P is a positive integer and where j has values from 0 to N-1, comprising, permuting in permuting means the input sequence, F 0 ,j, with a bisecting permutation to form a permuted sequence, F 1 ,j, processing in processing means said permuted sequence in P subsequent stages s where s has values from 2 to P+1, where the outputs from one stage form the inputs for the next stage and where each stage calculates N values of F s ,j as a function of direct values from the previous s-1 stage, as a function of values from the previous s-1 stage multiplied by cosine factors to form cosine terms, and as a function of values from the previous s-1 stage multiplied by sine factors to form sine terms whereby the transformed data values, F P+1 ,j, are provided from the P+1 stage.
Claim 2
Independent Claim
171 words
A method of performing a discrete transform on an input sequence of N input data values, F 0 ,j, where N is equal to 2 P , where P is a positive integer and where j has values from 0 to N-1, comprising, permuting in permuting means the input sequence, F 0 ,j, with a bisecting permutation to form a permuted sequence, F 1 ,j, processing in processing means said permuted sequence in P subsequent stages s where s has values from 2 to P+1, where the outputs from one stage form the inputs for the next stage and where each stage calculates N values of F s ,j as a function of direct values from the previous s-1 stage, as a function of values from the previous s-1 stage multiplied by cosine factors to form cosine terms, and as a function of values from the previous s-1 stage multiplied by sine factors to form sine terms whereby the transformed data values, F P+1 ,j, are provided from the P+1 stage.
Claim 3
Dependent Claim
63 words
The method of claim 1 wherein said processing means includes a first stage, with s equal to 2 of said P subsequent stages, said first stage including means to form sum and difference values from sequential pairs of the permuted sequence values to form the N output values from said first stage without need for explicit multiplication by said sine or cosine factors.
Claim 4
Dependent Claim
52 words
The method of claim 2 wherein a second stage of said P subsequent stages of said processing means forms sum and difference values from alternate output values from said first stage to form the N output values from said second stage without need for explicit multiplication by said sine or cosine factors.
Claim 5
Dependent Claim
47 words
The method of claim 3 wherein each stage s after said second stage forms each said cosine factor C s ,h and each said sine factor S s ,h as follows: C.sub.s,h =cos (2πh/2.sup.s-1) S.sub.s,h =sin (2πh/2.sup.s-1) where, h=0, . . . , (2E-1) E=2 s-2 .
Claim 6
Dependent Claim
22 words
The method of claim 1 wherein said processing step includes the step of dividing each output for the P+1 stage by N.
Claim 7
Dependent Claim
44 words
The method of claim 1 wherein said processing step includes for one or more of said subsequent stages after the second stage the steps of adding said direct value, said cosine term and said sine term to form each value of F s ,j.
Claim 8
Dependent Claim
28 words
The method of claim 1 further including the step of forming said input data values, F 0 ,j, as discrete values in one or more data collection steps.
Claim 9
Dependent Claim
24 words
The method of claim 1 further including the step of processing said transformed data values, F P+1 ,j, in one or more utilization steps.
Claim 10
Dependent Claim
18 words
The method of claim 1 further including the step of converting the transformed data values to Fourier transforms.
Claim 11
Dependent Claim
106 words
The method of claim 1 wherein said bisecting permutation comprises, bisecting each sequence, starting with said input sequence, into odd and even segments and reordering said segments with said odd segment followed by said even segment to form a reordered sequence, repeating said bisecting by bisecting each segment of the reordered sequence to form new odd and even segments of each segment and reordering each new odd and even segment with the odd segment followed by the even segment to form the next reordered sequence, repeating said bisecting until P-1 reordered sequences have been formed whereby the (P-1) th reordered sequence is the bisected permuted sequence.
Claim 12
Independent Claim
291 words
A method of computation employing an input sequence of N input data values, F 0 ,j, where N is equal to 2 P , where P is a positive integer and where j has values from 0 to N-1, comprising, permuting in permuting means the input sequence, F 0 ,j, with a bisecting permutation to form a permuted sequence, F 1 ,j, processing in processing means said permuted sequence in P subsequent stages s where s has values from 2 to P+1, where the output from one stage forms the input for the next stage and where each stage calculates N values of F s ,j as a function of direct values F s-1 ,e from the previous s-1 stage, as a function of values F s-1 ,f from the previous s-1 stage multiplied by a cosine factor C s ,h and as a function of values from the previous s-1 stage multiplied by a sine factor S s ,h where F s ,j is calculated as follows: F.sub.s,j =[F.sub.s-1,e +(F.sub.s-1,f)(C.sub.s,h)+(F.sub.s-1,g)(S.sub.s,h)].sub.q where, N=number of data elements=2 P s=stage number=2, . . . , T T=total number of stages=P+1 Q=N/(2E)=number of pairs of sets of equations in a stage q=0,1, . . . , (Q-1) E=2 s-2 =number of equations in each set of each pair e=[0+(2E)(q)], . . . , [(E-1)+(2E)(q)] f=e+E g=f when h=0 and also when f=f] h=0 g=K-f when h≠0 where K is a constant equal to (2g] h=0 +E h=0, . . . , (2E-1) for first set of pair h=0, . . . , (2E-1) for second set of pair h=0, . . . , (2E-1) j=p+h=0,1, . . . , (N-1) C s ,h =cos (2πh/2 s-1 ) S s ,h =sin (2πh/2 s-1 ).
Claim 13
Independent Claim
291 words
A method of computation employing an input sequence of N input data values, F 0 ,j, where N is equal to 2 P , where P is a positive integer and where j has values from 0 to N-1, comprising, permuting in permuting means the input sequence, F 0 ,j, with a bisecting permutation to form a permuted sequence, F 1 ,j, processing in processing means said permuted sequence in P subsequent stages s where s has values from 2 to P+1, where the output from one stage forms the input for the next stage and where each stage calculates N values of F s ,j as a function of direct values F s-1 ,e from the previous s-1 stage, as a function of values F s-1 ,f from the previous s-1 stage multiplied by a cosine factor C s ,h and as a function of values from the previous s-1 stage multiplied by a sine factor S s ,h where F s ,j is calculated as follows: F.sub.s,j =[F.sub.s-1,e +(F.sub.s-1,f)(C.sub.s,h)+(F.sub.s-1,g)(S.sub.s,h)].sub.q where, N=number of data elements=2 P s=stage number=2, . . . , T T=total number of stages=P+1 Q=N/(2E)=number of pairs of sets of equations in a stage q=0,1, . . . , (Q-1) E=2 s-2 =number of equations in each set of each pair e=[0+(2E)(q)], . . . , [(E-1)+(2E)(q)] f=e+E g=f when h=0 and also when f=f] h=0 g=K-f when h≠0 where K is a constant equal to (2g] h=0 +E h=0, . . . , (2E-1) for first set of pair h=0, . . . , (2E-1) for second set of pair h=0, . . . , (2E-1) j=p+h=0,1, . . . , (N-1) C s ,h =cos (2πh/2 s-1 ) S s ,h =sin (2πh/2 s-1 ).
Claim 14
Dependent Claim
63 words
The method of claim 11 wherein said processing means includes a first stage with s equal to 2 of said P subsequent stages, said first stage including means to form sum and difference values from sequential pairs of the permuted sequence values to form the N output values from said first stage without need for explicit multiplication by said sine or cosine factors.
Claim 15
Dependent Claim
52 words
The method of claim 12 wherein the second stage of said P subsequent stages of said processing means forms sum and difference values from alternate output values from said first stage to form the N output values from said second stage without need for explicit multiplication by said sine or cosine factors.
Claim 16
Dependent Claim
47 words
The method of claim 11 wherein each stage s after said second stage forms each said cosine factor C s ,h and each said sine factor S s ,h as follows: C.sub.s,h =cos (2πh/2.sup.s-1) S.sub.s,h =sin (2πh/2.sup.s-1) where, h=0, . . . , (2E-1) E=2 s-2 .
Claim 17
Dependent Claim
22 words
The method of claim 11 wherein said processing step performs the step of dividing each output for the P+1 stage by N.
Claim 18
Dependent Claim
43 words
The method of claim 11 wherein said processing includes for one or more of said subsequent stages after said second stage the steps of adding said direct value, said cosine term and said sine term to form each value of F s ,j.
Claim 19
Dependent Claim
28 words
The method of claim 11 further including the step of forming said input data values, F 0 ,j, as discrete values in one or more data collection steps.
Claim 20
Dependent Claim
24 words
The method of claim 11 further including the step of processing said transformed data values, F P+1 ,j, in one or more utilization steps.
Claim 21
Independent Claim
316 words
A method of performing a discrete transform on an input sequence of N input data values, F 0 ,j, where N is equal to 2 P , and P is a positive integer where j has values from 0 to N-1, comprising, permuting in permuting means the input sequence, F 0 ,j, with a bisecting permutation to form a permuted sequence, F 1 ,j, processing in processing means said permuted sequence in P subsequent stages s where s has values from 2 to P+1, wherein the output from one stage forms the input for the next stage and wherein each stage calculates N values of F s ,j as a function of direct values F s-1 ,e from the previous s-1 stage, as a function of values F s-1 ,f from the previous s-1 stage multiplied by a cosine factor C s ,h to form a cosine term and as a function of values from the previous s-1 stage multiplied by a sine factor S s ,h to form a sine term where F s ,j is calculated by concurrently adding the direct value, the cosine term and the sine term as follows: F.sub.s,j =[F.sub.s-1,e +(F.sub.s-1,f)(C.sub.s,h)+(F.sub.s-1,g)(S.sub.s,h)].sub.q where, N=number of data elements=2 P s=stage number=2, . . . , T T=total number of stages=P+1 Q=N/(2E)=number of pairs of sets of equations in a stage q=0,1, . . . , (Q-1) E=2 s-2 =number of equations in each set of each pair e=[0+(2E)(q)], . . . , [(E-1)+(2E)(q)] f=e+E g=f when h=0 and also when f=f] h=0 g=K-f when h≠0 where K is a constant equal to (2g] h=0 +E h=0, . . . , (2E-1) for first set of pair h=0, . . . , (2E-1) for second set of pair h=0, . . . , (2E-1) j=p+h=0,1, . . . , (N-1) C s ,h =cos (2πh/2 s-1 ) S s ,h =sin (2πh/2 s-2 ).
Claim 22
Independent Claim
316 words
A method of performing a discrete transform on an input sequence of N input data values, F 0 ,j, where N is equal to 2 P , and P is a positive integer where j has values from 0 to N-1, comprising, permuting in permuting means the input sequence, F 0 ,j, with a bisecting permutation to form a permuted sequence, F 1 ,j, processing in processing means said permuted sequence in P subsequent stages s where s has values from 2 to P+1, wherein the output from one stage forms the input for the next stage and wherein each stage calculates N values of F s ,j as a function of direct values F s-1 ,e from the previous s-1 stage, as a function of values F s-1 ,f from the previous s-1 stage multiplied by a cosine factor C s ,h to form a cosine term and as a function of values from the previous s-1 stage multiplied by a sine factor S s ,h to form a sine term where F s ,j is calculated by concurrently adding the direct value, the cosine term and the sine term as follows: F.sub.s,j =[F.sub.s-1,e +(F.sub.s-1,f)(C.sub.s,h)+(F.sub.s-1,g)(S.sub.s,h)].sub.q where, N=number of data elements=2 P s=stage number=2, . . . , T T=total number of stages=P+1 Q=N/(2E)=number of pairs of sets of equations in a stage q=0,1, . . . , (Q-1) E=2 s-2 =number of equations in each set of each pair e=[0+(2E)(q)], . . . , [(E-1)+(2E)(q)] f=e+E g=f when h=0 and also when f=f] h=0 g=K-f when h≠0 where K is a constant equal to (2g] h=0 +E h=0, . . . , (2E-1) for first set of pair h=0, . . . , (2E-1) for second set of pair h=0, . . . , (2E-1) j=p+h=0,1, . . . , (N-1) C s ,h =cos (2πh/2 s-1 ) S s ,h =sin (2πh/2 s-2 ).
Claim 23
Independent Claim
64 words
A method of performing a discrete transform H(ν) on an input sequence of N input data values, F 0 ,j representing f(τ) where N is equal to 2 P , and P is a positive integer where j is equal to τ and has values from 0 to N-1, and where the discrete transform is of the form ##EQU6## where, cas θ≡cos θ+sin θ
Claim 24
Independent Claim
64 words
A method of performing a discrete transform H(ν) on an input sequence of N input data values, F 0 ,j representing f(τ) where N is equal to 2 P , and P is a positive integer where j is equal to τ and has values from 0 to N-1, and where the discrete transform is of the form ##EQU6## where, cas θ≡cos θ+sin θ
Claim 25
Dependent Claim
29 words
ν=0. . . . , N-1 comprising, permuting in permuting means the input sequence F 0 ,j, with a bisecting permutation to form a permuted sequence, F 1 ,j,
Claim 26
Dependent Claim
29 words
ν=0. . . . , N-1 comprising, permuting in permuting means the input sequence F 0 ,j, with a bisecting permutation to form a permuted sequence, F 1 ,j,
Claim 27
Dependent Claim
231 words
processing in processing means said permuted sequence in P subsequent stages s where s has values from 2 to P+1, where the output from one stage forms the input for the next stage and where each stage calculates N values of F s ,j as a function of direct values F s-1 ,e from the previous s-1 stage, as a function of values F s-1 ,f from the previous s-1 stage multiplied by a cosine factor C s ,h and as a function of values from the previous s-1 stage multiplied by a a sine factor S s ,h where F s ,j is calculated as follows: F.sub.s,j =[F.sub.s-1,e +(F.sub.s-1,f)(C.sub.s,h)+(F.sub.s-1,g)(S.sub.s,h)].sub.q where, N=number of data elements=2 P s=stage number=2, . . . , T T=total number of stages=P+1 Q=N/(2E)=number of pairs of sets of equations in a stage q=0,1, . . . , (Q-1) E=2 s-2 =number of equations in each set of each pair e=[0+(2E) (q)], . . . , [(E-1)+(2E) (q)]f=e+E g=f when h=0 and also when f=f] h=0 g=K-f when h≠0 where K is a constant equal to (2g] h=0 +E h=0, . . . , (2E-1) for first set of pair h=0, . . . , (2E-1) for second set of pair h=0, . . . , (2E-1) j=p+h=0,1, . . . , (N-1) C s ,h =cos (2πh/2 s-1 ) S s ,h =sin (2πh/2 s-1 ).
Claim 28
Dependent Claim
231 words
processing in processing means said permuted sequence in P subsequent stages s where s has values from 2 to P+1, where the output from one stage forms the input for the next stage and where each stage calculates N values of F s ,j as a function of direct values F s-1 ,e from the previous s-1 stage, as a function of values F s-1 ,f from the previous s-1 stage multiplied by a cosine factor C s ,h and as a function of values from the previous s-1 stage multiplied by a a sine factor S s ,h where F s ,j is calculated as follows: F.sub.s,j =[F.sub.s-1,e +(F.sub.s-1,f)(C.sub.s,h)+(F.sub.s-1,g)(S.sub.s,h)].sub.q where, N=number of data elements=2 P s=stage number=2, . . . , T T=total number of stages=P+1 Q=N/(2E)=number of pairs of sets of equations in a stage q=0,1, . . . , (Q-1) E=2 s-2 =number of equations in each set of each pair e=[0+(2E) (q)], . . . , [(E-1)+(2E) (q)]f=e+E g=f when h=0 and also when f=f] h=0 g=K-f when h≠0 where K is a constant equal to (2g] h=0 +E h=0, . . . , (2E-1) for first set of pair h=0, . . . , (2E-1) for second set of pair h=0, . . . , (2E-1) j=p+h=0,1, . . . , (N-1) C s ,h =cos (2πh/2 s-1 ) S s ,h =sin (2πh/2 s-1 ).
Claim 29
Independent Claim
186 words
An apparatus for providing a discrete transform on an input sequence of N input data values, F 0 ,j, where N is equal to 2 P , where P is a positive integer and where j is equal to values from 0 to N-1, comprising, means for permuting the input sequence, F 0 ,j, with a bisecting permutation to form a permuted sequence, F 1 ,j, processing means for processing said permuted sequence in P subsequent stages s where s has values from 2 to P+1, where the output from one stage forms the input for the next stage and where each stage calculates N values of F s ,j, for j equal to values from 0 to N-1, as a function of direct values from the previous s-1 stage, as a function of values from the previous s-1 stage multiplied by a cosine factor to form a cosine term, and as a function of values from the previous s-1 stage multiplied by a a sine factor to form a sine term whereby the transformed data values, F P+1 ,j, are provided from the P+1 stage.
Claim 30
Independent Claim
186 words
An apparatus for providing a discrete transform on an input sequence of N input data values, F 0 ,j, where N is equal to 2 P , where P is a positive integer and where j is equal to values from 0 to N-1, comprising, means for permuting the input sequence, F 0 ,j, with a bisecting permutation to form a permuted sequence, F 1 ,j, processing means for processing said permuted sequence in P subsequent stages s where s has values from 2 to P+1, where the output from one stage forms the input for the next stage and where each stage calculates N values of F s ,j, for j equal to values from 0 to N-1, as a function of direct values from the previous s-1 stage, as a function of values from the previous s-1 stage multiplied by a cosine factor to form a cosine term, and as a function of values from the previous s-1 stage multiplied by a a sine factor to form a sine term whereby the transformed data values, F P+1 ,j, are provided from the P+1 stage.
Claim 31
Dependent Claim
64 words
The apparatus of claim 21 wherein said processing means includes a first stage with s equal to 2 for said P subsequent stages, said first stage including adder means to form sum and difference values from sequential pairs of the permuted sequence values to form the N output values from said first stage without need for explicit multiplication by said sine or cosine factors.
Claim 32
Dependent Claim
59 words
The apparatus of claim 22 wherein said processing means includes a second stage of said P subsequent stages, said second stage including adder means to form sum and difference values from alternate output values from said first stage to form the N output values from said second stage without need for explicit multiplication by said sine or cosine factors.
Claim 33
Dependent Claim
51 words
The apparatus of claim 23 wherein each stage s after said second stage includes generator means to form each said cosine factor C s ,h and each said sine factor S s ,h as follows: C.sub.s,h =cos (2πh/2.sup.s-1) S.sub.s,h =sin (2πh/2.sup.s-1) where, h=0, . . . , (2E-1) E=2 s-2 .
Claim 34
Dependent Claim
21 words
The apparatus of claim 21 wherein said processing means includes means for dividing each output for the P+1 stage by N.
Claim 35
Dependent Claim
44 words
The apparatus of claim 21 wherein said processing means includes for one or more of said subsequent stages after the second stage adder means for adding said direct value, said cosine term and said sine term to form each value of F s ,j.
Claim 36
Independent Claim
346 words
An apparatus for providing a discrete transform on an input sequence of N input data values, F 0 ,j, where N is equal to 2 P , where P is a positive integer and where j is equal to values from 0 to N-1, comprising, permuting means for permuting the input sequence, F 0 ,j, with a bisecting permutation to form a permuted sequence, F 1 ,j, processing means for processing said permuted sequence, said processing means including P subsequent stages s where s has values from 2 to P+1, said processing means including connection means connecting the output from one stage as the input for the next stage and wherein each stage calculates N values of F s ,j for j equal to values from 0 to N-1, said processing means including connection means for providing direct values F s-1 ,e from the previous s-1 stage, said processing means including multiplier means for multiplying values F s-1 ,f from the previous s-1 stage by a cosine factor C s ,h to form a cosine term and said processing means including multiplier means for multiplying values from the previous s-1 stage by a sine factor S s ,h to form a sine term, said processing means including adder means for adding terms to form F s ,j as follows: F.sub.s,j =[F.sub.s-1,e +(F.sub.s-1,f) (C.sub.s,h)+(F.sub.s-1,g) (S.sub.s,h)].sub.q where, N=number of data elements=2 P s=stage number=2, . . . , T T=total number of stages=P+1 Q=N/(2E)=number of pairs of sets of equations in a stage q=0,1, . . . , (Q-1) E=2 s-2 =number of equations in each set of each pair e=[0+(2E) (q)], . . . , [(E-1)+(2E) (q)] f=e+E g=f when h=0 and also when f=f] h=0 g=K-f when h≠0 where K is a constant equal to (2g] h=0 +E h=0, . . . , (2E-1) for first set of pair h=0, . . . , (2E-1) for second set of pair h=0, . . . , (2E-1) j=p+h=0,1, . . . , (N-1) C s ,h =cos (2πh/2 s-1 ) S s ,h =sin (2πh/2 s-1 ).
Claim 37
Independent Claim
346 words
An apparatus for providing a discrete transform on an input sequence of N input data values, F 0 ,j, where N is equal to 2 P , where P is a positive integer and where j is equal to values from 0 to N-1, comprising, permuting means for permuting the input sequence, F 0 ,j, with a bisecting permutation to form a permuted sequence, F 1 ,j, processing means for processing said permuted sequence, said processing means including P subsequent stages s where s has values from 2 to P+1, said processing means including connection means connecting the output from one stage as the input for the next stage and wherein each stage calculates N values of F s ,j for j equal to values from 0 to N-1, said processing means including connection means for providing direct values F s-1 ,e from the previous s-1 stage, said processing means including multiplier means for multiplying values F s-1 ,f from the previous s-1 stage by a cosine factor C s ,h to form a cosine term and said processing means including multiplier means for multiplying values from the previous s-1 stage by a sine factor S s ,h to form a sine term, said processing means including adder means for adding terms to form F s ,j as follows: F.sub.s,j =[F.sub.s-1,e +(F.sub.s-1,f) (C.sub.s,h)+(F.sub.s-1,g) (S.sub.s,h)].sub.q where, N=number of data elements=2 P s=stage number=2, . . . , T T=total number of stages=P+1 Q=N/(2E)=number of pairs of sets of equations in a stage q=0,1, . . . , (Q-1) E=2 s-2 =number of equations in each set of each pair e=[0+(2E) (q)], . . . , [(E-1)+(2E) (q)] f=e+E g=f when h=0 and also when f=f] h=0 g=K-f when h≠0 where K is a constant equal to (2g] h=0 +E h=0, . . . , (2E-1) for first set of pair h=0, . . . , (2E-1) for second set of pair h=0, . . . , (2E-1) j=p+h=0,1, . . . , (N-1) C s ,h =cos (2πh/2 s-1 ) S s ,h =sin (2πh/2 s-1 ).
Claim 38
Dependent Claim
64 words
The apparatus of claim 27 wherein said processing means including a first stage with s equal to 2 for said P subsequent stages, said first stage including adder means to form sum and difference values from sequential pairs of the permuted sequence values to form the N output values from said first stage without need for explicit multiplication by said sine or cosine factors.
Claim 39
Dependent Claim
59 words
The apparatus of claim 28 wherein said processing means includes a second stage of said P subsequent stages, said second stage including adder means to form sum and difference values from alternate output values from said first stage to form the N output values from said second stage without need for explicit multiplication by said sine or cosine factors.
Claim 40
Dependent Claim
51 words
The apparatus of claim 29 wherein each stage s after said second stage includes generator means to form each said cosine factor C s ,h and each said sine factor S s ,h as follows: C.sub.s,h =cos (2πh/2.sup.s-1) S.sub.s,h =sin (2πh/2.sup.s-1) where, h=0, . . . , (2E-1) E=2 s-2 .
Claim 41
Dependent Claim
21 words
The apparatus of claim 27 wherein said processing means includes means for dividing each output for the P+1 stage by N.
Claim 42
Dependent Claim
44 words
The apparatus of claim 27, wherein said processing means includes for one or more of said subsequent stages after the second stage adder means for adding said direct value, said cosine term and said sine term to form each value of F s ,j.
Claim 43
Dependent Claim
22 words
The apparatus of claim 27 further including data collection means for forming said input data values, F 0 ,j, as discrete values.
Claim 44
Dependent Claim
18 words
The apparatus of claim 27 further including utilization means for processing said transformed data values, F P+1 ,j.
Claim 45
Independent Claim
63 words
An apparatus for providing a discrete transform on an input sequence of N input data values, F 0 ,j representing f(τ) where N is equal to 2 P , and P is a positive integer where j is equal to τ and has values from 0 to N-1, and where the discrete transform is of the form ##EQU7## where, cas θ≡cos θ+sin θ
Claim 46
Independent Claim
63 words
An apparatus for providing a discrete transform on an input sequence of N input data values, F 0 ,j representing f(τ) where N is equal to 2 P , and P is a positive integer where j is equal to τ and has values from 0 to N-1, and where the discrete transform is of the form ##EQU7## where, cas θ≡cos θ+sin θ
Claim 47
Dependent Claim
313 words
ν=0. . . . , N-1 comprising, permuting means for permuting the input sequence F 0 ,j, with a bisecting permutation to form a permuted sequence, F 1 ,j, processing means for processing said permuted sequence, said processing means including P subsequent stages s where s has values from 2 to P+1, said processing means including connection means connecting the output from one stage as the input for the next stage and wherein each stage calculates N values of F s ,j where j has values from 0 to N-1, said processing means including means for storing direct values F s-1 ,e from the previous s-1 stage, said processing means including multiplier means for multiplying values F s-1 ,f from the previous s-1 stage by a cosine factor C s ,h to form a cosine term and said processing means including multiplier means for multiplying values from the previous s-1 stage by a sine factor S s ,h to form a sine term, said processing means including adder means for adding said direct value, said cosine term and said sine term to form F s ,j as follows: F.sub.s,j =[F.sub.s-1,e +(F.sub.s-1,f)(C.sub.s,h)+(F.sub.s-1,g)(S.sub.s,h)].sub.q where, N=number of data elements=2 P s=stage number=2, . . . , T T=total number of stages=P+1 Q=N/(2E)=number of pairs of sets of equations in a stage q=0, 1, . . . , (Q-1) E=2 s-2 =number of equations in each set of each pair e=[0+(2E)(q)], . . . , [(E-1)+(2E)(q)] f=e+E g=f when h=0 and also when f=f] h=0 g=K-f when h≠0 where K is a constant equal to (2g] h=0 +E h=0, . . . , (2E-1) for first set of pair h=0, . . . , (2E-1) for second set of pair h=0, . . . , (2E-1) j=p+h=0, 1, . . . , (N-1) C s ,h =cos (2πh/2 s-1 ) S s ,h =sin (2πh/2 s-1 ).
Claim 48
Dependent Claim
313 words
ν=0. . . . , N-1 comprising, permuting means for permuting the input sequence F 0 ,j, with a bisecting permutation to form a permuted sequence, F 1 ,j, processing means for processing said permuted sequence, said processing means including P subsequent stages s where s has values from 2 to P+1, said processing means including connection means connecting the output from one stage as the input for the next stage and wherein each stage calculates N values of F s ,j where j has values from 0 to N-1, said processing means including means for storing direct values F s-1 ,e from the previous s-1 stage, said processing means including multiplier means for multiplying values F s-1 ,f from the previous s-1 stage by a cosine factor C s ,h to form a cosine term and said processing means including multiplier means for multiplying values from the previous s-1 stage by a sine factor S s ,h to form a sine term, said processing means including adder means for adding said direct value, said cosine term and said sine term to form F s ,j as follows: F.sub.s,j =[F.sub.s-1,e +(F.sub.s-1,f)(C.sub.s,h)+(F.sub.s-1,g)(S.sub.s,h)].sub.q where, N=number of data elements=2 P s=stage number=2, . . . , T T=total number of stages=P+1 Q=N/(2E)=number of pairs of sets of equations in a stage q=0, 1, . . . , (Q-1) E=2 s-2 =number of equations in each set of each pair e=[0+(2E)(q)], . . . , [(E-1)+(2E)(q)] f=e+E g=f when h=0 and also when f=f] h=0 g=K-f when h≠0 where K is a constant equal to (2g] h=0 +E h=0, . . . , (2E-1) for first set of pair h=0, . . . , (2E-1) for second set of pair h=0, . . . , (2E-1) j=p+h=0, 1, . . . , (N-1) C s ,h =cos (2πh/2 s-1 ) S s ,h =sin (2πh/2 s-1 ).
Claim 49
Dependent Claim
19 words
The apparatus of claim 35 wherein said adder means is a three-input adder for each of said N values.
Claim 50
Dependent Claim
22 words
The apparatus of claim 35 wherein each of said subsequent stages includes register means for storing output values from the previous stage.
Claim 51
Independent Claim
242 words
A method of performing a discrete transform on an input sequence of N real input data values, F 0 ,j, where N is equal to 2 P , where P is a positive integer and where j has values from 0 to N-1, comprising, permuting with permuting means the input sequence, F 0 ,j, in a first stage with a bisecting permutation to form an N-numbered permuted sequence, F 1 ,j, processing with processing means said permuted sequence in P subsequent stages s where s has values from 2 to P+1, where the outputs from one stage form the inputs for the next stage, where the s-1 stage for each value of s from 2 to P+1 provides N-numbered outputs as inputs to the s stage, where the s equal 2 stage receives the F 1 ,j sequence as an input, and where each stage calculates N values of F s ,j as a function of direct values from the previous s-1 stage, as a function of first values F s-1 ,f from the previous s-1 stage multiplied by cosine factors C s ,h to form cosine terms, and as a function of values from the previous s-1 stage multiplied by sine factors C s ,h to form sine terms having retrograde indexes in that the indexes g and h for said sine terms change in opposite directions, whereby the transformed data values, F P+1 ,j, are provided from the P+1 stage.
Claim 52
Independent Claim
242 words
A method of performing a discrete transform on an input sequence of N real input data values, F 0 ,j, where N is equal to 2 P , where P is a positive integer and where j has values from 0 to N-1, comprising, permuting with permuting means the input sequence, F 0 ,j, in a first stage with a bisecting permutation to form an N-numbered permuted sequence, F 1 ,j, processing with processing means said permuted sequence in P subsequent stages s where s has values from 2 to P+1, where the outputs from one stage form the inputs for the next stage, where the s-1 stage for each value of s from 2 to P+1 provides N-numbered outputs as inputs to the s stage, where the s equal 2 stage receives the F 1 ,j sequence as an input, and where each stage calculates N values of F s ,j as a function of direct values from the previous s-1 stage, as a function of first values F s-1 ,f from the previous s-1 stage multiplied by cosine factors C s ,h to form cosine terms, and as a function of values from the previous s-1 stage multiplied by sine factors C s ,h to form sine terms having retrograde indexes in that the indexes g and h for said sine terms change in opposite directions, whereby the transformed data values, F P+1 ,j, are provided from the P+1 stage.
Claim 53
Dependent Claim
63 words
The method of claim 38 wherein said processing means includes a first stage, with s equal to 2 of said P subsequent stages, said first stage including means to form sum and difference values from sequential pairs of the permuted sequence values to form the N output values from said first stage without need for explicit multiplication by said sine or cosine factors.
Claim 54
Dependent Claim
52 words
The method of claim 39 wherein a second stage of said P subsequent stages of said processing means forms sum and difference values from alternate output values from said first stage to form the N output values from said second stage without need for explicit multiplication by said sine or cosine factors.
Claim 55
Dependent Claim
50 words
The method of claim 40 wherein each stage s after said second stage forms each said cosine factor C s ,h and each said sine factor [S 2 ,h ]S s ,h as follows: C.sub.s,h =cos (2πh/2.sup.s-1) S.sub.s,h =sin (2πh/2.sup.s-1) where, h=0, . . . , (2E-1) E=2 s-2 .
Claim 56
Independent Claim
174 words
The method of performing a discrete transform H(ν) on an input sequence of N input data values, f(τ), where N is a positive integer including 2 P , where P is a positive integer, and where τ has values from 0 to N-1, said method forming the transform H(ν) for each value of ν in accordance with the following sum for all values of τ, ##EQU8## where, cas θ≡cos θ+sin θ θ=(2πντ/N) and said method including the steps of, permuting in permuting means the input data vaues, f(τ), with a bisecting permutation to form a permuted sequence, processing said permuted sequence in processing means using a plurality of stages where the outputs from one stage form the inputs for the next stage, said processing employing direct values from the previous stage, employing values from the previous stage multiplied by cosine factors to form cosine terms, and employing values from the previous stage multiplied by sine factors to form sine terms whereby the transformed data values are provided from the last one of said stages.
Claim 57
Independent Claim
174 words
The method of performing a discrete transform H(ν) on an input sequence of N input data values, f(τ), where N is a positive integer including 2 P , where P is a positive integer, and where τ has values from 0 to N-1, said method forming the transform H(ν) for each value of ν in accordance with the following sum for all values of τ, ##EQU8## where, cas θ≡cos θ+sin θ θ=(2πντ/N) and said method including the steps of, permuting in permuting means the input data vaues, f(τ), with a bisecting permutation to form a permuted sequence, processing said permuted sequence in processing means using a plurality of stages where the outputs from one stage form the inputs for the next stage, said processing employing direct values from the previous stage, employing values from the previous stage multiplied by cosine factors to form cosine terms, and employing values from the previous stage multiplied by sine factors to form sine terms whereby the transformed data values are provided from the last one of said stages.
Claim 58
Independent Claim
146 words
A method of performing a final transform of the convolution of first and second sequences of N input data values, (F 0 ,j) 1 and (F 0 ,j) 2 representing f 1 (τ) and F 2 (τ), designated f i (τ), where H 1 (ν) and H 2 (ν), designated H i (ν), are the discrete transforms of f 1 (τ) and f 2 (τ) where for H i (ν) and f i (τ) i is equal to 1 and 2, where for each of said sequences N is equal to 2 P , and P is a positive integer where j is equal to τ and has values from 0 to N-1, where f 2 (τ) is an even function and where the discrete transform H i (ν) for i equal to 1 and 2 is of the form ##EQU9## where, cas θ≡cos θ+sin θ
Claim 59
Independent Claim
146 words
A method of performing a final transform of the convolution of first and second sequences of N input data values, (F 0 ,j) 1 and (F 0 ,j) 2 representing f 1 (τ) and F 2 (τ), designated f i (τ), where H 1 (ν) and H 2 (ν), designated H i (ν), are the discrete transforms of f 1 (τ) and f 2 (τ) where for H i (ν) and f i (τ) i is equal to 1 and 2, where for each of said sequences N is equal to 2 P , and P is a positive integer where j is equal to τ and has values from 0 to N-1, where f 2 (τ) is an even function and where the discrete transform H i (ν) for i equal to 1 and 2 is of the form ##EQU9## where, cas θ≡cos θ+sin θ
Claim 60
Dependent Claim
312 words
ν=0. . . . , N-1 i=1, 2 said method comprising, forming H i (ν) for i equal to 1 and 2 by the steps of, permuting in permuting means the input sequence (F 0 ,j) i , with a bisecting permutation to form a permuted sequence, (F 1 ,j) i , processing in processing means said permuted sequence in P subsequent stages s where s has values from 2 to P+1, where the output from one stage forms the input for the next stage and where each stage calculates N values of (F s ,j) i as a function of direct values F s-1 ,e from the previous s-1 stage, as a function of values F s-1 ,f from the previous s-1 stage multiplied by a cosine factor C s ,h and as a function of values from the previous s-1 stage multiplied by a a sine factor S s ,h where (F s ,j) i is calculated for i equal to 1 and 2 as follows: (F.sub.s,j).sub.i =([F.sub.s-1,e +(F.sub.s-1,f)(C.sub.s,h)+(F.sub.s-1,g)(S.sub.s,h)].sub.q).sub.i where, N=number of data elements=2 P s=stage number=2, . . . , T T=total number of stages=P+1 Q=N/(2E)=number of pairs of sets of equations in a stage q=0, 1, . . . , (Q-1) E=2 s-2 =number of equations in each set of each pair e=[0+(2E)(q)], . . . , [(E-1)+(2E)(q)] f=e+E g=f when h=0 and also when f=f] h=0 g=K-f when h≠0 where K is a constant equal to (2g] h=0 +E h=0, . . . , (2E-1) for first set of pair h=0, . . . , (2E-1) for second set of pair h=0, . . . , (2E-1) j=p+h=0, 1, . . . , (N-1) C s ,h =cos (2πh/2 s-1 ) S s ,h =sin (2πh/2 s-1 ) multiplying H 1 (ν) and H 2 (ν) to form [H 1 (ν)][H 2 (ν)] as said final transform.
Claim 61
Dependent Claim
312 words
ν=0. . . . , N-1 i=1, 2 said method comprising, forming H i (ν) for i equal to 1 and 2 by the steps of, permuting in permuting means the input sequence (F 0 ,j) i , with a bisecting permutation to form a permuted sequence, (F 1 ,j) i , processing in processing means said permuted sequence in P subsequent stages s where s has values from 2 to P+1, where the output from one stage forms the input for the next stage and where each stage calculates N values of (F s ,j) i as a function of direct values F s-1 ,e from the previous s-1 stage, as a function of values F s-1 ,f from the previous s-1 stage multiplied by a cosine factor C s ,h and as a function of values from the previous s-1 stage multiplied by a a sine factor S s ,h where (F s ,j) i is calculated for i equal to 1 and 2 as follows: (F.sub.s,j).sub.i =([F.sub.s-1,e +(F.sub.s-1,f)(C.sub.s,h)+(F.sub.s-1,g)(S.sub.s,h)].sub.q).sub.i where, N=number of data elements=2 P s=stage number=2, . . . , T T=total number of stages=P+1 Q=N/(2E)=number of pairs of sets of equations in a stage q=0, 1, . . . , (Q-1) E=2 s-2 =number of equations in each set of each pair e=[0+(2E)(q)], . . . , [(E-1)+(2E)(q)] f=e+E g=f when h=0 and also when f=f] h=0 g=K-f when h≠0 where K is a constant equal to (2g] h=0 +E h=0, . . . , (2E-1) for first set of pair h=0, . . . , (2E-1) for second set of pair h=0, . . . , (2E-1) j=p+h=0, 1, . . . , (N-1) C s ,h =cos (2πh/2 s-1 ) S s ,h =sin (2πh/2 s-1 ) multiplying H 1 (ν) and H 2 (ν) to form [H 1 (ν)][H 2 (ν)] as said final transform.
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) | 1990-02-23 | 1990-08-25 | 1991-02-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1994-02-23 | 1994-08-25 | 1995-02-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1998-02-23 | 1998-08-25 | 1999-02-24 | $7700.00 | Window Closed / Lapsed |