Let a = [4, 3, 2, 3, 3, 1, 1, 2] and b = [1, 2, 2, 4, 3, 2, 3, 1]…

Question Answered step-by-step Let a = [4, 3, 2, 3, 3, 1, 1, 2] and b = [1, 2, 2, 4, 3, 2, 3, 1]… Let a = [4, 3, 2, 3, 3, 1, 1, 2] and b = [1, 2, 2, 4, 3, 2, 3, 1]be two sequences and FFT(a)=[2, 0, 0, 15, 1, 10, 8, 13] andFFT(b)=[1, 16, 12, 8, 0, 4, 3, 13] where FFT operations are done in commutativering modulo 17. Note that 2 is the 8-th root of unity in this ring and 8?1 =15 ? ?2 mod 17 in this ring.(a) Find the inverse FFT of the sequence given by FFT(a) * FFT(b) where* is element-wise multiplication of the two FFT sequences. Show all thecomputational steps in this ring using butterfly network (10 points).Hint: FFT(a) can be written as [2, 0, 0, ?2, 1, ?7, 8, ?4] and FFT(b) canbe written as [1, ?1, ?5, 8, 0, 4, 3, ?4]. 2?1 = 9 andpowers of this root are 1, 9, 13(?4), 15(?2), 16(?1), 8(?9), 4, 2.(b) Positive wrapped convolutionPc of 2 sequences a and b is given by ci =ij=0 aj bi?j + Pn?1j=i+1 aj bn+i?j . Show that the result obtained in step (a) isthe positive wrapped convolution of the two sequences given in the prob-lem.(5 points) Computer Science Engineering & Technology Java Programming CS 610 Share QuestionEmailCopy link Comments (0)