BE Computer Engineering (IOE, TU) Digital Signal Analysis and Processing (IOE, EX 701 / ENEX 416) Question Paper 2079 Nepal

(a) LTI system; stability and causality

A discrete-time system is linear if it satisfies superposition: for inputs $x_1[n],x_2[n]$ with outputs $y_1[n],y_2[n]$,

$$T\{a\,x_1[n]+b\,x_2[n]\}=a\,y_1[n]+b\,y_2[n].$$

It is time-invariant if a shift in input produces only the same shift in output: $T\{x[n-n_0]\}=y[n-n_0]$. A system that is both is an LTI system, fully characterized by its impulse response $h[n]=T\{\delta[n]\}$, with $y[n]=x[n]*h[n]=\sum_{k=-\infty}^{\infty}x[k]\,h[n-k]$.

Stability (BIBO). A system is stable iff every bounded input produces a bounded output. Condition: $h[n]$ is absolutely summable,

$$\sum_{n=-\infty}^{\infty}|h[n]|<\infty.$$

Proof. If $|x[n]|\le B_x$, then

$$|y[n]|=\Big|\sum_k h[k]x[n-k]\Big|\le \sum_k|h[k]|\,|x[n-k]|\le B_x\sum_k|h[k]|.$$

If $\sum_k|h[k]|=S<\infty$, then $|y[n]|\le B_x S<\infty$ (sufficiency). Necessity follows by choosing $x[n]=\operatorname{sgn}(h[-n])$, which makes $y[0]=\sum_k|h[k]|$; a finite output requires $S<\infty$.

Causality. A system is causal if the output at time $n$ depends only on present and past inputs. Condition:

$$h[n]=0\quad\text{for } n<0.$$

Proof. In $y[n]=\sum_k h[k]x[n-k]$, terms with $k<0$ use future inputs $x[n-k]$ ($n-k>n$). These vanish iff $h[k]=0$ for all $k<0$, so the output uses only $x[n],x[n-1],\dots$

(b) Convolution of $h[n]=(0.5)^n u[n]$ with $x[n]=u[n]$

$$y[n]=\sum_{k=-\infty}^{\infty}x[k]\,h[n-k]=\sum_{k=0}^{n}(0.5)^{\,n-k},\qquad n\ge 0.$$

Let $m=n-k$ (as $k:0\to n$, $m:n\to 0$):

$$y[n]=\sum_{m=0}^{n}(0.5)^m=\frac{1-(0.5)^{n+1}}{1-0.5}=2\big(1-(0.5)^{n+1}\big),\quad n\ge 0,$$

and $y[n]=0$ for $n<0$. Thus

$$\boxed{\,y[n]=\big[2-(0.5)^{n}\big]\,u[n]\,}$$

since $2(0.5)^{n+1}=(0.5)^n$. As $n\to\infty$, $y[n]\to 2$ (the step response settles at the DC gain $H(1)=2$).

Stability: $\sum_{n=0}^{\infty}|(0.5)^n|=\dfrac{1}{1-0.5}=2<\infty$, so $h[n]$ is absolutely summable and the system is BIBO stable. (It is also causal since $h[n]=0$ for $n<0$.)

(a) Z-transform, ROC, and ROC properties

The (two-sided) Z-transform of $x[n]$ is

$$X(z)=\sum_{n=-\infty}^{\infty}x[n]\,z^{-n},\qquad z=re^{j\omega}\in\mathbb{C}.$$

The Region of Convergence (ROC) is the set of $z$ for which this sum converges absolutely. The ROC is essential because the algebraic expression $X(z)$ alone is not unique to a sequence; the same $X(z)$ with different ROCs corresponds to different time sequences. The ROC determines causality and stability of the system.

Properties of the ROC:

