全球定位系统（Global Positioning System；GPS），是当前全世界最普及的全球导航卫星系统（Global Navigation Satellite System；GNSS），GPS总共放置了多达32颗高度位于地表20200公里以上的卫星，均匀地分布在六个以55度倾斜于赤道的轨道面上。如此的设计提供高度的全球覆盖度，并使得几乎每一位使用者，在没有任何遮蔽物阻挡讯号的条件下，都可以拥有至少四颗以上的卫星在可视范围中以供定位之用。

GPS原先是由美国在20世纪中叶为了军事相关用途所开发，然而随着2000年5月美国柯林顿总统宣布关闭选择式供应（Selective Availability；SA）所造成的人为误差后，定位误差在一夕间从一百公尺降低到十几公尺，大开GPS方便应用之门。现在GPS已被广泛应用在其他领域，例如测量科学、航空安全、汽车及行人导航等，现今更成为许多手机的标准配备。 GPS会如此盛行的另一个主因就在于它可以提供高精确度， 却不向使用者收取服务费用。

与传统AM及FM广播系统类似，GPS也是从卫星到地面接收机的一种单向传输。与广播系统的差异在于GPS接收机并不只靠单接收以及处理一个卫星的讯号就可以完成定位，相反地，需要同时收到来自多颗卫星的讯号。透过还原隐藏在传输讯号中的导航资讯，接收机方可得到定位所需的两个重要资讯：首先是卫星的位置，接着是卫星到使用者的距离。有了超过四颗卫星的位置以及他们到接收机的距离估测之后，接收机便可以运用这些估测值来进行处理及决定其本身的位置、速度、以及时间（Position、Velocity、and Time； PVT）。一般说来，如果一个接收机可以掌握越多卫星讯号，则其对于位置估测的精确度便可以提高。然而实际上，并非所有的可视卫星皆可被成功接收。其主要的原因在于不同的卫星对于使用者有不同的仰角，导致信号的衰减或是接收讯号的强度并不一致，如果再加上使用者所在环境遭到建筑物或是其他物体遮蔽，都可能会造成有部份卫星讯号强度降低到接收机无法成功接收。在冷开机（cold start）的情况下，要知道究竟有哪些卫星可供利用，便得透过复杂且费时的搜寻过程，因此降低搜寻时间或是运算复杂度的方法就变的相当重要。
...
...