技术领域

本发明涉及数据处理技术领域， 具体涉及数据处理方法和相关装置。 背景技术

目前，在通信领域中的信道估计、信号分析及 信号比较等过程中需要进行 数据处理， 需要广泛的运用到傅立叶分析的方法， 并对傅里叶分析后的数据进 行相应的处理， 使得信道估计、 信号分析等过程得到筒化。 傅里叶分析可以通 过快速傅里叶变换（FFT, Fast Fourier Transform )运算处理单元来实现， 在其 它数据处理领域也有类似应用。

现有的数据处理系统中的 FFT运算处理单元可以通过多种算法 （例如基 2 蝶形运算、 基 4蝶形运算和混合基等算法） 来实现。 但是， 目前蝶形运算资源 利用率还相对较低， 例如 256点数据需要 4级基 4蝶形运算， 则需要耗费 4套运算 电路和存储资源， 资源耗费相对较多。 发明内容

本发明实施例提供一种数据处理方法和相关装 置，以减少对数据进行蝶形 运算所需的资源消耗。

本发明实施例一方面提供一种数据处理方法， 可包括：

将 y路待进行第 z级基 y蝶形运算的数据输入基 y蝶形运算器进行第 z级基 y 蝶形运算， 其中， 所述 y和 z为正整数；

在所述第 z级基 y蝶形运算为最后一级基 y蝶形运算的情况下，输出所述 第 z级基 y蝶形运算得到的结果数据；

在所述第 z级基 y蝶形运算不为最后一级基 y蝶形运算的情况下，将所述 第 z级基 y蝶形运算得到的结果数据，输入所述基 y蝶形运算器进行第 z+1级 基 y蝶形运算。

本发明实施例另一方面还提供一种数据处理装 置， 包括：

控制器和基 y蝶形运算器；

其中， 所述控制器， 用于将 y路待进行第 z级基 y蝶形运算的数据输入所 述基 y蝶形运算器进行第 z级基 y蝶形运算，在所述第 z级基 y蝶形运算为最 后一级基 y蝶形运算的情况下，输出所述第 z级基 y蝶形运算得到的结果数据； 在所述第 z级基 y蝶形运算不为最后一级基 y蝶形运算的情况下， 将所述第 z 级基 y蝶形运算得到的结果数据， 输入所述基 y蝶形运算器进行第 z+1级基 y 蝶形运算， 其中， 所述 y和 z为正整数。

本发明实施例另一方面还提供一种接入设备， 所述接入设备中部署有如上 述实施例所述的数据处理装置。

本发明实施例另一方面还提供一种用户设备， 所述用户设备中部署有如上 述实施例所述的数据处理装置。

本发明实施例另一方面还提供一种计算机存储 介质，

所述计算机存储介质存储有程序，所述程序执 行时包括如上述数据处理方 法的部分或全部步骤。

由上可见， 本发明实施例将 y路待进行第 z级基 y蝶形运算的数据， 输入基 y 蝶形运算器进行第 z级基 y蝶形运算， 在该第 z级基 y蝶形运算为最后一级基 y蝶 形运算的情况下， 输出该第 z级基 y蝶形运算得到的结果数据； 在该第 z级基 y 蝶形运算不为最后一级基 y蝶形运算的情况下， 将该第 z级基 y蝶形运算得到的 结果数据，输入该基 y蝶形运算器进行第 z+1级基 y蝶形运算。 由于该机制对基 y 蝶形运算器进行了复用， 两级基 y蝶形运算复用同一个基 y蝶形运算器， 例如可 利用数据输入的时间复用基 y蝶形运算器进行运算， 故而有利于减少蝶形运算 的时间并减少资源消耗。 附图说明

为了更清楚地说明本发明实施例技术方案，下 面将对实施例和现有技术描 述中所需要使用的附图作筒单地介绍， 显而易见地， 下面描述中的附图仅仅是 本发明的一些实施例，对于本领域普通技术人 员来讲，在不付出创造性劳动性 的前提下， 还可以根据这些附图获得其它的附图。

图 1-a是本发明实施例提供的一种基 2蝶形运算模型示意图；

图 1-b是本发明实施例提供的一种基 4蝶形运算模型示意图；

图 2是本发明实施例提供的一种 4级基 4蝶形运算电路的架构示意图； 图 3是一种移位寄存器的读写操作的示意图；

图 4是本发明实施例提供的一种数据处理方法的� �意图；

图 5是本发明实施例提供的一种数据处理装置的� �意图；

图 6是本发明实施例提供的一种移位寄存器操作� �示意图；

图 7-a是本发明实施例提供的一种蝶形运算顺序安 排的示意图；

图 7-b是本发明实施例提供的另一种蝶形运算顺序 安排的示意图； 图 8-a是本发明实施例提供的一种数据处理装置的 示意图；

图 8-b是本发明实施例提供的另一种数据处理装置 的示意图；

图 9是本发明实施例提供的一种电子设备的示意� �。

具体实施方式

本发明实施例提供一种数据处理方法和相关装 置，以减少对数据进行蝶形 运算所需的资源消耗。

为使得本发明的发明目的、 特征、 优点能够更加的明显和易懂， 下面将结 合本发明实施例中的附图，对本发明实施例中 的技术方案进行清楚、 完整地描 述， 显然， 下面所描述的实施例仅仅是本发明一部分实施 例， 而非全部的实施 例。基于本发明中的实施例， 本领域普通技术人员在没有做出创造性劳动前 提 下所获得的所有其它实施例， 都属于本发明保护的范围。

