北斗卫星导航定位系统(BDS)作为我国正在研发并建设的具有自主知识产权的全球卫星导航定位系统,对我国甚至全世界的相关应用领域产生了巨大的价值。而随着卫星导航应用需求的增长以及快速定位的要求,北斗信号的捕获跟踪复杂度成为了卫星接收机的一个重点研究方向。当前在北斗卫星捕获跟踪阶段通常采用基于离散傅里叶变换的并行码相位的捕获算法来进行捕获。相较于时域串行捕获,算法能大大缩短捕获的时间,但对接收机硬件资源的要求较高。为了快速定位以及减少卫星接收机的硬件资源消耗,我们需要寻找算法复杂度更低的算法来进行捕获跟踪从而达到这一目的。本文针对卫星定位捕获跟踪算法复杂度高,运算量大的问题,从如下方面展开了研究:第一,介绍了北斗卫星信号的结构,分析了常用的捕获跟踪方法和步骤,对采用基于离散傅里叶变换的并行码相位的捕获算法做了仿真,成功对信号进行了捕获跟踪。第二,在采用并行码相位捕获的基础上,通过平均相关的办法,将信号的采样点数变为2的整数次幂,从而变DFT为FFT,大大的减少运算量。提出了一种本地码二次采样法,在做平均相关的降低运算量的同时,获得更优的性能。本文对这种方法进行了仿真,成功捕获到了信号,并和基于离散傅里叶变换的并行码相位的捕获算法从性能和运算量上进行了对比。第三,通过对卫星信号结构的分析,利用卫星导航信号的稀疏性,引入了提出不久的稀疏傅里叶变换,根据卫星信号特点对其作了部分修改,提出了一种简化的基于稀疏傅里叶变换的捕获方法,在损失部分性能的情况下,减少了算法的运算复杂度。本文对这种方法进行了仿真,成功捕获到了信号,并与之前基于采用改进的平均相关的捕获算法从性能和运算量上进行了对比。第四,引入了地面差分站,讨论地面差分站辅助数据对整个捕获跟踪阶段算法复杂度的影响。通过对辅助数据的计算可以求得多普勒频移的预估值和频率误差值和码片相位的范围,降低了频率搜索范围,将其带入基于稀疏傅里叶变换的捕获算法中,改进了上文提到的稀疏傅里叶变换的复杂度,降低了整个算法的运算量。在接收机设计与实现的过程中,采用低复杂度的捕获跟踪算法能够降低硬件资源的开销,实现信号的快速及可靠捕获跟踪,从而达到各行业对捕获跟踪快速准确的捕获跟踪要求。