技术领域

本发明属于芯片设计中的算法硬件实现 , 具体来讲就是设计一种能够 配合矢量处理器技术实现高效快速傅里叶变换 ( FFT )运算的旋转因子产生 装置及其应用方法。 背景技术

在数字通信领域， FFT运算是最为常见的一种运算， 大部分的无线通 信都需要进行 FFT运算， 因此针对 FFT运算产生了多种电路和优化算法。 这些 FFT运算的方法大多是以硬件实现为主要方式， 一般独立成为一套系 统， 单独完成 FFT的相关运算。

随着 SDR (软件定义无线电）技术的不断发展， 越来越多的通信处理 计算任务， 逐渐直接交由处理器， 通过指令运算的方式直接运算产生结果。 各类的矢量处理器一般会将旋转因子看成是普 通的处理数据， 通过相关程 序设计配合来完成 FFT运算的任务， 效率不高。 发明内容

有鉴于此， 本发明的主要目的在于提供一种 FFT旋转因子产生装置及 其应用方法， 用于解决纯软件实现 FFT运算时， FFT旋转因子产生效率低 的问题。

为达到上述目的， 本发明的技术方案是这样实现的：

一种快速傅里叶 FFT旋转因子产生装置， 该装置包括：

地址产生单元 AGU, 用于对 FFT运算指令进行译码， 产生当前 FFT 运算状态对应的旋转因子查找表地址， 并将产生的旋转因子查找表地址输 出给查找表单元 LUT;

查找表单元 LUT, 用于根据旋转因子查找表地址在旋转因子查找 表中 查找对应的 FFT旋转因子， 并将查找到的 FFT旋转因子输出给输出单元 OU;

输出单元 OU, 用于将查找表单元 LUT输出的旋转因子送入算数运算 单元 AU。

所述地址产生单元 AGU包括：

FFT规模寄存器，用于通过对 FFT运算点数规模设置指令 fft— size指令 的译码获取并存储当前的 FFT运算规模；

FFT阶数寄存器， 用于通过对 FFT下一阶运行指令 fft— nxt— stage指令 的译码获取并存储当前 FFT运算所处的阶数；

FFT回合寄存器， 用于通过对 FFT蝶形运算指令 fft— round指令的译码 获取并记录当前 FFT运算所执行的回合数；

FFT地址译码单元， 用于根据当前 FFT规模寄存器、 FFT阶数寄存器 和 FFT回合寄存器三个寄存器的状态， 译码生成旋转因子查找表地址， 并 将产生的旋转因子查找表地址输出给所述查找 表单元 LUT。

所述查找表单元 LUT中包含旋转因子查找表， 在所述旋转因子查找表 中， 按照旋转因子查找表地址与旋转因子的对应关 系对用于 FFT运算的旋 转因子进行压缩存储。

所述输出单元 OUT内部包含緩存寄存器， 所述緩存寄存器用于保证输 出数据的时序特性， 所述输出单元 OUT输出的旋转因子送入算数运算单元 的复选器。

基于本发明提供的 FFT旋转因子产生装置， 本发明还提供一种 FFT旋 转因子产生装置的应用方法， 该方法包括：

在处理器的流水线上设置 FFT旋转因子产生装置， 该装置预先存储多 种 FFT运算所需要的旋转因子， 当处理器进行 FFT运算时， 通过专用 FF 指令触发所述 FFT旋转因子产生装置产生与 FFT运算对应的旋转因子， 并 在专用 FFT指令的控制下将 FFT运算需要的数据及旋转因子产生装置产生 的旋转因子送入算数运算单元 AU进行相应的 FFT运算。

进一步地， 所述专用 FFT指令包括：

FFT运算点数规模设置指令， 即 fft— size指令， 该指令用于向所述 FFT 旋转因子产生装置指示当前的 FFT运算点数规模；

FFT下一阶运行指令， 即 fft— nxt— stage指令， 该指令用于指示所述 FFT 旋转因子产生装置当前 FFT运算的阶数， 每当完成一阶的 FFT运算后， 运 行该指令指示所述 FFT旋转因子产生装置进入下一阶的运算；

FFT蝶形运算指令， 即 fft— round指令， 用于选通算数运算单元 AU的 输入端口， 将所述 FFT旋转因子产生装置产生的旋转因子和需要运 算的数 据输入算数运算单元 AU中， 并执行 FFT的蝶形运算。

进一步地，所述通过专用 FF指令触发所述 FFT旋转因子产生装置产生 与 FFT运算对应的旋转因子， 并在专用 FFT指令的控制下进行相应的 FFT 运算的过程为：

在新的 FFT运算开始时， 运行 fft— size指令， 对所述 FFT旋转因子产 生装置进行初始化， 所述 FFT旋转因子产生装置记录 fft— size指令指示的 FFT运算点数规模；

所述 FFT旋转因子产生装置根据每个阶段的 FFT运算的状态输出与当 前 FFT运算状态对应的旋转因子， 在每个阶段的内部， 执行 fft— round指令 将 FFT运算所需数据及旋转因子输入到算数运算单 元， 进行每个阶段内部 的 FFT蝶形运算；

在每一阶段的 FFT运算结束后， 执行 fft— nxt— stage指令， 进入下一阶 段的 FFT运算，直到完成 fft size指令指示的 FF运算点数规模的 FFT运算。 进一步地， 当所述 fft— size指令进入到译码阶段时， 使 FFT旋转因子产 生装置中的 FFT阶数寄存器和 FFT回合寄存器清零， 同时将 fft— size指令 指示的 FFT运算点数规模存入 FFT规模寄存器中；

每当 FFT数据运算指令 fft指令执行后， 通过指令流水线的指令译码， 使 FFT旋转因子产生装置中的 FFT回合寄存器自动加 1， 然后根据 FFT旋 转因子产生装置中的 FFT阶数寄存器、 FFT回合寄存器和 FFT规模寄存器 的值判断当前 FFT运算所处于的状态， 并根据当前状态从 FFT旋转因子产 生装置中的查找表单元 LUT获得当前 FFT运算所需的旋转因子，送入算数 运算单元 AU入口；

当 fft— nxt— stage指令执行后， FFT回合寄存器清零， FFT阶数寄存器寄 存器加 1。

本发明基于矢量处理器技术， 针对其 FFT运算， 提出一种 FFT旋转因 子产生装置， 并配合该装置在该处理器内部设计实现了一套 专用的 FFT运 算指令集， 在专用 FFT指令的控制下产生与 FFT运算所处状态对应的旋转 因子， 并将 FFT运算需要的数据及产生的旋转因子送入算数 运算单元 AU 进行相应的 FFT运算。 本发明通过提高旋转因子产生效率来达到提升 FFT 运算效率的效果， 从指令译码到旋转因子生成， FFT运算全部釆用流水线 技术， 大幅提升了 FFT运算的吞吐率。 本发明具有很广的适用性， 能够完 成 LTE等通信协议中的多种 FFT旋转因子的产生和计算工作。 并且可以通 过指令 好的控制 FFT运算的流程和旋转因子的产生， 非常适合用于通信 用矢量处理器的内部。 发明内容

图 1为本发明提供的旋转因子产生装置在处理器� �位置框图； 图 2为本发明提供的旋转因子产生装置结构及内� �运行时序示意图； 图 3为釆用本发明实施例提供的旋转因子产生装� �及专用 FFT运算指 令执行 FFT运算的流程。 附图说明

图 1为本发明提供的旋转因子产生装置在处理器� �位置框图； 图 2为本发明提供的旋转因子产生装置结构及内� �运行时序示意图； 图 3为釆用本发明实施例提供的旋转因子产生装� �及专用 FFT运算指 令执行 FFT运算的流程。 具体实施方式

为使本发明的目的、 技术方案和优点更加清楚明白， 以下举实施例并 参照附图， 对本发明进一步详细说明。

Radio , SDR )处理器能够直接对 FFT进行高效的运算， 本发明在处理器的 流水线上设计了专门的 FFT旋转因子产生（ Twiddle Factor Generate )装置， 该装置预先存储了多种 FFT运算所需要的旋转因子在只读存储器 ( ROM ) 空间内， 当处理器进行运算时， 通过调用本发明提供的指令， 产生与 FFT 运算对应的旋转因子， 并将旋转因子送入算数运算单元 AU 的入口， 然后 再通过本发明提供的一组专用的 FFT运算指令将 FFT运算需要的数据及旋 转因子产生装置所生成的旋转因子送入处理器 的 AU单元进行一次与 FFT 运算相关的蝶形运算。

