FPGA/DSP Expert - business partner for innovative FFT

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

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

Re: FPGA/DSP Expert - business partner for innovative FFT
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




Quoted text here. Click to load it




Re: FPGA/DSP Expert - business partner for innovative FFT
Hi Clay,

Not at all. You just need to add more stages.
My first patent on this is US5528736. The following patent number
is to be issued within three months.
If you are interested in more details, please send me an e-mail.

Regards,

Seung


Quoted text here. Click to load it

Re: FPGA/DSP Expert - business partner for innovative FFT
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&l50%&s155%28736.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

Quoted text here. Click to load it
you



Off topic - Re: FPGA/DSP Expert - business partner for innovative FFT
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

Quoted text here. Click to load it
http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1
Quoted text here. Click to load it
&u=/netahtml/srchnum.htm&r=1&f=G&l50%&s155%28736.WKU.&OS=PN/5528736&RS=PN/55
Quoted text here. Click to load it
USPTO



Re: Off topic - Re: FPGA/DSP Expert - business partner for innovative FFT
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.

Quoted text here. Click to load it
http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1
Quoted text here. Click to load it
&u=/netahtml/srchnum.htm&r=1&f=G&l50%&s155%28736.WKU.&OS=PN/5528736&RS=PN/55
Quoted text here. Click to load it
that
if
this
FFTs)
Quoted text here. Click to load it



Re: Off topic - Re: FPGA/DSP Expert - business partner for innovative FFT
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.

Quoted text here. Click to load it
page
http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1
Quoted text here. Click to load it
&u=/netahtml/srchnum.htm&r=1&f=G&l50%&s155%28736.WKU.&OS=PN/5528736&RS=PN/55
Quoted text here. Click to load it
HW
message
problem
not



Re: Off topic - Re: FPGA/DSP Expert - business partner for innovative FFT
Quoted text here. Click to load it

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
We've slightly trimmed the long signature. Click to see the full one.
Re: FPGA/DSP Expert - business partner for innovative FFT
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




Quoted text here. Click to load it

Re: FPGA/DSP Expert - business partner for innovative FFT
Quoted text here. Click to load it

Try www.tinyurl.com

With that utility, the url became: http://tinyurl.com/k1x6

Quoted text here. Click to load it

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

Quoted text here. Click to load it

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
We've slightly trimmed the long signature. Click to see the full one.
Re: FPGA/DSP Expert - business partner for innovative FFT
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






Quoted text here. Click to load it

Re: FPGA/DSP Expert - business partner for innovative FFT

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

Re: FPGA/DSP Expert - business partner for innovative FFT
Quoted text here. Click to load it
anyone is interested I can send the copy
Quoted text here. Click to load it

What is the IEEE reference (i.e. journal, date & title)?

Tom

Re: FPGA/DSP Expert - business partner for innovative FFT
snipped-for-privacy@yahoo.com (Tom Seim) writes:

Quoted text here. Click to load it

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

Re: FPGA/DSP Expert - business partner for innovative FFT
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


Quoted text here. Click to load it
found much innovation at all.
Quoted text here. Click to load it
as a 1-D row (column) FFT
Quoted text here. Click to load it
column transforms is of N words
Quoted text here. Click to load it
impractical for an FPGA implementation
Quoted text here. Click to load it
complexity N instead of N log(N).
Quoted text here. Click to load it



anyone is interested I can send the copy
Quoted text here. Click to load it

Site Timeline