BUPT卷积码编码及Viterbi译码班级：07114学号：070422姓名：吴希龙指导老师：彭岳星邮箱：FusionBupt@1. 序言卷积码最早于1955年由Elias 提出，稍后，1957年Wozencraft 提出了一种有效地译码方法即序列译码。

1963年Massey 提出了一种性能稍差但是比较实用的门限译码方法，使得卷积码开始走向实用化。

而后1967年Viterbi 提出了最大似然译码算法，它对存储级数较小的卷积码很容易实现，被称作Viterbi 译码算法，广泛的应用于现代通信中。

2. 卷积码编码及译码原理2.1 卷积码编码原理卷积码是一种性能优越的信道编码，它的编码器和解码器都比较易于实现，同时还具有较强的纠错能力，这使得它的使用越来越广泛。

卷积码一般表示为(n,k,K)的形式，即将k 各信息比特编码为n 个比特的码组，K 为编码约束长度，说明编码过程中相互约束的码段个数。

卷积码编码后的n 各码元不经与当前组的k 个信息比特有关，还与前K-1个输入组的信息比特有关。

编码过程中相互关联的码元有K*n 个。

R=k/n 是编码效率。

编码效率和约束长度是衡量卷积码的两个重要参数。

典型的卷积码一般选n,k 较小，但K 值可取较大(>10)，以获得简单而高性能的卷积码。

卷积码的编码描述方式有很多种：冲激响应描述法、生成矩阵描述法、多项式乘积描述法、状态图描述，树图描述，网格图描述等。

2.1.1 卷积码解析表示法卷积码的解析表示发大致可以分为离散卷积法，生成矩阵法，码多项式法。

下面以离散卷积为例进行说明。

卷积码的编码器一般比较简单，为一个具有k 个输入端，n 个输出端，m 级移位寄存器的有限状态有记忆系统。

下图所示为(2,1,7)卷积码的编码器。

若输入序列为u =(u 0u 1u 2u 3……),则对应两个码字序列c ①=(c 0①c 1①c 2①c 3①……)和c ②=(c 0②c 1②c 2②c 3②……)相应的编码方程可写为c ①=u ∗g ①，c ②=u ∗g ②，c=(c ①,c ②)。

“∗” 符号表示卷积运算，g ①，g ②表示编码器的两个冲激响应，即编码器的输出可以由输入序列和编码器的两个冲击响应卷积而得到，故称为卷积码。

这里的冲激响应指：当输入为[1 0 0 0 0 … … ]序列时，所观察到的两个输出序列值。

由于上图K 值为7，故冲激响应至多可持续到第7位，可写为g ①=[1 1 1 1 0 0 1]，g ②=[1 0 1 1 0 1 1]然后将两个输出端的码字序列合并为一个码字序列为c =(c 0①c 0②c 1①c 1②c 2①c 2②……)若输入信息序列为[1 1 0 1]; 则c ①=[1 0 0 1 0 1 0 1 0 1]，c ②=[1 1 1 1 1 0 1 1 1 1]c =[1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 1 0 1 1 1]。

下图所示为(2,1,3)卷积码的编码器，也是本次课程设计所研究的卷积码编码器，由于其生成冲激响应分别为[1 1 1]和[1 0 1]，故被称为(7,5)码。

2.1.2 卷积码图形表示法除了用解析法描述卷积码的编码外，还可以使用比较形象的图形法来表示卷积码。

比较常用的有状态图法，网格图法和树图法。

下面简介状态图法和网格图法。

状态图法：由于卷积码编码器在下一时刻的输出取决于编码器的当前状态和下一时刻的输入，而编码器当前状态取决于编码器当前各移位寄存器的存储内容。

称编码器当前各移位寄存器存储内容(0或)为编码器在该时刻的状态(此状态代表记忆以前的输入信息)。

随着信息序列的不断输入，编码器不断从一个状态转移到另外一个状态，并且输出相应的编码序列。

编码器的总可能状态数为2mk 个。

对(7,5)码的编码器来说，n=2，k=1，K=3，m=2。

共有四个可能状态，其状态图如下：图中四个方块表示状态，状态间的连线与箭头表示转移方向，连线上的数字表示是状态发生转移的到来比特，斜杠后的数字由一个状态到另一个状态转移时的输出码字。

如当前状态为11，输入信息为0，则转移到01状态并输出01码字，若输入信息为1，则依然为11状态并输出10码字。

网格图法：网格图可以描述卷积码的状态随时间推移而转移的情况。

该图纵坐标表示所有状态，横坐标表示时间。

网格图在卷积码的概率译码，特别是Viterbi译码中非常重要，它综合了状态图法直观简单和树图法时序关系清晰的特点。

如下图图中实线表示输入0时所走分支，虚线表示输入1时所走分支，编码时只需从起始状态开始依次选择路线并读出输出即可。

假设从a状态开始，输入为[1 0 1 1]，则可由图中读出输出为[11 10 10 01]。

2.2 卷积码译码原理卷积码的译码方式主要有三种:1).1963年Massey提出的门限译码，这是一种基于码代数结构的代数译码，类似于分组码中的大数逻辑译码。

2).1963年有Fano改进的序列译码，这是基于码的树状图结构的一种准最佳概率译码。

3).1967年Viterbi提出的Viterbi算法，基于码的网格图基础上的最大似然译码算法，是一种最佳概率译码。

