一种基于位串架构的蝶形运算单元、FFT处理器及方法

摘要

本发明公开了一种基于位串架构的蝶形运算单元，包括时延补偿器、乘法器、第一加法器、减法器，所述时延补偿器连接所述第一加法器、所述减法器，用于对输入的数据进行延时，以匹配所述乘法器的输出延时；所述乘法器连接所述第一加法器、所述减法器，用于将输入其中的数据与对应的旋转因子进行乘法运算；所述第一加法器用于根据所述时延补偿器输出的数据和所述乘法器输出的数据相加后输出第一结果，每个计算周期内首次运算时，所述第一加法器的进位标志位设置为0；所述减法器用于根据所述时延补偿器输出的数据和所述乘法器输出的数据相减后输出第二结果；任意一个时钟周期，所述时延补偿器、所述乘法器均只接收一个比特的数据输入。

说明书

技术领域

本发明涉及数字通信领域，特别涉及一种基于位串架构的蝶形运算单元、FFT处理 器及方法。

背景技术

快速傅里叶变换(FFT)广泛应用在数字信号处理领域，特别是作为OFDM系统的核 心技术之一，被广泛应用在802.11a、802.16、DAB与DVB-T等标准中，并将成为下一代无线通 信技术的基础。已有FFT的VLSI实现大致可以分为基于存储器(Memory-Based)实现与基于 流水线(Pipeline-Based)。基于存储器的结构的设计有双存储器(Ping-PongRAM)与缓存 存储(Cache-Memory)等众多结构。

但上述传统技术也存在着一些缺陷，图1所示是现有技术的一种蝶形运算单元，由 于数据运算和存储字长固定，传统设计只能处理数据字长固定的数据，其处理功能单一，其 处理数据的L个字长比特在同一时钟并行输入、输出，因此需要分解FFT并反复迭代计算，导 致设计逻辑复杂，处理时钟数较多，同时传统技术为了降低硬件面积，难以支持很大点数的 FFT计算。

发明内容

为了解决这些潜在问题，本发明的目的在于克服现有技术中所存在的上述不足， 提供一种设计逻辑简单、处理时钟较少、很好的支持大点数FFT计算的基于位串架构的蝶形 运算单元。

为了实现上述发明目的，本发明采用的技术方案是：

一种基于位串架构的蝶形运算单元，包括时延补偿器、乘法器、第一加法器、减法 器，

所述时延补偿器连接所述第一加法器、所述减法器，用于对输入的数据进行延时， 以匹配所述乘法器的输出延时；

所述乘法器连接所述第一加法器、所述减法器，用于将输入其中的数据与对应的 旋转因子进行乘法运算；

所述第一加法器用于根据所述时延补偿器输出的数据和所述乘法器输出的数据 相加后输出第一结果，每个计算周期内首次运算时，所述第一加法器的进位标志位设置为 0；

所述减法器用于根据所述时延补偿器输出的数据和所述乘法器输出的数据相减 后输出第二结果；

任意一个时钟周期，所述时延补偿器、所述乘法器均只接收一个比特的数据输入。

进一步地，所述加法器、减法器均由一位全加器组成。

进一步地，所述减法器包括取反器、第二加法器，所述乘法器输出端连接所述取反 器输入端，所述取反器输出端连接所述第二加法器，所述第二加法器的进位标志位在每个 计算周期第一个时钟周期置为1，其他时钟周期置为前一时钟周期第二加法器的进位输出。

进一步地，所述乘法器由多个一位全加器构成，所述一位全加器的个数与一位全 加器之间的连接方式由旋转因子确定，所述乘法器逐比特地完成输入序列与旋转因子的常 系数乘法。

进一步地，所述旋转因子使用CSD序列进行表示。

本发明同时提供一种基于位串架构的FFT处理器，包括多个如本发明的一种基于 位串架构的蝶形运算单元。

本发明还提供一种基于位串架构的蝶形运算FFT处理方法，利用分解算法将FFT分 解到多级运算单元阵列，并利用所述串行计算与存储的运算单元阵列实现对FFT的全部点 数并行计算。

进一步地，所述基于位串架构的蝶形运算FFT处理方法包括：

对2^m点的FFT，将其分解至2点，并建立m级蝶形运算阵列，每级阵列包括N/2个如权 利要求1-5任一项所述的蝶形运算单元，其中m＝log₂N，N是每个周期的采样点个数；

确定每个所述蝶形运算单元的乘法器中的旋转因子参数；

确定每个延时补偿器的延迟时间参数；

确定处理字长并据此确定电路计算周期；

根据上述参数设计每个蝶形运算单元，并按照CTA分解算法对所述的每个蝶形运 算单元进行连接。