首先， 由 FFT公式可推得：

W— 1

N ,

2 N

j kn

[x(n) +W _N N

n=0

.2π j

, - /—— kn _k N r i i,,kc为偶数

w ^kn = _e N

其中， W _N ² = (-l = k k为为奇苛数数 ， Q≤k≤N - 1 为待 _FFT 运算的数据， 为 O)的 _FFT 运算结果数据， N为待

FFT运算的数据的点数。 其中， 由上可得基 2蝶形运算方式可如图 1-a所示。

可以理解， 2^、数据的 FFT流水可由 k级基 2蝶形运算级联得到；

两级基 2蝶形运算等价于一级基 4蝶形运算， 基 4蝶形运算将 N点输入数据 等分成 4部分，每次取各部分的相应数据进行计算，� � 4蝶形运算方式可如图 1-b 所示。 其中， ^点数据进行？？！^运算， 需 k级基 4蝶形运算级联， 例如 256点数据 FFT运算需要 4级基 4蝶形。

参见图 2, 图 2是举例的一种 4级基 4蝶形运算电路的架构示意图。一般在对 数据进行基 4蝶形运算过程中， 假设有 N点数据需要进行基 4蝶形运算， 且写入 1点数据需要 1个时钟， 则前 3N/4个周期将 3N/4点数据依次存入三个移位寄存 器， 输入最后 N/4点数据开始， 基 4蝶形运算电路开始对数据进行运算， 如此则 基 4蝶形运算电路有近 3/4的时间处于闲置状态， 运算资源利用率相对较低， 例 如 256点数据需要 4级基 4蝶形运算， 则需要耗费 4套运算电路和存储资源， 资源 耗费相对较多。

为便于理解图 2所示架构的工作机制，下面以进行一级基 4蝶形运算过程为 例， 输入共 N点数据， 假设每个时钟输入一点数据， 需要 N个时钟周期； 前 N/4 个时钟周期， 将输入数据緩存至移位寄存器（R0 ); N/4~N/2个时钟周期， 将 输入数据緩存至移位寄存器（ R1 ); N/2~3N/4个时钟周期， 将输入数据緩存至 移位寄存器（R2 ); 最后 N/4个周期， 同时从三个移位寄存器中读出数据并与 最后的 N/4个数据同步输入到基 4蝶形运算器进行蝶形运算， 运算同时得到 4路 N/4个数据， 需要继续做 N/4点的 FFT运算， 将运算得到的第一路 N/4送往后级 蝶形运算器， 其余三路回写到本级蝶形运算器的对应緩存中 ， 等第一路的运算 结果 N/4个数据全部送到后级基 4蝶形运算器后， 再从移位寄存器 -0读出 N/4个 数据送往后级基 4蝶形运算器， 然后再从移位寄存器 -1读取对应 N/4个数据送往 后级基 4蝶形运算器，之后再从移位寄存器 -2读取对应数据送往后级基 4蝶形运 算器， 以此类推。

下面以后级做 8点数据的基 4蝶形运算为例， 对移位寄存器的操作可如图 3 示。 如图 3中 P1~P6状态所示， A1~A8为 8点数据， A_1~A_8为 A1~A8经过基 4 蝶形运算后的数据， 前 3N/4个周期将数据依次存入 3个移位寄存器（此处以用 移位寄存器实现为例）， 后 N/4个周期 （P7, P8 ) 完成蝶形运算， A7和 A8不送 移位寄存器， 而是直接同之前保存的数据送往基 4蝶形运算器。 每次运算后将 得到的 4个结果数据中的后 3个送回移位寄存器 （即回填， 如 P8所示）， 将第 1 个（即 A_l , A_2 )送入下 1级进行基 4蝶形运算（如 P9 )。 然后依次从 3个移位 寄存器取出 N/4个数据送入下一级基 4蝶形运算器运算， 此时， 可同时往移位寄 存器写入下一组的 N点输入数据 （即 B1~B8, 如 P10和 P11所示）。

其中， 图 3中， P1~P6为数据准备阶段， 此时基 4蝶形运算器空闲， P7~P9 为数据运算阶段， P10~P11为数据回写状态。 其它点数的数据的计算过程则以 此类推。

本发明实施例提出的方案有利于减少对数据进 行蝶形运算所需的资源消 耗。

下面通过具体实施例， 分别进行详细的说明。 本发明的数据处理方法的一个实施例， 其中， 该方法可包括： 将 y路待进 行第 z级基 y蝶形运算的数据， 输入基 y蝶形运算器进行第 z级基 y蝶形运算， 其 中， 该 y和 z为正整数； 在该第 z级基 y蝶形运算为最后一级基 y蝶形运算的情况 下， 输出该第 z级基 y蝶形运算得到的结果数据； 在该第 z级基 y蝶形运算不为最 后一级基 y蝶形运算的情况下， 将该第 z级基 y蝶形运算得到的结果数据， 输入 该基 y蝶形运算器进行第 z+ 1级基 y蝶形运算。

参见图 4, 本发明实施例提供的一种数据处理方法， 可包括以下内容： 401、 将 y路待进行第 z级基 y蝶形运算的数据， 输入基 y蝶形运算器进行第 z 级基 y蝶形运算；