其中，代数译码，利用编码本身的代数结构进行译码，不考虑信道本身的统计特性。

该方法的硬件实现简单，但性能较差，其中具有典型意义的是门限译码。

另一类是概率译码，这种译码通常建立在最大似然准则的基础上。

由于计算是用到了信道的统计特性.因而提高了译码性能，但这种性能的提高是以增加硬件的复杂度为代价的。

常用的概率译码方法有维特比译码和序列译码。

维特比译码具有最佳性能，但硬件实现复杂；门限译码性能最差，但硬件简单；序列译码在性能和硬件方面介于维特比译码和门限译码之间。

2.2.1 Viterbi译码卷积码概率译码的基本思路是:以接收码流为基础，逐个计算它与其他所有可能出现的、连续的网格图路径的距离，选出其中可能性最大的一条作为译码估值输出。

概率最大在大多数场合可解释为距离最小，这种最小距离译码体现的正是最大似然的准则。

卷积码的最大似然译码与分组码的最大似然译码在原理上是一样的，但实现方法上略有不同。

主要区别在于:分组码是孤立地求解单个码组的相似度，而卷积码是求码字序列之间的相似度。

基于网格图搜索的译码是实现最大似然判决的重要方法和途径。

用格图描述时，由于路径的汇聚消除了树状图中的多余度，译码过程中只需考虑整个路径集合中那些使似然函数最大的路径。

如果在某一点上发现某条路径已不可能获得最大对数似然函数，就放弃这条路径，然后在剩下的“幸存”路径中重新选择路径。

这样一直进行到最后第L级(L为发送序列的长度)。

由于这种方法较早地丢弃了那些不可能的路径，从而减轻了译码的工作量，Viterbi译码正是基于这种想法。

对于(n, k, K )卷积码，其网格图中共2kL种状态。

由网格图的前K-1条连续支路构成的路径互不相交，即最初2k_1条路径各不相同，当接收到第K条支路时，每条路径都有2条支路延伸到第K级上，而第K级上的每两条支路又都汇聚在一个节点上。

在Viterbi 译码算法中，把汇聚在每个节点上的两条路径的对数似然函数累加值进行比较，然后把具有较大对数似然函数累加值的路径保存下来，而丢弃另一条路径，经挑选后第K级只留下2K 条幸存路径。

选出的路径同它们的对数似然函数的累加值将一起被存储起来。

由于每个节点引出两条支路，因此以后各级中路径的延伸都增大一倍，但比较它们的似然函数累加值后，丢弃一半，结果留存下来的路径总数保持常数。

由此可见，上述译码过程中的基本操作是，“加-比-选”，即每级求出对数似然函数的累加值，然后两两比较后作出选择。

有时会出现两条路径的对数似然函数累加值相等的情形，在这种情况下可以任意选择其中一条作为“幸存”路径。

卷积码的编码器从全零状态出发，最后又回到全零状态时所输出的码序列，称为结尾卷积码。

因此，当序列发送完毕后，要在网格图的终结处加上（K-1）个己知的信息作为结束信息。

在结束信息到来时，由于每一状态中只有与已知发送信息相符的那条支路被延伸，因而在每级比较后，幸存路径减少一半。

因此，在接收到（K-1）个己知信息后，在整个网格图中就只有唯一的一条幸存路径保留下来，这就是译码所得的路径。

也就是说，在己知接收到的序列的情况下，这条译码路径和发送序列是最相似的。

3.MATLAB仿真在本次课程设计中，我们对整个通信过程进行了仿真，其过程如下：下面将分别对每一部分进行仿真3.1卷积码编码仿真在程序设计中，我们没有采用MATLAB自带的编码函数而是采用了自己的编码函数codec，其参数m为输入信息序列，g1，g2为两个输出端口的冲激响应序列。

function cod=codec(m,g1,g2)%g1,g2为两输出端口的冲激响应序列。

m1=conv(m,g1);m2=conv(m,g2);l=length(m1);for i=1:l;cod([2*i-1])=rem(m1([i]),2);cod([2*i])=rem(m2([i]),2);end下为试运行编码结果，g1=[1 1 1],g2=[1 0 1]。

clear allg1=[1 1 1];g2=[1 0 1];msg=[1 1 0 1];cod=codec(msg,g1,g2)输出为：cod =110101001011符合预期结果。

3.2信道传输过程仿真为了方便起见，我们采用了BPSK调制，为了了解整个通信系统，我们对BPSK的调制过程作了研究，用一个简短的程序对BPSK的全过程进行了观察。

function [bpsk_output]=bpsk_1(bpsk_input);%g=[1 0 1 1 1 0 0 1];基带信号g=bpsk_input;f=100; %载波频率t=0:2*pi/99:2*pi;cp=[];sp=[];mod=[];mod1=[];bit=[];for n=1:length(g);if g(n)==0;die=-ones(1,100); %Modulantese=ones(1,100); %endc=sin(f*t);cp=[cp die];mod=[mod c];bit=[bit se];endbpsk=cp.*mod;subplot(2,1,1);plot(bit,'LineWidth',1.5);grid on ;title('Binary Signal');axis([0 100*length(g) -2.5 2.5]);bpsk_output=bpsk;subplot(2,1,2);plot(bpsk,'LineWidth',1.5);grid on ;title('BPSK modulation');axis([0 100*length(g) -2.5 2.5]);观察到如下波形上图很好的符合了BPSK 的调制特性。