• It is an annular region (a ring) centered at the origin, $r_1<|z|<r_2$.
• It contains no poles of $X(z)$.
• For a finite-length sequence, the ROC is the entire $z$-plane (possibly excluding $z=0$ and/or $z=\infty$).
• For a right-sided (causal) sequence the ROC is the exterior of the outermost pole, $|z|>r_{\max}$.
• For a left-sided (anti-causal) sequence it is the interior of the innermost pole, $|z|<r_{\min}$.
• For a two-sided sequence it is a ring between two poles (if it exists).
• A system is stable iff its ROC includes the unit circle $|z|=1$; causal and stable iff all poles lie inside the unit circle.

(b) System function and impulse response

Taking the Z-transform of $y[n]-\tfrac34 y[n-1]+\tfrac18 y[n-2]=x[n]$:

$$Y(z)\Big(1-\tfrac34 z^{-1}+\tfrac18 z^{-2}\Big)=X(z)\;\Rightarrow\; H(z)=\frac{1}{1-\frac34 z^{-1}+\frac18 z^{-2}}.$$

Factor the denominator: $1-\tfrac34 z^{-1}+\tfrac18 z^{-2}=(1-\tfrac12 z^{-1})(1-\tfrac14 z^{-1})$. So

$$H(z)=\frac{1}{(1-\tfrac12 z^{-1})(1-\tfrac14 z^{-1})}=\frac{z^2}{(z-\tfrac12)(z-\tfrac14)}.$$

Pole-zero plot. Poles at $z=\tfrac12$ and $z=\tfrac14$ (both inside the unit circle); a double zero at $z=0$. Since the system is causal, ROC: $|z|>\tfrac12$, which includes the unit circle, so the system is stable. (Sketch: unit circle, two $\times$ on the positive real axis at $0.25$ and $0.5$, and $\circ$ at the origin.)

Partial fraction expansion:

$$H(z)=\frac{A}{1-\tfrac12 z^{-1}}+\frac{B}{1-\tfrac14 z^{-1}}.$$ $$A=\Big[1-\tfrac14 z^{-1}\Big]^{-1}\Big|_{z^{-1}=2}=\frac{1}{1-\tfrac14(2)}=\frac{1}{1/2}=2,$$ $$B=\Big[1-\tfrac12 z^{-1}\Big]^{-1}\Big|_{z^{-1}=4}=\frac{1}{1-\tfrac12(4)}=\frac{1}{-1}=-1.$$

For the causal case, $\dfrac{1}{1-a z^{-1}}\leftrightarrow a^n u[n]$, so

$$\boxed{\,h[n]=\Big[2\big(\tfrac12\big)^n-\big(\tfrac14\big)^n\Big]u[n]\,}$$

Check: $h[0]=2-1=1$, $h[1]=1-\tfrac14=\tfrac34$ (matches the recursion $h[1]=\tfrac34 h[0]=\tfrac34$).

(a) IIR design by bilinear transformation; warping and prewarping

Steps.

1. From the digital specifications (critical digital frequencies $\omega_k$), prewarp them to analog frequencies $\Omega_k=\dfrac{2}{T}\tan\!\dfrac{\omega_k}{2}$.
2. Design the analog prototype $H_a(s)$ (e.g. Butterworth/Chebyshev) meeting these prewarped specifications.
3. Apply the bilinear transformation $s=\dfrac{2}{T}\dfrac{1-z^{-1}}{1+z^{-1}}$ to obtain $H(z)=H_a(s)\big|_{s=\frac{2}{T}\frac{1-z^{-1}}{1+z^{-1}}}$.
4. Simplify into a realizable rational $H(z)$ and verify the response.

The bilinear transform maps the entire $j\Omega$ axis ($\Omega:-\infty\to\infty$) onto one full traversal of the unit circle ($\omega:-\pi\to\pi$), so it is one-to-one, avoids aliasing, and maps the left half $s$-plane inside the unit circle (stable analog $\to$ stable digital).