可以理解， y和 z为正整数。 假设需 256点（ 4 ⁴ )数据进行 FFT运算， 若是通 过基 2蝶形运算来进行 FFT运算， 则 y为 2, 若是通过基 4蝶形运算来进行 FFT运 算， 则 y为 4; 若是通过基 3蝶形运算来进行 FFT运算， 则 y为 3; 若是通过基 8蝶 形运算来进行 FFT运算， 则 y为 8; 若是通过基 16蝶形运算来进行 FFT运算， 贝' Jy 为 16, 以此类推。

在本发明的一些实施例中， 例如存在 N点 FFT运算， 若采用基 y蝶形运算器 进行处理， 则共需要进行 M ( M = log _y N )级基 y蝶形运算， z小于等于^1。 一般 的， 此处 N为 2正整数次幂， 当 N不为 2的正整数次幂时， 可将 N补充为 2的正整 数次幂， 例如可通过补 0法等， 在原有 N点数据的基础上补若干个 0, 使得补 0 后的数据总点数为 2的正整数次幂。

402、在该第 z级基 y蝶形运算为最后一级基 y蝶形运算的情况下， 输出该第 z级基 y蝶形运算得到的结果数据； 在该第 z级基 y蝶形运算不为最后一级基 y蝶 形运算的情况下， 将该第 z级基 y蝶形运算得到的结果数据， 输入该基 y蝶形运 算器进行第 z+1级基 y蝶形运算。

可以看出， 本实施例中将 y路待进行第 z级基 y蝶形运算的数据， 输入基 y 蝶形运算器进行第 z级基 y蝶形运算， 在该第 z级基 y蝶形运算为最后一级基 y蝶 形运算的情况下， 输出该第 z级基 y蝶形运算得到的结果数据； 在该第 z级基 y 蝶形运算不为最后一级基 y蝶形运算的情况下， 将该第 z级基 y蝶形运算得到的 结果数据，输入该基 y蝶形运算器进行第 z+1级基 y蝶形运算。 由于该机制对基 y 蝶形运算器进行了复用， 两级基 y蝶形运算复用同一个基 y蝶形运算器， 例如可 利用数据输入的时间复用基 y蝶形运算器进行运算， 故而有利于减少蝶形运算 的时间并减少资源消耗。

在本发明的一些实施例中， 还可以引入緩存器来存储基 y蝶形运算的中间 结果数据等。 举例来说， 在上述第 z级基 y蝶形运算不为最后一级基 y蝶形运算 的情况下， 可将该第 z级基 y蝶形运算的得到的 y路结果数据中的每路结果数据 等分为 y个部分， 并将该 y个部分分别写入 y个緩存区中； 而后将分别写入到该 y 个緩存区中的该每路结果数据所等分为的 y个部分，作为 y路待进行第 z+1级基 y 蝶形运算的数据， 输入该基 y蝶形运算器进行第 z+ 1级基 y蝶形运算。

此外，在第 z+1级基 y蝶形运算为最后 1级基 y蝶形运算的情况下， 可输 出上述第 z+1级基 y蝶形运算的结果数据；而在该第 z+1级基 y蝶形运算不为 最后一级基 y蝶形运算的情况下，又可将该第 z+1级基 y蝶形运算得到的结果 数据， 输入上述基 y蝶形运算器（或其它基 y蝶形运算器 )进行第 z+2级基 y 蝶形运算。其中，在上述第 z+1级基 y蝶形运算不为最后一级基 y蝶形运算的 情况下，例如可将该第 z+1级基 y蝶形运算的得到的 y路结果数据中的每路结 果数据等分为 y个部分， 并将该 y个部分分别写入 y个緩存区中； 而后将分别 写入到该 y个緩存区中的该每路结果数据所等分为的 y个部分，作为 y路待进 行第 z+2级基 y蝶形运算的数据， 输入该基 y蝶形运算器进行第 z+2级基 y 蝶形运算， 若结果数据后续还需进行基 y蝶形运算， 可据此循环处理以完成所 有级的基 y蝶形运算。

其中， 上述 y个緩存区可分别位于 y个緩存器中； 或者， 该 y个緩存区也可 位于至少一个緩存器中， 其中， 该緩存器例如可选用移位緩存器（例如移位寄 存器或其它移位緩存器）。

可以理解， 若进行本级基 y蝶形运算后还未能得到 FFT运算结果， 即在本 级基 y蝶形运算不是最后一级基 y蝶形运算的情况下， 可基于上述机制循环处 理， 分别从上述 y个緩存区中读取出， 写入该 y个緩存区到中的本级基 y蝶形运 算的结果数据中的每路结果数据所等分为的 y个部分， 将该 y个部分作为 y路待 进行下 1级基 y蝶形运算的数据， 输入该基 y蝶形运算器进行下一级基 y蝶形运 算， 据此循环处理最终将得到数据的 FFT运算结果。

举例来说， 以对 256点 （4 ⁴ 点）数据进行 FFT运算为例， 256点 （ 4 ⁴ )数据 需要进行 4级基 4蝶形运算。 其中， 第 1级将 256点数据进行基 4蝶形运算， 得到 64点数据 /组的 4组数据； 第 2级将 64点数据 /组的 4组数据进行基 4蝶形运算， 得 到 16点数据 /组的 16组数据； 而第 3级将 16点数据 /组的 16组数据进行基 4蝶形运 算， 得到 4点数据 /组的 64组数据； 而第 4级将 4点数据 /组的 64组数据进行基 4蝶 形运算， 得到 256点数据的 FFT运算结果。 可以理解， 其它点数的数据的 FFT 运算方式以此类推。