进一步地，还包括，根据所述字长确定对所述蝶形运算单元中的进位符进行更新 的时间。

与现有技术相比，本发明的有益效果

1、本发明的一种基于位串架构的蝶形运算单元通过采用全并行流水结构，任意一 个时钟周期均只接收一个比特的数据输入，一个字长周期就可以完成全部点数的FFT的计 算，大幅度减少了时钟处理；同时，由于本发明采用逐比特数据处理，对于不同字长的数据 处理需要，只更改控制逻辑而不需改变硬件结构，从而可以支持多种字长数据的计算。

2、现有技术完成FFT控制逻辑与计算结构较为复杂，本发明的一种基于位串架构 的FFT通过将全并行FFT中的运算单元和存储单元转换为一位全加器和一位寄存器，从而很 好的降低了结构复杂度和运算复杂度，并提高了计算运行效率。

附图说明

图1是现有技术的一种蝶形运算单元结构框图。

图2是本发明的一个实施例示出的一种基于位串架构的蝶形运算单元结构框图。

图3是本发明的一个实施例示出的乘法器设计流程框图。

图4是本发明的一个实施例示出的FFT处理器的流程框图。

图5是本发明的一个实施例示出的长度为2^N点FFT处理器的流程框图。

图6是本发明的一个实施例示出的长度为2^N点FFT处理器的结构框图。

图7是本发明的一个实施例示出的8点FFT实施示例图。

图8是本发明的一个实施例示出的8点FFT的乘法器实施示例图。

附图标记：201-乘法器、202-时延补偿器、203-第一加法器、204-减法器、205-取反 器、206-第二加法器。

具体实施方式

下面结合具体实施方式对本发明作进一步的详细描述。但不应将此理解为本发明 上述主题的范围仅限于以下的实施例，凡基于本发明内容所实现的技术均属于本发明的范 围。

实施例1：

图2是本发明的一个实施例示出的一种基于位串架构的蝶形运算单元结构框图， 包括时延补偿器202、乘法器201、第一加法器203、减法器204，

所述时延补偿器202连接所述第一加法器203、所述减法器204，用于对输入的数据 进行延时，以匹配所述乘法器201的输出延时；

所述乘法器201连接所述第一加法器203、所述减法器204，用于将输入其中的数据 与对应的旋转因子进行乘法运算；

所述第一加法器203用于根据所述时延补偿器输出的数据和所述乘法器输出的数 据相加后输出第一结果，每个计算周期内首次运算时，所述第一加法器203的进位标志位设 置为0,其他时钟周期置为前一时钟周期第一加法器的进位输出；

所述减法器204用于根据所述时延补偿器202输出的数据和所述乘法器201输出的 数据相减后输出第二结果；

任意一个时钟周期，所述时延补偿器202、所述乘法器201均只接收一个比特的数 据输入。

设数据可表示为x＝a_L-1a_L-2…a₁a₀，其中最高位a_L-1为符号位，在每个时钟数据逐比 特串行输入，第一个时钟先输入最低位a₀，然后逐位输入至第L个时钟输入a_L-1，在第L+1个 时钟输入下一个数据的最低位。数据输入后分别进入乘法器201和时延补偿器202。乘法器 完成对旋转因子的常系数乘法后，数据也是逐比特输入加法器203与减法器204，完成加法 和减法后数据再逐比特输出。

进一步地，所述加法器、减法器均由一位全加器组成。

一位全加器逻辑运算简单，便于设计，构成的加法器、减法器结构简单。

进一步地，所述减法器204包括取反器205、第二加法器206，所述乘法器201输出端 连接所述取反器205输入端，所述取反器205输出端连接所述第二加法器206，在每个计算周 期内首次运算时，所述第二加法器206的进位标志位设置为1,其他时钟周期置为前一时钟 周期第二加法器206的进位输出。

时延补偿器202用于对乘法器输出延迟补偿，由于乘法器201将会带来L′拍时钟的 处理迟滞，为了保证数据在输入加法器203和减法器204之前对齐，需要额外补偿延迟。加法 器203为基于单比特全加器实现的串入串出单比特加法器，其中输入为两路加数与一路低 位进位，输出为和与向高位的进位。计算第一个比特时进位初始化为“0”，第二时刻开始将 输出的进位延迟反馈回进位输入。减法器204为基于单比特全加器实现的减法器，与加法器 203的不同之处在于为了将减数转换为补码，在该路将数字取反，同时初始的进位为“1”。

取反器将减法运算的减数转化为补码，在进行减法运算时，在每个计算周期的第 一个时钟运算时，第二加法器的进位标志位需要设置为“1”，其他时钟周期置为前一时钟周 期第二加法器的进位输出。

