论文部分内容阅读
摘 要：本文对卷积码的Viterbi译码方法提出改进算法,以卷积码为例，介绍了Viterbi译码的思想，说明了改进算法的思想，然后通过数学分析的方法得出两者的比较结果，最后给出了MATLAB仿真结果。
关键词：Viterbi译码；改进算法；MATLAB仿真；卷积码
中图分类号：TP391.11文献标识码：A
Improved Algorithm about Viterbi Decoding
GAO MingLiang1, LIU JingHu2
（1. LanZhou JiaoTong University, GanSu LanZhou 730021；Northwest University for Uationalities, GanSu LanZhou 730030；2. LanZhou JiaoTong University, GanSu LanZhou 730021）
Key words: Viterbi decoding；Improved algorithm；Matlab simulation；convolutional codes
卷积码属于信道编码技术中重要的一种，其具有优良的纠检错能力，但是译码运算量的巨大限制了其应用与发展。对卷积码的译码传统采用极大似然数学思想，viterbi译码就是在其基础上发展起来的，其能够极大地减少译码时的运算量。但是其运算量还是比较大的，本文对viterbi译码提出一种改进算法，该算法能够进步极大减少卷积码在译码时候的运算量。
1 Viterbi译码算法思想
Viterbi译码的思想：把汇聚在每个节点上的2条路径的对数似然函数累加值进行比较，然后把具有较大对数似然函数累加值的路径保存下来,称此部分路径为幸存路径,而丢弃另一条路径。经挑选后,第N级只留下2条幸存路径,选出的路径连同它们的对数似然函数累加值一起被存储起来。因每个节点引出2条支路,因此以后各级中路径的延伸都增大一倍，但比较它们的似然函数累加值后,丢弃一半,结果留存下来的路径总数保持常数(等于其状态数)。由此可见,上述译码过程中的基本操作是“加→比→选”。即每级求出对数似然函数累加值,然后两两比较并做出选择。有时会出现2条路径的对数似然函数累加值相等的情形,此时可任意选择其中一条作为“幸存路径”。每一级都有2条幸存路径,则当序列发送完毕后,为判断其最后结果,通常要在网格图的终结处加上一些结束信息。通常结束信息为N-1个已知信息,当然结束信息大于N-1也可以。在此信息到来时,因每一个状态只有与已知发送信息相符的那条支路被延伸,因而在每级比较后,幸存路径减少一半。因此,在接收到N-1个已知信息后,整个网格图中只有惟一的一条幸存路径保留下来。这就是译码所得到的路径,这条译码路径和发送序列是最相似的。从上述卷积码的译码过程可以看出:约束长度为N时,需要存储和计算2（N-1）条路径的参量。由此可见,维特比算法的复杂度随约束长度N按指数形式增长2N。所以维特比算法适合约束长度较小(N≤10)的编码。
下面以（2，1，3）为例具体说明其译码过程。（2，1，3）的编码器结构示意图如下所示：
说明：图中方框表示移位寄存器， 表示模二和。从图中得到输入与输出的关系为：
b,移位移位寄存器b3b2的状态有4种：00、01、10、11，我们用a、b、c、d来分别表示。
现假设发送信息序列为11010，为了使全部信息位能通过编码器，在发送信息序列后面加上了3个零，这样输入编码器的信息序列变为11010000。编码器输出的序列为1101010010110000，相应移位寄存器的状态转移为：a-b-d-c-b-c-a-a,最后回到a。假设接收序列有差错，原输出序列变为：0101011010010001。我们以下图来说明viterbi译码的过程。
图中实线表示实际译码线路，虚线表示当前级上存在的可选线路，线上的数字表示状态转移输出数字。
由于该卷积码的编码约束长度为6，故先选前3段接收序列010101作为标准，与到达第3级的4个节点的8条路径进行对照，逐步算出每条路径与作为标准的接收序列010101之间的累积码距。到达第3级节点a的累积有两条：000000与111011，它们与010101之间的码距分别为3和4。同理，到达节点b的两条路径是000011，111000，它们与010101之间的码距分别为3和4；到达节点c的两条路径是001110，110101，它们与010101之间的码距分别为4和1；到达节点d的两条路径是001101，110110，它们与010101之间的码距分别为2和3。每个节点保留一条码距较小的路径作为幸存路径了，它们分别是000000，000011，110101和001101，它们与010101的对应码距分别是3，3，1和2，这些路径如图所示的到达第3级节点a,b,c和d的4条路径。若将当前节点移到第4级，同样也有8条路径。节点a的两条路径：00000000和11010111；节点b的两条路径是00000011和11010100；节点c的两条路径是：00001110和00110101；节点d的两条路径是：00110110和00001101。将它们与接收序列01010110对比求出累计码距，每个节点仅留下一条码距小的路径作为幸存路径，它们分别是：11010111，11010100，00001110和00110110。逐步推进筛选幸存路径，到第7级时，只要选出到达节点a和c的两条路径即可，因为到达终点a只可能从第7级的节点a或c出发。最后得到了到达终点a的一条幸存路径，即为解码路径，如图中实现所示。根据这条路径，可以得到解码结果为11010000，与发送信息序列一致。
假设接收到的码序列长度为r，现在我们对（2，1，3）卷积码viterbi译码的运算量进行分析。我们注意到两点：第一 译码结束时接收的序列的转移状态应该回归到a状态，而能够回归到a状态的前一状态只有a与c状态，因此在第r/2-1级只算2条路径的码距，第r级只算1条路径的码距。第二 对于（2，1，3）卷积码其约束长度为6，故译码是从第3级开始计算每条路径的码距。然后在第3级一直到第r/2-1级之间，每级均须进行8次码距运算，这样总的码距运算量为(r2-1-3)×8+2=（r-2）×4+2。
2 改进Viterbi译码算法思想
改进viterbi译码的思想：在利用viterbi方法进行译码时，从第3级一直到第r/2-1级之间对于每个状态节点的两个支路进行码距的计算，保留码距比较小的一个作为幸存路径，这样进入到下一节点时候一定会有4条幸存路径。现在我们将每一级的四个节点的8条路径都与接收的码序列进行码距计算，从8个计算的结果中找码距最小者为幸存路径，这样在进入下一节点的时候幸存的路径个数一定就比原来viterbi译码时候要少，从而大大减少了运算量。对于码距都是最小者保留到下一级再判断。同时在计算码距时候，我们只是计算本级所对应的码序列，这样又能够减少一定的运算量。
下面我们再分析改进viterbi译码的运算量。我们先考虑一个最坏的情况：某一级保留下来了2条幸存路径，进入下一级时候4条路径经计算也都是幸存路径，再进入下一级时候这样需要我们计算8次码距，从下一级又开始如此循环。这样在一个周期内需要计算的运算量为：14次。假设接收的码序列长度为r，则需要计算的预算量为：
（
)×12+2=2r-14;余0
（
)×12+2+2=2r-12;余1
（
)×12+2+4=2r-10;余2
然后我们再考虑最好的情况：同样对于第3级我们需要进行8次码重运算，之后除了最后一级外每级都需要进行2次码距的运算。这样对于长度为r接收序列，其运算量为(r2-4)×2+8=r。
对于其他情况运算量均介于上述讨论的关于1和2的运算量之间。例如当r=16时采用viterbi译码需要计算的码距次数为54次；采用改进viterbi译码在最坏的情况下需要计算的码距次数为20次；在最好的情况下需要的计算的码距次数为16次。从而能够看出采用改进的viterbi译码方法能够大大的减少运算量。
现在利用MATLAB计算机工具对上述的改进型viterbi译码进行仿真。路径存储图样和输出图样的样图如下所示:
输出图样路径存储图样
3 改进型viterbi译码的误码分析
对于卷积码的硬判决译码，维特比算法的量度是用汉明距离来表示的。假设发送的是全0路径，并假定在某节点上准备与全0路径比较的路径与全0路径相距d。
若d是奇数，那么当接收序列的差错数小于（d+1）/2时，正确选择全0路径；反之，选择错误路径。所以，选择错误路径的概率为：p(d)=d
k·p·（1-p）
若d为偶数，那么选择错误路径的概率为：
p(d)=d
k·p·（1-p）+d
d/2·p·（1-p）
将所有可能距离的路径的差错概率统加起来，便得到首次差错概率的上边界： p≤ap(d)
在求出p之后，就可以利用下式计算比特差错概率的上边界：
p≤
D=2,B=1,L=1
以(2,1,3)卷积码为例，代入相应的参数，就可以得该卷积码的比特差错概率的上边界：p≤≈2×p
现在利用MATLAB计算机工具对上述的改进型viterbi译码时的误码进行仿真，所得到的维特比错误图样和FER误码率分析图样如下所示：
维特比错误图样FER误码率分析
综上所述，可以看出改进型viterbi译码与viterbi译码相比较具有很大的优点:每一个译码时刻只向存储单元中存入幸存路径的信息,在此存入的是当前时刻此状态中路径度量值译码的信息即输入信息,因而节省了存储空间。译码输出时,只需读出最小路径度量对应的存储器中数值的最高位,因而减少了读寄存器的次数,提高了译码速度,缩短了译码延迟,同时在误码率方面也能够达到与viterbi译码相同的效果。
参考文献：
[1]沈振元.通信系统原理（第二版）[M].西安：西安电子工业出版社，1993.
[2]毛京丽.数据通信原理[M].北京：北京邮电大学出版社，2000.
[3]张森.MATLAB仿真技术与实例应用教程[M].北京：机械工业出版社，2004.
关键词：Viterbi译码；改进算法；MATLAB仿真；卷积码
中图分类号：TP391.11文献标识码：A
Improved Algorithm about Viterbi Decoding
GAO MingLiang1, LIU JingHu2
（1. LanZhou JiaoTong University, GanSu LanZhou 730021；Northwest University for Uationalities, GanSu LanZhou 730030；2. LanZhou JiaoTong University, GanSu LanZhou 730021）
Key words: Viterbi decoding；Improved algorithm；Matlab simulation；convolutional codes
卷积码属于信道编码技术中重要的一种，其具有优良的纠检错能力，但是译码运算量的巨大限制了其应用与发展。对卷积码的译码传统采用极大似然数学思想，viterbi译码就是在其基础上发展起来的，其能够极大地减少译码时的运算量。但是其运算量还是比较大的，本文对viterbi译码提出一种改进算法，该算法能够进步极大减少卷积码在译码时候的运算量。
1 Viterbi译码算法思想
Viterbi译码的思想：把汇聚在每个节点上的2条路径的对数似然函数累加值进行比较，然后把具有较大对数似然函数累加值的路径保存下来,称此部分路径为幸存路径,而丢弃另一条路径。经挑选后,第N级只留下2条幸存路径,选出的路径连同它们的对数似然函数累加值一起被存储起来。因每个节点引出2条支路,因此以后各级中路径的延伸都增大一倍，但比较它们的似然函数累加值后,丢弃一半,结果留存下来的路径总数保持常数(等于其状态数)。由此可见,上述译码过程中的基本操作是“加→比→选”。即每级求出对数似然函数累加值,然后两两比较并做出选择。有时会出现2条路径的对数似然函数累加值相等的情形,此时可任意选择其中一条作为“幸存路径”。每一级都有2条幸存路径,则当序列发送完毕后,为判断其最后结果,通常要在网格图的终结处加上一些结束信息。通常结束信息为N-1个已知信息,当然结束信息大于N-1也可以。在此信息到来时,因每一个状态只有与已知发送信息相符的那条支路被延伸,因而在每级比较后,幸存路径减少一半。因此,在接收到N-1个已知信息后,整个网格图中只有惟一的一条幸存路径保留下来。这就是译码所得到的路径,这条译码路径和发送序列是最相似的。从上述卷积码的译码过程可以看出:约束长度为N时,需要存储和计算2（N-1）条路径的参量。由此可见,维特比算法的复杂度随约束长度N按指数形式增长2N。所以维特比算法适合约束长度较小(N≤10)的编码。
下面以（2，1，3）为例具体说明其译码过程。（2，1，3）的编码器结构示意图如下所示：
说明：图中方框表示移位寄存器， 表示模二和。从图中得到输入与输出的关系为：
b,移位移位寄存器b3b2的状态有4种：00、01、10、11，我们用a、b、c、d来分别表示。
现假设发送信息序列为11010，为了使全部信息位能通过编码器，在发送信息序列后面加上了3个零，这样输入编码器的信息序列变为11010000。编码器输出的序列为1101010010110000，相应移位寄存器的状态转移为：a-b-d-c-b-c-a-a,最后回到a。假设接收序列有差错，原输出序列变为：0101011010010001。我们以下图来说明viterbi译码的过程。
图中实线表示实际译码线路，虚线表示当前级上存在的可选线路，线上的数字表示状态转移输出数字。
由于该卷积码的编码约束长度为6，故先选前3段接收序列010101作为标准，与到达第3级的4个节点的8条路径进行对照，逐步算出每条路径与作为标准的接收序列010101之间的累积码距。到达第3级节点a的累积有两条：000000与111011，它们与010101之间的码距分别为3和4。同理，到达节点b的两条路径是000011，111000，它们与010101之间的码距分别为3和4；到达节点c的两条路径是001110，110101，它们与010101之间的码距分别为4和1；到达节点d的两条路径是001101，110110，它们与010101之间的码距分别为2和3。每个节点保留一条码距较小的路径作为幸存路径了，它们分别是000000，000011，110101和001101，它们与010101的对应码距分别是3，3，1和2，这些路径如图所示的到达第3级节点a,b,c和d的4条路径。若将当前节点移到第4级，同样也有8条路径。节点a的两条路径：00000000和11010111；节点b的两条路径是00000011和11010100；节点c的两条路径是：00001110和00110101；节点d的两条路径是：00110110和00001101。将它们与接收序列01010110对比求出累计码距，每个节点仅留下一条码距小的路径作为幸存路径，它们分别是：11010111，11010100，00001110和00110110。逐步推进筛选幸存路径，到第7级时，只要选出到达节点a和c的两条路径即可，因为到达终点a只可能从第7级的节点a或c出发。最后得到了到达终点a的一条幸存路径，即为解码路径，如图中实现所示。根据这条路径，可以得到解码结果为11010000，与发送信息序列一致。
假设接收到的码序列长度为r，现在我们对（2，1，3）卷积码viterbi译码的运算量进行分析。我们注意到两点：第一 译码结束时接收的序列的转移状态应该回归到a状态，而能够回归到a状态的前一状态只有a与c状态，因此在第r/2-1级只算2条路径的码距，第r级只算1条路径的码距。第二 对于（2，1，3）卷积码其约束长度为6，故译码是从第3级开始计算每条路径的码距。然后在第3级一直到第r/2-1级之间，每级均须进行8次码距运算，这样总的码距运算量为(r2-1-3)×8+2=（r-2）×4+2。
2 改进Viterbi译码算法思想
改进viterbi译码的思想：在利用viterbi方法进行译码时，从第3级一直到第r/2-1级之间对于每个状态节点的两个支路进行码距的计算，保留码距比较小的一个作为幸存路径，这样进入到下一节点时候一定会有4条幸存路径。现在我们将每一级的四个节点的8条路径都与接收的码序列进行码距计算，从8个计算的结果中找码距最小者为幸存路径，这样在进入下一节点的时候幸存的路径个数一定就比原来viterbi译码时候要少，从而大大减少了运算量。对于码距都是最小者保留到下一级再判断。同时在计算码距时候，我们只是计算本级所对应的码序列，这样又能够减少一定的运算量。
下面我们再分析改进viterbi译码的运算量。我们先考虑一个最坏的情况：某一级保留下来了2条幸存路径，进入下一级时候4条路径经计算也都是幸存路径，再进入下一级时候这样需要我们计算8次码距，从下一级又开始如此循环。这样在一个周期内需要计算的运算量为：14次。假设接收的码序列长度为r，则需要计算的预算量为：
（
)×12+2=2r-14;余0
（
)×12+2+2=2r-12;余1
（
)×12+2+4=2r-10;余2
然后我们再考虑最好的情况：同样对于第3级我们需要进行8次码重运算，之后除了最后一级外每级都需要进行2次码距的运算。这样对于长度为r接收序列，其运算量为(r2-4)×2+8=r。
对于其他情况运算量均介于上述讨论的关于1和2的运算量之间。例如当r=16时采用viterbi译码需要计算的码距次数为54次；采用改进viterbi译码在最坏的情况下需要计算的码距次数为20次；在最好的情况下需要的计算的码距次数为16次。从而能够看出采用改进的viterbi译码方法能够大大的减少运算量。
现在利用MATLAB计算机工具对上述的改进型viterbi译码进行仿真。路径存储图样和输出图样的样图如下所示:
输出图样路径存储图样
3 改进型viterbi译码的误码分析
对于卷积码的硬判决译码，维特比算法的量度是用汉明距离来表示的。假设发送的是全0路径，并假定在某节点上准备与全0路径比较的路径与全0路径相距d。
若d是奇数，那么当接收序列的差错数小于（d+1）/2时，正确选择全0路径；反之，选择错误路径。所以，选择错误路径的概率为：p(d)=d
k·p·（1-p）
若d为偶数，那么选择错误路径的概率为：
p(d)=d
k·p·（1-p）+d
d/2·p·（1-p）
将所有可能距离的路径的差错概率统加起来，便得到首次差错概率的上边界： p≤ap(d)
在求出p之后，就可以利用下式计算比特差错概率的上边界：
p≤
D=2,B=1,L=1
以(2,1,3)卷积码为例，代入相应的参数，就可以得该卷积码的比特差错概率的上边界：p≤≈2×p
现在利用MATLAB计算机工具对上述的改进型viterbi译码时的误码进行仿真，所得到的维特比错误图样和FER误码率分析图样如下所示：
维特比错误图样FER误码率分析
综上所述，可以看出改进型viterbi译码与viterbi译码相比较具有很大的优点:每一个译码时刻只向存储单元中存入幸存路径的信息,在此存入的是当前时刻此状态中路径度量值译码的信息即输入信息,因而节省了存储空间。译码输出时,只需读出最小路径度量对应的存储器中数值的最高位,因而减少了读寄存器的次数,提高了译码速度,缩短了译码延迟,同时在误码率方面也能够达到与viterbi译码相同的效果。
参考文献：
[1]沈振元.通信系统原理（第二版）[M].西安：西安电子工业出版社，1993.
[2]毛京丽.数据通信原理[M].北京：北京邮电大学出版社，2000.
[3]张森.MATLAB仿真技术与实例应用教程[M].北京：机械工业出版社，2004.