A Art Story Essay

927 WordsApr 13, 20154 Pages
To evaluate FFT(a0,a1,a2,a3,a4,a5,a6,a7) we apply recursively FFT and obtain FFT( a0,a2,a4,a6) and FFT(a1,a3,a5,a7). Proceeding further with recursion, we obtain FFT(a0,a4) and FFT(a2,a6) as well as FFT(a1,a5) and FFT(a3,a7). Thus, from bottom up, FFT(a0,a1,a2,a3,a4,a5,a6,a7) is obtained using permutation (a0,a4,a2,a6,a1,a5,a7) as the leaves of the recursion tree of the original input sequence. Given any input (a0,a1,a2,…a2 n -1) describe the permutation of the leaves of the recursion tree. (Hint: write indices in binary and see what the relationship is of the bits of the i th element of the original sequence and the i th element of the resulting permutation of elements as they appear on the leaves on the recursion tree.) 3) Timing Problem in VLSI chips. Consider a complete balanced binary tree with n = 2k leaves. Each edge has an associate positive number that we call the length of this edge (see picture below). The distance from the root to a leaf is the sum of the lengths of all edges from the root to this leaf. The root sends a clock signal and the signal propagates along the edges and reaches the leaf in time proportional to the distance from the root to this leaf. Design an algorithm which increases the lengths of some of the edges in the tree in a way that ensures that the signal reaches all the leafs in the same time while the sum of the lengths of all edges is minimal. (For example, on the picture below if the tree A is transformed into trees B and C all leaves of B and C are on the distance 5 from the root and thus receive the clock signal in the same time, but the sum of lengths of edges in C is 17 while sum of lengths in B is only 15.) 4) Along the long, straight road from Loololong to Goolagong houses are scattered quite sparsely, sometimes with long gaps between two consecutive