Frequency warping. The relationship $\Omega=\dfrac{2}{T}\tan\!\dfrac{\omega}{2}$ is nonlinear: compressing the infinite analog axis onto the finite circle distorts the frequency scale, increasingly so at high frequencies. A linearly spaced analog response becomes nonlinearly spaced in $\omega$.

Prewarping removes the distortion at the critical frequencies: by predistorting each band-edge with $\Omega_k=\dfrac{2}{T}\tan(\omega_k/2)$ before designing the analog filter, the bilinear map sends those analog edges back to exactly the desired digital edges. (Warping elsewhere remains, but is unimportant for piecewise-constant specs.)

(b) First-order LP Butterworth, $\omega_c=0.2\pi$, $T=1$

Prewarp the cutoff:

$$\Omega_c=\frac{2}{T}\tan\frac{\omega_c}{2}=2\tan(0.1\pi)=2\tan(18^\circ)=2(0.3249)=0.6498\ \text{rad/s}.$$

Analog prototype (first-order Butterworth LP, 3-dB cutoff $\Omega_c$):

$$H_a(s)=\frac{\Omega_c}{s+\Omega_c}.$$

Apply bilinear $s=2\dfrac{1-z^{-1}}{1+z^{-1}}$:

$$H(z)=\frac{\Omega_c}{2\frac{1-z^{-1}}{1+z^{-1}}+\Omega_c} =\frac{\Omega_c(1+z^{-1})}{(2+\Omega_c)+(\Omega_c-2)z^{-1}}.$$

With $\Omega_c=0.6498$: numerator $0.6498(1+z^{-1})$, denominator $2.6498-1.3502\,z^{-1}$. Dividing through by $2.6498$:

$$\boxed{\,H(z)=\frac{0.2452\,(1+z^{-1})}{1-0.5095\,z^{-1}}\,}$$

Checks. DC ($z=1$): $\dfrac{0.2452(2)}{1-0.5095}=\dfrac{0.4904}{0.4905}\approx 1$ (0 dB pass-band). Nyquist ($z=-1$): numerator $=0$, i.e. a zero at $z=-1$ ($\omega=\pi$) — characteristic low-pass shape. The pole at $z=0.5095$ is inside the unit circle, so $H(z)$ is stable.

(a) Why FIR filters can have exactly linear phase

An FIR filter $H(e^{j\omega})=\sum_{n=0}^{N-1}h[n]e^{-j\omega n}$ has linear phase when its impulse response is symmetric or antisymmetric about its midpoint $(N-1)/2$. The symmetry lets the sum be factored into a real-valued amplitude function times a pure linear-phase term $e^{-j\omega(N-1)/2}$, so the phase is exactly $\phi(\omega)=-\omega\frac{N-1}{2}$ (plus a constant $\pm\pi/2$ for the antisymmetric case). This gives a constant group delay $\tau=\frac{N-1}{2}$ samples and no phase (waveform) distortion. IIR filters cannot generally achieve this exactly.

Symmetry conditions (length $N$):

• Symmetric: $h[n]=h[N-1-n]$ — Type I ($N$ odd), Type II ($N$ even).
• Antisymmetric: $h[n]=-h[N-1-n]$ — Type III ($N$ odd), Type IV ($N$ even). Either guarantees exactly linear phase.

(b) Length-7 LP FIR by Hamming window, $\omega_c=\pi/2$

Ideal impulse response (delayed by $\alpha=(N-1)/2=3$):

$$h_d[n]=\frac{\sin\big(\omega_c(n-3)\big)}{\pi(n-3)},\qquad h_d[3]=\frac{\omega_c}{\pi}=0.5.$$

With $\omega_c=\pi/2$, $h_d[n]=\dfrac{\sin(\frac{\pi}{2}(n-3))}{\pi(n-3)}$:

Hamming window $w[n]=0.54-0.46\cos\!\big(\frac{2\pi n}{N-1}\big)=0.54-0.46\cos(\pi n/3)$:

