UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN Department of Electrical and Computer Engineering
ECE 310 Digital Signal Processing
Homework 10
Profs. Kamalabadi, Katselis, Liang
Copyright By PowCoder代写 加微信 powcoder
1. Complete the following signal flow diagram (butterfly structure) of a 4-pt, radix-2, decimation-in- time FFT algorithm. Specify all the connection weights and determine the indexes (a, b, c, and d) of the input signal sequence.
Recall that a radix-2 decimation-in-time FFT first splits the signal into its even and odd samples. We want to calculate the DFT of the even samples, x0 and x2, and the odd samples, x1 and x3. Therefore,
X[k]=x[n]e−j2πnk =x +x e−j2πk +x e−j2π2k +x e−j2π3k
= x0 + x1(−j)k + x2(−1)k + x3(jk).
We can evaluate this for each 0 ≤ k ≤ 3 to find
X0 = x0 + x1 + x2 + x3,
X1 = x0 − jx1 − x2 + jx3, X2 = x0 − x1 + x2 − x3, X3 = x0 + jx1 − x2 − jx3.
1 −j2π This can be rearranged to show (given W4 = e 4
X0 =(x0 +x2)+(x1 +x3),
X1 =(x0 −x2)+(x1 −x3)W41, X2 =(x0 +x2)−(x1 +x3),
X3 =(x0 −x2)−(x1 −x3)W41.
Due: 5 pm, April 8, 2022
a=0, b=2, c=1, d=3. We can find the butterfly diagram by using the DFT definition:
We can define two sub-sequences, {A0, A1} = {(x0 + x2), (x0 − x2)} and {B0, B1} = {(x1 + x3), (x1 − x3)} such that
X0 = A0 + B0,
X 1 = A 1 + B 1 W 41 , X2 = A0 − B0,
X 3 = A 1 − B 1 W 41 .
This is how we can empirically derive the two-step process for completing the 4-point FFT. We notice the symmetry in the formation of this DFT in that we can construct A and B as differences and sums of our input signal first, then add and subtract these for the final result. We can summarize this in a butterfly diagram as follows: first, we can use two two-point DFT’s to construct A and B:
𝑊0 = 1 𝑥4𝐴
𝑊0 = 1 𝑥4𝐵
These two sub-butterflies can be read left to right along a particular path. Where arrows meet, their quantities are summed; when an arrow has a number next to it, that is a multiplier; when there is nothing next to an arrow, it has a multiplier of 1. In this case, we can read from the first butterfly that
A0 =x0 +W40x2 =x0 +x2, A1 =x0 +(W40x2)(−1)=x0 −x2,
confirming our analytic definition from above. Now that we have calculated A and B, we can use (2) to calculate each X component by linking the two butterfly diagrams in another stage, shown in the figure below.
Notice that this can be derived with a set of general rules rather than by inspection from the DFT definition. The straight branches will be 1 in the upper half of each stage, the diagonal branches coming from the top half all take the value 1, the mth diagonal branch going up takes the value
Wm−1, and the mth straight branch in the bottom half takes the value −Wm−1. NN
𝑥1 𝐴01 𝑋 00
𝑊0=1 −1 𝐵1 𝑊1=−𝑗
Notice that the computation of A and B each requires 2 additions for a total of 4; then, the computa- tion of X requires 2 multiplications and 4 additions, for a total of 8 additions and 2 multiplications. Doing the direct DFT method from (1) requires 12 additions and 4 multiplications. Clearly, for a system who can do a certain number of multiplications/additions every unit of time (like most mod- ern computers), this special way of computing the DFT is faster than the brute-force method. That is why this method, graphically demonstrated with the butterfly diagram, is called the fast fourier transform.
2. The diagram below represents a part of the computation in a 16-point decimation-in-time radix-2 FFT. Indicate the values of the three requested branch weights a, b and c.
This can be done by first recalling the rules of the butterfly diagram weights:
(a) Branches going across in the top half are always 1.
(b) Branches going diagonally down from the top half are always 1.
(c) Branches going diagonally up from the bottom half are WNm, where N is the current DFT size, and m is the index of the output node in the upper half the branch is heading towards.
(d) Branches going straight across in the bottom half are −WNm, where WNm is the value of the corresponding diagonal branch leaving the node.
We can apply these rules to each requested value. Note that this figure corresponds to two eight-point DFT’s from the left column to the middle and one 16-point DFT from the middle to the right. We can split the left hand side down its middle to reveal the first and second eight-point DFT’s. See the figure below.
Upon doing this, we can identify that c is the weight of the branch in the bottom half of the lower eight-point DFT, and it points to the third output (m = 3 − 1 = 2, as we count starting from zero) of the eight-point DFT. As such, we can conclude from rule (c) that
c=W3−1 =W2 =e−j2π2 =e−jπ =−j. 8882
We can identify a as a horizontal branch in the bottom half of the 16-point DFT, whose corresponding diagonal points to the zeroth output (the arrow pointing to the top right, m = 0). As such, we can conclude
a=−W0 =−1. 16
Finally, since b represents the weight of the seventh diagonal branch in the bottom half of the 16-point DFT (the diagonal branch corresponding to output m = 7 − 1 = 6), we can conclude from (c) that
7−1 6 3 −j2π3 −j3π −1−j b=W16=W16=W8=e8 =e4=√2.
8-point #1
8-point #2
𝑚=0 𝑚=1 𝑚=2
𝑚=6 𝑚=7 𝑚=8
𝑚=9 𝑚 = 10 𝑚 = 11
𝑚 = 12 𝑚 = 13 𝑚 = 14 𝑚 = 15
3. Consider the two finite-length sequences:
x = {1,2,3,4,5}, and h = {1,1}
(a) Compute the linear convolution x ∗ h. (b) Compute the circular convolution x ⊛5 h.
(c) What is the smallest value of N so that N-point circular convolution is equal to the linear convolution?
(a) We can compute the linear convolution by noting that h[n] = δ[n] + δ[n − 1], so
x[n] ∗ h[n] = x[n] ∗ (δ[n] + δ[n − 1]) = x[n] ∗ δ[n] + x[n] ∗ δ[n − 1] = x[n] + x[n − 1]. This formula can be evaluated for each n given the definition of x[n], which results in
x[n] ∗ h[n] = {1, 2, 3, 4, 5, 0} + {0, 1, 2, 3, 4, 5} = {1, 3, 5, 7, 9, 5}. ↑↑↑
This can be solved more robustly given the definition of convolution, x[n]∗h[n] = ∞l=−∞ x[l]h[n−l] = ∞l=−∞ x[n − l]h[l].
(b) We can compute the circular convolution via its definition, y[n] = (x⊛5h)[n] = N−1 x[m]hzp[⟨n− l=0
l⟩N ], which can be done only after zero-padding h[n] to length N = 5 to match that of x[n]: {hzp[n]}4n=0 ={h[0],h[1],0,0,0}={1,1,0,0,0}.
We can do the convolution index-by-index as follows:
y[0] = x[l]hzp[⟨0 − l⟩5] = x[0]hzp[0] + x[1]hzp[4] + x[2]hzp[3] + x[3]hzp[2] + x[4]hzp[1] = 6,
y[1] = x[l]hzp[⟨1 − l⟩5] = x[0]hzp[1] + x[1]hzp[0] + x[2]hzp[4] + x[3]hzp[3] + x[4]hzp[2] = 3, l=0
y[2] = x[l]hzp[⟨2 − l⟩5] = x[0]hzp[2] + x[1]hzp[1] + x[2]hzp[0] + x[3]hzp[4] + x[4]hzp[3] = 5,
y[3] = x[l]hzp[⟨3 − l⟩5] = x[0]hzp[3] + x[1]hzp[2] + x[2]hzp[1] + x[3]hzp[0] + x[4]hzp[4] = 7, l=0
y[4] = x[l]hzp[⟨4 − l⟩5] = x[0]hzp[4] + x[1]hzp[3] + x[2]hzp[2] + x[3]hzp[1] + x[4]hzp[0] = 9.
l=0 As such,
{y[n]}4n=0 ={6,3,5,7,9}. This can be done similarly with the tabular method:
x[l] 12345n y[n]
hzp[⟨0−l⟩5] 1 0 0 0 1 0 1+5=6 hzp[⟨1−l⟩5] 1 1 0 0 0 1 1+2=3 hzp[⟨2−l⟩5] 0 1 1 0 0 2 2+3=5 hzp[⟨3−l⟩5] 0 0 1 1 0 3 3+4=7 hzp[⟨4−l⟩5] 0 0 0 1 1 4 4+5=9
to retrieve the same result.
(c) The lowest value of N such that the circular and linear convolution of two sequences x and h of length L = 5 and M = 2, respectively, should be N = 5+2−1 = 6. This means we will have to pad x and h each to length 6 to have their convolution equal the linear convolution. Notice that the two are not equal when padded to N = 5. When we try N = 6,
xzp[l] 123450n y[n]
hzp[⟨0−l⟩6] 1 0 0 0 0 1 0 1+0=1 hzp[⟨1−l⟩6] 1 1 0 0 0 0 1 1+2=3 hzp[⟨2−l⟩6] 0 1 1 0 0 0 2 2+3=5 hzp[⟨3−l⟩6] 0 0 1 1 0 0 3 3+4=7 hzp[⟨4−l⟩6] 0 0 0 1 1 0 4 4+5=9 hzp[⟨5−l⟩6] 0 0 0 0 1 1 5 5+0=5
confirming the fact that x ∗ h = xzp ⊛6 hzp. Convince yourself that this remains true for N > 6. 4. Determine zn, the cyclic convolution of xn and yn for the following cases:
(a) {xn}5n=0 = {1,2,3,4,5,6} and {yn}5n=0 = {1,0,0,1,0,0}.
(b) {xn}8n=0 = {1,2,3,4,5,6,0,0,0} and {yn}8n=0 = {1,0,0,1,0,0,0,0,0}.
(a) This can be done most efficiently via the tabular method. Note that no zero padding has to occur because this cyclic convolution is between two equal-length sequences:
x[l] 123456n z[n]
y[⟨0−l⟩6] 1 0 0 1 0 0 0 1+4=5 y[⟨1−l⟩6] 0 1 0 0 1 0 1 2+5=7 y[⟨2−l⟩6] 0 0 1 0 0 1 2 3+6=9 y[⟨3−l⟩6] 1 0 0 1 0 0 3 4+1=5 y[⟨4−l⟩6] 0 1 0 0 1 0 4 5+2=7 y[⟨5−l⟩6] 0 0 1 0 0 1 5 6+3=9
{z[n]}5n=0 ={5,7,9,5,7,9}.
(b) This can be done most efficiently via the tabular method. Note that no zero padding has to
occur because this cyclic convolution is between two equal-length sequences:
l 012345678
x[l] 123456000n z[n]
y[⟨0−l⟩9] 1 0 0 0 0 0 1 0 0 0 1+0=1 y[⟨1−l⟩9] 0 1 0 0 0 0 0 1 0 1 2+0=2 y[⟨2−l⟩9] 0 0 1 0 0 0 0 0 1 2 3+0=3 y[⟨3−l⟩9] 1 0 0 1 0 0 0 0 0 3 4+1=5 y[⟨4−l⟩9] 0 1 0 0 1 0 0 0 0 4 5+2=7 y[⟨5−l⟩9] 0 0 1 0 0 1 0 0 0 5 6+3=9 y[⟨6−l⟩9] 0 0 0 1 0 0 1 0 0 6 0+4=4 y[⟨7−l⟩9] 0 0 0 0 1 0 0 1 0 7 0+5=5 y[⟨8−l⟩9] 0 0 0 0 0 1 0 0 1 8 0+6=6
5. The following linear convolution
is to be evaluated using the DFT method. Namely,
{z[n]}5n=0 ={1,2,3,5,7,9,4,5,6}. {x }46 ∗{h }32
{x }46 ∗ {h }32 = DFT−1{DFT{x } · DFT{h }} nn=0nn=0 nn
(a) Determine the minimum number of zeros should be padded to {xn} and {hn}, respectively, before the DFTs are applied.
(b) If the DFTs are to be calculated with a radix-2 FFT algorithm, how many zeros should now be padded to {xn} and {hn}, respectively.
(c) In (a), can the zeros be padded at the beginning (instead of the end) of the sequences? If so, how do you obtain {xn}46 ∗ {hn}32 from DFT−1{DFT{xn} · DFT{hn}}?
(a) Notice that this process is effectively computing the circular convolution of x and h; by the DFT property that
xzp,e ⊛N hzp,e ↔ Xzp,e[k]Hzp,e[k] = DFT{xn} · DFT{hn}
where xzp,e[n], hzp,e[n] are x[n] and h[n] padded on their tail ends to length N = L + M − 1, and Xzp,e[k], Hzp,e[k] are their DFT’s. See (7.152) from the text, and read over section 7.5 for more information. Effectively, the products of the DFT’s of x and h is the DFT of the circular convolution of xzp,e and hzp,e. We know that if we zero-pad to length N = L + M − 1, then this this circular convolution equal to the linear convolution of x and h. If we zero-pad according to that requirement, then the IDFT of the DFT product will be the linear convolution. Using this formula, we must zero pad to length N = L + M − 1 = 47 + 33 − 1 = 79, 32 zeros to x and 46 to h.
(b) Recall that radix-2 FFT algorithms require signals to be of length equal to a power of 2. With this requirement and that of above (N ≥ 79 for circular conv. = linear conv.), we can conclude that we must zero-pad to the smallest power of 2 above 79, which is N = 128. We will need to pad 81 zeros to x and 95 zeros to h.
(c) Yes. This can be seen by noting that xzp,e[n] (x[n] zero padded at the end) and xzp,b[n] (x[n] zero padded on the beginning), as well as hzp,e[n] and hzp,b[n], can be related as follows:
xzp,b[n] = xzp,e[⟨n − 81⟩128], hzp,b[n] = hzp,e[⟨n − 95⟩128].
Convince yourself of this by picturing xzp,b[n] and xzp,e[n]; notice how if we circularly shift xzp,e[n] by a number equal to the number of padded zeros (81 in this case), the numbers slide to the right by 81 samples and the tailing 81 zeros come to the front. This forms exactly what we call xzp,b[n], leading to the above equivalence. By the circular shift property, the front-padded DFT’s can be expressed
[k] = e−j 2π 81X [k], 128 zp,e
[k] = e−j 2π 95H [k]. 128 zp,e
Notice that
X [k]H [k]=e−j 2π 81X [k]e−j 2π 95H [k]=e−j 2π 176X [k]H [k]=e−j 2π 48X [k]H [k].
zp,b zp,b 128 zp,e 128 zp,b 128 zp,e zp,e 128 zp,e zp,e
If we define z[n] = x[n] ∗ h[n], which in (b) we showed is equal to z[n] = xzp,e[n] ∗ hzp,e[n], and define z ̃[n] = xzp,b[n] ∗ hzp,b[n] as the output resulting in front-zero padding, we can use the circular shift property to show
Z ̃ [k]=X [k]H [k]=e−j 2π 48X [k]H [k]=e−j 2π 48Z [k] =⇒ z ̃[n]=z[⟨n−48⟩ ]. zp,b zp,b zp,b 128 zp,e zp,e 128 zp,e 128
Thus, if we use front-padded sequences, the result will be the same as if we used back-padded sequences, only circularly shifted to the right by 48. To recover the correct sequence, thus, we must circularly shift this output to the left by 48.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com