二维离散傅里叶变换DFT(2^n;k)的快速算法

"这篇文档是关于长度为2^n的多维离散傅里叶变换（DFT_2^n_k）的算法，主要讨论了如何利用环结构优化计算过程，降低运算量。文章由华南理工大学的马维祯撰写，介绍了基于环结构的算法，将多维DFT转换为一维离散傅里叶变换（CFT）的计算，从而提高了效率。" 离散傅里叶变换（DFT）是数字信号处理中的一项基础技术，用于将信号从时域转换到频域，以便分析其频率成分。对于长度为2^n的序列，传统的DFT计算方法会涉及到大量的复数乘法和加法，计算复杂度较高。1965年Cooley-Tukey提出的快速傅里叶变换（FFT）极大地降低了计算复杂度，但对于多维DFT，即使有FFT，计算量仍可能很大。 文章中提到的算法是针对长度为2^n的多维DFT进行优化的一种方法。它利用环结构，将DFT转换成一系列互不相交子群（核群K陪集）的循环块，这些循环块进一步转换成具有相同块的块对角矩阵。每个块都是一维的CFT，这样可以将多维问题分解为一维问题来解决，显著减少了计算量。这种局部环结构的概念扩展了之前Vus的工作，他在1985年将环结构应用到长度为p的多维离散傅里叶变换上。 作者指出，孙der和wiedemann引入代数数论，揭示了DFT、离散卷积和多项式乘积之间的联系，使得长度为2^n的DFT算法可以扩展到长度为p和p^m的一维以及长度为p的多维情况。然而，对于长度为2^n的多维DFT，由于需要计算一系列多维核的CFT，原有的算法仍存在计算负担。通过作者提出的算法，DFT(2^n;k)被转换为一系列一维CFT(2^n)的计算，大大简化了计算流程，提高了计算效率。 文章的第二部分可能深入探讨了如何构建这种环结构，以及如何利用这种结构来重新排序输入和输出数组，以便于执行更有效的计算。作者还推导了DFT(2^n;k)的乘法复杂性，这在理解和优化算法性能方面至关重要。 这篇文献对于理解并优化长度为2^n的多维离散傅里叶变换的计算具有重要意义，对于涉及大量信号处理和数据分析的领域，如通信、图像处理和音频工程，都提供了有价值的理论和技术支持。