混合基DFT/IDFT并行读取及计算方法和装置

摘要

本发明公开了一种混合基DFT/IDFT数据并行读取方法、混合基DFT/IDFT并行计算方法、混合基DFT/IDFT数据并行读取装置、混合基DFT/IDFT并行计算装置。其中，该并行读取方法包括：根据待运算级数所对应的点数和已完成级数所对应点数的乘积，来配置两重循环参数；然后，判断最大并行读取数据个数与已完成级数所对应点数的乘积之间的大小；最后，基于判断结果，根据判断结果计算与之相对应的两重循环参数，并基于计算得到的两重循环参数并行读取数据。由此，本发明实施例提高了处理并行度，减少了数据间相关性，以使整体运算空拍减少，提高了流水线利用率，进而可有效提升混合基DFT/IDFT运算速率。

权利要求

1.一种混合基DFT/IDFT数据并行读取方法，其特征在于，所述方法至少包括：根据待运算级数所对应的点数和已完成级数所对应点数的乘积，来配置两重循环参数；

判断最大并行读取数据个数与所述已完成级数所对应点数的乘积之间的大小；

根据判断结果计算与之相对应的两重循环参数，并基于计算得到的两重循环参数并行读取数据。

2.根据权利要求1所述的方法，其特征在于，所述根据待运算级数所对应的点数和已完成级数所对应点数的乘积，来配置两重循环参数，具体包括：根据所述待运算级数所对应的点数和所述已完成级数所对应点数的乘积，配置如下两重循环参数：第一重循环步长为N1，第一重循环次数为N0，第二重循环步长为N2，第二重循环次数为 其中，所述N0表示待运算级数所对应的点数，所述N1表示已完成级数所对应点数的乘积，所述N2为所述N1与所述N0的乘积；所述N表示进行DFT/IDFT的点数。

3.根据权利要求1所述的方法，其特征在于，所述根据判断结果计算与之相对应的两重循环参数，并基于计算得到的两重循环参数并行读取数据，具体包括：在M小于等于N1的情况下，不处理所读取的旋转因子，计算以下两重循环参数：第一重循环步长为M、所述第一重循环次数为 第二重循环步长为N2、所述第二重循环次数为 其中，所述M表示处理器所支持的最大并行读取数据个数，所述N0表示待运算级数所对应的点数，所述N1表示已完成级数所对应点数的乘积，所述N2为所述N1与所述N0的乘积；所述N表示进行DFT/IDFT的点数；

根据上述两重循环参数并行读取所述数据，且每次读取所述M个数据，直至将所述N1个数据全部读出。

4.根据权利要求1所述的方法，其特征在于，所述根据判断结果计算与之相对应的两重循环参数，并基于计算得到的两重循环参数并行读取数据，还具体包括：在M大于N1的情况下，计算 值；

复制 份所读取的旋转因子；

根据以下两重循环参数以N2步长并行读取前 组数据：第一重循环步长为所述第一重循环次数为N0、第二重循环步长为 所述第二重循环次数为 其中，所述M表示处理器所支持的最大并行读取数据个数，所述N0表示待运算级数所对应的点数，所述N1表示已完成级数所对应点数的乘积，所述N2为所述N1与所述N0的乘积；所述N表示进行DFT/IDFT的点数。

5.一种基于上述权利要求1-4中任一所述方法的混合基DFT/IDFT并行计算方法，其特征在于，所述并行计算方法至少包括：步骤1：并行读取输入旋转因子与输出旋转因子，并将二者对应项进行相乘，将乘积结果连同所述输入旋转因子作为等效旋转因子；

步骤2：将所述等效旋转因子与输入数据相乘，并对乘积结果进行缓存；

步骤3：在第二重循环中，执行所述步骤2中乘法运算时，将所述步骤2缓存的结果读出，并进行相应的加法或减法操作。

6.根据权利要求5所述的并行计算方法，其特征在于，所述将所述等效旋转因子与输入数据相乘，并对乘积结果进行缓存，具体包括：在处理器未设有复数运算单元的情况下，将所述等效旋转因子与所述输入数据的实部、虚部交叉相乘的结果进行缓存。

7.根据权利要求5所述的并行计算方法，其特征在于，所述步骤3具体包括：在处理器设有复数运算单元的情况下，执行所述步骤2中乘法运算时，将所述步骤2缓存的结果读出，并进行相应的加法操作。

8.根据权利要求5所述的并行计算方法，其特征在于，所述步骤3还具体包括：在处理器未设有复数运算单元的情况下，执行所述步骤2中乘法运算时，将所述步骤2缓存的结果读出，并进行如下减法操作：将所述等效旋转因子和所述输入数据的实部之间乘积与所述等效旋转因子和所述输入数据的虚部之间乘积相减。

9.一种混合基DFT/IDFT数据并行读取装置，其特征在于，该并行读取装置至少包括：点数计算单元，用于根据待运算级数所对应的点数和已完成级数所对应点数的乘积，来配置两重循环参数；

组数判断单元，用于判断最大并行读取数据个数与所述已完成级数所对应点数的乘积之间的大小；

