2015, Vol. 44
[PDF全文]
随着车辆的增多，交通安全与城市拥堵成为了亟待解决的社会问题。由车载系统和路边单元构成的车联网系统，可以通过路面信息广播、自适应导航、不停车收费等技术，提高车辆行驶的安全性和交通效率，进而减少能耗、降低环境污染。随着车联网技术的发展与应用，基于802.11p/1609系列协议的车载无线宽带通信器件与系统的研究也得到了飞速的发展。符合802.11p协议标准的基带与射频芯片是车载无线宽带通信系统的核心，其性能直接决定了车载无线宽带通信系统的性能。FFT处理器是决定无线基带芯片性能的核心电路，因此研究高精度、低功耗、小面积的高性能FFT处理器对于开发高性能的车载无线宽带通信系统具有重要的意义。
快速傅里叶变换(FFT)是一种用于时域信号相位和频率成份分析的数字信号处理技术，该算法通过对离散傅里叶变换(DFT)进行递归分解为基本变换使其应用具有了可行性[1]。FFT在数字通信、生物医学信号处理、图像处理、多媒体广播、频谱分析与测量等领域得到了广泛的应用[2]。基于802.11p/ 1609系列协议的车载无线宽带通信系统采用正交频分复用(OFDM)技术，FFT处理器作为OFDM系统的核心功能电路而被用作调制器与解调器[3, 4, 5, 6, 7, 8, 9, 10]。由于FFT处理器占用了OFDM基带处理器的绝大部分面积与功耗，设计一个低功耗紧凑型的FFT处理器可以有效提高OFDM基带处理器的性能。目前主流FFT处理器主要有基于存储器结构的FFT处理器[11, 12, 13]、流水结构FFT处理器[14, 15, 16]、阵列结构FFT处理器[17]和基于高速缓冲存储器结构的FFT处理器[18]。基于高速缓冲存储器结构FFT处理器与基于存储器结构FFT处理器的结构相似，只是在处理单元和存储器之间增加了高速缓冲存储器。由于高速缓存比主存储器小，因此其读写速度比主存储器快且每次访问所需的功耗也比主存储器低，在一定程度上提高了FFT处理器的性能。
本文通过分析FFT算法的特点，设计了一种用于802.11p的基于高速缓冲存储器结构的低功耗紧凑型64点FFT处理器。随着基数的提高，蝶形运算的控制和数据流的复杂度会迅速增加，并严重影响所实现FFT处理器的性能提高，故该FFT处理器采用基-4时间抽取(decimation-in-time)FFT算法。
1 系统指标IEEE 802.11p是在IEEE 802.11a协议的基础上发展出来的无线标准，其物理层由数据扰码器、数据解扰器、调制器、解调器、卷积编码器、数据交织器、解交织器、Viterbi解码器和64点FFT/IFFT处理器构成。为了保证高机动车辆的数据通信，IEEE 802.11p信号的带宽由802.11a的20 MHz降为10 MHz、数据速率降为3～27 Mbps、OFDM符号持续时间8 μs、保护间隔1.6 μs。表 1为IEEE 802.11p物理层和IEEE 802.11a物理层的主要参数对比。
| 表1 IEEE 802.11p 物理层和 IEEE 802.11a 物理层参数对比 |
 |
