一种基于三叉树的分裂基FFT算法的优化方法

摘要

本发明公开了一种基于三叉树的分裂基FFT算法的优化方法是按如下步骤进行：1定义一棵三叉树和树节点中的信息；2针对特定的FFT计算规模使用三叉树生成计算信息；3使用宽度优先搜索算法对三叉树进行遍历，获取计算过程的各项信息，将计算信息保存到链表中。4利用链表中节点的计算信息，完成分裂基FFT算法的优化。本发明能克服分裂基FFT算法中传统递归实现中带来的低效问题，减少递归调用子函数时的系统开销，同时能够预先完成分裂基算法中的计算任务划分的工作，提高效率。

主权项

一种基于三叉树的分裂基FFT算法的优化方法，其特征是按如下步骤进行：步骤1、全局定义定义分裂基FFT算法的源向量为X[X₀,X₁,…,X_k,…,X_N‑1]；N表示源向量的长度；X_k表示FFT算法中的第k+1个复数数据；定义旋转因子数组为W[W₀,W₁,…,W_k,…,W_N‑1]；W_k表示第k+1个旋转因子；0≤k≤N‑1；定义全局变量为β，γ；定义链表L；定义所述三叉树中每个节点的计算信息包含：计算规模n、计算的起始位置pos、旋转因子在所述旋转因子数组W中的位置posOmega、父亲节点father、以及左子树left、中子树mid和右子树right；步骤2、使用迭代过程建立一棵三叉树Tree：步骤2.1、定义在创建每个节点时的传入参数包含：传入参数a为整数类型，表示当前计算规模；传入参数b为整数类型，表示当前计算的起始位置；传入参数c为整数类型，表示当前旋转因子在所述旋转因子数组W中的位置；传入参数d为指针类型，表示指向当前处理节点的父亲节点；步骤1.3、初始化所述传入参数和全局变量：a＝N；b＝0；c＝1；β＝1；γ＝1；步骤1.4、创建第β个节点Root_β：更新所述第β个节点Root_β的计算规模n_β为a、计算的起始位置pos_β为b、旋转因子在所述旋转因子数组W中的位置posOmega_β为c、父亲节点father_β为d；步骤1.5、判断γ＞β是否成立，如果成立，则跳入步骤2；否则，跳入步骤1.6；步骤1.6、判断n_γ＝2或n_γ＝4是否成立，若成立，则将所述第γ个节点Root_γ的左子树left_γ、中子树mid_γ和右子树right_γ均设置为空；否则跳入步骤1.7；步骤1.7、令b＝pos_γ、c＝2×posOmega_γ、d＝Root_γ；步骤1.8、将β+1赋值给β后，创建第β个节点Root_β：更新所述第β个节点Root_β的计算规模n_β为a、计算的起始位置pos_β为b、旋转因子在所述旋转因子数组W中的位置posOmega_β为c、父亲节点father_β为d；步骤1.9、令c＝4×posOmega_γ、d＝Root_γ；步骤1.10、将β+1赋值给β后，创建第β个节点Root_β：更新所述第β个节点Root_β的计算规模n_β为a、计算的起始位置pos_β为b、旋转因子在所述旋转因子数组W中的位置posOmega_β为c、父亲节点father_β为d；步骤1.11、令c＝4×posOmega_γ、d＝Root_γ；步骤1.12、将β+1赋值给β后，创建第β个节点Root_β：更新所述第β个节点Root_β的计算规模n_β为a、计算的起始位置pos_β为b、旋转因子在所述旋转因子数组W中的位置posOmega_β为c、父亲节点father_β为d；步骤1.13、将γ+1赋值给γ，跳入步骤1.5；步骤2、利用度优先搜索算法遍历所述三叉树Tree，获取每个节点所包含的计算信息，并将每个节点的计算信息添加到所述链表L中：步骤2.1、建立一个空队列Q；并初始化β＝1；步骤2.2、将第β个节点Root_β所包含的计算信息加入队列Q中；步骤2.3、判断队列Q是否为空，若为空，则执行步骤3；否则，执行步骤2.4；步骤2.4、判断队头元素中的左子树left是否为空，若为空，则将队列Q中的队头元素出队，并添加到链表L中，从而获得更新的链表L′后，跳入步骤2.3；否则，执行步骤2.5；步骤2.5、将队头元素中的左子树left、中子树mid和右子树right所包含的计算信息入队Q后；将队列Q中的队头元素出队，并添加到链表L中，从而获得更新的链表L′；步骤2.6、跳转到步骤2.3；步骤3、利用式(1)获得第k+1个旋转因子W_k，从而获得旋转因子数组W：$W_k=e^{-j\frac{2\pi }{N}k}---\left(1\right)$步骤4、遍历所述更新的链表L′中的所有元素并进行FFT变换：步骤4.1、将所述更新的链表L′记为L′[L′₀,L′₁,…,L′_M‑1]；M表示所述更新的链表L′中元素个数；步骤4.2、定义循环变量m，并初始化m＝1；步骤4.3、定义临时变量e₁、e₂、e₃、e₄；步骤4.4、判断m＞M是否成立，若成立，则跳入步骤4.18；否则，跳入步骤4.5；步骤4.5、将所述第m个元素L′_m‑1所对应的计算规模记为ρ_m，所对应的计算的起始位置记为σ_m，所对应的旋转因子在所述旋转因子数组W中的位置为η_m；步骤4.6、判断ρ_m≠2是否成立，若成立，跳入步骤4.8；否则令并利用公式，得到更新后的$X_{t+{\sigma }_m}=e_1+X_{t+{\sigma }_m+1}---\left(2\right)$步骤4.7、利用公式(3)，得到更新后的跳入步骤4.17；$X_{t+{\sigma }_m+1}=e_1-X_{t+{\sigma }_m+1}---\left(3\right)$步骤4.8、定义变量p_m，并初始化步骤4.9、定义临时变量t，并初始化为t＝0；步骤4.10、判断t＝p_m是否成立，若成立，则跳转到步骤4.17；否则，执行步骤4.11；步骤4.11、令$e_1=X_{t+{\sigma }_m},e_2=X_{t+{\sigma }_m+p_m},e_3=X_{t+2\times p_m+{\sigma }_m},e_4=X_{t+3\times p_m+{\sigma }_m};$步骤4.12、利用公式(4)，得到更新后的$X_{t+{\sigma }_m}=e_1+e_3---\left(4\right)$步骤4.13、利用公式(5)，得到更新后的$X_{t+{\sigma }_m+p_m}=e_2+e_4---\left(5\right)$步骤4.14、利用公式(6)，得到更新后的$X_{t+{\sigma }_m+2\times p_m}=\{e_1-e_3-j(e_2-e_4)\}\times W_{t\times {\eta }_m\%N}---\left(6\right)$步骤4.15、利用公式(7)，得到更新后的$X_{t+{\sigma }_m+3\times p_m}=\{e_1-e_3+j(e_2-e_4)\}\times W_{t\times 3\times {\eta }_m\%N}---\left(7\right)$步骤4.16、令t+1赋值给t后，跳入步骤4.10；步骤4.17、令m+1赋值给m后，跳入步骤4.4；步骤4.18、运算结束。