卷积码编译码算法研究与实现

河北联合大学轻工学院QINGGONGCOLLEGE,HEBEI移动通信题目：卷及编码及其仿真班级：2011级通信3班姓名学号侯宇明201124440303李乔松201124440306欧和鑫201124440307王明201124440308张蕴201124440313卷积码编译码算法研究与实现PAGE10摘要在数字通信系统中，通常采用差错控制编码来提高系统的可靠性。自P．Elias首次提出卷积码编码以来，这一编码技术至今仍显示出强大的生命力。目前，卷积码已广泛应用在无线通信标准中，如GSM，CDMA2000和IS-95等无线通信标准中。本文简单介绍了纠错码的基本原理，论述了卷积码编译码原理和算法，并通过matlab仿真对卷积码性能进行研究。卷积码是一种性能优越的信道编码。它的编码器和译码器都比较容易实现，同时它具有较强的纠错能力。随着纠错编码理论研究的不断深入，卷积码的实际应用越来越广泛。本文简明地介绍了卷积码的编码原理和译码原理。并在SIMULINK模块设计中，完成了对卷积码的编码和译码以及误比特统计整个过程的模块仿真。最后，通过在仿真过程中分别改变卷积码的重要参数来加深理解卷积码的这些参数对卷积码的误码性能的影响。经过仿真和实测，并对测试结果作了分析。得出了以下三个结论：（1）当改变卷积码的码率时，系统的误码性能也将随之发生变化。（2）对于码率一定的卷积码，当约束长度N发生变化时，系统的误码性能也会随之发生变化。（3）回溯长度也会不同程度上地影响误码性能。目录1绪论 21.1选题背景和研究意义 31.2信道编码的发展 32卷积码的基本理论 52.2卷积码编码原理 52.3

