GPS信道译码的DSP实现

1、DSP应用GPS信道译码的DSP实现通信与信息系统 21200602137 吕婷婷 摘要：本文重点探讨应用DSP技术实现卫星定位系统的信道译码方法：卷积编码的Viterbi译码技术，并介绍使用T1公司的高速数字信号处理器TMS320C55x在T1公司集成DSPs软件开发环境CCS下实现这种译码技术。 关键词： 卷积码 Viterbi DSP一、 概述卫星导航系统中的一项关键技术就是信道译码，GPS系统中的信道译码使用的卷积码。这种编码是一种线性纠错码，具有较好的差错控制能力。GPS系统使用的是码率为1/2的（2，1，7）卷积码，并利用Viterbi译码算法进行信道译码。使用汇编语言实现维特比译

2、码器功能，它不仅译码算法简单，易实现，而且可以得到较大的编码增益，具有良好的纠错编码功能，是一种软件方法的前向纠错编码技术。实验结果表明：应用软判决维特比译码算法时的误码率低于应用硬判决算法的误码率，一般要比硬判决算法多大约2dB-3dB的增益；约束长度越大误码率越低，译码性能越好。约束长度每增加一位，就可以提高0.5dB的增益；但在码率约束长度不变时，硬判决算法的执行速度比软判决算法快。二、 DSP产品的主要特点信息化的基础是数字化。数字化的核心技术之一是数字信号处理。数字信号处理的任务在很大程度上需要由DSP器件来完成。DSP技术已成为人们日益关注的并得到迅速发展的前沿技术。DSP（数字信

3、号处理器）作为一种微处理器，其设计的出发点和通用CPU以及MCU等处理器是不同的。DSP是为完成实时数字信号处理任务而设计的，算法的高效实现是DSP器件的设计核心。DSP在体系结构设计方面的很多考虑都可以追溯到算法自身的特点。l 对密集的乘法运算的支持DSP处理器使用专门的硬件来实现单周期乘法。DSP处理器还增加了累加器寄存器来处理多个乘积的和。累加器寄存器通常比其他寄存器宽，增加保护为来的指令集都包含有显示的MAC指令。l 存储器结构大多数DSP使用了哈佛结构，将存储器空间划分成两个，分别存储程序和数据。它们有两组总线连接到处理器核，允许同时对它们进行访问。这种安排将处理器存储器的带宽加倍，

4、更重要的是同时为处理器核提供数据与指令。在这种布局下，DSP得以实现单周期的MAC指令。DSP使用多个片内存储器和多组总线来保证每个指令周期内存储器的多次访问。在使用DSP时，程序员要明确地控制哪些数据和指令要存储在片内存储器中。程序员在写程序时，必须保证处理器能够有效地使用其双总线。l 专门的寻址方式DSP处理器往往都支持专门的寻址模式，它们对通常的信号处理操作和算法是很有用的。例如，模块（循环）寻址（对实现数字滤波器延时线很有用。位倒序寻址（对FFT很有用）。l 定点DSP指令集定点DSP指令集是按两个目标来设计的：使处理器能够在指令周期内完成多个操作，从而提高每个指令周期的计算效率。将存

5、贮DSP程序的存储器空间减到最小（由于存储器对整个系统的成本影响很大，该问题在对成本敏感的DSP应用尤为重要）。为了实现这些目标，DSP处理器的指令集通常都允许程序员在一个指令内说明若干个并行的操作。例如，在一条指令包含了MAC操作，即同时的一个或两个数据移动。在典型的例子里，一条指令就包含了计算FIR滤波器的一节所需要的所有操作。这种高效率付出的代价是，其指令集既不直观，也不容易使用。对于DSP的程序员来说，主要的DSP应用程序都是用汇编语言写的（至少部分是汇编语言优化的）。这里有两个理由：首先，大多数广泛使用的高级语言，例如C，并不适合于描述典型的DSP算法。其次，DSP结构的复杂性，如多

