全球定位系统（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）的情况下，要知道究竟有哪些卫星可供利用，便得透过复杂且费时的搜寻过程，因此降低搜寻时间或是运算复杂度的方法就变的相当重要。

除了美国GPS定位系统外，欧盟也于近几年自行积极发展卫星导航定位系统，命名为伽利略卫星导航系统（Galileo），并于2006 年初开始透过第一颗实验卫星（GIOVE-A）成功传送Galileo卫星讯号，第二颗实验卫星（GIOVE-B）也于2008年4月成功发射，未来欧盟将陆续发射总共达30颗卫星（27颗工作卫星与3颗辅助卫星）于3个轨道面上，并预计从2013年开始提供服务。

有别于GPS，Galileo有两项特色，第一，其设计的初衷就是为了提供给民间广泛使用，与美、俄导航定位系统原以军事用途不同，因非军事用途之故，Galileo不受战争影响，政治力介入少，并以相容于现存GPS与GLONASS为目标。第二，Galileo运用30颗卫星，每10个均匀分布在三个轨道，定位误差可小于1公尺，可补足美国GPS误差达10公尺的缺点，更适合用于导航定位精确度要求高之应用，如紧急救援、飞机与船舶等。另外，Galileo卫星距离地面 24126公里，距离较GPS高，且轨道面比GPS更偏向赤道，故定位讯号传送可覆盖更广的区域。欧盟发展此系统，并与中国合作，除看好导航定位的潜在市场需求外，不让美国系统的GPS专美于前亦为重要的因素之一。 Galileo部分功能优于GPS，如较低的误差范围及更广域之讯号，成为GPS以外的另一项定位系统选择。但另一方面，基于民间用途，Galileo未来发展是以相容于现存GPS与 GLONASS为目标，是以互补关系为主。当GPS及Galileo完成建构之后，将可扩大全球的卫星涵盖进而增进可视卫星数 目，定位的精准度也可望大幅地提升。

讯号格式

GPS

《图一 GPS C/A码讯号格式示意图》

GPS卫星讯号的调变方法主要是基于二进位相移调变（BPSK），并利用分码多工（CDMA）的机制来作卫星区别。图一中，首先导航资讯以50bps的速率传送，意味着每一资料位元传输所需的时间为20ms，接着数位资讯都将在时域上乘上一组特别的C/A（Coarse/Acquisition）码[1]。 GPS的C/A码共含有1023个chips，以1.023Mcps的码速率传送，因此每个C/A码的周期为1ms，且每一个chip的长度为977.52ns或者代表大约300m的距离长度（考虑光速为3×108m/s）。如果一个接收机以16倍码速率的速度做数位取样，则理想上时序可以达到1/32的码同步误差，换算成距离误差大约就为10m左右。

回到图一，任一个导航资讯位元，将会包含着20个重复的C/A码。注意如图所示，C/A码的讯号边缘与导航资讯位元是对齐的，因此，接收机便可以透过同步C/A码的方式来找到导航资讯位元的讯号边缘。当导航资讯与C/A码相乘之后，透过升频的方式将讯号载波到L1频带（1575.42MHz）然后广播到地球。目前，C/A码只有在L1频带上传送，有别于针对军事上用途的P（Y）码（precision code），在L1以及L2频带（1227.6 MHz）上都有其讯号的成份。

Galileo

Galileo在几个不同频带都有传送讯号，由低频到高频分别是E5a（1176.45MHz）、E5（1191.795MHz）、E5b（1207.14MHz）、E6（1278.75MHz）、E1（1575.42MHz）[2] 。其中E1频带与GPS的L1频带重复，因此本文将只讨论Galileo在E1频带上提供的开放式服务。与GPS提供的服务类似，其导航码也跟C/A码一样是完全公开。与GPS不同，Galileo将其发送的讯号分成两个不同的通道做传输，分别命名为资讯通道E1B以及导引通道E1C。在导引通道里面，并不包含任何导航的数位资讯，真正可以用来导航的资讯只放在资讯通道上，导引通道的引入使得讯号在撷取及追踪都更容易。另外，Galielo传送的导航资讯都将会额外经过交错、以及在前向错误更正码中的回旋编码进行处理，进一步增强讯号的侦错能力。