读取单元，用于根据所述组数判断单元得到的判断结果计算与之相对应的两重循环参数，并基于计算得到的两重循环参数并行读取数据。

10.根据权利要求9所述的并行读取装置，其特征在于，所述点数计算单元具体包括：配置模块，用于根据所述待运算级数所对应的点数和所述已完成级数所对应点数的乘积，配置如下两重循环参数：第一重循环步长为N1，第一重循环次数为N0，第二重循环步长为N2，第二重循环次数为 其中，所述N0表示待运算级数所对应的点数，所述N1表示已完成级数所对应点数的乘积，所述N2为所述N1与所述N0的乘积；所述N表示进行DFT/IDFT的点数。

11.根据权利要求9所述的并行读取装置，其特征在于，所述读取单元具体包括：第一计算模块，用于在M小于等于N1的情况下，不处理所读取的旋转因子，计算以下两重循环参数：第一重循环步长为M、重复次数为 第二重循环步长为N2、重复次数为其中，所述M表示处理器所支持的最大并行读取数据个数，所述N0表示待运算级数所对应的点数，所述N1表示已完成级数所对应点数的乘积，所述N2为所述N1与所述N0的乘积；所述N表示进行DFT/IDFT的点数；

第一读取模块，用于根据上述两重循环参数并行读取所述数据，且每次读取所述M个数据，直至将所述N1个数据全部读出。

12.根据权利要求9所述的并行读取装置，其特征在于，所述读取单元还具体包括：第二计算模块，用于在M大于N1的情况下，计算 值；

复制模块，用于复制所述 份所读取的旋转因子；

第二读取模块，用于根据以下两重循环参数以N2步长并行读取前所述 组数据：第一重循环步长为 第一重循环次数为N0、第二重循环步长为 第二重循环次数为 其中，所述M表示处理器所支持的最大并行读取数据个数，所述N0表示待运算级数所对应的点数，所述N1表示已完成级数所对应点数的乘积，所述N2为所述N1与所述N0的乘积；所述N表示进行DFT/IDFT的点数。

13.一种基于上述权利要求9-12中任一所述并行读取装置的混合基DFT/IDFT并行计算装置，其特征在于，所述并行计算装置至少包括：等效旋转因子计算单元，用于并行读取输入旋转因子与输出旋转因子，并将所述二者对应项进行相乘，将乘积结果连同所述输入旋转因子作为等效旋转因子；

缓存单元，用于将由所述等效旋转因子计算单元得到的所述等效旋转因子与输入数据相乘，并对乘积结果进行缓存；

数据处理单元，用于在第二重循环中，在所述缓存单元执行乘法运算时，将所述缓存单元中缓存的结果读出，并进行相应的加法或减法操作。

14.根据权利要求13所述的并行计算装置，其特征在于，所述等效旋转因子计算单元具体包括：并行读入模块，用于并行读入所述输入旋转因子及所述输出旋转因子；

缓存模块，用于将所述输入旋转因子与所述输出旋转因子对应项进行相乘，得到第一和第二组等效旋转因子，并将所述第一和所述第二组等效旋转因子连同作为第三组等效旋转因子的所述输入旋转因子存入缓存。

15.根据权利要求13所述的并行计算装置，其特征在于，所述数据处理单元还包括：复数运算单元，用于将所述缓存单元中缓存的结果读出，并进行相应的加法操作。

说明书

混合基DFT/IDFT并行读取及计算方法和装置

技术领域

[0001] 本发明实施例涉及移动通信技术领域，具体涉及一种混合基DFT/IDFT数据并行读取方法、混合基DFT/IDFT并行计算方法、混合基DFT/IDFT数据并行读取装置、混合基DFT/IDFT并行计算装置，但绝不限于此。

背景技术

[0002] 在数字信号处理系统中，尤其是有限长序列，DFT(离散傅里叶变换)是一种极为重要的数学变换。其本质为有限长序列傅里叶变换的有限点离散采样。它使得数字信号处理可以在频域采用数字运算方法完成，增强了数字信号处理的灵活性，DFT在数字通信、图像处理、功率谱估计等领域有着广泛应用。其中，点数为2的幂次方的DFT运算可采用基2类FFT算法完成。对于其他点数情况，即不能采用FFT算法完成称为一般数DFT。

[0003] 目前，一般数DFT一般采用以Cooley-Tukey算法为理论基础的混合基算法。基2类的FFT算法也以此为基础修改得到。其基本思想为：将大点数DFT转化为多次小点数DFT，其中每一次运算称为一级，依次执行每一级运算完成整个DFT过程。通常将小点数设置为质数，即3、5……在运算时依次按照基3、基5……的过程不断嵌套进行。每一级基N操作执行若干次，但所针对数据有所变化。

[0004]

[0005]

[0006] 式(1)为基3算法表达式，其中， 为输入旋转因子，与k有关；为输出旋转因子，与k无关。