$$w=\{0.08,\,0.31,\,0.77,\,1.0,\,0.77,\,0.31,\,0.08\}.$$

Windowed coefficients $h[n]=h_d[n]\,w[n]$:

The result is symmetric ($h[n]=h[6-n]$), confirming linear phase.

Trade-off. A window's main-lobe width sets the transition bandwidth and its side-lobe level sets stop-band attenuation. The two trade off inversely: the rectangular window has the narrowest main lobe (sharp transition) but poor side-lobe attenuation ($\approx 13$ dB, with Gibbs ripples); Hamming gives much better attenuation ($\approx 41$ dB) at the cost of a wider main lobe (wider transition band). Choosing a window means balancing transition sharpness against stop-band rejection.

(a) 4-point DFT of $x[n]=\{1,2,3,4\}$

$$X[k]=\sum_{n=0}^{3}x[n]\,e^{-j2\pi kn/4}=\sum_{n=0}^{3}x[n]\,(-j)^{kn}.$$

• $X[0]=1+2+3+4=10$
• $X[1]=1+2(-j)+3(-1)+4(j)=(1-3)+(-2+4)j=-2+2j$
• $X[2]=1+2(-1)+3(1)+4(-1)=1-2+3-4=-2$
• $X[3]=1+2(j)+3(-1)+4(-j)=(1-3)+(2-4)j=-2-2j$

$$\boxed{X[k]=\{10,\;-2+2j,\;-2,\;-2-2j\}}$$

(Note $X[3]=X[1]^*$, as expected for a real sequence.)

(b) Linear vs. circular convolution; DFT method

By the convolution property of the DFT, an $N$-point IDFT of $X[k]H[k]$ yields the circular convolution. To obtain the linear convolution of sequences of lengths $L_1$ and $L_2$ using DFTs:

1. Choose $N\ge L_1+L_2-1$.
2. Zero-pad both sequences to length $N$.
3. Compute $N$-point DFTs $X[k]$ and $H[k]$ (via FFT).
4. Multiply point-by-point: $Y[k]=X[k]H[k]$.
5. Take the $N$-point IDFT: $y[n]=\text{IDFT}\{Y[k]\}$.

With $N\ge L_1+L_2-1$ the wrap-around (time-aliasing) terms are zero, so the circular convolution equals the linear convolution. (For long streams, overlap-add or overlap-save uses this block-wise.)

8-point DIT radix-2 FFT

The DIT algorithm repeatedly splits a sequence into its even- and odd-indexed samples, giving $\log_2 N=3$ stages of butterflies for $N=8$. Each butterfly takes inputs $a,b$ and produces

$$A=a+W_8^k\,b,\qquad B=a-W_8^k\,b,\qquad W_8^k=e^{-j2\pi k/8}.$$

Input bit-reversal order. The inputs are fed in bit-reversed index order so the outputs emerge in natural order:

So inputs are ordered $x[0],x[4],x[2],x[6],x[1],x[5],x[3],x[7]$.

Structure (3 stages).

• Stage 1 (4 butterflies, span 1): twiddle $W_8^0$ only.
• Stage 2 (4 butterflies, span 2): twiddles $W_8^0, W_8^2$.
• Stage 3 (4 butterflies, span 4): twiddles $W_8^0, W_8^1, W_8^2, W_8^3$.

Twiddle factors: $W_8^0=1,\;W_8^1=\tfrac{1}{\sqrt2}(1-j),\;W_8^2=-j,\;W_8^3=\tfrac{1}{\sqrt2}(-1-j)$.

Text sketch of the flow graph: inputs in bit-reversed order on the left; each stage has 4 vertical butterflies (crossing lines) with the twiddle factor on the lower branch before the add/subtract; outputs $X[0]\dots X[7]$ in natural order on the right.

Computation count, $N=8$

