2
$\begingroup$

I am trying to synthesize sinusoids by using window function in the frequency domain.

It involves:

  1. In frequency domain, shift the window to center around the peak frequency
  2. To generate a DFT frame, sample a few values of the window around the peak as the spectral motif
  3. Inverse-Fourier transform the spectral motif, to generate the sinusoid in the desired frequency

This approach works great in general, except for synthesising low frequencies. Because when shifting the window to the low frequency, the left side of the window will sit in the negative frequency domain.

The figure in the middle demonstrates the issue (T(k) sits in the negative domain) figure

I found a solution here, it suggested to add the complex conjugate value of the left tail of the window (in the negative domain) to the DFT bin that’s on the right tail of the window (in the positive domain). Which I can’t make sense of, and following this solution creates even more distortion. So I wonder if anyone knows how to do it properly. Any suggestions would be very appreciated!

Some excerpt from the aforementioned solution:

The reflection about the k=0 axis is due to the specific embodiment described herein for synthesizing a sinusoid. For each real sinusoid, one peak exists in the positive frequency bins and another peak exists in the negative frequency bins. In the embodiment wherein only the peak in the positive frequency bins is synthesized, a peak centered about a low positive frequency bin spills into the negative frequencies (as shown by the plot for Ht(k−bc) in FIG. 3). Similarly, a peak centered about a low negative frequency bin spills into the positive frequencies. The portion of Ht(k−bc) in the negative frequencies that is reflected, or T*(−k), represents the portion of the peak centered about the negative frequency bin that spills into the positive frequencies.

PS. Some time ago I've raised this question on DSP-related forum. I've got very detailed suggestion from Robert, to ignore the bins lying on negative domain to specify the whole positive frequency, and then complex conjugate to reflect it to the negative frequency, which has improved the problem but it still can’t go down below 80 Hz. So I thought I’ll post again here.

$\endgroup$
  • $\begingroup$ How are you dealing with setting the 0 Hz bin? $\endgroup$ – Olli Niemitalo Jun 4 '15 at 19:46
  • $\begingroup$ @OlliNiemitalo based on the material I read, it should be 2 * real part of the associated value (the value sampled at 0 Hz) of the window function $\endgroup$ – Thinium Jun 4 '15 at 20:24
  • $\begingroup$ sometimes i wonder if frequency-domain synthesis is worth the effort. crossing all of the i's and dotting all of the t's is a pain in the ass. $\endgroup$ – robert bristow-johnson Jun 4 '15 at 22:19
  • $\begingroup$ Not an answer, but: When dealing with a related issue, I found the correct solution (for my issue) by realizing that the window is actually always reflected at 0Hz, and these two copies always overlap: Normally only the side-lobes do, which can be ignored if those are weak enough, but at 0 Hz they just happen to overlap completely. $\endgroup$ – Sebastian Reichelt Jun 5 '15 at 10:23
  • 1
    $\begingroup$ So I think a good way to figure out the "correct" solution is to first consider a variant of the Fourier transform that doesn't drop negative frequencies, and then figure out how to map the solution to a Fourier transform that does. Especially, you need to consider how the omission of negative frequencies is dealt with at the 0 Hz bin, which usually involves a factor of 2. $\endgroup$ – Sebastian Reichelt Jun 5 '15 at 10:26
3
$\begingroup$

You could use another approach: allow negative frequencies, do a complex IFFT, discard the imaginary parts of the time domain samples, and multiply the result by 2. Let's try it in Octave (MATLAB clone) with a motif $[1 + 2i, 3 + 4i, 5 + 6i, 7 + 8i]$ shifted so that its leftmost bin ($1 + 2i$) lands on a negative frequency. FFT length is 8. (I rewrote the results for readability.)

> g = [3 + 4i, 5 + 6i, 7 + 8i, 0, 0, 0, 0, 1 + 2i]
g =

   3 + 4i   5 + 6i   7 + 8i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   1 + 2i

> y = real(ifft(g))*2
y =

   4.00000  -0.89645  -2.00000   0.98223   1.00000  -1.60355   0.00000   4.51777

> fft(y)
ans =

   6 + 0i   6 + 4i   7 + 8i   0 + 0i   0 + 0i   0 + 0i   7 - 8i   6 - 4i

The same time-domain signal $y$ can be generated by synthesizing the first 5 bins of $\text{fft}(y)$ and feeding them to real IFFT (which I assume you use). The 3 remaining negative-frequency bins the IFFT kind of generates internally. You can follow these steps for the synthesis:

1) For each bin of the shifted motif that lands on a positive-frequency bin, copy the value verbatim. (You are already doing this)

2) For a bin of the shifted motif that lands on the 0 Hz bin, double its real part and write that to the 0 Hz bin, discarding the imaginary part, like $3 + 4i \rightarrow 6 + 0i$ in the example. (You are already doing this)

