Digital Signal Processing

Cheatsheet Content

### Introduction to DSP Digital Signal Processing (DSP) is the study of processing discrete-time signals. It involves converting analog signals to digital, manipulating them, and converting them back to analog. #### Key Concepts - **Discrete-Time System:** A system that processes discrete-time signals. - **Digital Signal:** A signal that is discrete in both time and amplitude. ### 1. System Definition and Types #### 1. Define system. Explain types of discrete-time system with examples. A **system** is a device or algorithm that operates on an input signal to produce an output signal. In DSP, we focus on discrete-time systems. #### Types of Discrete-Time Systems: 1. **Static/Dynamic:** * **Static (Memoryless):** Output depends only on the current input. * *Example:* $y[n] = 2x[n]$ * **Dynamic (With Memory):** Output depends on past or future inputs/outputs. * *Example:* $y[n] = x[n] + x[n-1]$ 2. **Linear/Non-linear:** * **Linear:** Satisfies superposition (additivity and homogeneity). * *Example:* $y[n] = x[n] + n$ (Non-linear due to $n$) * *Example:* $y[n] = 2x[n]$ (Linear) * **Non-linear:** Does not satisfy superposition. * *Example:* $y[n] = x^2[n]$ 3. **Time-Invariant/Time-Variant:** * **Time-Invariant (LTI):** System's behavior does not change with time. A time shift in input causes an identical time shift in output. * *Example:* If $x[n] \to y[n]$, then $x[n-k] \to y[n-k]$ * **Time-Variant:** System's behavior changes with time. * *Example:* $y[n] = nx[n]$ 4. **Causal/Non-causal:** * **Causal:** Output depends only on present and past inputs. * *Example:* $y[n] = x[n] + x[n-1]$ * **Non-causal:** Output depends on future inputs. * *Example:* $y[n] = x[n+1] + x[n]$ 5. **Stable/Unstable:** * **Stable (BIBO - Bounded Input Bounded Output):** A bounded input always produces a bounded output. * **Unstable:** A bounded input can produce an unbounded output. ### 2. Block Diagram Representation of Discrete-Time System #### 2. Explain block diagram representation of discrete time system. Block diagrams are used to represent the interconnections of basic operations in a discrete-time system. #### Basic Elements: - **Adder:** Sums two or more signals. $$\text{---}\hspace{-0.5em}\longrightarrow\hspace{-0.5em}\text{---}\hspace{-0.7em}\boxed{+}\hspace{-0.7em}\text{---}\hspace{-0.5em}\longrightarrow\hspace{-0.5em}\text{---}$$ - **Multiplier (Scalar):** Multiplies a signal by a constant. $$\text{---}\hspace{-0.5em}\longrightarrow\hspace{-0.5em}\text{---}\hspace{-0.7em}\boxed{\alpha}\hspace{-0.7em}\text{---}\hspace{-0.5em}\longrightarrow\hspace{-0.5em}\text{---}$$ - **Unit Delay:** Delays a signal by one sample ($z^{-1}$). $$\text{---}\hspace{-0.5em}\longrightarrow\hspace{-0.5em}\text{---}\hspace{-0.7em}\boxed{z^{-1}}\hspace{-0.7em}\text{---}\hspace{-0.5em}\longrightarrow\hspace{-0.5em}\text{---}$$ - **Unit Advance:** Advances a signal by one sample ($z$). $$\text{---}\hspace{-0.5em}\longrightarrow\hspace{-0.5em}\text{---}\hspace{-0.7em}\boxed{z}\hspace{-0.7em}\text{---}\hspace{-0.5em}\longrightarrow\hspace{-0.5em}\text{---}$$ #### Example: $y[n] = 0.5x[n] + 0.25x[n-1]$ ``` x[n] ------>[0.5]----->(+)-----> y[n] | ^ | | v | [z^-1]---->[0.25]----->(+) ``` ### 3. Basic Elements of Digital Signal Processing #### 3. Explain basic elements of digital signal processing. The fundamental components of a DSP system are: 1. **Analog-to-Digital Converter (ADC):** Converts continuous-time analog signals into discrete-time digital signals. This involves: * **Sampling:** Converting continuous time to discrete time. * **Quantization:** Converting continuous amplitude to discrete amplitude levels. * **Coding:** Assigning binary codes to quantized levels. 2. **Digital Signal Processor (DSP):** The core unit that performs mathematical operations on the digital signal. This can be a dedicated hardware chip or software running on a general-purpose processor. 3. **Digital-to-Analog Converter (DAC):** Converts the processed digital signal back into an analog signal. 4. **Anti-Aliasing Filter (Analog Low-Pass Filter):** Placed before the ADC to prevent aliasing (distortion due to sampling too slowly). It limits the bandwidth of the analog signal to half the sampling rate. 5. **Reconstruction Filter (Analog Low-Pass Filter):** Placed after the DAC to smooth out the stair-step output of the DAC and reconstruct the original continuous-time signal. ### 4. Linear Convolution #### 4. Perform linear convolution using Graphical & Tabular method. Given $x[n] = \{1, 2, 1\}$ (with arrow at 2) and $h[n] = \{1, -1\}$ (with arrow at 1). This implies: $x[n] = \delta[n+1] + 2\delta[n] + \delta[n-1]$ $h[n] = \delta[n] - \delta[n-1]$ The output $y[n]$ is given by $y[n] = x[n] * h[n] = \sum_{k=-\infty}^{\infty} x[k]h[n-k]$. #### Graphical Method: 1. **Flip and Shift:** Flip $h[k]$ to get $h[-k]$. Then shift it to $h[n-k]$. 2. **Multiply and Sum:** For each $n$, multiply $x[k]$ by $h[n-k]$ and sum the products. * $x[n]$ values: $x[-1]=1, x[0]=2, x[1]=1$ * $h[n]$ values: $h[0]=1, h[1]=-1$ * **For n = -1:** $y[-1] = x[-1]h[0] = 1 \times 1 = 1$ * **For n = 0:** $y[0] = x[0]h[0] + x[-1]h[1] = (2 \times 1) + (1 \times -1) = 2 - 1 = 1$ * **For n = 1:** $y[1] = x[1]h[0] + x[0]h[1] = (1 \times 1) + (2 \times -1) = 1 - 2 = -1$ * **For n = 2:** $y[2] = x[1]h[1] = 1 \times -1 = -1$ All other $y[n]$ are 0. So, $y[n] = \{1, 1, -1, -1\}$ with origin at $n=0$. #### Tabular Method: | | 1 | 2 | 1 | ($x[n]$) | |---|---|---|---|---| | **1** | 1 | 2 | 1 | (1 * $x[n]$) | | **-1** | | -1 | -2 | -1 | (-1 * $x[n]$, shifted) | | **Sum** | 1 | 1 | -1 | -1 | ($y[n]$) | The result is $y[n] = \{1, 1, -1, -1\}$, with the first element corresponding to $n = (-1) + 0 = -1$. So, $y[-1]=1, y[0]=1, y[1]=-1, y[2]=-1$. ### 5. Properties of Z-Transform #### 5. Explain properties of Z-transform. The Z-transform is a powerful tool for analyzing discrete-time systems. Let $X(z)$ be the Z-transform of $x[n]$ with Region of Convergence (ROC) $R_x$, and $Y(z)$ be the Z-transform of $y[n]$ with ROC $R_y$. 1. **Linearity:** * $ax[n] + by[n] \longleftrightarrow aX(z) + bY(z)$ * ROC: $R_x \cap R_y$ 2. **Time Shifting:** * $x[n-n_0] \longleftrightarrow z^{-n_0}X(z)$ * ROC: $R_x$, possibly excluding $z=0$ (if $n_0 > 0$) or $z=\infty$ (if $n_0 ### 6. Find the Z-transform of the following signal #### 6. Find the Z-transform of the following signal i) $x[n] = \{1, -1, 2, 3, 1\}$ (arrow at -1) This means $x[n]$ is defined as: $x[-1] = 1$ $x[0] = -1$ $x[1] = 2$ $x[2] = 3$ $x[3] = 1$ For a finite-duration signal, the Z-transform is directly calculated as $X(z) = \sum_{n=-\infty}^{\infty} x[n]z^{-n}$. $X(z) = x[-1]z^{-(-1)} + x[0]z^{-0} + x[1]z^{-1} + x[2]z^{-2} + x[3]z^{-3}$ $X(z) = 1 \cdot z^1 + (-1) \cdot z^0 + 2 \cdot z^{-1} + 3 \cdot z^{-2} + 1 \cdot z^{-3}$ $X(z) = z - 1 + 2z^{-1} + 3z^{-2} + z^{-3}$ ROC: Entire z-plane, except $z=0$ and $z=\infty$. ii) $x[n] = \{2, 3, 4, -2, -3\}$ (arrow at -2) This means $x[n]$ is defined as: $x[-2] = 2$ $x[-1] = 3$ $x[0] = 4$ $x[1] = -2$ $x[2] = -3$ $X(z) = x[-2]z^2 + x[-1]z^1 + x[0]z^0 + x[1]z^{-1} + x[2]z^{-2}$ $X(z) = 2z^2 + 3z^1 + 4z^0 - 2z^{-1} - 3z^{-2}$ $X(z) = 2z^2 + 3z + 4 - 2z^{-1} - 3z^{-2}$ ROC: Entire z-plane, except $z=0$ and $z=\infty$. ### 7. Find the Z-transform of the following signal #### 7. Find the Z-transform of the following signal. i) $x[n] = a^n u[n]$ The Z-transform of $a^n u[n]$ is given by the formula: $X(z) = \sum_{n=0}^{\infty} (az^{-1})^n = \frac{1}{1 - az^{-1}} = \frac{z}{z-a}$ ROC: $|az^{-1}| |a|$. ii) $x[n] = -a^n u[n-1]$ We know that the Z-transform of $a^n u[n]$ is $\frac{z}{z-a}$ for $|z| > |a|$. Consider $y[n] = a^n u[n]$. Then $Y(z) = \frac{z}{z-a}$. $x[n] = -a^n u[n-1] = -(a^n u[n] - a^n \delta[n])$ Since $a^n \delta[n] = a^0 \delta[n] = \delta[n]$, $x[n] = -(a^n u[n] - \delta[n])$ Using linearity property: $X(z) = -(Y(z) - Z\{\delta[n]\}) = -\left(\frac{z}{z-a} - 1\right)$ $X(z) = -\left(\frac{z - (z-a)}{z-a}\right) = -\left(\frac{a}{z-a}\right) = \frac{a}{a-z}$ ROC: The ROC for $a^n u[n]$ is $|z| > |a|$. The ROC for $\delta[n]$ is the entire z-plane. So, the ROC for $x[n]$ is $|z| > |a|$. Alternatively, $u[n-1]$ can be seen as $u[n]$ delayed by 1. $Z\{u[n]\} = \frac{z}{z-1}$. $Z\{u[n-1]\} = z^{-1} \frac{z}{z-1} = \frac{1}{z-1}$. So, $Z\{a^n u[n-1]\}$. This is a bit tricky, the $a^n$ term is not directly applied to $u[n-1]$. Using the definition: $X(z) = \sum_{n=-\infty}^{\infty} -a^n u[n-1]z^{-n} = -\sum_{n=1}^{\infty} a^n z^{-n}$ $X(z) = -\sum_{n=1}^{\infty} (az^{-1})^n$ This is a geometric series starting from $n=1$: $\frac{az^{-1}}{1-az^{-1}}$ for $|az^{-1}| |a|$. ### 8. Perform Time Signal Operation #### 8. Perform the time signal operation on following signal. Given $x[n] = \{1, 2, 3, 0, 2, 4, -1\}$ (arrow at 2, meaning $x[0]=2$). This implies: $x[-2]=1$ $x[-1]=2$ $x[0]=3$ $x[1]=0$ $x[2]=2$ $x[3]=4$ $x[4]=-1$ i) $x[n-3]$ (Time Shift: Delay by 3) The signal $x[n-3]$ means that the original $x[n]$ is shifted 3 units to the right. The value that was at $x[k]$ will now be at $x[k+3]$. Original indices: -2, -1, 0, 1, 2, 3, 4 New indices: 1, 2, 3, 4, 5, 6, 7 $x[n-3] = \{..., 0, 0, \underset{\uparrow}{1}, 2, 3, 0, 2, 4, -1, 0, ...\}$ The arrow moves from $n=0$ to $n=3$. $x[n-3] = \{1, 2, 3, 0, 2, 4, -1\}$ with origin at $n=3$. ii) $x[n+3]$ (Time Shift: Advance by 3) The signal $x[n+3]$ means that the original $x[n]$ is shifted 3 units to the left. The value that was at $x[k]$ will now be at $x[k-3]$. Original indices: -2, -1, 0, 1, 2, 3, 4 New indices: -5, -4, -3, -2, -1, 0, 1 $x[n+3] = \{1, 2, 3, 0, 2, 4, -1\}$ with origin at $n=0$. $x[n+3] = \{1, 2, 3, 0, 2, 4, -1\}$ (with arrow at $n=0$, which corresponds to original $x[3]$). So, $x[-5]=1, x[-4]=2, x[-3]=3, x[-2]=0, x[-1]=2, x[0]=4, x[1]=-1$. $x[n+3] = \{1, 2, 3, 0, 2, \underset{\uparrow}{4}, -1\}$ iii) $x[3n]$ (Time Scaling: Decimation by 3) Only samples where $n$ is a multiple of 3 are kept. $x[3n]$: $n=-1 \Rightarrow x[-3]$ (not in original signal, so 0) $n=0 \Rightarrow x[0] = 3$ $n=1 \Rightarrow x[3] = 4$ $n=2 \Rightarrow x[6]$ (not in original signal, so 0) $x[3n] = \{\underset{\uparrow}{3}, 4\}$ iv) $x[n/3]$ (Time Scaling: Interpolation by 3) This operation is generally defined for continuous-time signals or by inserting zeros. For discrete signals, $x[n/3]$ means only samples where $n$ is a multiple of 3 are non-zero. $x[n/3]$: $n=-6 \Rightarrow x[-2] = 1$ $n=-3 \Rightarrow x[-1] = 2$ $n=0 \Rightarrow x[0] = 3$ $n=3 \Rightarrow x[1] = 0$ $n=6 \Rightarrow x[2] = 2$ $n=9 \Rightarrow x[3] = 4$ $n=12 \Rightarrow x[4] = -1$ All other values are 0. $x[n/3] = \{1, 0, 0, 2, 0, 0, \underset{\uparrow}{3}, 0, 0, 0, 0, 0, 2, 0, 0, 4, 0, 0, -1\}$ v) $x[-n]$ (Time Reversal/Folding) The signal is flipped around the origin. Original indices: -2, -1, 0, 1, 2, 3, 4 Values: 1, 2, 3, 0, 2, 4, -1 New indices: -4, -3, -2, -1, 0, 1, 2 Values: -1, 4, 2, 0, 3, 2, 1 $x[-n] = \{-1, 4, 2, 0, \underset{\uparrow}{3}, 2, 1\}$ ### 9. Solve Difference Equation for Z-transform #### 9. Solve the following difference equation for Z-transform. Given $y[n] = x[n] + x[n-1] + \frac{3}{4}y[n-1] - \frac{1}{8}y[n-2]$ Initial conditions: $y[-1]=0$ and $x[-2]=1$. Take the Z-transform of both sides: $Y(z) = X(z) + Z\{x[n-1]\} + \frac{3}{4}Z\{y[n-1]\} - \frac{1}{8}Z\{y[n-2]\}$ Using the time-shifting property with initial conditions: $Z\{x[n-1]\} = z^{-1}X(z) + x[-1]$ $Z\{y[n-1]\} = z^{-1}Y(z) + y[-1]$ $Z\{y[n-2]\} = z^{-2}Y(z) + y[-2] + z^{-1}y[-1]$ Substitute the initial conditions: $y[-1]=0$. We need $y[-2]$ and $x[-1]$. From the difference equation: $y[-1] = x[-1] + x[-2] + \frac{3}{4}y[-2] - \frac{1}{8}y[-3]$ Since $y[-1]=0$ and $x[-2]=1$: $0 = x[-1] + 1 + \frac{3}{4}y[-2] - \frac{1}{8}y[-3]$ This indicates that solving this fully requires more information about $x[n]$ and $y[n]$ for negative indices before the given initial conditions, or the problem assumes zero initial rest conditions (i.e., signals are zero before a certain time). **Assuming zero initial conditions for $x[n]$ and $y[n]$ prior to the given indices for simplicity (as is common in such problems unless specified otherwise):** If $y[-1]=0$ and $y[-2]=0$, and $x[-1]=0$, $x[-2]=1$ (this $x[-2]=1$ is an input, not a state). The standard Z-transform for causal signals with initial conditions $y[-1], y[-2], ...$: $Z\{y[n-1]\} = z^{-1}Y(z) + y[-1]$ $Z\{y[n-2]\} = z^{-2}Y(z) + z^{-1}y[-1] + y[-2]$ Given $y[-1]=0$, these simplify to: $Z\{y[n-1]\} = z^{-1}Y(z)$ $Z\{y[n-2]\} = z^{-2}Y(z)$ For $x[n-1]$, if $x[n]$ is causal, $x[-1]=0$: $Z\{x[n-1]\} = z^{-1}X(z)$ Then, the equation becomes: $Y(z) = X(z) + z^{-1}X(z) + \frac{3}{4}z^{-1}Y(z) - \frac{1}{8}z^{-2}Y(z)$ Group $Y(z)$ terms: $Y(z) - \frac{3}{4}z^{-1}Y(z) + \frac{1}{8}z^{-2}Y(z) = X(z) + z^{-1}X(z)$ $Y(z)(1 - \frac{3}{4}z^{-1} + \frac{1}{8}z^{-2}) = X(z)(1 + z^{-1})$ The system function $H(z) = \frac{Y(z)}{X(z)}$ is: $H(z) = \frac{1 + z^{-1}}{1 - \frac{3}{4}z^{-1} + \frac{1}{8}z^{-2}}$ **Considering the initial condition $x[-2]=1$ explicitly:** The problem statement gives $y[-1]=0$ and $x[-2]=1$. This suggests a non-zero input before $n=0$. $Z\{x[n-1]\} = z^{-1}X(z) + x[-1]$ We need $x[-1]$. The problem only gives $x[-2]=1$. If $x[n]$ is a general signal, we cannot assume $x[-1]=0$. However, if the question implies $x[n]$ is causal *except* for the specified $x[-2]=1$, then $x[-1]=0$. Let's assume $x[n]$ is such that $x[-1]=0$ and $x[-2]=1$ are the only non-zero values for negative $n$. Then, $Z\{x[n-1]\} = z^{-1}X(z) + x[-1]$. If $x[-1]$ is not given, but $x[-2]=1$ is, this implies that the input $x[n]$ starts at $n=-2$. Let's rewrite $x[n]$ as $x_c[n] + x_i[n]$, where $x_c[n]$ is the causal part and $x_i[n]$ is the initial condition part. $X(z) = X_c(z) + X_i(z)$ Here, $x_i[n] = \delta[n+2]$ (since $x[-2]=1$). So $X_i(z) = z^2$. The Z-transform of the difference equation is: $Y(z) + y[-1]z^1 = (X(z) + x[-1]z^1) + (z^{-1}X(z) + x[-1]) + \frac{3}{4}(z^{-1}Y(z) + y[-1]) - \frac{1}{8}(z^{-2}Y(z) + z^{-1}y[-1] + y[-2])$ Given $y[-1]=0$. We need $y[-2]$ and $x[-1]$. If $x[n]$ is the general input, and $x[-2]=1$ is a specific value of that input. Then the Z-transform of $x[n-1]$ is $\sum x[n-1]z^{-n} = \sum x[k]z^{-(k+1)} = z^{-1} \sum x[k]z^{-k} = z^{-1}X(z)$. This is for two-sided Z-transform. For one-sided Z-transform, the initial values matter: $Z_I\{y[n-k]\} = z^{-k}Y_I(z) + \sum_{m=1}^k y[-m]z^{-(k-m)}$ So, $Z_I\{y[n-1]\} = z^{-1}Y_I(z) + y[-1]$ $Z_I\{y[n-2]\} = z^{-2}Y_I(z) + y[-2]z^{-0} + y[-1]z^{-1}$ Given $y[-1]=0$. We need $y[-2]$. From the difference equation: $y[0] = x[0] + x[-1] + \frac{3}{4}y[-1] - \frac{1}{8}y[-2]$ $y[0] = x[0] + x[-1] - \frac{1}{8}y[-2]$ This problem is a bit ambiguous with the initial conditions $y[-1]=0$ and $x[-2]=1$ if we are looking for a general $H(z)$ or $Y(z)$. If the question is asking for the system function $H(z)$ under zero initial conditions for the system states ($y[-1]=0, y[-2]=0$) and assuming $x[n]$ is causal (so $x[-1]=0, x[-2]=0$ for the input *signal* itself), then the first solution for $H(z)$ is correct. The condition $x[-2]=1$ would then refer to a specific input signal for which we would find $Y(z)$ using $X(z)$ derived from that specific $x[n]$. Let's assume the question is asking for the transfer function $H(z)$ assuming zero initial conditions for the system states. The $x[-2]=1$ is then an initial condition for the input signal, not the system itself. $Y(z) = X(z) + z^{-1}X(z) + \frac{3}{4}z^{-1}Y(z) - \frac{1}{8}z^{-2}Y(z)$ $Y(z)(1 - \frac{3}{4}z^{-1} + \frac{1}{8}z^{-2}) = X(z)(1 + z^{-1})$ $H(z) = \frac{Y(z)}{X(z)} = \frac{1 + z^{-1}}{1 - \frac{3}{4}z^{-1} + \frac{1}{8}z^{-2}}$ To find $y[n]$ for the given initial conditions $y[-1]=0$ and $x[-2]=1$: This implies that $x[n]$ is a specific input signal. Let's say $x[n] = \delta[n+2]$ if it's just that one value, or a more complex signal. If $x[n]$ is a general signal, and $x[-2]=1$ is just one of its values. Let's use the full one-sided Z-transform equations: $Z\{y[n-1]\} = z^{-1}Y_I(z) + y[-1]$ $Z\{y[n-2]\} = z^{-2}Y_I(z) + y[-2] + z^{-1}y[-1]$ $Z\{x[n-1]\} = z^{-1}X_I(z) + x[-1]$ $Z\{x[n-2]\} = z^{-2}X_I(z) + x[-2] + z^{-1}x[-1]$ Substitute $y[-1]=0$: $Z\{y[n-1]\} = z^{-1}Y_I(z)$ $Z\{y[n-2]\} = z^{-2}Y_I(z) + y[-2]$ We need $y[-2]$ and $x[-1]$. From $y[n] = x[n] + x[n-1] + \frac{3}{4}y[n-1] - \frac{1}{8}y[n-2]$: For $n=-1$: $y[-1] = x[-1] + x[-2] + \frac{3}{4}y[-2] - \frac{1}{8}y[-3]$ $0 = x[-1] + 1 + \frac{3}{4}y[-2] - \frac{1}{8}y[-3]$ This approach requires more initial conditions or assumptions. The most common interpretation for "solve the difference equation for Z-transform" when initial conditions are given is to find $Y(z)$ in terms of $X(z)$ and the initial conditions. Let's assume $x[n]$ is the input for $n \ge 0$, and we have the specific initial condition $x[-2]=1$. If $x[n]$ is defined as $x[n] = \delta[n+2]$ for $n