扩频信号基于FFT码捕获的计算量分析

摘要：扩频通信技术中信号的捕获是扩频体制的关键。从快速捕获的角度出发，对传统捕获方法和基于FFT的快速捕获方法的原理进行了对比，并对不同捕获方法的计算量进行了分析和比较。获得基于FFT的循环相关捕获方法其计算量比传统方法少了3个数量级以上的结果。得到该方法在硬件实现中与传统滑动相关法相比大大节省了资源，减少了耗时的结论。
关键词：扩频；快逮捕获；FFT；计算量

0 引言
    直接序列扩频通信技术，具有抗干扰、保密性强、可实现码分多址通信和高精度测量的优点，其中信号的快速捕获是扩频体制的关键。最常用的码捕获方法是滑动相关法，但该方法捕获时间过长，因此考虑采用计算速度较快的基于FFT的循环相关捕获方法。本文将对这两种方法的计算量进行比较。

1 扩频信号的捕获方法
    在扩频通信中，传统的伪码捕获是通过相关运算和能量检测来完成的，成功实现伪码捕获的一个必要前提是获得输入扩频信号载波的准确值，因此整个捕获过程是一个载波频率、伪码相位的二维捕获过程。捕获又称初始同步或粗同步，其任务是完成对伪随机序列的粗同步，对伪随机序列的相位同步精度一般小于一个或1／2个伪码码片时长。
    在高动态条件下，发射装置与接收装置的相对运动造成接收端不同程度的多普勒频率偏移，这会对伪随机码扩频信号捕获造成一定的影响，因此在捕获的过程中要将多普勒频移考虑进去。最大的多普勒频移大约在±5 kHz的范围内。考虑发射端和接收端均为高速运动，多普勒频移的最大值在±10 kHz比较合理，以便覆盖高速飞行器产生的多普勒频移。
1．1 滑动相关法
    常用的码捕获方法包括发射参考信号法、前置同步码法、匹配滤波器法和滑动相关法。其中最常用的是滑动相关法。
    设通信开始时系统处于失步状态，积分清洗检测器的输出只有噪声并低于捕获门限，捕获判决器的输出控制本地伪码产生器使之处于搜索状态，每隔一个积分周期，对PN码相位进行调整(提前或退后一个相位)。捕获判决器每隔一个积分周期对捕获情况进行一次判决，决定是否需要继续调整本地伪码的相位。当捕获判决器有信号输出并超过预定门限时，即认为它开始捕获到信号。但为了防止噪声或干扰引起偶然的假捕获，通常要连续观察几次，等到捕获判决器的输出信号超过门限的次数累计到规定值后，才认为滑动相关捕获检测器确实捕获到了信号。流程如图1所示。

    在各种扩频系统中，因为滑动相关法实现简单，而且不需要任何先验信息，使用的最为广泛。对码长较短的伪随机码序列，该方法是较好的捕获方案。但滑动相关法存在一个突出的缺点：当两个伪码之间的相位差很大，而且伪码长度又很长时，要逐位检查(滑动)以达到捕获的时间可能很长。
    取伪码长度N=1 023，信息码速率为1．2 Kb／s，M=5，则可得最长捕获时间为：
   
    如果在捕获的过程中考虑信号载波的同步问题，那么最大捕获时间还会成倍增加。显然，捕获时间过长是实际系统所不能接受的。因此，必须设法减小捕获时间。
1．2 基于FFT的循环相关捕获方法
    将FFT(快速傅里叶变换)应用于扩频信号的捕获源于20世纪90年代，它在当时是为导航系统而引进的一种新的扩频码捕获技术。这种技术使用FFT来计算相关函数，因而消除了码相位滑动过程所需的时间。基于FFT的捕获方法的优势在于FFT计算的快速性。
1．2．1 基本原理
    循环相关捕获的示意图如图2所示，它是在时域中表示的，且只给出21个本地码的其中一个。如果用5 MHz对输入信号采样，输入电文长1 ms，含有5 000个数据点。可以认为输入电文与本地电文位于两个圆柱体表面，为了去匹配输入电文，本地码要旋转5 000次。换句话说，一个圆柱体相对于另一个圆柱体旋转5 000次。

    在每一步，5 000个输入电文与5 000个本地电文点对点相乘，相乘结果加到一起。包含本地码与输入码所有可能的乘积需要5 000步，乘积中最高幅值被记录下，若大于门限值，就是我们的期望值。
    从基本原理上讲，这种方法与滑动相关法是等同的，都是通过滑动码片来寻找最大值。不同的是，循环相关法每一次滑动后不用逐一相乘后相加，而是将时域信号进行快速傅里叶变换(FFT)转换成频域信号，在频域中求循环相关运算，直接求出了5 000次滑动中每一次滑动的相关值。在硬件实现中，可以利用自带的IP核直接进行FFT运算，这大大节约了资源。FFT的运算量分析在后文中将进行介绍。