本发明的一种基于位串架构的蝶形运算单元通过采用全并行流水结构，任意一个 时钟周期均只接收一个比特的数据输入，一个计算周期就可以完成全部点数的FFT的计算， 大幅度减少了时钟处理；同时，由于本发明采用逐比特数据处理，对于不同字长的数据处理 需要，只更改控制逻辑而不需改变硬件结构，从而可以支持多种字长数据的计算。

进一步地，所述乘法器由多个一位全加器构成，所述一位全加器的个数与一位全 加器之间的连接方式由旋转因子确定，所述乘法器逐比特地完成输入序列与旋转因子的常 系数乘法。

进一步地，所述旋转因子使用CSD序列进行表示。

旋转因子的CSD(正则有符号系数)数表示为：其中最高位c_L′-1为整数位，其余位为小数位，由于乘法可以表达成移位加形式：即每一个非零的c_L′-1-i(i＝0到L′-1)，其将对应输入序列右移i位再求和。基于串行的计算 过程，是先从右移位数最多的序列的最低比特开始，和移位次多的序列对应相加，数据利用 比特加法器单比特处理，然后当下一个移位序列的最低位到达时，再添加一个比特加法器 或减法器来进行之前的计算结果与这一序列的计算，这样循环至最后i＝L′时终止。图3所 示是本发明的一个实施例示出的乘法器设计流程框图，其步骤包括：

步骤301：首先设置抽头延迟线模型，延迟数为L′。

步骤302：将需要的旋转因子转换为定长的CSD数表示，设长度为L′，则 $W_{N\_CSD}^{nk}=c_{L^{\prime }-1}{c}_{L^{\prime }-2}...c_1{c}_0.$

步骤303：设置遍历CSD数的下标循环变量i。

步骤304：从i＝0开始，由旋转因子CSD数的低位c₀向高位读取，每次读一位，然后i ＝i+1。

步骤305：判断c_i是否是非零位。若是，跳到步骤309，若不是，跳到步骤306。

步骤306：判断判断c_i是否小于0，若是，跳到步骤307，若不是，跳到步骤308。

步骤307：c_i小于0代表对应序列应该取补码，设置一个单比特减法器。减法器的输 入为：被减数是前一个加法器或减法器的计算结果经过移位器，移位器移位的个数为前一 个非零CSD数下标与现在时刻CSD数下标之差，减数连接该序列对应的延迟线抽头，减数在 第i时刻选通，选通前输入为0。特别地，当读入的第一个和第二个c_i都小于0，对应第一次的 运算为两个补码序列求和时，进位时刻需要调整。

步骤308：c_i大于0代表对应序列应该取原码，设置一个单比特加法器。加法器的一 个输入为：前一个加法器或减法器的计算结果经过移位器，移位器移位的个数为前一个非 零CSD数下标与现在时刻CSD数下标之差，若是第一个和第二个非零位则连接都第一个加法 器；另一个加数输入为c_i对应的延迟线抽头。加数在第i时刻选通，选通前输入为0。

步骤309：判断是否i＝L′，如果是则CSD序列已经读完，跳到步骤310，否则跳到步 骤304。

步骤310：去除多余延迟。由于可能存在CSD数最低的几个位和最高的几个位为零 的情况，为0的低位不对应计算序列，应该去除。

步骤311：最后需要在加法器和延迟线之间插入流水寄存器，使关键路径为一个单 比特加法器。

步骤312：完成乘法器设计并输出。

现有技术中，在全并行完成2^N点FFT时需要的乘法器数量多达(N/2)log₂N个，其结 构复杂、运算复杂，而本发明的一种基于位串架构的蝶形运算单元通过将现有技术中的乘 法器转换成为多个一位全加器，从而很好的降低了结构复杂度、运算复杂度，减少了硬件面 积，从而提高了运行效率与生产效率。

本发明提供一种基于位串架构的FFT处理方法，利用分解算法将FFT分解到多级运 算单元阵列，并利用所述串行计算与存储的运算单元阵列实现对FFT的全部点数并行计算。

具体的，将所需处理FFT逐步分解至需要直接电路计算的点数，其中分解点数互质 时依据PFA算法，非互质时使用CTA算法；

构建FFT处理运算单元阵列，处理单元分为m级，其中第j级阵列中运算单元处理点 数为N_j，该级运算单元数有N/N_j。其中一级与另一级之间可能有旋转因子调整，设计各级FFT 的计算电路，并对所有计算与存储单元应用串行化。设计各个运算单元中旋转因子的串行 乘法器，并将加法减法与延迟串行化。

图4是本发明的一个实施示例出的FFT处理流程框图，其步骤包括：