本发明实施例提供的旋转因子产生装置在处理 器流水线数据通路上的 位置如图 1 所示。 按照矢量处理器的一般流程， 处理器首先将需要处理的 数据从存储单元中取出， 送入寄存器堆（Register Files ), 然后经由专门的 数据选择单元（复选器 X、 复选器 Y、 复选器 Ζ )读出送入算数运算单元 AU进行计算， 旋转因子产生装置， 即图中的 TWFG , 将作为 AU单元的 Ζ 端口将产生的旋转因子送入 AU单元， 该数值与寄存器堆送入的数据进行 相关的 FFT运算， 最终的运算结果将被送回寄存器堆中。

图 1 的右侧为旋转因子产生装置的放大示意图， 该旋转因子产生装置 主要分为 3个部分： 地址产生单元（AGU )、 查找表单元（LUT )、 输出单 元（OU )。

AGU与指令流水线关联，用于对本发明专门提供 的 FFT运算指令进行 译码， 判断当前 FFT运算所处的状态， 获得当前 FFT运算状态对应的旋转 因子查找表地址， 并将产生的 FFT旋转因子查找表的地址输出给 LUT;

LUT用于根据 AGU输出的旋转因子查找表地址在旋转因子查找 表中 查找对应的 FFT旋转因子， 查找出的旋转因子通过 OU送入处理器 AU的 输入端口上， 进行相应的 FFT运算。 本实施例中输出单元 OU输出的 FFT 旋转因子输入到复选器 Z, 复选器 Z选通后， 进入 AU单元， 作为 AU单元 的一路入口数据参与 FFT运算。