6、存储器空间、多总线、不规则的指令集、高度专门化的硬件等，使得难于为其编写高效率的编译器。即使用编译器将C源代码编译成DSP的汇编代码，优化的任务仍然很重。典型的DSP应用都具有大量计算的要求，并有严格的开销限制，使得程序的优化必不可少（至少是对程序的最关键部分）。因此，考虑选用DSP的一个关键因素是，是否存在足够的能够较好地适应DSP处理器指令集的程序员。l 开发工具的要求因为DSP应用要求高度优化的代码，大多数DSP厂商都提供一些开发工具，可以帮助程序员完成其优化工作。例如，大多数厂商都提供处理器的仿真工具，以准确地仿真每一个指令周期内处理器的活动。无论对于确保实时操作还是代码的优化，这些都

7、是很有用的工具。三、 VITERBI译码的算法和实现卫星定位系统使用的卷积码作为常规信道纠错编码手段。Viterbi算法是使用最广泛的卷积译码算法之一，它用于描述整个纠错过程，其中主要用于译码。作为卷积码的一种最大似然译码算法，VA具有最佳的译码性能，但是硬件实现复杂。我们可以用软件的方法实现Viterbi译码过程。GPS为了保证其性能，使用了约束度为7的卷积编码，Viterbi译码的寄存器状态数也相应达到64，本文给出高速Viterbi译码算法，仅占用少量的系统资源，不必借助片外内存就可以实现译码算法。1、 Viterbi的译码环境在Viterbi译码的实现过程中，硬件基于T1的DSK开发板

8、，而将开发板上带的调试开发工具CSS作为软件开发环境。C55x通过增加功能单元，与C54x相比，其综合性能提高了5倍，而功耗仅为C54x的1/6。C55x采用变长指令以提高代码效率，增强并行机制以提高循环效率，不仅仅增加了硬件资源，也优化了资源的管理，所以性能得到了大大的提高，其处理能力可达400800MIPS。C55x在CPU的功能单元方面坐了如下扩展：（1） 总线增加了两条，一条读操作线(BB)，一条写操作线(FB)；（2） 乘加单元(MAC)增加了一个；（3） 增加了一个16bit的ALU；（4） 将累加器增至4个，即AC0,AC1,AC2,AC3;（5） 临时寄存器增至4个，即T0,T

9、1,T2,T3。本系统采用的是TMS320VC5510。硬件环境：DSK是T1公司的低成本代码开发工具，它的特点是功能全，价格低，代码编译速度快，使用简单。DSK包括一个基于TMS3200SPs的电路板。相应的代码产生工具和调试器。DSK板上带有模拟输入输出接口，DSK的汇编器和调试器都是相应商用版的简化版。利用板上的模拟输入输出接口，可以直接对DSP系统进行性能测试和评估。软件环境：Code Computer Studio(CCS)是T1公司推出的一个集成DSPs软件开发环境。它是一个完整的为开发T1 TMS320C2000,TMS320C5000,TMS320C6000系列DSP而设计的。

10、CCS不仅包含代码生成工具，具有基本调试功能，而且具有实时调试功能，而且具有实时分析能力。它支持整个软件开发过程：从方案设计、代码生成调试、实时分析等。2、 卷积编码和Viterbi译码数字通信中的纠错编码技术能提高通信的可靠性，所以自它出现以来就一直受到各国科学家的广泛关注。纠错码的基本思想是：在编码过程中，同感所传输的信息设置附加的校验位，即增加其冗余度，使原来无规律或规律性不强的一组信息具有某种相关性；接受信息时再根据这种相关性来译码，使编码信息具有检测或纠错的性能。卷积码是一种纠错码，它把信源输出的信息进行分段，通过编码器进行编码，编码后的码段的监督元不仅与本段信息有关，还与其前面的几

11、个段信息有关。 Viterbi译码算法（VA）就是从可能发送的码字中，找到一个与接收数据段为相似的码字。它利用码树的高度重复，对最大似然路径的选择上进行了优化，大大降低了用于搜索整个码空间的计算次数，减少了存储量，使约束度的增加成为可能。 近几年，由于译码算法简单、易实现，并且可以得到较大的编码增益，应用维比特算法的卷积码得到了广泛的应用。它尤其适合用于倍加性的高斯白噪声所污染的传输信道，比如GPS系统卫星向接收机发送的信号就使用了卷积码作为信道编码。本文实现的是应用于全球定位系统卫星信道编码中的约束度K=7、N=2、b=1、码率为R=1/2的卷积码中译码。卷积码的编码过程是由移位寄存器和模2

