卫星信号捕获中快速傅氏变换算法的实现装置和方法

摘要

本发明公开了一种卫星信号捕获中快速傅氏变换算法的实现装置和方法。该方法主要包括：通过多级运算处理来实现快速傅氏变换算法，每一级运算处理为两路输入和两路输出，每一级运算处理接收并处理前一级运算处理输出的数据，将处理后得到的数据再输出给下一级运算处理。本发明实施例实现了每个时钟输入两个数据，输出两个计算后的数据，可以提高卫星信号的伪码并行载波并行搜索方案中的FFT模块的数据处理效率，而所用硬件资源没有明显增长。

权利要求

1.一种卫星信号捕获中快速傅氏变换算法的实现装置，其特征在于，包括：多级处理单元，每一级处理单元为两路输入和两路输出，每一级处理单元的两路输入数据为每时钟输入两点的数据，每一级处理单元接收并处理前一级处理单元输出的数据，将处理后得到的数据再输出给下一级处理单元；

所述每一级处理单元包括：

数据选择器，用于接收上一级处理单元输出的两路数据，将该两路数据分别传输给数据存储器；

数据存储器，用于将所述数据选择器传输过来的两路数据分别进行存储，并且存储每路数据所对应的旋转因子；

蝶形运算单元，用于从所述数据存储器中获取两路数据和每路数据所对应的旋转因子，对获取的两路数据和相应的旋转因子进行复数乘法和加法运算，将获取的计算结果传输给数据存储器进行存储，并输出给下一级处理单元；

控制及地址产生模块，用于产生所述数据选择器输出的两路数据所对应的存储地址，以及每路数据所对应的旋转因子的存储地址，将所述存储地址传输给数据存储器。

2.根据权利要求1所述的快速傅氏变换算法的实现装置，其特征在于，所述数据存储器包括：随机存取存储器，用于按照所述控制及地址产生模块传输过来两路数据所对应的存储地址，将所述两路数据分别进行存储；

只读存储器，用于按照所述控制及地址产生模块传输过来每路数据所对应的旋转因子的存储地址，将所述两路数据所对应的旋转因子分别进行存储。

3.根据权利要求1或2所述的快速傅氏变换算法的实现装置，其特征在于，所述蝶形运算单元包括：复数乘法器，用于将每路数据和对应的旋转因子进行复数乘法运算，将得到的运算结果传输给加法器；

加法器，用于将所述复数乘法器传输过来的一路数据和对应的旋转因子的复数乘法运算结果和另一路数据进行相加。

4.根据权利要求1所述的快速傅氏变换算法的实现装置，其特征在于，所述快速傅氏变换算法的实现装置采用现场可编程门阵列模块来实现。

5.一种卫星信号捕获中快速傅氏变换算法的实现方法，其特征在于，包括：通过多级运算处理来实现快速傅氏变换算法，每一级运算处理为两路输入和两路输出，每一级处理单元的两路输入数据为每时钟输入两点的数据；

每一级运算处理接收上一级运算处理输出的两路数据，将该两路数据分别进行存储，并且存储每路数据所对应的旋转因子；

通过复数乘法器将每路数据和对应的旋转因子进行复数乘法运算，将得到的运算结果传输给加法器，通过所述加法器将所述复数乘法器传输过来的一路数据和对应的旋转因子的复数乘法运算结果和另一路数据进行相加，将获取的计算结果进行存储，并输出给下一级运算处理。

说明书

卫星信号捕获中快速傅氏变换算法的实现装置和方法

技术领域

[0001] 本发明涉及卫星导航信号处理技术领域，尤其涉及一种卫星信号捕获中FFT(Fast Fourier Transform，快速傅氏变换)算法的实现装置和方法。

背景技术