[0007] 由于一般数DFT过程非2的整数倍，因此一般处理器进行处理时无法将整数组数据一次读入或写出，从而降低了并行度。同时，一般DFT处理过程为先进行数据与输入旋转因子的乘、加运算，再进行与输出旋转因子的乘、加运算，使得数据间相关性较大。再者，一般DFT过程将乘、加混合交替执行，再次引入计算相关性。这导致由数据相关性引起的运算器等待周期变长，流水线利用率降低，从而降低整个DFT运算的处理速率。

[0008] 有鉴于此，特提出本发明。

发明内容

[0009] 本发明实施例的主要目的在于提供一种混合基DFT/IDFT数据并行读取方法，其至少部分地解决了如何提升运算效率的技术问题。此外，还提供一种混合基DFT/IDFT并行计算方法、混合基DFT/IDFT数据并行读取装置、混合基DFT/IDFT并行计算装置。

[0010] 为了实现上述目的，根据本发明的一个方面，提供了以下技术方案：

[0011] 一种混合基DFT/IDFT数据并行读取方法。所述方法可以包括：

[0012] 根据待运算级数所对应的点数和已完成级数所对应点数的乘积，来配置两重循环参数；

[0013] 判断最大并行读取数据个数与所述已完成级数所对应点数的乘积之间的大小；

[0014] 根据判断结果计算与之相对应的两重循环参数，并基于计算得到的两重循环参数并行读取数据。

[0015] 进一步地，所述根据待运算级数所对应的点数和已完成级数所对应点数的乘积，来配置两重循环参数，具体可以包括：

[0016] 根据所述待运算级数所对应的点数和所述已完成级数所对应点数的乘积，配置如下两重循环参数：第一重循环步长为N1，第一重循环次数为N0，第二重循环步长为N2，第二重循环次数为 其中，所述N0表示待运算级数所对应的点数，所述N1表示已完成级数所对应点数的乘积，所述N2为所述N1与所述N0的乘积。

[0017] 进一步地，所述根据判断结果计算与之相对应的两重循环参数，并基于计算得到的两重循环参数并行读取数据，具体可以包括：

[0018] 在M小于等于N1的情况下，不处理所读取的旋转因子，计算以下两重循环参数：

[0019] 所述第一重循环步长为M、所述第一重循环次数为 所述第二重循环步长为N2、所述第二重循环次数为 其中，所述M表示处理器所支持的最大并行读取数据个数，所述N0表示待运算级数所对应的点数，所述N1表示已完成级数所对应点数的乘积，所述N2为所述N1与所述N0的乘积；

[0020] 根据上述两重循环参数并行读取所述数据，且每次读取所述M个数据，直至将所述N1个数据全部读出。

[0021] 进一步地，所述根据判断结果计算与之相对应的两重循环参数，并基于计算得到的两重循环参数并行读取数据，还具体可以包括：

[0022] 在M大于N1的情况下，计算 值；

[0023] 复制 份所读取的旋转因子；

[0024] 根据以下两重循环参数以N2步长并行读取前 组数据：所述第一重循环步长为 所述第一重循环次数为N0、所述第二重循环步长为 所述第二重循环次数为 其中，所述M表示处理器所支持的最大并行读取数据个数，所述N0表示待运算级数所对应的点数，所述N1表示已完成级数所对应点数的乘积，所述N2为所述N1与所述N0的乘积。

[0025] 为了实现上述目的，根据本发明的另一个方面，还提供了一种基于上述方法的混合基DFT/IDFT并行计算方法。所述并行计算方法可以包括：

[0026] 步骤1：并行读取输入旋转因子与输出旋转因子，并将二者对应项进行相乘，将乘积结果连同所述输入旋转因子作为等效旋转因子；

[0027] 步骤2：将所述等效旋转因子与输入数据相乘，并对乘积结果进行缓存；

[0028] 步骤3：在第二重循环中，执行所述步骤2中乘法运算时，将所述步骤2缓存的结果读出，并进行相应的加法或减法操作。

[0029] 进一步地，所述将所述等效旋转因子与输入数据相乘，并对乘积结果进行缓存，具体可以包括：

[0030] 在处理器未设有复数运算单元的情况下，将所述等效旋转因子与所述输入数据的实部、虚部交叉相乘的结果进行缓存。

[0031] 进一步地，所述步骤3具体可以包括：

[0032] 在处理器设有复数运算单元的情况下，执行所述步骤2中乘法运算时，将所述步骤2缓存的结果读出，并进行相应的加法操作。

[0033] 进一步地，所述步骤3还具体可以包括：

[0034] 在处理器未设有复数运算单元的情况下，执行所述步骤2中乘法运算时，将所述步骤2缓存的结果读出，并进行如下减法操作：

[0035] 将所述等效旋转因子和所述输入数据的实部之间乘积与所述等效旋转因子和所述输入数据的虚部之间乘积相减。

[0036] 为了实现上述目的，根据本发明的再一个方面，还提供了一种混合基DFT/IDFT数据并行读取装置。该并行读取装置可以包括：

[0037] 点数计算单元，用于根据待运算级数所对应的点数和已完成级数所对应点数的乘积，来配置两重循环参数；

[0038] 组数判断单元，用于判断最大并行读取数据个数与所述已完成级数所对应点数的乘积之间的大小；

