FPGA/DSP Expert - business partner for innovative FFT

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 to
Seung
Loading thread data ...

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

Reply to
Clay S. Turner

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

Reply to
Seung

You can find the patent here:

formatting link

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

you

Reply to
Jon Harris

Jon

This will be your friend for long URLs.

formatting link
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...
formatting link

Cheers Bhaskar

formatting link

&u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1=5528736.WKU.&OS=PN/5528736&RS=PN/55

USPTO

Reply to
Bhaskar Thiagarajan

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.

formatting link

&u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1=5528736.WKU.&OS=PN/5528736&RS=PN/55

that

if

this

FFTs)

Reply to
Jon Harris

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

Reply to
Seung

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.

page

formatting link

&u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1=5528736.WKU.&OS=PN/5528736&RS=PN/55

HW

message

problem

not

Reply to
Bhaskar Thiagarajan

Try

formatting link

With that utility, the url became:

formatting link

Reply to
Jaime Andres Aranguren Cardona

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
 Click to see the full signature
Reply to
Hal Murray

--

--Ray Andraka, P.E. President, the Andraka Consulting Group, Inc.

401/884-7930 Fax 401/884-7950 email snipped-for-privacy@andraka.com
formatting link

"They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759

Reply to
Ray Andraka

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

Reply to
Seung

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 to
Arrigo Benedetti

anyone is interested I can send the copy

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

Tom

Reply to
Tom Seim

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

found much innovation at all.

as a 1-D row (column) FFT

column transforms is of N words

impractical for an FPGA implementation

complexity N instead of N log(N).

anyone is interested I can send the copy

Reply to
Seung

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

formatting link

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 to
Arrigo Benedetti

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.