Let the linear convolution of two discrete-time finite-length sequences x[n] and h[n], each of length 16 ...
Let the linear convolution of two discrete-time finite-length sequences $x[n]$ and $h[n]$, each of length 16, be denoted by $y[n]$. Let $z[n]$ denote the 16-point inverse discrete Fourier transform (IDFT) of the product of the 16-point discrete Fourier transforms (DFTs) of $x[n]$ and $h[n]$.
The value of $k$ for which $z[k]=y[k]$ is
- (A) 0
- (B) 1
- (C) 15
- (D) 16
Solution
Step 1: Length of Linear Convolution
Both sequences have length 16.
Length of linear convolution:
$
16+16-1=31
$
Hence the linear convolution contains the samples
$
y[0],y[1],\ldots,y[30]
$
Notice that there is no sample $y[31]$.
Step 2: What does the IDFT of the Product of DFTs Give?
A standard DFT property states:
$
\text{IDFT}\{X[k]H[k]\}
=
\text{Circular Convolution}
$
Therefore,
$
z[n]
=
\text{16-point circular convolution of }x[n]\text{ and }h[n].
$
So,
- $y[n]$ = Linear Convolution
- $z[n]$ = 16-point Circular Convolution
Step 3: Folding (Wrap-Around)
Since circular convolution has only 16 output samples, the extra samples of the 31-point linear convolution wrap around.
| Linear Convolution Sample | Wraps To |
|---|---|
| $y[0]$ | $z[0]$ |
| $y[1]$ | $z[1]$ |
| $\vdots$ | $\vdots$ |
| $y[15]$ | $z[15]$ |
| $y[16]$ | $z[0]$ |
| $y[17]$ | $z[1]$ |
| $\vdots$ | $\vdots$ |
| $y[30]$ | $z[14]$ |
Step 4: Write the Circular Convolution Samples
\[
\begin{aligned}
z[0]&=y[0]+y[16] \\
z[1]&=y[1]+y[17] \\
&\vdots \\
z[14]&=y[14]+y[30] \\
z[15]&=y[15]+y[31]
\end{aligned}
\]
But,
\[
y[31]=0
\]
because the linear convolution ends at $y[30]$.
Hence,
\[
z[15]=y[15].
\]
Step 5: Compare $z[k]$ and $y[k]$
| k | Relation | Equal? |
|---|---|---|
| 0 | $z[0]=y[0]+y[16]$ | ❌ |
| 1 | $z[1]=y[1]+y[17]$ | ❌ |
| $\vdots$ | $\vdots$ | |
| 14 | $z[14]=y[14]+y[30]$ | ❌ |
| 15 | $z[15]=y[15]$ | ✅ |
Final Answer
$\boxed{k=15}$
Therefore, the correct option is (C) 15.