[0039] 读取单元，用于根据所述组数判断单元得到的判断结果计算与之相对应的两重循环参数，并基于计算得到的两重循环参数并行读取数据。

[0040] 进一步地，所述点数计算单元具体可以包括：

[0041] 配置模块，用于根据所述待运算级数所对应的点数和所述已完成级数所对应点数的乘积，配置如下两重循环参数：第一重循环步长为N1，第一重循环次数为N0，第二重循环步长为N2，第二重循环次数为 其中，所述N0表示待运算级数所对应的点数，所述N1表示已完成级数所对应点数的乘积，所述N2为所述N1与所述N0的乘积。

[0042] 进一步地，所述读取单元具体可以包括：

[0043] 第一计算模块，用于在M小于等于N1的情况下，不处理所读取的旋转因子，计算以下两重循环参数：

[0044] 第一重循环步长为M、重复次数为 第二重循环步长为N2、重复次数为 其中，所述M表示处理器所支持的最大并行读取数据个数，所述N0表示待运算级数所对应的点数，所述N1表示已完成级数所对应点数的乘积，所述N2为所述N1与所述N0的乘积；

[0045] 第一读取模块，用于根据上述两重循环参数并行读取所述数据，且每次读取所述M个数据，直至将所述N1个数据全部读出。

[0046] 进一步地，所述读取单元还具体可以包括：

[0047] 第二计算模块，用于在M大于N1的情况下，计算 值；

[0048] 复制模块，用于复制所述 份所读取的旋转因子；

[0049] 第二读取模块，用于根据以下两重循环参数以N2步长并行读取前所述 组数据：第一重循环步长为 第一重循环次数为N0、第二重循环步长为第二重循环次数为 其中，所述M表示处理器所支持的最大并行读取数据个数，所述N0表示待运算级数所对应的点数，所述N1表示已完成级数所对应点数的乘积，所述N2为所述N1与所述N0的乘积。

[0050] 为了实现上述目的，根据本发明的又一个方面，还提供了一种基于上述并行读取装置的混合基DFT/IDFT并行计算装置。该并行计算装置可以包括：

[0051] 等效旋转因子计算单元，用于并行读取输入旋转因子与输出旋转因子，并将所述二者对应项进行相乘，将乘积结果连同所述输入旋转因子作为等效旋转因子；

[0052] 缓存单元，用于将由所述等效旋转因子计算单元得到的所述等效旋转因子与输入数据相乘，并对乘积结果进行缓存；

[0053] 数据处理单元，用于在第二重循环中，在所述缓存单元执行乘法运算时，将所述缓存单元中缓存的结果读出，并进行相应的加法或减法操作。

[0054] 进一步地，所述等效旋转因子计算单元具体可以包括：

[0055] 并行读入模块，用于并行读入所述输入旋转因子及所述输出旋转因子；

[0056] 缓存模块，用于将所述输入旋转因子与所述输出旋转因子对应项进行相乘，得到第一和第二组等效旋转因子，并将所述第一和所述第二组等效旋转因子连同作为第三组等效旋转因子的所述输入旋转因子存入缓存。

[0057] 进一步地，所述数据处理单元还可以包括：

[0058] 复数运算单元，用于将所述缓存单元中缓存的结果读出，并进行相应的加法操作。

[0059] 与现有技术相比，上述技术方案至少具有以下有益效果：

[0060] 本发明实施例通过根据待运算级数所对应的点数和已完成级数所对应点数的乘积，来配置两重循环参数；然后，判断最大并行读取数据个数与已完成级数所对应点数的乘积之间的大小；最后，基于判断结果，根据判断结果计算与之相对应的两重循环参数，并基于计算得到的两重循环参数并行读取数据。由此，通过对点数相关信息进行计算，配置两重循环参数，当处理器的位宽一定时，根据点数与运算级数以最大并行度读取数据，并且数据间不相关，在运算时无需专门对数据进行重排操作，无需进行横向操作进行处理，提高了处理并行度，减少了运算周期。

[0061] 当然，实施本发明的任一产品不一定需要同时实现以上所述的所有优点。

[0062] 本发明的其它特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明而了解。本发明的目的和其它优点可通过在所写的说明书、权利要求书以及附图中所特别指出的方法来实现和获得。

附图说明

[0063] 附图作为本发明的一部分，用来提供对本发明的进一步的理解，本发明的示意性实施例及其说明用于解释本发明，但不构成对本发明的不当限定。显然，下面描述中的附图仅仅是一些实施例，对于本领域普通技术人员来说，在不付出创造性劳动的前提下，还可以根据这些附图获得其他附图。在附图中：

[0064] 图1为根据一示例性实施例示出的混合基DFT和IDFT数据并行读取方法的流程示意图；

[0065] 图2为根据另一示例性实施例示出的混合基DFT和IDFT并行计算方法的流程示意图；

[0066] 图3为根据一示例性实施例示出的并行读取输入旋转因子与输出旋转因子，并将二者对应项进行相乘，将乘积结果连同输入旋转因子作为等效旋转因子的流程示意图；

[0067] 图4为根据一示例性实施例示出的混合基DFT和IDFT数据并行读取装置的结构示意图；

