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). 编码率 r
k n
当k=1时，卷积码编码器的结构包括一个由m个串接的寄存器构成的移位寄存器（成为m级移位寄存器、n个连接到指定寄存器的模二加法器以及把模二加法器的输出转化为穿行的转换开关。
本报告所讲的（2,1,3）卷积码是最简单的卷积码。就是n2，k1，m3的卷积码。每次输入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时 显示以下结果：
当接收到的序列错误时
译码结果如下：
如此时把译码结果输入上文中的编码器程序，即可得到发送方发出的正确的码字：
综上，译码程序能对于正确的较短（2）可以纠错，纠正后，得到正确的卷积码，然后译码得到原码。程序仿真完全正确。
d.模拟一个完整的传输过程： 发送方输入序列11001010 输入到编码器程序中：
得到卷积码输出：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
scanf("%1hd",&input[i]); }
printf("卷积码输出：\n"); for (i=0;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
{
/*00状态路径*/
if ((d00+hanming(0,code[i]))
for (j=0;j
{
lz00[j]=lu00[j];
}
lz00[i]=0;
dz00=d00+hanming(0,code[i]);
}
else
{
for (j=0;j
{
lz00[j]=lu01[j];
}
lz00[i]=0;
dz00=d01+hanming(11,code[i]);
}
/*10状态路径*/
if ((d00+hanming(11,code[i]))
for (j=0;j
{
lz10[j]=lu00[j];
}
lz10[i]=1;
dz10=(d00+hanming(11,code[i]));
}
else
{
for (j=0;j
{
lz10[j]=lu01[j];
}
lz10[i]=1;
dz10=d01+hanming(00,code[i]);
}
/*01状态路径*/
if ((d10+hanming(10,code[i]))
for (j=0;j
{
lz01[j]=lu10[j];
}
lz01[i]=0;
dz01=d10+hanming(10,code[i]);
}
else
{
for (j=0;j
{
lz01[j]=lu11[j];
}
lz01[i]=0;
dz01=d11+hanming(01,code[i]);
}
/*11状态路径*/
if ((d10+hanming(01,code[i]))
for (j=0;j
{
lz11[j]=lu10[j];
}
lz11[i]=1;
dz11=d10+hanming(01,code[i]);
}
else
{
for (j=0;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
{
lu00[m]=lz00[m];
}
for (m=0;m
{
lu10[m]=lz10[m];
}
for (m=0;m
{
lu01[m]=lz01[m];
}
for (m=0;m
{
lu11[m]=lz11[m];
}
}
/*最后一步，在四条路径中选择汉明距离最小的一条*/ error=d00;
p=lu00;
if (d01
{
error=d01;
p=lu01;
}
if (d10
{
error=d10;
p=lu10;
}
if (d11
{
error=d11;
p=lu11;
}
printf("共有%d位错误，译码如下：\n",error); for (m=0;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
{
scanf("%2d",&code[i]);
}
/*长度大于3的 用Viterbi decoder纠错过程如下,*/ if (length>2)
{
correct(code,length);
}
/*长度小于3的直接译码*/
else
{
printf("\n卷积码解码结果：\n");
/*解码过程如下*/
for (i=0;i
{
codenow =code[i]*100+now;
codenow=de(codenow);
now=codenow%100;
decode = (codenow-now)/100;
printf("%d",decode);
}
}
return 0;
}
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). 编码率 r
k n
当k=1时，卷积码编码器的结构包括一个由m个串接的寄存器构成的移位寄存器（成为m级移位寄存器、n个连接到指定寄存器的模二加法器以及把模二加法器的输出转化为穿行的转换开关。
本报告所讲的（2,1,3）卷积码是最简单的卷积码。就是n2，k1，m3的卷积码。每次输入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时 显示以下结果：
当接收到的序列错误时
译码结果如下：
如此时把译码结果输入上文中的编码器程序，即可得到发送方发出的正确的码字：
综上，译码程序能对于正确的较短（2）可以纠错，纠正后，得到正确的卷积码，然后译码得到原码。程序仿真完全正确。
d.模拟一个完整的传输过程： 发送方输入序列11001010 输入到编码器程序中：
得到卷积码输出：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
scanf("%1hd",&input[i]); }
printf("卷积码输出：\n"); for (i=0;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
{
/*00状态路径*/
if ((d00+hanming(0,code[i]))
for (j=0;j
{
lz00[j]=lu00[j];
}
lz00[i]=0;
dz00=d00+hanming(0,code[i]);
}
else
{
for (j=0;j
{
lz00[j]=lu01[j];
}
lz00[i]=0;
dz00=d01+hanming(11,code[i]);
}
/*10状态路径*/
if ((d00+hanming(11,code[i]))
for (j=0;j
{
lz10[j]=lu00[j];
}
lz10[i]=1;
dz10=(d00+hanming(11,code[i]));
}
else
{
for (j=0;j
{
lz10[j]=lu01[j];
}
lz10[i]=1;
dz10=d01+hanming(00,code[i]);
}
/*01状态路径*/
if ((d10+hanming(10,code[i]))
for (j=0;j
{
lz01[j]=lu10[j];
}
lz01[i]=0;
dz01=d10+hanming(10,code[i]);
}
else
{
for (j=0;j
{
lz01[j]=lu11[j];
}
lz01[i]=0;
dz01=d11+hanming(01,code[i]);
}
/*11状态路径*/
if ((d10+hanming(01,code[i]))
for (j=0;j
{
lz11[j]=lu10[j];
}
lz11[i]=1;
dz11=d10+hanming(01,code[i]);
}
else
{
for (j=0;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
{
lu00[m]=lz00[m];
}
for (m=0;m
{
lu10[m]=lz10[m];
}
for (m=0;m
{
lu01[m]=lz01[m];
}
for (m=0;m
{
lu11[m]=lz11[m];
}
}
/*最后一步，在四条路径中选择汉明距离最小的一条*/ error=d00;
p=lu00;
if (d01
{
error=d01;
p=lu01;
}
if (d10
{
error=d10;
p=lu10;
}
if (d11
{
error=d11;
p=lu11;
}
printf("共有%d位错误，译码如下：\n",error); for (m=0;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
{
scanf("%2d",&code[i]);
}
/*长度大于3的 用Viterbi decoder纠错过程如下,*/ if (length>2)
{
correct(code,length);
}
/*长度小于3的直接译码*/
else
{
printf("\n卷积码解码结果：\n");
/*解码过程如下*/
for (i=0;i
{
codenow =code[i]*100+now;
codenow=de(codenow);
now=codenow%100;
decode = (codenow-now)/100;
printf("%d",decode);
}
}
return 0;
}