论文部分内容阅读
本文涉及数字信号处理的技术领域，更具体的，本文涉及一种能够对离散傅立叶变换进行并行计算的方法及实现
离散傅立叶变换的主要实现方法
离散时间信号的频谱分析，噪声的滤波处理，以及信号捕获的相关运算，离散傅立叶变换（DFT）都是一种常用的数字信号处理方法。
目前计算离散傅立叶变换主要包括以下几种方法[1]：
（1）通过解联立方程计算离散傅立叶变换；（2）通过相关性方法计算离散傅立叶变换；（3）直接法（DFT）计算离散傅立叶变换；（4）快速傅立叶变换（FFT）计算离散傅立叶变换；（5）稀疏傅里叶变换（sFFT）计算离散傅立叶变换。
方法（3）是一种直接算法，计算原理易于掌握，但是计算效率低下，其计算复杂度为，不利于大规模的运算。
方法（4）是方法（3）一种快速高效的实现方法，其计算复杂度为，是当前主流计算离散傅立叶变换的方法。
方法（5）是比方法（4）更快速高效的离散傅立叶变换的计算方法，是由于MIT发布的最新研究成果，其计算复杂度为[2]。
并行计算是指，在并行机上，将一个问题分解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行的执行子任务。
并行计算主要是为了达到提高求解同一个应用的速度，或者提高求解同一个应用的问题规模的目的。
并行计算能够成功开展必备的三个基本条件为[3]：
（a）能够与客服端相互通信的并行机；（b）应用问题必须能够分解成多个子任务，并且这些子任务能够并行的执行；（c）并行编程实现并且能够运行求解应用问题的程序。目前，提高离散傅立叶变换计算速度还是数字信号处理方法的一个重要发展方向。
离散傅立叶变换进行并行计算的理论基础
步骤如下：当待处理的离散时间信号的序列长度大于系统能够处理的最大序列长度，或者系统计算离散时间信号的离散傅立叶变换时间超过预设的时间阈值时，使用离散时间信号分段模块对所述离散时间信号进行分段处理，得到预设数目的分段并且长度相等的离散时间信号，其中，分段的离散时间信号长度不能超过系统所能处理的最大序列长度；
所述系统对传输到各并行机中每一段的等长分段离散时间信号，使用离散时间信号并行处理模块进行快速离散傅立叶变换，得到对应的离散傅立叶变换结果；
[所述系统对分段离散时间信号的对应离散傅立叶变换结果，使用离散时间信号加权运算模块进行加权运算，得到对应的分段加权结果；
所述系统对分段离散时间信号对应的分段加权结果，使用离散时间信号组装模块进行组合运算，得到所述离散时间信号的离散傅立叶变换结果。
进一步地，所述系统对所述的离散时间信号进行分段处理，得到预设数目的分段并且长度相等的离散时间信号的步骤包括：
当预设数目的分段数小于或等于并行机的个数时，直接对所述离散时间信号进行分段传输到各并行机中；
当预设数目的分段数大于并行机的个数时，对所述离散时间信号按照分段编号顺序优先原则传输到各并行机中。进一步地，所述系统对传输到各并行机中每一段的等长分段离散时间信号，使用离散时间信号并行处理模块进行快速离散傅立叶变换，并且得到对应的离散傅立叶变换结果的步骤包括：其中的离散傅立叶变换根据需求，可以采用常用的快速傅立叶变换（FFT）或者稀疏傅里叶变换（sFFT）计算。
进一步地，所述系统对分段离散时间信号的对应离散傅立叶变换结果，使用离散时间信号加权运算模块进行加权运算，得到对应的分段加权结果的步骤包括：当预设数目的分段数小于或等于并行机的个数时，直接对各并行机输出结果进行加权运算；当预设数目的分段数大于并行机的个数时，直到各并行机输出结果的次数等于预设数目的分段数，再对各输出结果进行加权运算；
本文仅利用了旋转因子的周期性和共轭对称性，因此，本文对离散时间信号的逆离散傅立叶变换 （IDFT）同样适用。
本文从提高离散傅立叶变换计算速度和针对现有的处理器的性能局限性的目的出发，提出了利用并行算法计算离散傅立叶变换，从而以最小的计算量实现所述离散时间信号的完整离散傅立叶变换。
具体实施方式和实验结果
为了使得本文的目的、技术原理以及优点更加清楚，下面结合附图和实施例对本文进行详细的说明。
参照附图1，附图1是本文分段并行计算离散傅立叶变换方法的流程图。
本文所述的分段并行计算离散傅立叶变换的方法包括以下步骤：
步骤101，采集离散时间信号；大多数离散时间信号是由对连续时间信号抽样得到的，这里对连续时间信号的抽样应该满足奈奎斯特抽样定理。
步骤102，判断是否需要进行并行计算处理；首先，需要判断是否有进行并行计算的环境，主要是硬件环境；其次，需要判断采集到的离散时间信号是否满足并行计算的条件，例如分段；最后，需要判断该计算方法是否能够进行并行算法编程实现。
步骤103，将离散时间信号进行分段处理，依次传送到对应的并行机中；
在本步骤中，离散时间信号进行分段有三种情况：离散时间信号的分段数小于并行机的个数，离散时间信号的分段数等于并行机的个数，离散时间信号的分段数大于并行机的个数。当离散时间信号的分段数小于或者等于并行机的个数时，只需要对分段的离散时间信号依次传送到对应的并行机中即可；当离散时间信号的分段数大于并行机的个数时，需要对分段的离散时间信号按照分段编号顺序优先原则排队传输到对应并行机中进行处理。
步骤104，直接使用快速傅立叶变换计算，得到该离散时间信号的离散傅立叶变换结果；
本步骤中用到的快速傅立叶变换根据需求，可以采用常用的快速傅立叶变换（FFT）或者稀疏傅里叶变换（sFFT）计算。 步骤105，在并行机中，对各分段离散时间信号进行快速傅立叶变换；并行机中使用的使用快速傅立叶变换，根据需求，可以采用常用的快速傅立叶变换（FFT）或者稀疏傅里叶变换（sFFT）计算。
步骤106，对各并行机输出的结果进行对应的加权运算；本步骤中的加权运算需要用所有分段离散时间信号经过离散傅立叶变换后的结果，因此，本步骤需要在所有分段离散时间信号在并行机中都处理完成后开始执行运算。
步骤106，对各加权运算的结果进行组合，得到离散时间信号的离散傅立叶变换结果；
具体地，只需要对加权运算后的结果按照顺序排列，就可以得到所述离散时间信号的离散傅立叶变换结果。
本文实施例中的离散时间信号分段模块主要包括：
上述矩阵的第一行即为所述离散时间信号的第一分段，其形状如图402所示；第二行即为所述离散时间信号的第二分段，其形状如图403所示；第三行即为所述离散时间信号的第三分段，其形状如图404所示。
本文实施例中的离散时间信号并行处理模块主要包括：
将分段信号分别传输到对应的并行机中，在并行机中进行离散傅立叶变换；
用具体实施例说明，上述分段离散时间信号中第一段分段离散时间信号传输到1号并行机中，第二段分段离散时间信号传输到2号并行机中，第三段分段离散时间信号传输到3号并行机中；
对上述矩阵，第一行对应1号并行机的输出结果，第二行对应2号并行机的输出结果，第三行对应3号并行机的输出结果。
其中，第一段分段离散时间信号经过离散傅立叶变换后的幅值如图502所示，第二段分段离散时间信号经过离散傅立叶变换后的幅值如图503所示，第三段分段离散时间信号经过离散傅立叶变换后的幅值如图504所示。
本文实施例中的离散时间信号加权运算模块主要包括：
待上述并行机中所有离散傅立叶变换后的分段离散时间信号都传输完毕后，离散时间信号加权运算模块对所述的离散傅立叶变换后的分段离散时间信号进行加权运算；
本文实施例中的离散时间信号组装模块主要包括：
对上述加权运算结果按照输出顺序进行组合运算，得到所述离散时间信号的离散傅立叶变换结果。
通过上述实施例，本文给出了离散傅立叶变换的等价实施算法：分段并行计算离散傅立叶变换。但应该明确的是，不能认定本文只限于上述的具体实施说明。对于本领域的技术人员在本文揭露的技术范围内，都应当视为本文的保护范围。
参考文献
[1] Steven W.Smith著，张瑞峰詹敏晶等译.实用数字信号处理从原理到应用 [M] 人民邮电出版社.p112-115
[2] Piotr Indyk， Michael Kapralov， and Eric Price SODA，Sample-Optimal Sparse Fourier Transform [J] January 2014.
[3] 张林波. 并行计算导论 [M] 清华大学出版社.p23-25
离散傅立叶变换的主要实现方法
离散时间信号的频谱分析，噪声的滤波处理，以及信号捕获的相关运算，离散傅立叶变换（DFT）都是一种常用的数字信号处理方法。
目前计算离散傅立叶变换主要包括以下几种方法[1]：
（1）通过解联立方程计算离散傅立叶变换；（2）通过相关性方法计算离散傅立叶变换；（3）直接法（DFT）计算离散傅立叶变换；（4）快速傅立叶变换（FFT）计算离散傅立叶变换；（5）稀疏傅里叶变换（sFFT）计算离散傅立叶变换。
方法（3）是一种直接算法，计算原理易于掌握，但是计算效率低下，其计算复杂度为，不利于大规模的运算。
方法（4）是方法（3）一种快速高效的实现方法，其计算复杂度为，是当前主流计算离散傅立叶变换的方法。
方法（5）是比方法（4）更快速高效的离散傅立叶变换的计算方法，是由于MIT发布的最新研究成果，其计算复杂度为[2]。
并行计算是指，在并行机上，将一个问题分解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行的执行子任务。
并行计算主要是为了达到提高求解同一个应用的速度，或者提高求解同一个应用的问题规模的目的。
并行计算能够成功开展必备的三个基本条件为[3]：
（a）能够与客服端相互通信的并行机；（b）应用问题必须能够分解成多个子任务，并且这些子任务能够并行的执行；（c）并行编程实现并且能够运行求解应用问题的程序。目前，提高离散傅立叶变换计算速度还是数字信号处理方法的一个重要发展方向。
离散傅立叶变换进行并行计算的理论基础
步骤如下：当待处理的离散时间信号的序列长度大于系统能够处理的最大序列长度，或者系统计算离散时间信号的离散傅立叶变换时间超过预设的时间阈值时，使用离散时间信号分段模块对所述离散时间信号进行分段处理，得到预设数目的分段并且长度相等的离散时间信号，其中，分段的离散时间信号长度不能超过系统所能处理的最大序列长度；
所述系统对传输到各并行机中每一段的等长分段离散时间信号，使用离散时间信号并行处理模块进行快速离散傅立叶变换，得到对应的离散傅立叶变换结果；
[所述系统对分段离散时间信号的对应离散傅立叶变换结果，使用离散时间信号加权运算模块进行加权运算，得到对应的分段加权结果；
所述系统对分段离散时间信号对应的分段加权结果，使用离散时间信号组装模块进行组合运算，得到所述离散时间信号的离散傅立叶变换结果。
进一步地，所述系统对所述的离散时间信号进行分段处理，得到预设数目的分段并且长度相等的离散时间信号的步骤包括：
当预设数目的分段数小于或等于并行机的个数时，直接对所述离散时间信号进行分段传输到各并行机中；
当预设数目的分段数大于并行机的个数时，对所述离散时间信号按照分段编号顺序优先原则传输到各并行机中。进一步地，所述系统对传输到各并行机中每一段的等长分段离散时间信号，使用离散时间信号并行处理模块进行快速离散傅立叶变换，并且得到对应的离散傅立叶变换结果的步骤包括：其中的离散傅立叶变换根据需求，可以采用常用的快速傅立叶变换（FFT）或者稀疏傅里叶变换（sFFT）计算。
进一步地，所述系统对分段离散时间信号的对应离散傅立叶变换结果，使用离散时间信号加权运算模块进行加权运算，得到对应的分段加权结果的步骤包括：当预设数目的分段数小于或等于并行机的个数时，直接对各并行机输出结果进行加权运算；当预设数目的分段数大于并行机的个数时，直到各并行机输出结果的次数等于预设数目的分段数，再对各输出结果进行加权运算；
本文仅利用了旋转因子的周期性和共轭对称性，因此，本文对离散时间信号的逆离散傅立叶变换 （IDFT）同样适用。
本文从提高离散傅立叶变换计算速度和针对现有的处理器的性能局限性的目的出发，提出了利用并行算法计算离散傅立叶变换，从而以最小的计算量实现所述离散时间信号的完整离散傅立叶变换。
具体实施方式和实验结果
为了使得本文的目的、技术原理以及优点更加清楚，下面结合附图和实施例对本文进行详细的说明。
参照附图1，附图1是本文分段并行计算离散傅立叶变换方法的流程图。
本文所述的分段并行计算离散傅立叶变换的方法包括以下步骤：
步骤101，采集离散时间信号；大多数离散时间信号是由对连续时间信号抽样得到的，这里对连续时间信号的抽样应该满足奈奎斯特抽样定理。
步骤102，判断是否需要进行并行计算处理；首先，需要判断是否有进行并行计算的环境，主要是硬件环境；其次，需要判断采集到的离散时间信号是否满足并行计算的条件，例如分段；最后，需要判断该计算方法是否能够进行并行算法编程实现。
步骤103，将离散时间信号进行分段处理，依次传送到对应的并行机中；
在本步骤中，离散时间信号进行分段有三种情况：离散时间信号的分段数小于并行机的个数，离散时间信号的分段数等于并行机的个数，离散时间信号的分段数大于并行机的个数。当离散时间信号的分段数小于或者等于并行机的个数时，只需要对分段的离散时间信号依次传送到对应的并行机中即可；当离散时间信号的分段数大于并行机的个数时，需要对分段的离散时间信号按照分段编号顺序优先原则排队传输到对应并行机中进行处理。
步骤104，直接使用快速傅立叶变换计算，得到该离散时间信号的离散傅立叶变换结果；
本步骤中用到的快速傅立叶变换根据需求，可以采用常用的快速傅立叶变换（FFT）或者稀疏傅里叶变换（sFFT）计算。 步骤105，在并行机中，对各分段离散时间信号进行快速傅立叶变换；并行机中使用的使用快速傅立叶变换，根据需求，可以采用常用的快速傅立叶变换（FFT）或者稀疏傅里叶变换（sFFT）计算。
步骤106，对各并行机输出的结果进行对应的加权运算；本步骤中的加权运算需要用所有分段离散时间信号经过离散傅立叶变换后的结果，因此，本步骤需要在所有分段离散时间信号在并行机中都处理完成后开始执行运算。
步骤106，对各加权运算的结果进行组合，得到离散时间信号的离散傅立叶变换结果；
具体地，只需要对加权运算后的结果按照顺序排列，就可以得到所述离散时间信号的离散傅立叶变换结果。
本文实施例中的离散时间信号分段模块主要包括：
上述矩阵的第一行即为所述离散时间信号的第一分段，其形状如图402所示；第二行即为所述离散时间信号的第二分段，其形状如图403所示；第三行即为所述离散时间信号的第三分段，其形状如图404所示。
本文实施例中的离散时间信号并行处理模块主要包括：
将分段信号分别传输到对应的并行机中，在并行机中进行离散傅立叶变换；
用具体实施例说明，上述分段离散时间信号中第一段分段离散时间信号传输到1号并行机中，第二段分段离散时间信号传输到2号并行机中，第三段分段离散时间信号传输到3号并行机中；
对上述矩阵，第一行对应1号并行机的输出结果，第二行对应2号并行机的输出结果，第三行对应3号并行机的输出结果。
其中，第一段分段离散时间信号经过离散傅立叶变换后的幅值如图502所示，第二段分段离散时间信号经过离散傅立叶变换后的幅值如图503所示，第三段分段离散时间信号经过离散傅立叶变换后的幅值如图504所示。
本文实施例中的离散时间信号加权运算模块主要包括：
待上述并行机中所有离散傅立叶变换后的分段离散时间信号都传输完毕后，离散时间信号加权运算模块对所述的离散傅立叶变换后的分段离散时间信号进行加权运算；
本文实施例中的离散时间信号组装模块主要包括：
对上述加权运算结果按照输出顺序进行组合运算，得到所述离散时间信号的离散傅立叶变换结果。
通过上述实施例，本文给出了离散傅立叶变换的等价实施算法：分段并行计算离散傅立叶变换。但应该明确的是，不能认定本文只限于上述的具体实施说明。对于本领域的技术人员在本文揭露的技术范围内，都应当视为本文的保护范围。
参考文献
[1] Steven W.Smith著，张瑞峰詹敏晶等译.实用数字信号处理从原理到应用 [M] 人民邮电出版社.p112-115
[2] Piotr Indyk， Michael Kapralov， and Eric Price SODA，Sample-Optimal Sparse Fourier Transform [J] January 2014.
[3] 张林波. 并行计算导论 [M] 清华大学出版社.p23-25