2
$\begingroup$

Let $N\in \mathbb{N}$. I am looking for a non-zero scalar $\lambda$ and a nonzero vector

$$f=(f(0),f(1),\cdots,f(N-1)) \in \mathbb{C}^N$$ satisfying the following equations for $l=0,\cdots,N-1$:

$$\hat{f}(l)=\lambda e^{\frac{l\pi}{N}i}f(N-l).$$

$\hat{f}$ is just the Fourier transform of $f$ and it is assumed $f(N)=f(0)$.

$\endgroup$
2
  • 1
    $\begingroup$ Where does this arise from?`Why did you tag it spread-spectrum and signal-analysis? What have you tried? Where did you get stuck? $\endgroup$ Jun 12, 2021 at 13:42
  • $\begingroup$ i'm voting to keep this question open. I i prefer more like the electrical engineering notation. what is it that they're looking for? $$ \text{(DFT)} \qquad \qquad \mathscr{F}\Big\{ x[n] \Big\} = X[k]$$ where $X[k] = x[k+k_0]$ ? $\endgroup$ Jun 12, 2021 at 16:19

3 Answers 3

1
$\begingroup$

A Gaussian might work. If you do $x[n] = e^{-jn^2/\sigma}$ with $\sigma = N/\pi$ you get $X(k) = \sqrt{N}x[k]$ assuming it's a periodic sequence anyway and you run your time & frequency indices from $-N/2$ to $N/2-1$

Since it's symmetric in both domains you automatically get $X[k] = \sqrt{N}x[N-k]$ as well.

I'm not quite sure what to do with $e^{j\pi\frac{k}{N}} = (-1)^k$

Time shifting by N/2 will modulate the frequency response by $(-1)^k$ but then you have to shift the frequency response as well which modulates the time domain signal. So it's almost there but not quite. Maybe the right combination of modulation and shifting in both domains will do the trick.

$\endgroup$
5
  • $\begingroup$ i think you need to overlap the tails of the gaussian as you periodically extend it to make it work for the DFT. like: $$ x[n] = \sum\limits_{m=-\infty}^{\infty} e^{-j \pi (n - mN)^2/(\sigma N)} $$ $\endgroup$ Jun 12, 2021 at 17:25
  • $\begingroup$ That is only a problem is $N$ is very small . Even for N = 32 the tail is down to about $10^{-10}$ $\endgroup$
    – Hilmar
    Jun 12, 2021 at 18:25
  • $\begingroup$ What is the relationship between $k$ and $n$ in your assertion that $X(k) = \sqrt{N}x[n]$? $\endgroup$ Jun 13, 2021 at 14:48
  • $\begingroup$ @DilipSarwate: sloppy notation on my part. They should be the same index, i.e. $X(m) = k\cdot x(m)$ I fixed it $\endgroup$
    – Hilmar
    Jun 14, 2021 at 0:02
  • $\begingroup$ i dunno what to do with $e^{j\pi\frac{k}{N}} = (-1)^{k/N} $ either. $\endgroup$ Jun 17, 2021 at 5:20
1
$\begingroup$

Okay, I am going to answer this question in two parts. The first part will be in the continuous-time and continuous-frequency domains (the regular Fourier Transform). I will use the "ordinary frequency" definition (that electrical engineers like to use) of the continuous-time Fourier Transform:

$$ \mathscr{F}\Big\{x(t)\Big\} \triangleq X(f) = \int\limits_{-\infty}^{\infty}x(t)\, e^{-j 2 \pi f t} \,\mathrm{d}t$$

$$ \mathscr{F}^{-1}\Big\{X(f)\Big\} \triangleq x(t) = \int\limits_{-\infty}^{\infty}X(f)\, e^{j 2 \pi f t} \,\mathrm{d}f$$

Note the symmetry between the forward and inverse Fourier transforms. They are, in a very important sense, exactly the same. This is because $-j$ and $+j$ have the same claim to squaring to be $-1$. If all textbooks and literature was changed so that every occurrence of $+j$ was replaced with $-j$ (and vise versa), every equation, every theorem, every derived fact would be just as true.

Now there is this Duality Theorem that says if:

$$ X(f) = \mathscr{F}\Big\{x(t)\Big\} $$

then

$$ x(-f) = \mathscr{F}\Big\{X(t)\Big\} $$

Note that all we're doing is swapping the roles of $f$ and $t$ and applying a ($-$) minus sign to one or the other (above it's $f$). That minus sign is necessary because while $-j$ and $+j$ are qualitatively the same, they are negatives of each other and they are not zero.

So, adjusting the notation a little, if we define $x_n(\cdot)$ like this:

$$\begin{align} x_1(f) &= \mathscr{F}\Big\{x_0(t)\Big\} \\ x_2(f) &= \mathscr{F}\Big\{x_1(t)\Big\} \\ x_3(f) &= \mathscr{F}\Big\{x_2(t)\Big\} \\ x_4(f) &= \mathscr{F}\Big\{x_3(t)\Big\} \\ \end{align} $$

Then you will see that $x_4(t) = x_0(t)$ for any $x_0(\cdot)$ that isn't pathologically (or "funkily") defined.

So, given any $x_0(\cdot)$, and the relationships above, if you define

$$ x(t) \triangleq x_0(t) + x_1(t) + x_2(t) + x_3(t) $$

then the Fourier Transform does not change $x(t)$.

$$ x(f) = \mathscr{F}\Big\{x(t)\Big\} $$

The function is exactly the same, you just changed the $t$ to an $f$.

Now the next part will be adjusting this to the Discrete Fourier Transform, because your question is about the DFT.

$\endgroup$
5
  • $\begingroup$ I am eagerly awaiting the modifications that you are going to make for the DFT since the DFT is not a unitary transform the way the continuous-time Fourier Transform is, at least for us benighted folks who prefer $f$ to $\omega$ (unlike most participants and readers of dsp.SE). $\endgroup$ Jun 15, 2021 at 14:04
  • $\begingroup$ Isn't this unitary? $$ X[k] \triangleq \frac{1}{\sqrt{N}} \sum\limits_{n=0}^{N-1} x[n] e^{-j2\pi nk/N} $$ $\endgroup$ Jun 15, 2021 at 14:50
  • $\begingroup$ Yes, but that is not the usual definition of the DFT. $\endgroup$ Jun 15, 2021 at 14:53
  • $\begingroup$ Yeah, but the OP has that $\lambda$ factor that we can dink around with. $\endgroup$ Jun 15, 2021 at 14:59
  • 1
    $\begingroup$ Very nice approach. $\endgroup$
    – ABB
    Jun 21, 2021 at 11:12
1
$\begingroup$

So now we're changing this to the Discrete Fourier Transform and we're gonna reach only half as far and I will use the "unitary" DFT scaling (which is not common) so that the symmetry between the discrete-time and discrete-frequency domain remains:

$$ \mathscr{F}\Big\{x[n]\Big\} \triangleq X[k] = \frac{1}{\sqrt{N}} \sum\limits_{n=0}^{N-1}x[n]\,e^{-j 2 \pi \frac{nk}{N}} $$

$$ \mathscr{F}^{-1}\Big\{X[k]\Big\} \triangleq x[n] = \frac{1}{\sqrt{N}} \sum\limits_{k=0}^{N-1}X[k]\,e^{j 2 \pi \frac{nk}{N}} $$

Note the symmetry between the forward and inverse discrete Fourier transforms. Now the mapping above in both cases is from one periodic discrete sequence of length $N$ in one domain to another periodic discrete sequence of the same length $N$ in the reciprocal domain.

$$ x[n+N] = x[n] \qquad \forall n \in \mathbb{Z} $$ $$ X[k+N] = X[k] \qquad \forall k \in \mathbb{Z} $$

The Duality Theorem says if:

$$ X[k] = \mathscr{F}\Big\{x[n]\Big\} $$

then

$$ x[-k] = \mathscr{F}\Big\{X[n]\Big\} $$

or (because of periodicity)

$$ x[N-k] = \mathscr{F}\Big\{X[n]\Big\} $$

Note that all we're doing is swapping the roles of $k$ and $n$ and applying a ($-$) minus sign to one or the other (above it's $k$).

If we define $x_m[\cdot]$ like this:

$$\begin{align} x_1[k] &= \mathscr{F}\Big\{x_0[n]\Big\} \\ x_2[k] &= \mathscr{F}\Big\{x_1[n]\Big\} \\ \end{align} $$

Then you will see that $x_2[n] = x_0[-n]$ for any $x_0[\cdot]$,

So, given any $x_0[\cdot]$, and the relationships above, if you define

$$ x[n] \triangleq x_0[n] + x_1[n] $$

then the DFT does not change $x[n]$ except for reversing $n$.

$$ x[k] = \mathscr{F}\Big\{x[-n]\Big\} $$

The function is exactly the same, you just changed the $-n$ to $k$.

or (because of periodicity)

$$ x[N-k] = \mathscr{F}\Big\{x[n]\Big\} $$

$\endgroup$
2
  • $\begingroup$ It is surprising that you need only two $x_i$ in the discrete case but four $x_i$ in the continuous case. Also, if one uses the "regular" DFT instead of the unitary DFT that you choose to use, the OP's $\lambda$ will likely work out to be $\sqrt{N}$ as in @Hilmar's answer. $\endgroup$ Jun 17, 2021 at 14:39
  • $\begingroup$ no, @DilipSarwate , what happened was that i re-read the OP and noticed the time reversal posed in the question. Two Fourier transforms will reverse $x(t)$ to $x(-t)$. Two more will flip it back to $x(t)$. in fact i copied and modified the whole thing for my second answer: $$ x[k] = \mathscr{F}\Big\{x[n]\Big\} $$ and was about to apply the periodicity thing to add that $N$ to it. then i noticed that it was $$ x[k] = \mathscr{F}\Big\{x[N-n]\Big\} $$ so i had to take out two passes and use periodicity to add the offset $N$. $\endgroup$ Jun 17, 2021 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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