《图二 Galileo E1B信息信道的讯号格式示意图》

参照图二E1B的传输讯号，可以发现导航资料位元的传输长度与GPS比较，从20ms缩短成4ms，与此同时，导航码则是增长到4ms，因此对于E1B来说，一个导航资讯位元将包含一个完整周期的导航码。与GPS一样，导航资讯位元与导航码的起始位置都相同，因此位元边际都是互相对齐的。 E1B的导航码共包含了4092个chips，使用与GPS的码速率相同的1.023Mcps的速度传送。与GPS系统最大的差异则是Galileo引进了新的调变方式，称多工二进制偏移载波调变（MBOC）。如图二所示，E1B的讯号除了将导航资讯乘以导航码之外，还要再多乘一个次载波信号。这个次载波由两个二进制偏移载波BOC（1,1）及BOC（6,1）分别乘上正规化因子√(10/11)跟√(1/11)之后相加所组成，因为Galileo的次载波都是以这种方式形成，所以又被称为复合二进制偏移载波（CBOC）。在图中BOC（m,n）的表示法主要是用来描述次载波频率为m×1.023MHz且码频率为n×1.023MHz。所以可以看到在BOC（1,1）中一个chip有一个完整周期的正弦方波讯号，而BOC（6,1）即代表着六个正弦方波讯号存在于一个chip内，显而易见的，BOC （6,1）的高频成份比BOC（1,1）更多。这一点也可以在接下来的功率频谱密度函数中看出来。

《图三 Galileo E1C导引信道的讯号格式示意图》

至于E1C的部份，如图三，由于其不需要负责传输任何导航资讯位元，取而代之的是一组固定的副码，其单一位元长度为4ms，一共有25个位元，所以总共长度为100ms。另外在次载波组合上也有些微的差异，在E1B上次载波为BOC（1,1）与BOC（6,1）乘上相对应的正规化因子后相加而成，反之，E1C上的次载波则是由乘上正规化因子的BOC（1,1），减去乘上正规化因子的BOC（6,1）组合而成。

马自相关函数及功率频谱函数

一个展频码c[n]的自相关函数r[n]可以表示成：

《公式一》

其中，Nc为码长度。在图四以及图五中，分别针对GPS C/A码以及Galileo E1B的导航码，绘出他们的自相关函数特性。从图中大略可以知道，一个好的展频码所必须具备的特性，就是自相关函数在两两讯号非同步时候的大小，必须尽量保持在与信号同步的时候有较大的差异。事实上，一般接收机也正是利用这个特性来做讯号同步。假设收到讯号的取样为x[n]，则透过交互相关值的测量 ：

《公式二》

其中，N为同步积分的长度，一般来说设计在码长度的整数倍。当交互相关的测量值大于某一设定的阈值时，接收机就可以基于当时测量的码相位去作讯号时序上面的同步。由于C/A码其实就是金氏码（Gold code）的一种，所以可以看到图四除了主峰值之外，C/A码的自相关函数在其他位置的大小只有三种可能，反观图五Galileo E1B导航码的自相关函数，由于其产生是基于一种记忆码，其在峰值之外的大小分布也比较不均匀。

《图四 GPS C/A码自相关函数》

《图五 Galileo 导航码自相关函数》

如果对峰值左右各一个chip的时间范围作放大，可以得到如图六的波形。 GPS的自相关函数在峰值附近呈现出一个三角波，而Galileo则比较陡峭，且除了主峰外还有两个高度较低的侧峰。波形改变的原因，主要是因为Galileo引进了次载波的调变，导致自相关函数以更快的速度向两边衰减至零，然后分别走至两端的负向侧峰。主峰宽度变窄主要的好处是导航距离误差的下降，这是由于在常用的信号追踪过程中，一个越陡峭的主峰可以在码鉴别函数中产生越陡峭的S曲线，进而降低杂讯的影响，提升讯号追踪准确度。