参见图 5 , 图 5中的数据处理运算装置包括： 4个深度至少为 64 (即至少存 储 64点数据） 的移位寄存器和一个基 4蝶形运算器， 每次完成运算后将运算结 果数据写回该移位寄存器中， 当下一级基 4蝶形运算开始时， 再从该移位寄存 器中读取待进行下级基 4蝶形运算的数据进行下级基 4蝶形运算， 直到得到 FFT 运算结果输出。

在本发明的一些实施例中， 例如可以在所有待进行每级基 y蝶形运算的数 据都进行该级基 y蝶形运算后，再进行所有待进行下一级基 y蝶形运算的数据的 下一级基 y蝶形运算。

举例来说， 在进行上述第 z+1级基 y蝶形运算得到的 y*y路第 z+1级基 y 蝶形运算的结果数据之后，在第 z+1级基 y蝶形运算不是最后一级基 y蝶形运 算的情况下，可将该 y*y路第 z+1级基 y蝶形运算的结果数据中的每路结果数 据等分为 y个部分，将该 y个部分作为 y路待进行第 z+2级基 y蝶形运算的数 据， 输入上述基 y蝶形运算器（或其它蝶形运算器 )进行第 z+2级基 y蝶形运 算， 例如， 可将该第 z+1级基 y蝶形运算的得到的 y*y路结果数据中的每路结 果数据等分为 y个部分， 并将该 y个部分分别写入 y个緩存区中； 而后将分别 写入到该 y个緩存区中的该每路结果数据所等分为的 y个部分，作为 y路待进 行第 z+2级基 y蝶形运算的数据， 输入该基 y蝶形运算器进行第 z+2级基 y 蝶形运算， 若第 z+2级基 y蝶形运算的结果数据还需进行基 y蝶形运算， 可据 此循环处理以完成所有级的基 y蝶形运算，所有待进行每级基 y蝶形运算的数 据都进行该级基 y蝶形运算后，再进行所有待进行下一级基 y蝶形运算的数据 的下一级基 y蝶形运算。 以对 256点 （4 ⁴ 点）数据进行 FFT运算为例， 256点数据需要进行 4级基 4蝶 形运算， 其中， 第 1级完成 256点数据的基 4蝶形运算后得到 64点数据 /组的 4组 数据； 而后进行第 2级 64点数据 /组的 4组数据的基 4蝶形运算（其中， 64点数据 /组的 4组数据中的每组数据被等分为的 4个部分， 每组数据都被等分为的 4个部 分作为 4路待进行第 2级基 4蝶形运算的数据，输入基 4蝶形运算器进行第 2级基 4 蝶形运算），得到 16点数据 /组的 16组数据； 在 64点数据 /组的 4组数据的基 4蝶形 运算都完成之后， 再进行第 3级的 16点数据 /组的 16组数据的基 4蝶形运算， 得 到 4点数据 /组的 64组数据； 在 16点数据 /组的 16组数据的基 4蝶形运算都完成之 后， 再进行第 4级的 4点数据 /组的 64组数据的基 4蝶形运算， 得到 256点数据的 FFT运算结果。 其它点数的数据的 FFT运算方式以此类推。

在本发明的另一些实施例中， 例如也可以在先将待进行第 k级（如第 2 或第 3级或非最后 1级的其它级）基 y蝶形运算的数据的划分为几个部分（例 如 2个部分、 3个部分或更多部分），先进行其中的某部分� �据的该第 k级基 y 蝶形运算， 直到该某部分数据的剩余所有级的基 y蝶形运算都计算完成后，再 进行待进行第 k级基 y蝶形运算的数据的另一部分的第 k级基 y蝶形运算，直 到该另一部分数据的剩余所有级的基 y蝶形运算都计算完成，若还有在待进行 第 k级的再一部分数据，再进行该待进行第 k级基 y蝶形运算的数据的再一部 分的第 k级基 y蝶形运算，直到该再一部分数据的剩余所有� �的基 y蝶形运算 都计算完成， 以此类推， 最终完成所有数据所有级基 y蝶形运算， 得到 FFT 计算结果。

例如， 先将 y路数据进行第 z级基 y蝶形运算得到的 y路结果数据中， 先 写入到 y个緩存区的其中 m路结果数据（写入到 y个緩存区的结果数据也就 是先计算出的结果数据）的每路数据所分别等 分为的 y个部分，作为 y路待进 行第 z+1级基 y蝶形运算的数据以输入上述基 y蝶形运算器进行第 z+1级基 y 蝶形运算， 可得到 y*m路第 z+1级基 y蝶形运算的结果数据； 在得到该 y*m 路第 z+1级基 y蝶形运算的结果数据之后，将上述 y路结果数据中，后写入到 该 y个緩存区的剩余 n路结果数据中的每路数据所分别等分为的 y个部分，作 为 y路待进行第 z+1级基 y蝶形运算的数据， 输入该基 y蝶形运算器进行第 z+1级基 y蝶形运算， 可得到 y*n路第 z+1级基 y蝶形运算的结果数据， 其中 上述 m小于 y, 上述 m与 n之和等于 y; 上述 m小于或等于或大于 n。

其中，在第 z+1级基 y蝶形运算不是最后一级基 y蝶形运算的情况下，在 将上述第 z级基 y蝶形运算得到的 y路结果数据中，后写入到该 y个緩存区的 剩余 n路结果数据中的每路结果数据所分别等分为� � y个部分，作为 y路待进 行第 z+1级基 y蝶形运算的数据， 输入所述基 y蝶形运算器进行第 z+1级基 y 蝶形运算之前， 将 y*m路第 z+1级基 y蝶形运算的结果数据中的每路结果数 据等分为 y个部分，将该 y个部分作为 y路待进行第 z+2级基 y蝶形运算的数 据， 输入该基 y蝶形运算器进行第 z+2级基 y蝶形运算， 可得到 y*y*m路第 z+2级基 y蝶形运算的结果数据。