LUT单元主要是根据旋转因子产生的特点， 将旋转因子进行压缩， 并 且按照一定规律进行存储的一个只读存储器 （ROM )单元， 该单元一但建 立就形成为固化的逻辑， 其内部就是一张查找表机制， 用于根据 AGU输出 的地址查找对应的 FFT旋转因子， 并将其输出给 OU。

输出单元 OU负责将 LUT产生的旋转因子送入 AU的输入单元， 该单 元内部设计有寄存器逻辑， 保证了输出数据的良好时序特性。

进一步地， 所述 AGU单元进一步包括：

FFT规模 ( fft size )寄存器， 一端与指令流水线关联， 另一端与 FFT 地址译码单元相连，用于通过对 FFT运算点数规模设置指令 fft— size的译码 获取并存储当前的 FFT运算规模；

FFT阶数（fft— stage )寄存器， 一端与指令流水线关联， 另一端与 FFT 地址译码单元相连， 用于通过对 FFT下一阶运行指令 fft— nxt— stage指令的 译码获取并存储当前 FFT运算所处的阶数；； FFT回合（fft— round )寄存器， 一端与指令流水线关联， 另一端与 FFT 地址译码单元相连， 用于存储通过指令译码获取的当前 FFT运算所执行的 回合数；

FFT 地址译码单元 （ twfg— addr— gen ) , 主要用于根据当前 fft— size、 fft— stage和 fft— round三个寄存器的状态， 译码生成旋转因子查找表的入口 地址， 并将产生的入口地址输出给所述查找表单元 LUT。

基于本发明对处理器流水线的改进， 本发明实施例针对矢量处理器进 行 FFT运算专门提供了如下一些指令：

( 1 ) FFT运算点数规模设置指令， 即 fft— size指令， 该指令用于设置 FFT运算点数规模，该指令控制 AUG内部的 fft— size寄存器记录当前的 FFT 运算点数规模；

( 2 ) FFT下一阶运行指令， 即 fft— nxt— stage指令， 该指令用于指令进 行下一阶（stage ) 的 FFT运算， 该指令控制 AUG内部的 fft— stage寄存器 记录下一阶 FFT运算的阶数,每当当前的 FFT运算完成一阶的 FFT运算后， 需要运行该指令保证硬件进入下一阶运算， 例如通知 FFT旋转因子产生装 置产生下一阶的阶数。

