Digital Signal Processing – Useful Resources The following resources contain additional information on Digital Signal Processing. Please use them to get more in-depth knowledge on this. Useful Links on Digital Signal Processing − Wikipedia Reference for Digital Signal Processing. − Video Lectures Digital Signal Processing. Useful Books on Digital Signal Processing To enlist your site on this page, please drop an email to [email protected] Learning working make money
Discuss Digital Signal Processing Digital Signal Processing is an important branch of Electronics and Telecommunication engineering that deals with the improvisation of reliability and accuracy of the digital communication by employing multiple techniques. This tutorial explains the basic concepts of digital signal processing in a simple and easy-to-understand manner. Learning working make money
DSP – In-Place Computation This efficient use of memory is important for designing fast hardware to calculate the FFT. The term in-place computation is used to describe this memory usage. Decimation in Time Sequence In this structure, we represent all the points in binary format i.e. in 0 and 1. Then, we reverse those structures. The sequence we get after that is known as bit reversal sequence. This is also known as decimation in time sequence. In-place computation of an eight-point DFT is shown in a tabular format as shown below − POINTS BINARY FORMAT REVERSAL EQUIVALENT POINTS 0 000 000 0 1 001 100 4 2 010 010 2 3 011 110 6 4 100 001 1 5 101 101 5 6 110 011 3 7 111 111 7 Decimation in Frequency Sequence Apart from time sequence, an N-point sequence can also be represented in frequency. Let us take a four-point sequence to understand it better. Let the sequence be $x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7]$. We will group two points into one group, initially. Mathematically, this sequence can be written as; $$x[k] = sum_{n = 0}^{N-1}x[n]W_N^{n-k}$$ Now let us make one group of sequence number 0 to 3 and another group of sequence 4 to 7. Now, mathematically this can be shown as; $$displaystylesumlimits_{n = 0}^{frac{N}{2}-1}x[n]W_N^{nk}+displaystylesumlimits_{n = N/2}^{N-1}x[n]W_N^{nk}$$ Let us replace n by r, where r = 0, 1 , 2….(N/2-1). Mathematically, $$displaystylesumlimits_{n = 0}^{frac{N}{2}-1}x[r]W_{N/2}^{nr}$$ We take the first four points (x[0], x[1], x[2], x[3]) initially, and try to represent them mathematically as follows − $sum_{n = 0}^3x[n]W_8^{nk}+sum_{n = 0}^3x[n+4]W_8^{(n+4)k}$ $= lbrace sum_{n = 0}^3x[n]+sum_{n = 0}^3x[n+4]W_8^{(4)k}rbrace times W_8^{nk}$ now $X[0] = sum_{n = 0}^3(X[n]+X[n+4])$ $X[1] = sum_{n = 0}^3(X[n]+X[n+4])W_8^{nk}$ $= [X[0]-X[4]+(X[1]-X[5])W_8^1+(X[2]-X[6])W_8^2+(X[3]-X[7])W_8^3$ We can further break it into two more parts, which means instead of breaking them as 4-point sequence, we can break them into 2-point sequence. Learning working make money
Digital Signal Processing Tutorial Job Search Digital Signal Processing is an important branch of Electronics and Telecommunication engineering that deals with the improvisation of reliability and accuracy of the digital communication by employing multiple techniques. This tutorial explains the basic concepts of digital signal processing in a simple and easy-to-understand manner. Audience This tutorial is meant for the students of E&TC, Electrical and Computer Science engineering. In addition, it should be useful for any enthusiastic reader who would like to understand more about various signals, systems, and the methods to process a digital signal. Prerequisites Digital signal processing deals with the signal phenomenon. Along with it, in this tutorial, we have shown the filter design using the concept of DSP. This tutorial has a good balance between theory and mathematical rigor. Before proceeding with this tutorial, the readers are expected to have a basic understanding of discrete mathematical structures. Learning working make money
DSP – Z-Transform Inverse If we want to analyze a system, which is already represented in frequency domain, as discrete time signal then we go for Inverse Z-transformation. Mathematically, it can be represented as; $$x(n) = Z^{-1}X(Z)$$ where x(n) is the signal in time domain and X(Z) is the signal in frequency domain. If we want to represent the above equation in integral format then we can write it as $$x(n) = (frac{1}{2Pi j})oint X(Z)Z^{-1}dz$$ Here, the integral is over a closed path C. This path is within the ROC of the x(z) and it does contain the origin. Methods to Find Inverse Z-Transform When the analysis is needed in discrete format, we convert the frequency domain signal back into discrete format through inverse Z-transformation. We follow the following four ways to determine the inverse Z-transformation. Long Division Method Partial Fraction expansion method Residue or Contour integral method Long Division Method In this method, the Z-transform of the signal x (z) can be represented as the ratio of polynomial as shown below; $$x(z)=N(Z)/D(Z)$$ Now, if we go on dividing the numerator by denominator, then we will get a series as shown below $$X(z) = x(0)+x(1)Z^{-1}+x(2)Z^{-2}+…quad…quad…$$ The above sequence represents the series of inverse Z-transform of the given signal (for n≥0) and the above system is causal. However for n<0 the series can be written as; $$x(z) = x(-1)Z^1+x(-2)Z^2+x(-3)Z^3+…quad…quad…$$ Partial Fraction Expansion Method Here also the signal is expressed first in N (z)/D (z) form. If it is a rational fraction it will be represented as follows; $x(z) = b_0+b_1Z^{-1}+b_2Z^{-2}+…quad…quad…+b_mZ^{-m})/(a_0+a_1Z^{-1}+a_2Z^{-2}+…quad…quad…+a_nZ^{-N})$ The above one is improper when m<n and an≠0 If the ratio is not proper (i.e. Improper), then we have to convert it to the proper form to solve it. Residue or Contour Integral Method In this method, we obtain inverse Z-transform x(n) by summing residues of $[x(z)Z^{n-1}]$ at all poles. Mathematically, this may be expressed as $$x(n) = displaystylesumlimits_{allquad polesquad X(z)}residuesquad of[x(z)Z^{n-1}]$$ Here, the residue for any pole of order m at $z = beta$ is $$Residues = frac{1}{(m-1)!}lim_{Z rightarrow beta}lbrace frac{d^{m-1}}{dZ^{m-1}}lbrace (z-beta)^mX(z)Z^{n-1}rbrace$$ Learning working make money
DSP – DFT Discrete Cosine Transform DCT (Discrete Cosine Transform) is an N-input sequence x(n) , 0≤n≤N-1 , as a linear transformation or combination of complex exponentials. As a result, the DFT coefficients are in general, complex even if x(n) is real. Suppose, we try to find out an orthogonal transformation which has N×N structure that expressed a real sequence x(n) as a linear combination of cosine sequence. We already know that − $X(K) = displaystylesumlimits_{n = 0}^{N-1}x(n)cosfrac{2Pi kn}{N}0leq k leq N-1$ And $x(n) = frac{1}{N}sum_{k = 0}^{N-1}x(k)cosfrac{2Pi kn}{N}0leq k leq N-1$ This is possible if N point sequence x(n) is real and even. Thus, $x(n) = x(N-n),0leq n leq (N-1)$. The resulting DFT itself is real and even. These things make it clear that we could possibly device a discrete cosine transform, for any N point real sequence by taking the 2N point DFT of an “Even extension” of sequence. DCT is, basically, used in image and speech processing. It is also used in compression of images and speech signals. $DFT[s(n)] = S(k) = sum_{n = 0}^{2N-1}s(n)W_{2N}^{nk},quad wherequad 0leq k leq 2N-1$ $S(k) = displaystylesumlimits_{n = 0}^{N-1}x(n)W_{2N}^{nk}+displaystylesumlimits_{n = N}^{2N-1}x(2N-n-1)W_{2N}^{nk};quad wherequad 0leq kleq 2N-1$ $Rightarrow S(k) = W_{2N}^{-k/2}+sum_{n = 0}^{N-1}x(n) [W_{2N}^{nk}W_{2N}^{k/2}+W_{2N}^{-nk}W_{2N}^{-k/2}];quad wherequad 0leq kleq 2N-1$ $Rightarrow S(k) = W_{2N}^{frac{k}{2}}sum_{n = 0}^{N-1}x(n)cos [frac{pi}{N}(n+frac{1}{2})k];quad wherequad 0leq kleq 2N-1$ DCT is defined by, $V(k) = 2sum_{n = 0}^{N-1}x(n)cos [frac{pi}{2}(n+frac{1}{2})k]quad wherequad 0leq kleq N-1$ $Rightarrow V(k) = W_{2N}^{frac{k}{2}}S(k)quad orquad S(k) = W_{2N}^{frac{k}{2}}V(k),quad wherequad 0leq kleq N-1$ $Rightarrow V(k) = 2R[W_{2N}^{frac{k}{2}}sum_{n = 0}^{N-1}x(n)W_{2N}^{nk}],quad wherequad 0leq kleq N-1$ Learning working make money
DSP – Z-Transform Introduction Discrete Time Fourier Transform(DTFT) exists for energy and power signals. Z-transform also exists for neither energy nor Power (NENP) type signal, up to a certain extent only. The replacement $z=e^{jw}$ is used for Z-transform to DTFT conversion only for absolutely summable signal. So, the Z-transform of the discrete time signal x(n) in a power series can be written as − $$X(z) = sum_{n-infty}^infty x(n)Z^{-n}$$ The above equation represents a two-sided Z-transform equation. Generally, when a signal is Z-transformed, it can be represented as − $$X(Z) = Z[x(n)]$$ Or $x(n) longleftrightarrow X(Z)$ If it is a continuous time signal, then Z-transforms are not needed because Laplace transformations are used. However, Discrete time signals can be analyzed through Z-transforms only. Region of Convergence Region of Convergence is the range of complex variable Z in the Z-plane. The Z- transformation of the signal is finite or convergent. So, ROC represents those set of values of Z, for which X(Z) has a finite value. Properties of ROC ROC does not include any pole. For right-sided signal, ROC will be outside the circle in Z-plane. For left sided signal, ROC will be inside the circle in Z-plane. For stability, ROC includes unit circle in Z-plane. For Both sided signal, ROC is a ring in Z-plane. For finite-duration signal, ROC is entire Z-plane. The Z-transform is uniquely characterized by − Expression of X(Z) ROC of X(Z) Signals and their ROC x(n) X(Z) ROC $delta(n)$ $1$ Entire Z plane $U(n)$ $1/(1-Z^{-1})$ Mod(Z)>1 $a^nu(n)$ $1/(1-aZ^{-1})$ Mod(Z)>Mod(a) $-a^nu(-n-1)$ $1/(1-aZ^{-1})$ Mod(Z)<Mod(a) $na^nu(n)$ $aZ^{-1}/(1-aZ^{-1})^2$ Mod(Z)>Mod(a) $-a^nu(-n-1)$ $aZ^{-1}/(1-aZ^{-1})^2$ Mod(Z)<Mod(a) $U(n)cos omega n$ $(Z^2-Zcos omega)/(Z^2-2Z cos omega +1)$ Mod(Z)>1 $U(n)sin omega n$ $(Zsin omega)/(Z^2-2Z cos omega +1)$ Mod(Z)>1 Example Let us find the Z-transform and the ROC of a signal given as $x(n) = lbrace 7,3,4,9,5rbrace$, where origin of the series is at 3. Solution − Applying the formula we have − $X(z) = sum_{n=-infty}^infty x(n)Z^{-n}$ $= sum_{n=-1}^3 x(n)Z^{-n}$ $= x(-1)Z+x(0)+x(1)Z^{-1}+x(2)Z^{-2}+x(3)Z^{-3}$ $= 7Z+3+4Z^{-1}+9Z^{-2}+5Z^{-3}$ ROC is the entire Z-plane excluding Z = 0, ∞, -∞ Learning working make money
Digital Signal Processing – DFT Introduction Like continuous time signal Fourier transform, discrete time Fourier Transform can be used to represent a discrete sequence into its equivalent frequency domain representation and LTI discrete time system and develop various computational algorithms. X (jω) in continuous F.T, is a continuous function of x(n). However, DFT deals with representing x(n) with samples of its spectrum X(ω). Hence, this mathematical tool carries much importance computationally in convenient representation. Both, periodic and non-periodic sequences can be processed through this tool. The periodic sequences need to be sampled by extending the period to infinity. Frequency Domain Sampling From the introduction, it is clear that we need to know how to proceed through frequency domain sampling i.e. sampling X(ω). Hence, the relationship between sampled Fourier transform and DFT is established in the following manner. Similarly, periodic sequences can fit to this tool by extending the period N to infinity. Let an Non periodic sequence be, $X(n) = lim_{N to infty}x_N(n)$ Defining its Fourier transform, $X(omega ) = sum_{n=-infty}^infty x(n)e^{-jwn}X(Kdelta omega)$…eq(1) Here, X(ω) is sampled periodically, at every δω radian interval. As X(ω) is periodic in 2π radians, we require samples only in fundamental range. The samples are taken after equidistant intervals in the frequency range 0≤ω≤2π. Spacing between equivalent intervals is $delta omega = frac{2pi }{N}k$ radian. Now evaluating, $omega = frac{2pi}{N}k$ $X(frac{2pi}{N}k) = sum_{n = -infty}^infty x(n)e^{-j2pi nk/N},$ …eq(2) where k=0,1,……N-1 After subdividing the above, and interchanging the order of summation $X(frac{2pi}{N}k) = displaystylesumlimits_{n = 0}^{N-1}[displaystylesumlimits_{l = -infty}^infty x(n-Nl)]e^{-j2pi nk/N}$ …eq(3) $sum_{l=-infty}^infty x(n-Nl) = x_p(n) = aquad periodicquad functionquad ofquad periodquad Nquad andquad itsquad fourierquad seriesquad = sum_{k = 0}^{N-1}C_ke^{j2pi nk/N}$ where, n = 0,1,…..,N-1; ‘p’- stands for periodic entity or function The Fourier coefficients are, $C_k = frac{1}{N}sum_{n = 0}^{N-1}x_p(n)e^{-j2pi nk/N}$k=0,1,…,N-1…eq(4) Comparing equations 3 and 4, we get ; $NC_k = X(frac{2pi}{N}k)$ k=0,1,…,N-1…eq(5) $NC_k = X(frac{2pi}{N}k) = X(e^{jw}) = displaystylesumlimits_{n = -infty}^infty x_p(n)e^{-j2pi nk/N}$…eq(6) From Fourier series expansion, $x_p(n) = frac{1}{N}displaystylesumlimits_{k = 0}^{N-1}NC_ke^{j2pi nk/N} = frac{1}{N}sum_{k = 0}^{N-1}X(frac{2pi}{N}k)e^{j2pi nk/N}$…eq(7) Where n=0,1,…,N-1 Here, we got the periodic signal from X(ω). $x(n)$ can be extracted from $x_p(n)$ only, if there is no aliasing in the time domain. $Ngeq L$ N = period of $x_p(n)$ L= period of $x(n)$ $x(n) = begin{cases}x_p(n), & 0leq nleq N-1\0, & Otherwiseend{cases}$ The mapping is achieved in this manner. Properties of DFT Linearity It states that the DFT of a combination of signals is equal to the sum of DFT of individual signals. Let us take two signals x1(n) and x2(n), whose DFT s are X1(ω) and X2(ω) respectively. So, if $x_1(n)rightarrow X_1(omega)$and$x_2(n)rightarrow X_2(omega)$ Then $ax_1(n)+bx_2(n)rightarrow aX_1(omega)+bX_2(omega)$ where a and b are constants. Symmetry The symmetry properties of DFT can be derived in a similar way as we derived DTFT symmetry properties. We know that DFT of sequence x(n) is denoted by X(K). Now, if x(n) and X(K) are complex valued sequence, then it can be represented as under $x(n) = x_R(n)+jx_1(n),0leq nleq N-1$ And $X(K) = X_R(K)+jX_1(K),0leq Kleq N-1$ Duality Property Let us consider a signal x(n), whose DFT is given as X(K). Let the finite duration sequence be X(N). Then according to duality theorem, If, $x(n)longleftrightarrow X(K)$ Then, $X(N)longleftrightarrow Nx[((-k))_N]$ So, by using this theorem if we know DFT, we can easily find the finite duration sequence. Complex Conjugate Properties Suppose, there is a signal x(n), whose DFT is also known to us as X(K). Now, if the complex conjugate of the signal is given as x*(n), then we can easily find the DFT without doing much calculation by using the theorem shown below. If, $x(n)longleftrightarrow X(K)$ Then, $x*(n)longleftrightarrow X*((K))_N = X*(N-K)$ Circular Frequency Shift The multiplication of the sequence x(n) with the complex exponential sequence $e^{j2Pi kn/N}$ is equivalent to the circular shift of the DFT by L units in frequency. This is the dual to the circular time shifting property. If, $x(n)longleftrightarrow X(K)$ Then, $x(n)e^{j2Pi Kn/N}longleftrightarrow X((K-L))_N$ Multiplication of Two Sequence If there are two signal x1(n) and x2(n) and their respective DFTs are X1(k) and X2(K), then multiplication of signals in time sequence corresponds to circular convolution of their DFTs. If, $x_1(n)longleftrightarrow X_1(K)quad&quad x_2(n)longleftrightarrow X_2(K)$ Then, $x_1(n)times x_2(n)longleftrightarrow X_1(K)© X_2(K)$ Parseval’s Theorem For complex valued sequences x(n) and y(n), in general If, $x(n)longleftrightarrow X(K)quad &quad y(n)longleftrightarrow Y(K)$ Then, $sum_{n = 0}^{N-1}x(n)y^*(n) = frac{1}{N}sum_{k = 0}^{N-1}X(K)Y^*(K)$ Learning working make money
DSP – System Properties Solved Examples Example 1 − Check whether $y(t) = x*(t)$ is linear or non-linear. Solution − The function represents the conjugate of input. It can be verified by either first law of homogeneity and law of additivity or by the two rules. However, verifying through rules is lot easier, so we will go by that. If the input to the system is zero, the output also tends to zero. Therefore, our first condition is satisfied. There is no non-linear operator used either at the input nor the output. Therefore, the system is Linear. Example 2 − Check whether $y(t)=begin{cases}x(t+1), & t > 0\x(t-1), & tleq 0end{cases}$ is linear or non linear Solution − Clearly, we can see that when time becomes less than or equal to zero the input becomes zero. So, we can say that at zero input the output is also zero and our first condition is satisfied. Again, there is no non-linear operator used at the input nor at the output. Therefore, the system is Linear. Example 3 − Check whether $y(t) = sin t.x(t)$ is stable or not. Solution − Suppose, we have taken the value of x(t) as 3. Here, sine function has been multiplied with it and maximum and minimum value of sine function varies between -1 to +1. Therefore, the maximum and minimum value of the whole function will also vary between -3 and +3. Thus, the system is stable because here we are getting a bounded input for a bounded output. Learning working make money
DSP – Time-Variant Systems For a time variant system, also, output and input should be delayed by some time constant but the delay at the input should not reflect at the output. All time scaling cases are examples of time variant system. Similarly, when coefficient in the system relationship is a function of time, then also, the system is time variant. Examples a) $y(t) = x[cos T]$ If the above signal is first passed through the system and then through the time delay, the output will be $xcos (T-t)$. If it is passed through the time delay first and then through the system, it will be $x(cos T-t)$. As the outputs are not same, the system is time variant. b) $y(T) = cos T.x(T)$ If the above expression is first passed through the system and then through the time delay, then the output will be $cos(T-t)x(T-t)$. However, if the expression is passed through the time delay first and then through the system, the output will be $cos T.x(T-t)$. As the outputs are not same, clearly the system is time variant. Learning working make money