关于《算法的乐趣》傅立叶变换一章的补充_oRbIt 的专栏-CSDN博客

关于《算法的乐趣》傅立叶变换一章的补充

一些热心读者反馈在介绍快速傅立叶变换（FFT）部分的描述和代码不一致，比如某位读者反馈前面正文介绍的是DIT-FFT，但是给出的代码实现确是DIF-FFT，让人困惑，本文准备补充一下相关的内容。

DIT-FFT和DIF-FFT，一个是按时间抽取计算（Decimation-In-Time），一个是按频率抽取计算（Decimation-In-Frequency），是两种等价的FFT算法，本章内容主要集中在离散傅立叶变换算法的使用实例，比如频谱和均衡器，因此并没有具体描述这二者的差异，只是在242页中间一段文字中做了说明，原文如下：

“FFT算法对这个位置关系的处理有两种方式，一种是如图15-4所示，在开始蝶形运算之前就对原始数据按照码位关系进行排序，则计算后可直接得到与原始序列一致的输出。这种方式又称为原位运算方式。另一种方式是直接进行蝶形运算，然后按照码位关系对运算后的输出结果重新排序。”

这段文字其实存一个错误，在此需要更正一下，实际上无论是DIT-FFT还是DIF-FFT，都可以实现为原位运算方式。

DIT-FFT和DIF-FFT的主要差异就是蝶形运算的方式，有的资料说属否需要对输入数据倒序重排也是DIT-FFT和DIF-FFT的差异，这一点是仁者见仁，智者见智了，许多高效的算法都可以通过巧妙的循环控制避免这个重排操作，因此这应该不算是DIT和DIF的主要差异。蝶形运算的差异主要体现在参与蝶形运算的两个点的数据与旋转因子的乘法是在减法之前还是在减法之后，这句话理解起来有点困难，可以通过蝶形运算关系图来理解。书中的图15-3是DIT-FFT的蝶形运算关系图，可以看出X2(n)X2(n)先与旋转因子进行了乘法计算，然后又X1(n)X1(n)分别与乘法计算的结果做加法和减法得到下一级的X1(n)X1(n)和X2(n)X2(n)，因为之前已经进行过倒序重排操作，因此参与计算前的X2(n)X2(n)实际上就是X(n+ N/2)，原位计算后得到对应结果就是下一级的X1(n)X1(n)和X2(n)X2(n)。本文在此给出DIF-FFT的蝶形运算关系图，如图(1)所示，X1(n)X1(n)和X2(n)X2(n)先做减法，然后将减法的结果与旋转因子相乘得到下一级的X2(n)X2(n)。图(1) DIF蝶形运算示意图

根据以上分析，本文补充一个DIT_FFT的算法实现，大家可以对比一下书中给出的DIF_FFT算法，可以看到蝶形运算部分的明显区别。

void DIT_FFT(FFT_HANDLE *hfft, COMPLEX *TD2FD)
{
    int power = NumberOfBits(hfft->count); //power为蝶形运算级数

    //重新排序
    ResortSequence(TD2FD, hfft->count, power);

    for(int k = 0; k < power; k++)  //第k级蝶形运算
    {
        int butterfly = 1 << (k + 1);
        int wtp = 1 << (power - k - 1);
        for(int j = 0; j < (1 << k); j++)  //蝶形运算分组
        {
            for(int i = j; i < hfft->count; i += butterfly)
            {
                int b = i + butterfly / 2;
                COMPLEX t = TD2FD[b]*hfft->wt[j * wtp];
                TD2FD[b] = TD2FD[i] - t; 
                TD2FD[i] = TD2FD[i] + t; 
            }
        }
    }
}

企业员工角色权限管理平台（SpringBoot2.0+Mybatis+Shiro+Vue）

08-07

课程简介： 历经半个多月的时间，Debug亲自撸的 “企业员工角色权限管理平台” 终于完成了。正如字面意思，本课程讲解的是一个真正意义上的、企业级的项目实战，主要介绍了企业级应用系统中后端应用权限的管理，其中主要涵盖了六大核心业务模块、十几张数据库表。 其中的核心业务模块主要包括用户模块、部门模块、岗位模块、角色模块、菜单模块和系统日志模块；与此同时，Debug还亲自撸了额外的附属模块，包括字典管理模块、商品分类模块以及考勤管理模块等等，主要是为了更好地巩固相应的技术栈以及企业应用系统业务模块的开发流程！ 核心技术栈列表： 值得介绍的是，本课程在技术栈层面涵盖了前端和后端的大部分常用技术，包括Spring Boot、Spring MVC、Mybatis、Mybatis-Plus、Shiro(身份认证与资源授权跟会话等等)、Spring AOP、防止XSS攻击、防止SQL注入攻击、过滤器Filter、验证码Kaptcha、热部署插件Devtools、POI、Vue、LayUI、ElementUI、JQuery、HTML、Bootstrap、Freemarker、一键打包部署运行工具Wagon等等，如下图所示： <img src="https://img-bss.csdn.net/201908070402564453.png" alt="" /> 课程内容与收益： <img src="https://img-bss.csdn.net/201908070403452052.png" alt="" /> 总的来说，本课程是一门具有很强实践性质的“项目实战”课程，即“企业应用员工角色权限管理平台”，主要介绍了当前企业级应用系统中员工、部门、岗位、角色、权限、菜单以及其他实体模块的管理；其中，还重点讲解了如何基于Shiro的资源授权实现员工-角色-操作权限、员工-角色-数据权限的管理；在课程的最后，还介绍了如何实现一键打包上传部署运行项目等等。如下图所示为本权限管理平台的数据库设计图： <img src="https://img-bss.csdn.net/201908070404285736.png" alt="" /> 以下为项目整体的运行效果截图： <img src="https://img-bss.csdn.net/201908070404538119.png" alt="" /> <img src="https://img-bss.csdn.net/201908070405002904.png" alt="" /> <img src="https://img-bss.csdn.net/201908070405078322.png" alt="" /> <img src="https://img-bss.csdn.net/201908070405172638.png" alt="" /> <img src="https://img-bss.csdn.net/201908070405289855.png" alt="" /> <img src="https://img-bss.csdn.net/201908070405404509.png" alt="" /> <img src="https://img-bss.csdn.net/201908070405523495.png" alt="" /> 值得一提的是，在本课程中，Debug也向各位小伙伴介绍了如何在企业级应用系统业务模块的开发中，前端到后端再到数据库，最后再到服务器的上线部署运行等流程，如下图所示： <img src="https://img-bss.csdn.net/201908070406328884.png" alt="" />

关于《算法的乐趣》傅立叶变换一章的补充

关于《算法的乐趣》傅立叶变换一章的补充

Recommend

傅立叶变换的物理意义

细讲傅立叶变换

您身边不懂傅立叶变换的程序员现在都混的怎么样了？

手把手教你用傅立叶变换画可达鸭 - 知乎

算法系列之二十四：离散傅立叶变换之音频播放与均衡器

关于《算法的乐趣》历法一章演示程序错误的说明

算法系列之二十三：离散傅立叶变换之音频播放与频谱显示

傅立叶变换的直观解释

快速傅立叶变换（FFT）在整数乘法中的应用

数学狂想曲（二）——傅立叶变换, DFT, 拉普拉斯变换

About Joyk