## [Freetel-codec2] FFFT for sparse frequency domain

 [Freetel-codec2] FFFT for sparse frequency domain From: Rick van Rein - 2012-01-20 12:36:14 ```Hello, This would seem to be of interest to Codec2: a Faster-than-Fast Fourier Transform designed especially for sparsely filled spectra: News article: http://web.mit.edu/newsoffice/2012/faster-fourier-transforms-0118.html Paper (free download, as public-funded research ought to be): http://arxiv.org/abs/1201.2501v1 The algorithm achieves O(k.log(n)) if the input signal has at most k non-zero Fourier coefficients. In terms of Codec2, we could expect k=10 over 320 samples, so O(2663) becomes O(133). Roughly -- and background noise would worsen these figures. The Codec2 encoder spends about 1/3 of its time in FFT. Cheers, -Rick ```

 [Freetel-codec2] FFFT for sparse frequency domain From: Rick van Rein - 2012-01-20 12:36:14 ```Hello, This would seem to be of interest to Codec2: a Faster-than-Fast Fourier Transform designed especially for sparsely filled spectra: News article: http://web.mit.edu/newsoffice/2012/faster-fourier-transforms-0118.html Paper (free download, as public-funded research ought to be): http://arxiv.org/abs/1201.2501v1 The algorithm achieves O(k.log(n)) if the input signal has at most k non-zero Fourier coefficients. In terms of Codec2, we could expect k=10 over 320 samples, so O(2663) becomes O(133). Roughly -- and background noise would worsen these figures. The Codec2 encoder spends about 1/3 of its time in FFT. Cheers, -Rick ```
 Re: [Freetel-codec2] FFFT for sparse frequency domain From: Jon K Hellan - 2012-01-20 13:08:19 ```Any idea about code size, and about workload in setup code? I've seen academic algorithm improvements where a huge C dwarfs any gain in the O(whatever) part. Jon LA4RT On 01/20/2012 01:37 PM, Rick van Rein wrote: > Hello, > > This would seem to be of interest to Codec2: a Faster-than-Fast > Fourier Transform designed especially for sparsely filled spectra: > > News article: > http://web.mit.edu/newsoffice/2012/faster-fourier-transforms-0118.html > > Paper (free download, as public-funded research ought to be): > http://arxiv.org/abs/1201.2501v1 > > The algorithm achieves O(k.log(n)) if the input signal has at > most k non-zero Fourier coefficients. In terms of Codec2, we > could expect k=10 over 320 samples, so O(2663) becomes O(133). > > Roughly -- and background noise would worsen these figures. > The Codec2 encoder spends about 1/3 of its time in FFT. > > > Cheers, > -Rick > > ------------------------------------------------------------------------------ > Keep Your Developer Skills Current with LearnDevNow! > The most comprehensive online learning library for Microsoft developers > is just \$99.99! Visual Studio, SharePoint, SQL - plus HTML5, CSS3, MVC3, > Metro Style Apps, more. Free future releases when you subscribe now! > http://p.sf.net/sfu/learndevnow-d2d > _______________________________________________ > Freetel-codec2 mailing list > Freetel-codec2@... > https://lists.sourceforge.net/lists/listinfo/freetel-codec2 ```
 Re: [Freetel-codec2] FFFT for sparse frequency domain From: Rick van Rein - 2012-01-20 13:15:50 ```Hey, > Any idea about code size, and about workload in setup code? I've seen > academic algorithm improvements where a huge C dwarfs any gain in the > O(whatever) part. Of course that is a concern! I haven't read the paper yet, so I cannot comment. I thought it worth sharing anyway, as it seems to provide an extra option for Codec2 implementations. Cheers, -Rick ```
 Re: [Freetel-codec2] FFFT for sparse frequency domain From: Brian Smith - 2012-01-20 13:48:07 ```Rick van Rein wrote: > Hello, > > This would seem to be of interest to Codec2: a Faster-than-Fast > Fourier Transform designed especially for sparsely filled spectra: > > News article: > http://web.mit.edu/newsoffice/2012/faster-fourier-transforms-0118.html > > Paper (free download, as public-funded research ought to be): > http://arxiv.org/abs/1201.2501v1 > > The algorithm achieves O(k.log(n)) if the input signal has at > most k non-zero Fourier coefficients. In terms of Codec2, we > could expect k=10 over 320 samples, so O(2663) becomes O(133). > > Roughly -- and background noise would worsen these figures. > The Codec2 encoder spends about 1/3 of its time in FFT. > > > Cheers, > -Rick > > An alternative would be to use FFTW instead of Kiss-FFT, which runs roughly twice as fast, presumably by pre-computing the required sine/cosine values used in the transform. ```
 Re: [Freetel-codec2] FFFT for sparse frequency domain From: Ronan Paixão - 2012-01-21 17:35:10 Attachments: Message as HTML ```FFTW is a problem, since it is GPL (not LGPL as codec2). Non-free licenses are available for a fee from MIT. I'm not sure they'd license it for distribution as LGPL, even for a fee, because that would pretty much ruin their income venue as people could then grab FFTW from codec2 as LGPL. --------------8<--------------8<------------- *Ronan Paixão* 2012/1/20 Brian Smith > Rick van Rein wrote: > > Hello, > > > > This would seem to be of interest to Codec2: a Faster-than-Fast > > Fourier Transform designed especially for sparsely filled spectra: > > > > News article: > > http://web.mit.edu/newsoffice/2012/faster-fourier-transforms-0118.html > > > > Paper (free download, as public-funded research ought to be): > > http://arxiv.org/abs/1201.2501v1 > > > > The algorithm achieves O(k.log(n)) if the input signal has at > > most k non-zero Fourier coefficients. In terms of Codec2, we > > could expect k=10 over 320 samples, so O(2663) becomes O(133). > > > > Roughly -- and background noise would worsen these figures. > > The Codec2 encoder spends about 1/3 of its time in FFT. > > > > > > Cheers, > > -Rick > > > > > An alternative would be to use FFTW instead of Kiss-FFT, which runs > roughly twice as fast, presumably by pre-computing the required > sine/cosine values used in the transform. > > > ------------------------------------------------------------------------------ > Keep Your Developer Skills Current with LearnDevNow! > The most comprehensive online learning library for Microsoft developers > is just \$99.99! Visual Studio, SharePoint, SQL - plus HTML5, CSS3, MVC3, > Metro Style Apps, more. Free future releases when you subscribe now! > http://p.sf.net/sfu/learndevnow-d2d > _______________________________________________ > Freetel-codec2 mailing list > Freetel-codec2@... > https://lists.sourceforge.net/lists/listinfo/freetel-codec2 > ```
 [Freetel-codec2] linux.conf.au 2012 Codec 2 presentation From: David Rowe - 2012-01-21 23:44:42 ```Hello, Last week I presented a paper on Codec 2 at linux.conf.au 2012. In fact it was voted the best paper of the conference and I was asked to present it again at the end of the conference. I put some effort into relating Ham radio and Open source which went down well. The video has been posted on youtube: https://www.youtube.com/watch?v=KsywWf8dQgU Slide are here (Open office format): http://rowetel.com/downloads/lca_2012_codec2.odp Jean-Marc Valin and Timothy B. Terriberry attended the conference which was great. During and just after the conference Jean-Marc did some work on designing LSP vector quantisers for Codec 2 - thanks a lot Jean-Marc! Thanks, David ```
 Re: [Freetel-codec2] linux.conf.au 2012 Codec 2 presentation From: Bruce Perens - 2012-01-21 23:49:39 ```On 01/21/2012 03:44 PM, David Rowe wrote: > Jean-Marc Valin and Timothy B. Terriberry attended the conference which > was great. During and just after the conference Jean-Marc did some work > on designing LSP vector quantisers for Codec 2 - thanks a lot Jean-Marc! It was really impressive watching David, Jean-Marc, and Tim in a hackathon on David's girlfriend's dining room table. Enough got done to improve the codec that I'm convinced we should do anything possible to get them together once in a while. Thanks Bruce ```