[0002] 信号捕获，又称信号的同步，是指从白噪声中检测出已知波形信号，是一个信号检测处理过程。用来捕获信号的最佳接收机是相关接收机，该相关接收机将输入信号与本地复现波形进行相关运算并将处理结果进行门限判决。在信号未捕获时只能采用试探方式进行相关处理，即遍历各种的码相位可能性直至找出相关峰。

[0003] 为了捕获到卫星信号，需要同时复现卫星信号的码和载波，这其实是一个二维搜索过程。根据在码和多普勒域上捕获方法的不同，将卫星信号的捕获方案分为以下四种：伪码串行载波串行、伪码串行载波并行、伪码并行载波串行、伪码并行载波并行搜索方案。

[0004] 现有技术的一种伪码并行载波方案中，伪码搜索和载波分析采用的是单点输入和单点输出，单点输入即每个时钟输入一个待处理数据，每个时钟输出一个处理完的数据。

[0005] 在实现本发明的过程中，发明人发现上述现有技术中的伪码并行载波方案的缺点为：占用系统资源多，计算效率低下。以一个商用IP核为例，该IP核计算128点的FFT，单点输入单点输出，在FPGA(Field Programmable Gate Array，现场可编程门阵列)内实现时占用逻辑资源3410个LC，存储器为90112比特。

发明内容

[0006] 本发明实施例提供了一种卫星信号捕获中FFT算法的实现装置和方法，以提高FFT模块的数据处理效率，降低FFT模块的占用资源。

[0007] 一种卫星信号捕获中快速傅氏变换算法的实现装置，包括：

[0008] 多级处理单元，每一级处理单元为两路输入和两路输出，每一级处理单元的两路输入数据为每时钟输入两点的数据，每一级处理单元接收并处理前一级处理单元输出的数据，将处理后得到的数据再输出给下一级处理单元；

[0009] 所述每一级处理单元包括：

[0010] 数据选择器，用于接收上一级处理单元输出的两路数据，将该两路数据分别传输给数据存储器；

[0011] 数据存储器，用于将所述数据选择器传输过来的两路数据分别进行存储，并且存储每路数据所对应的旋转因子；

[0012] 蝶形运算单元，用于从所述数据存储器中获取两路数据和每路数据所对应的旋转因子，对获取的两路数据和相应的旋转因子进行复数乘法和加法运算，将获取的计算结果传输给数据存储器进行存储，并输出给下一级处理单元；

[0013] 控制及地址产生模块，用于产生所述数据选择器输出的两路数据所对应的存储地址，以及每路数据所对应的旋转因子的存储地址，将所述存储地址传输给数据存储器。

[0014] 一种卫星信号捕获中快速傅氏变换算法的实现方法，包括：

[0015] 通过多级运算处理来实现快速傅氏变换算法，每一级运算处理为两路输入和两路输出，每一级处理单元的两路输入数据为每时钟输入两点的数据；

[0016] 每一级运算处理接收上一级运算处理输出的两路数据，将该两路数据分别进行存储，并且存储每路数据所对应的旋转因子；

[0017] 通过复数乘法器将每路数据和对应的旋转因子进行复数乘法运算，将得到的运算结果传输给加法器，通过所述加法器将所述复数乘法器传输过来的一路数据和对应的旋转因子的复数乘法运算结果和另一路数据进行相加，将获取的计算结果进行存储，并输出给下一级运算处理。

[0018] 由上述本发明的实施例提供的技术方案可以看出，本发明实施例可以提高卫星信号的伪码并行载波并行搜索方案中的FFT模块的数据处理效率，使FFT模块占用资源少，配置灵活。

附图说明

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

[0020] 图1为本发明实施例一提出的卫星信号的伪码并行载波并行搜索方案的原理示意图；

[0021] 图2为本发明实施例一提出的卫星信号的伪码并行载波并行搜索方案的具体处理过程的处理流程图；

[0022] 图3为本发明实施例一提供的两点输入两点输出的FFT模块的原理示意图；

[0023] 图4为本发明实施例一提供的FFT模块中的每一级处理单元的结构示意图；