例如， 仍以对 256点（4 ⁴ 点）数据进行 FFT运算为例， 256点数据需要进行 4 级基 4蝶形运算， 其中，在第 1级完成 256点数据的基 4蝶形运算后得到 64点数据 /组的 4组数据； 先进行第 2级 64点数据 /组的 4组数据中的其中两组数据的基 4蝶 形运算，得到 16点数据 /组的 8组数据；在 64点数据 /组的 2组数据的基 4蝶形运算 都完成后， 再进行 16点数据 /组的 8组数据的第 3级基 4蝶形运算， 得到 4点数据 / 组的 32组数据， 而后再进行 4点数据 /组的 32组数据的第 4级基 4蝶形运算， 得到 128点数据的 FFT运算结果； 然后， 在进行第 2级 64点数据 /组的 4组数据中的剩 余两组数据的基 4蝶形运算， 得到 16点数据 /组的 8组数据； 在 64点数据 /组的剩 余 2组数据的基 4蝶形运算都完成后，再进行得到的 16点数据 /组的 8组数据的第 3级基 4蝶形运算， 得到 4点数据 /组的 32组数据， 而后再进行得到的 4点数据 /组 的 32组数据的第 4级基 4蝶形运算， 得到 128点数据的 FFT运算结果， 至此， 256 点数据需要进行的 4级基 4蝶形运算全部完成。 可以理解， 其它点数的数据的 FFT运算方式可以此类推。

其中， 本发明实施例方案在对待进行同一级基 y蝶形运算的数据进行同一 级基 y蝶形运算的过程中，可将先写入緩存区中的� �据先输入基 y蝶形运算器进 行运算， 将后写入緩存区中的数据后输入基 y蝶形运算器进行运算。

可以理解的是， 上述方案中的步骤可在控制器的控制下实施， 该控制器可 独立于基 y蝶形运算器和緩存器，也可将其部分或全部� �能集成在基 y蝶形运算 器和緩存器中。 为便于更好的理解和实施上述方案，下面以进 行 256点数据的基 4蝶形运算 的过程为例进行描述。

参见图 6,在一种可行的实施方式中， 图 5所示架构的数据处理装置的移位 寄存器存储操作机制可以如下， 其中， 此处主要以每路数据利用不同的緩存器 进行緩存为例进行描述。

首先， 输入 64点数据 /路的 4路数据进行 256点数据的基 4蝶形运算， 得到 4 路计算结果分别存放于四个移位寄存器中 （移位寄存器 R0~ R3 )。

图 6中的 4种底纹分别表示基 4蝶形运算得到的 4路数据。 其中， 同 1路数据 等分成 4份来进行下一级的基 4蝶形运算， 为了能同时的读取同 1路（图中相同 底纹） 的 4份数据进行基 4蝶形运算， 在存放数据时， 每存完 1路的 16个数据后 就可对存储该路数据的移位寄存器进行切换， 最终形成第 1路数据中的前 16个 数据存在移位寄存器 R0的低 16个地址中， 第 1路数据中的第 17~32个数据存在 移位寄存器 R1的地址 16~地址31 , 第 1路数据中的第 33~48个数据存在移位寄存 器 R2的地址 32~地址47,第 1路数据中的第 49~64个数据存在移位寄存器 R3的地 址 48~地址63； 其它路数据（图中其它底纹） 的存储方式以此类推。

当需要进行下级基 4蝶形运算的时候，分别从 4个移位寄存器中读出同一种 底纹的部分送入基 4蝶形运算器， 运算后得到的数据可再存放在读取出来的对 应地址（若移位寄存器足够大， 则运算后得到的数据亦可存放在其它空闲位 置）， 举例来说， 第 1路 64点数据进行基 4蝶形运算后得到的数据， 仍可存储在 移位寄存器 R0的 0~15地址位置、 移位寄存器 R1的 16~31地址位置、 移位寄存器 R 2的 32~47地址位置和移位寄存器 R3的 48~63地址位置， 其它几路的存储方式 以此类推， 即基 4蝶形运算得到的 4路中， 同 1路的数据分成 4份存在不同的移位 寄存器中， 以保证后续能够同时读取出来以进行下级基 4蝶形运算。 第三级和 第四级基 4蝶形运算得到的数据的地址存储方式可以此� �推， 此处不再赘述。

为获得尽量高的运算效率， 还可对基 4蝶形运算优先级顺序进行合理巧妙 的安排。 下面介绍本发明实施例提供的几种安排基 4蝶形运算优先级顺序的方 式。

可以理解，后级蝶形运算的前提是前级蝶形运 算结果已经得到， 考虑到计 算延迟和控制延迟等情况，可根据需要来适当 的安排各路数据进行每级蝶形运 算的先后顺序。

下面以对 256点数据（4 ⁴ )进行 FFT运算为例， 一种蝶形计算的顺序安排例 如图 7-a所示。

①执行 256点的第一级基 4蝶形运算， 得到 64点数据 /路的 4路数据， 需 64个 时钟周期（ _C yd _e );

②执行其中 1路（例如第 1路） 的 64点数据的第二级基 4蝶形运算， 得到 16 点数据 /路的 4路数据， 需 16个 cycle;