The FFT reduces multiplications from $64$ to $12$ (about $5\times$) and additions from $56$ to $24$; the saving grows as $\dfrac{N^2}{(N/2)\log_2 N}$ for larger $N$.

Sampling theorem

Statement. A band-limited continuous-time signal containing no frequency components above $f_m$ Hz is completely determined by, and can be exactly reconstructed from, its samples taken at a rate

$$f_s\ge 2f_m\quad(\text{Nyquist rate}).$$

If $f_s<2f_m$, higher-frequency components fold (alias) into lower frequencies and the original signal cannot be recovered. Reconstruction uses ideal low-pass (sinc) interpolation. A component at $f$ that exceeds the folding frequency $f_s/2$ appears at the aliased frequency $|f-k f_s|$ for the integer $k$ that brings it into $[0,\,f_s/2]$.

Aliasing analysis, $f_s=6$ kHz

Folding frequency $f_s/2=3\ \text{kHz}$. The signal has components at $f_1=2\ \text{kHz}$ and $f_2=5\ \text{kHz}$.

• $f_1=2$ kHz: $2<3$ kHz, below the folding frequency $\Rightarrow$ not aliased; appears at $2$ kHz.
• $f_2=5$ kHz: $5>3$ kHz $\Rightarrow$ aliased. Apparent frequency $=|f_2-f_s|=|5-6|=1\ \text{kHz}$.

Result. The sampled signal contains tones at $2$ kHz and $1$ kHz; the original $5$ kHz component masquerades as a spurious $1$ kHz tone. To avoid this, either sample at $f_s\ge 2(5)=10$ kHz or place an anti-aliasing low-pass filter before sampling.

(a) Cross-correlation and autocorrelation

Cross-correlation of $x[n]$ and $y[n]$:

$$r_{xy}[l]=\sum_{n=-\infty}^{\infty}x[n]\,y[n-l],\qquad l=\text{lag}.$$

It measures the similarity between two sequences as a function of relative shift $l$; the lag of its peak gives the time delay between them. Use: signal detection, time-delay/range estimation (radar, sonar), pattern matching.

Autocorrelation is the special case $y=x$:

$$r_{xx}[l]=\sum_{n=-\infty}^{\infty}x[n]\,x[n-l].$$

It measures self-similarity; $r_{xx}[0]=\sum_n x^2[n]$ equals the signal energy and is the maximum. Use: detecting periodicity/pitch, characterizing random signals (its DFT is the power spectral density). Note correlation is like convolution without folding one sequence: $r_{xy}[l]=x[l]*y[-l]$.

(b) Linear convolution of $x[n]=\{1,-1,2\}$ and $h[n]=\{2,1,1\}$

Output length $=3+3-1=5$. Using $y[n]=\sum_k x[k]h[n-k]$:

• $y[0]=1\cdot2=2$
• $y[1]=1\cdot1+(-1)\cdot2=1-2=-1$
• $y[2]=1\cdot1+(-1)\cdot1+2\cdot2=1-1+4=4$
• $y[3]=(-1)\cdot1+2\cdot1=-1+2=1$
• $y[4]=2\cdot1=2$

$$\boxed{y[n]=\{2,\,-1,\,4,\,1,\,2\}}$$

Check: $\sum y=8=(\sum x)(\sum h)=(2)(4)$. ✓

Frequency response of $H(z)=\dfrac{1-z^{-1}}{1-0.5z^{-1}}$

Set $z=e^{j\omega}$:

$$H(e^{j\omega})=\frac{1-e^{-j\omega}}{1-0.5e^{-j\omega}}.$$

Magnitude. Using $|1-ae^{-j\omega}|=\sqrt{1-2a\cos\omega+a^2}$:

$$|H(e^{j\omega})|=\frac{\sqrt{1-2\cos\omega+1}}{\sqrt{1-\cos\omega+0.25}}=\sqrt{\frac{2-2\cos\omega}{1.25-\cos\omega}}.$$

