目前卫星导航系统应用十分广泛,便携性与低成本是导航接收机未来发展的一个新趋势。其中信号捕获是导航系统基带信号处理的核心组成部分,是影响GPS接收模块功耗和成本的重要因素。传统的捕获算法分为时域和频域两种处理模式,但是无论是时域捕获(如时域串行捕获算法),还是频域捕获(如循环相关捕获算法),都是遵循奈奎斯特采样定理对信号进行采样,存在处理数据量大和消耗资源多等缺陷。GPS信号是由导航电文通过伪码进行扩频,再经过二进制相移键控调制形成卫星信号,这就使得接收的GPS信号具有稀疏性,因此可以运用一种基于压缩感知的GPS信号捕获算法。和现有捕获算法相比,该算法使用的测量值要少得多,大大降低了对系统采样率的要求。本文是以GPS信号捕获为基础,运用压缩感知理论来降低测量数据量,同时设计出高效的并行捕获算法以降低运算量。主要的研究工作有:首先,本文利用压缩感知技术实现GPS信号捕获,将数据量降低到半码片捕获精度要求的门限之下,同时提出高效的并行捕获算法以降低运算量。具体而言,首先利用C/A码构造正交基,运用高斯随机矩阵构形成合适观测序列,之后再进行信号的重构。其次,在压缩信号的重构中,由于典型的正交匹配追踪算法计算复杂度高,难以并行实现,从而设计了能够进行分布式处理的算法,即把压缩感知问题纳入坐标下降法框架和交替方向乘子法的框架。对于坐标下降法,把原压缩感知问题分解成多个相关联的子问题,沿着坐标方向进行逐一顺序解决。对于交替方向乘子法,原压缩感知问题被分解成多个相对独立的子问题并行迭代求解,充分利用了计算资源。最后把传统的捕获算法和基于压缩感知的捕获算法从捕获时间和捕获精度两方面进行对比,验证了算法的可行性。