快速傅里叶变换(FFT)——有史以来最巧妙的算法？-【强推|双字】快速傅里叶变换(FFT)——有史以来最巧妙的算法？ 附:傅里叶变换解析！

热门回复：

• 乐空hermit:原视频为油管博主Reducible发布，信息闭塞的小伙伴们别犯蠢了，原视频title：The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?
• 数电汤家凤:数字信号处理的必学内容
• Exist-Cain:up加油，关注啦[打call]
• 晓宇老师12138:在FFT中，视频里面的w=exp(2πi/n)，而实际上应该是w=exp(-2πi/n)，视频里面缺少了一个负号。所以FFT的代码如图一。 由于MATLAB的向量下标是从1开始而非0，所以在第26和27行，w的幂应该是j-1。 在IFFT中，视频里面直接将w改为exp(-2πi/n)/n，实际上大错特错。IDFT矩阵每个位置处的w都是DFT矩阵中的w，不需要任何变化。反而是需要给w的幂乘以负一。另外，IDFT矩阵是一次性除以n，而非每次都让w除以n。所以IFFT的代码如图二。 w和FFT中的w一模一样，都是exp(-2πi/n)。 第26和27行，w的幂应该是FFT中的幂乘以负一，也就是1-j。另外，整个过程应该是一次性除以n，如果每次递归都除以n就错了。而递归程序刚好递归log(2)n次，所以只需要每次都除以2，递归log(2)n次后，就可以达到除以n的效果了。因此可以看见我在第26和27行的后面都除以了2。 我知道UP主想要大家的三连才能给源代码，但是我希望这个勘误评论可以留下来不要删，让更多想要学习的人看见。[打call]
• AI视频小助理:一、算法的分类以及其中一个名为快速傅里叶变换的算法。该算法被广泛应用于现代技术中，同时也是一个美丽的算法。 00:01 - 算法分为两类：天生有用的和纯粹美丽的算法 00:57 - 快速傅里叶变换是上个世纪创造的最重要算法之一 03:45 - 任何d次多项式都可以唯一地用d+1个点表示，这是多项式乘法的巧妙延伸 二、多项式乘法的两种表示方法，以及如何将多项式从系数表示转换为值表示，并提出了优化多项式乘法的计划。 05:43 - 两种表示d次多项式的方法：系数表示和值表示 07:12 - 改进多项式乘法的计划：将多项式转换为值表示并转换回系数表示 10:45 - 将多项式拆分为偶项和奇项，计算多项式的方法：将两个较小的多项式的n次方除以二减一 三、FFT算法，通过计算每个原始输入处的多项式平方，解决了递归算法中断的问题，并提出了扩展初始点的域为复数的特殊选择的方法。 11:22 - 计算多项式平方的递归算法 12:08 - 利用正负配对点之间的关系计算原始多项式的值表示 15:52 - 选择2的幂的初始点集，选择n大于或等于d加一点的统一的第n根作为初始点集 四、快速傅里叶变换(FFT)算法的实现过程，包括多项式的拆分、递归调用、统一根的处理以及最终的输出结果。该算法具有高效性，是信号处理领域的重要工具。 17:04 - FFT算法利用欧米茄到零的次方来计算多项式 18:21 - FFT算法的关键是利用正负对之间的关系，递归调用FFT函数 20:36 - FFT算法的最后一步是返回多项式p的值，在统一的第n根上评价 五、从值表示到系数表示的反向转换过程，也就是所谓的插值，以及如何使用FFT算法进行插值和逆FFT算法的实现。 22:40 - 插值是将值表示转换为系数表示的过程 23:31 - FFT算法可以高效计算矩阵向量积，适用于插值问题 25:41 - 反向FFT算法可以用于插值，只需调整欧米茄定义即可 --本内容由AI视频小助理生成，关注解锁AI助理，由@PあScAL 召唤发送