然而，随着主峰宽度变小，讯号撷取也更加困难。因为一般接收机在讯号撷取过程中，采用固定码相位间距去测量每个码相位上的相关函数值大小，以判定是否撷取到正确的讯号相位，所以主峰宽度越小，码相位搜寻间距也需要随之变小，以确保可以取样到主峰所在的码相位，且维持足够的讯噪比。然而间距缩小意味着在一个码周期里头，所需要测试的码相位变更多。如此将造成计算复杂度以及硬体成本的增加。

《图六 GPS C/A码与Galileo 导航码之自相关函数在峰值附近的放大图》

图七模拟产生GPS C/A码及Galileo E1B导航码的功率频谱密度函数，因为C/A码的码频率为1.023Mcps，所以造成如图上类似sinc2的频谱，其零点到零点的频宽为大约2MHz。反观Galileo的频谱，由于次载波调变的缘故，其频谱从中间向两旁偏移，与GPS频谱重叠的部份减少，因而，两个系统彼此的互相干扰也可以有效降低，这也是另一个采用次载波调变带来的优点。这种频谱偏移现象其实类似把一个基频讯号乘上一个载波调变到高频，只不过对于Galileo来说，乘上的这个次载波在基数倍码频率的位置都有能量存在。所以可以看到因为BOC（1,1）这个成份造成在1、3、5、7MHz左右有比较大能量的情形，而BOC（6,1）则导致在大约6MHz附近也有峰值的现象。此外，从频谱的资讯中也可以估计出要接收到主峰的讯号成份所需要之最小频宽，对于GPS来说是2MHz，Galileo是4MHz。

《图七 GPS C/A码与Galileo 导航码之功率频谱密度函数》

信号撷取

基频接收机架构

为了取得接收机的位置，基频的电路有三项主要任务：撷取、追踪、及导航。信号撷取的目的在于判定其可以掌握的卫星数量及卫星号码。为了决定哪一颗卫星是否要先作搜寻，通常会使用卫星搜寻演算法以决定哪一颗卫星有较高的出现机率。在完成信号撷取的程序之后，对于掌握到的卫星其频率以及码相位估测误差通常都不大，不过因为频率及码相位的误差皆非定值，因此接收机必须利用在信号撷取中所获得的资讯作讯号追踪，此程序会进一步改进前述两项估计值的精确度，直到估计值相对稳定下来后，才会把码相位的资讯及已经解调的导航资讯位元输出给后端的导航模组。

图八为一个典型的基频导航接收机主要的模组方块图，中频的讯号在数位取样过后，送到讯号撷取的通道去作处理，一般接收机为了加速搜寻卫星的速度，均采用多套撷取模组同时处理多颗卫星的搜索方式。在每一个撷取通道中，讯号因为都卜勒效应所造成的频率漂移会先被估测，为了考虑接收机本身的振荡器漂移，正负10kHz的搜寻范围是一般常用的设计值。为了加速频率搜寻的速度，在这个区间里头等间隔频率（如500Hz）将由频率数控震荡器产生出来。当接收讯号的频率误差被补偿回来之后，接着便是要去估计码相位，这部份由码数控振荡器产生的本地端复制码，会跟接收的信号作交互相关侦测，其结果就像图四与图五所示。当本地端的复制码跟接收讯号同步的时候，后端的相关性峰值验证将会依据事先决定的阈值判断此峰值所代表的码相位是否正确，如果相关值小于阀值，撷取通道将会持续改变都卜勒以及码相位的参数，如果所有可能的参​​数都已经测试过且都未能超过阀值，此时，接收机便判定目前搜索的卫星不存在或是讯号太弱，因此撷取通道将会再寻找下一颗可能出现的卫星。

《图八 导航接收机之基频架构模块》

时域上匹配滤波器

如前所述，在任何一个撷取通道中，必须对收到讯号的都卜勒频率以及码相位作估测的动作。搜索频率及码相位的过程可以用图九来做进一步的说明。在图中 二维平面上每一个小方格代表待测试的都卜勒频率及码相位。在导航的讯号撷取中，码相位所需要测试的数量会远大于都卜勒频率，以GPS的C/A码为例，考虑在讯号撷取时采取的频率解析度为500Hz及码解析度为1/2 chip，则接收机所需要测试的都卜勒频率分别为0、±0.5、±1、...、±10kHz共41组。但所需要测试的码相位却高达2046个。在Galileo的讯号中，因为码长度增为四倍及码解析度需求更高，这个差距将变得更大，因此一个快速搜寻码相位的演算法就更为重要。

