# Relationship between DFT input sequence and magnitude

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!

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.

• 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)? – P_Gate Jan 31 '20 at 18:29

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

$$\left|X[k]\right| = \sum_{n=0}^{N-1} \left| x[n]\right|$$
• 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. – Dilip Sarwate Jan 31 '20 at 21:02