Digital Signal Processing

Cheatsheet Content

### Introduction Digital Signal Processing (DSP) involves processing discrete-time signals using digital computers. DSP systems offer numerous advantages over analog systems, including higher precision, flexibility, and immunity to noise. ### Discrete-Time Signals A discrete-time signal $x(n)$ is defined only at discrete instants of time $n$. #### Representation of Discrete-Time Signals 1. **Graphical Representation:** Plotting amplitude $x(n)$ against time $n$. 2. **Functional Representation:** Defining $x(n)$ by a mathematical function (e.g., $x(n) = 2^n u(n)$). 3. **Tabular Representation:** A table listing $n$ and $x(n)$ values. 4. **Sequence Representation:** Listing values in curly braces, with an arrow indicating $n=0$ (e.g., $x(n) = \{3, 2, \vec{0}, 3, 1, 2\}$). #### Elementary Discrete-Time Signals 1. **Unit Step Sequence:** $u(n) = \begin{cases} 1 & \text{for } n \ge 0 \\ 0 & \text{for } n 0$, advance if $k 1$, expansion if $a 0$. A sinusoidal sequence $A \sin(\omega_0 n + \phi)$ is periodic if $\omega_0/(2\pi)$ is a rational number. 3. **Energy vs. Power:** * **Total Energy:** $E = \sum_{n=-\infty}^{\infty} |x(n)|^2$ * **Average Power:** $P = \lim_{N\to\infty} \frac{1}{2N+1} \sum_{n=-N}^{N} |x(n)|^2$ * **Energy Signal:** $0 0$. 5. **Even vs. Odd:** Even if $x(n)=x(-n)$. Odd if $x(n)=-x(-n)$. Any signal can be decomposed into $x_e(n) = \frac{1}{2}[x(n)+x(-n)]$ and $x_o(n) = \frac{1}{2}[x(n)-x(-n)]$. ### Discrete-Time Systems A system transforms an input signal $x(n)$ into an output signal $y(n)$. #### Classification of Discrete-Time Systems 1. **Static (Memoryless) vs. Dynamic (Memory):** Output depends only on present input vs. on past/future inputs/outputs. 2. **Causal vs. Non-causal:** Output depends only on present/past inputs vs. on future inputs. 3. **Linear vs. Non-linear:** Obeys superposition (additivity and homogeneity). 4. **Shift-Invariant vs. Shift-Varying:** Input shift causes identical output shift ($T[x(n-k)] = y(n-k)$). 5. **Stable vs. Unstable (BIBO Stability):** Bounded Input produces Bounded Output ($|x(n)| ### Discrete Convolution and Correlation #### Discrete Convolution The output $y(n)$ of a Linear Time-Invariant (LTI) system with impulse response $h(n)$ for an input $x(n)$ is given by the convolution sum: $$y(n) = x(n) * h(n) = \sum_{k=-\infty}^{\infty} x(k)h(n-k)$$ ##### Properties of Discrete Convolution 1. **Commutative:** $x(n) * h(n) = h(n) * x(n)$ 2. **Associative:** $[x(n) * h_1(n)] * h_2(n) = x(n) * [h_1(n) * h_2(n)]$ 3. **Distributive:** $x(n) * [h_1(n) + h_2(n)] = [x(n) * h_1(n)] + [x(n) * h_2(n)]$ 4. **Shifting Property:** If $x(n) * h(n) = y(n)$, then $x(n-k) * h(n-m) = y(n-k-m)$. 5. **Convolution with Impulse:** $x(n) * \delta(n) = x(n)$ ##### Methods to Compute Linear Convolution 1. **Graphical Method (Flip, Shift, Multiply, and Sum):** Flip one sequence, shift it, multiply overlapping samples, and sum. 2. **Tabular Array Method:** Create a grid, fill with products, sum along diagonals. 3. **Matrix Method:** Express as matrix multiplication. 4. **Polynomial Multiplication:** Coefficients of product polynomial are convolution. #### Deconvolution Finding $x(n)$ (or $h(n)$) from $y(n)$ and $h(n)$ (or $x(n)$). 1. **Using Z-transform:** $X(z) = Y(z)/H(z)$. 2. **By Recursion:** Directly solve the convolution sum equation. 3. **Tabular Method:** Assume unknown sequence, set up convolution table, solve for unknowns. #### Circular Convolution For N-point sequences $x_1(n)$ and $x_2(n)$: $$x_3(n) = x_1(n) \circledast x_2(n) = \sum_{k=0}^{N-1} x_1(k)x_2((n-k) \pmod N)$$ ##### Methods of Performing Circular Convolution 1. **Graphical Method (Concentric Circle Method):** Plot one sequence clockwise, the other anti-clockwise, multiply, and sum. 2. **Tabular Array Method:** Similar to linear, but with modulo N shifts. 3. **Matrix Method:** Express as a circulant matrix multiplication. #### Linear Convolution from Periodic Convolution To obtain linear convolution of $x(n)$ (length $N_1$) and $h(n)$ (length $N_2$), zero-pad both sequences to length $L = N_1+N_2-1$, then perform $L$-point circular convolution. #### Periodic Convolution from Linear Convolution Perform linear convolution of $x(n)$ and $h(n)$ to get $y_{lin}(n)$. Then wrap-around $y_{lin}(n)$ to length $N$ (where $N$ is the period) by adding samples that map to the same index modulo $N$. #### Discrete Correlation Measures similarity between two signals. 1. **Cross Correlation:** $R_{xy}(n) = \sum_{k=-\infty}^{\infty} x(k)y(k-n)$. $R_{xy}(n) = x(n) * y(-n)$. 2. **Autocorrelation:** $R_{xx}(n) = \sum_{k=-\infty}^{\infty} x(k)x(k-n)$. $R_{xx}(n) = x(n) * x(-n)$. * $R_{xx}(0) = \sum |x(n)|^2 = E$ (total energy). * $R_{xx}(n)$ is even symmetric: $R_{xx}(n) = R_{xx}(-n)$. * $|R_{xx}(n)| \le R_{xx}(0)$. ### Z-Transforms The Z-transform converts difference equations into algebraic equations, simplifying the analysis of discrete-time systems. #### Definition 1. **Bilateral Z-transform:** $X(z) = \sum_{n=-\infty}^{\infty} x(n)z^{-n}$ 2. **Unilateral Z-transform:** $X(z) = \sum_{n=0}^{\infty} x(n)z^{-n}$ (for causal signals) #### Region of Convergence (ROC) The set of $z$ values for which $X(z)$ converges. 1. **Right-sided sequence:** ROC is of the form $|z| > R_{max}$. 2. **Left-sided sequence:** ROC is of the form $|z| ### System Realization Representing a digital filter's difference equation or transfer function as an interconnection of basic elements (adders, multipliers, delay elements). #### Basic Elements * **Adder:** Sums signals. * **Constant Multiplier:** Multiplies signal by a constant. * **Unit Delay Element:** Delays signal by one sample ($z^{-1}$). #### Structures for Realization of IIR Systems 1. **Direct Form-I:** Direct implementation of the difference equation. Uses $M+N$ delay elements for $M$-th order numerator and $N$-th order denominator. Not canonical. 2. **Direct Form-II:** Obtained by interchanging the order of the numerator and denominator sections of Direct Form-I. Uses $\max(M,N)$ delay elements. Canonical. 3. **Transposed Form:** Obtained by reversing all signal paths, interchanging input/output, and replacing adders with branch nodes and vice-versa. 4. **Cascade Form:** $H(z) = H_1(z)H_2(z)...H_K(z)$. Each $H_i(z)$ is typically 1st or 2nd order (Direct Form-II). 5. **Parallel Form:** $H(z) = H_0(z) + H_1(z) + ... + H_K(z)$. Obtained by partial fraction expansion. Each $H_i(z)$ is typically 1st or 2nd order. 6. **Lattice Structure:** Realizes poles and zeros in a lattice network. 7. **Ladder Structure:** Realizes transfer function as a continued fraction expansion. #### Structures for Realization of FIR Systems 1. **Direct Form:** Direct implementation of the difference equation $y(n) = \sum_{k=0}^{N-1} h(k)x(n-k)$. Also called transversal or tapped-delay-line filter. Canonical. 2. **Transposed Form:** Similar to IIR, by transposing the direct form. 3. **Cascade Form:** $H(z) = H_1(z)H_2(z)...H_K(z)$. Each $H_i(z)$ is typically 1st or 2nd order. 4. **Lattice Structure:** Used extensively in digital speech processing. 5. **Linear Phase Realizations:** Exploits symmetry of impulse response $h(n) = h(N-1-n)$ to reduce multipliers. ### Discrete-Time Fourier Transform (DTFT) Transforms discrete-time signals to continuous frequency domain. #### Definition $X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x(n)e^{-j\omega n}$ #### Inverse DTFT $x(n) = \frac{1}{2\pi} \int_{-\pi}^{\pi} X(e^{j\omega})e^{j\omega n}d\omega$ #### Relation between Z-transform and DTFT The DTFT is the Z-transform evaluated on the unit circle in the z-plane: $X(e^{j\omega}) = X(z)|_{z=e^{j\omega}}$. For DTFT to exist, the ROC of $X(z)$ must include the unit circle. #### Properties of DTFT 1. **Linearity:** $DTFT[ax_1(n) + bx_2(n)] = aX_1(e^{j\omega}) + bX_2(e^{j\omega})$ 2. **Periodicity:** $X(e^{j\omega})$ is periodic with period $2\pi$. 3. **Time Shifting:** $DTFT[x(n-m)] = e^{-j\omega m}X(e^{j\omega})$ 4. **Frequency Shifting:** $DTFT[e^{j\omega_0 n}x(n)] = X(e^{j(\omega-\omega_0)})$ 5. **Time Reversal:** $DTFT[x(-n)] = X(e^{-j\omega})$ 6. **Differentiation in Frequency:** $DTFT[n x(n)] = j \frac{dX(e^{j\omega})}{d\omega}$ 7. **Convolution:** $DTFT[x_1(n) * x_2(n)] = X_1(e^{j\omega})X_2(e^{j\omega})$ 8. **Multiplication:** $DTFT[x_1(n)x_2(n)] = \frac{1}{2\pi} [X_1(e^{j\omega}) \circledast X_2(e^{j\omega})]$ 9. **Parseval's Theorem:** $\sum_{n=-\infty}^{\infty} |x(n)|^2 = \frac{1}{2\pi} \int_{-\pi}^{\pi} |X(e^{j\omega})|^2 d\omega$ ### Discrete Fourier Transform (DFT) Transforms finite discrete-time sequences to finite discrete frequency sequences. #### Definition For an N-point sequence $x(n)$: $X(k) = \sum_{n=0}^{N-1} x(n)W_N^{nk}$, for $k=0, 1, ..., N-1$, where $W_N = e^{-j2\pi/N}$ is the twiddle factor. #### Inverse DFT (IDFT) $x(n) = \frac{1}{N} \sum_{k=0}^{N-1} X(k)W_N^{-nk}$, for $n=0, 1, ..., N-1$. #### Properties of DFT 1. **Periodicity:** $x(n)=x(n+N)$ and $X(k)=X(k+N)$. 2. **Linearity:** $DFT[ax_1(n)+bx_2(n)] = aX_1(k)+bX_2(k)$. 3. **Time Reversal:** $DFT[x((N-n)\pmod N)] = X((N-k)\pmod N)$. 4. **Circular Time Shift:** $DFT[x((n-l)\pmod N)] = W_N^{kl}X(k)$. 5. **Circular Frequency Shift:** $DFT[x(n)W_N^{-ln}] = X((k-l)\pmod N)$. 6. **Circular Convolution:** $DFT[x_1(n) \circledast x_2(n)] = X_1(k)X_2(k)$. 7. **Circular Correlation:** $DFT[R_{x_1x_2}(n)] = X_1(k)X_2^*(k)$. ### Fast Fourier Transform (FFT) Efficient algorithm to compute DFT, reducing computational complexity from $O(N^2)$ to $O(N \log_2 N)$. #### Radix-2 Algorithms ($N=2^m$) 1. **Decimation-In-Time (DIT) FFT:** * Input $x(n)$ is in bit-reversed order, output $X(k)$ is in normal order. * Decomposes DFT into smaller DFTs by splitting $x(n)$ into even and odd indexed samples. * Butterfly operation: $A = (a + bW_N^k)$, $B = (a - bW_N^k)$. 2. **Decimation-In-Frequency (DIF) FFT:** * Input $x(n)$ is in normal order, output $X(k)$ is in bit-reversed order. * Decomposes DFT by splitting $X(k)$ into even and odd indexed samples. * Butterfly operation: $A = (a + b)$, $B = (a - b)W_N^k$. #### Number of Operations For an N-point FFT ($N=2^m$): * **Complex Multiplications:** $(N/2) \log_2 N$ * **Complex Additions:** $N \log_2 N$ #### Inverse FFT IDFT can be computed using FFT by $x(n) = \frac{1}{N} DFT[X^*(k)]^*$. ### FIR Filters Finite Impulse Response (FIR) filters have a finite-duration impulse response $h(n)$. #### Characteristics of FIR Filters with Linear Phase FIR filters can achieve exact linear phase, meaning constant group delay. This occurs when the impulse response $h(n)$ is symmetric ($h(n) = h(N-1-n)$) or antisymmetric ($h(n) = -h(N-1-n)$) about the center point $(N-1)/2$. #### Design Techniques for FIR Filters 1. **Fourier Series Method:** * Obtain desired impulse response $h_d(n)$ from desired frequency response $H_d(e^{j\omega})$ by inverse DTFT. * Truncate $h_d(n)$ to length $N$ by applying a window function $w(n)$, so $h(n) = h_d(n)w(n)$. * The transfer function is $H(z) = \sum_{n=0}^{N-1} h(n)z^{-n}$. * **Gibbs Phenomenon:** Abrupt truncation causes ripples in passband and stopband. 2. **Window Method:** Uses different window functions to smoothly truncate $h_d(n)$, reducing Gibbs phenomenon. * **Rectangular Window:** $w_R(n) = 1$ for $0 \le n \le N-1$. (Smallest mainlobe, highest sidelobes). * **Triangular (Bartlett) Window:** $w_T(n) = 1 - \frac{2|n-(N-1)/2|}{N-1}$ for $0 \le n \le N-1$. (Wider mainlobe, lower sidelobes than rectangular). * **Hanning Window:** $w_{Han}(n) = 0.5 + 0.5\cos\left(\frac{2\pi n}{N-1}\right)$ for $0 \le n \le N-1$. * **Hamming Window:** $w_{Ham}(n) = 0.54 + 0.46\cos\left(\frac{2\pi n}{N-1}\right)$ for $0 \le n \le N-1$. * **Blackman Window:** $w_{Bla}(n) = 0.42 + 0.5\cos\left(\frac{2\pi n}{N-1}\right) + 0.08\cos\left(\frac{4\pi n}{N-1}\right)$ for $0 \le n \le N-1$. * **Kaiser Window:** Allows adjustable trade-off between mainlobe width and sidelobe attenuation using a parameter $\beta$. 3. **Frequency Sampling Technique:** * Sample the desired frequency response $H_d(e^{j\omega})$ at $N$ points to get $H(k)$. * Compute $h(n)$ by taking the IDFT of $H(k)$. * $H(z) = \sum_{n=0}^{N-1} h(n)z^{-n}$. #### Structures for Realization of FIR Systems 1. **Direct Form:** $H(z) = \sum_{n=0}^{N-1} h(n)z^{-n}$. 2. **Transposed Form:** Obtained by transposing the direct form. 3. **Cascade Form:** $H(z) = \prod_{i=1}^K H_i(z)$, where $H_i(z)$ are typically 1st or 2nd order. 4. **Lattice Structure:** Common in speech processing. 5. **Linear Phase Realizations:** Exploits symmetry to reduce computational cost. ### IIR Filters Infinite Impulse Response (IIR) filters have an infinite-duration impulse response $h(n)$. #### Requirements for Transformation (Analog to Digital) 1. Imaginary axis in s-plane maps to unit circle in z-plane. 2. Left half of s-plane maps to interior of unit circle in z-plane (for stability). #### Design of IIR Filter by Approximation of Derivatives Replace $s$ in $H_a(s)$ with an approximation of the derivative in the digital domain. 1. **Backward Difference:** $s \approx \frac{1-z^{-1}}{T}$. Maps left s-plane to a circle inside the unit circle. 2. **Forward Difference:** $s \approx \frac{z-1}{T}$. Maps left s-plane to a circle outside the unit circle (unstable). #### Design of IIR Filter by Impulse Invariant Transformation $h(n) = h_a(nT)$. This method directly samples the analog impulse response. * **Mapping:** A pole at $s=p_i$ in $H_a(s)$ maps to a pole at $z=e^{p_i T}$ in $H(z)$. * Preserves stability (left s-plane to inside unit circle). * Suffers from aliasing (many-to-one mapping of frequency). #### Design of IIR Filter by the Bilinear Transformation Method Approximates integration using the trapezoidal rule. * **Mapping:** $s \approx \frac{2}{T}\frac{1-z^{-1}}{1+z^{-1}}$. * Maps imaginary axis of s-plane to unit circle in z-plane (one-to-one). * Maps left s-plane to inside unit circle (preserves stability). * Introduces **frequency warping**: $\omega = \frac{2}{T}\tan\left(\frac{\Omega T}{2}\right)$ (non-linear relationship between analog $\Omega$ and digital $\omega$). * **Prewarping:** Adjust analog cutoff frequencies before transformation to compensate for warping. #### Design of Low-pass Digital Butterworth Filter 1. **Magnitude Squared Response:** $|H_a(j\Omega)|^2 = \frac{1}{1 + (\Omega/\Omega_c)^{2N}}$, where $N$ is filter order, $\Omega_c$ is 3dB cutoff. 2. **Order N and Cutoff $\Omega_c$:** Determined from passband/stopband specifications. 3. **Analog Transfer Function:** Poles are on a circle in the s-plane. 4. **Transformation:** Use Bilinear or Impulse Invariant methods to get $H(z)$. #### Design of Low-pass Chebyshev Filter 1. **Magnitude Squared Response (Type I):** $|H_a(j\Omega)|^2 = \frac{1}{1 + \epsilon^2 C_N^2(\Omega/\Omega_c)}$, where $\epsilon$ relates to passband ripple, $C_N(\cdot)$ is Chebyshev polynomial. 2. **Order N and Cutoff $\Omega_c$:** Determined from passband/stopband specifications. 3. **Analog Transfer Function:** Poles are on an ellipse in the s-plane. 4. **Transformation:** Use Bilinear or Impulse Invariant methods to get $H(z)$. #### Inverse Chebyshev Filters (Type-II) Maximally flat passband and equiripple stopband. #### Elliptic Filters (Cauer Filters) Equiripple in both passband and stopband. Offer steepest rolloff for a given order. #### Frequency Transformation Used to convert a prototype low-pass filter into other filter types (high-pass, band-pass, band-stop). 1. **Analog Frequency Transformation:** Substitute $s$ in $H_p(s)$ with a function of $s$ to get $H(s)$. 2. **Digital Frequency Transformation:** Substitute $z^{-1}$ in $H_p(z)$ with a function of $z^{-1}$ to get $H(z)$. ### Multi-rate Digital Signal Processing Processing signals at more than one sampling rate. #### Sampling Rate Conversion 1. **Down Sampling (Decimation):** Reduce sampling rate by factor $D$. $y(n) = x(Dn)$. Requires an anti-aliasing filter (low-pass filter) before downsampling to prevent aliasing. 2. **Up Sampling (Interpolation):** Increase sampling rate by factor $I$. $y(n) = \begin{cases} x(n/I) & \text{if } n \text{ is a multiple of } I \\ 0 & \text{otherwise} \end{cases}$. Requires an anti-imaging filter (low-pass filter) after upsampling to remove image spectra. 3. **Sampling Rate Conversion by I/D:** Cascade an upsampler by $I$ and a downsampler by $D$. The anti-imaging and anti-aliasing filters are combined into a single low-pass filter. #### Identities * Scaling and addition commute with D/I operations. * Delay by D samples before downsampler (D) is equal to delay by 1 sample after downsampler (D). * Delay by 1 sample before upsampler (I) is equal to delay by I samples after upsampler (I). * Cascading $D_1$ and $D_2$ downsamplers is equivalent to a single $D_1D_2$ downsampler. * Cascading $I_1$ and $I_2$ upsamplers is equivalent to a single $I_1I_2$ upsampler. * An upsampler (I) followed by a downsampler (D=I) results in no change in input signal. * A downsampler (D) followed by an upsampler (I=D) results in an output that is same as input at new sampling instants. * Upsampler (I) and Downsampler (D) commute if $I$ and $D$ are co-prime. #### Polyphase Decomposition Decomposes a filter $H(z)$ into parallel branches, allowing efficient implementation in multirate systems. * **Type I:** $H(z) = \sum_{k=0}^{D-1} z^{-k}P_k(z^D)$ * **Type II:** $H(z) = \sum_{k=0}^{D-1} z^{k}R_k(z^D)$ (Polyphase components $P_k(z^D)$ or $R_k(z^D)$ operate at the lower rate). #### Multistage Decimators and Interpolators For large $D$ or $I$, multistage implementations (cascading several decimators/interpolators) are more computationally efficient. #### Efficient Transversal Structure for Decimator The anti-aliasing filter $h(n)$ can be implemented using polyphase components to operate at the lower sampling rate, reducing computations. #### Efficient Transversal Structure for Interpolator The anti-imaging filter $h(n)$ can be implemented using polyphase components to operate at the lower sampling rate, reducing computations. ### Introduction to DSP Processors Specialized microprocessors designed for efficient digital signal processing, often in real-time. #### Advantages of DSP Processors over Conventional Microprocessors * Optimized architecture and instruction sets for DSP algorithms (e.g., MAC operations). * Support fast processing of arrays. * Parallel execution of instructions. * Separate data and program memories (Harvard/Modified Harvard architecture). * Dedicated hardware for MAC units, shifters, etc. * On-chip memories and peripherals. #### Multiplier and Multiplier Accumulator (MAC) Essential for DSP. A dedicated MAC unit integrates multiplier and accumulator for single-cycle operation. #### Modified Bus Structures and Memory Access Schemes 1. **Von Neumann Architecture:** Single bus for data and instructions (slower). 2. **Harvard Architecture:** Separate buses for program and data memory (faster, but less flexible). 3. **Modified Harvard Architecture:** Combines Harvard with shared data/program memory access (common in P-DSPs). 4. **Multiple Access Memory:** Permits more than one memory access per clock period. 5. **Multiported Memory:** Has multiple independent data and address buses for simultaneous access. #### VLIW Architecture (Very Long Instruction Word) Executes multiple instructions (a "very long instruction word") simultaneously using multiple processing units (ALUs, MACs). #### Pipelining Splits instruction execution into stages (fetch, decode, execute, write-back) to increase throughput by processing multiple instructions concurrently. #### Special Addressing Modes in P-DSPs * **Short Immediate/Direct Addressing:** Operands/addresses are part of the instruction. * **Memory Mapped Addressing:** Accesses CPU/I/O registers as memory locations. * **Indirect Addressing:** Uses auxiliary registers (ARs) to store operand addresses, often with auto-increment/decrement. * **Bit Reversed Addressing:** For FFT computations. * **Circular Addressing:** For implementing circular buffers. #### On-chip Peripherals Relieve CPU from routine functions and reduce chip count. * Timers, Serial Ports (general purpose, TDM, buffered), Parallel I/O Ports (general purpose, host, comm ports), A/D and D/A Converters. #### P-DSPs with RISC and CISC * **RISC (Reduced Instruction Set Computer):** Simpler instruction set, faster execution, pipelines, smaller control unit, higher parallelism. * **CISC (Complex Instruction Set Computer):** Rich instruction set, complex instructions (e.g., MACD), shorter assembly programs, easier microprogramming. #### Architecture of TMS320C50 (Example P-DSP) * Fixed-point, 16-bit processor, advanced Harvard architecture. * **CPU:** Central Arithmetic Logic Unit (CALU), Parallel Logic Unit (PLU), Auxiliary Register Arithmetic Unit (ARAU), Memory Mapped Registers, Program Controller. * **Bus Structure:** Program Bus (PB), Program Read Bus (PRB), Data Read Bus (DB), Data Read Address Bus (DRB). * **On-chip Memory:** RAM (DARAM, SARAM), ROM. * **On-chip Peripherals:** Clock Generator, Hardware Timer, Software-programmable Wait-state Generators, General Purpose I/O Pins, Parallel I/O Ports, Serial Port Interface (general purpose, buffered, TDM), Host Port Interface. * **User Maskable Interrupts:** External and internal interrupts with defined priorities.