按照IEEE 802.11p协议，一次FFT运算需要在8 μs内完成，采用传统的Cooley-Tukey基-2 FFT算法计算64点FFT需要192个复数蝶形运算，每次蝶形运算需要在41.6 ns内完成，而采用基-4FFT算法计算64点FFT需要48个蝶形运算，每次蝶形运算需要在166.7 ns内完成，因此采用基-2 FFT算法和基-4 FFT算法时蝶形运算单元所需的时钟频率将分别为24 MHz和6 MHz。
2 FFT算法分析DFT算法是分析有限长序列的理论分析工具，也是数字信号处理的最重要的算法之一，其在时域和频域均为离散信号。N点DFT运算表示为：
| $X[k] = \sum\limits_{n = 0}^N {x[n]} W_N^{nk}$ | (1) |
式中，k=0,1,…,N-1；旋转因子WN=e-j2π/N。N点离散傅里叶变换需要N2个复数乘法和N(N-1)复数加法，在N较大时DFT需要占用较大的面积与功耗。为了提高DFT的运算效率，利用旋转因子WN的的对称性、周期性和可约性，将N点输入DFT运算分解为较短序列的DFT运算。FFT算法通过对离散傅里叶变换进行递归分解为基本运算单元。
设N=L×M，L和M为整数。式(1)中的n和k可以分别表示为：
| $k = {k_1}L + {k_0}$ | (2) |
式中，k0=0,1,…,L-1；k1=0,1,…,M-1。
| $n = {n_1}M + {n_0}$ | (3) |
式中，n0=0,1,…,M-1；n1=0,1,…,L-1。
式(1)的N点输入DFT运算分解为长度为L点和M点较短序列的DFT运算，分解结果表示为：
| $\begin{array}{c} X({k_1},{k_0}) = \sum\limits_{{n_0} = 0}^{M - 1} {\sum\limits_{{n_1} = 0}^{L - 1} A } ({n_1},{n_0})W_N^{k({n_1}M + {n_0})} = \\ \underbrace {\sum\limits_{{n_0} = 0}^{M - 1} {\left( {\underbrace {\left( {\sum\limits_{{n_1} = 0}^{L - 1} {A({n_1},{n_0})W_L^{{k_0}{n_1}}} } \right)}_{L{\rm{DFT}}}\underbrace {W_L^{{k_0}{n_0}}}_{}} \right)W_M^{{k_1}{n_0}}} }_{M{\rm{DFT}}} \end{array}$ | (4) |
通过将式(1)的N点输入DFT运算分解为式(4)的长度为L点和M点较短序列DFT运算，可以将乘法运算次数和加法运算次数分别从N2和N(N-1)减少为N(M+L+1)和N(M+L-21)，由此可见，通过对N点输入DFT分解可以极大地减少所需的运算次数。Cooley-Tukey FFT算法的基数越高，所需要的运算量就越低[18]，但当基数超过4时蝶形运算的控制和数据流的复杂度会迅速增加，从而严重影响了所实现FFT处理器的性能提高，这使得基-2 FFT算法和基-4 FFT算法成为最普遍应用的FFT算法。
2.1 基-2 FFT算法基-2 FFT算法先将输入序列x(n)按照n的奇偶分为两组，然后通过变量置换，利用WN的周期特性，得到N点的蝶形运算公式为：
| $\left\{ \begin{array}{l} X(k) = {X_1}(k) + W_N^k{X_2}(k)\\ X\left( {k + \frac{N}{2}} \right) = {X_1}(k) - W_N^k{X_2}(k) \end{array} \right.$ | (5) |
式中，k=0,1,2,…,N/2-1；${X_1}(k) = \sum\limits_{r = 0}^{\frac{N}{2} - 1} {x(2r)W_{N/2}^{rk}} $；${X_2}(k) = \sum\limits_{r = 0}^{\frac{N}{2} - 1} {x(2r + 1)W_{N/2}^{rk}} $；N=2M且M为整数。N点序列的原始DFT算法需要N2次复数乘法和N(N-1)次复数加法，由式(5)可以看出，在基-2算法中，每个蝶形运算单元需要进行1次复数乘法和2次复数加法，N点序列的基-2 FFT算法需要(Nlog2N)/2次复数乘法和Nlog2N次复数加法。
2.2 基-4 FFT算法基-4 FFT算法可对序列长度N为4的整数次幂的序列进行运算，与基-2 FFT算法的相似，基-4 FFT算法通过短序列的DFT来表示长序列的DFT来减少运算次数。由式(4)可以推导4点FFT公式为：
| $\begin{array}{c} X(k) = \sum\limits_{{n_0} = 0}^3 {\sum\limits_{{n_1} = 0}^{L - 1} x } [4{n_1} + {n_0}]W_N^{K(4{n_1} + {n_0})} = \\ \sum\limits_{{n_0} = 0}^3 {\left( {\left( {\sum\limits_{{n_1} = 0}^{L - 1} {x[4{n_1} + {n_0}]W_L^{{k_1}{n_1}}} } \right)W_N^{{k_1}{n_0}}} \right)W_4^{{k_0}{n_0}}} \end{array}$ | (6) |
式中，N=4×L；K=L×k0+k1；k0=0,1,2,3；k1=0,1,2,…, L-1，且L为整数。由式(6)可知首先对输入信号矩阵的行进行L点DFT运算，将得到的L点DFT矩阵中的每一项都乘上旋转因子，再对该矩阵按列做4点的DFT运算，就实现一个按行排序的基-4 FFT运算结果矩阵，该N点基-4 FFT算法的矩阵变换过程如下：
| $\left( {\begin{array}{*{20}{c}} {x[0]}&{x[4]}& \cdots &{x[N - 4]}\\ {x[1]{\kern 1pt} }&{x[5]}& \cdots &{x[N - 3]}\\ {x[2]}&{x[6]}& \cdots &{x[N - 2]}\\ {x[3]}&{x[7]}& \cdots &{x[N - 1]} \end{array}} \right)$行DFT |
| $\left( {\begin{array}{*{20}{c}} {{X_{0,0}}}&{{X_{0,1}}}& \cdots &{{X_{0,L - {\rm{1}}}}}\\ {{X_{1,0}}}&{{X_{1,1}}}& \cdots &{{X_{1,L - {\rm{1}}}}}\\ {{X_{2,0}}}&{{X_{2,1}}}& \cdots &{{X_{2,L - {\rm{1}}}}}\\ {{X_{3,0}}}&{{X_{3,1}}}& \cdots &{{X_{3,L - {\rm{1}}}}} \end{array}} \right)$×旋转因子WNk1n0 |
| $\left( {\begin{array}{*{20}{c}} {{X_{0,0}}W_N^{{\rm{00}}}}&{{X_{0,1}}W_N^{{\rm{10}}}}& \cdots &{{X_{0,L - {\rm{1}}}}W_N^{(L - {\rm{1}}){\rm{0}}}}\\ {{X_{1,0}}W_N^{{\rm{01}}}}&{{X_{1,1}}W_N^{{\rm{11}}}}& \cdots &{{X_{1,L - {\rm{1}}}}W_N^{(L - {\rm{1}}){\rm{1}}}}\\ {{X_{2,0}}W_N^{{\rm{02}}}}&{{X_{2,1}}W_N^{{\rm{12}}}}& \cdots &{{X_{2,L - {\rm{1}}}}W_N^{L - {\rm{12}}}}\\ {{X_{3,0}}W_N^{{\rm{03}}}}&{{X_{3,1}}W_N^{{\rm{13}}}}& \cdots &{{X_{3,L - {\rm{1}}}}W_N^{L - {\rm{13}}}} \end{array}} \right)$ |
| 列DFT$\left( {\begin{array}{*{20}{c}} {X[{\rm{0}}]}&{X[{\rm{1}}]}& \cdots &{X[L - 1]}\\ {X[L]}&{X[L + 1]}& \cdots &{X[2L - 1]}\\ {X[2L]}&{X[2L + 1]}& \cdots &{X[3L - 1]}\\ {X[3L]}&{X[3L + 1]}& \cdots &{X[N - 1]} \end{array}} \right)$ |
式(6)的L点DFT运算可以进一步分解为4点DFT运算和L/4点DFT运算，分解得到的L/4点运算又可以进一步分解为4点DFT运算和L/16点DFT运算，如此循环下去直到每个序列的长度为4为止。N点序列的基-4 FFT处理器中的每个蝶形运算单元需要3次复数乘法和8次复数加法，因此N点序列的基-4 FFT运算共需要(3Nlog2N)/8次复数乘法和Nlog2N次复数加法。复数乘法在FFT处理器硬件实现中占用了大量的面积与功耗，因此减少复数乘法运算成为提高FFT处理器性能的一个重要途径。N点序列的基-4 FFT算法需要的复数乘法比基-2 FFT算法需要的复数乘法减少了25%，从而有效地提高了FFT处理器的性能。
3 基-4 FFT处理器的设计与实现符合802.11p协议标准的基带芯片采用64点FFT处理器，根据前面的分析可知，该处理器可以采用三级基-4运算完成，且本文设计采用时间抽取(DIT)、倒序输入、顺序输出的FFT处理器结构。FFT处理器的结构框图如图 1所示，其主要由蝶形运算单元、旋转因子ROM、顺序调整模块、控制模块以及随机访问存储器(RAM)构成。
|
| 图1 FFT处理器的结构框图 |
定点运算的电路结构简单且运算速度较快，但是由于定点运算的小数点位置固定导致了定点运算的动态范围小且容易产生溢出。浮点运算的动态范围大、不易产生溢出，但是浮点运算运算速度慢、实现复杂且实现成本较高。块浮点运算具有比定点运算更高的运算精度，比浮点运算更快的运算速度，且其实现复杂度与成本介于定点运算和浮点运算之间，因此本文FFT处理器采用块浮点运算实现数据运算。
控制模块用于生成蝶形运算单元所需旋转因子ROM的地址和数据RAM的地址并控制各个单元的工作时序。FFT处理器存储单元采用两个并行的双口RAM，在控制单元生成的控制信号放入控制下，数据流在两个RAM之间无延迟地交替存入与读出。在控制单元的控制下，FFT处理器开始接收数据并存储到第一个RAM中，接收完一组数据后控制单元产生第一个RAM和旋转因子ROM的读取数据地址和读使能信号同时向第二个RAM写入数据，第一个RAM中的数据被读出后被分成4路并行数据和从旋转因子ROM中读出的数据一起送到蝶形运算单元进行运算，蝶形运算的中间结果不断写回RAM，从而减少所需的硬件资源。
4 FFT处理器性能仿真与分析本文通过分析FFT算法的特点，设计了一个64点输入的基-4 FFT处理器，通过向该FFT处理器输入一个64点的三频率时域信号，可以得到三频率时域信号的频谱图。向FFT处理器输入三频率信号$x = {\rm{cos}}\left( {\frac{{{\rm{2}}\pi }}{3}t} \right){\rm{ + cos}}\left( {\frac{{{\rm{2}}\pi }}{5}t} \right){\rm{ + cos}}\left( {\frac{{{\rm{2}}\pi }}{7}t} \right)$时，可以得到该三频率信号的频谱图如图 2所示。
|
| 图2 三频率信号波形及其64点基-4 FFT频谱图 |
FFT处理器是决定无线基带芯片性能的核心电路，其性能直接决定了车载无线宽带通信系统的性能。本文通过分析802.11p协议标准和FFT算法的特点，设计了一种用于802.11p的低功耗紧凑型64点FFT处理器。该FFT处理器采用采用块浮点运算技术与单蝶形4路并行结构，在保证较低设计复杂度与成本的情况下极大地提高了FFT处理器数据运算精度与运算速度。仿真结果显示，该FFT处理器具有较高的数据运算精度与运算速度，完全满足车载无线宽带通信系统的要求。
| [1] | DIONYSIOS R, NIKOLAOS V. Conflict-Free parallel memory accessing techniques for FFT architectures[J]. IEEE Transactions on Circuits and Systems-I: Regular Papers, 2008, 55(11): 3438-3447. |
| [2] | CHIA H.Y, TSUNG H. Y, DEJAN M. Power and area minimization of reconfigurable FFT processors: a 3GPP-LTE example[J]. IEEE Journal of Solid-State Circuits, 2012, 47(3): 757-768. |
| [3] | XIN X, ERDAL O, JAFAR S. An efficient fft engine with reduced addressing logic[J]. IEEE Transactions on Circuits and Systems-Ⅱ: Express Briefs, 2008, 55(11): 1149-1153. |
| [4] | LINKAI W, XIAO F Z, GERALD E, et al. Generic mixed-radix FFT PRUNING[J]. IEEE Signal Processing Letters, 2012, 19(3): 167-170. |
| [5] | MANOHAR A, MICHAEL B, KESHAB K P. Pipelined parallel FFT architectures via folding transformation[J]. IEEE Transactions on Very Large Scale Integration(VLSI) Systems, 2012, 20(6): 1068-1081. |
| [6] | SHIN Y L, CHIN L W, MING D S. Low-cost FFT processor for DVB-T2 applications[J]. IEEE Transactions on Consumer Electronics, 2010, 56(4): 2072-2079. |
| [7] | CHAO M C, CHIEN C H, YUAN H H. An energy-efficient partial FFT processor for the OFDMA communication system[J]. IEEE Transactions on Circuits and Systems-Ⅱ: Express Briefs, 2010, 57(2): 136-140. |
| [8] | YUN N C. An efficient VLSI architecture for normal I/O order pipeline FFT design[J]. IEEE Transactions on Circuits and Systems-Ⅱ: Express Briefs, 2008, 55(12): 1234-1238. |
| [9] | SONG N. T, CHI H L, TSIN Y C. An area- and energy-efficient multimode FFT processor for WPAN/WLAN/WMAN systems[J]. IEEE Journal of Solid-State Circuits, 2012, 47(6): 1419-1435. |
| [10] | MARK L, SANJAY R. A 0.13-mm 1-GS/s CMOS discrete-time FFT processor for ultra-Wideband OFDM wireless receivers[J]. IEEE Transactions on Microwave Theory and Techniques, 2011, 59(6): 1639-1650. |
| [11] | LIN C T, YU Y C, FAN L D. A low-power 64-point FFT/IFFT design for IEEE 802.11a WLAN application[C]//IEEE International Conference Circuits System.[S.l.]: IEEE, 2006. |
| [12] | MAGAR S, SHEN S, LUI K G, et al. An application specific DSP chip set for 100 MHz data rates[C]// International Conference Acoustics, Speech, and Signal Processing.[S.l.]:[s.n.], 1988. |
| [13] | JO B G, SUNWOO M H. New continuous-flow mixed-radix (CFMR) FFT processor using novel in-place strategy[J]. IEEE Transactions on Circuits and Systems-I: Regular Papers, 2005, 52(5): 911-919. |
| [14] | HE S, TORKELSON M. Designing pipeline FFT processor for OFDM (de)modulation[C]//International Symposium on Signals, Systems, and Electronics.[S.l.]:[s.n.], 1998. |
| [15] | LEE S, PARK S C. Modified SDF architecture for mixed DIF/DIT FFT[C]//International Conference on Communication Technology.[S.l.]:[s.n.], 2006. |
| [16] | HE S, TORKELSON M. Design and implementation of a 1 024-point pipeline FFT processor[C]//IEEE Custom Integrated Circuits Conference (CICC’98).[S.l.]: IEEE, 1998. |
| [17] | BRIEN J O, MATHER J, HOLLAND B. A 200 MIPS single-chip 1k FFT processor[C]//IEEE International Solid-State Circuits Conference, Digest of Technical Papers.[S.l.]: IEEE, 1989. |
| [18] | BAAS B M. A low-power high-performance 1 024-point FFT processor[J]. IEEE Journal of Solid-State Circuits, 1999, 34(3): 380-387. |