Thread: [Alsa-user] multichannel multiband FFT-based equalizer - README
Brought to you by:
perex
Menu
▾
▴
alsa-user
|
From: Sergei S. <ste...@li...> - 2006-01-02 17:58:45
Attachments:
README.multichannel_multiband_equalizer.txt
|
Hello All, please find the promised multichannel multiband FFT-based equalizer. Attached is README.multichannel_multiband_equalizer.txt files. Part two to follow will contain source tarball. Regards, Sergei. |
|
From: fons a. <fon...@sk...> - 2006-01-02 21:30:31
|
On Mon, Jan 02, 2006 at 07:58:57PM +0200, Sergei Steshenko wrote: > The existence of spectral resolution prevents end user from having > arbitrary central band frequencies in DFT-based equalizers, central frequencies > can only be a multiple of spectral resolution. Not true, you can have arbitrary central frequencies. You can even sweep them. But you can't have two independent bands that are closer than Fs/N (or more if windowing is taken into account). -- FA |
|
From: Sergei S. <ste...@li...> - 2006-01-02 21:37:36
|
So, how are going to implement a central frequency which is not a multiple of (Fs / N) in a DFT equalizer ? That is, what data resulting from direct DFT represents such frequencies ? On Mon, 2 Jan 2006 22:36:21 +0100 fons adriaensen <fon...@sk...> wrote: > On Mon, Jan 02, 2006 at 07:58:57PM +0200, Sergei Steshenko wrote: > > > The existence of spectral resolution prevents end user from having > > arbitrary central band frequencies in DFT-based equalizers, central frequencies > > can only be a multiple of spectral resolution. > > Not true, you can have arbitrary central frequencies. You can even sweep them. > But you can't have two independent bands that are closer than Fs/N (or more > if windowing is taken into account). > > -- > FA > > > |
|
From: fons a. <fon...@sk...> - 2006-01-02 22:47:38
|
On Mon, Jan 02, 2006 at 11:37:54PM +0200, Sergei Steshenko wrote: > So, how are going to implement a central frequency which is > not a multiple of (Fs / N) in a DFT equalizer ? > > That is, what data resulting from direct DFT represents such frequencies ? A weighted sum of some DFT outputs, instead of just one of them. Look at what you have now. You do a forward FFT and get N complex values A [i]. You multiply each of these A [i] by some factor, and then do an IFFT. The second step can be regarded as the multiplication of the vector A [i] by a diagonal matrix. Using central frequencies in between the 'integer' bins would just mean this matrix is no longer diagonal. In practice it would become a band matrix and still be quite sparse, and the product can be done efficiently. Once you have the matrix instead of the term by term product, the windowing can also be absorbed into it. -- FA |
|
From: Sergei S. <ste...@li...> - 2006-01-02 23:22:40
|
Regarding "A weighted sum of some DFT outputs" - do you agree that if, say, I have an 8 point FFTW, the following frequencies are represented in the FFTW output array C (the result of time -> frequency conversion, i.e. direct FFT): C[0] <=> DC (only real part) C[1], C[7] <=> 1 * Fs / 8; C[2], C[6] <=> 2 * Fs / 8; C[3], C[5] <=> 3 * Fs / 8; C[4] <=> 4 * Fs / 8; Nyquist frequency (only imaginary part) ? If yes, do you agree that no SINGLE C-array element represents, say 1.5 * Fs / 8 frequency ? If yes, do you agree that changing simultaneously gain of C[1], C[7] and C[2], C[6] pairs. i.e of the pairs that represent (1 * Fs / 8) and (2 * Fs / 8) pairs I will not only change gain of (1.5 * Fs / 8) frequency, but also of the whole 1 * Fs / 8) .. (2 * Fs / 8) frequency range ? If yes, do you agree that had I wanted to change only gain of, say, (2 * Fs / 8), i.e amplitude of (C[2], C[6]) I wouldn't have changed the amplitude of, say, (1 * Fs / 8) spectral component or any other spectral component for that matter ? If yes, that's what I meant saying that central frequencies should be a multiple of frequency resolution ((Fs / 8) in this example). If central frequency is not a multiple of frequency resolution, its amplitude can NOT be changed without affecting the amplitude of other spectral components. On Mon, 2 Jan 2006 23:53:33 +0100 fons adriaensen <fon...@sk...> wrote: > On Mon, Jan 02, 2006 at 11:37:54PM +0200, Sergei Steshenko wrote: > > > So, how are going to implement a central frequency which is > > not a multiple of (Fs / N) in a DFT equalizer ? > > > > That is, what data resulting from direct DFT represents such frequencies ? > > A weighted sum of some DFT outputs, instead of just one of them. > > Look at what you have now. You do a forward FFT and get N complex > values A [i]. You multiply each of these A [i] by some factor, and > then do an IFFT. > > The second step can be regarded as the multiplication of the vector > A [i] by a diagonal matrix. Using central frequencies in between > the 'integer' bins would just mean this matrix is no longer diagonal. > In practice it would become a band matrix and still be quite sparse, > and the product can be done efficiently. > > Once you have the matrix instead of the term by term product, the > windowing can also be absorbed into it. > > -- > FA > > > > > |
|
From: fons a. <fon...@sk...> - 2006-01-03 00:19:38
|
On Tue, Jan 03, 2006 at 01:22:56AM +0200, Sergei Steshenko wrote: > - do you agree that if, say, I have an 8 point FFTW, the following > frequencies are represented in the FFTW output array C (the result of time -> > frequency conversion, i.e. direct FFT): > > C[0] <=> DC (only real part) > C[1], C[7] <=> 1 * Fs / 8; > C[2], C[6] <=> 2 * Fs / 8; > C[3], C[5] <=> 3 * Fs / 8; > C[4] <=> 4 * Fs / 8; Nyquist frequency (only imaginary part) Yes, except that it's the cosine (real) part of Fs/2, that is in C[4]. > If yes, do you agree that no SINGLE C-array element represents, say > 1.5 * Fs / 8 frequency ? Yes. > If yes, do you agree that changing simultaneously gain of > C[1], C[7] and C[2], C[6] pairs. i.e of the pairs that represent > (1 * Fs / 8) and (2 * Fs / 8) pairs I will not only change gain > of (1.5 * Fs / 8) frequency, but also of the whole > 1 * Fs / 8) .. (2 * Fs / 8) frequency range ? Yes. This is no different from changing only one value - it represents more than just the exact central frequency (you'd have a very bad equaliser otherwise !). The minimum bandwidth you can make is Fs/N, and a bit more with windowing. You may have some difficulty in believing that a 'non-integer' band could have the same bandwidth as an 'integer' one, but it *is* possible, and even quite straightforward. Look at it like this: there is no essential difference between the time and the frequency domains, they are 'duals'. Just as you can delay a sampled signal by half (or any fraction of) a sample by interpolation and without impairing bandwidth (i.e. resolution in the time domain), you can interpolate in the frequency domain without impairing resolution. The output of a DFT is just 'samples in the frequency domain', like the input is 'samples in the time domain'. Or one more variation: you say "no SINGLE C-array element represents, say 1.5 * Fs / 8 frequency", and that is correct. In the same way, in a sampled signal, no single sample represents the value of the original analog signal halfway between samples i and i+1. It is represented by all surrounding samples, with sin(x)/x weighting. And it can be reconstructed. The same is true in the frequency domain. -- FA |
|
From: Bill U. <un...@ph...> - 2006-01-03 00:52:50
|
On Tue, 3 Jan 2006, fons adriaensen wrote: > On Tue, Jan 03, 2006 at 01:22:56AM +0200, Sergei Steshenko wrote: > >> - do you agree that if, say, I have an 8 point FFTW, the following >> frequencies are represented in the FFTW output array C (the result of time -> >> frequency conversion, i.e. direct FFT): >> >> C[0] <=> DC (only real part) >> C[1], C[7] <=> 1 * Fs / 8; >> C[2], C[6] <=> 2 * Fs / 8; >> C[3], C[5] <=> 3 * Fs / 8; >> C[4] <=> 4 * Fs / 8; Nyquist frequency (only imaginary part) > > Yes, except that it's the cosine (real) part of Fs/2, that is in C[4]. It depends on how your particular fourier transform stores the elements. > >> If yes, do you agree that no SINGLE C-array element represents, say >> 1.5 * Fs / 8 frequency ? It does not exist. A discrete fourier transform has only integer parts. > > Yes. > >> If yes, do you agree that changing simultaneously gain of >> C[1], C[7] and C[2], C[6] pairs. i.e of the pairs that represent >> (1 * Fs / 8) and (2 * Fs / 8) pairs I will not only change gain >> of (1.5 * Fs / 8) frequency, but also of the whole >> 1 * Fs / 8) .. (2 * Fs / 8) frequency range ? What do you mean by those? They do not exist in the discrete transform. If you want to define them, then that transform depends on all of the discrete transforms. > > Yes. This is no different from changing only one value - it represents > more than just the exact central frequency (you'd have a very bad equaliser > otherwise !). The minimum bandwidth you can make is Fs/N, and a bit more > with windowing. You may have some difficulty in believing that a 'non-integer' > band could have the same bandwidth as an 'integer' one, but it *is* possible, > and even quite straightforward. > > Look at it like this: there is no essential difference between the time > and the frequency domains, they are 'duals'. Just as you can delay a > sampled signal by half (or any fraction of) a sample by interpolation > and without impairing bandwidth (i.e. resolution in the time domain), > you can interpolate in the frequency domain without impairing resolution. Sure you can interpolate. but that is not very useful. You could extend the range (eg doubling it with zeros) and get an interpolation. But that interpolation is a fourier transform of your signal extrapolated by zeros. It is NOT the value the transform would have if you had actually recorded twice as much of the signal. > The output of a DFT is just 'samples in the frequency domain', like the > input is 'samples in the time domain'. Well, no. it is no. The discrete transform of a finite range of a signal is not the same as a discrete sample of the transform of a longer span of the signal. It is NOT just "samples in the frequency domain". > > Or one more variation: you say "no SINGLE C-array element represents, > say 1.5 * Fs / 8 frequency", and that is correct. In the same way, > in a sampled signal, no single sample represents the value of the > original analog signal halfway between samples i and i+1. It is > represented by all surrounding samples, with sin(x)/x weighting. > And it can be reconstructed. The same is true in the frequency domain. No and No. Once you have made teh discrete sampling you have lost the original signal. It is gone. You cannot reconstruct it. IF you assume that the original signal is frequency limited, then you may be able to reconstruct it. > > -- William G. Unruh | Canadian Institute for| Tel: +1(604)822-3273 Physics&Astronomy | Advanced Research | Fax: +1(604)822-5324 UBC, Vancouver,BC | Program in Cosmology | un...@ph... Canada V6T 1Z1 | and Gravity | www.theory.physics.ubc.ca/ |
|
From: fons a. <fon...@sk...> - 2006-01-03 01:14:24
|
On Mon, Jan 02, 2006 at 04:52:42PM -0800, Bill Unruh wrote: > Once you have made teh discrete sampling you have lost the original signal. > It is gone. You cannot reconstruct it. > IF you assume that the original signal is frequency limited, then you may > be able to reconstruct it. Sigh. Of course it's assumed to be limited in frequency. Should I really restate obvious preconditions each time ? A frequency limited signal can be represented by and reconstructed from a finite number of samples per time unit. (Shannon) Dual: A time limited spectrum can be represented by and reconstructed from a finite number of samples per frequency unit. I didn't invent any of this. Hundreds of thousands of engineers have been capable of understanding it. I'll gladly admit it has taken me some time to do the same. I'm sure you will be able to follow. Just think. Please. -- FA |
|
From: Sergei S. <ste...@li...> - 2006-01-03 01:12:34
|
Fons, when I said "central frequencies" I meant the frequencies which can be reproduced exactly using one direct DFT and one inverse DFT buffer. That is, I claim that for the 8 points DFT/FFT example I gave if input signal contains only 0 * Fs / 8 1 * Fs / 8 2 * Fs / 8 3 * Fs / 8 frequencies, i.e if it is periodic band limited signal, it can be reproduced with infinite precision (provided calculations are infinitely precise) using only one 8-element array. Any other signal, even if it is band limited, can not be reproduced precisely using only one 8-element array because that signal is not a periodic function with the (4 / Fs) period. Look at this another way. For the small 8 points FFT example one can build at maximum 4-band equalizer with 0 * Fs / 8 1 * Fs / 8 2 * Fs / 8 3 * Fs / 8 central frequencies Any attempt to increase the number of central frequencies will cause ambiguity, or, as you said, "The minimum bandwidth you can make is Fs/N" . My choice of central frequencies means I'm using the strict subset of the maximum number of them - 4 in this example. I know about interpolation, resampling and stuff like that, but it is not what a simple FFT-based equalizer is doing. And yes, you are correct regarding "Yes, except that it's the cosine (real) part of Fs/2, that is in C[4].", though it doesn't change the point. My point was that with an IIR-based equalizer central frequency can really be chosen to have whatever value in 0..Fs/2 range, I mean, the bandpass IIRs can be built that their magnitude maximum will be at really arbitrary value in 0..Fs/2 range, and their Q factor can be made arbitrary high (I mean infinite precision computer arithmetics) - it's not the case with DFT when N is limited. In the IIR case moral equivalent of limited N is limited IIR filter order, still, its resonance frequency can be whatever in 0..Fs/2 range. In the case of DFT limited N means both limited Q and discrete central frequencies in the terms of precise signal restoration. Regards, Sergei. P.S, I've just seen a very good reply from Bill Unruh: http://article.gmane.org/gmane.linux.alsa.user/21688 . On Tue, 3 Jan 2006 01:25:39 +0100 fons adriaensen <fon...@sk...> wrote: > On Tue, Jan 03, 2006 at 01:22:56AM +0200, Sergei Steshenko wrote: > > > - do you agree that if, say, I have an 8 point FFTW, the following > > frequencies are represented in the FFTW output array C (the result of time -> > > frequency conversion, i.e. direct FFT): > > > > C[0] <=> DC (only real part) > > C[1], C[7] <=> 1 * Fs / 8; > > C[2], C[6] <=> 2 * Fs / 8; > > C[3], C[5] <=> 3 * Fs / 8; > > C[4] <=> 4 * Fs / 8; Nyquist frequency (only imaginary part) > > Yes, except that it's the cosine (real) part of Fs/2, that is in C[4]. > > > If yes, do you agree that no SINGLE C-array element represents, say > > 1.5 * Fs / 8 frequency ? > > Yes. > > > If yes, do you agree that changing simultaneously gain of > > C[1], C[7] and C[2], C[6] pairs. i.e of the pairs that represent > > (1 * Fs / 8) and (2 * Fs / 8) pairs I will not only change gain > > of (1.5 * Fs / 8) frequency, but also of the whole > > 1 * Fs / 8) .. (2 * Fs / 8) frequency range ? > > Yes. This is no different from changing only one value - it represents > more than just the exact central frequency (you'd have a very bad equaliser > otherwise !). The minimum bandwidth you can make is Fs/N, and a bit more > with windowing. You may have some difficulty in believing that a 'non-integer' > band could have the same bandwidth as an 'integer' one, but it *is* possible, > and even quite straightforward. > > Look at it like this: there is no essential difference between the time > and the frequency domains, they are 'duals'. Just as you can delay a > sampled signal by half (or any fraction of) a sample by interpolation > and without impairing bandwidth (i.e. resolution in the time domain), > you can interpolate in the frequency domain without impairing resolution. > The output of a DFT is just 'samples in the frequency domain', like the > input is 'samples in the time domain'. > > Or one more variation: you say "no SINGLE C-array element represents, > say 1.5 * Fs / 8 frequency", and that is correct. In the same way, > in a sampled signal, no single sample represents the value of the > original analog signal halfway between samples i and i+1. It is > represented by all surrounding samples, with sin(x)/x weighting. > And it can be reconstructed. The same is true in the frequency domain. > > -- > FA > |
|
From: fons a. <fon...@sk...> - 2006-01-03 01:21:58
|
On Tue, Jan 03, 2006 at 03:12:50AM +0200, Sergei Steshenko wrote: > In the case of DFT limited N means both limited Q and discrete > central frequencies in the terms of precise signal restoration. It means limited Q, but no discrete central frequencies. BTW, I've used such 'interpolated frequency' filters many times in my professional work, and they are also in JAAA. Bye for now ! -- FA |
|
From: Sergei S. <ste...@li...> - 2006-01-03 01:43:38
|
Fons, regarding, " It means limited Q, but no discrete central frequencies. " - please implement in the given 8 points example a filter an equalizer, changing 1.5 * Fs / 8, but not affecting other frequencies. To be more versatile: Case_1: input signal is sin(2 * PI * 1 * Fs / 8) + sin(2 * PI * 2 * Fs / 8) Case_2: sin(2 * PI * 1 * Fs / 8) + sin(2 * PI * 1.5 * Fs / 8) + sin(2 * PI * 2 * Fs / 8) . I claim that if I select central frequencies as 1 * Fs / 8 2 * Fs / 8 , them for changing gain of (1 * Fs / 8) will only change amplitude of sin(2 * PI * 1 * Fs / 8), but not of sin(2 * PI * 2 * Fs / 8); changing gain of o(2 * Fs / 8) will change amplitude of sin(2 * PI * 2 * Fs / 8), but not of sin(2 * PI * 1 * Fs / 8); in both cases of gain change in case of Case_2 amplitude of sin(2 * PI * 1.5 * Fs / 8) will change. Whatever implementation of yours should be limited to simple FFT-based equalizer similar to the one I published. That is, data from no more than two adjacent FFT buffers can be used. Thanks in advance, Sergei. On Tue, 3 Jan 2006 02:27:46 +0100 fons adriaensen <fon...@sk...> wrote: > On Tue, Jan 03, 2006 at 03:12:50AM +0200, Sergei Steshenko wrote: > > > In the case of DFT limited N means both limited Q and discrete > > central frequencies in the terms of precise signal restoration. > > It means limited Q, but no discrete central frequencies. > BTW, I've used such 'interpolated frequency' filters many times > in my professional work, and they are also in JAAA. > > Bye for now ! > > -- > FA > > > > > > ------------------------------------------------------- > This SF.net email is sponsored by: Splunk Inc. Do you grep through log files > for problems? Stop! Download the new AJAX search engine that makes > searching your log files as easy as surfing the web. DOWNLOAD SPLUNK! > http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click > _______________________________________________ > Alsa-user mailing list > Als...@li... > https://lists.sourceforge.net/lists/listinfo/alsa-user > |
|
From: fons a. <fon...@sk...> - 2006-01-03 01:55:36
|
Sergei, > Whatever implementation of yours should be limited to simple > FFT-based equalizer similar to the one I published. That is, > data from no more than two adjacent FFT buffers can be used. I will take up this challenge, but not immediately. Right now, I'm working until almost 3 hours after midnight to finish my papers for LAC2006. After that it will be the same to finish the code... Hint: if you want to boost e.g. 8.5 * Fs / N, you should not only boost bins 8 and 9, but also *decrease* the gain in 7 and 10. Look at the values of sin(x)/x for x = (i + 0.5) * pi. -- FA (going to sleep now) |
|
From: Sergei S. <ste...@li...> - 2006-01-03 02:11:13
|
Fons, we are making rounds I want JUST to increase amplitude of 8.5 * Fs / N, and not to touch anything else. Your suggestion to "also *decrease* the gain in 7 and 10" will change amplitudes of 7 and 10, and that's exactly what I want to avoid. I am trying to say that if one uses ONLY (k * Fs / (2 * N)) frequencies (0 <= k <= N/2) discrete Fourier transform behaves the same way as classical continuous Fourier transform. Whenever other frequencies are used, all kinds of artifacts come. So, if you are going to implement the code using "also *decrease* the gain in 7 and 10" approach, you've already failed the contest, because I asked " please implement in the given 8 points example a filter an equalizer, changing 1.5 * Fs / 8, but not affecting other frequencies " - please pay attention to "but not affecting other frequencies" part. Even more, "boost bins 8 and 9" is also against the request to change gain of only 8.5. Regards, Sergei. On Tue, 3 Jan 2006 03:01:17 +0100 fons adriaensen <fon...@sk...> wrote: > Sergei, > > > Whatever implementation of yours should be limited to simple > > FFT-based equalizer similar to the one I published. That is, > > data from no more than two adjacent FFT buffers can be used. > > I will take up this challenge, but not immediately. Right now, > I'm working until almost 3 hours after midnight to finish my > papers for LAC2006. After that it will be the same to finish > the code... > > Hint: if you want to boost e.g. 8.5 * Fs / N, you should not only > boost bins 8 and 9, but also *decrease* the gain in 7 and 10. > Look at the values of sin(x)/x for x = (i + 0.5) * pi. > > -- > FA (going to sleep now) > > > > |