1．2．2 具体步骤
    采用如上所述的基于FFT的循环相关捕获方法，假定捕获的频率搜索范围是±10 kHz，步进1 kHz，总共有21个频率分量。本地码lsi可表示为：
   
    式中：下标s代表卫星编号，下标i=1，2，…，21，Cs是卫星s的C／A码，fi=fc，-10，-9，…，9，10 kHz。这21组数据代表了间隔1 kHz的21个频率。将他们与输入信号进行相关运算，如果本地产生信号的C／A码和频率都正确的话，当C／A码相位对准时，输出达到峰值。
    对输入数据进行捕获操作的具体步骤如下：
    (1)对1 ms的输人数据x(n)进行FFT变换，将输入数据变换到频域X(k)，n=k=0～4 999；
    (2)取X(k)的复共轭，值为X*(k)；
    (3)用式(2)生成21个本地码lsi(n)，i=1，2，…，21。每个lsi(n)都有5 000个数据点。
    (4)对lsi(n)取FFT，转换为频域中的Lsi(k)。
    (5)将Lsi(k)与X*(k)逐点相乘，结果为Rsi(k)。
    (6)求Rsi(k)的FFT逆变换，变换到时域rsi(n)，求绝对值|rsi(n)|，总共有105 000(5 000×21)个|rsi(n)|。
    (7)在输入电文200 ns的时间分辨率和载波频率为1 kHz分辨率的条件下，|rsi(n)|最大值中的第n位和第i个载波频率给出了C／A码的初始点。
     图3给出了基于FFT的捕获流程示意图。

2 不同捕获方法的计算量比较
    从理论上讲，滑动相关法与基于FFT的循环相关捕获法都是利用数据点进行相关计算并比较求得最大值。其不同之处在于计算量的差距上，采用基于FFT的循环相关法计算量大大的减少，下面对其进行分析。
2．1 传统滑动相关法
    使用传统滑动相关法进行捕获，考虑21个多普勒频率分量，由于它们进行相同的操作，只对这21组数据的某一组进行讨论。
    输入数据和C／A码各含有5 000个数据点，根据滑动相关法的原理，要将C／A码滑动5 000次，每滑动一次码片都要将C／A码与数据进行5 000点的复乘，这样，在每个频率分量上要进行5 000×5 000次乘法运算，则21个频率分量共进行：
    S=5 000×5 000×21=5．25×108      (3)
    次运算。由此可见，这种方法在硬件实现中非常浪费资源。
2．2 基于FFT的循环相关法
2．2．1 FFT算法计算量简介
    采用快速FFT／IFFT运算，可以显著降低运算的复杂度，在这里简单介绍一下如何计算IFFT的运算量。FFT的运算量与此相同，不做赘述。
    对于常用的基2IFFT算法来说，其复数乘法的次数仅为(N／2)log N。随着N的增加，算法复杂度之间的差距越明显，IDFT的计算复杂度会随着N的增加而呈现二次方增长，IFFT的计算复杂度的增加速度只是稍微快于线形变化。
    对于计算点数比较多的系统，可以采用基4FFT算法。在4点的IFFT运算中，只存在与{1，-1，j，-j)的相乘运算，因此不需要采用完整的乘法器来实施这种乘法，只需要通过简单地加、减以及交换实部和虚部的运算(当与-j，j相乘时)来实现这种乘法。在基4算法中，IFFT变换可以被分为多个4点的IFFT变换，这样就只需要在两个级别之间执行完整的乘法操作。因此，N点的基4IFFT算法中只需要执行(3／8)·N·(log N-2)次复数乘法或相位旋转，以及N·log N次复数加法。
    图4说明了4点的IFFT运算，称做基4蝶型运算。4个输入x0，x1，x2，x3经过简单的相加和相位旋转，生成4个输出y0，y1，y2，y3，例如y1=x0+jx1-x2-jx3。

    基4蝶型算法可以用于高效的计算大规模的IFFT。图5说明了利用基4蝶型算法实施16点的IFFT，其中包括2级运算，每级内包含4个基4蝶型运算，在两级之间存在中间过渡级别，用于对16个中间过渡结果实施相位旋转ωi，其中ωi=exp(j2πi／N)。在N=16的情况下，当i=0，2，4，8，12时，与ωi相乘就可以简化为与{1，-1，j，-j)相乘。

2．2．2 计算量分析
    根据1．2．2节中介绍的循环相关捕获的具体步骤以及FFT算法的计算量，对基于FFT的循环相关捕获法计算量分析如下。
    首先，根据式(2)将21个频率分量下的C／A码与射频相乘，需要运算次数为：
    S1=21·N          (4)
    另外，N点基4FFT的运算量为(3／8)·N·(log N-2)，考虑21个多普勒频率分量以及FFT和IFFT双向变换，计算量为：
    S2=2·21·(3／8)·N·(log N-2)        (5)
    因此，总的计算量为：
    S=S1+S2=21·N·[(3／4)(log N-2)+1]    (6)
    这里数据点数N=5 000，则总计算量为915 180次，与滑动相关法相比，少了3个数量级。

3 结语
    本文从扩频信号捕获的角度出发，描述了传统捕获方法和基于FFT的快速捕获方法的原理和步骤，并对不同捕获方法的计算量进行了分析和比较。在文中可以看到，基于FFT的循环相关捕获法其计算量比传统方法少了3个数量级以上，该方法在硬件实现中，与传统滑动相关法相比大大节省了资源，减少了耗时，是一种比较好的捕获方法。