英语原文共 5 页，剩余内容已隐藏，支付完成后下载完整资料
基于稀疏傅里叶变换的更快的GPS
Haitham Hassanieh Fadel Adib Dina Katabi Piotr Indyk
计算机科学与人工智能实验室
麻省理工学院
{haithamh，fadel，dk，indyk}@mit.edu
摘要：
GPS是最广泛使用的无线系统之一。 GPS接收机必须锁定卫星信号来计算其位置。锁定在卫星上的过程相当昂贵，需要数亿次的硬件乘法，从而导致了高功耗。该问题最快的算法是基于傅里叶变换的，并且具有O（n log n）的复杂度，复杂度中的n是信号样本的数量。
本文介绍了迄今为止最快的GPS锁定算法。该算法将锁定复杂度降低到O（nradic;logn）。此外，如果SNR高于阈值，则算法变为线耳，即O（n）。我们的算法建立在稀疏恢复增长领域的最新发展。它利用同步问题的稀疏性，其中只有接收的GPS信号和卫星码之间的正确对准导致其互相关峰值尖峰。
我们进一步表明，理论收益转化为GPS接收机的经验增益。具体来说，我们使用软件无线电设计了一个设计原型，并在美国和欧洲收集的两个GPS数据集上进行了测试。结果表明，与实际GPS信号的现有技术设计相比，新算法将乘法中值减少了2.2倍。
类别和主题描述符C.2 [计算机系统组织]：计算机通信网络
一般术语：算法，设计，性能，理论
关键词：GPS，同步，稀疏傅里叶变换
一、简介
全球定位系统(GPS)是最普及的无线技术之一。它在全球范围内的多款智能手机上都有它的应用，并嵌入了各种各样的设备，包括个人导航系统、传感器、数码相机，甚至是超肤生物芯片。
GPS接收机的关键功能是计算位置，称为定位。定位的计算包括锁定GPS卫星信号和解码卫星轨道和时间数据。然而，大多数GPS接收机都嵌入了一些其他无线电（例如，WiFi，Cellu或ZigBee），因此可以从辅助GPS（A-GPS）服务器下载GPS信号的内容，而不是从卫星信号解码服务器。GPS广泛应用于手机和其他具有GPS功能的设备，GPS接收机的主要部分是锁定卫星信号（即与其同步）。这要求接收器能够拥有计算其位置所必需的亚毫秒同步化的延迟计算。锁定的重要性进一步强调了现在的GPS接收机通常是负载循环的。因此，他们需要定期与卫星信号重新同步。然而，与卫星信号同步是一个昂贵的过程，需要数千万到数十亿次数字乘法。许多启用GPS的设备（例如，移动电话，传感器等）具有严格的功率限制，并且将明显的从减少该过程的复杂性中受益。
本文旨在降低与GPS等弱信号同步的成本。在高水平上，GPS同步工作如下：每个卫星被分配一个CDMA码。对于每个卫星，接收机需要将相应的CDMA码与接收的信号对准。这个过程很复杂，因为GPS信号非常弱（比噪声水平低20 dB）。 为了找到每个卫星的正确对齐，GPS接收机进行搜索过程。它计算CDMA代码与接收到的信号的相关性，用于对信号进行重新分析的代码的所有可能的移位。正确的移动是最大化相关性的移动。
那么，GPS接收机如何计算所有这些偏移的相关度？ 传统方法在时域中将接收的信号与每颗卫星的CDMA码进行卷积。正确的对齐对应于最大化该卷积的对齐。更近期的GPS接收机使用频域计算来锁定卫星。 这种方法杠杆化了时域中的卷积对应于频域中的乘法的事实。 它在以下三个步骤中进行，如图1所示。 1：1）接收机接收接收信号的FFT; 2）将该傅立叶变换的输出乘以CDMA码的FFT; 和3）对所得到的信号执行逆FFT。 这个3步过程在数学上等同于将信号与代码进行卷积; 因此，逆FFT的输出将以与接收信号同步的正确移位尖峰，如图3所示。1D。 这种方法的计算复杂度为O（n log n）。 在过去二十年中，这是一种具有最低计算复杂度的算法，用于同步GPS接收机。
本文介绍了迄今为止最低复杂度的GPS同步算法。我们的同步算法是基于以下观察：
首先，我们注意到，由于同步过程的输出在正确的位移处具有单个主峰值，如图1所示。 1d，逆FFT非常稀疏。稀疏FFT的问题近来受到计算机科学界的广泛关注，导致了可以在亚线性时间内计算稀疏信号的FFT（或逆FFT）的新算法。构建在这些进步中显着降低了GPS同步算法的运行时间。然而，存在的稀疏FFT算法使用相对复杂的滤波器（例如，Dirichlet [11]，Gaussian [14]或Dolph-Chebyshev滤波器[15]）来处理变换输出处的多个潜在尖峰的相互作用。相比之下，我们利用同步问题只产生一个尖峰，并设计一个简单的子线性算法，它只使用混叠来过滤信号。这允许我们降低图1中IFFT步骤的复杂性。
尽管逆FFT的输出稀疏且可以快速计算，频域中的GPS信号并不稀疏，因此，通过应用稀疏变换，不能减小正向FFT的运行时间。然而，简单地使用稀疏逆FFT不会降低问题的整体复杂性（由于正向FFT，这仍然是O（n log n））。为了解决这个问题，我们注意到图中的FFT.1b只是一个中间步骤，将用作稀疏IFFT的输入。由于稀疏的IFFT算法（包括我们的）算法仅在其输入信号的子集上运行，所以我们不需要计算这些值在正向FFT的输出处的所有频率。我们利用此属性仅计算频率的一个子集，并减少FFT步骤的复杂度。
我们提供一种算法，对于任何SNR，与原始的基于FFT（或基于卷积的）算法一样精确，但将计算复杂度从O（n log n）降低到O（）。此外，当接收到的信号中的噪声可以被O（n / log2 n）限制时，我们证明相同的算法具有线性复杂性。
我们在GPS信号的两个数据集上实现我们的设计和测试：我们使用软件无线电收集了美国的第一个数据集。第二个数据集在欧洲收集.5数据集涵盖城市和郊区。我们将设计与基于FFT的同步算法进行比较。我们的设计减少了用于检测正确移位中值为2.2times;的乘法数。由于GPS功率的很大一部分被同步过程消耗（30％至75％取决于准确度），我们预计新设计可以显着降低GPS功耗。
贡献：本文对算法和系统的贡献进行了总结如下：
本文提供了迄今为止将GPS接收机与卫星信号同步的最快算法。该算法具有多个特征：（1）自适应，即如果SNR较高，则可以更快地完成; （2）它在非常低的SNR下继续工作;（3）通常，即它可以用于使任意信号与随机（或伪随机）码同步。
本文提供了对实际GPS信号的实现和经验评估，表明算法增益转化为GPS接收机执行的操作次数显着降低。
2.GPS PRIMER
GPS接收机的关键功能是使用从GPS卫星接收的信号来计算其位置。 为了做到这一点，接收者计算信号从每个卫星到自身的行进所需的时间。 然后将计算出的时间乘以光速以获得其与每颗卫星的距离。 结果，接收机知道它位于以该卫星为中心的球体上，其半径是计算出的距离。 然后，它将它的位置确定为几个这样的球体的交点，通过一个称为三边形的方法[20]，如图2所示。
图2-三角测量：确定不同卫星的距离后，接收机可以绘制以每个卫星为中心的半球，其半径为相应的距离。这些球体应在接收者的位置相交。 GPS接收机需要四颗卫星来唯一确定其位置[20]。可以使用额外的卫星来校正接收机的时钟与卫星的时钟之间的非常紧密的同步性。
但接收机如何计算卫星的传播时间？传播时间使用允许设备锁定接收信号的同步算法获得。具体来说，每个卫星都有自己的CDMA码，称为C / A码，由1023个码片组成[20]。假设接收机和卫星的时钟完全同步，则GPS接收机在与卫星同时产生卫星的码。然而，由于传播延迟，信号在接收机处以移动版本到达准确的信号从卫星行进的时间量。通过与卫星码的移位版本相关，接收机将传播时间计算为相关峰值的移位[36]。实际上，接收机的时钟与卫星的时钟不完全同步;然而，通过增加三边测量过程中使用的卫星数量，可以补偿这一情况
卫星的运动在接收信号中引入了多普勒频移。该信号与C / A码不相关，除非校正多普勒频移。为了解决这个问题，GPS设备通常对接收到的信号进行二维搜索[20]：一个用于时间（码移），一个用于多普勒频移。具体来说，接收机尝试所有可能的码移，以及在中心频率的 /- 10kHz内的等距间隔的多普勒频移[36]，如图1所示。最后，GPS卫星对每个数据位重复20次代码，使GPS接收机解码非常弱的信号。接收器尝试使用一个代码重复进行同步。然而，如果信号太弱，接收机将重复2D搜索多个代码并求和结果[20]。
3.QuickSync
我们描述了QuickSync，GPS接收器的同步算法。该算法在频域中工作，类似于sect;1中描述的基于FFT的算法。然而，QuickSync利用同步问题的稀疏性，只有接收到的GPS信号和卫星代码之间的正确对准才能使其互相关相关。 QuickSync利用此属性在比O（n log n）快的时间内执行傅立叶和傅立叶逆傅立叶变换，从而降低GPS同步的整体复杂度。下一小节使问题正式化并详细说明算法。
3.1问题制定
同步问题可以表达如下：给定一个扩展码c = ，... ，和接收信号x = ，...，，找到使c和x之间的相关性最大化的时移t，即计算：
Ť
其中是循环卷积，是时间反转代码;即 = ...，c0。在时间do-main中计算该卷积需要执行每个大小为n的n个相关，因此具有复杂度O（n2）。然而，时域中的卷积对应于频域中的逐个元素乘法。因此，计算公式1可以通过在每个代码和信号上执行FFT，乘以那些FFT，然后执行逆FFT（IFFT），如下所示，可以更有效地完成：
其中（.）是FFT，（.）是IFFT，*是复数结点，t是卷积输出向量中的任何时间样本。这将同步过程的复杂度降低到O（n log（n））。因此，在本文的其余部分，我们只考虑基于FFT的同步算法作为评估QuickSync性能的基准。在引入同步算法之前，我们提醒读者傅立叶变换的基本属性，我们在设计中依赖：在时域中混叠信号是等效的
图4-混叠和二次抽样的二重性。时域中的混叠对应于频率do-main中的子采样，反之亦然。折叠（混叠）左上角的时域信号导致右上角的信号;具体来说，时间样本1和6将混叠信号中的样本1加入样本2和7到样本2等。在傅立叶域中，混叠信号的FFT是初始信号的FFT的子采样版本;即右下方信号中的样品1对应于左下方的样品2，样品2对应样品4等。
在频域中对其进行子采样，反之亦然。
形式上，让x为长度为n的离散时间信号，X为频率表示。令x是x的版本，其中大小为B（其中B除以n）的相邻窗口在彼此之上被别名（即，将p = n / B分开的样本相加）。那么，对于t = 0... B - 1：
因此，X，x的FFT是X的子采样版本，对于f =0...B - 1
其中p = n / B，Xpf中的下标是指索引为ptimes;f的样本。
3.3 QuickSync算法
我们描述了QuickSync如何对接收到的GPS信号进行操作，以将其与内部生成的C / A代码进行同步。为了简单，我们假设输入信号既不表现出载波频率偏移也不表示多普勒频移;在后面的部分，我们扩展算法来处理这些频率偏移。此外，在本节中，我们描述了GPS接收机与只有一颗卫星的信号同步的上下文中的算法;该算法可以容易地适应于与多个卫星同步。
对于我们的算法的关键观点是，在基于FFT的同步算法的步骤3中执行的IFFT在时域中是稀疏的，即它仅具有一个尖峰，并且因此可以在亚线性时间[ 14。此外，用于计算稀疏IFFT的子线性时间算法将需要子线性数量的样本作为输入;因此，不需要对接收到的GPS信号执行完整的nlog n FFT并获得其所有n个频率采样。相反，我们只需要计算将用于执行稀疏逆FFT的频率样本。
下面，我们将解释我们如何利用这些想法来减少IFFT和FFT的复用，以使信号与代码同步。然后我们将这些组件放在一个完整的算法中。（a）稀疏IFFT。
灵感来自于近期关于稀疏傅里叶逆变换的工作[14,11]，我们开发了一种简单的算法来有效地执行GPS同步的IFFT步骤，并快速识别接收信号与CDMA码之间相关性的尖峰。为此，我们的算法使用信号样本的子线性数。
稀疏IFFT算法进行如下。它首先将大小为n的频域信号乘以p的因子。然后，通过这些n / p个频率样本计算IFFT。回想一下，频域中的子采样等效于时域中的混叠。因此，我们的IFFT步骤的输出是图1所示的原始IFFT步骤中的输出的混叠版本。这里的混叠可以被看作是一种散列形式，其中n个原始输出采样（即时移）被散列成n / p桶。时间间隔n / p将在我们的IFFT的输出处在同一个数据桶中进行总结和散列。由于在IFFT的输出中只有一个相关关系尖峰，所以它所散落的桶的大小将显着大于只有噪声样本哈希的其他桶的大小。因此，该算法在我们的IFFT的输出端选择n / p个桶中具有最大幅度的桶。
在将该混叠（或散列）的p时间段转换到该桶中，只有一个是实际的相关峰值。为了识别这些p候选移位中的尖峰，算法将接收的信号与CDMA码的那些p个移位相关。产生最大相关性的偏移是正确的峰值。
在我们的同步算法中使用混叠作为散列形式，与稀疏FFT算法（如高斯和Dirichlet分组[15,11]）中使用的其他形式的散列相反，具有两个主要优点：
bull;简单性：子采样可以简单地通过在输入的子集上获取大小为n / p的小IFFT，并且不需要任何其他复杂处理，例如随机哈希。
bull;无泄漏：在二次抽样中，每
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[138318]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
