[发明专利]一种并行快速傅立叶变换处理方法

摘要

本发明提供了一种并行快速傅立叶变换处理方法，该方法将点数为N＝r^S的数据序列x(n)划分为vr个二级数据块，然后采用基r FFT计算得到每个二级数据块中的个数据的FFT结果，其中：v＝r^Z，r和S为任意整数，Z＝0、1、…或S‑2，因此本发明的数据点数N具有更多的取值，可以在这些取值中选择补零最少的方案，从而减少对存储空间和计算时间的占用；而且本发明采用多蝶形并行计算，且并行蝶形计算单元的个数v＝r^Z，因此本发明可以根据硬件资源的配置来选择并行度，具有较大的灵活性。

主权项

1.一种并行快速傅立叶变换处理方法，其特征在于包括如下步骤：(1)、对接收到的数据序列x(n)进行第一级数据分组，n＝0、1、…、N‑1，即将N个数据划分为v个一级数据块，每个所述一级数据块包括个数据；其中，第n₂个一级数据块中第n₁个数据为x′(n₁,n₂)＝x(n₂v+n₁)，n₂＝0、1、…、v‑1；N＝r^S，v＝r^Z，Z＝0、1、…、S‑2，S和r为整数；(2)、对步骤(1)划分的各一级数据块进行第二级数据分组，即将每个一级数据块划分为r个二级数据块，每个所述二级数据块包括个数据；其中，第n₂个一级数据块划分的第n'₂个二级数据块中的第n'₁个数据x″(n'₁,n'₂,n₂)＝x′(n'₂r+n'₁,n₂)，n'₂＝0、1、…、r‑1，n₂＝0、1、…、v‑1；(3)、对每个二级数据块中的个数据进行点FFT计算；其中第n₂个一级数据块划分的第n'₂个二级数据块中的个数据FFT计算结果为其中，n'₂＝0、1、…、r‑1，n₂＝0、1、…、v‑1，采用v个基r蝶形单元对vr个二级数据块进行基r FFT计算，每个一级数据块中的r个二级数据块通过时分复用系统共用1个基r蝶形计算单元；所述时分复用系统包括r个串并转换模块、第一级选通控制单元、基r蝶形计算单元、第二级选通控制单元和r个并串转换模块，其中：r个串并转换模块：与一个一级数据块中的r个二级数据块一一对应；分别从r个二级数据块的存储器中读取数据，得到r路串行数据，其中每路串行数据包括个数据点；然后每个串并转换模块对相应的串行数据进行串并转换，将串行的个数据点转换为r路并行数据，每路并行数据包括个数据点；第一级选通控制单元：对r个串并转换模块输出的并行数据进行选通操作，每次选通其中1个串并转换模块输出的r路并行数据，然后将所述r路并行数据输出到基r蝶形计算单元；基r蝶形计算单元：接收r路并行数据进行基r FFT计算，输出r路并行计算结果到第二级通道选通控制单元；第二级选通控制单元：在r个并串转换模块之间进行选通，将接收到的r路并行FFT计算结果输出到其中1个并串转换模块，选通的并串转换模块序号与第一级选通控制单元选通的串并转换模块序号一致；r个并串转换模块：与一个一级数据块中的r个二级数据块一一对应；经第二级选通控制单元选通后的并串转换模块，接收r路并行FFT计算结果，进行并串变换1路串行数据，将所述串行数据保存在对应的二级数据块的存储器内，存储位置与串并转换模块读取数据的位置一致，即实现原位存储；(4)、将每个一级数据块中的r个二级数据块的FFT计算结果进行合并，得到每个一级数据块的FFT计算结果；其中，第n₂个一级数据块中的个数据的FFT计算结果为其中，n₂＝0、1、…、v‑1，(5)、将v个一级数据块的FFT计算结果进行合并，得到数据序列x(n)的N点FFT计算结果其中，k＝0、1、…、N‑1，W_N＝e^‑j2π/N。