《图九 序列式搜寻法在都卜勒频率：码相位之二维搜寻平面之示意图》

图十所示为一个基于匹配滤波器所实现，可用来测试码相位的快速相关器，可看到上下各有一长串的暂存器阵列，分别存着接收到的讯号取样点以及本地端的复制码，在本装置正式估算码相位之前，复制码将透过码数控振荡器，根据目前所欲搜寻的卫星码产生并依序输入码暂存器阵列中，直到复制码完全被读取。此时，一个完整周期的复制码取样将会存在下方暂存器中。反观上方的暂存器收到的讯号，随着每一次clock的驱动，新的取样值将存入暂存器、旧有的取样点各自往前移动到下一个暂存器、最后的取样点则会消失在暂存器阵列中。因此可以发现， 本地的复制码是固定的，只有收到的讯号在暂存器中移动，造成彼此所对应的相位差也持续在改变。所以只要在一个码周期的时间过后，这个匹配滤波器便可以输出 所有的码相位估计值。事实上，在每一次的clock驱动中，一个所对应的码相位估计就会被输出，后端的验证模组也可以立刻判断相关值的大小。这种在固定一个都卜勒测试频率下依序测试每个码相位的搜寻方式，又称为序列式搜寻。

《图十 运用匹配滤波器作讯号撷取》

《图十一 运用傅立叶变换作讯号撷取》

频域上傅立叶转换

随着快速傅立叶转换（FFT）演算法的成熟发展，对比在时域上计算码相位相关值的方式，将讯号藉由FFT转到频谱域上面作处理的想法也被提出[3]。其主要的精神是，在时域上作相关值的运算与回旋积分十分类似。而时域上两函数的回旋积分等同于在频域上作相乘。如图十一所示，将接收到的讯号先去除其残余的都卜勒频移，然后作傅立叶转换，与本地复制码傅立叶转换后的共轭复数作相乘，再透过IFFT转换到时域上，IFFT输出的资讯即代表了码相位的相关值大小。由于傅立叶转换演算法的进步，使得计算复杂度下降，因此在软体接收机上，在频域上用傅立叶转换的方式去作讯号撷取也比匹配滤波器的架构更受欢迎。由于傅立叶转换的处理方式乃接收一段资讯后做区块型的处理，因此采用这种搜寻方式为一种平行式的搜寻方法，如图十二所示。唯区块型的处理在实际应用上必须更小心处理资讯位元调变问题，以Galileo来解释，因为每个资料位元的长度为4ms，如果处理的区块刚好从一半2ms的位置开始抓取，则这收下来的区块必定包含两个位元的部份资讯。当两个位元的极性一致时，也就是同为+1或是-1时，则没有问题，但是当位元恰为反向时，则在做相关值计算时可以发现，即使讯号已同步，因为极性相反相关值的增益将互相抵销，导致讯号撷取失败，因此这也是傅立叶转换必须额外注意的事项。

《图十二 平行式搜寻法在都卜勒频率：码相位之二维搜寻平面之示意图》

缩短测试时间讯号撷取演算法

前文提到，Galileo所使用的码长度比起GPS C/A码来说变成四倍，这不单只是增加讯号撷取的复杂度，也使搜寻码相位所需的时间更长。本研究尝试不使用跟收到讯号内含一致的复制码，取而代之改变这个复制码的形式，让其可以更快撷取到卫星讯号。这想法源自于部份相关的方式以估测码相位，然而部份相关估测法存在一个严重的问题，就是如果实际接收讯号的码相位不存在这个部份码的话，则接收机便会错过可以搜寻到卫星的机会，除非有额外的验证机制存在。为了改善这项缺点，我们提出了回旋式位移后合并码（cyclically shift-and-combine code；CSC）[4]。

《图十三 CSC码的概念与形成方法》