[0068] 图5为根据一示例性实施例示出的混合基DFT和IDFT并行计算装置的结构示意图。

[0069] 这些附图和文字描述并不旨在以任何方式限制本发明的保护范围，而是通过参考特定实施例为本领域技术人员说明本发明的概念。

具体实施方式

[0070] 下面结合附图以及具体实施例对本发明实施例解决的技术问题、所采用的技术方案以及实现的技术效果进行清楚、完整的描述。显然，所描述的实施例仅仅是本申请的一部分实施例，并不是全部实施例。基于本申请中的实施例，本领域普通技术人员在不付出创造性劳动的前提下，所获的所有其它等同或明显变型的实施例均落在本发明的保护范围内。本发明实施例可以按照权利要求中限定和涵盖的多种不同方式来具体化。

[0071] 需要说明的是，在下面的描述中，为了方便理解，给出了许多具体细节。但是很明显，本发明的实现可以没有这些具体细节。

[0072] 还需要说明的是，在没有明确限定或不冲突的情况下，本发明中的各个实施例及其中的技术特征可以相互组合而形成技术方案。

[0073] 本发明实施例应用的环境为移动通信领域的LTE系统，其中，上行发送端传输预编码模块为DFT过程，对应的接收端为IDFT(离散傅里叶反变换)过程。

[0074] 根据分配资源数不同，进行DFT/IDFT的点数N满足以下关系：

[0075] N＝2α×3β×5γ，12≤N≤1536，α≥2，β≥1，γ≥0

[0076] 具体实现时，2α点的DFT可采用FFT完成，剩余基3、基5的DFT过程则需使用混合基DFT完成。其中，混合基DFT需进行β次基3运算及γ次基5运算，且采用先基3后基5的顺序完成。

[0077] 图1示例性地示出了一种混合基DFT/IDFT数据并行读取方法。如图1所示，该方法可以包括：

[0078] S100：根据待运算级数所对应的点数和已完成级数所对应点数的乘积，来配置两重循环参数。

[0079] S110：判断最大并行读取数据个数与已完成级数所对应点数的乘积之间的大小。

[0080] S120：根据判断结果计算与之相对应的两重循环参数，并基于计算得到的两重循环参数并行读取数据。

[0081] 本发明实施例通过对点数相关信息进行计算，配置两重循环参数，当处理器的位宽一定时以最大并行度读取数据，从而提高了处理并行度。

[0082] 作为本实施例的一种可选的实现方式，根据待运算级数所对应的点数和已完成级数所对应点数的乘积，来配置两重循环参数具体可以包括：根据待运算级数所对应的点数和已完成级数所对应点数的乘积，配置如下两重循环参数：第一重循环步长为N1，第一重循环次数为N0，第二重循环步长为N2，第二重循环次数为 其中，N0表示待运算级数所对应的点数，N1表示已完成级数所对应点数的乘积，N2为N1与N0的乘积。

[0083] 作为本实施例的一种可选的实现方式，基于判断结果，根据该判断结果计算与之相对应的两重循环参数，并基于计算得到的两重循环参数并行读取数据具体可以包括：

[0084] 在M小于等于N1的情况下，不处理所读取的旋转因子，计算以下循环参数：

[0085] 第一重循环步长为M、第一重循环次数为 第二重循环步长为N2、第二重循环次数为 其中，M表示处理器所支持的最大并行读取数据个数，N0表示待运算级数所对应的点数，N1表示已完成级数所对应点数的乘积，N2为N1与N0的乘积；

[0086] 根据上述循环参数并行读取数据，且每次读取M个数据，直至将N1个数据全部读出。

[0087] 本发明实施例通过对点数相关信息进行计算，配置两重循环参数，当处理器得位宽一定时以最大并行度读取数据，并且数据间不相关，无需进行横向操作处理，从而提高了处理并行度。

[0088] 作为本实施例的一种可选的实现方式，基于判断结果，根据该判断结果计算与之相对应的两重循环参数，并基于计算得到的两重循环参数并行读取数据具体还可以包括：

[0089] 在M大于N1的情况下，计算 值，将所读取的旋转因子复制 份，并根据以下循环参数以N2步长并行读取前 组数据：第一重循环步长为 第一重循环次数为N0、第二重循环步长为 第二重循环次数为 其中，M表示
处理器所支持的最大并行读取数据个数，N0表示待运算级数所对应的点数，N1表示已完成级数所对应点数的乘积，N2为N1与N0的乘积。

[0090] 本发明实施例通过对点数相关信息进行计算，配置两重循环参数，当处理器得位宽一定时以最大并行度读取数据，并且数据间不相关，无需进行横向操作处理，从而提高了处理并行度。

[0091] 本发明实施例可以基于任意混合基过程，鉴于混合基理论可能取任意数，不可能穷尽举例，所以，下面通过优选的方式以基3为例来详细说明本发明。

[0092] 假设：N0表示待运算级数所对应的点数；N1表示已完成级数所对应点数的乘积；M表示处理器所支持的最大并行读取数据个数(可以取为16)；N表示DFT点数(可以取为1200点)。

