卷积码的编码及Viterbi译码论文

《信息理论与编码》课程报告

题目______________________________________

姓名______________________________________

学号______________________________________

日期______________________________________

成绩______________________________________

1

卷积码的编码及Viterbi译码

1、 卷积码

卷积码是将k个信息比特编成n个比特，但k和n通常很小，特别适合以串行形式进行传输，时延小。与分组码不同，卷积码编码后的n个码元不仅与当前段的k个信息有关，还与前面的N-1段信息有关，编码过程中互相关联的码元个数为nN。

卷积码的纠错性能随N的增加而增大，而差错率随N的增加而指数下降。在编码器复杂性相同的情况下，卷积码的性能优于分组码。但卷积码没有分组码那样严密的数学分析手段，目前大多是通过计算机进行好码的搜索。 1.1卷积码的结构和描述

1输入1k2N输出1n一、卷积码的一般结构

卷积码编码器的形式如图所示，它包括：一个由N段组成的输入移位寄存器，每段有k个，共Nk个寄存器；一组n个模2和相加器，一个由n级组成的输出移位寄存器。对应于每段k个比特的输入序列，输出n个比特。

由上图可以看到，n个输出比特不仅与当前的k个输入信息有关，还与前（N-1）k个信息有关。通常将N称为约束长度，（有的书的约束长度为Nn）。

常把卷积码记为：（n，k，N），当k=1时，N-1就是寄存器的个数。 二、卷积码的描述

描述卷积码的方法有两类：图解法和解析表示。 图解法包括：树图、状态图、网格图 解析法包括：矩阵形式、生成多项式形式。 以如下的结构说明各种描述方法。

2

c1g10输入m0m1g11m2g12输出c2g20g22

1、树图

根据上图，我们可以得到下表： M0 M1m2 C1c2 状态 1 00 a 11 10 b 0 00 a 00 00 a 1 01 c 00 10 b 0 01 c 11 00 a 1 10 b 01 11 d 0 10 b 10 01 c 1 11 d 10 11 d 0 11 d 01 01 c aabacb0起点1aadcbbcdd我们可以画出如下的树状图：

3

2、状态图

a110000110110011000/011/1b11/000/101/101/010/0cd10/1 3、网格图

例1， 输入为1 1 0 1 1 1 0，输出为： 11 01 01 00 01 10 01

4、生成多项式表示 定义

g1[g10,g11,g12]，g2[g20,g21,g22]

则上述结构为g17，g25，这里用8进制表示g1,g2

m0c1[g10,g11,g12]m1m2，

m0c2[g20,g21,g22]m1m2

22g(D)ggDgD1DD1101112定义

g2(D)g20g21Dg22D21D2

2b,b,b,...M(D)bbDbDb3.... 012012则输入信息的多项式为

3那么我们可以得到输出

C1(D)M(D)g1(D) C2(D)M(D)g2(D)

最终输出是C1(D),C2(D)的相同次数项的排列。

345M(D)1DDDD... 例，输入为1101110…,

C1(D)1D5...

4

C2(D)1DD2D4...

则最后输出为11 01 01 00 01 10… 2、 Viterbi译码算法

2.1 viterbi译码算法简介

viterbi译码算法是一种卷积码的解码算法。缺点就是随着约束长度的增加算法的复杂度增加很快。约束长度N为7时要比较的路径就有条，为8时路径变为12。 (2<<(N-1))。所以viterbi译码一般应用在约束长度小于10的场合中。

先说编码（举例约束长度为7）：编码器7个延迟器的状态（0，1）组成了整个编码器的个状态。每个状态在编码器输入0或1时，会跳转到另一个之中。比如110100输入1时，变成101001（其实就是移位寄存器）。并且输出也是随之而改变的。

这样解码的过程就是逆过程。算法规定t时刻收到的数据都要进行次比较，就是个状态每条路有两条分支（因为输入0或1），同时，跳传到不同的两个状态中去，将两条相应的输出和实际接收到的输出比较，量度值大的抛弃（也就是比较结果相差大的），留下来的就叫做幸存路径，将幸存路径加上上一时刻幸存路径的量度然后保存，这样条幸存路径就增加了一步。在译码结束的时候，从条幸存路径中选出一条量度最小的，反推出这条幸存路径（叫做回溯），得出相应的译码输出。如下图：

