Beijing Dublin International College
EEEN3004J Digital Signal Processing
Spring 2020
Assignment 1
The Fast Fourier Transform

You have been assigned to a team for this assignment (See Appendix 1). You may divide the work
between team members any way you agree to, but a joint grade will be awarded except where one
team member fails to engage with the assignment.
You are to solve the problems given below, and to submit your report on Brightspace. See
Brightspace for the submission deadline. Late reports will be penalized according to UCD policy.


Problems:
Each team has been assigned a combination of two different fft algorithms. See Appendix 1 for the
assignments.
1. Write down how what length of DFT, N, your algorithm will be able to calculate.
• This can be easily found for most assignments, as simply the product of the two
radices, e.g. if you had a radix 3 stage followed by a radix 4 stage, you get =
3 × 4 = 12 points. That would split a 12-point DFT calculation into three 4-point
DFTs, which would then be carried out by means of a single stage of the radix 4
algorithm, something like this:




=




For another example, consider Fig. 7.2.4 in the notes. That figure shows a butterfly
diagram for a three-stage algorithm, each stage of which is a radix 2 decimation in
time algorithm.
2. Algebraic derivations of any algorithms must be presented.
• The general proofs are presented in the journal paper supplied to you, but you must
customize them for the specific number of points for your problem. Cooley and
Tukey derive an algorithm for any = 12. A radix 2 decimation-in-time algorithm
requires that 2 = 2 (this is the algorithm in the notes for the class). A radix 2
decimation-in-frequency algorithm requires that 1 = 2.
3. You are to draw a butterfly diagram for your entire algorithm.
4. A numerical example must be traced through the diagram. Verify using MATLAB that your
calculation is correct. The example signal should be derived from the digits of your student
numbers, e.g. Given a team with an = 12 problem, the last six digits of both member’s
student numbers should be used to give 12 integers which can then be tracked.

Appendix 1
Algorithms
1 Decimation-in-time radix 2
2 Decimation-in-time radix 3
3 Decimation-in-time radix 4
4
Decimation-in-frequency
radix 2
5
Decimation-in-frequency
radix 3
6
Decimation-in-frequency
radix 4

Teams and assignments
#
Member
1
Member
2
Member 3
(if
applicable)
Stage
1
Stage
2
1 14207109 Wang Xiaozhi 15206092 Deng Zida 1 3
2 15206094 Fan PengYuan 15206120 Liu Yunhe 2 4
3 15206134 Sun Tierui 15206137 Tian Xiaoyang 3 6
4 15206141 Wang Jiyu 15206154 Yang Weiqin 4 2
5 15206160 ZHAO ZHAO 15206164 Zhang Yupeng 5 4
6 15206168 Zheng Lingruo 15206304 Jiang Canhui 6 5
7 16206535 Bai Wenyuan 16206539 Cui Jinkai 1 3
8 16206553 Liu Ziyang 16206560 Wang Xiaoxin 2 5
9 16206564 Wu Siyuan 16206565 Wu Wenqi 3 6
10 16206570 Zhang Runmin 16206573 Zhang Zhelin 4 2
11 16206574 Zhu Lei 16206709 Yao Xiyao 5 6
12 16206716 Sun Yuqing 16206749 Ma Chi 6 5
13 16206798 Sun Yiran 16206802 Lv Jiaming 1 2
14 16206807 Wang Tong 16206810 Chen Qipei 2 4
15 16206812 Xiao Xiangyu 16206814 Zhang Mingyu 3 4
16 16206820 Lu Tianyang 16206823 Zhu Chensi 4 3
17 16206829 Ren Zeyu 16206832 Chen Yuqiao 5 6
18 16206835 Zhao Yuxin 16206868 Zhang Jinming 6 2
19 16206955 Feng Haoze 17205857 Gu Chenran 1 5
20 17205858 Li Xinyu 17205859 Han Jinfang 2 3
21 17205860 Wang Shuyi 17205861 Zhang Xiaofei 3 2
22 17205862 Zhu Ziming 17205865 Li Tianhao 4 5
23 17205866 Zhang Cenyue 17205867 Wang Zichen 5 4
24 17205868 Zhang Manlin 17205869 Wang Jianan 6 3
25 17205870 Shi Bo 17205871 Zhang Zichen 1 6
26 17205872 Zou Xueping 17205873 Qi Wanpeng 2 4
27 17205874 Sun Yifeng 17205877 Zhang Guangzhen 3 2
28 17205878 Hao Tingting 17205879 Li Nan 4 3
29 17205880 Wang Pinhua 17205881 Cao Yuan 5 2
30 17205882 Xu Jiaming 17205883 Yuan Xiling 6 5
31 17205884 Li Zichen 17205885 Zou Yang 1 4
32 17205886 Li Jiashu 17205888 Hu Jiayi 2 3
33 17205889 Bai Wanfeng 17205890 Li Xinghao 3 5
34 17205892 Fang Xiang 17205893 Guo Haoran 4 6
35 17205894 Chen Yixiao 17205897 Xu Zhikun 5 6
36 17205898 Han Sanyue 17205900 Zhu Yanxing 6 3
37 17205901 Yang Ruicui 17205904 Qiu Sitao 1 5
38 17205905 Li Yuan 17205906 Zhao Zijie 2 4
39 17205907 Zhang Youwu 17205908 Zhang Zhengyan 3 2
40 17205909 Wu Bochen 17205910 Zhang Xinyan 4 2
41 17205911 Yuan Xiaoran 17205912 Zhang Yuhui 5 6
42 17205913 Wang Zhengpu 17205914 Gong Chen 6 3
43 17205915 Wang Siqi 17205916 Wang Zhining 1 6
44 17205918 Bian Yuhan 17205919 Gao Yuzhe 2 4
45 17205920 Zhang Qiyue 17205921 Ma Siteng 3 2
46 17205922 Xu Yiruo 17205924 Lu Jiacheng 4 5
47 17205925 Zhao Yuting 17205926 Jia Zixuan 5 6
48 17205927 Xiao Shibang 17205928 Wang Weixing 6 4
49 17205930 Fang shicheng 17205931 Wang Ziyi 1 3
50 17205932 Cao Yunfeng 17205933 Wang Kaize 2 5
51 17205935 Zhang Aoran 17205950 Yang Feifan 3 6
52 17205952 Fu Ziyi 17205953 Zhang Ran 4 2
53 17205954 Qi Tianzhuo 17205955 Li Jinglin 17206238 Wu Haochang 5 4
54 17205956 Wu Ming Yang 17205957 Zhu Yucheng 6 3
55 17206005 Luo Yuzhao 17206012 Chen Hanming 1 6
56 17206013 Zhou Puqi 17206014 Jian Dingding 2 4
57 17206015 Li Jiahua 17206016 Tian Feng 3 2
58 17206018 Cheng Litao 17206019 Guo Xu 4 5
59 17206020 Que Chencan 17206021 Wang Peizhao 5 3
60 17206022 Li Xiang 17206023 Chen Haixin 6 4
61 17206024 Wei Lian 17206040 Chen Xiang 1 5
62 17206041 Lu Jiahe 17206151 Gu Zhenlei 2 3
63 17206185 Wen Yannuo 17206205 Wang Xuliang 3 6
64 17206206 Zhang Yuxiang 17206208 Chen Dingrui 4 2
65 17206209 Li Chengjin 17206210 Sun Buwei 5 3
66 17206211 Li Ruijie 17206221 Tang Song 6 2