③执行上述 16点数据 /路的 4路数据的第三级基 4蝶形运算， 得到 4点数据 / 路的 16路数据， 需 16个 cycle;

④执行上述 16路 4点数据的基 4蝶形运算， 需要 16个 cycle;

至此， 执行 256点的第 1级基 4蝶形运算得到的 4路数据 （64点数据 /路） 的 其中 1路数据计算完毕。 以此类推， 重复执行 3遍步骤②③④， 便可将第 1级基 4 蝶形运算得到的 4路数据得其余三路运算完毕。

假设 64点基 4蝶形运算， 相当于图 5中步骤②中的运算过程， 输入 4路数据 需要 16cycles, 64个数据标号例如可如下：

0、 1、 2、 3、 4、 5、 6、 7、 8、 9、 10、 11、 12、 13、 14、 15

16、 17、 18、 19、 20、 21、 22、 23、 24、 25、 26、 27、 28、 29、 30、 31 32、 33、 34、 35、 36、 37、 38、 39、 40、 41、 42、 43、 44、 45、 46、 47 48、 49、 50、 51、 52、 53、 54、 55、 56、 57、 58、 59、 60、 61、 62、 63 进行基 4蝶形运算得到 4路数据的第 1路数据为例如标记为：

A、 B、 C、 D、 E、 F、 G、 H、 I、 J、 K、 L、 M、 N、 0、 P, 该 16个数据 需要进行下 1级的基 4蝶形运算；

进行下 1级基 4蝶形运算的 4路共 16个输入数据如下：

A、 B、 C、 D

E、 F、 G、 H

1、 J、 K、 L

M、 N、 0、 P 考虑到在进行蝶形运算时加减、旋转因子乘法 需若干个时钟周期，在进行 上述 16点数据的基 4蝶形运算中， 需用到的数据 M、 N、 0、 P是由 64点数据进 行基 4蝶形运算时对应由数据 12、 13、 14、 15、 28、 29、 30、 31、 44、 45、 46 及 47、 60、 61、 62、 63计算产生的， 而刚输入基 4蝶形运算器的这些数据需要 若干时钟周期 （一般大于 4个时钟周期） 才会生成运算结果 M、 N、 0、 P, 因 此， 若从移位寄存器中读得 64点蝶形运算需要的 4路各 16个数后立即进行下一 级 16点基 4运算可能还不行， 因为数据 12、 28、 44、 60输入基 4蝶形运算器才过 了 3个时钟（该 3个时钟为将 13、 14、 15输入基 4蝶形运算器）， 数据 M此时可能 还未能计算得到并存入移位寄存器中， 同理 N、 0、 P此时也未计算完毕。 因此， 可进行一定的延迟处理，使得进行后级蝶形运 算所需数据， 已在相应前级蝶形 运算后得到并存入了移位寄存器中。

下面仍以对 256点数据（4 ⁴ )进行 FFT运算为例， 本发明实施例提供的另一 种蝶形计算的顺序安排例如图 7-b所示。

(1)执行 256点数据第 1级的基 4蝶形运算， 得到 4路（64点数据 /路）待进行 第 2级基 4蝶形运算的数据；

(2)执行步骤 (1)得到的 4路（64点数据 /路）待进行第 2级基 4蝶形运算的数据 中的其中 2路（64点数据 /路）数据的第 2级基 4蝶形运算， 得到 8路（16点数据 / 路）待进行第 3级基 4蝶形运算的数据；

(3)执行步骤 (2)中得到的 8路待进行第 3级基 4蝶形运算数据中的其中 4路（ 16 点数据 /路）数据的第 3级基 4蝶形运算， 得到 16路（4点数据 /路）待进行第 4级 基 4蝶形运算的数据；

(4)执行步骤 (3)得到的 16路（4点数据 /路）数据的第 4级基 4蝶形运算， 得到 64个输出数据 （FFT运算结果）。

其中， 步骤 (1)执行 1次， 而后再执行 1次步骤 (2)(3)(4), 而后再执行 1次步骤 (3)(4), 而后再执行 1次步骤 (2)(3)(4), 而后在再执行 1次 (3)(4), 至此， 所有数据均 完成运算输出运算结果。

在步骤 (2)中用了 32个 cycle,先将 256点数据进行第一级基 4蝶形运算得到的 4路数据 （64点数据 /路） 中的其中两路执行其对应的后级基 4蝶形运算， 而后 再对 256点数据进行第 1级基 4蝶形运算得到的 4路数据 （ 64点数据 /路） 中的另 外两路执行其对应的后级基 4蝶形运算。 如此， 既能够保证下 1级的基 4蝶形运 算的执行是在当前级运算结果存入移位寄存器 后才进行，同时又充分利用了基 4蝶形运算器的工作周期， 减少了闲置时间， 较大的提高了运算效率。

可以理解的是， 上述举例主要是以对数据进行基 4蝶形运算为例来进行描 述的， 而对数据进行其它蝶形运算的过程可以此类推 ， 此处不再赘述。 可以利 用控制器来控制本发明实施例上述方案的执行 ，该控制器例如可独立部署并与 各个緩存区和基 y蝶形运算器连接，或者也可直接部署于緩存� �或基 y蝶形运算 器中。