卷积码译码原理 63卷积码编译码及MATLAB仿真 73.1卷积码编码及仿真 73.2维特比译码程序及仿真 81绪论1.1选题背景和研究意义信道编码是数字通信系统的重要组成部分，随着通信技术的不断发展，信道编码技术也在不断地发展。在通信系统中，信道传输特性不理想以及噪声的存在，会导致接收端出现接收信号的错误，因此用于信道纠错的信道编码是数字通信系统中极为重要的一个环节。二十世纪40年代香农定理的出现为人们指出了纠错码的研究方向。根据香农的有噪信道编码定理[1]，可以推导出一个码率为R的编码通信系统达到无误码传输状态所必须的最小信噪比的理论极限。这个理论极限通常称为香农限，它说明对一个码率为R的编码通信系统，只有当SNR超过这个极限值时才能获得无误码传输。只要SNR高于这个极限值，香农的编码定理保证了能够获得无误码传输的（可能相当复杂）编码通信系统的存在性。另外，香农证明了在采用无限长的随机编码时，数据可以以接近信道容量的速率几乎无误码的传输，从而为信道编码的研究奠定了基础。1.2信道编码的发展1948年,信息论的奠基人Shannon在他的开创性论文“通信的数学理论”中，首次阐明了在有扰信道中实现可靠通信的方法，提出了著名的有扰信道编码定理[2]，指出了实现最佳编码的三个基本条件：(1)采用随机编码方式；(2)编码长度L→∞，即码元序列长度无限；(3)译码采用最大似然译码算法。在满足这三个条件的前提下，香农认为在有噪信道中可以实现无差错传输。自20世纪50年代以来，编码理论研究与技术应用是长期围绕数字通信业务的特点和需要而发展的，即以伽罗华域上的代数编码方法为主体，研究适合串行信道中使用的码率尽可能高、检错纠错能力尽可能强的码型及其译码算法。从结构上看，码型可划分为分组码和卷积码两大类；译码算法主要分为基于代数的译码算法和基于概率的译码算法两大类。在分组码研究中，各种好的循环码、能纠正多重差错的BCH码、RS码[3]等码型都从理论推导到计算机模拟、搜索中找到。分组码的译码方法可分为代数和非代数两类。代数方法是以求解一组用以确定差错位置与数值的联立方程为基础的，而非代数方法以更为直接的方式确定差错模式。非代数方法主要有梅吉特（Meggitt）于1961年首先提出的纠突发差错的梅吉特译码器、1963年梅茜（Massey）所给出的门限译码器和1962年由布拉格（Prange）首先介绍的信息组译码法。此外，为了充分利用解调器所能提供的软信息，后来又陆续推出了一系列分组码软判决译码算法，如梅茜的后验概率（APP）译码算法、哈特曼（Hartmann）-鲁道夫（Rudolph）最优逐符号译码算法和威尔顿算法等。在卷积码研究方面，随着Viterbi算法的提出及序列译码算法Fano算法的提出，也出现了以译码算法优化、减少译码复杂度为突破口的一批好的研究成果。为了在译码复杂性不高的同时获得更好的纠错性能，范尼（Forney）于1966年首先提出级联码的概念。20世纪70~80年代，以Goppa为首的学者从理论上构造了一类Goppa码[4]，其中的一个子类的性能达到了香农信道编码定理中提出的“好码”的标准，具有理论上的重大意义。这个时期由于大规模集成电路的迅速发展，为信道编码的大规模使用打下了坚实的基础，如美国在20世纪70年代发射的“旅行者”号宇宙飞船中就成功地运用了信道编码技术，使宇宙飞船能从遥远的太空传回清晰的照片。同时，由于数字信号处理技术的发展，信道编码在通信系统中的应用也得到关注，并广泛用于实际的通信系统中。另外，近几十年来，许多研究学者致力于寻找低编译码复杂度的实用化编码，先后提出了非规则重复累加码（IRA），以及多维并行级联单奇偶校验码（M-PC-SPC）等结构。在1993年IC国际会议上，法国不列颠通信大学的C．Berrou、A．Glavieux[5]等人，首先提出了一种称之为Turbo码的编译码方案。Turbo码的出现，是首次对第一章绪论3香农提出的非构造性问题的构造性回答，引起了研究人员对随机编码方法迭代译码[6]的热情关注，完善了香农信道编码理论。LDPC码由Gallager[7]于19世纪60年代初期首次提出，然而不幸的是，他的重大发现被编码研究人员忽视了大约20年；1996年，两位LDPC码的追踪研究者MacKay和Neal[8]重新发现了LDPC码的优越性能。总之，Turbo码和LDPC码[9]的出现，加深了人们对随机编码方式和迭代译码的全面理解，掀开了信道编码理论的新篇章，开创了数字通信领域的新纪元。2卷积码的基本理论2.1卷积码编码原理卷积码一般表示为(n,k,N)的形式，即将k个信息比特编码为n个比特的码组，N为编码约束长度，说明编码过程中相互约束的码段个数。卷积码编码后的n个码元不仅与当前组的k个信息比特有关，还与前N-1个输入组的信息比特有关。编码过程中相互关联的码元有N*n个。R=k/n是编码效率。编码效率和约束长度是衡量卷积码的两个重要参数。典型的卷积码一般选n,k较小，但N值可取较大(>10)，以获得简单而高性能的卷积码。卷积码的编码描述方式有很多种：冲激响应描述法、生成矩阵描述法、多项式乘积描述法、状态图描述，树图描述，网格图描述等。2.1.1卷积码图形表示法除了用解析法描述卷积码的编码外，还可以使用比较形象的图形法来表示卷积码。比较常用的有状态图法，树图法和网格图法。网格图可以描述卷积码的状态随时间推移而转移的情况。该图纵坐标表示所有状态，横坐标表示时间。网格图在卷积码的概率译码，特别是Viterbi译码中非常重要，它综合了状态图法直观简单和树图法时序关系清晰的特点[18]。如图2-1所示状态状态t1t2t3t4t5t621111111111102202002020211102010000111图2-1译码器网格图图中实线表示输入0时所走分支，虚线表示输入1时所走分支，编码时只需从起始状态开始依次选择路线并读出输出即可。假设从a状态开始，输入为[1011]，则可由图中读出输出为[11101001]。2.2卷积码译码原理维特比译码维特比译码是根据接收序列在码的格图上找出一条与接收序列距离（或其他量度）为最小的一种算法。它和运筹学中求最短路径的算法相类似。若接收序列为R=(10100101100111)，译码器从某个状态,例如从状态ɑ出发,每次向右延伸一个分支（对于l＜L,从每个节点出发都有2种可能的延伸,其中L是信息序列段数,对l≥L，只有一种可能）,并与接收数字相应分支进行比较,计算它们之间的距离，然后将计算所得距离加到被延伸路径的累积距离值中。对到达每个状态的各条路径（有2条）的距离累积值进行比较，保留距离值最小的一条路径，称为幸存路径（当有两条以上取最小值时，可任取其中之一）,译码过程如图。图中标出到达各级节点的幸存路径的距离累积值。对给定R的估值序列为=(10111)。这种算法所保留的路径与接收序列之间的似然概率为最大，所以又称为最大似然译码。这种译码的译码约束长度常为编码约束长度的数倍，因而可以纠正不多于(df/2)个错误[19]。维特比译码器的复杂性随m呈指数增大。实用中m不大于10。它在卫星和深空通信中有广泛的应用。在解决码间串扰和数据压缩中也可应用。3卷积码编译码及MATLAB仿真在本次课题研究中，我们对整个通信过程进行了仿真，其过程如下图：序列序列产生信道编码BPSK