[0093] S200：计算N0和N1，N0＝3，N1＝16，并根据N0和N1来确定循环参数，其中，循环参数包括第一重循环步长及循环次数、第二重循环步长及循环次数。

[0094] 在本步骤中，N2为N1与N0的乘积，第一重循环步长为N1，第一重循环次数为N0，第二重循环步长为N2，第二重循环次数为 由此通过计算可以得出：N2＝48，第一重循环步长为16，第一重循环次数为3；第二重循环步长为48，第二重循环次数为25。

[0095] S210：判断M与N1大小关系。如果M小于等于N1，则执行步骤S211；否则，执行步骤S212。

[0096] S211：不处理所读取的旋转因子，根据以下循环参数并行读取数据，且每次读取M个数据，直到将N1个数据全部读出：

[0097] 第一重循环步长为M、重复次数为 第二重循环步长为N2、重复次数为

[0098] 此时并行度为16，带宽利用率为1。在本步骤中，第二重循环参数是不变的。在实际应用中，第一重循环参数和第二重循环参数可以根据处理器的位宽进行调整。

[0099] S212：计算 值，将所读取的旋转因子复制 份，并根据以下循环参数以N2步长并行读取前 组数据：第一重循环步长为 第一重循环次数为N0、第二重循环步长为 第二重循环次数为

[0100] 此时的并行度为

[0101] 基于上述实施例，本发明实施例还提出一种混合基DFT/IDFT并行计算方法。如图2所示，该方法可以通过步骤S300至步骤S320来实现。

[0102] S300：并行读取输入旋转因子与输出旋转因子，并将二者对应项进行相乘，将乘积结果连同输入旋转因子作为等效旋转因子。

[0103] 具体地，如图3所示，本步骤可以包括：步骤S301和步骤S302。

[0104] S301：并行读入输入旋转因子及输出旋转因子。

[0105] S302：将输入旋转因子与输出旋转因子对应项进行相乘，得到第一和第二组等效旋转因子，并将第一和第二组等效旋转因子连同作为第三组等效旋转因子的输入旋转因子存入缓存。

[0106] 下面通过优选的方式以基3为例来详细说明得到等效旋转因子的过程。

[0107] S401：并行读入输入旋转因子 及输出旋转因子 和其中，W为旋转因子标记；k为进行基N操作的数据大小，取值为0,1,……N-
1。

[0108] S402：将输入旋转因子与输出旋转因子对应项进行相乘，得到第一和第二组等效旋转因子：

[0109] 并将第一和第二组等效旋转因子连同作为第三组等效旋转因子的输入旋转因子存入缓存。

[0110] 其中，可以根据以下方式进行缓存：不单独存储输入旋转因子与输出旋转因子恒为1的因子。输入旋转因子根据数据不同需存储(N0-1)×N1个不同数据，输出旋转因子仅有(N0-1)×(N0-1)个不同数据，对应相乘结果为(N0-1)×(N0-1)×N1个不同数据。

[0111] S310：将等效旋转因子与输入数据相乘，并对乘积结果进行缓存。

[0112] 具体地，以基3为例，本步骤将步骤S302得到的两组等效旋转因子和 以及输入旋转因 子
作为三组等效旋转因子与输入数据相乘。

[0113] 其中，乘法结果为其中，B和C表示输入数据。

[0114] 在一个可选的实施例中，若处理器无复数运算单元，则该步骤将等效旋转因子与输入数据的实部、虚部交叉相乘的结果进行缓存。

[0115] 本步骤在进行计算时，由于每一组运算过程中的旋转因子使用缓存中的等效旋转因子，使得每一组的运算过程仅包含输入数据及旋转因子之间的乘、加运算，每一组运算过程之间无数据前后相关性，并且第二重循环中25次运算该过程仅需执行一次。

[0116] S320：在第二重循环中，执行步骤S310中乘法运算时，将步骤S310缓存的结果读出，并进行相应的加法或减法操作。

[0117] 其中，作为优选实施例之一，以基3为例，在处理器设有复数运算单元的情况下，加法操作可以为其中，A、B和C表示输入数据。

[0118] 本发明实施例将输入与输出旋转因子进行相乘，再通过将计算过程中乘法结果进行缓存，从而将乘、加操作完全分离，降低了整个运算过程中的相关性，提高了流水线利用率，进而提升了运算速率。

[0119] 在一个可选的实施例中，若处理器无复数运算单元，则本步骤包含等效旋转因子和输入数据的实部之间的乘积与等效旋转因子和输入数据的虚部之间的乘积的减法操作。

[0120] 本发明实施例通过将乘、减操作完全分离，从而提高了各部件流水线利用率，进而提升了运算速率。

[0121] 综上所述，本发明实施例在进行计算时，每一组运算过程中先进行等效旋转因子与输入数据的乘法操作，然后将乘积结果全部存入缓存。在下一组运算进行乘法操作时将缓存中的乘积结果数据读出进行加、减操作，以规避数据间相关性产生的运算器空拍。

[0122] 上述实施例中虽然将各个步骤按照上述先后次序的方式进行了描述，但是本领域技术人员可以理解，为了实现本实施例的效果，不同的步骤之间不必按照这样的次序执行，其可以同时(并行)执行或以颠倒的次序执行，这些简单的变化都在本发明的保护范围之内。