由上可见， 本实施例中将 y路待进行第 z级基 y蝶形运算的数据， 输入基 y 蝶形运算器进行第 z级基 y蝶形运算， 在该第 z级基 y蝶形运算为最后一级基 y蝶 形运算的情况下， 输出该第 z级基 y蝶形运算得到的结果数据； 在该第 z级基 y 蝶形运算不为最后一级基 y蝶形运算的情况下， 将该第 z级基 y蝶形运算得到的 结果数据，输入该基 y蝶形运算器进行第 z+1级基 y蝶形运算。 由于该机制对基 y 蝶形运算器和緩存区进行了复用， 两级基 y蝶形运算复用同一个基 y蝶形运算 器， 例如可利用数据输入的时间复用基 y蝶形运算器进行运算， 故而有利于减 少蝶形运算的时间并减少资源消耗。

并且， 通过巧妙安排数据的各级基 y蝶形运算顺序， 有利于减少延迟等待 时间， 进一步提高运算效率。 为便于更好的实施本发明实施例的相关装置， 本发明实施例还提供用于实 施上述方案的相关装置。

参见图 8-a, 本发明实施例提供一种数据处理装置 800, 可包括：

控制器 810和基 y蝶形运算器 820;

其中控制器 810, 用于控制将 y路待进行第 z级基 y蝶形运算的数据， 输入基 y蝶形运算器 820进行第 z级基 y蝶形运算， 其中， 该 y和 z为正整数； 在该第 z级 基 y蝶形运算为最后一级基 y蝶形运算的情况下，输出该第 z级基 y蝶形运算得到 的结果数据； 在该第 z级基 y蝶形运算不为最后一级基 y蝶形运算的情况下， 将 该第 z级基 y蝶形运算得到的结果数据， 输入该基 y蝶形运算器 820进行第 z+1级 基 y蝶形运算。

参见图 8-b , 在本发明的一些实施例中， 数据处理装置 800还可包括 y个緩 存区 830;

控制器 810还可进一步用于，在将 y路待进行第 z级基 y蝶形运算的数据输入 基 y蝶形运算器 820进行第 z级基 y蝶形运算， 得到 y路第 z级基 y蝶形运算的结果 数据之后， 将该第 z级基 y蝶形运算得到的 y路结果数据中的每路结果数据等分 为 y个部分， 并将该 y个部分分别写入 y个緩存区 830中。

在本发明的一些实施例中， 控制器 810可具体用于， 将 y路待进行第 z级基 y 蝶形运算的数据输入基 y蝶形运算器 820进行第 z级基 y蝶形运算， 在第 z级基 y 蝶形运算为最后一级基 y蝶形运算的情况下， 输出第 z级基 y蝶形运算得到的结 果数据； 在第 z级基 y蝶形运算不为最后一级基 y蝶形运算的情况下， 将第 z级基 y蝶形运算得到的 y路结果数据中的每路结果数据等分为 y个部分，并将 y个部分 分别写入 y个緩存区 830中，将分别写入到 y个緩存区 830中的该每路结果数据所 等分为的 y个部分， 作为 y路待进行第 z+1级基 y蝶形运算的数据， 输入该基 y蝶 形运算器 820进行第 z+1级基 y蝶形运算， 其中， y和 z为正整数。

在本发明的一些实施例中， 控制器 810 例如可以控制在先将待进行第 k 级（如第 2或第 3级或非最后 1级的其它级）基 y蝶形运算的数据的划分为几 个部分（例如 2个部分、 3个部分或更多部分）， 先进行其中的某部分数据的 该第 k级基 y蝶形运算，直到该某部分数据的剩余所有级� �基 y蝶形运算都计 算完成后， 再进行待进行第 k级基 y蝶形运算的数据的另一部分的第 k级基 y 蝶形运算， 直到该另一部分数据的剩余所有级的基 y蝶形运算都计算完成， 若 还有在待进行第 k级的再一部分数据，再进行该待进行第 k级基 y蝶形运算的 数据的再一部分的第 k级基 y蝶形运算，直到该再一部分数据的剩余所有� �的 基 y蝶形运算都计算完成，以此类推，最终完成� �有数据所有级基 y蝶形运算， 得到 FFT计算结果。

举例来说，控制器 810可具体用于， 将 y路待进行第 z级基 y蝶形运算的 数据输入基 y蝶形运算器 820进行第 z级基 y蝶形运算，在第 z级基 y蝶形运 算为最后一级基 y蝶形运算的情况下，输出该第 z级基 y蝶形运算得到的结果 数据； 在该第 z级基 y蝶形运算不为最后一级基 y蝶形运算的情况下， 将该第 z级基 y蝶形运算得到的 y路结果数据中的每路结果数据等分为 y个部分， 并 将该 y个部分分别写入 y个緩存区 830中； 先将该 y路结果数据中，先写入到 该 y个緩存区 830的其中 m路结果数据中的每路结果数据所分别等分为� � y 个部分，作为 y路待进行第 z+1级基 y蝶形运算的数据以输入该基 y蝶形运算 器 820进行第 z+1级基 y蝶形运算， 得到 y*m路第 z+1级基 y蝶形运算的结 果数据； 在得到所述 y*m路第 z+1级基 y蝶形运算的结果数据之后， 将该 y 路结果数据中，后写入到该 y个緩存区 830的剩余 n路结果数据中的每路结果 数据所分别等分为的 y个部分，作为 y路待进行第 z+1级基 y蝶形运算的数据， 输入该基 y蝶形运算器 820进行第 z+1级基 y蝶形运算， 得到 y*n路第 z+1 级基 y蝶形运算的结果数据， 其中该 m小于 y, 该 m与该 n之和等于y。