12、相加器组成的，如下图所示： 图1（2，1，7）卷积码编码器编码过程示意图信息位输入到移位寄存器中，经过抽头的提取，采用模2和的方式来产生输出。可以看出，整个编码过程可以看作输入信息序列与由移位寄存器和模2和连接方式所决定的另一个序列的卷积。编码过程中用到的输入位数成为约束长度，它的值等于延迟单元的数目加上1。编码速率则指的是移入编码器的位数与进入信道的位数的比率。在上图中，对应于每一个输入，有两个输出进入信道传输，因此编码速率为1/2。需要注意的是当序列发送完毕后，为了在译码时判断其最后结果，要在网格结束处加上N-1个0作为结束信息。 卷积码译码过程可能的状态转移表可以由网格图来表示，卷积码译

13、码器就是通过找出网格图中码的最大可能序列完成译码过程。一个K=3，编码速率R=1/2的卷积码，网格图如图下图所示： 图2 卷积码的网格表示 图中延迟状态(指编码器的状态)的数目由约束长度决定。例如，约束长度K=3，延迟状态的数目就是;路径状态G0,G1，指的是编码器的输出。 卷积码译码时，根据接收到的数据估算延迟状态序列(在这里，延迟状态代表了编码数据)，在网格图中重建一条路径作为信息序列路径，以满足译码路径最大可能的与发送序列相似。Viterbi译码算法就是这样的一个译码器，它把汇聚在每个节点上的2条路径的对数似然函数累加值进行比较;然后把具有较大对数似然函数累加值的路径保存下来，称此部分路

14、径为留选路径;经挑选后第K级只留下条幸存路径，选出的路径连同它们的对数似然函数累加值一起被存储起来。因每个节点引出2条支路，因此以后各级路径数目都增大一倍;但比较它们的似然函数累加值后，又丢弃一半，结果存留下来的路径总数保持常数。由此可见，译码过程中的基本操作是对路径量度相加、比较，选择出幸存路径。当收到结束信息时，因每一状态只有与已知发送信息相符的那条支路被延伸，因而在每级比较后，幸存路径减少一半。因此，在接收到K-1个结束信息后，整个网格图就只剩下一条路径了。这就是译码所得路径。图3、维特比译码流程图 下面对流程图作一个简要说明：（1） 权值的更新过程：在权值更新单元中，本地距离用于计算似

15、然函数的累加值即权值。对于软判决输入，常用欧几里德距离计算本地距离：其中表示软判决输入，代表每一个路径状态的期望输入，是与路径数据即当前状态相关的，由编码多项式代表接收到的数据，与当前状态无关。C是编码速率的倒数。考虑到和项对所有的路径都是相同的，因此它们可以不计算，本地距离可以表示为: 除掉常系数一2，则编码速率C=1/2的卷积码的本地距离可以简单记为: 。将编码表示为0值代表十1, 1值代表示一1，这样就进一步简化了计算步骤。 (2)路径回溯单元: 回溯运算将从转移数据状态次序表中找出正确的转移字并从转移字中找出正确的比特位。一个码间隔的转移数据如下表1 表1 一个码字间隔内转移数据状态次

16、序表3、 Viterbi译码的实现 GPS中使用的卷积码约束长度为7，有个状态。实现这种状态数多的Viterbi译码器，对DSP的处理速度要求很高。Viterbi译码的大部分时间消耗在路径的“加一比一选”上面。C55x系列因其片内专用的硬件乘法器和特殊的DSP指令，所以能够快速完成这些运算。TMS320C55X器件集成了一个特殊的CSS硬件单元来加快Viterbi运算权值更新计算。K=7的蝶形单元如图4所示: 图4 蝶型单元示意图此图表示出了各个状态沿相应路径从旧权值转移到新权值的路径状态。其中2*j,2*j+1是旧状态即路径比较的出发点，j, j+为新状态。M是1/2码率的卷积码的分支度量值