[0123] 基于与上述并行读取方法实施例相同的技术构思，本发明实施例还提供一种混合基DFT/IDFT数据并行读取装置。如图4所示，该装置40可以包括点数计算单元42、组数判断单元44和读取单元46。其中，点数计算单元42用于根据待运算级数所对应的点数和已完成级数所对应点数的乘积，来配置两重循环参数。组数判断单元44用于判断最大并行读取数据个数与已完成级数所对应点数的乘积之间的大小。读取单元46用于根据组数判断单元44得到的判断结果计算与之相对应的两重循环参数，并基于计算得到的两重循环参数并行读取数据。

[0124] 本混合基DFT/IDFT数据并行读取装置实施例通过对点数相关信息进行计算，配置两重循环参数，当处理器的位宽一定时，根据点数与运算级数以最大并行度读取数据，并且数据间不相关，提高了处理并行度，减少了运算周期。

[0125] 在上述实施例的基础上，上述点数计算单元42可以进一步包括配置模块。该配置模块用于根据待运算级数所对应的点数和已完成级数所对应点数的乘积，配置如下两重循环参数：第一重循环步长为N1，第一重循环次数为N0，第二重循环步长为N2，第二重循环次数为 其中，N0表示待运算级数所对应的点数，N1表示已完成级数所对应点数的乘积，N2为N1与N0的乘积。

[0126] 在图4所示实施例的基础上，读取单元46可以进一步包括第一计算模块和第一读取模块。其中，第一计算模块用于在M小于等于N1的情况下，不处理所读取的旋转因子，计算以下两重循环参数：

[0127] 第一重循环步长为M、重复次数为 第二重循环步长为N2、重复次数为 其中，M表示处理器所支持的最大并行读取数据个数，N0表示待运算级数所对应的点数，N1表示已完成级数所对应点数的乘积，N2为N1与N0的乘积。第一读取模块用于根据上述两重循环参数并行读取数据，且每次读取M个数据，直至将N1个数据全部读出。

[0128] 在图4所示实施例的基础上，读取单元46还可以进一步包括第二计算模块、复制模块和第二读取模块。其中，第二计算模块用于在M大于N1的情况下，计算 值。复制模块用于复制 份所读取的旋转因子。第二读取模块用于根据以下两重循环参数以N2步长并行读取前 组数据：第一重循环步长为 第一重循环次数为N0、第二重循环步长为 第二重循环次数为 其中，M表示处理器所支持的最大并行读取数据个数，N0表示待运算级数所对应的点数，N1表示已完成级数所对应点数的乘积，N2为N1与N0的乘积。

[0129] 有关该并行读取装置实施例的说明可以参考与之相关的并行读取方法实施例的说明，在此不再赘述。

[0130] 需要说明的是，上述实施例提供的混合基DFT/IDFT数据并行读取装置在进行数据读取时，仅以上述各功能模块的划分进行举例说明，在实际应用中，可以根据需要而将上述功能分配由不同的功能模块来完成，即将装置的内部结构划分成不同的功能模块，以完成以上描述的全部或者部分功能。

[0131] 此外，本发明实施例还提出一种基于上述并行读取装置实施例的混合基DFT/IDFT并行计算装置。该并行计算装置可以执行上述并行计算方法实施例。如图5所示，该装置50可以包括等效旋转因子计算单元52、缓存单元54和数据处理单元56。其中，等效旋转因子计算单元52用于并行读取输入旋转因子与输出旋转因子，并将二者对应项进行相乘，将乘积结果连同输入旋转因子作为等效旋转因子。缓存单元54用于将由等效旋转因子计算单元52得到的等效旋转因子与输入数据相乘，并对乘积结果进行缓存。数据处理单元56用于在第二重循环中，在缓存单元54执行乘法运算时，将缓存单元54中缓存的结果读出，并进行相应的加法或减法操作。

[0132] 本混合基DFT/IDFT并行计算装置实施例在进行运算时优先对旋转因子进行处理，并将乘法运算与加减法运算分离，减少了数据间相关性，以使整体运算空拍减少，提高了流水线利用率，进而可有效提升混合基DFT和IDFT运算速率。

[0133] 在上述实施例的基础上，上述等效旋转因子计算单元52可以进一步包括并行读入模块和缓存模块。其中，并行读入模块用于并行读入输入旋转因子及输出旋转因子。缓存模块用于将输入旋转因子与输出旋转因子对应项进行相乘，得到第一和第二组等效旋转因子，并将第一和第二组等效旋转因子连同作为第三组等效旋转因子的输入旋转因子存入缓存。

[0134] 在上述图5所示实施例的基础上，数据处理单元还可以包括复数运算单元。其中，复数运算单元用于将缓存单元中缓存的结果读出，并进行相应的加法操作。

[0135] 有关该并行计算装置实施例的说明可以参考与之相关的并行计算方法实施例的有关说明，在此不再赘述。

