C13-DSP

Homework1.ShowthatthedirectcomputationoftheN-pointDFTofalength-Nsequencerequires4N^2realmultiplicationsand(4N−2)Nrealadditions.InordertocomputetheDFT(orInverseDFT)ofalength-Nsequence,weneed:N^2complexmultiplicationsandN(N-1)complexadditions.Andcomplexmultiplications(a+bi)*(c+di)needfourmultiplicationssothedirectcomputationoftheN-pointDFTofalength-Nsequencerequires4N^2realmultiplications.Andcomplexmultiplications(a+bi)*(c+di)needtwomultiplicationssothedirectcomputationoftheN-pointDFTofalength-Nsequencerequires2N^2-2N+2N^2realmultiplications.2.IfMDFTsamplesoftheN-pointDFTofalength-NsequencearerequiredwithM≤N,whatisthesmallestvalueofMforwhichtheN-pointradix-2FFTalgorithmiscomputationallymoreefficientthanadirectcomputationoftheMDFTsamples?WhatarethevaluesofMforthefollowingvaluesofN:N=32,N=64andN=128.N=32.2M/log2N1,M=2.5,soM=3—32;N=64.2M/log2N1,M=3,soM=3—64;N=128.2M/log2N1,M=3.5,soM=4—128;3.A256-pointDFTofalength-197sequencex[n]istobecomputed.–Howmanyzero-valuedsamplesshouldbeappendedtox[n]priortothecomputationoftheDFT?256-197=59–WhatarethetotalnumberofcomplexmultiplicationsandadditionsneededforthedirectevaluationofallDFTsamples?N=197,thedirectcomputationoftheN-pointDFTofalength-197sequencerequires38809complexmultiplicationsand38612complexadditions.–WhatarethetotalnumberofcomplexmultiplicationsandadditionsneededifaCooley-TukeytypeFFTisusedtocomputetheDFTsamples?(Nlog2N)/2--complexmultiplications--1024Nlog2N--complexadditions—20484.UsingtheFFTalgorithm,computethe8-pointDFTofthe8-pointsignalx=[4,−3,2,0,−1,−2,3,1].X[n]=[4,5-W81-W82-W83,-8,5-W81+W82+W83,12,5+W81-W82+W83,4,5+W81+W82-W83]WhileresultfromMATLAB:X[n]=[4.0000+0.0000i,5.0000+2.4142i,-2.0000+6.0000i,5.0000+0.4142i,12.0000+0.0000i,5.0000-0.4142i,-2.0000-6.0000i,5.0000-2.4142i]