3) For each bin of the shifted motif that lands on a negative-frequency bin, add its complex conjugate (same real part, sign of imaginary part flipped) to the positive-frequency bin that is at the same distance from the 0 Hz bin. This will be one of the bins already written to in step 1. In the second bin of the example $5+6i$ and $\text{conj}(1 + 2i) = 1 - 2i$ were summed to get $6 + 4i$. Don't expect the imaginary parts to cancel, because even if the motif might be symmetrical, those two motif bins are not located symmetrically on the opposite sides of the motif, unless you are synthesizing a 0 Hz sinusoid. It is perfectly fine if the imaginary part remains non-zero; frequency domain bins can have complex values and still yield real-valued time-domain data.

Oh, and if the shifted motif reaches the Nyquist bin (corresponding to half the sampling frequency) or beyond, do exactly the same things there, mirroring around the Nyquist bin.

$\endgroup$
  • $\begingroup$ Could you please elaborate a bit about the last two sentences “don’t expect the imaginary parts to cancel…”? For example, if I complex conjugate a negative bin and add it to the positive side (as you said, the bin will be one that’s already written in step 1.), then this bin will have 2 times the real part of the original value, and the imaginary part gets cancelled out, right? It’s amazing that you already know what I am confused about without me mentioning it! Thanks in advance! $\endgroup$ – Thinium Jun 4 '15 at 22:20
  • $\begingroup$ Those two bins are not located symmetrically on opposite sides of the shifted motif. They are located symmetrically around 0 Hz. For example, if the leftmost bin of the shifted motif lands on the first negative frequency bin, you would add its complex conjugate to the first positive frequency bin. That would be where the 3rd leftmost bin of the motif was written to. It is very unlikely that the leftmost and the 3rd leftmost bins of the motif have identical values. $\endgroup$ – Olli Niemitalo Jun 5 '15 at 5:28
  • $\begingroup$ in your example it looks like a complex conjugate of the first half of the spectrum to the latter half is not necessary, right? As I am only dealing with frequency up to half of the sample rate. I assume only the first half of the spectrum will be filled (I've edited the original post with some psedo code to elaborate my attempt). Thanks! $\endgroup$ – Thinium Jun 5 '15 at 10:54
  • $\begingroup$ That's right. In the example I just take the real part in time domain. This is equivalent to doing the complex conjugate mirroring in frequency domain. $\endgroup$ – Olli Niemitalo Jun 5 '15 at 11:50
0
$\begingroup$

so, if you know what the window shape will be in the time-domain, then you know what the "motif" (i haven't thought of using that word) of the window is in the frequency domain. the Fourier transform of the window is your motif centered at DC (bin 0). at some point you need to truncate the sidelobes of the motif to zero. with a Gaussian window, the motif shape will also be Gaussian and will decay to zero rapidly on both sides and when it gets to, say, $10^{-9}$ or so, then you can truncate the Gaussian motif to zer0. if you want your sinusoid frequencies to have fractional-bin precision, you will need to be able to interpolate the motif at different fractional-bin offsets and maybe store a variety of slightly different motif templates for different fractional-bin offsets.

so, first start out by clearing your entire spectrum to 0. for each frequency component, you plop down a motif shifted to that frequency and, where the motif is non-zero, you must add it to the existing spectrum (which is initialized to zero). that means some of the tails of motifs of different sinusoidal frequencies will overlap. make sure you overlap-add and not just write over existing non-zero values in your spectrum.

do this for both the positive and negative frequency components of each real sinusoid.

if the frequency is so low that some of the tail of the motif extends past DC (bin 0) then allow that and add it in. i.e. the motif for the positive frequency component will extend into the negative frequencies and the reflected motif for the negative frequency component will extend into the positive frequencies. just do it and allow the tails to overlap and add whether they cross over to the other sign of frequencies or not.

$\endgroup$
  • $\begingroup$ I remember you mentioned in the DSP-related forum that this approach works well for chirp-like sound. (ps. I am using the concatenate approach from jean laroche, not overlap-add) I notice that if I modulate the frequency or amplitude rapidly, there is crackles in the signal. Is this an unavoidable artefact? $\endgroup$ – Thinium Sep 20 '15 at 16:25
0
$\begingroup$

Thanks so much olli! It works! To do it with real fft, just follow these 3 steps described by Olli, then complex conjugate the first half of the spectrum to the latter half.

Extending Olli's example:

With the spectral motif [1 + 2i , 3 + 4i, 5 + 6i, 7 + 8i] and fft size of 8, after doing what olli said you'll first get:

[6 + 0i, 6 + 4i, 7 + 8i, 0 + 0i, 0 + 0i, 0 + 0i, 0 + 0i, 0 + 0i]

Then perform a complex conjugate of the first 4 bins to the latter half:

[6 + 0i, 6 + 4i, 7 + 8i, 0 + 0i, 0 + 0i, 0 + 0i, 7 - 8i, 6 - 4i]

Then perform ifft, which should give you real-valued time-domain data.

$\endgroup$
  • 1
    $\begingroup$ One correction: "Latter half" should exclude the Nyquist bin as it was dealt with separately by doubling the real part and zeroing the imaginary part. $\endgroup$ – Olli Niemitalo Jun 7 '15 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.