[0136] 需要说明的是，上述实施例提供的混合基DFT/IDFT并行计算装置在进行并行计算时，仅以上述各功能模块的划分进行举例说明，在实际应用中，可以根据需要而将上述功能分配由不同的功能模块来完成，即将装置的内部结构划分成不同的功能模块，以完成以上描述的全部或者部分功能。

[0137] 本领域技术人员可以理解，上述混合基DFT/IDFT数据并行读取装置、混合基DFT/IDFT并行计算装置还包括一些其他公知结构，例如处理器、控制器、存储器等，其中，存储器包括但不限于随机存储器、闪存、只读存储器、可编程只读存储器、易失性存储器、非易失性存储器、串行存储器、并行存储器或寄存器等，处理器包括但不限于CPLD/FPGA、DSP、ARM处理器、MIPS处理器等，为了不必要地模糊本公开的实施例，这些公知的结构未在图4-5中示出。

[0138] 应该理解，图4-5中的各个模块的数量仅仅是示意性的。根据实际需要，可以具有任意数量的各模块。

[0139] 上述装置实施例可以用于执行上述相应的方法实施例，其技术原理、所解决的技术问题及产生的技术效果相似，所属技术领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的装置的具体工作过程及有关说明，可以参考前述方法实施例中的对应过程，在此不再赘述。

[0140] 应指出的是，上面分别对本发明的装置实施例和方法实施例进行了描述，但是对一个实施例描述的细节也可应用于另一个实施例。对于本发明实施例中涉及的模块、步骤的名称，仅仅是为了区分各个模块或者步骤，不视为对本发明的不当限定。本领域技术人员应该理解：本发明实施例中的模块或者步骤还可以再分解或者组合。例如上述实施例的模块可以合并为一个模块，也可以进一步拆分成多个子模块。

[0141] 以上对本发明实施例所提供的技术方案进行了详细的介绍。虽然本文应用了具体的个例对本发明的原理和实施方式进行了阐述，但是，上述实施例的说明仅适用于帮助理解本发明实施例的原理；同时，对于本领域技术人员来说，依据本发明实施例，在具体实施方式以及应用范围之内均会做出改变。

[0142] 需要说明的是，本文中涉及到的流程图或框图不仅仅局限于本文所示的形式，其还可以进行其他划分和/或组合。

[0143] 还需要说明的是：附图中的标记和文字只是为了更清楚地说明本发明，不视为对本发明保护范围的不当限定。

[0144] 再需要说明的是，本发明的说明书和权利要求书及上述附图中的术语“第一”、“第二”等是用于区别类似的对象，而不是用于描述或表示特定的顺序或先后次序。应该理解这样使用的数据在适当的情况下可以互换，以便这里描述的本发明的实施例能够以除了在这里图示或描述的那些以外的顺序实施。

[0145] 术语“包括”、“包含”或者任何其它类似用语旨在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备/装置不仅包括那些要素，而且还包括没有明确列出的其它要素，或者还包括这些过程、方法、物品或者设备/装置所固有的要素。

[0146] 如本文中所使用的，术语“模块”、“单元”可以指代在计算系统上执行的软件对象或例程。可以将本文中所描述的不同模块实现为在计算系统上执行的对象或过程(例如，作为独立的线程)。虽然优选地以软件来实现本文中所描述的系统和方法，但是以硬件或者软件和硬件的组合的实现也是可以的并且是可以被设想的。

[0147] 本发明的各个步骤可以用通用的计算装置来实现，例如，它们可以集中在单个的计算装置上，例如：个人计算机、服务器计算机、手持设备或便携式设备、平板型设备或者多处理器装置，也可以分布在多个计算装置所组成的网络上，它们可以以不同于此处的顺序执行所示出或描述的步骤，或者将它们分别制作成各个集成电路模块，或者将它们中的多个模块或步骤制作成单个集成电路模块来实现。因此，本发明不限于任何特定的硬件和软件或者其结合。

[0148] 本发明提供的方法可以使用可编程逻辑器件来实现，也可以实施为计算机程序软件或程序模块(其包括执行特定任务或实现特定抽象数据类型的例程、程序、对象、组件或数据结构等等)，例如根据本发明的实施例可以是一种计算机程序产品，运行该计算机程序产品使计算机执行用于所示范的方法。所述计算机程序产品包括计算机可读存储介质，该介质上包含计算机程序逻辑或代码部分，用于实现所述方法。所述计算机可读存储介质可以是被安装在计算机中的内置介质或者可以从计算机主体上拆卸下来的可移动介质(例如：采用热插拔技术的存储设备)。所述内置介质包括但不限于可重写的非易失性存储器，例如：RAM、ROM、快闪存储器和硬盘。所述可移动介质包括但不限于：光存储介质(例如：CD－ROM和DVD)、磁光存储介质(例如：MO)、磁存储介质(例如：磁带或移动硬盘)、具有内置的可重写非易失性存储器的媒体(例如：存储卡)和具有内置ROM的媒体(例如：ROM盒)。

[0149] 本发明并不限于上述实施方式，在不背离本发明实质内容的情况下，本领域普通技术人员可以想到的任何变形、改进或替换均落入本发明的保护范围。