FPGA/DSP Expert - business partner for innovative FFT

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

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

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

> 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

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

soar2morrow@yahoo.com (Tom Seim) writes:

> > 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