17、。一次蝶形运算包括至少需要四次加法，两次比较，两次转移，四次存储器读，两次存储器写和相当数量的寻址操作。 TMS320C55X完成的Viterbi译码的代码可以分为三部分:初始化，权值更新，回馈。l 初始化 初始化主要完成各存储区的初始化设置。其中包括:输入、输出缓冲区分别存储译码前和译码后的数据;状态转移表存储幸存路径的选择历史，作为回溯译码时的唯一依据。输入数据缓冲区是一个长度为FS/CR个字的线性缓冲区，其中FS是原始帧的比特数目，CR是经过删除后的编码速率。因为每一个被传输比特在软判决时以一个多比特字的形式接收，因此该缓冲区比帧长度要大。输出缓冲区内存储每个码元周期内的单比特数值，长度

18、为ES/16。状态转移表的大小是由约束长度和帧长度共同决定的的缓冲区。 状态值初始化时，由于除状态0之外所有的状态都可用于存储更新后的权值，所以都初始化为相同的初始权值0x8000，而状态0则可初始化为0.l 权值更新 权值更新耗费了译码过程的大部分时间。对于(2, 1, 7)码来说，每一个比特时间间隔，有64个状态度量值需要更新。权值更新分为以下4步: (1)分支距离权值的计算 对(2, 1, 7 )码，2个路径状态比较。分支度量值可以分别用T0和T1表示为。分支距离权值有3种情况:2条路径状态完全相同时，分支距离权值为2; 2条路径状态有一位相同时，分支距离权值为0; 2条路径状态完全不同

19、时，分支距离权值为一2，因此可通过对3种情况的判断得出分支距离权值。 (2)求距离权值累加和 用两个辅助寄存器作为累加器，然后把存储单元中的数与分支距离权值寄存器中的数相加，存放在累加器中，完成2条路径的距离权值的更新。 (3)选择存储大权值 比较2个累加器的值，将小的权值放到存储单元中，完成权值的存储。在权值的更新过程中，需要128个存储单元分别来存储旧权值和新权值。存储方案如下: 图5 权值存储方案 (4)存储被选路径的标号 选择小的权值存储到存储器后，用一个二进制位来标记这条被选择路径，并将这个二进制位存储到状态转移表中。具体操作为:进入每一状态的2条路径选择上面的一条，就标志0，选择下

20、面的路径，就标志1。每个状态需要1位，64个状态共需64位，即4个字。 编码器有64个状态，可以用6位状态字表示。最高2位表示了一个字在转移表中的位置，其他4个位表示了一个比特位在转移字中的位置， 当C=1/2时，本地距离权值:。在C55x中可以用特殊应用指令ADDSUB, SUBADD和MAXDIFF来完成各个状态路径度量值的累加、比较和选择，而且可以充分运用C55x的流水线处理优势口为了方便调用，可以将利用流水线处理的维特比蝶形运算定义为两个宏。BFLYA .macro pADDSUB p,*AR5+,ACO ;ACO=OLD_M(2*J)+p/OLD_ M(2*J)-pSUBADD p,

21、*AR5+,ACl ;ACl=OLD_M(2*J)-p/OLD_M(2*J+1)+pMAXDIFF ACO,ACI,AC2,AC3 ;NEW_M(J)=MAX(ACO39-16,ACl39-16)MOV AC2,*AR4+,*AR3+ ;TRNO=TRN#1 ;if Hi(ACO)#1 ;if ACO15-0#1 ;if Hi(ACO)#1 ;if ACO15-0#1 ;if Hi(ACO)#1 ;if ACO15-0ACl15-0 TRNl15=1.endm 程序中蝶形单元的前两条支路中，选择上支路过渡寄存器TRN0最高位赋值为0，选择下支路最高位赋值为1，蝶形单元的后两条支路中，选择上支路过渡寄存器TRN1的最高