在本发明的一些实施例中， 控制器 810可具体用于， 在将第 z级基 y蝶形 运算的 y路结果数据中，后写入到该 y个緩存区 830的剩余 n路结果数据所分 别等分为的 y个部分，作为 y路待进行第 z+1级基 y蝶形运算的数据，输入基 y蝶形运算器 820进行第 z+1级基 y蝶形运算之前，先将 y*m路第 z+1级基 y 蝶形运算的结果数据中的每路结果数据等分为 y个部分， 将该 y个部分作为 y 路待进行第 z+2级基 y蝶形运算的数据，输入所述基 y蝶形运算器 820进行第 z+2级基 y蝶形运算， 得到 y*y*m路第 z+2级基 y蝶形运算的结果数据。

在本发明的另一些实施例中， 例如控制器 810也可以控制在所有待进行每 级基 y蝶形运算的数据都进行该级基 y蝶形运算后，再进行所有待进行下一级基 y蝶形运算的数据的下一级基 y蝶形运算。

例如， 控制器 810还可用于， 在进行第 z+1级基 y蝶形运算得到的 y*y 路第 z+1级基 y蝶形运算的结果数据之后，将 y*y路第 z+1级基 y蝶形运算的 结果数据中的每路结果数据等分为 y个部分，将该 y个部分作为 y路待进行第 z+2级基 y蝶形运算的数据， 输入该基 y蝶形运算器 820进行第 z+2级基 y蝶 形运算。

在本发明的一个实施例中， y个緩存区 830可分别位于 y个緩存器中； 或者， y个緩存区 830位于至少一个緩存器中。

可以理解，控制器 810可内置于基 y蝶形运算器 820中， 或可内置于緩存 区 830中， 当然亦可独立设置。 控制器 810的功能， 也可部分或全部的集成于 基 y蝶形运算器 820或緩存区 830所在緩存器中。

可以理解的是，本实施例的数据处理装置 800的各个功能模块的功能可以 根据上述方法实施例介绍的方法具体实现，其 具体实现过程可以参见上述实施 此不再赘述。

可以看出， 本实施例数据处理装置 800中的控制器控制将 y路待进行第 z级 基 y蝶形运算的数据， 输入基 y蝶形运算器进行第 z级基 y蝶形运算， 在该第 z级 基 y蝶形运算为最后一级基 y蝶形运算的情况下，输出该第 z级基 y蝶形运算得到 的结果数据； 在该第 z级基 y蝶形运算不为最后一级基 y蝶形运算的情况下， 将 该第 z级基 y蝶形运算得到的结果数据， 输入该基 y蝶形运算器进行第 z+ 1级基 y 蝶形运算。 由于该机制对基 y蝶形运算器进行了复用， 两级基 y蝶形运算复用同 一个基 y蝶形运算器， 例如可利用数据输入的时间复用基 y蝶形运算器进行运 算， 故而有利于减少蝶形运算的时间并减少资源消 耗。

参见图 9, 本发明实施例还提供一种电子设备 900, 其中， 该电子设备中部 署有数据处理装置 800。 其中， 电子设备 900例如可以是接入设备（如基站、 接 入点等）、 用户终端（如手机、 便携电脑等）、 或其它需要进行数据处理的电子 设备。

本发明实施例还提供一种计算机存储介质， 其中， 该计算机存储介质可存 储有程序，该程序执行时包括上述方法实施例 中记载的数据处理方法的部分或 全部步骤。

需要说明的是， 对于前述的各方法实施例， 为了筒单描述， 故将其都表述 为一系列的动作组合，但是本领域技术人员应 该知悉， 本发明并不受所描述的 动作顺序的限制，因为依据本发明，某些步骤 可以采用其他顺序或者同时进行。 其次， 本领域技术人员也应该知悉，说明书中所描述 的实施例均属于优选实施 例， 所涉及的动作和模块并不一定是本发明所必须 的。

在上述实施例中，对各个实施例的描述都各有 侧重， 某个实施例中没有详 述的部分， 可以参见其他实施例的相关描述。

综上， 本发明实施例中将 y路待进行第 z级基 y蝶形运算的数据， 输入基 y 蝶形运算器进行第 z级基 y蝶形运算， 在该第 z级基 y蝶形运算为最后一级基 y蝶 形运算的情况下， 输出该第 z级基 y蝶形运算得到的结果数据； 在该第 z级基 y 蝶形运算不为最后一级基 y蝶形运算的情况下， 将该第 z级基 y蝶形运算得到的 结果数据，输入该基 y蝶形运算器进行第 z+1级基 y蝶形运算。 由于该机制对基 y 蝶形运算器进行了复用， 两级基 y蝶形运算复用同一个基 y蝶形运算器， 例如可 利用数据输入的时间复用基 y蝶形运算器进行运算， 故而有利于减少蝶形运算 的时间并减少资源消耗。

并且，通过巧妙安排数据的各级基 y蝶形运算顺序，有利于减少延迟等待 时间， 进一步提高运算效率。

本领域普通技术人员可以理解上述实施例的各 种方法中的全部或部分步 骤是可以通过程序来指令相关的硬件来完成， 该程序可以存储于一计算机可读 存储介质中， 存储介质例如可以包括： 只读存储器、 随机存储器、 磁盘或光盘 等。

以上对本发明实施例所提供的一种数据处理方 法和相关装置进行了详细 施例的说明只是用于帮助理解本发明的方法及 其核心思想； 同时，对于本领域 的一般技术人员，依据本发明的思想， 在具体实施方式及应用范围上均会有改 变之处， 综上， 本说明书内容不应理解为对本发明的限制。