2.2硬判决的维特比算法

以1/2速率的卷积码为例说明卷积码的维特比译码算法。

'(d,d,...d)X(x1,y1,x2,y2,...xn,yn)经12n假设输入，经过编码后，编码后的输出

''''''过调制、信道、解调、硬判决后在输出端得到序列于噪声的影响XY。 输入

'Y(x1,y1,x2,y2,...xn,yn)，则由

(d1,d2...dn)共有2n种组合，即X'序列有2n种，我们的任务就是从这2n种序列

中挑出与序列Y的距离最小的序列，该序列在卷积码的格形图上形成一条路径，对应该

5

路径的输入信息比特就是我们最终要译码输出的信息。

维特比算法通过比较和筛选的方法使实现的计算复杂度大大降低。

我们知道，在格形图上，每个状态都有若干条路径进入，那么某个时刻会聚在某个状态的路径与接收序列的距离不同，如果选择最小距离的路径保留，其它路径舍弃，则从每个状态出发的路径只有1条。所以，只需要存储与状态数相等的路径数即可。 大大减小了存储量。

以g17，g25的卷积码为例说明维特比译码算法。 假设输入为110111100，编码输出为11 01 01 00 01 10 01 11 00 假设经过调制、信道、解调、硬判决后输出10 01 01 10 01 10 01 11 00

a00/011/1b11/000/101/101/0d10/1d10/0ba00/011/111/000/101/101/010/110/0cc 输入第1比特，有两条路径

进入状态a，aa（距离1），选择aa（1） 进入状态b，ab（距离1），选择ab（1） 输入第2比特，有4条路径 进入状态a，aaa（距离2） 进入状态b，aab（距离2） 进入状态c，abc（距离3） 进入状态d，abd（距离1） 2.3 软判决的维特比算法

在软判决译码中，路径的距离不是用汉明距离作为比较，而是用欧式距离作为比较，其他的算法与硬判决译码算法没有本质的区别。与硬判决算法相比，软判决译码算法的路径度量采用“软距离”而不是汉明距离。最常采用的是欧几里德距离，也就是接收波形与可能的发送波形之间的几何距离。在采用软距离的情况下，路径度量的值是模拟量，需要经过一些处理以便于相加和比较。因此，使计算复杂度有所提高。除了路径度量以外，软判决算法与硬判决算法在结构和过程上完全相同。一般而言，由于硬判决译码的判决过程损失了信道信息，软判决译码比硬判决译码性能上要好约2 dB 。不管采用软

6

判决还是硬判决，由于Viterbi 算法是基于序列的译码，其译码错误往往具有突发性。 2.4 Viterbi译码C程序如下

#include \"main.h\"

// 微分真值表，第4和第5位用于发送，第0和第0位用于接收 char Diff[] =

{ 0x00, 0x11, 0x23, 0x32, 0x11, 0x00, 0x32, 0x23, 0x22, 0x33, 0x10, 0x01, 0x33, 0x22, 0x01, 0x10 };

// 延迟状态发送矩阵，用于回溯当前状态 char TMBackward[8][4] = { 0, 3, 1, 2, 14 4, 7, 6, 5, 15 1, 2, 0, 3, 16 5, 6, 7, 4, 17 2, 1, 3, 0, 18 7, 4, 5, 6, 19 3, 0, 2, 1, 20 6, 5, 4, 7 21 };

char Tdr, DelayState[16][8], PathState[16][2], DStCurr; int AccDist[8]; // 初始化函数 void Init () {

short i, j; DStCurr = 0; Tdr = 0; AccDist[0] = 0; for (i = 1; i < 8; i++)

AccDist[i] = (1 << 10) / 2;

7

for (j = 0; j < 16; j++) for (i = 0; i < 8; i++) DelayState[j][i] = 0; for (j = 0; j < 16; j++) for (i = 0; i < 2; i++) PathState[j][i] = 0; } // 译码