[0024] 图5为本发明实施例一提供的一种碟形运算单元的结构示意图；

[0025] 图6为本发明实施例一提供的一种FFT模块的输入输出时序图。

具体实施方式

[0026] 在本发明实施例中，通过多级运算处理来实现FFT算法，每一级运算处理为两路输入和两路输出，每一级运算处理接收并处理前一级运算处理输出的数据，将处理后得到的数据再输出给下一级运算处理。

[0027] 为便于对本发明实施例的理解，下面将结合附图以几个具体实施例为例做进一步的解释说明，且各个实施例并不构成对本发明实施例的限定。

[0028] 实施例一

[0029] 本发明实施例提出的卫星信号的伪码并行载波并行搜索方案的原理示意图如图1所示，该方案的具体处理过程的处理流程如图2所示，包括如下步骤：

[0030] 步骤21、使用匹配滤波器进行伪码搜索，采用FFT处理方法来估计匹配滤波器输出的信号的多普勒频率。

[0031] 在图1所示的方案中，伪码搜索使用匹配滤波器，该匹配滤波器实际上就是一个系数可变的FIR(Fixed Information Rate，固定比特率)滤波器。对于一个N阶的匹配滤波器，可以对输入信号同时完成N个伪码不确定度的相关计算。在匹配滤波器的设计中，为提高数据吞吐效率，每时钟输出两点。

[0032] 基准码由本地码生成器产生，生成的本地码和所捕获的卫星所使用的扩频码一致，并存入码存储器以备读取。相干积累在匹配滤波器能完成，即将本地码和输入的采样数据依次相乘并把各个乘积累加，这个过程对输入数据解扩频并积累能量。

[0033] 匹配滤波器输出的信号传输给FFT，采用FFT处理方法来估计信号的多普勒频率。上述FFT处理相当于在多普勒域上同时捕获信号的所有可能的多普勒频率的最大值，所以总的捕获时间不受载波多普勒范围影响，非常适合对捕获时间要求严格场合。并且上述匹配滤波器接收到的输入信号一旦在时域上被捕获，经过FFT处理后在某个多普勒频率上将肯定出现相关峰，这对于高动态应用环境非常合适。

[0034] 步骤22、FFT设计成两点输入和输出，包括流水线工作的多级处理单元。

[0035] 由于上述匹配滤波器接收到的输入数据的量大，要求FFT实时地处理匹配滤波器的输出数据，由于匹配滤波器每时钟输出两点，因此FFT也要设计成每时钟输入两点，以便和前级配合。

[0036] 以64点FFT为例，该实施例提供的两点输入两点输出的FFT的原理示意图如图3所示。在图3中，64点FFT分成6级处理单元，流水线工作，每一级处理单元在实时接收并处理前一级处理单元输出的数据，输入的时域数据经过若干个时钟的延时后变成频域的数据，再输出给下一级处理单元。由于每一级处理单元在每个时钟都在实时处理数据，因此效率极高。

[0037] 步骤23、每一级处理单元通过蝶形运算单元、数据选择器、控制及地址产生模块、存储旋转因子的查找表和数据存储器组成。

[0038] 上述每一级处理单元的结构示意图如图4所示，由一个蝶形运算单元，三个数据选择器，一个控制及地址产生模块，一对存储旋转因子的查找表，一对数据存储器组成。

[0039] 其中，蝶形运算单元、数据选择器级与级之间完全相同；存储器大小依照级数以2倍递增；控制及地址产生模块级与级之间结构相同，根据存储器的读写地址宽度的不同作相应调整。上一级处理单元输出的数据直接流入本级处理单元，经过处理单元内部缓存后送入本级蝶形运算单元，得出的结果流出本级处理单元，送入下一级处理单元。这样，每级每次处理2点，流水作业，共需要32个时钟周期完成一次64点FFT。

[0040] 上述图4所示的每级处理单元具有如下特点：

[0041] (1)采用补码运算；