( 3 ) FFT蝶形运算指令， 即 fft— round指令， 该指令用于执行 FFT的 回合（round )运算， 为专门的 FFT数据运算指令， 该指令选通 AU单元的 输入端口， 将旋转因子和需要运算的数据输入 AU中， 并完成 FFT的一次 蝶形运算。

图 3为釆用本发明实施例提供的旋转因子产生装� �及专用 FFT运算指 令执行 FFT运算的流程， 具体步骤如下：

步骤 301、 调用 fft— size指令对 FFT旋转因子产生装置进行初始化， 使 FFT阶数寄存器和 FFT回合寄存器清零， 为 FFT规模寄存器赋值；

每次有新的 FFT运算开始时， 首先运行 fft size指令设置快速傅里叶 ( FF )运算点数规模， 矢量处理器收到 fft— size指令后， 当指令进入到译码 阶段（DEC stage ) 时， fft— stage和 fft— round寄存器将会清零， 表明进入了 新的 FFT运算。 同时将 FFT运算点数规模写入 fft— size寄存器中。

每种点数规模的 FFT运算根据程序需求， 被划分成多个阶段（stage ), 每个阶段对应一个 FFT运算的级别， 每个阶段的内部又可能会被划分成多 个回合（round ), 通过运行 fft— round指令来进行每个阶段内部的一个回合 的 FFT运算。

步骤 302、 调用 fft— round指令执行当前阶段和当前回合的的蝶形运� ��， FFT旋转因子产生装置对 fft— round指令进行译码， 根据当前 FFT运算状态 产生当前 FFT运算所需的旋转因子， 完成当前的蝶形运算， fft— round指令 完成后， FFT回合寄存器自动加 1 ;

每当 fft— round指令执行后， 通过指令流水线的指令译码， 使 fft— round 寄存器自动加 1 , 表明运行了一条相关的蝶形运算。 AGU单元则会根据当 前的 fft— size、 fft round, fft— stage的信息联合判断当前 FFT运算所处于的 状态， 并进行译码， 通过一组组合逻辑电路（Combination Logic ), 即图 2 中的 FFT地址译码单元， 产生当前 FFT运算所需要的旋转因子地址， 然后 将该地址送入 LUT中并在流水线节拍的下一节拍， 即寄存器读出阶段用寄 存器读出相关的旋转因子数值。

产生的旋转因子被送入 OU单元后经过选通处理， 在 fft— round指令执 行阶段 ( EX stage )被送入到 AU单元直接参与蝶形运算。

步骤 303、 判断是否完成当前阶段的 FFT运算， 若未完成则继续执行 步骤 302, 若完成则执行步骤 304;

步骤 304、 判断是否完成 fft— size指令指示的点数规模的 FFT运算， 若 未完成， 则执行步骤 305 , 否则结束流程。

步骤 305、 执行 fft— nxt— stage指令， 进入下一阶段的 FFT运算， 同时 fft— round寄存器清零， fft— stage寄存器加 1 , 然后执行步骤 302。 本发明提出的 FFT旋转因子产生装置是一种直接配合矢量处理 器技术 的硬件电路实现， 他将硬件电路实现和指令流水线技术相结合， 将 FFT运 算完全融合于矢量处理器的指令集中。 极大的提高了矢量处理器对于 FFT 运算的支持能力。

本发明提出的 FFT旋转因子产生装置， 同时具有极强的灵活性， 因为 其 FFT运算的点数、阶数等 FFT运算中的参数，均可以通过指令进行配置， 因此他可以根据配置， 灵活的产生各类型的 FFT旋转因子。

本发明提出的旋转因子产生装置因为融合于处 理器技术， 因此借鉴了 处理器的流水线技术， 其本身的流水线与矢量处理器的流水线相融合 ， 具 有处理能力强， 处理频率高， 配合处理器数据通路， 能够产生较高的 FFT 运算吞吐率。

以上所述， 仅为本发明的较佳实施例而已， 并非用于限定本发明的保 护范围。