int Viterbi (int Xi, int Yi, int modd) {

short State[8], Xb, Yb, Nx, Ny, Qx, Qy, Ix, Iy, Id; short c, i, j, tmp1, tmp2, tmp3, tmp4, tt, ss, pp; int Distance[8], dist1, dist0, DataOut, Sht; Mod *Mcurr; Mcurr = (Mod*) modd; Sht = Mcurr->TSht;

// Xi和Yi是输入，首先得到最低距离 for (c = 0; c < 8; c++) {

Xb = (Mcurr->TXs[c]) << 10; Yb = (Mcurr->TYs[c]) << 10; Nx = Mcurr->TNx[c]; Ny = Mcurr->TNy[c]; Qx = (Mcurr->TQx) << 10; Qy = (Mcurr->TQy) << 10; Iy = Ny;

for (i = 0; i < Ny; i++) {

if (Yi < Yb) { Iy = i; break; } Yb += Qy; } Ix = Nx;

for (i = 0; i < Nx; i++)

8

{

if (Xi < Xb) { Ix = i; break; } Xb += Qx; }

Id = Iy * (Nx + 1) + Ix; State[c] = *(Mcurr->St[c] + Id); tmp1 = *(Mcurr->Xc[c] + Id); tmp2 = *(Mcurr->Yc[c] + Id); if (State[c] != SS) {

tmp3 = Xi - (tmp1 << 10); tmp4 = Yi - (tmp2 << 10);

Distance[c] = (int)tmp3 * (int)tmp3 + (int)tmp4 * (int)tmp4; } else {

tmp3 = Xi - (*(Mcurr->Xc[c] + tmp1) << 10); tmp4 = Yi - (*(Mcurr->Yc[c] + tmp1) << 10); dist1 = (int)tmp3 * (int)tmp3 + (int)tmp4 * (int)tmp4; tmp3 = Xi - (*(Mcurr->Xc[c] + tmp2) << 10); tmp4 = Yi - (*(Mcurr->Yc[c] + tmp2) << 10);

Distance[c] = (int)tmp3 * (int)tmp3 + (int)tmp4 * (int)tmp4; State[c] = *(Mcurr->St[c] + tmp2); if (dist1 < Distance[c]) {

Distance[c] = dist1;

State[c] = *(Mcurr->St[c] + tmp1); } } }

9

// 在路径状态0～7中寻找最短距离 dist0 = 0x7FFFFFFF; for (c = 0; c < 4; c++) {

if (Distance[c] < dist0) {

dist0 = Distance[c]; Id = c; } }

DelayState[DStCurr][0] = TMBackward[0][Id]; DelayState[DStCurr][2] = TMBackward[2][Id]; DelayState[DStCurr][4] = TMBackward[4][Id]; DelayState[DStCurr][6] = TMBackward[6][Id]; PathState[DStCurr][0] = State[Id]; dist1 = 0x7FFFFFFF; for (c = 4; c < 8; c++) {

if (Distance[c] < dist1) {

dist1 = Distance[c]; Id = c; } }

DelayState[DStCurr][1] = TMBackward[1][Id-4]; DelayState[DStCurr][3] = TMBackward[3][Id-4]; DelayState[DStCurr][5] = TMBackward[5][Id-4]; DelayState[DStCurr][7] = TMBackward[7][Id-4]; PathState[DStCurr][1] = State[Id]; // 更新距离累加值

10

for (i = 0; i < 8; i++)

Distance[i] = AccDist[i]; for (i = 0; i < 8; i++) {

Id = DelayState[DStCurr][i]; AccDist[i] = Distance[Id] / 8 * 7; }

for (i = 0; i < 8; i+=2) AccDist[i] += dist0 / 8; for (i = 1; i < 8; i+=2) AccDist[i] += dist1 / 8; dist0 = 0x7FFFFFFF; for (i = 0; i < 8; i++) {

if (AccDist[i] < dist0) {

dist0 = AccDist[i]; Id = i; } }

j = DStCurr; for (i = 0; i < 15; i++) {

Id = DelayState[j][Id]; j--; if (j < 0) j = 15; }

tt = PathState[j][Id % 2]; DStCurr++;

if (DStCurr >= 16) DStCurr = 0; ss = tt & ((1 << Sht) - 1);

11

tt = (tt >> Sht) & 0x03; pp = (tt << 2) | Tdr; Tdr = tt;

DataOut = ((Diff[pp] & 0x03) << Sht) | ss; return (DataOut); }

12