摘  要：针对噪声信道传输中的特点，本文采用约束列表维特比译码算法对乘积码进行译码。约束维特比算法能够充分利用已知正确的译码信息减少译码复杂度，提高译码效率。列表维特比算法通过增加候选路径提高译码可靠性。因此约束列表维特比算法兼顾了二者的优点，采用SPIHT编码图象数据进行测试，结果表明本文所提出的方法能够很好地提高图像传输质量。
关键词：约束维特比译码 列表维特比译码 图像传输

1 引　言
   在现代数字通信中,特别是高效压缩后的多媒体信号，对于传输质量的要求越来越高，这是因为具有庞大数据量的多媒体信号的压缩通常都采用不定长码(Variable Length Codes)来达到最佳熵编码，当经过噪声信道传输时,某一特定比特的误差将对接收端信号重建产生严重影响[1-3]。因此,多媒体信号传输需要一种纠错性能强大的信道编译码来提高可靠性。
    目前普遍采用的译码方法是Viterbi算法,它是一种最大似然(ML)译码算法，在一定条件下等效于最佳译码[4]。众所周知，Viterbi算法最适用于随机误差的信道。在突发误差情况下，即使是很少的连续错误，Viterbi算法的译码性能也将急剧下降。为了在具有突发差错特性的衰落信道中提高图像传输的性能，文献[5]提出在一个方向上应用RCPC/CRC,在另一个方向上应用Reed-Solomon(RS)码的乘积编码方案。但是一旦译码后的数据包不满足CRC校验，整个包中的数据就被全部丢弃。这就在一定程度上造成了巨大的浪费，因为有可能包中的绝大部分比特是正确的。
为了充分利用接受到的每一位有用信息，提高译码性能，本文把文献[6]提到约束Viterbi（CVA）算法的思想，应用于文献[7]中列表Viterbi（LVA）译码算法，形成约束列表Viterbi算法（CLVA），并结合乘积编码方案，在固定信道误码率（BER）的情况下，对CLVA的译码性能进行分析。

2 乘积编码
   本文采用二维的乘积码作为信道编码，具体结构如图1所示，压缩后图像数据排列组成图1中m行n列的信源码，其行和列均采用递归系统卷积码RSC（Recursive Systematic Convolutional Code）进行编码。之所以采用RSC码，这是由其本身的特点决定的。首先，RSC码拥有于其他广泛应用的卷积码相匹配的编码性能[8]。其次，RSC码是系统码，这不会打乱信源码与信道码之间的界限，从而省去乘积编码所引起的二次冗余。传输过程中先传输信息位，再传输校验位。在信源码和信道码之间，又引入循环冗余检测CRC来检测信源码在接收端是否被正确译码，并把行（列）正确译码的结果作为约束信息供相应的列（行）进行再次译码之用。标志为“double CRC”的部分，是通过双重CRC校验来实现交叉检测的功能，增强行或列CRC校验的可靠性。

上述乘积码总编码速率可由下式计算得出:

其中R1和R2分别对应行和列的编码率，d1、d2分别是行和列所加CRC长度，m和n是信源码的长和宽。从式（1）可以看出，在R一定的情况下，两个方向上可以选择的不同码率，因此这种编码结构是非常灵活的，可以适应多媒体信号在不同信道情况下的传输，况且不同的码率只需简单地通过凿孔矩阵对相应的母码凿孔即可获得。

3 约束列表维特比译码算法
   文献[7]中提到的LVA的根本思想是在ML路径的基础上，寻找L条候选路径，通过CRC检测来确定这L条路径中满足条件的路径，这在一定程度上提高了正确译码的可能性。一旦ML路径出现错误，那么建立在此基础上的候选路径，虽说在路径条数适当的情况下，能够找到正确路径，但是却在无形之中大大增加了路径的条数，增加了计算复杂度，延长了译码时间。为了杜绝这一现象，把约束译码的思想应用于LVA，形成CLVA。
   文献[6]中提到的约束译码的根本思想是充分利用已知正确接收的比特位来约束译码路径。因而必须首先知道接收的序列中哪些位是正确的，但是在实际应用中，很难判断接收到的序列中哪些是正确的。不过可以通过CRC校验来检测译码是否正确，再利用正确的译码结果来约束译码路径。具体方法是根据行（列）CRC来检测相应行（列）译码正确与否，如果正确，则可以把行（列）译码结果作为每列（行）译码的约束条件。
   以文献[6]中的(2,1,2)RSC码为例。假定原始信息{0 1 0 1 1 0 0}经过生成矩阵G＝{7,5}（八进制）RSC编码后的序列是{00 11 01 11 10 01 00}，通过噪声信道后接收到的序列是{00 11  11 1 01 00}，其中有三个比特由于信道噪声的影响发生错误。采用一般VA译码，图2所示，译码序列为{00 11  1 1 01 00}，有四个错误比特，不但没有纠正错误反而多了一个错误，这正说明VA在译码中具有产生突发差错的特点[5]，译码结果是{0 1   1 0 0}，译错了两位。如果通过其对应的列CRC校验确定译码结果中第三位发生错误，尽管不能知道第四位是否正确，但仍可以通过对前一位的约束来修正第四位的错误。具体如下：在t=2和t=3之间代表1的所有向下路径（图3虚线所示）都被强制断开，再根据一般VA来确定ML路径。由图3可知，可得到正确的译码结果{0 1 0 1 1 0 0}。如果知道的正确位越多，断开的路径就越多，计算量就越少，所以约束的引入在提高译码性能的同时，加快了译码速度。