调制AWGN信道传输BPSK

解调Viterbi译码信息输出图3-1卷积码编译码流程图3.1卷积码编码及仿真3.1.1编码程序functioncod=codec(m,g1,g2)%g1,g2为两输出端口的冲激响应序列。m1=conv(m,g1);%端口一输出 m2=conv(m,g2);%端口二输出l=length(m1);fori=1:l;cod([2*i-1])=rem(m1([i]),2);%将端口一编码输出赋给cod奇数位置cod([2*i])=rem(m2([i]),2);%将端口二编码输出赋给cod偶数位置end试运行编码：clearallg1=[111];g2=[101];msg=[1101];cod=codec(msg,g1,g2)输出为：cod=[110101001011]3.1.2仿真结果如下图3-1。图3-2（2,1,3）卷积码编码3.2Viterbi译码程序3.2.1Viterbi译码主要程序如下：forj=0:number_of_states-1form=0:M-1[next_state,memory_contents]=nxt_stat(j,m,N,k);%调用nxt_stat函数input(j+1,next_state+1)=m;branch_output=rem(memory_contents*G',2);% nextstate数组记录了当前状态j下输入l时的下一个状态nextstate(j+1,m+1)=next_state;% output数组记录了当前状态j下输入l时的输出（十进制）output(j+1,m+1)=bin2deci(branch_output);endendstate_metric=zeros(number_of_states,2);depth_of_trellis=length(channel_output)/n;channel_output_matrix=reshape(channel_output,n,depth_of_trellis);survivor_state=zeros(number_of_states,depth_of_trellis+1);fori=1:depth_of_trellis-N+1flag=zeros(1,number_of_states);if(i<=N)step=2^(k*(N-i));elsestep=1;endforj=0:step:number_of_states-1form=0:M-1branch_metric=0;binary_output=deci2bin(output(j+1,m+1),n);forll=1:nbranch_metric=branch_metric+metric(channel_output_matrix(ll,i),binary_output(ll));end%选择码间距较小的路径,即当下一个状态没有被访问时就直接赋值，否则，用比它小的将其覆盖if((state_metric(nextstate(j+1,m+1)+1,2)>state_metric(j+1,1)+branch_metric)|flag(nextstate(j+1,m+1)+1)==0)state_metric(nextstate(j+1,m+1)+1,2)=state_metric(j+1,1)+branch_metric;survivor_state(nextstate(j+1,m+1)+1,i+1)=j;flag(nextstate(j+1,m+1)+1)=1;endendendstate_metric=state_metric(:,2:-1:1);endfori=depth_of_trellis-N+2:depth_of_trellisflag=zeros(1,number_of_states);last_stop=number_of_states/(2^(k*(i-depth_of_trellis+N-2)));forj=0:last_stop-1branch_metric=0;binary_output=deci2bin(output(j+1,1),n);for

ll=1:nbranch_metric=branch_metric+metric(channel_output_matrix(ll,i),binary_output(ll));endif((state_metric(nextstate(j+1,1)+1,2)>state_metric(j+1,1)+branch_metric)|flag(nextstate(j+1,1)+1)==0)state_metric(nextstate(j+1,1)+1,2)=state_metric(j+1,1)+branch_metric;survivor_state(nextstate(j+1,1)+1,i+1)=j;flag(nextstate(j+1,1)+1)=1;endendstate_metric=state_metric(:,2:-1:1);end%从最佳路径中产生解码，译码过程可从数组survivor_state的最后一个位置向前逐级译码state_sequence=zeros(1,depth_of_trellis+1);state_sequence(1,depth_of_trellis)=survivor_state(1,depth_of_trellis+1);fori=1:depth_of_trellisstate_sequence(1,depth_of_trellis-i+1)=survivor_state((state_sequence(1,depth_of_tre