Alternating sign after Discrete Fourier transform

Question

Let me start by saying that this question is motivated by data analysis that I am doing. Its part of a much larger set of signal processing operations, but in order to keep the question contained I'll talk only about what (to my best knowledge) is relevant.

The scenario is as follows: we start from some discrete dataset $u$ of size $N$ in the time domain, $u ={u_1,u_2,\dots,u_N}$. From observation one finds that this dataset has some special properties: every odd value is purely real, and every even value is purely imaginary. If I subsequently compute the discrete Fourier transform of this dataset given by $v ={v_1,v_2,\dots,v_N}$ where \begin{equation} v_s=\frac{1}{\sqrt{N}}\sum_{r=1}^{N}u_r\exp{\left[2\pi i (r-1)(s-1)/n\right]} \end{equation}

I find that I obtain a curious result: the outcome $v$ is almost purely real, and the even and odd values alternate in sign: $\mathrm{sgn}{(v_s)}=-\mathrm{sgn}{(v_{s+1})}$. With this first part I mean that the real data is $\mathcal{O}(10^{-4})$ and the imaginary part is $\mathcal{O}(10^{-12})$; I'd say is purely from numerical errors.

However, it is this second aspect that is not obvious to me; why do the real values alternate in sign? For those who appreciate some visual aspects, the real part of the Fourier transform ($\mathrm{Re}(v)$) looks like this . Note that the first quarter is a mirror image of the second, and the third of the fourth; this is a different point that is not entirely relevant.

Note that an answer could also definitely be that, given the above, there is no explanation. I am not posting the entire dataset as its rather large and makes the question messy, but perhaps I am missing a crucial ingredient. In that case I will edit it to make it more complete.

Answer 1

Let's suppose that your original data, $u_n$, has been windowed (which is something you might typically do, in order to 'tidy up' the FFT). In this case, most of the energy in your input data sequence is clustered around the region near $n=N/2$. To be more specific, I expect that your input data is actually centred on $n=N/2+1$.

Now, look at your expression for the FFT, and imagine that all the $u_n$ are zero, except $u_{N/2+1}=1$. This means that:

$v_s=\frac{1}{N}\sum_{r=1}^N u_r \exp[2\pi i(r−1)(s−1)/n] = \frac{1}{N} \exp[2\pi i(N/2)(s-1)] = \frac{1}{N} (-1)^{s-1}$

In other words, the sign-flipping behaviour of your FFT output is generally related to the fact that the energy of you input sequence, $u_n$, is clustered around time $N/2$.

Ideally, you'd like to have your energy clustered around time zero, and in order to do this, you could shift your signal $N/2$ samples to the left (this should be a circular shift, so that the data wraps around in the buffer). In practice, you don't bother with the circular shift, and instead you simply swap the sign of all the odd FFT bins, which does exactly the same thing as shifting the data in the time domain.

Also, if your FFT output is real, this implies that your time-domain input is Hermitian. This means that there is a particular symmetry in your input data, $u_n$, such that the real part of the input satisfies:

$Re(u_{N/2+1+k}) = Re(u_{N/2+1-k})$ for all $k$ $\quad\leftarrow$ This means that the real part is even

and the odd part satisfies:

$Im(u_{N/2+1+k}) = -Im(u_{N/2+1-k})$ for all $k$ $\quad\leftarrow$ This means that the imaginary part is odd

If you look at your data (the $u_n$ values) you should see this property. You will find that $u_{N/2+1-2}$ (which is real, according to your description) will be equal to $u_{N/2+1+2}$. Furthermore, $u_{N/2+1-1}$ (which is imaginary, according to your description) will be equal to $-u_{N/2+1+1}$.

Answer 2

To arrive at any data set $y[k]$ for which "every odd value is purely real, and every even value is purely imaginary" there is always some real $x[k]$ such that:

$$y[k] = x[k]e^{i\pi k} = x[k]\times[1, i, -1, -i, ...]$$

In the frequency domain, that operation is convolution of a sequence with Hermitian symmetry (because $x[k]$ is real) by a sequence $[0, 0, \dots, 0, 0, 1, 0, 0, \dots, 0, 0]$, where the value $1$ is at frequency bin $\pi/2$. That is simply a cyclic shift. For example if the discrete Fourier transform (DFT) is of length 8, in the frequency domain this takes place:

$$[A B C D E \overline D \overline C \overline B]*[0\, 0\, 1\, 0\, 0\, 0\, 0\, 0] = [\overline C \overline B A B C D E \overline D],$$

where the overline denotes complex conjugation and $A$ and $E$ are real and the other variables complex. Now for the right side of the equation to match your observation that the result should be "almost purely real, and the even and odd values alternate in sign", at least $C$ and $B$ should be real and have alternating signs. But they are free to be complex. So the properties that you observed must stem from other constraints on your original data that you have not disclosed. I did not verify your discrete Fourier transform implementation.