步骤401：依照CTA算法与PFA算法将FFT点数分解至直接计算的较小点数上。N点的离散傅里 叶变换表达式为其中旋转因子表达式为其中 n,k∈[0,N-1]，对于分解N＝N₁N₂，当分解的较小点数N₁,N₂互质时，使用PTA算法可以将原本 N点的FFT改写为先做N₁点FFT，然会再做N₂点的：当N₁,N₂不互质时，利用CTA算法可以将FFT改写为先做N₁点FFT，然后点乘上旋转因子之后再 做N₂点FFT：$X[k_1,k_2]={\Sigma }_{n_2}{\Sigma }_{n_1}x[n_1,n_2]W_{N_1}^{n_1{k}_1}{W}_{N_2}^{n_2{k}_2}{W}_N^{n_2{k}_1}.$分解出的N₁N₂点数还是较大时， 可以将N₁或N₂再进行迭代分解，直到分解成m个希望直接进行计算的点数：

步骤402：构建FFT处理运算单元阵列，依据步骤401分为m级：其中第j级阵列中运 算单元处理点数为N_j，这一级将有N/N_j个N_j点运算单元。其中一级与另一级之间可能有旋转 因子调整。

步骤403：确定FFT处理阵列中的各旋转因子参数。

步骤404：确定每一级乘法器的延迟以及延迟补偿器时间参数。

步骤405：根据步骤403和步骤404分别设计所有所述旋转因子的串行乘法器以及 所述串行运算单元，并将加法减法与延迟串行化。

步骤406：确定输入数据的字长，根据所述字长确定对所述运算单元中的进位符进 行更新的时间。

步骤407：输出设计的电路。

特别地，当长度为基2时，图5是本发明的一个实施例示出长度为N＝2^m点FFT处理 器的流程框图，包括如下步骤：

步骤501：依照CTA算法将N点FFT分解成为m级2点FFT。

步骤502：建立m级蝶形运算阵列，每级阵列包括N/2个如本发明的一种基于位串架 构的蝶形运算单元，其中m＝log₂N，N为全并行输入的各FFT点数。

步骤503：确定各2点蝶形运算单元中的各旋转因子参数。

步骤504：确定每一级乘法器的延迟以及延迟补偿器时间参数。

步骤505：分别设计所有所述旋转因子的乘法器以及所述蝶形运算单元。

步骤506：确定输入数据的字长，根据所述字长确定对所述运算单元中的进位符进 行更新的时间。

步骤507：输出设计的电路。

图6是本发明的一个实施例示出的长度为2^N点FFT处理器的结构框图。

按照图5所述的步骤建立如图6所示的全并行FFT处理器，其中模块602为第一级BU 阵列，模块603为第二级，以此类推。以处理N＝2^m点FFT，处理字长为L比特为例，蝶形运算单 元阵列将会有m级，每一级有N/2个BU；对全并行的N路数据输入，每一路都是串行输入，小端 数据先输入。数据在每个时钟逐比特输入第一级蝶形运算单元BU阵列602，BU对数据进行乘 加运算、经过一定处理迟滞后输入到第二级阵列603，并继续处理下去直至第m级处理完成 后输出。

实施例2：

图7所示是本发明的一个实施例示出的8点FFT实施示例图。

首先由于FFT点数N＝8＝2^m＝2³，可知全并行电路需要3级BU阵列，每一级BU有4个， 将BU阵列编号如图7中所示；其次明确BU阵列中乘法器的旋转因子，可知BU编号1到5、6和9 的旋转因子为1，BU6、8和11旋转因子为-j，BU10和12的旋转因子分别为0.707(1+j)和0.707 (-1+j)。乘法计算式分别为：与-j相乘-j(x+yj)＝-y+xj，相当于将IQ两路交换，同时将将y 取补码；与0.707(1+j)相乘0.707(1+j)(x+yj)＝0.707[x-y+(x+y)j]；同时与0.707(-1+j) 相乘0.707(-1+j)(x+yj)＝0.707[-x-y+(x-y)j]，涉及到的常系数乘法器系数都是0.707。 图8是本发明的一个实施例示出的8点FFT的乘法器实施示例图，其中示出的0.707的CSD数 只取了7位，表示为1.0-0-0101(“-”代表该位为“-1”)。同时为了数据对齐，可以在第三级乘 法器阵列的相应位置应该插入寄存器。在明确BU单元以及乘法器之后，将各个BU单元按照 蝶形运算分解结果连线，就可构成FFT处理器。

上面结合附图对本发明的具体实施方式进行了详细说明，但本发明并不限制于上 述实施方式，在不脱离本申请的权利要求的精神和范围情况下，本领域的技术人员可以作 出各种修改或改型。