Current version

v1.10.4 (stable)

Navigation

Main page
Archived news
Downloads
Documentation
   Capture
   Compiling
   Processing
   Crashes
Features
Filters
Plugin SDK
Knowledge base
Contact info
Forum
 
Other projects
   Altirra

Search

Archives

01 Dec - 31 Dec 2013
01 Oct - 31 Oct 2013
01 Aug - 31 Aug 2013
01 May - 31 May 2013
01 Mar - 31 Mar 2013
01 Feb - 29 Feb 2013
01 Dec - 31 Dec 2012
01 Nov - 30 Nov 2012
01 Oct - 31 Oct 2012
01 Sep - 30 Sep 2012
01 Aug - 31 Aug 2012
01 June - 30 June 2012
01 May - 31 May 2012
01 Apr - 30 Apr 2012
01 Dec - 31 Dec 2011
01 Nov - 30 Nov 2011
01 Oct - 31 Oct 2011
01 Sep - 30 Sep 2011
01 Aug - 31 Aug 2011
01 Jul - 31 Jul 2011
01 June - 30 June 2011
01 May - 31 May 2011
01 Apr - 30 Apr 2011
01 Mar - 31 Mar 2011
01 Feb - 29 Feb 2011
01 Jan - 31 Jan 2011
01 Dec - 31 Dec 2010
01 Nov - 30 Nov 2010
01 Oct - 31 Oct 2010
01 Sep - 30 Sep 2010
01 Aug - 31 Aug 2010
01 Jul - 31 Jul 2010
01 June - 30 June 2010
01 May - 31 May 2010
01 Apr - 30 Apr 2010
01 Mar - 31 Mar 2010
01 Feb - 29 Feb 2010
01 Jan - 31 Jan 2010
01 Dec - 31 Dec 2009
01 Nov - 30 Nov 2009
01 Oct - 31 Oct 2009
01 Sep - 30 Sep 2009
01 Aug - 31 Aug 2009
01 Jul - 31 Jul 2009
01 June - 30 June 2009
01 May - 31 May 2009
01 Apr - 30 Apr 2009
01 Mar - 31 Mar 2009
01 Feb - 29 Feb 2009
01 Jan - 31 Jan 2009
01 Dec - 31 Dec 2008
01 Nov - 30 Nov 2008
01 Oct - 31 Oct 2008
01 Sep - 30 Sep 2008
01 Aug - 31 Aug 2008
01 Jul - 31 Jul 2008
01 June - 30 June 2008
01 May - 31 May 2008
01 Apr - 30 Apr 2008
01 Mar - 31 Mar 2008
01 Feb - 29 Feb 2008
01 Jan - 31 Jan 2008
01 Dec - 31 Dec 2007
01 Nov - 30 Nov 2007
01 Oct - 31 Oct 2007
01 Sep - 30 Sep 2007
01 Aug - 31 Aug 2007
01 Jul - 31 Jul 2007
01 June - 30 June 2007
01 May - 31 May 2007
01 Apr - 30 Apr 2007
01 Mar - 31 Mar 2007
01 Feb - 29 Feb 2007
01 Jan - 31 Jan 2007
01 Dec - 31 Dec 2006
01 Nov - 30 Nov 2006
01 Oct - 31 Oct 2006
01 Sep - 30 Sep 2006
01 Aug - 31 Aug 2006
01 Jul - 31 Jul 2006
01 June - 30 June 2006
01 May - 31 May 2006
01 Apr - 30 Apr 2006
01 Mar - 31 Mar 2006
01 Feb - 29 Feb 2006
01 Jan - 31 Jan 2006
01 Dec - 31 Dec 2005
01 Nov - 30 Nov 2005
01 Oct - 31 Oct 2005
01 Sep - 30 Sep 2005
01 Aug - 31 Aug 2005
01 Jul - 31 Jul 2005
01 June - 30 June 2005
01 May - 31 May 2005
01 Apr - 30 Apr 2005
01 Mar - 31 Mar 2005
01 Feb - 29 Feb 2005
01 Jan - 31 Jan 2005
01 Dec - 31 Dec 2004
01 Nov - 30 Nov 2004
01 Oct - 31 Oct 2004
01 Sep - 30 Sep 2004
01 Aug - 31 Aug 2004

Stuff

Powered by Pivot  
XML: RSS feed 
XML: Atom feed 

§ Brute force works a lot better than it used to

I've been playing with pitch shifting again. It's not that I've gotten bored with video, but I do like to write little DSP kernels to affect music that I listen to while coding. I could do the same with video, but I don't think I could get any work done with video playing on the side. Especially if I'm reading subtitles.

As I've said before, pitch shifters (err, pitch scalers) can work either in frequency domain or time domain. Well, after I got the frequency-domain shifter working, I got a better idea for doing a time-domain shifter. The main problem in creating a time-domain shifter is the cross-correlation step, where you find a well-matching segment within a window to overlap with the end of the last segment you used. One way to do this is to try to do some sort of hierarchical approximation to zero in on a good match. Since I had just written a radix-4 FFT/IFFT, I got the idea instead of using FFT convolution to efficiently generate cross-correlation results for all positions without approximation. FFT convolution allows you to compute all possible circular convolutions of one signal with another, and by sufficiently zero-padding the two samples and reversing one of them -- or equivalently, using the conjugate of its frequency representation -- you can do a full cross-correlation search in O(N log N) time, and then scan the resultant array for the best match. And it sort of worked.

I was still hearing some artifacts that made the convolution results suspect, so I decided to double-check the results using a brute force routine. This is trying to search for a match for a block of 512 paired stereo samples in a window of 1024 samples, every 2048 samples, at 44KHz. Amusingly enough, it still ran in real-time... using regular x87 scalar floating-point code, in Debug with optimizations disabled, and with the laptop CPU in low-speed mode. So I just listened to some music for a while, confirmed the difference, dumped the results, fixed the minor bug that was causing the problem, and was back to speedy FFT goodness.

The wonderful thing about audio signal processing is that, even at 44KHz, the data rate is so low compared to video that you can get away with writing a truly awful and unoptimized version of an algorithm, and it still has a fairly decent chance of running full-speed on a modern CPU. A few years ago I might have had to wait for a WAV file to be written out, but now CPUs are so much faster that I can just launch the reference algorithm and compare. Cool.

Comments

Comments posted:


Any intuition about how short a signal has to be before doing 2 FFT's and one inverse FFT is slower than just cross-multiplying and adding all the terms?

Mike H (link) - 27 09 07 - 05:30

Comment form


Please keep comments on-topic for this entry. If you have unrelated comments about VirtualDub, the forum is a better place to post them.
Name:  
Remember personal info?

Email (Optional):
Your email address is only revealed to the blog owner and is not shown to the public.
URL (Optional):
Comment: /

An authentication dialog may appear when you click Post Comment. Simply type in "post" as the user and "now" as the password. I have had to do this to stop automated comment spam.



Small print: All html tags except <b> and <i> will be removed from your comment. You can make links by just typing the url or mail-address.