[0042] (2)变换序列长度N＝64；

[0043] (3)使用fpga内置双端口RAM(Random Access Memory，随机存取存储器)，用于存储每次碟形运算后的中间结果。

[0044] (4)旋转因子也由系统内部产生，不需外部编程。

[0045] 该实施例提供的碟形运算单元的结构如图5所示，碟形运算单元是每级处理单元的核心部分，它采用Pipeline(导管)流水线结构，主要包括复数乘法器和加法器。每级碟形单元的计算输出结果存储于相应的RAM单元中。

[0046] 控制及地址产生模块由两个地址发生器组成，主要功能是进行同址运算，产生数据地址。同时为了节省资源，加大数据存储器的使用效率，每级处理单元提供了两个多路器，在地址发生器的控制之下，对进入数据存储器的数据予以处理，这样在FFT工作时每级数据存储器(双端口RAM)读和写的使用效率均为75％。

[0047] 数据存储器(RAM)用于存储中间运算结果。每个碟形运算单元的输入、输出数据均要经过RAM的读写操作。因此，RAM的频繁读写操作速度对FFT的处理速度影响较大。为了加快FFT的运算速度，需要构造双端口RAM来加快数据传输的吞吐量。

[0048] 在上述每级处理单元中，将旋转因子以查找表的形式预先存储在内置ROM(Read Only Memory，只读存储器)中，由于三角函数属第二、三、四象限的旋转因子均可由第一象限变换得到，所以本系统ROM只存储了第一象限的旋转因子数据。

[0049] 上述每级处理单元的处理过程主要包括：数据选择器1首先接收输入的两路数据，将该两路数据按照控制和地址产生模块所产生的地址，分别存储在RAMA和RAMB，其中RAMA和RAMB分别存储一路数据。同时，按照控制和地址产生模块所产生的地址，将每路数据所对应的旋转因子分别存储在ROMA和ROMB中。碟形运算单元从RAMA和RAMB中读取两路数据，数据选择器2按照控制和地址产生模块所提供的地址，从ROMA和ROMB中分别读取每路数据所对应的旋转因子，并将该旋转因子发送给碟形运算单元。碟形运算单元对获取的两路数据和相应的旋转因子，进行复数乘法和加法运算，将获取的计算结果存储在RAMA和RAMB中，并输出给下一级处理单元。

[0050] 上述每级处理单元由于使用了流水线的工作原理，FFT模块可不间断对数据进行处理，即在第一批64点数据输入完毕后不需等待即可输入下一批数据，因此若使用基-2FFT结构，每次处理2点，计算一次64点FFT模块只需要32个时钟周期。该实施例提供的一种FFT模块的输入输出时序图如图6所示，图6中开始信号(start)之间相隔32个时钟周期，结束信号(done)之间相隔32个时钟周期。

[0051] 上述FFT模块可以使用FPGA模块来实现。

[0052] 上述本发明实施例所述方法和装置适用于BD2(北斗2代)/GPS(Global Position System，全球定位系统)导航卫星接收机。

[0053] 综上所述，本发明实施例实现了每个时钟输入两个数据，输出两个计算后的数据，在124M时钟下，每秒能处理248兆个数据，可以提高卫星信号的伪码并行载波并行搜索方案中的FFT模块的数据处理效率，比单点输入和单点输出方案的效率提高一倍，而所用硬件资源没有明显增长。还是以一个商用IP核为例，该I P核计算128点的FFT，在FPGA内实现时占用逻辑资源为2444个LC，存储器为17170比特，而计算速度比商用IP快一倍。

[0054] FFT模块的资源使用少，在不降低效率的情况下，至少省50％的资源。FFT模块的配置灵活，可以通过增加FFT的级数来提高FFT的点数。

[0055] FFT模块的输出延时少，以64点FFT为例在输入第一个数据后104个时钟，FFT开始输出数据，适用于高速系统。

[0056] 以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求的保护范围为准。