DSP Lect Note - 6th Sem Etc - PNG
DSP Lect Note - 6th Sem Etc - PNG
DIGITAL SIGNAL
PROCESSING
TH
[6 SEM ETC -ETT603]
PREPARED BY
The input signal is applied to the anti aliasing filter. The low pass filter removes the high frequency
noise and to band-limit the signals.
The sample and hold provides the discrete time signal to A/D converter.
The ADC converts the along signal into its equivalent digital signal.
The Digital Signal Processor may be a large programmable digital computer, programmed to perform
the desired operations on the input signals.
The output of DSP is converted to analog signal by DAC.
The high frequency components in DAC output are released by the reconstruction filter.
ADVANTAGES OF DSP OVER ASP : -
1. Digital signal processing operations can be changed by changing the program in digital programmable
system. This means that these are flexible system.
2. There is a better control of accuracy in digital systems compared to analog systems.
3. Digital signals are easily stored on magnetic media (tape or disk) without loss of signal quality.
4. Sophisticated signal processing algorithms can be implemented by DSP method.
5. Digital circuits are less sensitive to tolerance of component values.
6. Digital systems are independent of temperature, ageing and other external parameters.
7. Digital circuits can be reproduced easily in large quantities at comparatively lower cost.
8. Cost of processing per signal in DSP is reduced by time sharing of a processors among multiple signals
9. As adaptive filters are used in DSP which can be easily adjusted in digital implementation.
10. Digital systems can be cascaded without any loading effect.
11. As digital Codes are often used in the transmission of information. So it becomes more data secure.
12. Digital signals typically use less bandwidth. So we can send more information in the same space
13. Data Transmission is at a higher rate.
14. There is minimal electromagnetic interference in digital technology.
15. It enables multi-directional transmission simultaneously etc.
Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 603] <INTRODUCTION TO DSP> [Page 1.3]
LIMITATIONS OF DSP: -
1. System Complexity: - System complexity increased in the digital
processing of analog signals because of the devices such as A/D and
D/A converters and their associated filters are used here.
2. Bandwidth limited by Sampling Rate: - Processing of signals
beyond higher frequencies (beyond GHz) and below lower
frequencies (a few Hz) involves limitations
3. Power Consumption: - Processing of signals involves more power consumption.
4. Information is lost because we only take samples of the signal at intervals.
APPLICATIONS OF DSP: -
As a matter of fact, there are various application areas of DSP due to the availability of high resolution
spectral analysis. Some of these areas are can be listed as under: -
1. Speech Processing
2. Image Processing
3. Radar Signal Processing
4. Sonar Signal Processing
5. Digital Communication
6. Spectral Analysis
7. Instrumentation and control
Few other application of DSP are: -
1. Transmission lines.
2. Advanced Optical Fiber Communication
3. Analysis of sound & Vibration signals
4. Implementation of speech recognition algorithms.
5. VLSI Technology
6. Telecommunication networks
7. Microprocessor Systems
8. Satellite Communications
9. Telephony Transmission
10. Astronomy
11. Industrial noise control
12. Biomedical Engineering etc
CLASSIFICATION OF SIGNALS: -
There are various methods of classifying signals based on different features.
Based on type of Independent Variables : -
Continuous Time Signal & Discrete Time Signal
Depending upon the number of independent variable : -
1-Dimentional Signal, 2-Dimentional Signal & M-Dimensional Signal
Depending upon the certainty by which the signal can be uniquely described : -
Deterministic Signal & Random Signal
Based on repetition nature: -
Periodic Signal & Non-Periodic Signal
Based on reflection: -
Even Signal (Symmetric) & Odd Signal (Asymmetric/Anti-symmetric)
Continuous Time Signal: -
It is also referred as Analog Signal i.e. the signal is
represented continuously in time.
In simple words, a signal x (t) is said to be a continuous time
signal if it is defined for all time.
Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 603] <INTRODUCTION TO DSP> [Page 1.4]
Discrete Time Signal: -
Signals are represented as sequence at discrete time intervals. Thus it has discrete values only.
1-Dimentional Signal (1-D)
It is a function of single independent variables. Ex -
Speech Signal, Music Signal are function of time.
2-Dimentional Signal (2-D)
It is a function of two independent variables. Ex – Image
Signal, each frame of a B/W video signal etc.
M-Dimensional Signal (M-D)
It is function of m independent variable in time. Ex – Colour Signal (3-D) composed of RGB.
Deterministic Signal
A signal that can be uniquely determined by a well defined process such as a mathematical expression
or rule or table is called a deterministic signal.
For examples A Sinusoidal Signal can be expressed as v (t) = Vm Sin ωt, for t ≥0
A Square Signal can be expressed as x (t) = A for 0 < t < T/2 and x (t) = - A for T/2 < t < T
A Exponential function can be expressed as x (n) = ean for n ≥ 0
Random Signal
A signal that is generated in a random fashion and cannot be predicted ahead of
time is called random signal. Ex: - Speech Signal, ECG Signal, EEG Signal etc.
Periodic Signal
The periodic signal means, the signal which repeats every finite interval of time or a continuous time
signal x(t) is a function that satisfies the condition x(t+T) = x(t), for all „t‟. Ex-Sine, Square wave etc
Non-Periodic Signal
Any signal x (t) for which there is no value of T to satisfy the
relation given in equation x (t) = x (t +T) is known as non-
periodic signal. i.e. x (t+T) ≠ x (t), for all „t‟.
Even Signal (Symmetric)
A Signal x (t) or x (n) is referred to as even signal, if it is identical to its time reversal counter part i.e.
with its about origin. x (-t) = x (t) for all „t‟. Even Signals are Symmetric w.r.t vertical axis.
`
Odd Signal (Asymmetric/Anti-symmetric )
A Signal is said to be odd if x (- t) = - x (t) for all „t‟
However, let us assume that we want to use only one significant digit. To eliminate the excess digits,
we can either simply discard them (truncation) or discard them bv rounding the resulting number.
The resulting quantized signals xq(n) are shown in Table. We discuss only quantization by rounding,
although it is just as easy to treat truncation. The rounding process is graphically illustrated in Fig b.
The values allowed in the digital signal are called the quantization levels, whereas the distance Δ
between two successive quantization levels is called the quantization step size or resolution.
The rounding quantizer assigns each sample of x(n) to the nearest quantization level.
In contrast, a quantizer that performs truncation would have assigns each sample of x(n) to the
quantization level below it.
The quantization error eq(n) in rounding is limited to the range of that is
If xmin and xmax represent the minimum and maximum value of x(n ) and
L is the number of quantization levels, then
We define the dynamic range of the signal as xmix and xmin.
Here, we have xmix= 1, xmin = 0, & L=11, which leads to Δ =0.1.
Note if dynamic range is fixed, increasing the number of quantization
levels, L results in a decrease of the quantization step size.
So quantization error decreases & accuracy of quantizer increases.
In practice we can reduce quantization error to an insignificant
amount by choosing a sufficient number of quantization levels.
Theoretically, quantization of analog signals always results in a loss
of information. This is a result of ambiguity by quantization.
Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 603] <INTRODUCTION TO DSP> [Page 1.12]
Indeed, quantization is an irreversible or noninvertible process (i.e. a many-to-one mapping) since
all samples in a distance A /2 about a certain quantization level are assigned the same value.
This ambiguity makes the exact quantitative analysis of quantization extremely difficult.
CODING OF QUANTIZED SAMPLES
The coding process in an A/D converter assigns a unique binary number to each quantization level.
If we have L levels we need at least L different binary numbers. With a word length of b bits we can
create 2b different binary numbers. Hence we have 2b > L. or equivalently, b > log2L.
Thus the number of bits required in the coder is the smallest integer greater than or equal to log2 L.
In our example it can easily be seen that we need a coder with b = 4 bits.
Commercially available A/D converters may be obtained
with finite precision of b=16 or less.
Generally, for the high sampling speed and fine
quantization, the devices used become more expensive.
DIGITAL-TO-ANALOG CONVERSION
To convert a digital signal into an analog signal we can use
a digital-to-analog converter.
As stated previously, the task of a D/A converter is to interpolate between samples
The sampling theorem specifies the optimum interpolation for a band limited signal.
However, this type of interpolation is too complicated and hence impractical, as indicated previously.
From a practical view point, the simplest D/A converter is the zero order hold which simply holds
constant the value of one sample until the next one is received.
Additional improvement can be obtained by using linear interpolation as shown in fig to connect
successive samples with straight-line segments.
The zero-order hold and linear interpolator are analyzed. Better interpolation can be achieved by using
more sophisticated higher order interpolation techniques.
In general, suboptimum interpolation techniques result in passing frequencies above folding frequency.
Such frequency components are undesirable and are usually removed by passing the output of the
interpolator through a proper analog filter, which is called a Post Filter or Smoothing Filter.
Thus D/A conversion usually involve a suboptimum interpolator followed by a post filter.
ANALYSIS OF DIGITAL SIGNAL SYSTEMS VS DISCRETE-TIME SIGNAL SYSTEMS
We have seen that a digital signal is defined as a function of an integer in dependent variable and its
values are taken from a finite set of possible values.
The usefulness of such signals is a consequence of the possibilities offered by digital computers.
Computers operate on numbers, which are represented by a string of 0's and l's.
The length of this string (word length) is fixed and finite and usually is 8, 12, 16 or 32 bits.
The effects of finite word length in computations cause complications in the analysis of digital signal
processing systems. To avoid these complications, we neglect the quantized nature of digital signals
and systems in much o four analysis and consider them as discrete-time signals and systems.
-------------- ALL THE BEST -------------------- ALL THE BEST ----------------
Define Analog, Discrete and Digital Signals with diagram?
Draw the block diagram of Simple DSP System.
Write the Advantages of DSP over ASP.
Write the different Applications of DSP.
What is Continuous and Discrete Time Signal with Fig?
What are 1, 2 & Multi dimensional signals with example?
What do you mean by deterministic and random signal?
What is periodic and non-periodic signal with fig?
What is Symmetric and Asymmetric Signal with fig?
Write the properties of Even and Odd Signals.
What do you mean by multichannel and multi dimensional signals with examples?
What is Sampling & Quantization and where we use it.
Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 603] <DISCRETE TIME SIGNALS & SYSTEMS > [Page 2.1]
[CHAPTER-2]
---------------------- DISCRETE TIME SIGNALS & SYSTEMS ----------------------
SIGNAL: -
Discrete-time Signals are defined for discrete
values of independent variables (time).
Discrete-time signal is not defined at instants
between two successive samples.
Discrete time signals are represented in 2 ways
S (n), N1 ≤ n ≤ N2, where N1 and N2 are the
first and last sample point respectively in a
given discrete time signal. It represents non-
uniformly spaced samples and is shown in
below fig1.
Whereas S (nTs), N1 ≤ n ≤ N2, represents
uniformly spaced samples & is shown in below fig2.
(i) Decaying Exponential (ii) Rising Exponential (iii) Double Sided Growing & (iv) Double Sided Decaying Exponential Signal
Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 603] <DISCRETE TIME SIGNALS & SYSTEMS > [Page 2.3]
SINUSOIDAL SEQUENCE
There are two types of sinusoidal sequences;
that are called as the sine and cosine sequence.
A Sine Sequence is defines as s (n) = A Sin ω0n,
for all values of n.
Cosine Sequence is defines as s (n) = A Cos ω0 n, for all values of n.
SINC FUNCTION: -
𝐒𝐢𝐧 (𝛑𝐱)
The Sinc Function is mathematically expressed as Sinc (x) = 𝛑𝐱
for x = 0
Sin (x) = 1 at x = 0; Sin x = 0 at x = ±1, ±2, ±3 …
SIGNUM FUNCTION: -
𝟏, 𝐭 > 0
The CT Signum Function is mathematically defined as, sgn (t) =
−𝟏, 𝐭 < 0
It is an Odd and Anti-symmetric Function.
A discrete time Signum function can be obtained by
sampling the CT Signum function.
It is train of samples of values +1 for positive n and 1 for
negative n as shown in figure.
RECTANGULAR FUNCTION: -
A rectangular pulses of Unit Amplitude and Unit duration is
𝟏 𝟏
𝟏, − 𝟐 ≤ 𝐭 ≤ 𝟐
represented as rect (t) =
𝟎, 𝐎𝐭𝐡𝐞𝐫𝐰𝐢𝐬𝐞
A rectangular pulses of A Amplitude and T duration is
𝐓 𝐓
𝐭 𝐀, − ≤ 𝐭 ≤
represented as rect 𝐓 = 𝟐 𝟐. It is centered about the y-axis i.e. about t = 0.
𝟎, 𝐎𝐭𝐡𝐞𝐫𝐰𝐢𝐬𝐞
Relationship between Step, Ramp & Delta Signals:-
d
Relation between Unit Step & Unit Ramp Function: - r (t) = u (t) and u t dt = r (t)
dt
d
Relation between Unit Step & Delta Function: - u (t) = δ (t) and δ t dt = u (t)
dt
d2
Relation between Unit Ramp & Delta Function : - r (t) = δ t dt and r (t) = δ (t)
dt 2
SOME EXAMPLES: - Determine the Value of Power and Energy of the following Signals. Find
whether the signals are Power, Energy or neither Power nor Energy Signals.
1 n π
(i) x (n) = u (n). (iii) x (n) = Sin n
3 4
π π
j n+
x (n) = e 2 4
(ii) (iv) x (n) = e2n u (n)
SOLUTION ( i ) n
Given that x (n) = (1/3) u (n).
We know that the Energy of the Signal, E = ∞ 𝐧=−∞ | 𝐱 𝐧 |
𝟐
[Putting the value of x(n)]
2 2 2
∞ 1 n 0 1 n ∞ 1 n
E= n=−∞ u n = n=−∞ u n + n=0 u n (limit divided)
3 3 3
2 2
0 1 n ∞ 1 n 1, n ≥ 0
= n=−∞ 0 + n=0 1 As, Unit Step Function u n =
3 3 0, n < 0
2
∞ 1 n ∞ 1 n 𝟏 𝟗 ∞ n 1
=0+ n=0 = n=0 = 𝟏 = 𝟖 E = 9/8 (Finite) As, n=0 a = 1−a
3 9 𝟏−
𝟗
𝟏 𝐍
Now the Power of the Signal, 𝐏 = 𝐥𝐢𝐦 𝟐𝐍+𝟏 𝐧=−𝐍 | 𝐱 𝐧 |𝟐
𝐍→∞
2 2
1 0 1 n N 1 n
P = limN→∞ 2N+1 n=−N u n + n=0 u n
3 3
2 2
1 0 1 n N 1 n 1, n ≥ 0
= limN→∞ 2N+1 n=−N 0 + n=0 1 As, u n =
3 3 0, n < 0
N +1
1 N 1 n 1 N 1 n 1 1−1 9
= limN→∞ 2N+1 0 + n=0 = limN→∞ 2N+1 n=0 = limN→∞ 2N+1 x
9 9 1−1 9
∞+1
1 1−1 9 1 1 N n 1−a N +1
= 2 x ∞+1 X =∞ =0 P=0 As, =0 As, n=0 a =
1−1 9 ∞ 1−a
Here the Energy is Finite and Power is Zero. Therefore the given signal is an Energy Signal.
𝛑 𝛑
SOLUTION ( ii ) Given that x (n) = 𝐞𝐣 𝟐𝐧+𝟒
We Know that Energy of the Signal, E = ∞ 𝐧=−∞ | 𝐱 𝐧 |
𝟐
[Putting the value of x(n)]
π π 2 πn π 2 π
ej n+ j j
E= ∞
n=−∞ 2 4 = ∞
n=−∞ e 2 xe 4 [As, ejθ = 1. Let ejθ = ej 2 and putting ejθ ]
(1/2) jθ 2 2
E= ∞ n=−∞ e
jθn
x e = ∞ n
n=−∞ 1 x 1
1/2
= ∞ n=−∞ 1
2n
x1
∞ 2n ∞ 2 n ∞ n ∞ n
= n=−∞ 1 = n=−∞ 1 = n=−∞ 1 = ∞ E = ∞ As, n=−∞ 1 = ∞
𝟏 𝐍 𝟐
Now the Power of the Signal, P = 𝐥𝐢𝐦𝐍→∞ 𝟐𝐍+𝟏 𝐧=−𝐍 | 𝐱 𝐧 |
𝛑 𝛑 𝟐
1 1
𝐞𝐣
N 𝐧+ N n
P = limN→∞ 2N+1 n=−N
𝟐 𝟒 = limN→∞ 2N+1 n=−N 1 [Solved Above]
xe (t) = ½ [X (n) + X (-n)] = 1 +3t2 + 9t4 AND xo (t) = ½ [X (n) - X (-n)] = t + 5t3
Find Even & Odd Components of the signal x (t) = Cos t + Sin t + Cos t . Sin t x (-t) = Cos (-t) +
Sin(-t) + Cos(-t) . Sin(-t) = Cos t - Sin t – Cos t . Sin t xe (t) = Cos t & xo (t) = Sin t + Cos t . Sin t
We have already discussed some more problems in 1st Chapter.
Causal and Non-Causal Signals: -
A Signal is said to be Causal if its value
is Zero for n < 0. Otherwise the signal is
Non-Causal. For example X1(n) = an u
(n) & X2 (n) = {𝟏, 2, -3, -1, 2} are
examples of Causal Signals. [u(t), r(t)]
Whereas X3 (n) = an u (- n + 1) and X4 (n) = {-2, 𝟒, 2, -1, 3} are examples of Non-Causal Signals
QNS:-Represent Graphically (i) x1(n) = {1,2, 𝟎 ,-1,1} (ii) x1(n) = {0,0,-1,2, 𝟑} (iii) x1(n)={𝟎,1,-1,1,-1}
Sketch (i) x(n) = 2-n for -2 ≤ n ≤ 2 [≡ {4,2,1, 𝟎 ,0.5,0.25}] (ii) x(n) = 2n2 for -2 ≤ n ≤ 2 [≡ {8,2, 𝟎,2,8}]
x(n) = {2,5,1,𝟐, 2,0,1,7}, Find y1(k) = 3k=−3 x n and y2(k) = 3k=−3 x n . {Answer 13 & 0}
SIMPLE MANIPULATION OF DISCRETE TIME SIGNAL: -
Signal processing is a group of basic operations applied to an input signal resulting in another signal as
the output. The mathematical transformation from one signal to another is represented as y (n)=T[x(n)]
The basic set of operations are
1) Shifting < Delays or Advances > 4) Scalar Multiplication
2) Time Scaling 5) Signal Multiplier
3) Time Reversal < Folding> 6) Signal Addition
SHIFTING
The Shift operation takes the input sequence and shift the values by an integer increment of the
independent variable. The shifting may Delays or Advances the sequence in time.
Mathematically this can be represented as y (n) = x (n – k), Where x (n) is input and y (n) is output.
If k is Positive the Shifting Delays the sequence. If k is Negative the shifting Advances the sequence.
Ex1: x(n) = {2, 1, 𝟐,1, 3, 5}, So, x(n-2) = {𝟐,1, 2, 1, 3, 5} [Delay] & x(n+2) = {2, 1, 2, 1, 𝟑, 5} [Advance]
Ex2: x (n) = {2, 1, 5, 9, 𝟖, 6, 1, 2, 3} x (n+1) = {2, 1, 5, 9, 8, 𝟔, 1, 2, 3}
x (n-4) = {𝟐, 1, 5, 9, 8, 6, 1, 2, 3}, x (n+2) = {2, 1, 5, 9, 8, 6, 𝟏, 2, 3}
Find the Values of the Following questions
∞ n=0 δ n e
2n
= e2n n=0 = 1 ∞ n=−∞ δ n − 2 sin2n = sin2n n=2 = 𝐒𝐢𝐧 𝟒
∞
n=0 δ n + 1 e −2n
=0 ∞ n=−∞ δ n + 1 x(n) = x(n) n=−1 = x (-1)
n=−∞ δ n − 2 Cos 2n + δ n − 1 Sin 2n = Cos 4 + Sin 2
5
SCALING : -
This is accomplished by replacing „n’ by „λn’ in the sequence x (n). Then y (n) = x (λn)
From the above, figure (a) is a discrete time signal x (n). If it is scaled by 2 means that y (n) = x (2n).
It means that what we were getting at x (2n) that will get at y (n). That is y (1) = x (2), y (2) = x (4) etc.
Similarly If it is scaled by ½ means that y (n) = x (½ n). i.e. y (2) = x (1), y (4) = x (2), y (6) = x (3) etc.
The process of reducing sampling rate is often referred as Down Sampling or Decimation.
Whereas the process of increasing sampling rate is referred as Up Sampling.
Example If x(n) = {1, 2, 3, 4, 5, 4, 3, 2, 1} x(2n) = {1, 3, 5, 3, 1} <Down Sampling>
-4 -3 -2 -1 1 2 3 4 -2 -1 1 2
Solution: - We know that u(-15)= 0, u(-8)=0, u(-2)=0, u(0)=1, u(3)=1, u(7)=1, u(12)=1 and so on.
Now from the expression, u(-8) = δ (-∞) + …. + δ (-10) + δ (-9) + δ (-8) = 0+…+0+0+0 = 0
Similarly, u (0) = δ (-∞) + …. + δ (-2) + δ (-1) + δ (0) = 0+…+0+0+1 = 1
u (7) = δ (-∞) + …. + δ (0) + δ (1) +…..+ δ (7) = 0+…+1+0+…..+0 = 1, Hence proved
EX: - A DTS is as shown in fig1. Sketch (i) x(n-3) (ii) x(3-n) (iii) x(2n) (iv) x(n) u(3-n) (v) x[(n-1)2]
EX: - A Continuous Time Signal x (t) is as shown in fig1. Sketch (i) x(t/2)
EX: - A Continuous Time Signal x (t) is as shown in fig2. Sketch (i) x(3t)
1 &2
1, for − 1 ≤ t ≤ 1
EX: - For a Continuous Time Signal defined as x(t) = . Sketch the following
0, Otherwise
(i) x(2t) (ii) x(-2+t) (iii) x(t+1) (iv) x(t+1) u(t) (v) x(t) . δ (t)
Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 603] <DISCRETE TIME SIGNALS & SYSTEMS > [Page 2.10]
EX: - A DTS is given by x (n) = {1, 𝟏, 1, 1, 2} Sketch the following signals: - (i) x(n-2) (ii) x(n+1)
(iii) x (3-n) (iv) x(n).u(n-1) (v) x(n-1) δ (n-1) (vi) Even samples of x(n) (vii) Odd samples of x(n)
EX: - Sketch a DTS x(n) = 2-n for -2 ≤ n ≤ 2 and obtain y1(n) = 2 x(n) + δ (n) & y2(n) = x(n) . u (2-n)
EX: - A Discrete Time Signal is as shown in fig. Sketch (i) x(n-3) (ii) x(3-n) (iii) x(2n) (iv) x(n) u(3-n)
EX: - A CTS is as shown in fig. Sketch (i) x(t-2) (ii) x(1-t) (iii) [x(t) + x(1-t)]. u(t-1)
EX: - A DTS is given by x (n) = {3, 2, 1, 𝟎, 1, 2, 3}.Then Sketch y (n) = [x (n) + x (n-1)] – x (n+1)
EX: - Sketch the Even and Odd parts of the signal x(n) = u(n).
NOTE: -
In time shifting operation equation [y (n) = x (n – k)], if k=1,
we get unit delay element that delays the signal by one sample.
If the input signal is x (n) the output is x (n -1).
In fact the sample x (n-1) is stored in memory at time n-1 & is
recalled from memory at time n to form y (n) = x (n-1)
Thus this basic building block requires memory.
Similarly If k = - 1, we get unit advance element. The diagram Shows unit delay and advance element.
DISCRETE TIME SYSTEM.
A discrete-time system is a device or algorithm that
operates on a discrete-time input signal x (n),
according to some well defined rule, to produce
another discrete-time signal y (n) called output signal.
The relation between input signal x (n) and the output signal y(n) is Representation for the output
signal y (n ) = 0.25 y (n - 1) + 0.5 x (n) + 0.5 x (n - 1) is shown below.
EXPLATION
(A) This system is described by the input-output equations y (n) = Ґ [x (n)] = x (n) – x (n – 1)
Now if the input x(n) is delyed by k units in time and applied to the system, it is clear from the block
diagram that the output will be y (n , k) = x (n – k) – x (n – k – 1)
On the other hand, if we delay y (n) by k units in time, we obtain y (n - k) = x (n – k) – x (n – k – 1)
Since y (n, k) = y (n – k), for all possible values of k, the system is Time Invariant System.
(B) This system is described by the input-output equations y (n) = Ґ [x (n)] = n x (n)
The response of this system to x (n –k) is y (n, k) = n x (n – k) ----- (1)
Now if we delay y (n) by k units in time for the given expression i.e. y (n) = n x (n), we obtain
y (n – k) = (n – k) x (n – k) = [{n x (n – k)} – {k x (n – k)}] ------------ (2)
Since y (n, k) ≠ y (n – k), for all possible values of k, the system is Time Variant System.
(C) This system is described by the input-output equations y (n) = Ґ [x (n)] = x (- n)
The response of this system to x (n –k) is y (n, k) = x (- n - k) ------------- (1)
Now if we delay y (n) by k units in time for the given expression i.e. y (n) = x (- n), we obtain
y (n – k) = x {-(n – k)} = x (- n + k) ------------- (2)
Since y (n, k) ≠ y (n – k), for all possible values of k, the system is Time Variant System
(D) This system is described by the input-output equations y (n) = Ґ [x (n)] = x (n) Cos ω0n
The response of this system to x (n –k) is y (n, k) = x (n - k) Cos ω0n ------------- (1)
Now if we delay y (n) by k units in time for the given expression i.e. y (n) = x (- n), we obtain
y (n – k) = x (n -k) Cos ω0 (n – k) ------------- (2)
Since y (n, k) ≠ y (n – k), for all possible values of k, the system is Time Variant System
Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 603] <DISCRETE TIME SIGNALS & SYSTEMS > [Page 2.13]
EXAMPLES: - *** y(n, k ) = F[x(n-k)] ; y (n-k) = n n-k ***
y(n, k) = sin x(n − k)
1) y(n) = sin x(n) Same → Time Invariant
y(n − k) = sin x(n − k)
y(n, k) = nx(n − k)
2) y(n) = nx(n) Not Equal → Time Variant
y n − k = (n − k)x(n − k)
y(n, k) = x n − k Cos200πn
3) y(n)=x(n) Cos200πn Not Same → Time Variant
y(n − k) = x n − k Cos 200π(n − k)
y n, k = x n − k + x(n − 1 − k)
4) y(n) = x(n) + x(n-1) Same → Time Invariant
y n − k = x n − k + x(n − k − 1)
y n, k = nx 2 n − k
5) y(n) = nx2(n) Not Equal → Time Variant
y n − k = n − k x2 n − k
n
y n, k = x −k
2
6) y(n) = x(n/2) n−k
Not Equal → Time Variant
y n−k = x 2
y(t,k) = sin [x(t+2−k)]
7) y(t) = sin [x(t+2)] y(t−k) = sin [x(t−k+2)] Same Time invarient
y(n,k) = nx (n−k)+4x(n−1−k)–2x(n+1−k)
8) y(n)=nx(n)+4x(n-1)–2x(n+1) Time Varient
y(n−k) = (n−k)x(n−k)+4x(n−k−1)–2x(n−k+1)
y(n,k) = anx (n−k)
9) y(n) = anx(n) y(n−k) = a(n−k)x(n−k) Not Same Time Varient
y(n,k) = ax (n−1−k) + bx (n−2−k)
10) y(n) = ax(n-1) + bx(n-2) y(n−k) = ax (n−k−1) + bx (n−k−2) Same Time Invarient
y(n,k) = n x(n−k) 2
11) y(n) = n x(n) 2
y(n−k) = (n−k) x(n−k) 2 Not Same Time Varient
y(n,k) = a x(n−k) 2 + bx (n−k)
12) y(n) = a x(n) 2 + bx(n) Same Time Invarient
y(n−k) = a x(n−k) 2 + bx (n−k)
y(n,k) = 7x(n−k) + 5n
13) y(n) = 7x(n) + 5n y(n−k) = 7x(n−k) + 5(n−k) Not Same Time Varient
14) y(n) = 3y 2 (n-1) - nx(n) + 4x(n-1) - 2x(n+1)
y(n,k) = 3y 2 (n−1−k) − nx (n−k) + 4x(n−1−k) − 2x(n+1−k)
y(n−k) = 3y 2 (n−k−1) − n−k x(n−k) + 4x(n−k−1) − 2x(n−k+1) Not Same Time Varient
y(n,k) = 12x(n−1−k) + 11x(n−2−k)
15) y(n) = 12x(n-1) + 11x(n-2) y(n−k) = 12x(n−k−1) + 11x(n−k−2) Time Invarient
y n,k = T x n−k =nx n−k
16) y(n) = nx(n) Time Varient
y(n−k) = (n−k) x n−k
y n,k = T x n−k =e x n −k
17) y(n) = ex(n) Time Invarient
y(n−k) = e x n −k
y n,k = T x n−k =x 2n−k
18) y(n) = x(2n) y n−k = x 2 n−k = x 2n−2k Time Varient
19) y(n) = m n
k=0 a k x n − k − k=1 b k y n − k [Here k is there so take a new term m]
y n,m = T x n−m = m n
k =0 a(k)x n−k−m − k =1 b(k)y n−k−m
Time invarient
y(n−m) = m n
k =0 a(k)x n−m−k − k =1 b k y n−m−k {𝑝𝑢𝑡 𝑛→𝑛−𝑚 }
y n,k = T x n−k =x n−k +nx n+1−k
20) y(n) = x(n)+ nx(n+1) Time varient
y n−k = x n−k +(n−k) x n+1−k
CAUSAL AND NON-CAUSAL SYSTEMS.
A system is said to be causal if the output of the system at any time n depends only on prsent and past
inputs, but does not depend on future inputs. This can be represented mathematically as
y (n) = F [x (n), x (n – 1), x (n - 2), …… ]
If systems depend not only on present & past but also future inputs then said to be a non-causal system.
Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 603] <DISCRETE TIME SIGNALS & SYSTEMS > [Page 2.14]
EXAMPLES:- Determine if the system described by the following equations are Causal or Non-causal
𝟏
(i) y(n) = x(n) + 𝒙 (𝒏−𝟏) (ii) y (n) = x (n2)
𝟏
SOLUTION (i) Given that y(n) = x(n) + 𝒙 (𝒏−𝟏)
𝟏 𝟏 𝟏
So, For n = - 1, y (- 1) = x(-1) + 𝒙 (−𝟐) ; For n = 0, y (0) = x(0) + 𝒙 (−𝟏) ; For n = 1, y (1) = x(1) + 𝒙 (𝟎)
For all the values of n the output depends on present and past inputs. Therefore, the system is Causal.
(i) Given y(n) = x (n2); So, For n = - 1, y(-1) = x(1) ; For n = 0, y(0) = x(1); For n = 1, y(1) = x(1),
For negative values of n, the system depends on future inputs. So, the system is Non-Causal.
y (n) = Ax(n)+B ; ax(n)+bx(n-1) ; x(t) cos(t+1) ; x(n) +x(n-1) ; 0.8x(n-1) Causal Systems
y(n) = x(2n) ; x(n)+3x(n+4) ; x(-n) & y(n-2) = x(n) are Non-Causal Systems.
EX: (1) y(t) = x(-t2) Causal (2) y(n) = x(n-1) Causal (3) y(t) = x(t+1) Non-causal
(4) y(n) = x(n) + x(n+1) Non-causal (5) y(t) = 0.2x(t) – x(t-1) Causal
LINEAR AND NON-LINEAR SYSTEMS
A system that satisfies the superposition principle is said
to be a linear system.
Superposition principle states that the response of the
system to a weighted of a signal be equal to the
corresponding weighted sum of the outputs of system to
each of the individual input signals.
A system is said to be Linear if and only if
T [a1 x1(n) + a2 x2(n)] = a1T[x1(n)] + a2T[x2(n)]
for any arbitrary constant a1 & a2
A relaxed system that does not satisfy the Superposition
principle is called Non-Linear System.
EXAMPLES:- Determine if the system described by the following equations are Linear or Non-Linear
𝟏
(i) y (n) = nx(n) (ii) y(n) = x(n2) (iii) y(n) = x(n) + 𝒙 (𝒏−𝟏) (iv) y(n) = x2(n)
SOLUTION
(i) Given that y(n) = n x(n). The outputs due to the signals x1(n) & x2(n) are [Here T=n, Scalar Multiplication]
y1 (n) = T[x1(n)] = n x1(n) …….(1.1) & y2 (n) = T[x2(n)] = n x2(n) ………….(1.2)
The weighted sum of outputs is y3(n) = a1T[x1(n)] + a2T[x2(n)] = a1 nx1(n) + a2 nx2(n) ……… (1.3)
The output due to weighted sum of inputs is, y4(n) = T[a1x1(n) + a2x2(n)] = na1x1(n)+ na2x2(n) …(1.4)
The equation 1.3 and 1.4 are equal. Superposition principle is satisfied. The system is LINEAR
(ii) Given that y(n) = x(n2) The outputs due to the signals x1(n) and x2(n) are [Here T=n2, Time Square]
y1 (n) = T[x1(n)] = x1 (n2) ……… (2.1) & y2 (n) = T[ x2(n) ] = x2(n2) ………(2.2)
The weighted sum of outputs is y3(n) = a1y1(n) + a2y2(n) = a1x1 (n2) + a2x2 (n2) ………(2.3)
The output due to weighted sum of inputs is y4 (n) = T[a1x1(n) + a2x2(n)] = T[a1x1(n)] + T [a2x2(n)]
= a1T [x1(n)] + a2T [x2(n)] = a1x1(n2) + a2x2(n2)] ----(2.4) < As Linear Satisfy Additive and scaling Property >
Equation 2.3 & 2.4 are equal, Superposition principle is satisfied. So, system in Linear.
𝟏
(iii) Given y(n) = x(n) + 𝒙 (𝒏−𝟏) . For two input sequence x1 (n) and x2 (n) the corresponding outputs are
𝟏 𝟏
y1 (n) = T [x1 (n)] = x1(n) + 𝒙 ------- (3.1) & y2 (n) = T [x2 (n)] = x2(n) + 𝒙 --------- (3.2)
𝟏 (𝒏−𝟏) 𝟐 (𝒏−𝟏)
The output due to weighted sum of inputs is y4 (n) = T [a1 x1(n) + a2 x2(n)]
𝟏
Y4 (n) =a1 x1(n) + a2 x2(n) + 𝒂 ------------ (3.3) [Here T= p(n) + 1/p(n-1)]
𝟏 𝒙𝟏 𝒏−𝟏 +𝒂𝟐 𝒙𝟐 (𝒏−𝟏)
On the other hand, the linear combination of the two outputs is
𝒂𝟏 𝒂𝟐
Y3 (n) =a1 y1(n) + a2 y2(n) = a1 x1(n) + 𝒙 (𝒏−𝟏) + a2 x2(n) + 𝒙 -------------------- (3.4)
𝟏 𝟐 (𝒏−𝟏)
Equations 3.3 & 3.4 are not equal, superposition principle is not satisfied, So system is Non-Linear.
(iv) Given y(n) = x2(n). For two input sequence x1 (n) and x2 (n) the corresponding outputs are
y1(n) = T [x1(n)] = x12(n) ---- (4.1) & y2(n) = T [x2(n)] = x22(n) ----- (4.2) [Here T= Square the Signal]
We emphasize that the right-hand side of above equation is the summation of an infinite number of unit
sample sequences where the unit sample sequence δ (n - k) has an amplitude value of x (k).
Thus it gives the resolution of or decomposition of any arbitrary signal x (n) into a weighted (scaled)
sum of shifted unit sample sequences.
EXAMPLES:- Consisder a finite-duration sequence as x (n) = {2, 𝟒, 0, 3}. Resolve the sequences x(n)
into a sum of weighted impulse sequences.
SOLUTION: - Since the sequece x (n) is nonzero for the time instants n = -1, 0, 2, we need three
impulses at delays k = -1, 0, 2. So by follwing the above equation, we find that
x (n) = 2δ (n + 1) + 4δ (n) + 3δ (n - 2) {0. δ (n - 1) = 0 is missing here}
EXAMPLES:- Represent the sequence x (n) = {4, 2, -1, 𝟏, 3, 2, 1, 5} as sum of shifted unit impulse.
Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 603] <DISCRETE TIME SIGNALS & SYSTEMS > [Page 2.18]
SOLUTION: - Since the sequece x (n) is nonzero for the time instants n = -3, -2, -1, 0, 1, 2, 3, 4. So by
follwing the equation we find that x (n) = ∞ 𝒌= − ∞ 𝒙 𝒌 𝜹 (𝒏 − 𝒌)
= x(-3)δ(n+3) + x(-2)δ(n+2) + x(-1)δ(n+1) + x(0)δ(n) + x(1)δ(n-1) + x(2)δ(n-2) + x(3)δ(n-3) + x(4)δ(n-4)
= 4δ (n+3) + 2δ (n+2) – δ (n+1) + δ (n) + 3δ (n-1) + 2δ (n-2) + δ (n-3) + 5δ (n-4)
Response of LTI Systems to Arbitrary Inputs: The CONVOLUTION Sum
A discrete-time system performs an operation on input signal based on predefined criteria to produce a
modified output signal. The input signal x (n) is the system excitation and y (n) is system response.
If the input to the system is a unit impulse i.e. x (n) = δ (n) then the output of the system is known as
impulse response denoted by h (n) where h (n) = T [δ (n)].
We know that any arbitrary sequence x (n) can be represented as a weighted sum of discrete impulses.
Now the system response is given by y(n) = T [x(n)] = T [ ∞ 𝒌= − ∞ 𝒙 𝒌 𝜹 (𝒏 − 𝒌)]
∞
For a linear system it can be reduced to y (n) = 𝒌= − ∞ 𝒙 𝒌 𝑻 [𝜹 (𝒏 − 𝒌)]
The response to the shifted impulse sequence can be denoted by h(n, k) is defined as h(n,k)=T[δ(n-k)]
For a time invariant system h(n, k) = h(n – k)
Substituting this in the above equation, we obtain y (n) = ∞ 𝒌= − ∞ 𝒙 𝒌 𝒉 (𝒏 − 𝒌)
For a linear time-invariant system if the input sequence x (n) and impulse response h(n) is given, we
can find the output y (n) by using the equation y (n) = ∞ 𝒌= − ∞ 𝒙 𝒌 𝒉 (𝒏 − 𝒌) .
Which is known as Convolution Sum and can be represented as y (n) = x (n) * h (n), Where * denotes
the convolution operation. This is an extremely powerful result that allows us to compute the system
output for any input signal excitation.
The convolution sum of two sequences can be found by using following steps.
Step-1 Choose an initial value of n, the starting time for evaluating the output sequence y (n). If x (n)
starts at n = n1 and h (n) starts at n = n2 then n = n1 + n2 is a good choice.
Step-2 Express both sequences in terms of the index k.
Step-3 Fold h (k) about k = 0 to obtain h (- k) and shift by n to the right if n is positive and left if n is
negative to obtain h (n – k).
Step-4 Multiply the two sequences x(k) & h(n-k) elements by element and sum the products to get y(n)
Step-5 Increment the index n, shift the sequence h (n-k) to right by one sample and do Step - 4.
Step-6 Repeat Step – 5 until the sum of products is Zero for all remaining values of n.
PROPERTIES OF CONVOLUTION
(1) Commutative law : - x (n) * h (n) = h (n) * x (n)
(2) Associative Law : - [x (n) * h1(n)] * h2 (n) = x (n) *[ h1(n) * h2 (n)] = [x (n) * h1(n)] * h2 (n)
(3) Distributive Law : - x (n) * [h1(n) + h2 (n)] = [x (n) * h1(n) + x (n) * h2 ]
EXAMPLES:- (A) Find the convolution sum of two sequences
X (n) = n+2 for 0 ≤ n ≤ 3 and h (n) = an u (n) for all n.
We know that y(n) = ∞ 3
k=−∞ x k . h(n − k) = k=0 x k . h(n − k) (As, h(n) = 0 for n < 0)
= 3k=0 k + 2 . an−k u(n − k) = 2an u(n) + 3an-1 u(n-1) + 4an-2 u(n-2) + 5an-3 u(n-3)
(B) Find y(n) if x(n) = h(n) = {𝟏, 2, -1} [Total no. of samples M = 3, N = 3 M+N-1 = 3+3-1 = 5]
[No. of Samples in LHS & RHS are xl = hl = 0 yl = xl + hl = 0+0 = 0 & xr = yr =2 yr = xr + hr = 2+2=4]
Now x(k) ={𝟏, 2, -1}, h(k) ={𝟏, 2, -1} h(-k) ={-1, 2, 𝟏}
h (1-k) ={-1, 𝟐, 1} h (2-k) ={-𝟏, 2, 1}
h (3-k) ={𝟎, -1, 2, 1} h (4-k) ={𝟎, 0, -1, 2, 1}
So, y(n) = {1.1, 2.1+1.2, -1.1+2.2+1.-1, 0.1+-1.2+2.-1+1.0, 0.1+0.2+-1.-1+2.0} = {𝟏, 4, 2, -4, 1}
EXAMPLES:- Find the convolution sum of two sequences x (n) = {𝟑, 2, 1, 2} and h (n)= {1, 𝟐, 1, 2}
SOLUTION: - < METHOD -1 > From the problem x (n) starts at n1 = 0 and h (n) starts at n2 = -1.
Thus the starting value of n = n1 + n2 = 0 + (-1) = -1
For n = -1 , y (-1) = ∞𝒌= − ∞ 𝒙 𝒌 𝒉 (−𝟏 − 𝒌), from Figure , we get y (-1) = 3.1 = 3
Similarly, for n = 0, y (0) = ∞𝒌= − ∞ 𝒙 𝒌 𝒉 (−𝒌) = 3.2 + 2.1 = 8
∞
For n = 1, y (1) = 𝒌= − ∞ 𝒙 𝒌 𝒉 (𝟏 − 𝒌) = 3.1 + 2.2 + 1.1 = 8
Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 603] <DISCRETE TIME SIGNALS & SYSTEMS > [Page 2.19]
For n = 2, y (2) = ∞ 𝒌= − ∞ 𝒙 𝒌 𝒉 (𝟐 − 𝒌)
= 3.2 + 2.1 + 1.2 + 2.1 = 12
For n = 3, y (3) = ∞ 𝒌= − ∞ 𝒙 𝒌 𝒉 (𝟑 − 𝒌)
= 3.0 + 2.2 + 1.1+ 2.2 = 9
For n = 4, y (4) = ∞ 𝒌= − ∞ 𝒙 𝒌 𝒉 (𝟒 − 𝒌)
= 1.2 + 2.1 = 4
For n = 5, y (5) = ∞ 𝒌= − ∞ 𝒙 𝒌 𝒉 (𝟓 − 𝒌)
= 2.2 = 4
For n = 6, y (6) = ∞ 𝒌= − ∞ 𝒙 𝒌 𝒉 (𝟔 − 𝒌)
= 0.0 = 0
Hence y (n) = {3, 𝟖, 8, 12, 9, 4, 4}
To check the correctness of the result, sum
all the samples in x (n) and multiply with
the sum of all the samples in h (n).
This value must be equal to sum of all the
samples in y (n).
In the given problem ∞ 𝒌= − ∞ 𝒙 𝒏 = 8,
∞ ∞
𝒌= − ∞ 𝒉 𝒏 = 6, 𝐤= − ∞ 𝒚 𝒏 = 48.
As ∞ 𝒌= − ∞ 𝒙 𝒏 .
∞
𝒌= − ∞ 𝒉 𝒏 =
∞
𝒌= − ∞ 𝒚 𝒏 is proved. Thus result is correct. [8 x 6 = 48]
SOLUTION: - < METHOD -2 >
From the problem tabulate the sequence
x(n) and shifted version of h (n) as shown
in table below.
Starting value of n = n1 + n2 = 0 + (-1) = -1
The Staring value of n = -1
For n = -1, y (-1) = 3.1 = 3
For n = 0, y (0) = 3.2 + 2.1 = 8
For n = 1, y (1) = 3.1 + 2.2 + 1.1 = 8 ; For
n = 2, y (2) = 3.2 + 2.1 + 1.2 + 2.1 = 12 ;
For n = 3, y (3) = 3.0 + 2.2 + 1.1 + 2.2 = 9 ; For n = 4, y (4) = 1.2 + 2.1 = 4 ;
For n = 5, y (5) = 2.2 = 4; For n = 6, y (6) = 0.0 = 0 ; Hence y (n) = {3, 𝟖, 8, 12, 9, 4, 4}
SOLUTION: - < METHOD -3 > Given that x (n) = {3, 2, 1, 2} and h (n) = {1, 𝟐, 1, 2}
Write down the sequence x (n) and h (n) as shown in figure.
Multiply each and every sample in h (n) with samples of x (n) & tabulate values.
Divide the elements in table by drawing diagonal lines as shown in fig.
Starting from the left sum all the elements in each strip and write down in the
same order. 3, 6 + 2, 3 + 4 + 1, 6 + 2 +2 + 2 , 4 + 1 + 4, 2 + 2, 4
3, 8, 8, 12, 9, 4, 4
The starting value of n = -1, mark symbol ↑ at the time of origin (n = 0).
Hence y (n) = {3, 8, 8, 12, 9, 4, 4}
EXAMPLES:- Find the convolution sum of two signals
𝟏, 𝒏 = −𝟐, 𝟎, 𝟏
h (n) = δ (n) - δ (n - 1) + δ (n - 2) - δ (n - 3) and x (n) = 𝟐, 𝒏 = −𝟏
, 𝑶𝒕𝒉𝒆𝒓𝒘𝒊𝒔𝒆
SOLUTION:-
Given that x (n) = {1, 2, 𝟏, 1} and h (n) = { 𝟏, -1, 1, -1}
The starting value of n = n1 + n2 = - 2 + 0 = - 2
Now applying method - 3, we get
y (n) = {1, - 1 + 2, 1 - 2 + 1, -1 + 2 - 1 + 1, -2 + 1 – 1, -1 + 1, -1}
= {1, 1, 0, 1, -2, 0, -1} Hence y (n) = {1, 1, 𝟎, 1, -2, 0, -1}
From the fig the output of system 1 is y1 (n) = x (n) * h1 (n) = ∞𝑘= − ∞ 𝑥 𝑘 ℎ1 (𝑛 − 𝑘) and
∞ ∞
The output of system 2 is y (n) = y1 (n) * h2 (n) = 𝑘= − ∞ 𝒌= − ∞ 𝒙 𝒌 𝒉𝟏 𝒏 − 𝒌 . ℎ2 (𝑛 − 𝑘) and
By putting the expression for y1 (n), we can find out the expression for y (n) as x(n) * h (n).
Where h (n) = ∞ 𝑘= − ∞ ℎ1 𝑛 ℎ2 (𝑛 − 𝑘) = h1 (n) * h2 (n)
Thus the impulse response of two LTI systems connected cascade is the Convolution Product of the
individual impulse responses.
Example: Obtain convolution sum of two discrete-time signals given:x(n) = 𝐞−𝐧 , h(n) = 3𝐧𝟐 for all n.
𝟐
Solution: - x(k) = e−k , h(n-k) = 3(n − k) 2 y(n) = ∞𝐤=−∞ 𝐱 𝐤 . 𝐡(𝐧 − 𝐤) = ∞k=−∞ e−k . 3(n − k) 2
2 2
∞ −k 2 ∞ −k 2 ∞ 2 −k 2 ∞ −k 2
=3 k=−∞ e n 2 + k 2 − 2nk = 3n 2 k=−∞ e +3 k=−∞ k e - 6n3 k=−∞ ke
Example: - Find convolution sum for x(n) = 𝟐 u(n), h(n) = 𝟏/𝟑 u(n)
𝐧 𝐧
[As y(n) = x(n)*h(n)]
n +1 −1 n +1 −1
∞ k n−k n ∞ k k n ∞ k n 6 n 6
y(n) = k=0 2 1/3 = 1/3 k=0 2 3 = 1/3 k=0 6 = 1/3 6−1
= 1/3 5
Example: - Find convolution sum of the given signals below.
x(n) = u(n-1), h(n) = 3nu(-n-1), ANS: 0.5(3)n for n < 0; 0.5 for n ≥ 0.
5[1− −1/2 n +1
x(n) = u(n), h(n) = 5(1/2)nu(n), ANS: 1+1/2
1− 1/2 n +1 1− 1/2 n +1
= 2[1- (1/2) n+1] = 2n . 2[1 - (1/2) n+1] = 2n+1 [1- (1/2) n+1] [By Formula, = 2−1 ]
1−1/2
2
= 2n+1 - (1/2) n+1. 2n+1 = 2n+1 - (1) n+1 = 2n+1 – 1 (ANS)
∞ ∞ 1 n−k
Q2.x(n)= 2nu(n), h(n)= (1/3)nu(n) y(n) = k=−∞ x k . h(n − k) = k=−∞ 2 ku k . u(n − k)
3
0 1 n−k N 1 n−k N 1 n−k
= k=−∞ 2 k u(k) . u(n − k) + k=0 2 k u(k) . u(n − k) = k=0 2
k
. 3
3 3
N k 1 n 1 −k 1 n N k 1 −k 1 n N k k 1 n N k
= k=0 2 . = k=0 2 . = k=0 2 . 3 = k=0 6
3 3 3 3 3 3
1 n 6 n +1 −1 6 n +1 −1 𝟏 𝐧 𝟔 𝐧+𝟏 −𝟏
= (6 + 61 +62 +…+6n+1 ) = = = (ANS)
3 6−1 5 𝟑 𝟓
∞ ∞ −1 n−k
Q3.x(n) = u(n), h(n) = 5 (-1/2)nu(n) y(n) = k=−∞ x k . h(n − k) = k=0 u n .5 u(n − k)
2
N −1 n −1 −k −1 n N k −1 n 1− −2 n +1
= k=0 5 2 2
= 5 2 k=0 −2 =5 2
− 1−(−2)
−1 n 1− −2 n +1 𝟓 −𝟏 𝐧 𝐧+𝟏
= − =𝟑 𝟏 − −𝟐 (ANS)
2 3 𝟐
Systems with Finite-Duration and Infinite-Duration Impulse Response: -
Up to this point we have characterized a LTI system in terms of its Impulse Response h (n).
It is also subdivided the class of linear time-invariant systems into two types, those that have a Finite-
duration Impulse Response (FIR) and those that have an Infinite-duration Impulse Response (IIR).
Thus an FIR system has an impulse response that is zero outside of some finite time interval.
Without loss of generality, we focus our attention on causal FIR systems, so that h(n)= 0, n<0 & n>M.
The convolution formula for such a system reduces to y (n) = 𝑴−𝟏 𝒌= 𝟎 𝒉 𝒌 𝒙 (𝒏 − 𝒌).
A useful interpretation of this expression is obtained by observing that the output at any time n is
simply a weighted linear combination of the input signal samples x (n), x (n - 1)…… x (n - M + 1).
In other words, the system simply weights, by the values of the impulse response h (k), k = 0, 1… M-1,
the most recent M signal samples and sums the resulting M products.
In effect, the system acts as a window that views only the most recent M input signal samples in
forming the output. It neglects or simply “forgets” all prior input samples [i.e., x(n - M), x (n - M -1),..]
Thus we say that an FIR system has a finite memory of length-M samples.
In contrast, an IIR linear time-invariant system has an infinite-duration impulse response.
Its output, based on the convolution formula, is y (n) = ∞ 𝐤= 𝟎 𝐡 𝐤 𝐱 (𝐧 − 𝐤).
Where causality has been assumed, although this assumption is not necessary.
Now the system output is a weighted [by the impulse response h(k)] linear combination of the input
signal samples x (n), x (n - 1), x (n - 2 )........
Since this weighted sum involves the present and all the past input samples, we say that the system has
an infinite memory. We investigate characteristics of FIR & IIR systems in more detail in later chapter.
Discrete-Time Systems Described By Difference Equations: -
Up to this point we have treated linear and time-invariant systems that are characterized by their unit
sample response h (n). In turn h (n) allow s us to determine the output y (n) of the system for any given
input sequence x (n) by means of the convolution summation. y (n) = ∞ 𝐤= 𝟎 𝐡 𝐤 𝐱 (𝐧 − 𝐤).
In general, then, we have shown that any linear time-invariant system is characterized by the input-
output relationship.
Moreover, the convolution summation formula suggests a means for the realization of the system.
In the case of FIR systems, such a realization involves additions, multiplications, and a finite number
of memory locations. Consequently, an FIR system is readily implemented directly, as implied by the
convolution summation.
EXAMPLE: - Determine the impulse response h(n) for the system described by the second-order
difference equation y (n) = 0.6y(n-1) – 0.08 y(n-2) + x(n)
SOLUTION: Given that : y (n) = 0.6y(n-1) – 0.08 y(n-2) + x(n)
We know the total response y (n) = yh(n) + yp(n) ……………… (i)
For impulse x(n) = δ(n), the particular solution yp(n) = 0 y(n) = yh(n)
Homogeneous solution can be found by substituting x(n) = 0 y(n)-0.6y(n-1)+0.08y(n-2) = 0 ……(ii)
Let the solution yh(n) = λn …………(iii).
Substituting equ(iii) in equ (ii), λn - 0.6 λn-1 + 0.08 λn-2 = 0 λn-2 [λ2 - 0.6 λ + 0.08] = 0
λ2 - 0.6 λ + 0.08. Thus the roots of the characteristic equation are λ1 = 0.4, λ2 = 0.2
The general form of the solution of the homogeneous equation is given by
yh(n) = C1 λ1n + C2n λ2n = C1 (0.4)n + C2(0.2)n ………………(iv)
From equn (iv), y(0) = C1 + C2 & y(1) = 0.4 C1 + 0.2 C2 ……………(v)
From the difference equation we have y(0) = 0.6y(-1) – 0.08 y(-2) + x(0) = 1
y(-1) = y(-2) = 0, x(0)=δ(0)=1 y(1)= 0.6y(0) – 0.08 y(-1) + x(1)=0.6(1) – 0.08(0) + 0 =0.6…(v)
Comparing equation (iv) & (v), C1 + C2 = 1, 0.4 C1 + 0.2 C2 = 0.6 After Solving we get, C1=2, C2=-1
Substituting the values in equation (iv) yields y(n) = 2 (0.4)n u(n) - (0.2)n u(n)
EXAMPLE: - Determine the impulse response h(n) for the system described by difference equation
y(n) + y(n-1) – 2y(n-2) = x(n-1) + 2x(n-2)
SOLUTION: Given that: y(n) + y(n-1) – 2y(n-2) = x(n-1) + 2x(n-2)
The homogeneous solution includes an impulse term. Total response is given by y(n) = yh(n) + yp(n).
For input x(n) = δ(n), the particular solution yp(n) = 0 y(n) = yh(n)
Homogeneous solution can be found by input terms = zero, that is y(n) + y(n-1) – 2y(n-2) = 0...(i)
Let the solution yh(n) = λn. Substituting this solution in equation (i) we obtain the characteristic
equation λn + λn-1 - 2λn-2 = 0 λn-2 [λ2 + λ - 2] = 0 λ2 + λ – 2 = 0
Therefore, the roots are 1, -2 and the general form of the solution to the homogeneous equation is
yh(n) = c1 (1)n + c2n (-2)n + Aδ(n) ………………(ii)
From the difference equation y (0) + y(-1) – 2y(-2) = x(-1) + 2x(-2), y(0) = 0 <for n=0>
y(1) + y(0) – 2y(-1) = x(0) + 2x(-1), y(1) = 1 y(0) = 0, y(1) = 1, y(2) = 1 ………………(iii)
Putting n=0, n=1 & n=2 in equ (ii), we get y(0) = C1 + C2 + A, y(1) = C1 – 2C2, y(2) = C1 – 4C2….(iv)
From which C1 = 1, C2 = 0, A = -1.
Substituting these values in equation (ii) yield y(n) = u(n) - δ(n) = u(n-1)
PRACTICE PROBLEM: - Determine the impulse response h(n) for the system described by the
n
second-order difference equation y(n) - 4y(n-1) + 4y(n-2) = x(n-1) [ANS: 2 (2)n]
PRACTICE PROBLEM: - Determine the impulse response of a discrete-time LTI system whose
difference equation y(n) = y(n-1) + 0.5y(n-2) + x(n) + x(n-1) [ANS: 1.37(1.37)n - 0.37(0.37)n]
PRACTICE PROBLEM: - Determine solution for the system described by the difference equation
y(n) = 5/6 y(n-1) -1/6 y(n-2) + x(n) for x(n) = 2nu(n) [A -(1/2)n u(n) + 2/5 (1/3)n u(n)+8/5 2nu(n)]
-------------- ALL THE BEST -------------------- ALL THE BEST ----------------
Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 603] <Z-TRANSFORM & ITS APPLICATION> [Page 3.1]
[CHAPTER-3]
---------------THE
Z-TRANSFORM & ITS APPLICATION TO LTI SYSTEM------------
INTRODUCTION: -
Transform techniques are an important
tool in the analysis of signals and
Linear Time-Invariant (LTI) systems.
In this chapter we introduce the Z -
Transform, develop its properties, and
demonstrate its importance in the
analysis and characterization of linear
time-invariant systems.
The Z - transform plays the same role
in the analysis of discrete-time signals and LTI systems as the Laplace transform does in the analysis of
continuous-time signals and LTI systems. [ Convolution (CTS) = Multiplication (Z-Transform) ]
For example, we shall see that in the Z - domain (complex Z-plane) the convolution of two time-
domain signals is equivalent to multiplication of their corresponding z-transforms.
This property greatly simplifies the analysis of the response of an LTI system to various signals.
In addition, the Z -Transform provides us with a means of characterizing an LTI system, and its
response to various signals, by its pole-zero locations.
THE DIRECT z-TRANSFORM: -
In this section we introduce the Z-transform of a discrete-time signal, investigate its convergence
properties, and briefly discuss the Inverse Z-transform.
X(z) ≡ ∞𝒏=−∞ 𝒙(𝒏)𝒛
−𝒏
The Z-Transform of a discrete-time signal x(n) is defined as the power series
Where z is a complex variable. In polar form z can expressed as z = rejω. Where r = radius of the circle.
So the above equation becomes X (z) = ∞ 𝒏=−∞ 𝒙(𝒏)(𝐫 𝐞 )
𝐣𝛚 −𝒏
= ∞ 𝒏=−∞{𝒙(𝒏)(𝐫
−𝒏
)}𝐞− 𝐣𝛚𝒏 .
Hence from the above expression, it is clear that if r =1, then the z – transform evaluated on the unit
circle produces the discrete-time Fourier transform of the signal x (n).
The relation is sometimes called the Direct Z - Transform because it transforms the time-domain
signal x (n) in to its complex-plane representation X (z).
The inverse procedure [i.e., obtaining x (n) from X (z)] is called the Inverse Z – Transform.
For convenience, the Z - transform of a signal x (n) is denoted by X (z) ≡ Z{x(n)} ; x(n) = Z-1{ X(z) }
Whereas the relationship between x (n) and X (z) is indicated by x (n) Z X(z)
Region of Convergence (ROC): -
The Region of Convergence (ROC) of X (z) is the set of all values of z in the z-plane for which the
magnitude of X (z) is finite. Thus any time we cite a z - transform we should also indicate its ROC.
Since the z - transform is an infinite power series; it exists only for those values of z for which this
series converges. We illustrate these concepts by some simple examples.
Properties of Region of Convergence (ROC) for Z-Transform: -
1) The ROC is a ring or disk in the z-plane centered at the origin. The ROC cannot contain any pole.
2) If x(n) is a causal sequence then ROC is the entire z-plane except at z = 0;
3) If x (n) is a non-causal sequence then the ROC is the entire z-plane except at z = ∞.
4) If x (n) is a finite duration, two sided sequence the ROC is entire z-plane except at z = 0 and z = ∞.
5) If x (n) is an infinite duration, two sided sequence the ROC will consists of a ring in the z-plane,
bounded on the interior and exterior by a pole, not containing any poles.
6) The ROC of a LTI stable system contains the unit circle. The ROC must be a connected region.
TWO-SIDED Z-TRANSFORM: -
The Z-Transform of a discrete-time signal x(n) may be expressed as
∞ −𝒏
Z {x (n)} = X (z) = 𝒏=−∞ 𝒙(𝒏)𝐳 -------------------- (3. 1)
Where z is a complex variable. This expression is generally known as Two-sided z-Transform
A signal that has finite duration on both the left and right hand sides is known as two sided sequences.
For such type of sequence the ROC is entire z-plane except at z = 0 and z = ∞.
Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 603] <Z-TRANSFORM & ITS APPLICATION> [Page 3.2]
EXAMPLE: -Find the z - transform and ROC of the signal x(n) = { 2, -1, 3, 2, 𝟏, 0, 2, 3, -1}
∞ −𝑛
ANS: - Given x (n) = { 2, -1, 3, 2, 𝟏, 0, 2, 3, -1}, we know that X (z) = 𝑛=−∞ 𝑥(𝑛)z
Thus X(z) = 2z4 – z3 + 3z2 + 2z + 1 + 2z-2 + 3z-3 - 3z-4. X(z) converges for all value except z = 0 & ∞.
ONE-SIDED Z-TRANSFORM < RIGHT HAND SEQUENCE >: -
If discrete time signal x(n) is causal signal i.e. x (n) = 0 for n < 0, then the z-transform is One-Sided z-
Transform (Right Hand Sequence) and is expressed as Z{x(n)}= X (z)= ∞ 𝒏 = 𝟎 𝒙(𝒏)𝐳
−𝒏
----- (3.2)
For such type of sequence the ROC is entire z-plane except at z = 0.
EXAMPLE: -Find the z – transform and ROC of the signal x(n) = { 𝟏, 0, 3, -1, 2}
ANS: - Expanding the equation (3.2), we get X+ (z) = x(0) + x(1) Z-1 + x(2) Z-2 + x(3) Z-3 + ………
Thus x (Z) = 1 + 3z-2 - z-3 + 2z-4. The X+ (z) converges for all value of z except z = 0.
ONE-SIDED Z-TRANSFORM < LEFT HAND SEQUENCE >: -
If a discrete time signal x(n) is non-causal signal i.e. x (n) = 0 for n > 0, then z-transform is also called
as One-sided z-Transform (Left Handed) & is expressed as Z{x(n)}=X(z)= 𝟎𝒏 =−∞ 𝒙(𝒏)𝐳 −𝒏 --- (3.3)
EXAMPLE: -Find the z – transform and ROC of the signal x(n) = { -3, -2, -1, 0, 𝟏 }
ANS: - Expanding the equation (3.3), we get X - (z) = x(0) + x(-1) Z1 + x(-2) Z2 + x(-3) Z3 + ………
Thus x - (Z) = 1 - z2 - 2z3 - 3z4. The X - (z) converges for all value of z except z = ∞.
EXAMPLE: - Determine the z - transforms of the following Finite Duration signals.
1) x1 (n) = {𝟏, 2, 5, 7, 0, 1} 4) x4 (n) = {2, 4, 𝟓, 7, 0, 1} 7) x7 (n) = δ (n + k), k > 0
2) x2 (n) = {1, 2, 𝟓, 7, 0, 1} 5) x5 (n) = δ (n) 8) x8 (n) = {𝟏, 4, 3, 2, 3, 4}
3) x3 (n) = {3, 𝟒, 2, 5, 7, 0,1} 6) x6 (n) = δ (n - k), k > 0 9) x9 (n) = {2, 3, 𝟏, 9, 9}
10) x10 (n) = {2n, for 0 ≤ n ≤ 5 and 0, otherwise} i.e x10 (n) = {𝟎, 2, 4, 6, 8, 10}
SOLUTION: - From definition of Z - Transform, we have
1) X1(z) = 1 + 2z-1 + 5z-2 + 7z-3 + z-5, ROC: Entire z-plane except z = 0
2) X2(z) = z2 + 2z + 5 + 7z-1 + z-3, ROC: Entire z-plane except z = 0 and z = ∞
2 -1 -2 -3 -5
3) X3(z) = 3z + 4 + 2z + 5z + 7z + z ROC: Entire z-plane except z = 0 and z = ∞
4) X4(z) = 2z2 + 4z + 5 + 7z-1 + z-3, ROC: Entire z-plane except z = 0 and z = ∞
5) X5(z) = l [i.e. δ(n) z 1], ROC: Entire z-plane
-k -k
6) X6(z) = z [i.e., δ(n - k) z z ], k > 0, ROC: Entire z-plane except z = 0
7) X7(z) = z k [i.e., δ(n + k) z z k], k > 0, ROC: Entire z-plane except z = ∞
-1 -2 -3 -4 -5
8) X8(z) = 1 + 4z + 3z + 2z + 3z +4z , ROC: Entire z-plane except z = 0
9) X9(z) = 2z2 + 3z + 1 + 9z-1 + 9z-2, ROC: Entire z-plane except z = 0 and z = ∞
-1 -2 -3 -4 -5
10) X10(z) = 2z + 4z + 6z + 8z +10z ROC: Entire z-plane except z = 0
Finite Duration Signals with their ROC Infinite Duration Signals with their ROC
+ ∞𝑛=−∞ a 2 x2 (n)z
−n
= a1 ∞ −n ∞
𝑛=−∞ x1 n z +a 2 𝑛=−∞ x2 (n)z
−n
= a1 x1(z) + a2 x2(z) [Proved]
EXAMPLE: - Find the z-Transform of the signal x (n) = [5(3) - 4(2) ] u(n).
n n
Since the ROC of X(z) is r1 < |z| < r2 r1 < |𝑎−1 z | < r2 ROC of X(𝑎−1 z) is |a| r1 < |z| < |a| r2
TIME SHIFTING:- If x(n) z X(z) then, x(n - m) z z – m X (z)
The ROC of z - m X (z) is the same as that of X (z) except for z = 0 if m > 0 and z = ∞ if m < 0.
PROOF: - We have X(z) = ∞ 𝐧=−∞ 𝐱(𝐧)𝐳
−𝐧
z {x(n-m)} = ∞ n=−∞ x(n − m)z
−n
e jw 0 n
−e −jw 0 n
= 0
𝑛=−∞ Sin w0 n u(n)z
−n
+ ∞ 𝑛=0 Sin w0 n u(n)z
−n
= ∞ 𝑛=0 z −n
2j
−1 ∞ 1
= 2j 𝑛=0 ejw 0 n − e−jw 0 n z −n = 2j ∞ 𝑛=0 e z − ∞
jw 0 n −n
𝑛=0 e
−jw 0 n −n
z
1 ∞ 1 1 1 1 (1−e −jw 0 z −1 )−(1−e jw 0 z −1 )
= 𝑛=0(e z ) − ∞
jw 0 n −1 −n
𝑛 =0(e
−jw 0 n −1 −n
z ) = jw − −jw =
2j 2j 1−e 0 z −1 1−e 0z −1 2j 1−e jw 0 z −1 1−e −jw 0 z −1
1 1−e −jw −1 jw
0 z −1+e 0 z −1 1 jw
(e 0 −e −jw 0 )z −1
= 2j = 2j
1−e −jw 0 z −1 −e jw 0 z −1 +e jw 0 z −1 e −jw 0 z −1 1−z −1 e −jw 0 +e jw 0 + e jw 0 e −jw 0 z −2
1 2j Sin w 0 n z −1 𝐒𝐢𝐧 𝐰𝟎 𝐧 𝐳 −𝟏
= 2j = 𝟏−𝟐𝐂𝐨𝐬 𝐰 ROC: Z > ejw 0 = Z > 1 ; Z > e−jw 0 = Z>1 (ANS)
1−2Cos w 0 z −1 +z −2 𝟎 𝐳 −𝟏 +𝐳 −𝟐
Find its Z – Transform and ROC of 𝐚𝐧 Sin 𝐰𝟎 𝐧 u(n).
Sin w z −1
SOLUTION: - z{Sin w0 n u(n)} = 1−2Cos w 0z −1 +z −2 z{an Sin w0 n u(n)} (Using Scaling Property)
0
Sin w 0 (a −1 z)−1 𝐒𝐢𝐧 𝐰𝟎 𝐚𝐳 −𝟏
= 1−2Cos w −1 −1 −1 −2
= (ANS)
0 (a z) +(a z) 𝟏−𝟐𝐂𝐨𝐬 𝐰𝟎 𝐚𝐳 −𝟏 +𝐚𝟐 𝐳 −𝟐
= z −1 ∞ 𝑛=−∞ x n −n z
−n
(multiplying –z both side)
d 1 𝐝
- z dz z{x(n)} = - z x z ∞𝑛=−∞ x n z
−n
−n = ∞ 𝑛=−∞ n x n z
−n
- z𝐝𝐳 (z) = z{n x(n)} [Proved]
EXAMPLE: - Find the z-transform of the sequence x (n) = 𝐧 𝐚𝐧 𝐮(𝐧).
1
SOLUTION: - We know z an u(n) = 1−az −1 z > a.
d d 1 az −1
By differentiation property, z n x(n) = -zdz X(z) z n an u(n) = -z dz = : z > a
1−az −1 1−az −1 2
az −1 az
Thus, z n an u(n) = = ; ROC: z > a
1−az −1 2 z −a 2
𝟏 𝐧 𝟏 −𝐧
EXAMPLE: - Find the z-transform of the signal x (n) = − 𝟓 u (n) + 5 u (-n-1) also find ROC.
𝟐
1 n 1 −n
SOLUTION:- We have X(z) = ∞
n=−∞ x(n)z
−n
= ∞
n=−∞ −5 u(n) + 5 u(−n − 1) z −n
2
∞ 1 n ∞ 1 n ∞
= n=0 −5 z −n + 5 −1 n −n
n=−∞ 2 z = n=0 −5 z −n + 5 n=1 2−1 z n
1 −1 1
First series converges for − 5 z < 1, i.e. z > 5. Second series converges for z/2 < 1, i.e. z > 2.
1 1 5 1
Therefore, the ROC is 5 < z < 2 . Thus, X(z) = 1+0.2z −1 - 1−2z −1 ROC: 5 < z < 2
𝟏 𝟏
EXAMPLE: - Find the z-transform of the signal x(n) = 𝟐 𝛅(𝐧) + 𝛅(𝐧 − 𝟏) - 𝟑 𝛅(𝐧 − 𝟐) & find ROC.
𝟏 𝟏
SOLUTION: - Referring the table we find X(z) = 𝟐 + 𝐳 −𝟏- 𝟑 𝐳 −𝟐 ; ROC: All values of z except z = 0.
EXAMPLE: - Find the z-transform of the signal x(n) = u(n-2) also find ROC.
z
SOLUTION: - We know z[u(n)] = z−1. Using Time shifting property we have Z[x(n-m)] = z −m X(z).
𝐳 𝐳 −𝟏
Similarly Z[u(n-2)] = 𝐳 −𝟐 𝐳−𝟏 = 𝐳−𝟏 ROC: z > 1
𝟏 𝐧
EX: - Find z-transform of x(n) = 𝐧 + 𝟎. 𝟓 𝐮(𝐧) & ROC
𝟑
1 n
SOLUTION: - Given that x(n) = n + 0.5 u(n)
3
1 n 1 n
= n u(n) + 0.5 u(n)
3 3
𝟏 𝐧 𝟏
From the table we find 𝒁 𝐮(𝐧) = 𝟏 .
𝟑 𝟏− 𝐳 −𝟏
𝟑
𝐝
Using Differential property, Z[nx(n)] = −𝐳 𝐝𝐳 𝐗(𝐳)
1 −1
1 n d 1 z
=𝑍 n u(n) = −z dz 1 = 3
1 −1 2
3 1− z −1 1− z
3 3
1 −1
z 0.5 1
3
X(z) = 1 −1 2
+ 1 ; ROC: z > 3
1− z 1− z −1
3 3
PRACTICE PROBLEM:- Find the z-transform of the following sequence and find ROC in each case.
1 (0.3)4
(i) x(n) = (0.4)n u(n) + (0.3)n u(n-4) ANS: 1−0.4z −1 + 1−0.3z −1 ROC: z > 0.4
−z −2 [1+az −1 ]
(ii) x(n) = n2 an u(n) ANS: ROC: z >a
(1−az −1 )3
EX: - Find inverse z-transform of X(z) = 𝐥𝐨𝐠 𝟏 − 𝟎. 𝟓𝐳 −𝟏
; z > 0.5 using Differential Property.
d 0.5z −2
SOLUTION: - Given X(z) = log 1 − 0.5z −1 . Differentiating on both sides we get dz X(z) = 1−0.5z −1
d −0.5z −1
Multiplying both sides by –z obtain −z dz X(z) = 1−0.5z −1
1 z −1
As 0.5 n u n = and Z 0.5 n−1
u n−1 =
1 − 0.5z −1 1 − 0.5z −1
Upon interchanging the order of the summations and applying the time-shifting property, we obtain,
X(z) = ∞ 𝑘=−∞ 𝑥1 𝑘
∞
𝑛=−∞ 𝑥2 𝑛 − 𝑘 𝑧
−𝑛
= ∞ 𝑘=−∞ 𝑥1 𝑘 . 𝒛
−𝒌
X2(z) [As Z{x(n-k)}=Z-k x(Z)]
= X2(z). ∞ 𝑛=−∞ 𝑥1 𝑘 𝑧
−𝑘
= X2(z). Z{x1(k)} = X2(z). X1(z) Z{x(n) * h(n)} = X(z). H(z)
1, 0 ≤ 𝑛 ≤ 5
EXAMPLE: - Find the convolution sum x(n) of the signals x1(n) = {1, -2, 1} & x2(n)=
0, 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
SOLUTION: - By applying Z-transform to x1(n), we have X1(Z) = 1 - 2z-1 + z-2
Similarly Z{x2(n)}= X2(Z) = 1 + z-1 + z-2 + z-3 + z-4 + z-5
According to convolution property of z-transform, X(Z) = X1(z) . X2(z) = 1- z-1 – z-6 + z-7
Hence x (n) = {1, -1, 0, 0, 0, 0, -1, 1}
The same result can also be obtained by using the convolution sum formula in time domain approach.
CORRELATION OF TWO SEQUENCES:-
If x1(n) z X1(z) & x2(n) z X2(z)
∞
Then 𝑟𝑥 1 𝑥 2 (𝑙) = 𝑛=−∞ 𝑥1 𝑛 𝑥2 (𝑛 − 𝑙) z 𝑅𝑥 1 𝑥 2 (𝑧) = X1(z) X2(z-1)
PROOF: We recall that 𝑟𝑥 1 𝑥 2 (𝑙) = x1(𝑙) * x2(-𝑙). Using the convolution and time-reversal properties,
we easily obtain, 𝑅𝑥 1 𝑥 2 (𝑧) = Z{x1(𝑙)} Z{x2(-𝑙)} = X1(z) X2(z-1)
The ROC of 𝑅𝑥 1 𝑥 2 (𝑧) is at least the intersection of that for X1(z) and X2(z-1).
RATIONAL Z-TRANSFORMS:-
We have discussed an important family of z-
transforms are those for which X(z) is a
rational function, that is, a ratio of two
polynomials in z-1(or z).
In this section we discuss some very
important issues regarding the class of
rational z-transforms.
POLES AND ZEROS:
The Zeros of a z-transform X(z) are the
values of z for which X(z) = 0.
The Poles of a z-transform are the values of
z for which X(z) = ∞.
Since N(z) and D(z) are polynomials in z, they can be expressed in factored form as
𝑴
𝑵(𝒛) 𝒃𝟎 𝒛−𝒛𝟏 𝒛−𝒛𝟐 …(𝒛−𝒛𝑴 ) 𝒌=𝟏 (𝒛−𝒛𝒌)
X (z) = = 𝒛−𝑴+𝑵 X(z) = GzN-M 𝑵 . Where G = b0/a0.
𝑫(𝒛) 𝒂𝟎 𝒛−𝒑𝟏 𝒛−𝒑𝟐 …(𝒛−𝒑𝑴 ) 𝒌=𝟏 (𝒛−𝒑𝒌 )
Thus X(z) has M finite zeros at z = z1, z2,…, zM (the roots of the numerator polynomial), N finite poles
at z = p1, p2,…, pN (the roots of the denominator polynomial), and |N-M| zeros (if N > M ) or poles (if
N < M ) at the origin z = 0. Poles or Zeros may also occur at z = ∞.
A Zero exists at z = ∞ if X(∞) = 0 and a Pole exists at z = ∞ if X(∞) = ∞.
If we count the poles and zeros at zero and infinity, we find that X (z) has
exactly the same number of poles as zeros. We can represent X(z ) graphically
by a pole – zero plot (or pattern) in the complex plane, which shows the
location of Poles by crosses (X) & the location of Zeros by circles (O).
The multiplicity of multiple order poles or zeros is indicated by a number
close to the corresponding cross or circle. Obviously, by definition, the ROC
of a z-transform should not contain any poles.
EXAMPLE: - Determine the pole-zero plot for the signal x(n) = an u(n) a > 0
SOLUTION:- We have X (z) = ∞ 𝑛=−∞ 𝑥(𝑛) 𝑧
−𝑛
= ∞ n
𝑛=−∞ [a u n ] 𝑧
−𝑛
1 𝒛 𝒛
= ∞
𝑛=0 a
n
𝑧 −𝑛 = ∞
𝒏=𝟎 𝐚 𝒛−𝟏 𝐧
=
1− a 𝑧−1
= X(z) = ; ROC: |z| > a
𝒛− 𝐚 𝒛−𝒂
Thus X (z) has one Zero at z1 = 0 & one Pole at p1 = a. Pole-Zero plot is in Fig.
Note that the pole p1 = a is not included in the ROC since the z-transform does not converge at a pole.
EX: - Determine pole-zero plot for the signal x(n) = {an, a ≤ n ≤ M-1 and 0, Otherwise}; Where a>0
(1− a 𝑧−1 )𝑀 𝑍𝑀 − 𝑎𝑀
SOLUTION: - We have X (z) = ∞
𝑛=−∞ 𝑥(𝑛) 𝑧
−𝑛
X (z) = 𝑀−1 −1 𝑛
𝑛=0 (𝑎𝑧 ) = =
1− a 𝑧−1 𝑍 𝑀 −1 (𝑧−𝑎)
Since a>0, the equation ZM = aM has M roots at Zk = aej2πk/M, k = 0, 1, 2, ……… M - 1
The zero z0 = a cancels the pole at z = a.
𝒛−𝒛𝟏 𝒛−𝒛𝟐 …(𝒛−𝒛𝑴−𝟏 )
Thus X(z) = Which has M-1 zeros and M-1
𝑍 𝑀 −1
poles, located as shown in fig.
Note that ROC is the entire z-plane except z= 0 because of the M-1
poles located at the origin.
Pole Location & Time-Domain Behavior of Causal Signals:
Here we consider the relation between the z-plane location of a pole pair
and the form (shape) of the corresponding signal
in time domain.
It is based generally on the collection of z-
transform pairs given in Table & the results in the
preceding subsection.
We deal exclusively with real, causal signals.
In particular, we see that the characteristic
behavior of causal signals depends on whether the
poles of the transform are contained in the region
|z| < 1, or in the region |z| > 1, or on circle |z| = 1.
Since the circle |z| = 1 has a radius of 1, it is called
the unit circle.
If a real signal has a z-transform with one pole,
this pole has to be real.
Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 603] <Z-TRANSFORM & ITS APPLICATION> [Page 3.10]
The only such signal given below is the real exponential having one Zero at z1 = 0 and one Pole at p1 =
𝟏
a on the real axis. x(n) = anu(n) z X(z) = ROC: |z| > |a|
𝟏−𝒂𝒛−𝟏
Fig illustrates the behavior of the signal w.r.t. the location of the pole relative to the unit circle.
The signal is decaying if the pole is inside the unit circle, fixed if the pole is on the unit circle, and
growing if the pole is outside the unit circle.
In addition, a negative pole results in a signal that alternates in sign.
Obviously, causal signals with poles outside the unit circle become unbounded, cause overflow in
digital systems, and in general, should be avoided.
THE SYSTEM FUNCTION OF A LINEAR TIME-INVARIANT SYSTEM:-
We demonstrated that the output of a (relaxed) linear time-invariant system to an input sequence x(n)
can be obtained by computing the convolution of x(n) with the unit sample response of the system .
The convolution property, derived in properties of z- transform section, allows us to express this
relationship in the z-domain as Y(z) = H(z) X(z) ;
Where Y(z) is the z-transform of the output sequence y(n), X(z) is the z-transform of the input
sequence x(n) and H(z) is the z-transform of the unit sample response h(n).
If we know h(n) and x(n), we can determine their corresponding z-transforms H(z) and X(z), multiply
them to obtain Y(z), and therefore determine y(n) by evaluating the inverse z-transform of Y(z).
Alternatively, if we know x(n) and we observe the output y(n) of the system, we can determine the unit
sample response by 1st solving for H(z) from relation & then evaluating inverse z-transform of H(z).
𝒀(𝒛)
H (z) = 𝑿(𝒛) and then evaluating the inverse z-transform of H(z). As H(z) = ∞ 𝒏=−∞ 𝒉(𝒏)𝒛
−𝒏
Suppose that we multiply both sides by zn - 1 and integrate both sides over
a closed contour within the ROC of X (z) which encloses the origin.
Such a contour is illustrated in Fig as above.
Thus we have 𝒄
𝑿 (z)zn-1dz = 𝒄 ∞ 𝒌=−∞ 𝒙(𝒌)𝒛
𝒏−𝟏−𝒌
𝒅𝒛
Where C denotes the Closed Contour in the ROC of X (z), taken in a
counterclockwise direction.
Since the series converges on this contour, we can interchange the order
of integration and summation on the right-hand side of above equation.
Thus it becomes, 𝒄 𝑿 (z)zn-1dz = ∞
𝒌=−∞ 𝒙(𝒌) 𝒄 𝒛
𝒏−𝟏−𝒌
𝒅𝒛
Now we can invoke the Cauchy integral theorem, which states that,
𝟏
𝒛𝒏−𝟏−𝒌 𝒅𝒛 = {1, k = n and 0, k ≠ n}, Where C is any contour that encloses the origin.
𝟐𝝅𝒋 𝒄
By applying this, in the right hand side of above equation, that reduces to 2πjx (n) and hence the
𝟏
desired inversion formula x (n) = 𝑿(𝒛)𝒛𝒏−𝟏 𝒅𝒛.
𝟐𝝅𝒋 𝒄
Although the contour integral provides the desired inversion formula for determining the sequence x(n)
from the z-transform, we shall not use the above directly in our evaluation of inverse z-transforms.
In our treatment we deal with signals and systems in the z-domain which has rational z-transforms (i.e.,
z-transforms that are a ratio of two polynomials). For such z-transforms we develop a simpler method.
INVERSION OF THE Z-TRANSFORM
The inverse z-transform is formally given by x(n) = 𝒄 𝑿 𝒛 𝒛𝒏−𝟏 𝒅𝒛
Where the integral is a contour integral over a closed path C that encloses the origin and lies within the
region of convergence of X (z). For simplicity, C can be a circle in the ROC of X (z) in the z-plane.
There are three methods that are often used for the evaluation of the inverse z-transform in practice:-
(A) Residue method
(B) Convolution method
(C) Direct evaluation by contour integration.
(D) Expansion in to a series of terms in the variables z, and z-1. (Long Division method)
(E) Partial-Fraction Expansion Method and table lookup.
Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 603] <Z-TRANSFORM & ITS APPLICATION> [Page 3.12]
The Inverse z-Transform by PARTIAL-FRACTION EXPANSION Method: -
We attempt to express the function X(z) as linear combination X (z) = α1X1(z) + α2X2(z) +…+ αkXk(z)
Where X1(z),…, Xk (z) are expressions with inverse transforms x1(n),…, xk(n) available in a table of z-
transform pairs. If such a decomposition is possible, then x(n), the inverse z-transform of X(z ), can
easily be found using the linearity property as x(n) = α1x1(n) + α2x2(n) + …+ αkxk(n)
This approach is particularly useful if X(z) is a rational function.
Without loss of generality, we assume that a0 ≠ 1, so that that can be expressed as
𝑵 𝒛 𝒃𝟎 +𝒃𝟏 𝒛−𝟏 +⋯ + 𝒃𝑴 𝒛−𝑴
X(z) = = ------------------- (i)
𝑫 𝒛 𝟏+𝒂𝟏 𝒛−𝟏 +⋯+ 𝒂𝑵 𝒛−𝑵
If a0 ≠ 1, we can obtain above by dividing both numerator & denominator by a0.
A rational function of the form equation (i) is called Proper if aN ≠ 0 and M < N.
An Improper rational function (M ≥ N) can always be written as the sum of a polynomial and a proper
rational function. In general any improper rational function can be expressed as,
N(z) N 1 (z)
X(z) = D(z) = c0 + c1z -1 + …+ cM – N z - (M - N) + D(z) …………… (ii)
In the above equation (ii) the Inverse z-transform of polynomial can be easily found.
We focus our attention on the inversion of proper rational functions, since any improper function can
be transformed into a proper function by using eq. (ii).
Let us consider a rational function of the form of eq. (i).
We eliminate negative power of z by multiplying both numerator and denominator by zN.
𝐛𝟎 𝐳 𝐍 +𝐛𝟏 𝐳 𝐍−𝟏 +⋯+𝐛𝐌 𝐳 𝐍−𝐌
This results in X(z) = ……………(iii) . Dividing equation (iii) by z,
𝐳 𝐍 +𝐚𝟏 𝐳 𝐍−𝟏 +⋯+𝐚𝐍
X(z) b 0 z N −1 +b 1 z N −2 +⋯+b M z N −M −1 b 0 z N −1 +b 1 z N −2 +⋯+b M z N −M −1
We obtain = = ……………(iv)
z z N +a 1 z N −1 +⋯+a N z−p 1 z−p 2 ……(z−p N )
𝐗(𝐳) 𝐂𝟏 𝐂𝟐 𝐂𝐍
For distinct poles equation (iv) is expanded in the form = + + ⋯+ ……(v)
𝐳 𝐳−𝐩𝟏 𝐳−𝐩𝟐 𝐳−𝐩𝐍
𝐳−𝐩𝐤 𝐗(𝐳)
We can find the co-efficient, C1, C2, …CN by using formula Ck = k = 1, 2,…, N …(vi)
𝐳 𝒛 = 𝐩𝐤
If X(z) has a pole of multiplicity l, that is, it contains in denominator the factor (z - pk)l, then expansion
𝐗(𝐳) 𝟏
of the form of equation (v) is no longer valid. Let us assume l = 2 and = ……(vii)
𝐳 𝐳−𝐩𝟐 𝟐 𝐳−𝐩𝟏
𝐗(𝐳) 𝐂𝟏 𝐂𝟐 𝐂𝟑
The above equation (vii) can be expressed in partial fraction form as = + +
𝐳 𝐳−𝐩𝟏 𝐳−𝐩𝟐 𝐳−𝐩𝟐 𝟐
𝐗(𝐳) 𝐝 𝟐 𝐗(𝐳) 𝟐 𝐗(𝐳)
Where C1 = 𝐳 − 𝐩𝟏 ; C2 = 𝐳 − 𝐩𝟐 and C3 = 𝐳 − 𝐩𝟐
𝐳 𝒛 = 𝐩𝟏 𝐝𝐳 𝐳 𝒛 = 𝐩𝟐 𝐳 𝒛 = 𝐩𝟐
𝐗(𝐳) 𝐑(𝐳) 𝐂𝐤 𝟏 𝐂𝟐𝐤 𝐂𝐢𝐤 𝐂𝒍𝐤
In general for a case of l-repeated roots let = = + + ⋯+ + ⋯+
𝐳 𝐳−𝐩𝐤 𝒍 𝐳−𝐩𝐤 𝐳−𝐩𝐤 𝟐 𝐳−𝐩𝐤 𝐢 𝐳−𝐩𝐤 𝒍
X(z) 𝑙
Where i is any term in the partial fraction expansion and R(z) = z − pk
z
𝟏 𝐝𝒍−𝒊 𝒍 𝐗(𝐳)
Thus to find general term Cik is given as 𝐂 𝒊𝒌 = 𝐳 − 𝐩𝐤
(𝒍−𝒊)! 𝐝𝐳 𝒍−𝒊 𝐳 𝐳 = 𝐩𝐤
𝟏+𝟑𝐳 −𝟏
EXAMPLE (1) Find the inverse z-transform of X(z) = 𝟏+𝟑𝐳−𝟏 +𝟐𝐳−𝟐 ; ROC : 𝑧 >2
𝐳(𝐳 𝟐 −𝟒𝐳+𝟓)
(2) Find the inverse z-transform of X(z) = for ROC (i) 2 < 𝑧 < 3 (ii) 𝑧 > 3 (iii) 𝑧 < 1
𝐳−𝟑 𝐳−𝟏 (𝐳−𝟐)
1+3z −1
SOLUTION: - (1) Given X(z) = . First we eliminate the negative power, by multiplying
1+3z −1 +2z −2
2 𝐳 𝟐 +𝟑𝐳 𝐳(𝐳+𝟑) 𝐳(𝐳+𝟑) 𝐳(𝐳+𝟑)
numerator and denominator by z . X(z) = 𝐳𝟐 +𝟑𝐳+𝟐 = 𝐳𝟐 +𝟐𝐳+𝐳+𝟐 = 𝐳 𝐳+𝟐 +𝟏(𝐳+𝟐) = 𝐳+𝟏 (𝐳+𝟐)
𝐗(𝐳) (𝐳+𝟑)
Dividing X(z) by z we obtain = …………(1)
𝐳 𝐳+𝟏 (𝐳+𝟐)
𝐗(𝐳) 𝐂𝟏 𝐂𝟐
The above equation can be written in partial fraction form as = + ……… (2)
𝐳 𝐳+𝟏 𝐳+𝟐
X(z) (z+3) (z+3)
i.e. C1 = z + 1 = z+1 = =2
z 𝑧 = −1 z+1 (z+2) 𝑧 = −1 (z+2) 𝑧 = −1
X(z) (z+3) (z+3)
C2 = z + 2 = z+2 = (z+1) = -1
z 𝑧 = −2 z+1 (z+2) 𝑧 = −2 𝑧 = −2
Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 603] <Z-TRANSFORM & ITS APPLICATION> [Page 3.13]
X(z) 2 1 𝟐𝐳 𝐳 𝑧
Therefore = - X(z) = - [As 𝛼 𝑛 u(n) z X(z) = ]
z z+1 z+2 𝐳+𝟏 𝐳+𝟐 𝑧−𝛼
2z z z z
Thus x(n) = Z-1 {X(z)} = Z-1 − = 2 Z-1 - Z-1 = 2(-1)nu(n) - (-2)nu(n)
z+1 z+2 z+1 z+2
As ROC is 𝑧 >2 the sequence is causal and by inspection we can find x(n) = 2(-1)nu(n) - (-2)nu(n)
z(z 2 −4z+5) 𝐗(𝐳) (𝐳 𝟐 −𝟒𝐳+𝟓)
SOLUTION: - (2) Given X(z) = . Dividing X(z) by z we obtain =
z−3 z−1 (z−2) 𝐳 𝐳−𝟑 𝐳−𝟏 (𝐳−𝟐)
X(z) C1 C2 C3
= + + . The value of C1, C2, C3 can be evaluated using equation
z z−1 z−2 z−3
X(z) (z 2 −4z+5) (z 2 −4z+5) 1−4+5 2
C1 = z − 1 = z−1 = = −2 x −1 = 2 = 1
z z =1 z−3 z−1 (z−2) z = 1 z−3 (z−2) z = 1
X(z) (z 2 −4z+5) (z 2 −4z+5) 4−8+5 1
C2 = z − 2 = z−2 = = = = -1
z 𝑧 =2 z−3 z−1 (z−2) 𝑧 = 2 z−1 (z−3) 𝑧 = 2 1 x −1 −1
X(z) (z 2 −4z+5) (z 2 −4z+5) 9−12+5 2
C3 = z − 3 = z−3 = = =2=1
z z =3 z−3 z−1 (z−2) z = 3 z−1 (z−2) z = 3 2.1
𝐗(𝐳) 𝟏 𝟏 𝟏 𝐳 𝐳 𝐳
Substituting C1, C2, C3, we have = - + . From which X(z) = - +
𝐳 𝐳−𝟏 𝐳−𝟐 𝐳−𝟑 𝐳−𝟏 𝐳−𝟐 𝐳−𝟑
In case (i) when the ROC is 2 < 𝑧 < 3, shown
in figure, the signal x(n) is two sided.
The poles z = 1 & z = 2 provide the causal
part and the pole z = 3 the anticausal part.
Thus, x(n) = u(n) - 2nu(n) + 3nu(-n-1)
In case (ii) when ROC is 𝑧 > 3, shown in fig,
the signal x(n) is causal and all the three terms
in eq. are causal terms. Therefore x(n) = u(n) - 2nu(n) + 3nu(n)
In case (iii) when ROC is 𝑧 < 1, shown in fig, the signal x(n) is anti-causal & all the terms in equation
are anti-causal terms. Therefore x(n) = ±u(-n-1) - 2nu(-n-1) + 3nu(-n-1) x(n) = [-1 + 2n - 3n] u(-n-1)
𝟏
EXAMPLE-3 Determine the causal signal x(n) having the z-transform X(z) = −𝟏 −𝟏 𝟐 𝟏−𝟐𝐳 𝟏−𝐳
1 z3
Answer: -Given X(z) = . Multiply numerator & denominator by z X(z) = 3
1−2z −1 1−z −1 2 z−2 z−1 2
𝐗(𝐳) 𝐳𝟐 𝐂𝟏 𝐂𝟐 𝐂𝟑
Dividing the above result by z we have = = + +
𝐳 𝐳−𝟐 𝐳−𝟏 𝟐 𝐳−𝟐 𝐳−𝟏 𝐳−𝟏 𝟐
X(z) z2
C1 = z − 2 = z−2 =4
z z =2 z−2 z−1 2 z =2
1 d 2 X(z) d 2 z2
C2 = 1! dz z−1 = z − 1
z z =1 dz z−2 z−1 2 z =1
d d
d z2 z−2 z2 − z2 z−2
= = dz dz
[z 2 (1-0) = z 2 ]
dz z−2 z =1 z−2 2
z =1
z−2 2z − z 2 1−2 2− 12 −2− 1
= = = = -3
z−2 2 z =1 1−2 2 1
2 X(z) 2 z2
C3 = z−1 = z−1 = -1
z z =1 z−2 z−1 2 z = 1
𝐗(𝐳) 𝟒 𝟑 𝟏
Substituting C1, C2, C3 values, = - -
𝐳 𝐳−𝟐 𝐳−𝟏 𝐳−𝟏 𝟐
𝟒𝐳 𝟑𝐳 𝐳
X (z) = – – x (n) = 4(2)n u(n) - 3u(n) – nu(n)
𝐳−𝟐 𝐳−𝟏 𝐳−𝟏 𝟐
z 3 +z 2
EXAMPLE - 4 Find the Inverse z-Transform of X(z) = ROC: 𝑧 >3
z−1 z−3
z2 + z
𝐗(𝐳) 𝐳 𝟐 +𝐳 z 2 +z z 2 +z
ANS - 4:-From the expression = = z 2 −3z−z+3 = z 2 −4z+3 z − 4z + 3 z 2 − 4z + 32
1
𝐳 𝐳−𝟏 𝐳−𝟑
(−) (+) (−)
5z - 3
Converting the above improper rational function (as M = N) into sum of a constant and a proper
𝐗(𝐳) 𝟓𝐳−𝟑
rational function, we get =1+
𝐳 𝐳−𝟏 𝐳−𝟑
(A) In the region 𝑧 > 3, all poles are Interior, i.e. the signal x(n) is causal, and therefore,
𝟐 𝟏 𝒏 𝟏
x (n) = δ (n) - u(n) + 𝟑 (3)n u(n).
𝟑 𝟐
(B) In the region 𝑧 < ½ , both the poles are Exterior, i.e. x(n) is anti-causal, and hence,
𝟐 𝟏 𝒏 𝟏
x (n) = δ (n) - u(-n-1) - 𝟑 (3)n u(-n-1).
𝟑 𝟐
1 1
(C) In the region 2
𝑧 < l < 3, [ i.e. 𝑧 < 3 anti causal and 𝑧 > ½ causal], the pole p1 = 2
is interior and
𝟐 𝟏 𝒏 𝟏
p2 = 3 is exterior, and hence x(n) = δ(n) - u(n) - (3)n u(-n-1). {For ROC Fig Ref Page- 3.13}
𝟑 𝟐 𝟑
[CHAPTER-4]
--------- FOURIER TRANSFORM: ITS APPLICATIONS PROPERTIES---------
INTRODUCTION: -
Discrete Fourier Transform (DFT)
computes the values of Z- transform
for evenly spaced points around the
unit circle for given sequence.
If the given sequence to be represented
is of finite duration i.e. it has only a
finite number of non-zero values, then the Transform used is Discrete Fourier Transform (DFT).
DFT finds its application in DSP including linear filtering, correlation analysis and spectrum analysis.
To develop the DFT let us first consider the Continuous Time Fourier Transform (CTFT) of a
∞
continuous signal x(t) which is expressed as X(jω) = − ∞ 𝒙(𝒕) 𝒆−𝒋𝝎𝒕 𝒅𝒕 ------------- (1)
This equation is also called Analysis Equation of CTFT.
𝟏 ∞
Also Inverse CTFT is given by the following synthesis equations 𝒙 𝒕 = 𝟐𝝅 − ∞ 𝑿(𝒋𝝎) 𝒆 𝒋𝝎𝒕 𝒅𝝎 - (2)
The Continuous Time Fourier Transform (CTFT) is used for non periodic Continuous Time Signal.
It produces a continuous spectrum of signal x (t).
∞
Similarly the DTFT of discrete time signal x(n) is expressed as X(𝒆 𝒋𝝎) = − ∞ 𝒙(𝒏) 𝒆−𝒋𝝎𝒏 ---- (3)
This is known as the analysis equation of DTFT of a discrete – time signal or sequence.
𝟏 ∞
Also Inverse DTFT is given by the following synthesis equations 𝒙 𝒏 = 𝟐𝝅 − ∞ 𝑿(𝒆 𝒋𝝎) 𝒆 𝒋𝝎𝒏𝒅𝝎-(4)
This also produces a continuous spectrum of signal x (n).
Now DFT of a discrete – time signal x (n) is obtained by performing the sampling operation in both the
time domain and frequency domain. However, the Discrete Time Fourier Transform (DTFT) of a
discrete-time sequence x (n) is obtained by performing the sampling operation in time domain only.
Now, let x (n) be a finite duration sequence. the N-Point DFT of the sequence x(n) is expressed as
X (k) = 𝐍−𝟏𝒏=𝟎 𝐱 (𝐧) 𝐞
−𝐣𝟐𝛑𝐧𝐤/𝐍
, k = 0, 1, 2, 3, 4 … N-1 ------ (5)
Also the corresponding Inverse Discrete Fourier Transform (IDFT) is expressed as
𝟏 𝐍−𝟏
x (n) = 𝐗(𝐤)𝐞 𝐣𝟐𝛑𝐧𝐤/𝐍 , n = 0, 1, 2, 3, 4 … N-1 ------ (6)
𝑵 𝒌=𝟎
−𝐣𝟐𝛑/𝐍
Now let us define WN = 𝐞 , which is called Twiddle Factor.
So the above equations for DFT and IDFT can be written as
𝐤𝐧 𝟏
X (k) = 𝐍−𝟏
𝒏=𝟎 𝐱(𝐧) 𝐖𝐍 , k = 0, 1,… N-1 – (7) & x (n) = 𝐍−𝟏
𝐗(𝐤)𝐖𝐍 − 𝐤𝐧 , n = 0, 1, … N-1 - (8)
𝑵 𝒌=𝟎
Here both the indices n and k are ranging from 0 to N-1. The integer n is known as time index since it
denotes the time instant. The integer k denotes discrete frequency and is called frequency Index.
EXAMPLE - 1: - Find the 4-point DFT of a sequence x(n) = {𝟏, 1, 0, 0}.
SOLUTION: Let us assume N = L = 4
We have X(k) = 𝐍−𝟏 𝒏=𝟎 𝐱(𝐧) 𝐞
− 𝐣𝟐𝛑𝐧𝐤/𝐍
, k = 0, 1,… N-1 X(k) = 𝟑𝒏=𝟎 𝐱(𝐧) 𝐞− 𝐣𝟐𝛑𝐧𝐤/𝐍
3 e jθ − e −jθ e jθ + e −jθ
X(0) = 𝑛=0 x(n) = x(0) + x(1) + x(2) + x(3) = 1+1+0+0 =2 𝐀𝐬 Sin θ = 2j
& Cos θ = 2
3 − jπn/2 𝜋 𝜋
X(1) = 𝑛=0 x(n) e = x(0) + x(1) e-jπ/2 + x(2) e-jπ + x(3) e-j3π/2 = 1 + cos 2 - 𝑗 sin 2 +0+0= 1 – j
3 − jπn
X(2) = 𝑛=0 x(n) e = x(0) + x(1) e-jπ + x(2) e-j2π + x(3) e-j3π = 1 + cos 𝜋 - 𝑗 sin 𝜋 = 1 - 1 = 0
3 − j3πn/2 3𝜋 3𝜋
X(3) = 𝑛=0 x(n) e = x(0) + x(1) e-j3π/2 + x(2) e-j3π + x(3) e-j9π/2 = 1 + cos 2 - 𝑗 sin 2 = 1 + j
X(k) = {2, 1 - j, 0, 1 + j}
𝟏
EXAMPLE - 2: - Compute the DFT of the sequence: 𝐱 𝐧 = {𝟒 , 𝐟𝐨𝐫 𝟎 ≤ 𝐧 ≤ 𝟐 ; and 𝟎, 𝐎𝐭𝐡𝐞𝐫𝐰𝐢𝐬𝐞}
SOLUTION: -From the above expression, the sequence is given by, x(n) = { ¼ , ¼ , ¼ }
We know that the N-point DFT of the sequence x(n) is expressed as
X(k) = 𝐍−𝟏
𝒏=𝟎 𝐱(𝐧) 𝐞
− 𝐣𝟐𝛑𝐧𝐤/𝐍
, k = 0, 1,… N-1 [AS 𝐞𝐣𝛉 = 𝑪𝒐𝒔𝜽 + 𝒋𝑺𝒊𝒏 𝜽 & 𝐞−𝐣𝛉 = 𝑪𝒐𝒔𝜽 − 𝒋𝑺𝒊𝒏 𝜽]
<DIGITAL SIGNAL PROCESSING> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DSP [ETT 603] <FOURIER TRANSFORM: ITS APPLICATIONS PROPERTIES > [Page 4.2]
1 1 − jω 1
Therefore, X(k) = 4 [1 + e− jω + e− 2jω ] = e + 1 + e− jω ]
[
𝜔=2πk/N 4 e jω
−
𝜔 =2πk/N
1 − jω jω − jω 1 − jω jω − jω 1
= 4e [e + 1 + e ] = 4e [1 + e + e ] = X(k) = 4 e− jω [1+2cos 𝜔]
𝜔 =2πk/N 𝜔=2πk/N
1 − j2πk/3 2𝜋𝑘
Where 𝝎 = 𝟐𝛑𝐤/𝐍 and N = 3 Therefore, X(k) = 4 e 1 + 2 cos 3
𝟏 − 𝐣𝟐𝛑𝐤/𝟑 𝟐𝝅𝒌
X(k) = 𝟒 𝐞 𝟏 + 𝟐 𝐜𝐨𝐬 , Where k = 0, 1,… N-1
𝟑
𝟏
EXAMPLE - 3:- Compute DFT of the sequence: 𝐱 𝐧 = {𝟓 , 𝐟𝐨𝐫 − 𝟏 ≤ 𝐧 ≤ 𝟏 ; and 𝟎, 𝐎𝐭𝐡𝐞𝐫𝐰𝐢𝐬𝐞}
SOLUTION: - From the above expression
1 𝟏 1
the sequence is given by, x(n) = , ,
5 𝟓 5
N-point DFT of the Signal x(n) is expressed
as X(k) = ∞ 𝒏=−∞ 𝐱(𝐧) 𝐞
− 𝐣𝛚𝐧
, 𝜔 = 2πk/N
1 jω −jω
Thus, X(k) = [e + 1 + e ]
5 at ω=2πk/N
1 𝟏 𝟐𝝅𝒌
= 5 [1+2cos ω] = 𝟏 + 𝟐 𝐜𝐨𝐬 ;
𝟓 𝟑
2πk
Where k = 0, 1, … N-1, 𝜔 = and N = 3
N
EXAMPLE - 4: -
Derive the DFT of the sample data sequence
x(n) = {1, 1, 2, 2, 3, 3}.
SOLUTION:
We know N-point DFT of the Signal x(n) is
X(k) = 𝐍−𝟏𝒏=𝟎 𝐱(𝐧) 𝐞
− 𝐣𝟐𝛑𝐧𝐤/𝐍
, k = 0,1,…N-1
5
For k = 0 X(0) = 𝑛 =0 x(n)e− j2π(0)n/6
= 5𝑛=0 x(n) = 1 + 1 + 2 + 2 + 3 + 3 = 12
Similarly, X(1) = 5𝑛=0 x(n)e− j2π(1)n/6
= 5𝑛=0 x(n) e-jπn/3 = 1 + e-jπ/3 + 2e-j2π/3 +2e-jπ
+ 3e-j4π/3 + 3e-j5π/3
= 1 + (0.5 - j0.866) + 2(-0.5- j0.866) + 2(-1) +
3(-0.5- j0.866) + 3(0.5- j0.866) = -1.5 + j2.598
X(2) = 5𝑛=0 x(n)e− j2π(2)n/6 = 5𝑛=0 x(n) e-2jπn/3 = 1 + e-j2π/3 + 2e-j4π/3 + 2e-j2π + 3e-j8π/3 + 3e-j10π/3
= 1 + (-0.5-j0.866) + 2(-0.5+ j0.866) + 2(1) + 3(-0.5- j0.866) + 3(-0.5+ j0.866) = -1.5 + j0.866
X(3) = 5𝑛=0 x(n)e− j2π(3)n/6 = 5𝑛=0 x(n) e-jπn = 1 + e-jπ + 2e-j2π + 2e-j3π + 3e-j4π + 3e-j5π
= 1 – 1 + 2(1) + 2(-1) + 3(1) + 3(-1) = 0
X(4) = 𝑛=0 x(n)e− j2π(4)n/6 = 5𝑛=0 x(n) e-j4πn/3 = 1 + e-j4π/3 + 2e-j8π/3 + 2e-j4π + 3e-j14π/3 + 3e-j20π/3
5
<DIGITAL SIGNAL PROCESSING> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DSP [ETT 603] <FOURIER TRANSFORM: ITS APPLICATIONS PROPERTIES > [Page 4.3]
𝒏𝝅
EXAMPLE - 5: - Compute the 4 - point DFT of the sequence x(n) = 𝐜𝐨𝐬 𝟒
𝜋 𝜋 3𝜋
SOLUTION: Given that, N = 4 So x(n) = cos 0 , cos , cos , cos = [1, 0.707, 0, -0.707]
2 4
4
We know that the N-point DFT of x(n) is expressed as X(k) = 𝐍−𝟏 𝒏=𝟎 𝐱(𝐧) 𝐞 − 𝐣𝟐𝛑𝐧𝐤/𝐍
, k = 0, 1,… N-1
3 − j2πnk /4 3 − jπnk /2
The DFT is X(k) = 𝑛=0 x(n) e , k = 0, 1, 2, 3 X(k) = 𝑛=0 x(n) e , k = 0, 1, 2, 3
3 3
For k = 0, we have, X(0) = 𝑛=0 x(n) = 1; For k = 1, we have, X(1) = 𝑛=0 x(n) e− jπ(1)n/2
X(1) = 1 + 0.707e-π/2 + 0+ (-0.707)e-j3π/2 = 1 + (0.707) (-j) + 0 - (0.707) (j) = 1 - j1.414
For k = 2, we have, X(2) = ∞𝑛=−∞ x(n) e
− jπ(2)n/2
= ∞𝑛=−∞ x(n) e
− jπn
-jπ -j3π
X(2) = 1 + 0.707e + 0 + (-0.707)e = 1 + 0.707(-1) + 0 + (-0.707)(-1) = 1
For k = 3, we have, X(3) = 3𝑛=0 x(n) e− jπ(3)n/2 = 1 + 0.707e-3π/2 + 0 + (-0.707)e-j9π/2
Or X(3) = 1 + 0.707(j) + 0 + (-0.707)(-j) = 1 + j1.414 X(k) = [1, 1-j1.414, 1, 1 + j1.414]
INVERSE DISCRETE FOURIER TRANSFORM (IDFT): -
𝟏
The IDFT for a sequence is expressed as x(n) = 𝑵 𝐍−𝟏 𝒌=𝟎 𝐗(𝐤) 𝐞
𝐣𝟐𝛑𝐧𝐤/𝐍
, n = 0, 1, 2, 3, 4 … N-1
EXAMPLE - 6: - Find the IDFT of a sequence Y(k) = {1, 0, 1, 0}.
𝟏
SOLUTION: We know that the N-point IDFT of x(n) is y(n) = 𝑵 𝐍−𝟏 𝒌=𝟎 𝐘(𝐤) 𝐞
𝐣𝟐𝛑𝐧𝐤/𝐍
, n = 0, 1,… N-1
1 3 1 1
For n= 0 y(0) = 4 𝑘=0 Y(k)= 4 [y(0) + y(1) + y(2) + y(3)] = 4 [1 + 0 + 1 + 0] = 0.5
1
Similarly for n = 1, y(1) = 𝑁 3𝑘=0 Y(k) ejπk/2
1 1 1
y(1) = 4 [Y(0) + Y(1)ejπ/2 + Y(2)ejπ + Y(3)ej3π/2] = 4 [1 + 0 + cos 𝜋 + 𝑗 sin 𝜋 + 0] = 4 [1 + 0 – 1 + 0] = 0
1 3 jπk 1
For n = 2; y(2) = 4 𝑘=0 Y(k) e = 4 [Y(0) + Y(1) ejπ + Y(2) ej2π + Y(3) ej3π]
1 1
= 4 [1 + 0 + cos 2𝜋 + 𝑗 sin 2𝜋 + 0] = 4 [1 + 0 + 1 + 0] = 0.5
1 3 j6πk/4 1
For n = 3; y(3) = 4 𝑘=0 Y(k) e = 4 [Y(0) + Y(1)ej3π/2 + Y(2)ej3π + Y(3)ej9π/2]
1 1
= [1 + 0 + cos 3𝜋 + 𝑗 sin 3𝜋 + 0] = [1 + 0 – 1 + 0] = 0 Thus y(n) = {0.5, 0, 0.5, 0}
4 4
EXAMPLE - 7: - Compute the inverse DFT of a sequence X(k) = {1,2,3,4}.
𝟏
SOLUTION: We know that the DFT is expressed as, x(n) = 𝑵 𝐍−𝟏
𝒌=𝟎 𝐗(𝐤) 𝐞
𝐣𝟐𝛑𝐧𝐤/𝐍
, n = 0, 1,… N-1
𝟏𝟑 𝐣𝟐𝛑𝐧𝐤/𝐍
Given that N = 4, Therefore, x(n) = 𝟒 𝒌=𝟎 𝐗(𝐤) 𝐞 , n = 0, 1, 2, 3
1 3 jπ(0)k/2 1
When n = 0, we have x(0) = 4 𝑘=0 X(k)e = 4 [1 + 2 + 3 + 4] = 5/2
1 3 jπ(1)k/2 1
When n = 1, we have x(1) = 4 𝑘=0 X(k)e = 4 [1 + 2ejπ/2 + 3ejπ + 4ej3π/2]
1 1 𝟏 𝟏
= 4 [1 + 2(j) + 3(-1) + 4(-j)] = 4(-2 - j2) = - 𝟐 - j𝟐
1 3 jπ(2)k/2 1
When n = 2, we have x(2) = 4 𝑘=0 X(k)e = 4 [1 + 2ejπ + 3ej2π + 4ej3π]
1 1 𝟏
= 4 [1 + 2(-1) + 3(1) + 4(-1)] = 4 (-2) = - 𝟐
1 3 jπ(3)k/2 1
When n = 3, we have x(3) = 4 𝑘=0 X(k)e = 4 [1 + 2ej3π/2 + 3ej3π + 4ej9π/2]
1 1 𝟏 𝟏 𝟓 𝟏 𝟏 𝟏 𝟏 𝟏
= 4 [1 + 2(-j) + 3(-1) + 4(j)] = 4(-2 + j2) = - 𝟐 + j𝟐 x(n) = ,− − 𝐣𝟐,− 𝟐,− + 𝐣𝟐
𝟐 𝟐 𝟐
EXAMPLE - 8:- Find the IDFT of a sequence X(k) = {3, (2+j), 1, (2-j)}.
𝟏
SOLUTION: The IDFT is expressed as x(n) = 𝑵 𝐍−𝟏
𝒌=𝟎 𝐗(𝐤) 𝐞
𝐣𝟐𝛑𝐧𝐤/𝐍
, 0 ≤ n ≤ N-1
𝟏 𝟑 𝐣𝛑𝐧𝐤/𝟐
Here, given that N = 4, Therefore, x(n) = 𝟒 𝒌=𝟎 𝐗(𝐤) 𝐞 , 0≤n≤ 3
1 3 0 1
When n = 0, we have x(0) = 4 𝑘=0 X(k)e = 4[3 + (2+j) + 1 + (2-j)] = 2
1 3 jπk/2 1
When n = 1, we have x(1) = 4 𝑘=0 X(k)e =4 [3 + (2+j)ejπ/2 + ejπ + (2-j)ej3π/2]
1
= 4 [3 + (2+j)(j) + 1(-1) + (2-j)(-j)] = 0
1 3 jπk 1
When n = 2, we have x(2) = 𝑘=0 X(k)e = [3 + (2+j)ejπ + ej2π + (2-j)ej3π]
4 4
1
= 4 [3 + (2+j) (-1) + (1) + (2-j) (-1)] = 0
<DIGITAL SIGNAL PROCESSING> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DSP [ETT 603] <FOURIER TRANSFORM: ITS APPLICATIONS PROPERTIES > [Page 4.4]
1 3 jπ3k/2 1
When n = 3, we have x(3) = 4 𝑘=0 X(k)e = 4 [3 + (2+j)ej3π/2 + ej3π + (2-j)ej9π/2]
1
= 4 [3 + (2+j) (-j) + (-1) + (2-j) (j)] = 1 Hence x(n) = [2, 0, 0, 1]
EXAMPLE - 9: -
1, for 0 ≤ n ≤ 2
Find DFT of the sequence x n = for [1] N = 4 & [2] N = 8; Plot 𝑋(𝑘) & ∠X(k).
0, otherwise
SOLUTION: - From the above expression x(n) = {1, 1, 1, 0}
Given L = 3, so for N = 4, the periodic extension of x(n) can be obtained by adding one zero [Zero Padding]
Thus x(0) = 1; x(1) = 1; x(2) = 1; x(3) = 0 ; But We have X(k) = 𝐍−𝟏 𝒏=𝟎 𝐱(𝐧) 𝐞
− 𝐣𝟐𝛑𝐧𝐤/𝐍
, k = 0, 1,… N-1
FOR N = 4 𝟑
X(k) = 𝒏=𝟎 𝐱(𝐧) 𝐞 − 𝐣𝛑𝐧𝐤/𝟐
, k = 0, 1, 2, 3
3
For k = 0, X(0) = 𝑛=0 x(n) = x(0) + x(1) + x(2) + x(3) = 1+1+1+0 = 3 Thus, 𝑿(𝟎) = 3, ∠X(0) = 0
For k = 1, X(1) = 3𝑛=0 x(n) e− jπn/2 = x(0) + x(1)e-jπ/2 + x(2) e-jπ + x(3) e-j3π/2
𝜋 𝜋 𝝅
= 1 + cos 2 - 𝑗 sin 2 + cos 𝜋 - 𝑗 sin 𝜋 + 0= 1 – j – 1 = - j ; Therefore, 𝑿(𝟏) = 1, ∠X(1) = − 𝟐
For k = 2, X(2) = 3𝑛=0 x(n) e− jπn = x(0) + x(1)e-jπ + x(2) e-j2π + x(3) e-j3π
= 1 + cos 𝜋 - 𝑗 sin 𝜋 + cos 2𝜋 - 𝑗 sin 2𝜋 + 0= 1 – 1 +1= 1; Therefore, 𝑿(𝟐) = 1, ∠X(2) = 0
For k = 3, X(3) = 3𝑛=0 x(n) e− j3πn/2 = x(0) + x(1)e-j3π/2 + x(2) e-j3π + x(3) e-j9π/2
3𝜋 3𝜋 𝝅
= 1 + cos 2 - 𝑗 sin 2 + cos 3𝜋 - 𝑗 sin 3𝜋 + 0= 1 + j-1 = j Therefore, 𝑿(𝟑) = 1, ∠X(3) = 𝟐
𝝅 𝝅
Thus 𝑿 𝒌 = {3, -j, 1, j} 𝑿(𝒌) = {3, 1, 1, 1} and ∠X(k) = 𝟎, − , 𝟎, ; 𝑿(𝒌) = 𝒂𝟐 + 𝒃𝟐
𝟐 𝟐
FOR N = 8, x(n)={1,1,1,1,1,1,0,0}
Given L = 3, thus the periodic
extension of x(n) can be obtained
by adding Five zero.
Thus, we have x(0) = x(1) = x(2) =
1; x(n) = 0 for 3 ≤ n ≤ 7
We know that X(k) = N−1 𝑛=0 x(n) e
− j2πnk /N
For N = 8, X(k) = 𝟕𝒏=𝟎 𝐱(𝐧) 𝐞− 𝐣𝛑𝐧𝐤/𝟒 , k = 0, 1, 2,…,7
For k = 0, X(0) = 7𝑛=0 x(n) = 1 + 1 + 1 + 0 + 0 + 0 + 0 + 0 = 3 ; Therefore, 𝑿(𝟎) = 3, ∠X(0) = 0
For k = 1, X(1) = 7𝑛=0 x(n) e− jπn/4 = x(0) + x(1)e-jπ/4 + x(2) e-jπ/2
𝝅
= 1 + 0.707 – j0.707 + 0 – j = 1.707 – j1.707 ; Therefore, 𝑿(𝟏) = 2.414, ∠X(1) = − 𝟒
For k = 2, X(2) = 7𝑛=0 x(n) e− jπn/2 = x(0) + x(1)e-jπ/2 + x(2) e-jπ
𝜋 𝜋 𝝅
= 1 + cos 2 - 𝑗 sin 2 + cos 𝜋 - 𝑗 sin 𝜋 = 1 – j -1= -j ; Therefore, 𝑿(𝟐) = 1, ∠X(2) = − 𝟐
For k = 3, X(3) = 7𝑛=0 x(n) e− j3πn/4 = x(0) + x(1)e-j3π/4 + x(2) e-j3π/2
3𝜋 3𝜋 3𝜋 3𝜋
= 1 + cos 4 - 𝑗 sin 4 + cos 2 - 𝑗 sin 2
𝝅
= 1 – 0.707 – j0.707 + j = 0.293 + j0.293; Therefore, 𝑿(𝟑) = 0.414, ∠X(3) = 𝟒
For k = 4, X(4) = 7𝑛=0 x(n) e− jπn = x(0) + x(1)e-jπ + x(2) e-j2π
= 1 + cos 𝜋 - 𝑗 sin 𝜋 + cos 2𝜋 - 𝑗 sin 2𝜋 = 1 – 1 + 1 = 1; Therefore, 𝑿(𝟒) = 1, ∠X(1) = 0
For k = 5, X(5) = 7𝑛=0 x(n) e− j5πn/4 = x(0) + x(1)e-j5π/4 + x(2) e-j5π/2
5𝜋 5𝜋 5𝜋 5𝜋
= 1 + cos 4 - 𝑗 sin 4 + cos 2 - 𝑗 sin 2 = 1 – 0.707 + j0.707 – j
𝝅
= 0.293 – j0.293 ; Therefore, 𝑿(𝟓) = 0.414, ∠X(5) = − 𝟒
For k = 6, X(6) = 7𝑛=0 x(n) e− j3πn/2 = x(0) + x(1)e-j3π/2 + x(2) e-j3π/2
3𝜋 3𝜋 𝝅
= 1 + cos 2 - 𝑗 sin 2 + cos 3𝜋 - 𝑗 sin 3𝜋 = 1 + j – 1 = j; Thus, 𝑿(𝟔) = 1, ∠X(6) = − 𝟐
<DIGITAL SIGNAL PROCESSING> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DSP [ETT 603] <FOURIER TRANSFORM: ITS APPLICATIONS PROPERTIES > [Page 4.5]
7 − j7πn/4 -j7π/4 -j7π/2
For k = 7, X(7) = 𝑛=0 x(n) e = x(0) + x(1)e + x(2) e
7𝜋 7𝜋 7𝜋 7𝜋
= 1 + cos - 𝑗 sin + cos - 𝑗 sin = 1 + 0.707 + j0.707 + j
4 4 2 2
𝝅
= 1.707 + j1.707 ; Therefore, 𝑿(𝟕) = 2.414, ∠X(7) = 𝟒
𝝅 𝝅 𝝅 𝝅 𝝅 𝝅
Thus 𝑿(𝒌) = {3, 2.414, 1, 0.414, 1, 0.414, 1, 2.414} and ∠X(k) = 𝟎, − , − , , 𝟎 , − , − ,
𝟒 𝟐 𝟒 𝟒 𝟐 𝟒
The plot of 𝑋(𝑘) and ∠X(k) for N = 4 & 8 is shown in figure.
NOTE: - From figure we can observe that it is difficult to extrapolate the entire frequency spectrum,
with N = 4. That is the resolution of the spectrum is very poor. In order to increase the resolution, we
must increase N. in figure it is possible to extrapolate the frequency spectrum, where the value of N =8.
Thus we concluded that the Zero Padding gives a high density spectrum and provides a better display
version for plotting.
EXAMPLE - 10: Determine the 8-point DFT of the sequence x(n) = {1, 1, 1, 1, 1, 1, 0, 0}
SOLUTION: We know X(k) = 𝐍−𝟏 𝒏=𝟎 𝐱(𝐧) 𝐞
− 𝐣𝟐𝛑𝐧𝐤/𝐍
, k = 0, 1,… N-1
𝟕 − 𝐣𝛑𝐧𝐤/𝟒
For given N = 8; X(k) = 𝒏=𝟎 𝐱(𝐧) 𝐞 , k = 0, 1, 2,…,7
For k = 0; X(0) = 7𝑛=0 x(n) = x(0) + x(1) + x(2) + x(3) + x(4) + x(5) + x(6) + x(7)
=1+1+1+1+1+1+0+0=6
For k = 1; X(1) = 7𝑛=0 x(n) e− jπn/4
= x(0) + x(1)e-jπ/4 + x(2) e-jπ/2 + x(3)e-j3π/4 + x(4) e-jπ+ x(5)e-j5π/4 + x(6) e-j3π/2 + x(7)e-j7π/4
= 1 + 0.707 – j0.707 – j - 0.707 – j0.707 – 1 - 0.707 + j0.707 = -0.707 – j1.707
For k = 2; X(2) = 7𝑛=0 x(n) e− jπn/2
= x(0) + x(1)e-jπ/2 + x(2) e-jπ + x(3)e-j3π/2 + x(4) e-j2π+ x(5)e-j5π/2 + x(6) e-j3π + x(7)e-j7π/2
=1–j–1+j+1–j=1-j
For k = 3 ; X(3) = 7n=0 x(n) e− j3πn/4
= x(0)+x(1)e-j3π/4+x(2) e-j3π/2+x(3)e-j9π/4+x(4) e-j3π+x(5)e-j15π/4+x(6) e-j9π/2+x(7)e-j21π/4
= 1 - 0.707 – j0.707 + j + 0.707 – j0.707 – 1 + 0.707 + j0.707 = 0.707 + j0.293
For k = 4 ;X(4) = 7𝑛=0 x(n) e− jπn
= x(0) + x(1)e-jπ + x(2) e-j2π + x(3)e-j3π + x(4) e-j4π+ x(5)e-j5π + x(6) e-j6π + x(7)e-j7π
=1–1+1-1+1–1=0
For k = 5 ;X(5) = 7n=0 x(n) e− j5πn/4
= x(0)+x(1)e-j5π/4+x(2)e-j5π/2+x(3)e-j15π/4 + x(4) e-j5π+ x(5)e-j25π/4 + x(6) e-j15π/2 + x(7)e-j35π/4
= 1 - 0.707 + j0.707 – j + 0.707 + j0.707 – 1 + 0.707 - j0.707 = 0.707 – j0.293
For k = 6; X(6) = 7n=0 x(n) e− j3πn/2
= x(0) + x(1)e-j3π/2 + x(2) e-j3π + x(3)e-j9π/2 + x(4) e-j6π+ x(5)e-j15π/2 + x(6) e-j9π + x(7)e-j21π/2
=1+j–1-j+1+j=1+j
For k = 7; X(7) = 7𝑛=0 x(n) e− j7πn/4
= x(0)+x(1)e-j7π/4+x(2)e-j7π/2+ x(3)e-j21π/4 + x(4) e-j7π+ x(5)e-j35π/4 + x(6) e-j21π/2 + x(7)e-j49π/4
= 1 + 0.707 + j0.707 + j - 0.707 + j0.707 – 1 - 0.707 - j0.707 = -0.707 + j1.707
X(k) = {6, -0.707 - j1.707, 1 - j, 0.707 + j0.293, 0, 0.707 – j0.293, 1 + j, -0.707 + j1.707}
EXAMPLE - 11: -Find IDFT of the sequence X(k) = {5, 0, 1-j, 0, 1, 0, 1+j, 0}
1
SOLUTION: We have x(n) = 𝑁 N−1 𝑘=0 X(k) e
j2πnk /N
, n = 0, 1,… N-1
𝟏 𝟕 𝐣𝛑𝐧𝐤/𝟒
For N = 8, x(n) = 𝟖 𝒌=𝟎 𝐗(𝐤) 𝐞 , n = 0, 1, 2, …,7
1 7 1
For n = 0; x(0) = 8 𝑘=0 X(k) = 8[5 + 0 + 1-j + 0 + 1 + 0 + 1+j + 0] = 1
1 7 jπk/4 1 1
For n = 1; x(1) = 8 𝑘=0 X(k) e = 8[5 + 0 + (1-j)(j) + 0 + 1(-1) + 0 + (1+j)(-j) + 0] = 8[6] = 0.75
<DIGITAL SIGNAL PROCESSING> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DSP [ETT 603] <FOURIER TRANSFORM: ITS APPLICATIONS PROPERTIES > [Page 4.6]
1 7 jπk/2 1 1
For n = 2; x(2) = 8 𝑘=0 X(k) e = 8[5 + 0 + (1-j)(-1) + 0 + 1(1) + 0 + (1+j)(-1) + 0] = 8[4] = 0.5
1 7 j3πk/4 1 1
For n = 3; x(3) = 8 𝑘=0 X(k) e = 8[5 + 0 + (1-j)(-j) + 0 + 1(-1) + 0 + (1+j)(j) + 0] = 8[2] = 0.25
1 7 jπk 1 1
For n = 4; x(4) = 8 𝑘=0 X(k) e = 8[5 + 0 + (1-j)(1) + 0 + 1(1) + 0 + (1+j)(1) + 0] = 8[8] = 1
1 7 j5πk/4 1 1
For n = 5; x(5) = 8 𝑘=0 X(k) e = 8[5 + 0 + (1-j)(j) + 0 + 1(1) + 0 + (1+j)(-j) + 0] = 8[6] = 0.75
1 7 j3πk/2 1 1
For n = 6; x(6) = 8 𝑘=0 X(k) e = 8[5 + 0 + (1-j)(-1) + 0 + 1(1) + 0 + (1+j)(-1) + 0] = 8[4] = 0.5
1 7 j7πk/4 1 1
For n = 7; x(7) = 8 𝑘=0 X(k) e = 8[5 + 0 + (1-j)(-j) + 0 + 1(-1) + 0 + (1+j)(j) + 0] = 8[2] = 0.25
x(n) = {1, 0.75, 0.5, 0.25, 1, 0.75, 0.5, 0.25}
PRACTICE PROBLEMS:
i. Compute 4-point DFT of the sequence x(n) = {0, 2, 4, 6} Ans : 12, -4 + j4, -4, -4 - j4
ii. Compute 8-point DFT of the sequence x(n) = {2, 22, 23, 24} = {2, 4, 8, 16}
Ans: {30, -6.48 - j22, -6 + j12, 10.48 - j6.14, -10, 10.48 + j6.4, -6 - j12, -6.48 + j22}
RELATIONSHIP OF THE DFT TO OTHER TRANSFORM:-
RELATIONSHIP TO THE FOURIER TRANSFORM
The Fourier transform X(ejω) of a finite duration sequence x(n) having length N is given by
X(ejω) = 𝐍−𝟏
𝐧=𝟎 𝐱(𝐧) 𝐞
𝐣𝛚𝐧
…………… (1) Where X(ejω) is a continuous function of ω.
The discrete Fourier transform of x(n) is given by X(k) = 𝐍−𝟏
𝒏=𝟎 𝐱(𝐧) 𝐞
− 𝐣𝟐𝛑𝐧𝐤/𝐍
, k = 0, 1,… N-1…(2)
Comparing equation 1 & 2, we find that the DFT of x(n) is a sampled version of the Fourier transform
of the sequence and is given by, X(k) = 𝑿(𝐞 𝐣𝛚 ) 𝝎=𝟐𝛑𝐤/𝐍, k = 0, 1,… N-1 ……… (3)
RELATIONSHIP TO THE Z- TRANSFORM
𝐍−𝟏 −𝐧
Let us consider a sequence x(n) of finite duration N with z-transform X(z) = 𝒏=𝟎 𝐱(𝐧) 𝐳 ………(4)
𝟏
We have x(n) = 𝑵 𝐍−𝟏 𝒌=𝟎 𝐗(𝐤) 𝐞
𝐣𝟐𝛑𝐧𝐤/𝐍
………………………(5)
Substituting equation 5 in 4,
N−1 𝟏 𝐍−𝟏 j2πnk /N 1 N−1 N−1 n 𝟏−𝐳 −𝐍 𝐍−𝟏 𝑿(𝒌)
X(z) = 𝑛=0 𝑵 𝒌=𝟎 𝐗(𝐤) e z −n = 𝑁 𝑘=0 X(k) 𝑛=0 ej2πk/N z −1 = 𝒌=𝟎 𝟏−𝐞𝐣𝟐𝛑𝐤/𝐍 𝐳 −𝟏
𝑵
PROPERTIES OF DFT:-
The properties of DFT can be listed as under:
1) Periodicity 7) Complex conjugate property
2) Linearity 8) Circular convolution
3) Shifting property 9) Circular correlation
4) Time reversal of a sequence 10) Multiplication of two sequences
5) Circular time shift 11) Parseval׳s Theorem
6) Circular frequency shift
1. PERIODICITY
This property states that if a discrete-time signal is periodic then its DFT will also be periodic.
Also, if a signal or sequence repeats its waveform after N number of samples then it is called a periodic
signal or sequence and N is called the period of signal.
Mathematically, If X(k) is an N-point DFT of x(n), then we have
x(n + N) = x(n) for all values of n & X(k + N) = X(k) for all values of k
2. LINEARITY
Linearity properties states that if X1(k) and X2(k) are the N-point DFTs of x1(n) and x2(n) respectively,
and a and b are arbitrary constants either real or complex-valued, then we have
𝐷𝐹𝑇
ax1(n) + bx2(n) 𝑁 aX1(k) + bX2(k)
3. SHIFTING PROPERTY
This property can be explained as follows:
Let xp(n) is a periodic sequence with period N, which is obtained by extending x(n) periodically i.e.
xp(n) = ∞ 𝑙=−∞ x(n − 𝑙N).
Now, let us shift the sequence xp(n) by k units to the right.
Again, let resultant signal be expressed as xp(n) is expressed as xp(n) = xp(n-k) = ∞
𝑙=−∞ x(n − k − 𝑙N)
<DIGITAL SIGNAL PROCESSING> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DSP [ETT 603] <FOURIER TRANSFORM: ITS APPLICATIONS PROPERTIES > [Page 4.7]
The finite duration sequence x′ n = {xp′ (n), for 0
≤ n ≤ N − 1 ; and 0, Otherwise} can be obtained
from x(n) by a circular shift.
The circular shift of a sequence can be represented as the index modulo N, x(׳n) = x[n-k, (mod N)]
4. TIME REVERSAL OF A SEQUENCE
𝐷𝐹𝑇
This property of DFT states that, If x(n) 𝑁 X(k), then, we have
𝐷𝐹𝑇
x [-n, (mod N)] = x(N - n) 𝑁 X(k, (mod N)) = X(N - k)
Thus, when the N-point sequence in time is reversed, it is equivalent to reversing the DFT values.
5. CIRCULAR TIME SHIFT
𝐷𝐹𝑇 𝐷𝐹𝑇
−j2πk/N
This property of DFT states that, If x(n) 𝑁 X(k), then x[n-l, (mod N)] 𝑁 X(k) e
This means that shifting of the sequence by l units in the time-domain is equivalent to multiplication of
e−j2πk/N in the frequency-domain.
6. CIRCULAR FREQUENCY SHIFT
𝐷𝐹𝑇 𝐷𝐹𝑇
j2π𝑙n/N
This property of DFT states that, If x(n) 𝑁 X(k), then x(n)e 𝑁 X(k - l, (mod N))
This means that when the sequence x(n) is multiplied by the complex exponential sequence ej2π𝑙n/N , it
is equivalent to circular shift of the DFT by l units in the frequency domain.
7. COMPLEX CONJUGATE PROPERTY
𝐷𝐹𝑇
This property of DFT states that, If x(n) 𝑁 X(k), then
𝐷𝐹𝑇 𝐷𝐹𝑇 1 1 ∗
N−1 ∗ j2πkn /N N−1 j2πk(N−n)/N
x*(n) 𝑁 X*(-k,(mod N))=X*(N-k) & X*(k) 𝑁 𝑁 𝑘=0 X (n)e = 𝑁 𝑘=0 X(n)e
𝐷𝐹𝑇
Hence x*[-n, (mod N)] = x*(N-k) 𝑁 X*(k)
8. CIRCULAR CONVOLUTION: - Circular convolution property states that
𝐷𝐹𝑇 𝐷𝐹𝑇 𝐷𝐹𝑇
If x1(n) 𝑁 X1(k) and x2(n) 𝑁 X2(k) then x1(n) x2(n) 𝑁 X1(k) X2(k)
Where x1(n) N x2(n) denotes the circular convolution of the sequence x1(n) and x2(n) expressed as
x3(n) = N−1 N−1
𝑚 =0 x1 (m)x2 (n − m, (mod N))= 𝑚 =0 x1 (m)x1 (n − m, (mod N))
9. CIRCULAR CORRELATION
This property of DFT states that for complex valued sequence x(n) and y(n),
𝐷𝐹𝑇 𝐷𝐹𝑇 𝐷𝐹𝑇
If x(n) 𝑁 X(k) and y(n) 𝑁 Y(k), then rxy(l) 𝑁 Rxy(k) = X(k) Y*(k)
Where rxy(l) is the (un-normalized) circular cross-correlation sequence, given as
rxy(l) = N−1 ∗
𝑛=0 x(n)y (n − 𝑙, (mod N))
10. MULTIPLICATION OF TWO SEQUENCES: - This property of DFT states that
𝐷𝐹𝑇 𝐷𝐹𝑇 𝐷𝐹𝑇 1
If x1(n) 𝑁 X1(k) and x2(n) 𝑁 X2(k) then x1(n) x2(n) 𝑁 𝑁 X1(k) X2(k)
11. PARSEVAL׳S THEOREM
This property of DFT states that for complex valued sequence x(n) and y(n),
𝐷𝐹𝑇 𝐷𝐹𝑇 1
N−1 ∗ N−1 ∗
If x(n) 𝑁 X(k) and y(n) 𝑁 Y(k), then 𝑛=0 x(n)y (n) =𝑁 𝑘=0 X(k)Y (k)
N−1 1
If y(n) = x(n), then the above equation reduces to N−1 2
𝑛=0 x(n) = 𝑁 𝑘=0 X(k)
2
It relates the energy in finite duration sequence x(n) to the power in the frequency components X(k).
PROPERTIES OF THE DFT: -
SN PROPERTIES TIME DOMAIN FREQUENCY DOMAIN
1. PERIODICITY x(n) = X(n + N) X(k) = X(k + N)
2. LINEARITY a1x1(n) + a2x2(n) a1X1(k) + a2X2(k)
3. TIME REVERSAL OF A SEQUENCE x(N - n) X(N - k)
4. CIRCULAR TIME SHIFT x((n - l))N X(k) e-j2πkl/N
5. CIRCULAR FREQUENCY SHIFT x(n) ej2πln/N X((k - l))N
6. CIRCULAR CONVOLUTION x1(n) x2(n) X1(k) X2(k)
7. CIRCULAR CORRELATION x1(n) y* (-n) X(k) Y* (k)
1
8. MULTIPLICATION OF TWO SEQUENCES x1(n) x2(n) [X1(k) X2(k)]
𝑁
<DIGITAL SIGNAL PROCESSING> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DSP [ETT 603] <FOURIER TRANSFORM: ITS APPLICATIONS PROPERTIES > [Page 4.8]
9. COMPLEX CONJUGATE PROPERTY x* (n) X* (N - k)
N−1 ∗ 1 N−1 ∗
10. PARSEVAL׳S THEOREM 𝑛=0 x(n)y (n) 𝑁 𝑘=0 X(k)Y (k)
The sequence x2(n) is repeated via circular shift of samples and represented in N x N matrix form.
The sequence x1(n) is represented as column matrix.
The multiplication of these two matrices gives the sequences x3(n).
EXAMPLE – 1: -
Find the circular convolution of two finite duration sequences x1(n) = {1, -1, -2, 3, 1}; x2(n) = {1, 2, 3}
SOLUTION (By Circular Convolution Method)
To find circular convolution, both sequences must be of same length.
Therefore we append two zeros to the sequence x2(n) and use concentric
circle method to find circular convolution.
We have x1(n) = {1, -1, -2, 3, 1} and x2(n) = {1, 2, 3, 0, 0}
Graph all points of x1(n) on the outer circle in counterclockwise direction.
Starting at same point as x1(n) graph all points of x2(n) on the inner circle
in clockwise direction. Multiply corresponding samples on the circle and
add to obtain, y(0) = 1(1) + 0(-1) + 0(-2) + 3(3) + 2(-1) = 8
Rotate the inner circle in counterclockwise direction by one sample, multiply corresponding samples.
<DIGITAL SIGNAL PROCESSING> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DSP [ETT 603] <FOURIER TRANSFORM: ITS APPLICATIONS PROPERTIES > [Page 4.9]
y(1) = 1(2) + 1(-1) + 0(-2) + 3(0) + 3(-1) = - 2 ; y(2) = 3(1) + 2(-1) + 1(-2) + 0(3) + 0(-1) = - 1
y(3) = 0(1) + 3(-1) + 2(-2) + 1(3) + 0(-1) = - 4 ; y(4) = 0(1) + 0(-1) + 3(-2) + 2(3) + 1(-1) = - 1
y(n) = {8, -2, -1, -4, -1}
SOLUTION (By Matrix Method)
Given that x1(n) = {1, -1, -2, 3, 1} & x2(n) = {1, 2, 3} {We Can Inter change Two Signals}
By adding two zeros to the
sequences x2(n), we bring the
length of the sequence x2(n) to 5.
Now x2(n) = {1, 2, 3, 0, 0}
The matrix form can be written
by substituting N = 5 in above
matrix method equation, we get
By representing the sequence x2(n) in N x N matrix form and x1(n) in column matrix form and multiply
to get y(n). y(n) = {8, -2, -1, -4, -1}
EXAMPLE - 2
Find the circular convolution of two finite duration
signal x1(n) = {1, 2, 2, 1} & x2(n) = {1, 2, 3, 1} using
(1) Concentric circle method (2) Matrix
multiplication method.
SOLUTION: - (A)By Concentric Circle Method
y(0) = 1(1) + 2(1) + 2(3) + 1(2) = 11 ; y(1) = 1(2) + 2(1) + 2(1) + 1(3) = 9
y(2) = 1(3) + 2(2) + 2(1) + 1(1) = 10 ; y(3) = 1(1) + 2(3) + 2(2) + 1(1) = 12
y(n) = {11, 9, 10, 12}
a) By Matrix Multiplication Method
Represent the sequence x2(n) in N x N matrix form & x1(n) in column matrix form i.e. substitute N = 4.
Substitute the sequence values and multiply as shown fig above. y(n) = {11, 9, 10, 12}
EXAMPLE - 3
Given the sequences x1(n) = {1, 2, 3, 4}; x2(n) = {1, 1, 2, 2}. Find x3(n) such that X3(k) = X1(k) X2(k).
SOLUTION
As x3(n) = IDFT [X3(k)] = IDFT [X1(k) X2(k)] = x1(n) x2(n)
<DIGITAL SIGNAL PROCESSING> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DSP [ETT 603] <FOURIER TRANSFORM: ITS APPLICATIONS PROPERTIES > [Page 4.10]
So we find x3(n) by circular convolving x1(n) and x2(n).
Given that x1(n) = {1, 2, 3, 4} and x2(n) = {1, 1, 2, 2}
Representing x2(n) as N x N matrix form and x1(n) in column
matrix and multiplying we have, y(n) = {15, 17, 15, 13}
EXAMPLE – 4: - Perform the circular convolution of the
following sequences x(n) = {1, 1, 2, 1} and h(n) = {1, 2, 3, 4}. Using DFT and IDFT method
SOLUTION : - We know X3(k) = X1(k) X2(k)
X1(k) = 𝐍−𝟏
𝒏=𝟎 𝐱 𝟏 (𝐧) 𝐞
− 𝐣𝟐𝛑𝐧𝐤/𝐍
, k = 0, 1,… N-1 ; But given x1(n) = {1, 1, 2, 1} and N = 4
3
X1(0) = 𝑛 =0 x1 (n) = 1+1+2+1 = 5 ; X1(1) = 3𝑛 =0 x1 (n) e− jπn/2 = 1 – j – 2 + j = -1
3
X1(2) = 𝑛 =0 x1 (n) e − jπn
= 1 – 1 + 2 - j = 1; X1(3) = 3𝑛 =0 x1 (n) e− j3πn/2 = 1 + j – 2 - j = -1
DFT {x1 (n)} X1(k) = (5, -1, 1, -1)
𝐍−𝟏 − 𝐣𝟐𝛑𝐧𝐤/𝐍
X2(k) = 𝐱 𝟐 (𝐧) 𝐞
𝒏=𝟎 , k = 0, 1,… N-1 ; But given x2(n) = {1, 2, 3, 4} and N = 4
3
X2(0) = 𝑛 =0 x2 (n) = 1+2+3+4=10
X2(1) = 3𝑛 =0 x2 (n) e− jπn/2 = 1 + 2(–j) + 3(-1) + 4(j) = -2 + j2
X2(2) = 3𝑛 =0 x2 (n) e− jπn = 1 + 2(-1) + 3(1) + 4(-1) = -2
X2(3) = 3𝑛 =0 x2 (n) e− j3πn/2 = 1 + 2(j) + 3(-1) + 4(-j) = -2 - j2
DFT {x2 (n)} X2(k) = (10, -2 + j2, -2, -2 - j2)
𝟏
X3(k) = X1(k) X2(k) = {50,2–j2, -2,2+j2}; But IDFT{x3(k)}=𝑵 𝐍−𝟏
𝒌=𝟎 𝐗 𝟑 (𝐤) 𝐞
𝐣𝟐𝛑𝐧𝐤/𝐍
, n = 0, 1,… N-1
1 3 1
x3(0) = 4 𝑛=0 X 3 (k) = 4 (50 + 2 – j2 – 2 + 2 + j2) = 13
1 4 jπk/2 1
x3(1) = 4 𝑘=0 X 3 (k) e = 4 [50 + (2 – j2)j + (– 2) (-1) + (2 + j2) (-j)] = 14
1 4 jπk 1
x3(2) = 4 𝑘=0 X 3 (k) e = 4 [50 + (2 – j2) (-j) + (– 2) (-1) + (2 + j2) (j)] = 12
x3(n) = {13, 14, 11, 12}
EXAMPLE - 5
Consider the sequence x1(n) = {0, 1, 2, 3, 4} and x2(n)
= {0, 1, 0, 0, 0}. Find y(n) so that Y(k) = X1(k) X2(k).
SOLUTION The sequence y(n) can be obtained by
circular convolution of x1(n) and x2(n). Using Matrix
approach we have y(n) = {4, 0, 1, 2, 3}
TASK -1: - Perform the circular convolution of the following sequences,
i. x1(n) = {1, 1, 2, 1}; x2(n) = {1, 2, 3, 4}. Ans: - {13, 14, 11, 12}
ii. x1(n) = {1, 2, 3, 1}; x2(n) = {4, 3, 2, 2}. Ans: - {17, 19, 22, 19}
TASK 2: - Find circular convolution of the following sequences, x(n) = {1, 1, 1, 2}; h(n) = {1, 2, 3, 2}
using DFT and IDFT method. Ans: - {10, 11, 10, 09}
TASK 3: - Find circular convolution of the following sequences, x1(n) = {2,1,0,0,5}; x2(n) = {2,2,1,1}
TASK 4: - Find circular convolution of the following sequences, x1(n) = {1, 2, 2, 1}; x2(n) = {1,2,3,1}
TASK 5: - Find circular convolution of the following sequences, x1(n) = {1, 1, -1, 2}; x2(n) = {2,0,1,1}
TASK 6: - Find circular convolution of the following sequences, x1(n) = {1, 2, 3, 4}; x2(n)= {4, 3,2,1}
TASK 7: - Find circular convolution of the following sequences, x1(n) = {1,-1, 2, 3}; x2(n)= {0, 1,2,3}
∞ −𝒋𝝎𝒕
𝟏 ∞
CTFT X(jω) = − ∞ 𝒙(𝒕) 𝒆 𝒅𝒕 ICTFT 𝒙 𝒕 = 𝑿(𝒋𝝎) 𝒆 𝒋𝝎𝒕 𝒅𝝎
𝟐𝝅 − ∞
𝒋𝝎 ∞ −𝒋𝝎𝒏
𝟏 ∞
DTFT X(𝒆 ) = −∞
𝒙(𝒏) 𝒆 IDTFT 𝒙 𝒏 = 𝑿(𝒆 𝒋𝝎) 𝒆 𝒋𝝎𝒏 𝒅𝝎
𝟐𝝅 − ∞
N-Point 𝐍−𝟏 −𝐣𝟐𝛑𝐧𝐤/𝐍 𝐍−𝟏 𝐤𝐧
X(k) = 𝒏=𝟎 𝐱(𝐧)𝐞 X(k) = 𝒏=𝟎 𝐱(𝐧) 𝐖𝐍
DFT
N-Point 𝟏 𝐍−𝟏 𝐣𝟐𝛑𝐧𝐤/𝐍 𝟏 𝐍−𝟏 − 𝐤𝐧
x(n) = 𝒌=𝟎 𝐗(𝐤)𝐞 = 𝒌=𝟎 𝐗(𝐤)𝐖𝐍
IDFT 𝑵 𝑵
= N−1
n=0 Re x(n) Re WN nk − N−1
n=0 Im x(n) Im WN nk
nk nk
+ j N−1
n=0 Im x(n) Re WN + N−1
n=0 Re x(n) Im WN …….(04)
From Eq.(3) we see that to evaluate one value of X (k), the number of complex multiplications required
is N. Therefore to evaluate all N value of X(k), the number of complex multiplications required is N2.
In the same way, to evaluate all N value of X(k), the total number of additions required is N(N-1).
From Eq.(4), we can observe that the computation of X(k) for each k requires 4N real multiplications.
Therefore, to evaluate X(k) for all k from 0 to N - 1 requires 4N2 real multiplications.
Each of the four sums of N terms requires N - 1 real two-input additions, and to combine the sum to get
the real part and imaginary part requires two more.
Therefore to evaluate X(k) for each k requires 4 (N - 1) + 2 real additions.
For all values of k a total number of real additions N (4N - 2) required for direct evaluation of the DFT.
The above results are obtained by assuming the value of WN nk as always complex, even though for
some values of kn, it equals to 1, -1, j or -j. the direct evaluation of the DFT is basically inefficient
because it does not use the symmetry and periodicity properties of the twiddle factor WN·
These two are Symmetry Property: WN k+N/2 = −WN k & Periodicity Property: WN k+N = WN k ...(05)
THE FAST FOURIER TRANSFORM : -
The fast Fourier transform algorithms exploit the two basic properties of the twiddle factor shown in
𝑵
Eq. (5) & reduces the number of complex multiplications required to perform DFT from N2 to log2N.
𝟐
6
For ex if N = 1024, this implies about 5000 instead of 10 multiplications - a reduction factor of 200.
FFT algorithm is based on the fundamental principle of decomposing the computation of Discrete
Fourier Transform of a sequence of length N into successively smaller Discrete Fourier Transforms.
<FAST FOURIER TRANSFORM (FFT)> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [Page 5.2]
[ETT 604]
There are two classes of FFT algorithms. That is Decimation-In-Time & Decimation-In-Frequency.
In Decimation-In-Time, sequence for which we need DFT is successively divided into sequences &
DFTs of these subsequences are combined in a certain pattern to obtain required DFT of entire signal.
In the Decimation-In-Frequency approach, the frequency samples of the DFT are decomposed into
smaller and smaller subsequences in a similar manner.
DECIIMATION.IN-TIME ALGORITHM : -
This algorithm is also known as Radix-2 DIT FFT algorithm which means the number of output points
N can be expressed as a power of 2, that is, N = 2M, where M is an integer.
Let x(n) is an N-point sequence, where N is assumed to be a power of 2.
Decimate or break this sequence into two sequences of length N /2, where one sequence consisting of
the Even-indexed values of x( n) and the other of Odd-indexed values of x(n).
𝑁 𝑁
That is xe(n) = x(2n), n = 0, 1, …, − 1 AND Xo(n) = x(2n+1), n = 0, 1, …, −1 …….(06)
2 2
𝐍−𝟏 𝐧𝐤
The N-point DFT of x(n) can be written as X(k) = 𝐧=𝟎 𝐱(𝐧)𝐖𝐍 , k = 0, 1, …, N-1 …….(07)
Separating x (n) into Even and Odd indexed values of x(n),we obtain
nk nk
X(k) = N−1 n=0 x(n)WN + N−1
n=0 x(n)WN
(Even ) (Odd )
𝑁 𝑁
−1 2nk −1
= 2
n=0 x(2n)WN + 2
n=0 x(2n + 1)WN (2n+1)k
𝑁 𝑁
−1 2nk k −1
= 2
n=0 x(2n)WN + WN 2
n=0 x(2n + 1)WN 2nk …….(08)
𝑁 𝑁
−1 2nk −1
Substituting Eq.(6) in Eq.(8) we have, X(k) = 2
n=0 xe (n) WN + WN k 2
n=0 xo (n)WN 2nk …….(09)
2 j2π
But we can write WN 2 = e−j2π/N = e− N /2 = WN/2 WN 2 = WN/2 …….(10)
Substituting Eq.(10) in Eq.(9) we get
𝑁 𝑁
−1 nk k −1
X(k) = 2
n=0 xe (n) WN/2 + WN 2
n=0 xo (n)WN/2 nk …….(11) X(k) = 𝐗 𝐞 (𝐤) + 𝐖𝐍 𝐤 𝐗 𝐨 (𝐤)…(12)
𝑁 𝑁
−𝑝𝑜𝑖𝑛𝑡 𝐷𝐹𝑇 𝑜𝑓 𝑒𝑣𝑒𝑛 −𝑝𝑜𝑖𝑛𝑡 𝐷𝐹𝑇 𝑜𝑓 𝑜𝑑𝑑
2 2
𝑖𝑛𝑑𝑒𝑥𝑒𝑑 𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑒 𝑖𝑛𝑑𝑒𝑥𝑒𝑑 𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑒
𝑁 𝑁
Each of the sums in Eq. (1l) is an 2
-point DFT, the First sum being the 2
-point DFT of the Even-
𝑁
indexed sequence and the Second being the -point DFT of Odd-indexed sequence.
2
𝑁
Although index k ranges from k = 0, 1..., N - 1, each of the sums is computed only for k = 0, 1..., -1,
2
𝑁
since Xe(k) and Xo(k) are periodic in k with period 2 .
After two DFTs are computed, they are combined according to Eq. (12) to get N-point DFT of X (k).
𝑁
So Eq. (12) holds for the values of k = 0, 1, ... , - l. For k ≥ N/2, 𝐖𝐍 𝐤+𝐍/𝟐 = −𝐖𝐍 𝐤 …….(13)
2
𝐍
𝑵 𝑵 𝑁 𝑁
Now X(k) for k ≥ N/2 is given by X(k) = 𝐗 𝐞 𝐤 − 𝟐 - 𝐖𝐍 𝐤−𝟐 𝐗 𝐨 𝐤 − 𝟐 for k = 2 , 2 +1, …, N-1...(14)
Let us find the number of complex multiplications and complex additions required to compute Eq.(12).
For direct evaluation of DFT we know that number of complex multiplications required is equal to N2.
𝑵 𝑁 2
In same way to calculate - Point DFT of Xe(k) we need complex multiplications & to compute
𝟐 2
𝑁 2 𝑁 2
Xo(k) we need another complex multiplications. That is we need 2 complex multiplications.
2 2
𝑁
Then the two - point DFTs are combined to get X(k). For this we need N complex multiplications.
2
𝑵 𝟐 𝑵 𝟐 𝐍𝟐
Thus total number of complex multiplications required for computing X(k) is + +N=N+
𝟐 𝟐 𝟐
𝑵 𝑵 𝑵 𝑵 𝐍𝟐
Similarly the total number of complex Additions required is −𝟏 + +𝟏 +N=
𝟐 𝟐 𝟐 𝟐 𝟐
<FAST FOURIER TRANSFORM (FFT)> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 604] [Page 5.3]
2
The direct evaluation of X(k) requires N Complex multiplications and N(N - 1) complex additions.
𝑁
When we decompose x(n) into two subsequences of length and compute X(k) using Eq.(12) the
2
number of computations are reduced by a factor of 2. If we again decompose the sequence Xe(k) and
Xo(k) into two subsequences, then the amount of computation again be cut in half.
Now let us take N = 8. Then Xe(k) and Xo(k) are 4-point (N/2) DFTs of Even-indexed sequence xe(n)
and Odd-indexed sequence xo(n) respectively, where
xe(0) = x(0); xe(1) = x(2); xe(2) = x(4); xe(3) = x(6);
xo(0) = x(1); xo (1) = x(3); xo (2) = x(5); xo (3) = x(7)
k
From Eq.(12) and Eq.(14) we have X(k) = Xe (k) + W8 Xo (k) for 0 ≤ k ≤ 3
𝐤−𝟒
= 𝐗 𝐞 (𝐤 − 𝟒) + 𝐖𝟖 𝐗 𝐨 (𝐤 − 𝟒) for 4 ≤ k ≤ 7 …….(15)
By substituting different values of k we get
X(0) = Xe (0) + W8 0 Xo (0); X(4) = X e (0) - W8 0 Xo (0)
X(1) = Xe (1) + W8 1 Xo (1); X(5) = X e (1) - W8 1 Xo (1)
X(2) = Xe (2) + W8 2 Xo (2); X(6) = X e (2) - W8 2 Xo (2)
X(3) = Xe (3) + W8 3 Xo (3); X(7) = X e (3) - W8 3 Xo (3) …….(16)
From above equation, we find X(0) & X(4), X(1) & X(5), X(2) & X(6), X(3) & X(7) have same inputs.
X(0) is obtained by multiplying Xo(0) with W8 0 and adding the
product to Xe(0). Similarly X(4) is obtained by multiplying Xo(0)
with W8 0 and subtracting the product from Xe(0).
This operation can be represented by a butterfly diagram as in Fig.
Now the values X(k) for k = 1,2,3,4,5,6,7 can be obtained
An 8-point DFT flow graph can be constructed from two 4-point DFTs as shown in Fig. 5.2.
From Fig. 5.2 we can find that initially the sequence xo(n) is
shuffled into even indexed sequenced xe(n) & odd-indexed
sequence xo(n) & then transformed to give Xe(k) and Xo(k).
For k = 0, 1, 2, 3 the values Xe(k) and Xo(k) are combined
according to Eq. (16) and using butterfly structure shown in
Fig. 5.1 the 8-point DFT is obtained.
N
The inputs to the butterfly are separated by 2 samples i.e. 4
samples and the powers of the twiddle factors associated in
this set of butterflies are in natural order.
N
Now we apply the same approach to decompose each of 2
samples DFT. This can be done by dividing the sequence xe(n) and xo(n) into two sequences consisting
of even and odd members of the sequences.
N N
The - point DFTs can be expressed as a combination of – point DFTs.
2 4
N N
That is, Xe(k) for 0 ≤ k ≤ − 1 can be written as 𝐗 𝐞 (𝐤) = 𝐗 𝐞𝐞 (𝐤) + 𝐖𝐍 𝟐𝐤 𝐗 𝐞𝐨 (𝐤) for 0 ≤ k ≤ −1
2 2
𝐍 𝐍 N N
= 𝐗 𝐞𝐞 𝐤 − 𝟒 - 𝐖𝐍 𝟐(𝐤−𝐍/𝟒) 𝐗 𝐞𝐨 𝐤 − 𝟒 for ≤k≤ −1 ……. (17)
4 2
N N
Where Xee (k) is the - point DFT of the even member of xe(n) and Xeo (k) is the 4 - point DFT of the
4
N
odd members of xe(n). In the same way 𝐗 𝐨 (𝐤) = 𝐗 𝐨𝐞 (𝐤) + 𝐖𝐍 𝟐𝐤 𝐗 𝐨𝐨 (𝐤) for 0 ≤ k ≤ −1
2
𝐍 𝐍 N N
= 𝐗 𝐨𝐞 𝐤 − 𝟒 - 𝐖𝐍 𝟐(𝐤−𝐍/𝟒) 𝐗 𝐨𝐨 𝐤 − 𝟒 for ≤k≤ −1 …….(18)
4 2
N N
Where Xoe (k) is the 4 - point DFT of the even member of xo(n) and Xoo (k) is the - point DFT of the
4
odd members of xo(n).
<FAST FOURIER TRANSFORM (FFT)> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 604] [Page 5.4]
For N = 8 the sequence xe(n) can be divided into even and odd indexed sequences as
xee(0) = xe(0); xee(1) = xe(2) & xeo(0) = xe(1); xeo(1) = xe(3)
Now from Eq.(17) we have Xe (0) = Xee (0) + W8 Xeo (0) ; Xe (1) = Xee (1) + W8 2 Xeo (1)
0
Xe (2) = Xee (0) - W8 0 Xeo (0) ; Xe (3) = Xee (1) - W8 2 Xeo (1) …(19)
Where, Xee (k) is 2 point DFT of even member of xe(n) and Xeo(k) is of odd members of xe(n).
Similarly the sequence xo(n) can be divided into even and odd member sequences as
xoe(0) = xo(0); xoe(1) = xo(2) & xoo(0) = xo(1); xoo(1) = xo(3)
Now from Eq.(17) we have Xo (0) = Xoe (0) + W8 Xoo (0) ; Xo (1) = Xoe (1) + W8 2 Xoo (1)
0
Xo (2) = Xoe (0) - W8 0 Xoo (0) ; Xo (3) = Xoe (1) - W8 2 Xoo (1) … (19)
Where Xoe (k) is the 2 point DFT of even
member of xo(n) and Xoo(k) is the 2-point
DFT of odd members of xo(n).
Fig.5.3 shows the resulting flow graph the
four-point DFTs of Fig.5.2 are evaluated
as in Eq.(19) and Eq.(20).
From Fig. 4.3 we find that the input
sequence is again reordered, the input
samples to each butterfly are separated by
N
samples i.e., 2 samples and there are two
4
sets of butterflies. In each set of butterflies the twiddle factor exponents are same and separated by two.
N
For the more general case, We could proceed by decomposing the 4 - point transforms in Eq. (17) and
N
Eq.(18) into 8 - point transforms and continue until we are left with only 2-point transforms.
Each decomposition is called a stage, and the total number of stages is given by M = log2(N).
In each stage we compute N values. Each value computed from a butterfly equation requires one
complex multiplication. Therefore each stage requires a total of N complex multiplications.
Since the number of stages is equal to log2N, the entire FFT requires a total of Nlog2N multiplications.
But we know W0 = 1; WN/2 = -1 and W±N/4 = -i about half of the multiplications are not really needed.
N
Therefore the entire FFT requires log2N complex multiplications. Each butterfly equation requires
2
one complex addition. Thus the entire number complex additions are given by N log2N.
For an 8-point DFT the number of stages required is three.
So far we have seen the decomposition for stage 3 and
stage 2. For stage 1 the two point DFT can be easily found
by adding and subtracting the input sequences as the
twiddle factor associated with first stage is W80 = 1.
That is the first stage involves no multiplication but
addition and subtraction. Now we have
Xee(0) = xee(0) + xee(1) = xe(0) + xe(2) = x(0) + x(4)
Xee(1) = xee(0) - xee(1) = xe(0) - xe(2) = x(0) + x(4) ….(21)
The algorithm has been called Decimation In Time since at
each stage; input sequence is divided into smaller
sequences, i.e., input sequences are decimated at each stage.
BIT-REVERSAL:
In DIT algorithm we can find that for the output sequence to
be in a natural order (i.e. X(k), k = 0, 1, …, N-1) the input
sequence has to be stored in a shuffled order.
<FAST FOURIER TRANSFORM (FFT)> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 604] [Page 5.5]
For an 8 - point DIT algorithm the Input sequence is x(0), x(4), x(2), x(6), x(5), x(3), and x(7).
We can see that when N is a Power of 2, the input sequence must be stored in blt-reversal order for the
output to be computed in a natural order. For N = 8 the bit-reversal process is shown in above table 5.1.
BASIC OPERATION:
The basic computation block in the diagram is the "butterfly" in
which two inputs are combined to give two outputs.
If we use m to represent the stage and p and q to represent nodes in
the stage, each butterfly can be represented as shown in Fig. where
power k of WN is variable & depends on the position of butterfly.
The nodes p and q represent memory locations. At the input nodes p and q the input values Xm(p) and
Xm(q) are stored. After the outputs Xm+1(p) and Xm+1(q) are calculated, the same memory location is
used to store the new values in place of the input values.
An algorithm that uses the same locations to store both the input and output sequences is called an in-
place algorithm. The FFT algorithm reduces the number of computations.
The total number of complex
multiplications required for
N
calculating DIT-FFT = log2N and
2
the total number of complex
additions for evaluating a DFT
using DIT-FFT is N log2N.
A comparison of number of complex
multiplications required for direct
evaluation of the DFT ^ the number
needed for FFT is given in table 5.2.
SUMMARY OF STEPS OF RADIX - 2 DIT-FFT ALGORITHM : -
1. The number of input samples N = 2M, where, M is an integer.
2. The input sequence is shuffled through bit-reversal.
3. The number of stages in the flow graph is given by M = log2N.
𝑁
4. Each stage consists of butterflies.
2
5. Inputs/outputs for each butterfly are separated by 2m-1 samples, where m represents the stage index, i.e,
for first stage m = 1 and for second stage m = 2 so on.
𝑁
6. The number of complex multiplications is given by log2N.
2
7. The number of complex additions is given by N log2N.
𝐍
8. The twiddle factors are a function of the stage index m & is given by K = 𝟐𝐦𝐭 ; t = 0,1,2,.., 2m-1 – 1...(22)
The number of sets or sections of butterflies in each stage is given by the formula 2M-m.
9. The Exponent Repeat Factor (ERF), which is the number of times the exponent sequence associated
with m is repeated is given by 2M-m.
EXAMPLE: Find the DFT of a sequence x(n) = {1, 2, 3, 4, 4, 3, 2, 1} using DIT algorithm.
Solution: The twiddle factors associated with the flow graph are
1
𝐖𝟖 𝟎 = 1; 𝐖𝟖 𝟏 = e−j2π/8 = e−jπ/4 = 0.707 - j0.707
2
𝐖𝟖 𝟐 = e−j2π/8 = e−jπ/2 = -j ;
3
𝐖𝟖 𝟑 = e−j2π/8 = e−j3π/4 = -0.707 - j0.707
The basic operation is,
<FAST FOURIER TRANSFORM (FFT)> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 604] [Page 5.6]
PRACTICE PROBLEM: Find the 8-point DFT of sequence x(n) = {1, 1, 1, 1, 1, 0, 0, 0} using DIT-FFT
algorithm. [ANS: {5, -j2.414, 1, -0.414j, 0.414j, 1, j2.414}]
DECIMATION-IN-FREQUENCY ALGORITHM : -
DIT algorithm is based on the decomposition of the DFT computation by forming smaller and smaller
subsequences of the sequence x(n).
In DIF algorithm the output sequence X(k) is divided into smaller and smaller subsequences.
In this algorithm the input sequence x(n) is partitioned into two sequences each of length N/2 samples.
N
The first sequence x1(n) consists of first 2 samples of x(n) and the second sequence x2(n) consists of
N
the last 2 samples of x(n) i.e., x1(n) = x(n), n = 0, 1, 2,.. N/2-1; x2(n) = x(n+ N/2), n = 0, 1, 2,..N/2-1
If N = 8 the first sequence x1(n) has values for 0 ≤ n ≤ 3 and x2(n) has values for 4 ≤ n ≤ 7.
𝐍
−𝟏
The N-point DFT of x(n) can be written as, X(k) = 𝟐
𝐧=𝟎
𝐱(𝐧)𝐖𝐍 𝐧𝐤 + 𝐍
𝐍 𝐱(𝐧)𝐖𝐍
𝐧𝐤
𝐧=
𝟐
N N
−1 nk (n+N/2)k −1 nk
= 2
n=0 x1 (n) WN + N
n=0 x2 (n)WN = 2
n=0 x1 (n) WN + WN Nk /2 N
n=0 x2 (n)WN
nk
𝐍
−𝟏
= 𝟐
𝐧=𝟎
𝐱 𝟏 (𝐧) 𝐖𝐍 𝐧𝐤 + 𝐞−𝐣𝛑𝐤 𝐍
𝐧=𝟎 𝐱 𝟐 (𝐧)𝐖𝐍
𝐧𝐤
N
−1
When k is Even, e −jπk
= 1 X(2k) = 2
n=0 x1 n + x2 (n) WN 2nk
N 𝐍
−1 −𝟏
= 2
n=0 x1 n + x2 (n) WN/2 nk = 𝟐
𝐧=𝟎
𝐟(𝐧)𝐖𝐍/𝟐 𝐧𝐤 --- (25a); Where f(n) = 𝐱 𝟏 𝐧 + 𝐱 𝟐 (𝐧) --- [25b]
N N
Eq. (25a) is the 2 -point DFT of the 2 -point sequence f(n) obtained by adding the First-half and the last-
half of the input sequence.
N
−1
When k is Odd, e −jπk
= -1 X(2k+1) = 2
n=0 x1 n − x2 (n) WN (2k+1)n
N 𝐍
−1 −𝟏
= 2
n=0 x1 n − x2 (n) WN n WN/2 nk = 𝟐
𝐧=𝟎
𝐠(𝐧)𝐖𝐍/𝟐 𝐧𝐤 ---(26a); Where g(n)=[x1 n − x2 (n)]WN n [26b]
N
Eq. (26) is the 2 -point DFT of the sequence g(n) obtained by subtracting the Second-half of the input
sequence from the first half and then multiplying the resulting sequence with WN n .
From Eq.(25a) and Eq.(26a) we find that the Even and Odd
N
samples of the DFT can be obtained from the -point
2
DFTs of f(n) and g(n) respectively.
The Eq.(25b) and Eq.(26b) can be represented by a
butterfly as shown in Fig. 5.10.
This is the basic operation of DIF algorithm.
<FAST FOURIER TRANSFORM (FFT)> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 604] [Page 5.7]
From Eq.(4.25), for n = 8, we have
X(0) = 3n=0 x1 n + x2 (n) = 3n=0 f(n) = f(0) + f(1) + f(2) + f(3)
X(2) = 3n=0 x1 n + x2 (n) W8 2n = 3n=0 f(n)W8 2n = f(0) + f(1) 𝐖𝟖 𝟐 - f(2) - f(3) 𝐖𝟖 𝟐
4 8
W8 4 = ej2π/8 = ejπ = −1; W8 8 = ej2π/8 = ej2π = 1
X(4) = 3n=0 x1 n + x2 (n) W8 4n = 3n=0 f(n)W8 4n = 3n=0 f(n)(−1)n = f(0) - f(1) + f(2) - f(3)
X(6) = 3n=0 x1 n + x2 (n) W8 6n = 3n=0 f(n)(−W8 2 )n = f(0) - f(1) 𝐖𝟖 𝟐 + f(2) + f(3) 𝐖𝟖 𝟐
From Eq. (4.26) we have
X(1) = 3n=0 x1 n − x2 (n) W8 n = 3n=0 g(n) = g(0) + g(1) + g(2) + g(3)
X(3) = 3n=0 x1 n − x2 (n) W8 3n = 3n=0 g(n)W8 2n = g(0) + g(1) 𝐖𝟖 𝟐 - g(2) - g(3) 𝐖𝟖 𝟐
X(5) = 3n=0 x1 n − x2 (n) W8 5n = 3n=0 g(n)W8 4n = 3n=0 g(n)(−1)n = g(0) - g(1) + g(2) - g(3)
X(3) = 3n=0 x1 n − x2 (n) W8 7n = 3n=0 g(n)(−W8 2 )n = g(0) - g(1) 𝐖𝟖 𝟐 + g(2) + g(3) 𝐖𝟖 𝟐
We have seen that the Even-indexed samples of X(k) can be obtained from the 4-point DFT of the
sequence f(n) where f(n) = x1 n + x2 (n) n = 0, 1, 2, …, N/2-1.
i.e. f(0) = x1 0 + x2 (0) ; f(1) = x1 1 + x2 (1)
f(2) = x1 2 + x2 (2) ; f(3) = x1 3 + x2 (3)
The Odd-indexed samples of X(k) can be
obtained from the 4-point DFT of the sequence
g(n) where g(n)= [x1 n − x2 (n)]W8 n
i.e. g(0) = x1 0 − x2 (0) W8 0
g(1) = x1 1 − x2 (1) W8 1
g(2) = x1 2 − x2 (2) W8 2
g(3) = x1 3 − x2 (3) W8 3
Using the above information and the butterfly structure shown in fig.5.10 we can draw the flow graph
of 8-point DFT shown in fig 5.11.
N
Now each 2 -point DFT can be computed by combining the first half and the last half of the input points
N N
for each of the 2 -point DFTs and then computing 4 -point DFTs.
For the 8-point DFT example the resultant flow graph is shown in Fig. 5.12. The 2-point DFT can be
found by adding and subtracting the input points. The Fig. 5.12 can be further reduced as in. Fig 5.13.
<FAST FOURIER TRANSFORM (FFT)> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 604] [Page 5.8]
Thus the total number of computations is same for DIT and
DIF algorithms. The basic computational block in the
diagram is the "butterfly" shown in Fig. 5.15.
Like DIT algorithm, DIF algorithm also is an in-place
algorithm where the same locations are used to store both the
input and output sequences.
Summary of Steps for Radix - 2 DIF-FFT Algorithm : -
1. The number of input samples N = 2M, where, M is number of stages.
2. The input sequence is in natural order.
3. The number of stages in the flow graph is given by M = log2N.
N
4. Each stage consists of butterflies.
2
5. Inputs/outputs for each butterfly are separated by 2M-m samples, where m represents the stage index i.e.,
for first stage m = 1 and for second stage m = 2 so on.
N
6. The number of complex multiplications is given by log2N.
2
7. The number of complex additions is given by N log2N.
𝐍𝐭
8. Twiddle factor exponents are a function of stage index m & is given by k = 𝟐𝐌−𝐦+𝟏 , t = 0,1,2,..2M-m – 1
9. The number of sets or sections of butterflies in each stage is given by the formula 2m-1.
10. The Exponent Repeat Factor (ERF), which is the number of times the exponent sequence associated
with m repeated is given by 2m-1.
Differences and Similarities between DIT and DIF Algorithms : -
DIFFERENCE
1. For Decimation-In-Time (DIT), the input is bit-reversed while the output is in natural order. Whereas,
for Decimation-In-Frequency (DIF) the input is in natural order while the output is bit reversed order.
2. The DIF butterfly is slightly different from the DIT wherein DIF the complex multiplication takes
place after the add-subtract operation.
SIMILATITIES: Both algorithms require N log2 N operations to compute the DIF. Both algorithms
can be done in-place and both need to perform bit reversal at some place during the computation.
EXAMPLE: Find the DFT of a sequence x(n) = {1, 2, 3, 4, 4, 3, 2, 1}
using DIF algorithm.
Solution: The twiddle factors associated with the flow graph are: -
W8 0 = 1, W8 1 = 0.707 – j0.707; W8 2 = - j, W8 3 = - 0.707 - j0.707
The basic operation is,
<FAST FOURIER TRANSFORM (FFT)> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 604] [Page 5.9]
1; 0 ≤ n ≤7
EXAMPLE: Find 8-point DFT of sequence x(n) = by using DIT & DIF algorithms.
0 ; Otherwise
Solution: The twiddle factors associated with butterflies can be found as,
W8 0 = 1; W8 1 = 0.707 - j0.707; W8 2 = -j; W8 3 = -0.707 - j0.707
X(k) = {2, 0.5 - j1.207, 0, 0.5 – j0.207, 0, 0.5 + j0.207, 0, 0.5 + j1.207} [Same ans in both Method]
<FAST FOURIER TRANSFORM (FFT)> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 604] [Page 5.10]
EXAMPLE: Find DFT of a sequence EXAMPLE: Find DFT of a sequence
x(n) = {1,-1, 1, -1} by DIT algorithm. x(n) = {1, 0, 0, 1} by DIF algorithm.
SOLUTION: Twiddle factors are SOLUTION: Twiddle factors are
0
W4 = 1; W4 = -j1
W4 0 = 1; W4 1 = -j
<FAST FOURIER TRANSFORM (FFT)> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 604] [Page 5.11]
EXAMPLE: An 8-point sequence is given by EXAMPLE: Find the 8-point DFT of the given
x(n) = {2, 2, 2, 2, 1, 1, 1, 1}. Compute 8-point sequence x(n) = {0, 1, 2, 3, 4, 5, 6, 7} using DIF,
DFT of x(n) by radix-2 DIT FFT. radix-2, FFT algorithm.
Solution: Solution:
X (k) = {0, -1.414 + j3.414, 2 – j2, 1.414 – j0.586, Thus the from the butterfly diagram the 4-Pont
4, 1.414 + j0.586, 2 + j2, -1.414 - j3.414} DFT of the given sequence is X(k) = {0, 2, 0, 2}
EXAMPLE: Given x(n) = 2n & N = 8, fine PRACTICE PROBLEM: Find the 8-point
X(k) by DIF-FFT algorithm. DFT of sequence x(n) = {1, 2, 2, 1, 1, 2, 2, 1}
Solution: Given x(n) = 2n using DIF-FFT algorithm.
x(n) = {1, 2, 4, 8, 16, 32, 64, 128} Answer: - {12, 0,.2 - j2, 0, 0, 0, -2 + j2, 0}
<FAST FOURIER TRANSFORM (FFT)> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 604] [Page 5.12]
INTRODUCTION TO DIGITAL FILTERS
Basically a digital filter is a linear time invariant (LTI) system. The term Finite Impulse Response
(FIR) and Infinite Impulse Response (IIR) are used to distinguish filter types.
The FIR filters are of non-recursive type, whereby the present output sample depends on the present
input sample and previous input samples; whereas the IIR filters are recursive type, whereby the
present output sample depends on present input, past input samples and output samples.
The impulse response h(n) for a realizable filter is h(n) = 0 for n ≤ 0 and for stability it must satisfy
the condition ∞ 𝐧=𝟎 𝐡(𝐧) < ∞.
𝐌
∞ −n 𝐛𝐤 𝐳 −𝐤
IIR digital filters have the transfer function of the form H(z) = n=0 h(n)z = 𝟏+ 𝐤=𝟎
𝐍 −𝐤
𝐤=𝟏 𝐚𝐤 𝐳
The design of an IIR filter for given specifications is to find filter coefficient ak s and bk s of above eqn.
FREQUENCY SELECTIVE FILTERS
A filter, which rejects unwanted frequencies from the input signal and allows the desired frequencies.
The range of frequencies of signal that are passed through the filter is called pass band.
The range of frequencies that are blocked is called stop band.
The filters are of different types,
1) Low Pass Filter 2) High Pass Filter 3) Band Pass Filter 4) Band Reject Filter
1) LOW PASS FILTER: The magnitude response of
an ideal low pass filter allows low frequencies in the
pass band 0 < Ω < ΩC to pass, whereas the higher
frequencies in the stop band Ω > ΩC are blocked.
The frequency ΩC between the two bands is the
cutoff frequency, where magnitude H(jΩ) = 1 2.
In practice it is impossible to obtain the ideal
response. The practical response of a low pass filter is shown in solid line in fig.
2) HIGH PASS FILTER: The high pass
filter allows high frequencies above Ω > ΩC
and rejects the frequencies between Ω = 0
and Ω = ΩC. The magnitude response of an
ideal & practical HPF is shown.
BAND PASS FILTER: It allows only a
band of frequencies Ω1 to Ω2 to pass and
stops all other frequencies. The ideal and
practical responses of BPF are shown in fig.
3) BAND REJECT FILTER: It rejects all the
frequencies between Ω1 and Ω2 and allows
remaining frequencies. The magnitude response of
an ideal and practical filter in shown in fig.
Design Of Digital Filters From Analog Filters
The common technique used for designing IIR
digital filters known as indirect method, involves
first designing an analog prototype filter and then transforming the prototype to a digital filter.
For the given specification, the derivation of the digital filter transfer function requires the three steps.
Step-1 Map the desired digital filter specifications into those for an equivalent analog filter.
Step-2 Derive the analog transfer function for the analog prototype.
Step-3 Transform the transfer function of analog prototype to equivalent digital filter transfer function.
<FAST FOURIER TRANSFORM (FFT)> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 604] [Page 5.13]
DIGITAL VERSUS ANALOG FILTERS
SN ANALOG FILTER DIGITAL FILTER
Analog filter process analog inputs and A digital filter processes and generates
1)
generates analog output digital data.
Analog filters are constructed from active or A digital filter consists of elements like
2)
passive electronic components adder, multiplies and delay unit.
Analog filter is described by a differential Digital filter is described by a difference
3)
equation. equation.
The frequency response of an analog filter can The frequency response can be changed by
4)
be modified by changing the components. changing the filter co-efficients.
<FAST FOURIER TRANSFORM (FFT)> Prepared by Er. PARAMANANDA GOUDA, Dept of ETC, UCP Engg School
A Hand Note on DIGITAL SIGNAL PROCESSING [ETT 604] [Page 5.14]
−𝜽(𝝎) −𝒅𝜽(𝝎)
We define the Phase delay and Group delay of a filter as, τp = and τg =
𝝎 𝒅𝝎
For FIR filters with linear phase we can define θ(ω) = -αω; -π ≤ ω ≤ π
Where α is a constant phase delay in samples. Substituting θ(ω) in above equation, we have τp = τg = α,
Which means that α is independent of frequency. We can write, 𝐍−𝟏 𝐧=𝟎 𝐡(𝐧)𝐞
−𝐣𝛚𝐧
= ± 𝐇(𝐞𝐣𝛚 ) 𝐞𝐣𝛉(𝛚)
Which gives us, N−1 jω
n=0 h(n) cos ωn = ± H(e ) cos θ(ω) & −
N−1
n=0 h(n) sin ωn =± H(ejω ) sin θ(ω)
By taking ratio of above two equations, we obtain
𝐍−𝟏
𝐧=𝟎 𝐡(𝐧) 𝐬𝐢𝐧 𝛚𝐧 𝐬𝐢𝐧 𝛂𝛚
𝐍−𝟏 𝐡(𝐧) 𝐜𝐨𝐬 𝛚𝐧 = 𝐜𝐨𝐬 𝛂𝛚 θ(ω) = -αω]
𝐧=𝟎
𝐍−𝟏
After simplifying this equation, we have 𝐧=𝟎 𝐡(𝐧) 𝐬𝐢𝐧(𝛂 − 𝐧)𝛚 = 0.
𝑵−𝟏
The above equation will be zero when h(n) = h(N – 1 - n) and α= 𝟐
𝑵−𝟏
FIR filters have constant phase & group delays when impulse response is symmetrical about α = .
𝟐
QUESTION AND ANSWERS:
1. What are the difference types of filters based on impulse response?
Based on impulse response, filters are of two types. 1. IIR Filter 2. FIR Filter
The IIR filters are recursive type, whereby the present output sample depends on the present input, past
input samples and output samples. The FIR filters are of non-recursive type whereby the present output
sample depends on the present input sample and previous input samples.
2. What are the difference types of filters based on frequency response?
The filters can be classified based on frequency response.
They are 1. Low Pass Filter 2. High Pass Filter 3. Band Pass Filter 4. Band Reject Filter
3. What is the most general form of IIR filter?
𝐌
𝐛𝐤 𝐳 −𝐤
The most general form of IIR filter can be written as, H(z) = 𝟏+ 𝐤=𝟎
𝐍 −𝐤
. Where at least one of the
𝐤=𝟏 𝐚𝐤 𝐳
ak is nonzero and all the roots of the denominator are not cancelled by the roots of the numerator.
4. Distinguish between FIR and IIR filters.
SN FIR FILTER IIR FILTER
It can be easily designed to have perfectly linear
1) These filters do not have linear phase
phase.
FIR filters can be realized recursively & non-
2) IIR filters are easily realized recursively
recursively.
Greater flexibility to control shape of their Less flexibility, usually limited to
3)
magnitude response. specific kind of filters.
Errors due to round off noise are less severe in The round off noises in IIR filters is
4)
FIR filters, mainly because feedback is not used. more
5. What are the techniques of designing FIR filters?
There are three well-known methods for designing FIR filters with linear phase.
These are 1. Windows method 2. Frequency sampling method 3. Optimal or minimal design.
6. What is the reason that FIR filter is always stable?
FIR filter is always stable because all its poles are at the origin.
7. What are the properties of FIR filter?
1) FIR filter is always stable
2) A realizable filter can always be obtained
3) FIR filter has a linear phase response.
Collected By:-
Er. Paramananda Gouda
(Dept. of ETC, UCP Engg School)
Previous Year Semester Question of DIGITAL SIGNAL PROCESSING [6TH ETC - ETT 603] P a g e | 2 |
Collected By:-
Er. Paramananda Gouda
(Dept. of ETC, UCP Engg School)
Previous Year Semester Question of DIGITAL SIGNAL PROCESSING [6TH ETC - ETT 603] P a g e | 6 |
Collected By:-
Er. Paramananda Gouda
(Dept. of ETC, UCP Engg School)
Previous Year Semester Question of DIGITAL SIGNAL PROCESSING [6TH ETC - ETT 603] P a g e | 7 |
6. (a) Draw the basic butterfly diagram for DIF – FFT. [2]
(b) Differentiate between linear and circular convolution. [5]
(c) Compute the z-transform and ROC of x (n) = 2n u (n) [7]
Collected By:-
Er. Paramananda Gouda
(Dept. of ETC, UCP Engg School)
Previous Year Semester Question of DIGITAL SIGNAL PROCESSING [6TH ETC - ETT 603] P a g e | 8 |
4. (a) What is the need of signal processing and give any two applications. [2]
(b) Find the step response of the following differential equation:
y (n) - 5y (n-1) + 6y (n-2) = x(n) [5]
𝒛 (𝟏− 𝒆−𝑻 )
(c) Compute the inverse z transform of x (z) = [7]
(𝒛 − 𝟏)(𝒛 − 𝒆−𝑻 )
5. (a) Draw the basic butterfly diagram for DIT – FFT and DIF-FFT. [2]
(b) Find the z transform and ROC of x (n) = (0.4)n u(n) + (0.3)n u(n-4) [5]
(c) Compute a 4 point DFT of the sequence x (n) = {0, 2, 4, 6} [7]
6. (a) Name number of complex multiplications & additions required to compute N point DFT. [2]
(b) Find the circular convolution of two finite duration sequence
x1(n) = {1, 2, 3, 4} & x1(n) = {4, 3, 2, 1} [6]
(c) Compute the four point DFT of the sequence x(n) = {1, 1, 1, 1} [8]
7. (a) Define twiddle factor. [2]
(b) State the difference between analog filter and digital filter. [6]
(c) Determine the DFT of the sequence x(n) = {1, 2, 1, 1, 0, 1, 1, 1} using DIT-FFT algorithm. [8]
Collected By:-
Er. Paramananda Gouda
(Dept. of ETC, UCP Engg School)
Previous Year Semester Question of DIGITAL SIGNAL PROCESSING [6TH ETC - ETT 603] P a g e | 10 |
4. Express the signal x(n) = {1, -2, 3, 0, 1, -5, 2, 1} in even and odd signal. [10]
𝟓
5. Find out the impulse response of the system y(n) - y(n-1) + y(n-2) = x(n)- x(n-1) [10]
𝟐
2
6. (a) Determine the linearity of the system described by the input output equation y(n) = x(n ) [5]
(b) Differentiate between continuous valued and discrete valued signals. [5]
7. Describe DFT and FFT algorithm and write the computational formula. [10]
Collected By:-
Er. Paramananda Gouda
(Dept. of ETC, UCP Engg School)
Previous Year Semester Question of DIGITAL SIGNAL PROCESSING [6TH ETC - ETT 603] P a g e | 13 |