下载文档原格式
(2,1,7)卷积码Viterbi译码器FPGA实现方案韩可;邓中亮;施乐宁【摘要】移动通信系统标准中普遍采用卷积码作为信道编码方案.本文阐述了目前最常用的卷积码译码算法——Viterbi译码算法,然后给出了(2,1,7)卷积码编码电路FPGA实现方法.该方法给出了新的Viterbi幸运路径算法和高效的状态度量存储技术,可以充分利用FPGA的优势获得较好的译码结果.利用幸存路径交换寄存器模块,能有效减少存储量并降低功耗.【期刊名称】《现代电子技术》【年(卷),期】2007(030)015【总页数】4页(P90-92,96)【关键词】Viterbi译码;FPGA;卷积码;寄存器交换;回溯【作者】韩可;邓中亮;施乐宁【作者单位】北京邮电大学,电子工程学院,北京,100876;北京邮电大学,电子工程学院,北京,100876;北京航空航天大学,电子信息工程学院,北京,100083【正文语种】中文【中图分类】TN74在无线通信过程中，信道中的噪声干扰会造成接收端的一定的误码率,这必定会影响无线数据传输的精确性。
为了解决这一问题经常采用信道编码技术。
卷积编码和Viterbi译码是广泛使用的信道编码技术，具有一定的克服突发错误的能力，可以降低信道的误码率，带来很高的编码增益。
因而卷积编码和Viterbi译码也是目前移动通信中的重要组成部分。
1 (2，1，7)卷积码Viterbi译码原理卷积码的译码方式有3种[1]：Viterbi译码、序列译码、门限译码。
Viterbi译码具有最佳性能。
Viterbi译码的主要思想就是根据产生卷积码的网格图[2](或称为状态图)，图1以(2，1，3)码为例，确定最可能的发送序列，这个最可能的发送序列对应网格图上的某一特殊路径。
译码时，将接收序列与网格图上所有可能的传输路径相比较，求其汉明距离，从中选择具有最小距离的发送序列，距离最小表示接收码取此序列的可能性最大。
假设为(n，k，N)码，下面详细叙述Viterbi译码算法。
No.15 (2,1,3)卷积码的编码及译码摘要：本报告对于（2,1,3）卷积码原理部分的论述主要参照啜刚教材和课件，编程仿真部分绝对原创，所有的程序都是在Codeblocks 8.02环境下用C语言编写的，编译运行都正常。
完成了卷积码的编码程序，译码程序，因为对于短于3组的卷积码，即2 bit或4 bit纠错是没有意义的，所以对正确的短序列直接译码，对长序列纠错后译码，都能得到正确的译码结果。
含仿真结果和程序源代码。
如果您不使用Codeblocks运行程序，则可能不支持中文输出显示，但是所有的数码输出都是正确的。
一、 卷积码编码原理卷积码编码器对输入的数据流每次1bit 或k bit 进行编码，输出n bit 编码符号。
但是输出的分支码字的每个码元不仅于此时可输入的k 个嘻嘻有关，业余前m 个连续式可输入的信息有关，因此编码器应包含m 级寄存器以记录这些信息。
通常卷积码表示为 (n,k,m). 编码率 k r n=当k=1时，卷积码编码器的结构包括一个由m 个串接的寄存器构成的移位寄存器（成为m 级移位寄存器、n 个连接到指定寄存器的模二加法器以及把模二加法器的输出转化为穿行的转换开关。
本报告所讲的（2,1,3）卷积码是最简单的卷积码。
就是2n =，1k =，3m =的卷积码。
每次输入1 bit 输入信息，经过3级移位寄存器，2个连接到指定寄存器的模二加法器，并把加法器输出转化为串行输出。
编码器如题所示。
二、卷积码编码器程序仿真 C 语言编写的仿真程序。
为了简单起见，这里仅仅提供数组长度30 bit 的仿真程序，当然如果需要可以修改数组大小。
为了更精练的实现算法，程序输入模块没有提供非法字符处理过程，如果需要也可以增加相应的功能。
进入程序后，先提示输入数据的长度，请用户输入int （整型数）程序默认用户输入的数据小于30，然后提示输入01数码，读入数码存储与input 数组中，然后运算输出卷积码。
实验九 (2,1,5）卷积码编码译码技术一、实验目的1、掌握(2,1,5）卷积码编码译码技术2、了解纠错编码原理。
二、实验内容1、(2,1,5）卷积码编码。
2、(2,1,5）卷积码译码。
三、预备知识1、纠错编码原理。
2、(2,1,5）卷积码的工作原理。
四、实验原理/卷积码是将发送的信息序列通过一个线性的，有限状态的移位寄存器而产生的编码。
通常卷积码的编码器由K级（每级K比特）的移位寄存器和n个线性代数函数发生器（这里是模2加法器）组成。
若以（n,k,m）来描述卷积码，其中k为每次输入到卷积编码器的bit数，n 为每个k元组码字对应的卷积码输出n元组码字，m为编码存储度，也就是卷积编码器的k元组的级数，称m+1= K为编码约束度m称为约束长度。
卷积码将k 元组输入码元编成n元组输出码元，但k和n通常很小，特别适合以串行形式进行传输，时延小。
与分组码不同，卷积码编码生成的n元组元不仅与当前输入的k元组有关，还与前面m-1个输入的k元组有关，编码过程中互相关联的码元个数为n*m。
卷积码的纠错性能随m的增加而增大，而差错率随N的增加而指数下降。
在编码器复杂性相同的情况下，卷积码的性能优于分组码。
编码器随着信息序列不断输入，编码器就不断从一个状态转移到另一个状态并同时输出相应的码序列，所以图3所示状态图可以简单直观的描述编码器的编码过程。
因此通过状态图很容易给出输入信息序列的编码结果，假定输入序列为110100，首先从零状态开始即图示a状态，由于输入信息为“1”，所以下一状态为b并输出“11”，继续输入信息“1”，由图知下一状态为d、输出“01”……其它输入信息依次类推，按照状态转移路径a->b->d->c->b->c->a输出其对应的编码结果“”。
译码方法⒈代数代数译码是将卷积码的一个编码约束长度的码段看作是[n0(m+1），k0(m+1)]线性分组码，每次根据（m+1）分支长接收数字，对相应的最早的那个分支上的信息数字进行估计，然后向前推进一个分支。
卷积码编码和维特比译码的原理、性能与仿真分析1.引言卷积码的编码器是由一个有k位输入、n位输出，且具有m位移位寄存器构成的有限状态的有记忆系统，通常称它为时序网络。
编码器的整体约束长度为v,是所有k个移位寄存器的长度之和。
具有这样的编码器的卷积码称作[n,k,v]卷积码。
对于一个（n,1,v）编码器，约束长度v等于存储级数m.卷积码是由k个信息比特编码成n（n>k）比特的码组，编码出的n比特码组值不仅与当前码字中的k个信息比特值有关，而且与其前面v个码组中的v*k个信息比特值有关。
卷积码有三种译码方式：序列译码、门限译码和概率译码。
其中，概率译码根据最大似然译码原理在所有可能路径中求取与接收路径最相似的一条路径，具有最佳的纠错性能，维特比译码是概率译码中极重要的一种方式。
序列译码和门限译码则不一定能找出与接收路径最相似的一条路径。
不同于维特比译码，门限译码与序列译码所需的计算量是可变的且对于给定信息分组的最终判决仅仅基于（m+1）个接收分组，而不是基于整个接收序列。
与维特比译码所使用的对数似然量度不同，序列译码所使用的量度为Fano量度。
在接收序列受扰严重的情况下，序列译码的计算量大于维特比译码所需的固定计算量，虽然序列译码要求的平均计算次数通常小于维特比译码。
在采用并行处理的情况下，维特比译码的速度会优于序列译码。
在同样码率和存储级数的条件下，门限译码的性能比维特比译码低大约3dB.维特比译码的数据输出方式有硬判决及软判决两种方式，本文选取生成多项式为561,753的（2,1,8）卷积码对硬判决的性能进行分析，并依据维特比译码的原理以及卷积码的特性，对卷积码编码和维特比译码过程在加性高斯白噪声（AWGN）信道下进行仿真，并且根据仿真结果对维特比译码（硬判决）的结果进行分析。
由于卷积码的生成可以看做一个马尔科夫过程，因此，不同状态间的转移概率对描述这个过程有极关键的作用。
本文则基于MATLAB对不同状态间的转移概率进行求解，从而更准确地分析维特比译码的性能。
卷积码编码及译码实验浅谈卷积编码下的FPGA实现
卷积编码是现代数字通信系统中常见的一种前向纠错码，区别于常规的线性分组码，卷积编码的码字输出不仅与当前时刻的信息符号输入有关，还与之前输入的信息符号有关。
本文主要是关于卷积码编码及译码实验的相关介绍，并着重分析阐述了基于卷积编码下的FPGA实现。
卷积编码卷积码的编码分为两类：前馈和反馈，在每类中又可分为系统和非系统形式。
我们这里只考虑非系统形式的前馈编码器。
‘
上图是WLAN 802.11a协议中采用的卷积编码器结构，输入比特k=1，输出n=2，存储器长度m=6，编码输出不仅与当前输入有关，还与存储器存储的之前的输入数据有关，具体由之前的哪些数据得到编码输出呢，由生成多项式确定其连接关系。
这里，生成多项式为g0=133（八进制）和g1=171（八进制）（右边是最高位），输出数据A的生成多项式为：
输出数据B的生成多项式为：
生成多项式确定了卷积编码器输出的连接关系。
根据多项式的系数，在相应项进行连接。
生成多项式写成二进制序列的形式分别为：g0 = ［1 0 1 1 0 1 1］和g1 = ［1 1 1 1 0 0 1］（右边是最高位）。
我们假设信息序列u，两个编码器输出序列分别为v（0）和v（1），编码器可以看成一个线性系统，系统的信道响应脉冲最多持续m+1个时间单元，编码输出可以写成编码输入与信道脉冲响应的卷积（即生成多项式），即
其中需要注意的是，所有的加法都是模2加运算。
卷积码编码及译码实验基本原理
1、卷积码编码
卷积码是一种纠错编码，它将输入的k个信息比特编成n个比特输出，特别适合以串行形。
实验九 (2,1,5）卷积码编码译码技术一、实验目的1、掌握(2,1,5）卷积码编码译码技术2、了解纠错编码原理。
二、实验内容1、(2,1,5）卷积码编码。
2、(2,1,5）卷积码译码。
三、预备知识1、纠错编码原理。
2、(2,1,5）卷积码的工作原理。
四、实验原理卷积码是将发送的信息序列通过一个线性的，有限状态的移位寄存器而产生的编码。
通常卷积码的编码器由K级（每级K比特）的移位寄存器和n个线性代数函数发生器（这里是模2加法器）组成。
若以（n,k,m）来描述卷积码，其中k为每次输入到卷积编码器的bit数，n 为每个k元组码字对应的卷积码输出n元组码字，m为编码存储度，也就是卷积编码器的k元组的级数，称m+1= K为编码约束度m称为约束长度。
卷积码将k 元组输入码元编成n元组输出码元，但k和n通常很小，特别适合以串行形式进行传输，时延小。
与分组码不同，卷积码编码生成的n元组元不仅与当前输入的k元组有关，还与前面m-1个输入的k元组有关，编码过程中互相关联的码元个数为n*m。
卷积码的纠错性能随m的增加而增大，而差错率随N的增加而指数下降。
在编码器复杂性相同的情况下，卷积码的性能优于分组码。
编码器随着信息序列不断输入，编码器就不断从一个状态转移到另一个状态并同时输出相应的码序列，所以图3所示状态图可以简单直观的描述编码器的编码过程。
因此通过状态图很容易给出输入信息序列的编码结果，假定输入序列为110100，首先从零状态开始即图示a状态，由于输入信息为“1”，所以下一状态为b并输出“11”，继续输入信息“1”，由图知下一状态为d、输出“01”……其它输入信息依次类推，按照状态转移路径a->b->d->c->b->c->a输出其对应的编码结果“110101001011”。
译码方法⒈代数代数译码是将卷积码的一个编码约束长度的码段看作是[n0(m+1），k0(m+1)]线性分组码，每次根据（m+1）分支长接收数字，对相应的最早的那个分支上的信息数字进行估计，然后向前推进一个分支。
实验二--卷积码编码及译码实验实验二卷积码编码及译码实验一、实验目的通过本实验掌握卷积编码的特性、产生原理及方法，卷积码的译码方法，尤其是维特比译码的原理、过程、特性及其实现方法。
二、实验内容1、观察NRZ基带信号及其卷积编码信号。
2、观察帧同步信号的生成及巴克码的特性。
3、观察卷积编码信号打孔及码速率匹配方法。
4、观察接收端帧同步过程及帧同步信号。
5、观察译码结果并深入理解维特比译码的过程。
6、观察随机差错及突发差错对卷积译码的影响。
三、基本原理1、卷积码编码卷积码是一种纠错编码，它将输入的k个信息比特编成n个比特输出，特别适合以串行形式进行传输，时延小。
卷积码编码器的形式如图17-1所示，它包括：一个由N段组成的输入移位寄存器，每段有k 段，共Nk 个寄存器；一组n 个模2和相加器；一个由n 级组成的输出移位寄存器,对应于每段k 个比特的输入序列,输出n 个比特。
12…k 12…k …12…k12…n 卷积码输出序列信息比特一次移入k 个Nk 级移位寄存器…图17-1 卷积编码器的一般形式由图17-1可以看到，n 个输出比特不仅与当前的k 个输入信息有关,还与前（N -1）k 个信息有关。
通常将N 称为约束长度（有的书中也把约束长度定为nN 或N -1）。
常把卷积码记为：（n 、k 、N ），当k =1时，N -1就是寄存器的个数。
编码效率定义为：/c R k n (17-1)卷积码的表示方法有图解表示法和解析表示法两种：解析法，它可以用数学公式直接表达，包括离散卷积法、生成矩阵法、码生成多项式法；图解表示法，包括树状图、网络图和状态图（最的图形表达形式）三种。
一般情况下，解析表示法比较适合于描述编码过程，而图形法比较适合于描述译码。
（1）图解表示法（2）解析法下面以（2，1，3）卷积编码器为例详细讲述卷积码的产生原理和表示方法。
（2，1，3）卷积码的约束长度为3，编码速率为1/2，编码器的结构如图17-2所示。
(2,1,3)卷积码的编码及译码摘要：￥本报告对于（2,1,3）卷积码原理部分的论述主要参照啜刚教材和课件，编程仿真部分绝对原创，所有的程序都是在Codeblocks 环境下用C语言编写的，编译运行都正常。
完成了卷积码的编码程序，译码程序，因为对于短于3组的卷积码，即2 bit或4 bit纠错是没有意义的，所以对正确的短序列直接译码，对长序列纠错后译码，都能得到正确的译码结果。
含仿真结果和程序源代码。
如果您不使用Codeblocks运行程序，则可能不支持中文输出显示，但是所有的数码输出都是正确的。
一、 卷积码编码原理卷积码编码器对输入的数据流每次1bit 或k bit 进行编码，输出n bit 编码符号。
但是输出的分支码字的每个码元不仅于此时可输入的k 个嘻嘻有关，业余前m 个连续式可输入的信息有关，因此编码器应包含m 级寄存器以记录这些信息。
通常卷积码表示为 (n,k,m). 编码率 k r n=(当k=1时，卷积码编码器的结构包括一个由m 个串接的寄存器构成的移位寄存器（成为m 级移位寄存器、n 个连接到指定寄存器的模二加法器以及把模二加法器的输出转化为穿行的转换开关。
本报告所讲的（2,1,3）卷积码是最简单的卷积码。
就是2n =，1k =，3m =的卷积码。
每次输入1 bit 输入信息，经过3级移位寄存器，2个连接到指定寄存器的模二加法器，并把加法器输出转化为串行输出。
编码器如题所示。
二、卷积码编码器程序仿真 C 语言编写的仿真程序。
为了简单起见，这里仅仅提供数组长度30 bit 的仿真程序，当然如果需要可以修改数组大小。
为了更精练的实现算法，程序输入模块没有提供非法字符处理过程，如果需要也可以增加相应的功能。
进入程序后，先提示输入数据的长度，请用户输入int （整型数）程序默认用户输入的数据小于30，然后提示输入01数码，读入数码存储与input 数组中，然后运算输出卷积码。
经过实验仿真，编码完全正确。
}以下是举例：a.课件上的输入101 输出11 10 00 的实验b.更长的序列测试三、卷积码译码原理由有限状态移位寄存器产生的卷积码实质上是一个有限状态机。
(n, k)线性分组码的最大似然译码就是在所有合法码字中找出一个最接近接收码字的码字。
卷积码的最大似然译码法则是对于给定的接收符号序列R，找出最大可能的编码符号序列C。
维特比于1967年提出的维特比算法能够系统地去除那些不可能具有最大度量的路径排除，从而降低了最大似然译码的复杂度。
…（2,1,3）卷积码的状态图（2,1,3）卷积码的网格图卷积码一码通常按最大似然法则一码，对二进制对称信道（BSC），它就等小于最小汉明距离译码。
在这种译码器中，把接收序列和所有可能发送序列比较，选择一个汉明距离最小的序列盘坐发送序列。
由于信息序列编码序列有着一一对应关系，这种序列和网格图的一条路径唯一对应，因此译码就是根据接收序列R在网格图上全力搜索编码器在编码时经过的路径。
四、卷积码译码器程序仿真C语言编写的仿真程序。
为了简单起见，这里仅仅提供数组长度2×10 bit的仿真程序，当然如果需要可以修改数组大小。
为了更精练的实现算法，程序输入模块没有提供非法字符处理过程，如果需要也可以增加相应的功能。
进入程序后，先提示输入数据的长度，请用户输入int（整型数）程序默认用户输入的数据小于30，然后提示输入01数码，读入数码存储与input数组中，然后运算输出卷积码。
经过实验仿真，译码完全正确。
`以下是举例：a.课件上接收码字11 10 00 译码101的实验b.对应上文中的，长序列译码测试结果c.译码与编码的区别在于容错性，如果在传输过程中有出错的比特，也应该用Viterbi decoder在一定的范围内自动纠错，得到正确的发端的编码，并翻译出发端的原码。
本报告中对于比较长的序列（>2）进行纠错。
以课件中的例子进行仿真R是收到的码字，C是发送方发出的正确的码字，R有2 bit信息出现错误。
运行程序的到结果。
、当用译码器接收正确的序列C时显示以下结果：当接收到的序列错误时译码结果如下：如此时把译码结果输入上文中的编码器程序，即可得到发送方发出的正确的码字：综上，译码程序能对于正确的较短（<3组）的卷积码序列进行译码，得到正确的译码结果。
对于较长的序列（>2）可以纠错，纠正后，得到正确的卷积码，然后译码得到原码。
程序仿真完全正确。
|d.模拟一个完整的传输过程：发送方输入序列输入到编码器程序中：得到卷积码输出：11 01 01 11 11 10 00 10若传送到接收端，由于信道的各种干扰，接收码字发生了变化，得到的接收码字：11 11 01 11 01 10 11 10共有2 bit出现错误，输入到解码器中，纠错解码后得到：[有效地纠错，解码，还原了发送方的信息。
e.进一步大量仿真得到结果：当错误量比较多，或者比较集中时，有些时候不能有效地纠错，得到的译码结果可能也有1bit是错误的。
具体截图略。
五、编码C源程序清单#include <>#include <>short add3(short a,short b, short c)/* 3位模二加法器*/{：short sum;sum = a+b+c;sum = sum%2;return sum;}short add2(short a,short b)/* 2位模二加法器*/{short sum;/sum = a+b;sum = sum%2;return sum;}int main(){short a=0, b=0, c=0;/*三个移位寄存器初始状态为0*/int length=0;?/*输入长度*/short x,y;/*两个输出寄存器*/short input[30];/*存储输入数据的数组*/int i;printf("需要输入几位数据");scanf("%d",&length);printf("请输入%d位数字：\n",length);for (i=0;i<length;i++)…{scanf("%1hd",&input[i]);}printf("卷积码输出：\n");for (i=0;i<length;i++){c=b;b=a;a=input[i];/*移位运算*/(x=add3(a,b,c);y=add2(a,c);printf("%d%d\n",x,y);}return 0;}六、译码程序清单#include <>#include <>%int de(codenow){/*短序列不纠错解码器*/int decode,now,code;now=codenow%100;code =(codenow-now)/100;/*分离状态和接收到的码字*/switch (now){|case 10:if (code==10){now=01;decode=0;}else{now=11;decode=1;。
}break;case 11:if (code==01){now = 01;decode=0;}else，{now=11;decode=1;}break;case 01:if (code==11){now = 00; -decode=0;}else{now=10;decode=1;}break;case 00:【if (code==00){now = 00;decode=0;}else{now=10;decode=1;}。
break;default:printf("error!");}codenow=decode*100+now;return codenow;}】int hanming(int x, int y){/*计算xy两个2bit数的汉明距离*/int x1,x2,y1,y2,sum=0;/*分解数位*/x2=x%2;x1=(x-x2)/10;y2=y%2;y1=(y-y2)/10;if (x1 != y1)·sum++;if (x2 != y2)sum++;return sum;}void correct(int code[],int length)/*长序列纠错解码器*/{int i,j,m,error=0;—int *p;int d00=0, d10=0, d01=0, d11=0;int dz00=0, dz10=0, dz01=0, dz11=0;/*时刻1结束时*/int lu00[10]={0,0};int lu10[10]={0,1};int lu01[10]={1,0};int lu11[10]={1,1};int lz00[10]={0},lz10[10]={0};int lz01[10]={0},lz11[10]={0};￥d00=hanming(code[0],0)+hanming(code[1],0);d10=hanming(code[0],0)+hanming(code[1],11);d01=hanming(code[0],11)+hanming(code[1],10);d11=hanming(code[0],11)+hanming(code[1],01);for (i=2;i<length;i++){/*00状态路径*/if ((d00+hanming(0,code[i]))<(d01+hanming(11,code[i]))) !{for (j=0;j<i;j++){lz00[j]=lu00[j];}lz00[i]=0;dz00=d00+hanming(0,code[i]);}else{#for (j=0;j<i;j++){lz00[j]=lu01[j];}lz00[i]=0;dz00=d01+hanming(11,code[i]);}/*10状态路径*/if ((d00+hanming(11,code[i]))<(d01+hanming(00,code[i]))) ~{for (j=0;j<i;j++){lz10[j]=lu00[j];}lz10[i]=1;dz10=(d00+hanming(11,code[i]));}else{[for (j=0;j<i;j++){lz10[j]=lu01[j];lz10[i]=1;dz10=d01+hanming(00,code[i]);}/*01状态路径*/if ((d10+hanming(10,code[i]))<(d11+hanming(01,code[i]))) …{for (j=0;j<i;j++){lz01[j]=lu10[j];}lz01[i]=0;dz01=d10+hanming(10,code[i]);}else{%for (j=0;j<i;j++){lz01[j]=lu11[j];}lz01[i]=0;dz01=d11+hanming(01,code[i]);}/*11状态路径*/if ((d10+hanming(01,code[i]))<(d11+hanming(10,code[i]))) {{for (j=0;j<i;j++){lz11[j]=lu10[j];}lz11[i]=1;dz11=d10+hanming(01,code[i]);}else{}for (j=0;j<i;j++){lz11[j]=lu11[j];lz11[i]=1;dz11=d11+hanming(10,code[i]);}/*更新*/d00=dz00;|d10=dz10;d01=dz01;d11=dz11;for (m=0;m<length;m++){lu00[m]=lz00[m];}for (m=0;m<length;m++){lu10[m]=lz10[m];"}for (m=0;m<length;m++){lu01[m]=lz01[m];}for (m=0;m<length;m++){lu11[m]=lz11[m];}}@/*最后一步，在四条路径中选择汉明距离最小的一条*/ error=d00;p=lu00;if (d01<error){error=d01;p=lu01;}if (d10<error){：error=d10;p=lu10;}if (d11<error){error=d11;p=lu11;}printf("共有%d位错误，译码如下：\n",error);for (m=0;m<length;m++);{printf("%d",*p);p++;}}int main(){int codenow=0;,int now=0;/*当前状态*/int length=0;/*输入长度*/int decode;/*输出*/int code[20];/*存储输入数据的数组*/int i;printf("需要输入几组数据");scanf("%d",&length);printf("请输入%d组接收到的数字：\n",length);for (i=0;i<length;i++){scanf("%2d",&code[i]);}/*长度大于3的用Viterbi decoder纠错过程如下,*/if (length>2){correct(code,length);}/*长度小于3的直接译码*/else{printf("\n卷积码解码结果：\n");/*解码过程如下*/for (i=0;i<length;i++){codenow =code[i]*100+now;codenow=de(codenow);now=codenow%100;decode = (codenow-now)/100;printf("%d",decode);}}return 0;}。