Phase. Write numerator and denominator in phase form. With $1-e^{-j\omega}=2\sin(\omega/2)\,e^{j(\pi-\omega)/2}$ for the numerator, and $\angle(1-0.5e^{-j\omega})=\tan^{-1}\!\dfrac{0.5\sin\omega}{1-0.5\cos\omega}$,

$$\angle H(e^{j\omega})=\Big(\frac{\pi-\omega}{2}\Big)-\tan^{-1}\!\frac{0.5\sin\omega}{1-0.5\cos\omega}.$$

Sketch / sample values of $|H(e^{j\omega})|$ over $0\le\omega\le\pi$:

The magnitude rises monotonically from $0$ at DC ($\omega=0$) to $\tfrac{4}{3}$ at $\omega=\pi$.

Conclusion. There is a zero at $z=1$ ($\omega=0$) forcing $|H|=0$ at DC, and the response is largest at high frequency, so the system is a high-pass filter (a first-order differencing/high-pass section).

(a) Energy and power signals

For a discrete-time signal $x[n]$:

• Energy: $E=\displaystyle\sum_{n=-\infty}^{\infty}|x[n]|^2.$
• Power: $P=\displaystyle\lim_{N\to\infty}\frac{1}{2N+1}\sum_{n=-N}^{N}|x[n]|^2.$

An energy signal has $0<E<\infty$ (hence $P=0$) — typically finite or decaying sequences. A power signal has $0<P<\infty$ (hence $E=\infty$) — typically periodic or persistent signals. A signal cannot be both, and some signals are neither.

(b) Periodicity, linearity, time-invariance

Periodicity of $x[n]=\cos(\pi n/4)$. A discrete sinusoid $\cos(\omega_0 n)$ is periodic iff $\omega_0/2\pi$ is rational. Here $\omega_0=\pi/4$, so $\dfrac{\omega_0}{2\pi}=\dfrac{1}{8}$ (rational). The fundamental period is the smallest $N$ with $\omega_0 N=2\pi k$:

$$N=\frac{2\pi k}{\pi/4}=8k\;\Rightarrow\;\boxed{N=8}\ (k=1).$$

So $x[n]$ is periodic with period $8$. (It is also a power signal.)

System $y[n]=n\,x[n]$.

Linearity: For $x_1\to y_1=n x_1[n]$ and $x_2\to y_2=n x_2[n]$, the input $a x_1+b x_2$ gives $n(a x_1[n]+b x_2[n])=a y_1[n]+b y_2[n]$. Linear. ✓

Time-invariance: Delay the output: $y[n-n_0]=(n-n_0)\,x[n-n_0]$. Apply the delayed input $x[n-n_0]$ to the system: response $=n\,x[n-n_0]$. Since $n\,x[n-n_0]\neq(n-n_0)x[n-n_0]$ in general, the system is time-variant (the multiplier $n$ is an explicit function of time).

Conclusion: $y[n]=n\,x[n]$ is linear but time-variant.

Causality and stability of $H(z)=\dfrac{z}{z-1.5}$

The system has a pole at $z=1.5$ and a zero at $z=0$. The pole magnitude is $|z|=1.5>1$, i.e. it lies outside the unit circle.

• Causal choice: ROC is the exterior of the outermost pole, $|z|>1.5$. This region does not include the unit circle $|z|=1$, so the causal system is unstable (its impulse response $h[n]=(1.5)^n u[n]$ grows without bound).
• Stable choice: stability requires the ROC to include $|z|=1$, which forces $|z|<1.5$ (the interior), giving a left-sided, anti-causal $h[n]=-(1.5)^n u[-n-1]$.

Since the single pole lies outside the unit circle, no choice of ROC can be both causal and stable simultaneously. A system is causal and stable only when all poles lie strictly inside the unit circle, which is violated here.

$$\boxed{\text{The system cannot be both causal and stable (pole at }z=1.5\text{ is outside the unit circle).}}$$