> > I have seen very few references in the literature to the sliding FFT;
> if anyone is interested I can send the copy
> > of an IEEE paper about it.
>
> What is the IEEE reference (i.e. journal, date & title)?
>
> Tom
Farhang-Boroujeny, B and Y C Lim, .A comment on the computational complexity
of sliding FFT.. IEEE Transactions on Circuits and Systems, 39, no. 12
(December 1992): 875-876.
Farhang-Boroujeny, B and S Gazor, .Generalized sliding FFT and its application
to implementation of block LMS adaptive filters.. IEEE Transactions on Signal
Processing (March 1994): 532-538.
These papers can be downloaded from the author's web page at
http://www2.elen.utah.edu/~farhang
I have seen an EDN article (also cited in the first paper above) cited several
times, but the EDN web site does not carry it.
-Arrigo
Reply by Seung●September 4, 20032003-09-04
Dear Arrigo
The patent you mentioned is only the first one and not directly
related to FFT. Following FFT specific patent is granted but not yet
complete (I have to pay an issuance fee yet).
The patent has nothing to do with sliding FFT, though it can perform
inter-block pipelined (any block) transforms. The row- and column-transform
are not related to row and column transform of a 2-D FFT as you described.
The innovation is based on sampling and reconstruction
of bandlimited signals (harmonic limited) of finite support in
multi-dimensional space.
Seung
Arrigo Benedetti <arrigo@vision.caltech.edu> wrote in message news:<q0iso9qbjf.fsf@vision.caltech.edu>...
> I have spent some time to study this patent and, to be honest, I have not found much innovation at all.
> I might have missed something, but this seems a standard 2-D FFT implemented as a 1-D row (column) FFT
> followed by N 1-D column (row) transforms. The memory requirement for the column transforms is of N words
> for each transform for a total of N^2. This makes the architecture quite impractical for an FPGA implementation
> of large size transform.
> The basic block seems to be related to the sliding 1-D FFT, which has complexity N instead of N log(N).
> This would reduce the complexity of the 2-D FFT from N^2 log(N) to N^2.
> (I am using the conditional since I have not spent much time on this.)
> I have seen very few references in the literature to the sliding FFT; if anyone is interested I can send the copy
> of an IEEE paper about it.
> Any other comments?
>
> -Arrigo
Reply by Tom Seim●September 4, 20032003-09-04
> I have seen very few references in the literature to the sliding FFT; if anyone is interested I can send the copy
> of an IEEE paper about it.
What is the IEEE reference (i.e. journal, date & title)?
Tom
Reply by ●September 4, 20032003-09-04
I have spent some time to study this patent and, to be honest, I have not found much innovation at all.
I might have missed something, but this seems a standard 2-D FFT implemented as a 1-D row (column) FFT
followed by N 1-D column (row) transforms. The memory requirement for the column transforms is of N words
for each transform for a total of N^2. This makes the architecture quite impractical for an FPGA implementation
of large size transform.
The basic block seems to be related to the sliding 1-D FFT, which has complexity N instead of N log(N).
This would reduce the complexity of the 2-D FFT from N^2 log(N) to N^2.
(I am using the conditional since I have not spent much time on this.)
I have seen very few references in the literature to the sliding FFT; if anyone is interested I can send the copy
of an IEEE paper about it.
Any other comments?
-Arrigo
Reply by Seung●September 3, 20032003-09-03
Hi
I am sorry that I am not an expert on FPGA. So the bench mark numbers
are not available that would show actual computation time with actual
FPGA clock speed,lay out efficiencies, etc.
My innovation is more of an algorithmic level - so I would rather
compare
number of clock cycles and gate counts in abstract sense.
I know that highly optimized radix-4, -8 -16 (even 32) modules are out
there,
from which one could build fairly fast 1-D FFTs of moderate sizes
using
mux-parallel scheme if necessary. I would say these are implementation
optimized schemes.
My approach has the best speed/HW complexity ratio in its basic form.
The improvement mainly comes from simplicity of control and
highly regular structure due to algorithmic advances.
For 256 point FFT, it requires 256 clock cycles w/o parallel
implementation.
Precision/accuracy is not on my mind yet: I'm assuming that it is a
common trade-off. The delta improvement might be small for small size
FFTs,
but as FFT size increases, it becomes more significant.
Also 2-D,3-D,... M-D FFT can be done with the same
efficiency, i.e., NxN 2-D FFT requires N^2 cycles without the
complexity of
transpose HW, control nor associated latencies. This is a true
innovation
for multi-dimensional signal processing. Remember that there has been
no true
multi-dimensional FFT algorithm. My algorithm is the first 'intrinsic'
M-D FFT
not relying on 1-D FFT. This innovation will make multi-dimension
signal processing much more affordable. For example, high resolution
hand-held
2-D/3-D ultrasound imaging device will be possible. Also
machine/computer vision
application will benefit greatly.
Sorry that I didn't provide direct answers to your questions, but I
hope
my answer will provide better understanding.
Regards,
Seung P. Kim
Ray Andraka <ray@andraka.com> wrote in message news:<3F550D7F.3DC1122B@andraka.com>...
> I'd be curious to hear about a benchmark or two:
> what is the transform time for a given size FFT, say 256 points?
> what is the FPGA utilization for that FFT?
> Precision/accuracy?
> I have an FFT kernel specifically designed for FPGAs that also has nothing
> idle during the FFT processing. It also does not use the usual C-T
> butterfly, and has only local data flow. The data sheet for the 16 point
> kernel is posted on my website.
>
> Seung wrote:
>
> > Hello
> >
> > I have a patent and recently added one more on innovative FFT
> > algorithm and architecture.
> > If you're a business minded expert on FPGA with interests in DSP, this
> > is a great opportunity. Our FFT is 'the' optimal HW solution as
> > follows:
> >
> > 1. Minimum HW complexity: 100% HW utilization
> > 2. Suitable for super fast pipelined FFT: only local data flow - not
> > based on butterfly algorithm
> > 3. Minimum clock cycles: baseline architecture needs N clock for
> > N-point FFT
> > 4. Scalable to arbitrary large FFT size
> > 5. Multi-dimension extension: world's first 'intrinsic'
> > multi-dimensional FFT algorithm & architecture (not relay on 1-D FFTs)
> > : great for 2-D/3-D real-time medical imaging, SAR, etc.
> >
> > If you're interested in building a business together based on this
> > innovation,
> > please contact me with your resume. It'll be ideal if you have
> > contacts for potential customers.
> >
> > Any help on this matter from FPGA/DSP group members will be
> > appreciated.
> >
> > Thanks.
> >
> > Seung P. Kim, Ph.D
> > Silicon Computing, Inc.
> > Mountain View, CA
>
> --
> --Ray Andraka, P.E.
> President, the Andraka Consulting Group, Inc.
> 401/884-7930 Fax 401/884-7950
> email ray@andraka.com
> http://www.andraka.com
>
> "They that give up essential liberty to obtain a little
> temporary safety deserve neither liberty nor safety."
> -Benjamin Franklin, 1759
Reply by Ray Andraka●September 2, 20032003-09-02
I'd be curious to hear about a benchmark or two:
what is the transform time for a given size FFT, say 256 points?
what is the FPGA utilization for that FFT?
Precision/accuracy?
I have an FFT kernel specifically designed for FPGAs that also has nothing
idle during the FFT processing. It also does not use the usual C-T
butterfly, and has only local data flow. The data sheet for the 16 point
kernel is posted on my website.
Seung wrote:
> Hello
>
> I have a patent and recently added one more on innovative FFT
> algorithm and architecture.
> If you're a business minded expert on FPGA with interests in DSP, this
> is a great opportunity. Our FFT is 'the' optimal HW solution as
> follows:
>
> 1. Minimum HW complexity: 100% HW utilization
> 2. Suitable for super fast pipelined FFT: only local data flow - not
> based on butterfly algorithm
> 3. Minimum clock cycles: baseline architecture needs N clock for
> N-point FFT
> 4. Scalable to arbitrary large FFT size
> 5. Multi-dimension extension: world's first 'intrinsic'
> multi-dimensional FFT algorithm & architecture (not relay on 1-D FFTs)
> : great for 2-D/3-D real-time medical imaging, SAR, etc.
>
> If you're interested in building a business together based on this
> innovation,
> please contact me with your resume. It'll be ideal if you have
> contacts for potential customers.
>
> Any help on this matter from FPGA/DSP group members will be
> appreciated.
>
> Thanks.
>
> Seung P. Kim, Ph.D
> Silicon Computing, Inc.
> Mountain View, CA
--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com
"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759
Please also include the full/long URL so google gets it.
Shortcuts age and die after a while.
--
The suespammers.org mail server is located in California. So are all my
other mailboxes. Please do not send unsolicited bulk e-mail or unsolicited
commercial e-mail to my suespammers.org address or any of my other addresses.
These are my opinions, not necessarily my employer's. I hate spam.
Reply by Jaime Andres Aranguren Cardona●August 15, 20032003-08-15
"Jon Harris" <jon_harrisTIGER@hotmail.com> wrote in message news:<3f3a9180$1_1@newsfeed>...
> Clay, I interpreted his statement about "100% HW utilization" to mean that
> it packed well into current FPGA architectures, allowing (near) 100%
> utilization of the FPGA, not that it required 100% of any particular HW
> device.
>
> -Jon
>
> "Clay S. Turner" <physicsNOOOOSPPPPAMMMM@bellsouth.net> wrote in message
> news:sVw_a.7804$_3.5732@fe02.atl2.webusenet.com...
> > Hello Seung,
> >
> > If you have 100% hardware utilization, doesn't this present a problem if
> you
> > make a change to the design??
> >
> > Curious what is the # for your patent??
> >
> > Clay
> >
> >
> > "Seung" <kim.seung@sbcglobal.net> wrote in message
> > news:fdf92243.0308131136.74aff961@posting.google.com...
> > > Hello
> > >
> > > I have a patent and recently added one more on innovative FFT
> > > algorithm and architecture.
> > > If you're a business minded expert on FPGA with interests in DSP, this
> > > is a great opportunity. Our FFT is 'the' optimal HW solution as
> > > follows:
> > >
> > > 1. Minimum HW complexity: 100% HW utilization
> > > 2. Suitable for super fast pipelined FFT: only local data flow - not
> > > based on butterfly algorithm
> > > 3. Minimum clock cycles: baseline architecture needs N clock for
> > > N-point FFT
> > > 4. Scalable to arbitrary large FFT size
> > > 5. Multi-dimension extension: world's first 'intrinsic'
> > > multi-dimensional FFT algorithm & architecture (not relay on 1-D FFTs)
> > > : great for 2-D/3-D real-time medical imaging, SAR, etc.
> > >
> > > If you're interested in building a business together based on this
> > > innovation,
> > > please contact me with your resume. It'll be ideal if you have
> > > contacts for potential customers.
> > >
> > > Any help on this matter from FPGA/DSP group members will be
> > > appreciated.
> > >
> > >
> > > Thanks.
> > >
> > > Seung P. Kim, Ph.D
> > > Silicon Computing, Inc.
> > > Mountain View, CA
> >
> >
> >
Reply by Bhaskar Thiagarajan●August 15, 20032003-08-15
I've only been using this for a few months now. So it's hard to say. Perhaps
not that reliable for getting archived in Google groups, but then, even a
full link doesn't seem to stand the test of time these days. I have to
constantly delete or modify my bookmarks folder for broken links.
"Jon Harris" <jon_harrisTIGER@hotmail.com> wrote in message
news:3f3ad2ce$1_1@newsfeed...
> That toolbar method is pretty neat! The only thing I wonder about is how
> long the URL redirection will work. And of course it assumes that the
> tinyURL server is always up.
>
> "Bhaskar Thiagarajan" <bhaskart@deja.com> wrote in message
> news:bhgrnu$lln6$1@ID-82263.news.uni-berlin.de...
> > Jon
> >
> > This will be your friend for long URLs.
> > http://tinyurl.com/
> > You can create a toolbar button and click that after a long link web
page
> > and it voila, out pops the smaller one.
> > For example...
> > http://tinyurl.com/k1x6
> >
> > Cheers
> > Bhaskar
> >
> > "Jon Harris" <jon_harrisTIGER@hotmail.com> wrote in message
> > news:3f3a9180$1_1@newsfeed...
> > > You can find the patent here:
> > >
> >
>
> > > 28736
> > > (Watch the word wrap--I wish I knew how to get shorter URLs out of the
> > USPTO
> > > site.)
> > >
> > > Clay, I interpreted his statement about "100% HW utilization" to mean
> that
> > > it packed well into current FPGA architectures, allowing (near) 100%
> > > utilization of the FPGA, not that it required 100% of any particular
HW
> > > device.
> > >
> > > -Jon
> > >
> > > "Clay S. Turner" <physicsNOOOOSPPPPAMMMM@bellsouth.net> wrote in
message
> > > news:sVw_a.7804$_3.5732@fe02.atl2.webusenet.com...
> > > > Hello Seung,
> > > >
> > > > If you have 100% hardware utilization, doesn't this present a
problem
> if
> > > you
> > > > make a change to the design??
> > > >
> > > > Curious what is the # for your patent??
> > > >
> > > > Clay
> > > >
> > > >
> > > > "Seung" <kim.seung@sbcglobal.net> wrote in message
> > > > news:fdf92243.0308131136.74aff961@posting.google.com...
> > > > > Hello
> > > > >
> > > > > I have a patent and recently added one more on innovative FFT
> > > > > algorithm and architecture.
> > > > > If you're a business minded expert on FPGA with interests in DSP,
> this
> > > > > is a great opportunity. Our FFT is 'the' optimal HW solution as
> > > > > follows:
> > > > >
> > > > > 1. Minimum HW complexity: 100% HW utilization
> > > > > 2. Suitable for super fast pipelined FFT: only local data flow -
not
> > > > > based on butterfly algorithm
> > > > > 3. Minimum clock cycles: baseline architecture needs N clock for
> > > > > N-point FFT
> > > > > 4. Scalable to arbitrary large FFT size
> > > > > 5. Multi-dimension extension: world's first 'intrinsic'
> > > > > multi-dimensional FFT algorithm & architecture (not relay on 1-D
> FFTs)
> > > > > : great for 2-D/3-D real-time medical imaging, SAR, etc.
> > > > >
> > > > > If you're interested in building a business together based on this
> > > > > innovation,
> > > > > please contact me with your resume. It'll be ideal if you have
> > > > > contacts for potential customers.
> > > > >
> > > > > Any help on this matter from FPGA/DSP group members will be
> > > > > appreciated.
> > > > >
> > > > >
> > > > > Thanks.
> > > > >
> > > > > Seung P. Kim, Ph.D
> > > > > Silicon Computing, Inc.
> > > > > Mountain View, CA
> > > >
> > > >
> > > >
> > >
> > >
> >
> >
>
>
Reply by Seung●August 15, 20032003-08-15
Hi Jon and Clay,
I used the phrase '100% HW utilization' as an indicator of how well
the HW matches with the algorithm (as old systolic architecture guys
would
use the term) - it means no hardware is wasted sitting idle. So it is
not meant for FPGA utilization percentage, but rather usage
indicator of synthesized logic.
Regards,
Seung
"Jon Harris" <jon_harrisTIGER@hotmail.com> wrote in message news:<3f3a9180$1_1@newsfeed>...
> You can find the patent here:
> http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1
> &u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1=5528736.WKU.&OS=PN/5528736&RS=PN/55
> 28736
> (Watch the word wrap--I wish I knew how to get shorter URLs out of the USPTO
> site.)
>
> Clay, I interpreted his statement about "100% HW utilization" to mean that
> it packed well into current FPGA architectures, allowing (near) 100%
> utilization of the FPGA, not that it required 100% of any particular HW
> device.
>
> -Jon
>
> "Clay S. Turner" <physicsNOOOOSPPPPAMMMM@bellsouth.net> wrote in message
> news:sVw_a.7804$_3.5732@fe02.atl2.webusenet.com...
> > Hello Seung,
> >
> > If you have 100% hardware utilization, doesn't this present a problem if
> you
> > make a change to the design??
> >
> > Curious what is the # for your patent??
> >
> > Clay
> >
> >
> > "Seung" <kim.seung@sbcglobal.net> wrote in message
> > news:fdf92243.0308131136.74aff961@posting.google.com...
> > > Hello
> > >
> > > I have a patent and recently added one more on innovative FFT
> > > algorithm and architecture.
> > > If you're a business minded expert on FPGA with interests in DSP, this
> > > is a great opportunity. Our FFT is 'the' optimal HW solution as
> > > follows:
> > >
> > > 1. Minimum HW complexity: 100% HW utilization
> > > 2. Suitable for super fast pipelined FFT: only local data flow - not
> > > based on butterfly algorithm
> > > 3. Minimum clock cycles: baseline architecture needs N clock for
> > > N-point FFT
> > > 4. Scalable to arbitrary large FFT size
> > > 5. Multi-dimension extension: world's first 'intrinsic'
> > > multi-dimensional FFT algorithm & architecture (not relay on 1-D FFTs)
> > > : great for 2-D/3-D real-time medical imaging, SAR, etc.
> > >
> > > If you're interested in building a business together based on this
> > > innovation,
> > > please contact me with your resume. It'll be ideal if you have
> > > contacts for potential customers.
> > >
> > > Any help on this matter from FPGA/DSP group members will be
> > > appreciated.
> > >
> > >
> > > Thanks.
> > >
> > > Seung P. Kim, Ph.D
> > > Silicon Computing, Inc.
> > > Mountain View, CA
> >
> >
> >