利用图十三将这个概念简单的呈现出来。在这个例子中，只单纯考虑讯号时序上不同步的效应，其它例如杂讯、干扰、或是频率不同步的非理想效应先忽略不计。假设展频码的周期为12个单位，数字标记为代表其所对应的码相位，因为打算把原始的展频码缩短四倍，所以依序把展频码循环位移3个单位，总共位移3次。如图所示，便可以得到四个除了起始的码相位不同之外，其它特性完全相同的展频码，接着把这4个循环位移码相加起来之后可以得到一个新的码，这个新组成的码会有四个连续重复的部份，因此只需要保留其中一段即可，并称之为CSC码。透过这样的处理改变码的形式，CSC码的周期也缩短成原始展频码的1/4。

以图中接收到的一段讯号来说明CSC码仍旧具备撷取讯号的功能。这一段接收讯号的起始位置所对应到的展频码相位为2。图中CSC码第一个组成成份为0、1、2，将其向左循环式位移2个单位，则其2的成份可以与接收讯号对齐。再来看第四个组成部分3、 4、5，同样地，其中3及4的部份在向左位移两个单位后也可以与接收的讯号同步，至于其他组成的成份因为没有等同的接受讯号与之对应，所以将不会对相关运算的峰值造成贡献。如果把接收的讯号继续往后看三个单位5、6、7，同样可以归纳出这个结果，亦即当前接收到讯号的码相位为CSC码向左循环式位移两个单位的码相位。然而在此出现另一个须注意的事项：既然CSC码中包含了原始展频码的四段成份，所以无法得知真实的码相位是位在2、11、8、 5中的哪一个，因此，在使用CSC码作讯号撷取的过程中，虽然可以缩短所需要测试的码相位四倍，但是接收机随后必须额外再去测试四个可能的码相位。

《图十四 以Galileo的导航码形成CSC码的实例》

在图十四中，以实际Galileo E1B的导航码作测试，在这个实验中，假设接收讯号的真实码相位座落在500 chips的位置，因为原始的导航码为4ms，所以CSC码缩短成1ms ，其中包含了1023的chip，为了维持峰值的相对高度以利于后端的验证，接收2ms的长度作同步积分。由于CSC码的特性，可以在相位侦测500 chips的位置发现峰值。但真正的相位码偏移可能座落在500、500+1023、500+2×1023、500+3×1023 chips的码相位上。从这个例子中可以发现使用原本的导航码，接收机必须一一测试4092个不同的码相位，不过经由CSC码的帮助，可以将需要搜寻的码相位降至10​​23个，即使加上额外4个码相位的验证，总共只需要1027个，因此可大幅降低所需的搜寻时间。

《图十五 利用原始导航码作讯号撷取之二维搜寻平面图》

《图十六 利用CSC码作讯号撷取之二维搜寻平面图》

图十五、十六分别显示原始导航码以及CSC码在二维讯号撷取平面图所得到的模拟图，在这个实验中各项参数的设定如下：都卜勒频率的偏移为2500Hz，接收讯号的讯杂比设定在45dB/Hz，同步积分时间为4ms。另外刻意把接收讯号的码相位移至2546。再次从图十六中看到CSC码，可以正确在码相位500的位置侦测到峰值，当然更进一步验证其他四个可能的码相位是必须的。接着从这两张图可以比较发现，使用CSC码会造成峰值与非峰值之间的差距变小。会造成这样的效应主要是因为在CSC 码中，除了与接受讯号同步的区块之外还有其他的部份，因为与接受讯号不同步，造成类似干扰的效应。

结论

本文回顾现今已经被广泛使用的GPS系统，了解其展频码在自相关函数以及功率频谱函数上的特性。同时也介绍了欧盟下一代的Galileo导航系统，以及其在同样是1575.42MHz载波上的导航码与GPS C/A码之异同，随着多工二进制偏移载波（MBOC）调变的引入，下一代的导航将可以拥有更精准的位置估测。但实际上其带来许多设计上新的挑战有待克服， 其中一个便是因为码长度增加所造成的复杂度提升以及搜寻时间变长。本文提出了新的想法以改变本地端复制码的形式，可以大幅度的减少所需搜寻的相位，虽然使用本文的方法会造成讯号撷取上峰值的相对高度降低，然而，在多数室外应用场合卫星讯号的强度品质通常良好，这个时候便可以利用本文供的方法对存在的卫星作更快速地搜寻。

参考资料：