Linear convolution:
If x(n) is a sequence of L number of samples and h(n) with M number of samples, after convolution y(n) will have N=L+M-1 samples.
It can be used to find the response of a linear filter.
Zero padding is not necessary to find the response of a linear filter.
Circular convolution:
If x(n) is a sequence of L number of samples and h(n) with M samples, after convolution y(n) will have N=max(L,M) samples.
It cannot be used to find the response of a filter.
Zero padding is necessary to find the response of a filter.
There are three types of arithmetic used in digital systems. They are fixed point arithmetic, floating point ,block floating point arithmetic.
Rounding a number to b bits is accomplished by choosing a rounded result as the b bit number closest number being unrounded.
A signal x (n) is periodic in period N, if x (n+N) =x (n) for all n. If a signal does not satisfy this equation, the signal is called aperiodic signal.
Unit sample sequence (unit impulse)
δ (n)= {1 n=0
0 Otherwise
Unit step signal
U (n) ={ 1 n>=0
0 Otherwise
Unit ramp signal
Ur(n)={n for n>=0
0 Otherwise
Exponential signal
x (n)=an where a is real
x(n)-Real signal
Truncation and Rounding
The number of multiplications and additions required to compute N point DFT using radix-2 FFT are N log2 N and N/2 log2 N respectively,.
IIR filters are of recursive type whereby the present o/p sample depends on present i/p, past i/p samples and o/p samples. The design of IIR filter is realizable and stable.
The impulse response h(n) for a realizable filter is
h(n)=0 for n≤0
The bilinear trformation is a mapping that trforms the left half of S-plane into the unit circle in the Z-plane only once, thus avoiding aliasing of frequency components.
The mapping from the S-plane to the Z-plane is in bilinear trformation is
S=2/T(1-Z-1/1+Z-1)
Advantages:
Disadvantage:
The two important procedures for digitizing the trfer function of an analog filter are:
A system is called time invariant if its output , input characteristics dos not change with time.
e.g.y(n)=x(n)+x(n-1)
A system is called time variant if its input, output characteristics changes with time.
e.g.y(n)=x(-n).
Truncation is a process of discarding all bits less significant than LSB that is retained
A discrete time system is called static or memory less if its output at any instant n depends almost on the input sample at the same time but not on past and future samples of the input.
e.g. y(n) =a x (n)
In anyother case the system is said to be dynamic and to have memory.
e.g. (n) =x (n)+3 x(n-1)
Once the butterfly operation is performed on a pair of complex numbers (a,b) to produce (A,B), there is no need to save the input pair. We can store the result (A,B) in the same locations as (a,b). Since the same storage locations are used troughout the computation we say that the computations are done in place.
The product quantization errors arise at the out put of the multiplier. Multiplication of a b bit data with a b bit coefficient results a product having 2b bits. Since a b bit register is used the multiplier output will be rounded or truncated to b bits which produces the error.
A system is said to be stable if we get bounded output for bounded input.
In fixed point number the position of a binary point is fixed. The bit to the right represent the fractional part and those to the left is integer part.
In frequency sampling method the desired magnitude response is sampled and a linear phase response is specified .The samples of desired frequency response are identified as DFT coefficients. The filter coefficients are then determined as the IDFT of this set of samples.
There are three well known methods for designing FIR filters with linear phase .They are (1.)Window method (2.)Frequency sampling method (3.)Optimal or minimax design.
The Fast Fourier Trform is an algorithm used to compute the DFT. It makes use of the symmetry and periodicity properties of twiddle factor to effectively reduce the DFT computation time.It is based on the fundamental principle of decomposing the computation of DFT of a sequence of length N into successively smaller DFTs.
Depending on the negative numbers are represented there are three forms of fixed point arithmetic. They are sign magnitude,1’s complement,2’s complement
In this method the data sequence is divided into N point sections xi(n).Each section contains the last M-1 data points of the previous section followed by L new data points to form a data sequence of length N=L+M-1.In circular convolution of xi(n) with h(n) the first M-1 points will not agree with the linear convolution of xi(n) and h(n) because of aliasing, the remaining points will agree with linear convolution. Hence we discard the first (M-1) points of filtered section xi(n) N h(n). This process is repeated for all sections and the filtered sections are abutted together.
The effect of the non-linear compression at high frequencies can be compensated. When the desired magnitude response is piece-wise constant over frequency, this compression can be compensated by introducing a suitable pre-scaling, or pre-warping the critical frequencies by using the formula.
It is a popular form of the FFT algorithm. In this the output sequence X(k) is divided into smaller and smaller sub-sequences , that is why the name Decimation In Frequency.
FIR filter:
IIR filter:
Based on impulse response the filters are of two types:
The IIR filters are of 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.
Let the sequence x(n) has a length L. If we want to find the N-point DFT(N>L) of the sequence x(n), we have to add (N-L) zeros to the sequence x(n). This is known as zero padding.
The uses of zero padding are:
Decimation-In-Time algorithm is used to calculate the DFT of a N point sequence. The idea is to break the N point sequence into two sequences, the DFTs of which can be combined to give the DFt of the
original N point sequence.This algorithm is called DIT because the sequence x(n) is often splitted into smaller sub- sequences.
Overlap-save method:
In this method the size of the input data block is N=L+M-1
Each data block consists of the last M-1 data points of the previous data block followed by L new data points
In each output block M-1 points are corrupted due to aliasing as circular convolution is employed
To form the output sequence the first
M-1 data points are discarded in each output block and the remaining data are fitted together
Overlap-add method:
In this method the size of the input data block is L
Each data block is L points and we append M-1 zeros to compute N point DFT
In this no corruption due to aliasing as linear convolution is performed using circular convolution
To form the output sequence the last
M-1 points from each output block is added to the first M-1 points of the succeeding block
In this method the size of the input data block xi(n) is L. To each data block we append M-1 zeros and perform N point circular convolution of xi(n) and h(n). Since each data block is terminated with M-1 zeros the last M-1 points from each output block must be overlapped and added to first M-1 points of the succeeding blocks.This method is called overlap-add method.
A discrete or an algorithm that performs some prescribed operation on a discrete time signal is called discrete time system.
A real value signal x (n) is called symmetric (even) if x (-n) =x (n). On the other hand the signal is called antisymmetric (odd) if x (-n) =x (n).
The filter coefficients are computed to infinite precision in theory. But in digital computation the filter coefficients are represented in binary and are stored in registers. If a b bit register is used the filter coefficients must be rounded or truncated to b bits ,which produces an error.
The cascade form realization is preferred when complex zeros with absolute magnitude is less than one.
The trpose of a structure is defined by the following operations:
According to trposition theorem if we reverse the directions of all branch trmittance and interchange the input and output in the flowgraph, the system function remains unchanged.
If the data sequence x(n) is of long duration it is very difficult to obtain the output sequence y(n) due to limited memory of a digital computer. Therefore, the data sequence is divided up into smaller sections. These sections are processed separately one at a time and controlled later to get the output.
The FFT algorithm is most efficient in calculating N point DFT. If the number of output points N can be expressed as a power of 2 that is N=2M, where M is an integer, then this algorithm is known as radix-2 algorithm.
Speech processing ,Image processing, Radar signal processing.
A discrete time signal x (n) is a function of an independent variable that is an integer. a discrete time signal is not defined at instant between two successive samples.
The applications of FFT algorithm includes:
In floating point form the positive number is represented as F =2CM,where is mantissa, is a fraction such that1/2<M<1and C the exponent can be either positive or negative.