按照上述方法，在ML路径的基础上，把约束应用于LVA中的每一条候选路径，即可得到CLVA。从理论上来讲，CLVA的译码性能要比只找一条ML路径的VA译码性能好，也比相同候选路径下，不加约束的LVA译码性能好。CLVA既具有约束译码速度快的特点，又具有LVA译码准确性高的优点。另外，LVA只有在发现第k-1条路径错误的情况下，才寻找第k条路径，这又可以避免许多不必要的计算。下面用具体的仿真结果进行验证。


4 仿真分析
    仿真中使用的信源是一幅基于SPIHT[9]编码压缩的512×512,8 bits/pixel的Lena灰度图像，图像的压缩比约为60：1。就噪声引发差错的统计规律而言，可分为随机差错信道和突发差错信道两类，因此在仿真中采用代表随机差错信道的二进制对称信道BSC（binary symmetric channel）和代表突发差错信道的GEC（Gilbert-Elliott channel）信道。GEC信道模型有四个参数决定[4]，如图4所示，仿真中采用的具体信道参数见表1，最后一个信道用于900MHZ的GSM移动通讯系统，可以承受60公里的车载速度，每用户33.8kbps的传输速度和BER=0.07的误差率。

  仿真中，均采用图1所示的乘积码结构，具体参数如表2所示。表1中G3信道，由于BER值和连续出错的概率均比其他两个GEC信道高，所以直接采用未凿孔的RSC码来增强抵抗信道噪声干扰的能力。



  BSC信道和GEC信道的仿真结果分别见图5和表3，其中L代表候选路径的数目，PSNR（Peak Signal to Noise Ratio）称为峰值信噪比，它是一种通用的衡量图像重建质量的标准。为了直观说明译码效果的差别，本文给出了G1信道下重建图像（图6），只有PSNR达到31dB以上时，重建的图像才比较接近原始图像。由此可知，在如此高压缩比的情况下，CLVA通过适当的约束和增加候选路径，可使接收重建后的图像达到31dB以上，大幅提高了图像传输质量。




5 结束语
   本文针对Lena图像在噪声信道中传输的特点，研究了CLVA译码性能。仿真结果表明：由于充分利用了已知正确译码比特作为约束条件，在大大降低译码速度和复杂度的同时，使重建图像的质量比Viterbi算法提高了10dB。经过SPIHT算法压缩的图像数据，其比特的重要性在比特流中大致是逐渐递减的，因此接下来的工作可以通过不等误码保护(UEP)策略来进一步提高图像重建的质量。

参 考 文 献
[1]　H Nguyen, P Duhamel, J Brouet, et al. Optimal VLC sequence decoding exploiting additional video stream properties[A] Acoustics, Speech, and Signal Processing[C], Montreal, 2004:621~624.
[2] S S Hemami, T Chang, and R. Lau. Resynchronizing variable-length codes for robust image transmission[A]. Data Compression Conference Proceedings[C], Utah, 1999:529.
[3] T T Cheung, M S So, R S K Cheng, et al. Adaptive unequal error protection and VLC reshuffling for image transmission over wireless channels[J]. Tokyo, Jpn, 2000.
[4] 张宗橙.纠错编码原理和应用[M]. 北京:电子工业出版社, 2003:2~11.
[5] P G Sherwood, K Zeger. Error protection for progressive image transmission over memoryless and fading channels[J]. IEEE Trans. Commun. , 1998, 46:1555~1559.
[6] L Cao, C W Chen. A novel product coding and recurrent alternate decoding scheme for image transmission over noisy channels[J]. IEEE Trans. Commun. , 2003,51:1426~1431.
[7] N Seshadri, C -E W Sundberg. List Viterbi decoding algorithms with applications[J]. IEEE Trans. Commun. ,1994, 42: 313~323.
[8] M Claude Berrou, IEEE, and Alain Glavieux. Near Optimum Error Correcting Coding And Decoding: Turbo-Codes[J]. IEEE Trans. Commun. ,1996, 44:1261~1271.
[9] A Said, W A Pearlman. A new, fast, and efficient image codec based on set partitioning in hierarchical trees[J]. IEEE Transactions on Circuits and Systems for Video Technology, 1996,6:243~250.