0
$\begingroup$

Assuming there is a sequence that could look like this:

$$ x[n] = \{1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0,1, 1, 0, 0, 1, 1, 0, 0,1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0\} $$

Using this sequence, I want to perform a DFT manually, the connection between $x[n]$ and $|X[k]|$ is important to me.

Now there is only one problem: my sequence contains 32 values, so the DFT by hand would be very complicated. Is there a faster way to see the connection/relationship between the original signal (sequence) $x[n]$ and the magnitude $|X[k]|$.

One can recognize a period in the sequence, perhaps that could be exploited, the question being, how?

To make it short: Assuming I have a sequence (e.g. the above given), how can I infer the magnitude $|X[k]|$ from it?

I hope my question is understandable so far. Thanks for coming answers!

$\endgroup$
2
$\begingroup$

In general, one can't infer the magnitude of the DFT coefficients from the values of the input sequence if by inference one means a process that is much more amenable to manual computing than just evaluating the DFT directly. In a sense, you are asking for "half" (or more) of the information that the DFT provides without doing much work for it; TANSTAAFL. What can be done easily is to get a (weak) upper bound (in some sense, a trivial upper bound) on $|X[k]|$. We have that \begin{align} |X[k]| &= \left|\sum_{n=0}^{N-1} x[n]\exp(-j2\pi kn/N)\right|\\ &\leq \sum_{n=0}^{N-1} \left|x[n]\exp(-j2\pi kn/N)\right|\\ &\leq \sum_{n=0}^{N-1} \left|x[n]\right|\\ &\leq N \max_n |x[n]|. \end{align} In typical cases of DFT computations, this is a very weak bound. In the OP's special case however, one can use the fact that $16$ of the $32$ $x[n]$ are $0$ (and the rest have value $1$) to tweak the bound to $$|X[k]| \leq 16.$$ Since jomegaaA's calculations show that $X[0]$ does indeed have value $16$ in this instance, no tighter bound can be found in this particular instance.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I think your answer is very good and together with the amount spectrum that jomegaA has determined, it seems to fit. But assuming my sequence is (seq. 2 $x[n]=\{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0\}$, then the magnitude spectrum here would be another (maybe similar), how could I distinguish between the sequences or between the magnitude spectra? I would be interested in the assignment of sequence 1 and 2 to the corresponding magnitude spectra. In short:Say I have both sequences and both spectra, how can I assign them to each other (without knowing the relationship)? $\endgroup$ – P_Gate Jan 31 at 18:29
0
$\begingroup$

I don't really see any relation that gives an idea about magnitude of spectrum after transformation of a discrete sequence.

FFT of a given sequence

FFT of your sequence

| improve this answer | |
$\endgroup$
0
$\begingroup$

@Dilip Sarwate

Do I miss anything in the equation

$$\left|X[k]\right| = \sum_{n=0}^{N-1} \left| x[n]\right|$$

and its bit inconsistent to what follows after above equation

*I can't comment yet so I need to post as an answer

| improve this answer | |
$\endgroup$
  • $\begingroup$ You did not miss anything. The whole multiline expression is supposed to be a single-line statement and in the middle, we find $$|X(k)| \leq\cdots \sum_{n=0}^{N-1} \left|x[n]\exp(-j2\pi kn/N)\right| = \sum_{n=0}^{N-1} \left|x[n]\right| \leq \cdots$$. I am not claiming what you think I am. But I will edit my answer to eliminate doubts. $\endgroup$ – Dilip Sarwate Jan 31 at 21:02

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.