0
$\begingroup$

Given a discrete signal $ \left\{ x[n] \right\}_{n=0}^{N-1} $ and its Discrete Fourier Transform $ X[k] = DFT \left\{ x[n] \right\}[k] $.

I'd like to effectively compute the norm of each sample of the DFT, namely $ \left | X[k] \right | ^ {2} , k \in \left\{ 0, N-1 \right\}$ as opposed to the norm of the DFT series (Which equals the norm of the original series).

Could that be calculated without using complex multiplications (Since it's real)?
Namely, I'd like to not have to go through the calculation of the DFT and then calculate the norm of each sample.
What if $ x[n] $ is also a symmetric signal (Auto correlation for that matter), I assume then using the Cosine part makes it possible?

Thank You.

$\endgroup$
  • $\begingroup$ For how many values of $k$ do you want to compute $|X[k]|^2$? Or do you actually want the sum over all $|X[k]|^2$? $\endgroup$ – Matt L. Jun 21 '13 at 14:19
  • $\begingroup$ I don't want the sum. Let's say I want for each 'k' (0 to N-1). Edit the question to better qualify it. $\endgroup$ – Royi Jun 21 '13 at 14:29
  • $\begingroup$ Sheeesh! Can't you come up with something less confusing than $x[k] = DFT\left\{ x[n] \right\}$ where $x$ denotes both the original sequence and its DFT? Also, you are not wanting the Norm of the DFT, which, by Parseval's theorem, equals the norm of the original sequence, but $|X[k]|^2, 0 \leq k \leq N-1$ which is the DFT of the periodic autocorrelation function of the original sequence? $\endgroup$ – Dilip Sarwate Jun 21 '13 at 15:19
  • $\begingroup$ @DilipSarwate, I used the what most people use for notation. I do want the norm, yet not the norm of the series but the norm of each sample of the DFT if you want to be precise. Anyhow, I edited the question in order to try to be more accurate. Let me know if any more modifications are needed. $\endgroup$ – Royi Jun 21 '13 at 15:53
  • $\begingroup$ What is the specific problem with doing complex multiplications? Yes you can calculate a DFT without doing any complex arithmetic. Look at the real form of a Fourier series expansion. You have to do two calculations, one for sin and one for cos (for each frequency bin). Once you have coefficients calculated, you can use some trig to combine into a form that is Acos(nft+B) where A is you're magnitude and B is you're phase. You are only interested in the magnitude. This approach doesn't simplify the process, but you don't have to deal with an imaginary numbers. $\endgroup$ – user2718 Jun 21 '13 at 17:16
2
$\begingroup$

The simple answer: yes this can be done in various different ways:

  1. Calculate the $a_{k}$ and $b_{k}$ coefficients of the regular Fourier Series (http://en.wikipedia.org/wiki/Fourier_series) and then $a_{k}^{2}+b_{k}^{2}$ is the norm at frequency k. This is equivalent of splitting the original DFT equation into it's real and imaginary parts
  2. Calculate the auto-correlation of $c_{xx}[n]$ of $x[n]$. Then calculate only the cosine coefficients $a_{k}$ of the Fourier Series of $c_{xx}[n]$. $a_{k}$ is the norm at frequency k.

However, each of this methods is computationally much less efficient than simply doing the DFT and then taking the magnitude squared. Using the DFT (with complex math) is by far the most efficient way of doing this. If you worried about computationally efficiency, you can shave about 1/3 to 1/2 of the computation time by using the fact that your input signal is real. The DFT of a real function can be calculated by using DFT of a complex signal of half the length. That requires a bit if extra math, which I'll skip here.

$\endgroup$
  • $\begingroup$ The $a_{k}$ of the auto correlation equals $a_{k}^{2}+b_{k}^{2}$ of the original signal $\endgroup$ – Hilmar Jun 22 '13 at 16:02
  • $\begingroup$ An autocorrelation function (periodic autocorrelation in this instance) has symmetry and so all the sine coefficients $b_k$ must be $0$ any way, and need not be calculated at all. $\endgroup$ – Dilip Sarwate Jun 22 '13 at 19:14
  • $\begingroup$ @Hilmar, Thank You. I thought there would be even simpler method than the DFS, I guess there's non. $\endgroup$ – Royi Jun 25 '13 at 7:44
0
$\begingroup$

Norm of a single number is just its absolute value. In your case, the norm of $X[k]$ is obtained with the usual complex distance formula: $$|X[k]| = \sqrt{\text{Re}(X[k])\times\text{Re}(X[k]) + \text{Im}(X[k]) \times \text{Im}(X[k])}$$.

$\endgroup$
  • $\begingroup$ Actually, the OP is not interested in the norm $|X[k]|$ but rather in $|X[k]|^2$ which he calls the norm, and thus the square root need not be computed. But the issue seems to be that computing the DFT $X[k]$ from the original sequence via FFTs and complex multiplications is verboten in this question. $\endgroup$ – Dilip Sarwate Jun 25 '13 at 4:08
  • $\begingroup$ Phonon, I know how to compute the norm (Squared norm, to be exact, as @Dilip mentioned). I thought there might be a computationally efficient method doing so (Better than FFT for the DFT or the DFS). I guess there's non. Thank You. $\endgroup$ – Royi Jun 25 '13 at 5:28

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.